SUNMONTUEWEDTHUFRISAT
Events for November 10, 2006
-
SHORT COURSE on CODING and OPTIMIZATION
Fri, Nov 10, 2006 @ 09:30 AM - 01:00 PM
Ming Hsieh Department of Electrical and Computer Engineering
Conferences, Lectures, & Seminars
SPEAKER: Dr. Pascal Vontobel (HP Labs)ABSTRACT: Whenever information is transmitted across a channel, we have to ensure its integrity against errors. The ground-breaking work of Shannon showed (at least theoretically) how such integrity can be achieved, namely by using an appropriately chosen encoder at the sender side and an appropriately chosen decoder at the receiver side.From a practical point of view, so-called low-density parity-check (LDPC) and turbo codes together with message-passing iterative decoders have become increasingly popular in the last decade. It is fair to say that these codes and decoding algorithms (and ideas related to them) have thoroughly changed much of modern communications. Before this backdrop, a good understanding of these types of communication techniques is obviously highly desirable, especially the understanding of iterative decoding of finite-length codes.Another interesting development in coding theory is the linear programming decoder that was recently proposed by Feldman, Karger, and Wainwright. Simulation results indicate that this decoding algorithm seems to have a similar decoding behavior as iterative decoding.Ideas from optimization theory have arguably played a key role in the two above-mentioned developments. This stems from the fact that decoding can be formulated as an optimization problem. Given that this optimization problem cannot be solved efficiently for good codes, one has to look for suboptimal, yet efficient, algorithms that approximately solve the optimization problem. Both message-passing iterative decoding and linear programming decoding can be seen as successful attempts to formulate such algorithms.Starting from the optimization setup, the first part of this tutorial will introduce message-passing iterative decoding and linear programming decoding and show how they are tightly connected. (This part of the tutorial is planned to be accessible to an broad audience with a general background in communication theory / decision theory.) The second part will go more into the details of certain topics as listed below.First Part: a) Motivation for coding theory, b) Factor graphs and message-passing iterative decoding, c) Linear programming decoding, d) Graph-cover decoding as a way to connect message-passing iterative decoding and linear programming decodingSecond Part: a) Geometry and properties of the fundamental cone, b) Pseudo-weights; lower bounds on the minimum pseudo-weight, c) Low-complexity algorithms for linear programming decoding, d) Bounds on the threshold of linear programming decoding(Based on joint work with Ralf Koetter, UIUC.)BIO: Pascal O. Vontobel received a diploma in electrical engineering in 1997, a post-diploma in information techniques in 2002, and a PhD degree in electrical engineering in 2003, all from ETH Zurich, Switzerland. After being a postdoctoral research associate at the University of Illinois at Urbana-Champaign, the University of Wisconsin-Madison (visiting assistant professor), and at the Massachusetts Institute of Technology, he joined the Information Theory Research Group at Hewlett-Packard Labs in Palo Alto, CA, in the summer of 2006 as a research scientist. For his PhD thesis he was awarded the ETH medal.He is interested in information theory and signal processing in general. More specifically, for his diploma thesis he worked on source coding. Since then, he has mainly looked at the construction of LDPC and turbo codes based on algebraic principles, the calculation and bounding of capacities and information rates of finite-state machine channels, and connections between factor graphs, the summary-product algorithm, and electrical networks. Most recently, he has worked towards an understanding and characterization of the summary-product algorithm on factor graphs with cycles and its connections to linear programming (LP) decoding.Host: Dr. Giuseppe Caire, caire@usc.edu
Location: James H. Zumberge Hall Of Science (ZHS) - 360
Audiences: Everyone Is Invited
Contact: Mayumi Thrasher
-
Fundamental Limits on Wide Bandwidth Signal Acquisition (A Convexity and Optimization Perspective)
Fri, Nov 10, 2006 @ 02:00 PM - 03:00 PM
Ming Hsieh Department of Electrical and Computer Engineering
Conferences, Lectures, & Seminars
SPEAKER: Professor Moe Z. Win, MITABSTRACT: Signal acquisition is a challenging task in wide bandwidth transmission systems. The problem involves searching for a location of sequence-phase within a required accuracy, which is inversely proportional to the transmission bandwidth. To address this, we propose a search technique that takes advantage of multipath, which has long been regarded as deleterious for efficient communication, to aid the sequence acquisition in dense multipath channels. Using optimization and convexity theories, we determine the fundamental limits of achievable mean acquisition times (MATs) for a class of serial-search strategies. In particular, we derive both the minimum and maximum MATs and the conditions for achieving these limits. We prove that a fixed-step serial search, a form of non-consecutive serial search, achieves the near-optimal MAT. Our results also show that the conventional serial search, in which consecutive cells are tested serially, should be avoided since it results in the maximum MAT. We also consider a randomized search strategy and show that the corresponding MAT is at most two times the MAT of the optimal serial search. These results are valid for all signal-to-noise ratio values, regardless of the specifics of the detection layer and the fading distributions.Joint work with Watcharapan Suwansantisuk.Bio: Moe Win is an Associate Professor at the Laboratory for Information & Decision Systems (LIDS), Massachusetts Institute of Technology (MIT). Prior to joining MIT, he spent 5 years at AT&T Research Laboratories and 7 years at the Jet Propulsion Laboratory. As a Presidential Fellow at USC, he received both an M.S. degree in Applied Mathematics and the Ph.D. degree in Electrical Engineering in 1998. His main research interests are the application of mathematical and statistical theories to communication, detection, and estimation problems. Specific current research topics include measurement and modeling of time-varying channels, design and analysis of multiple antenna systems, ultra-wide bandwidth (UWB) communications systems, optical communications systems, and space communications systems.Dr. Win has been involved actively in organizing and chairing a number of international conferences. He is the current chair and past secretary (2002-2004) for the Radio Communications Committee of the IEEE Communications Society. He served as Area Editor (2003-2006) for Modulation and Signal Design and Editor (1998-2006), both for the IEEE TRANSACTIONS ON COMMUNICATIONS. He was Guest-Editor for the 2002 IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS (Special Issue on Ultra-Wideband Radio in Multiaccess Wireless Communications). He received the IEEE Antennas and Propagation Society Sergei A. Schelkunoff Transactions Prize Paper Award in 2003. In 2004, he received the Fulbright Fellowship, the Institute of Advanced Study Natural Sciences and Technology Fellowship, and the Presidential Early Career Award for Scientists and Engineers from the White House. In 2006 he was co-recipient (jointly with Professor Robert A. Scholtz) of the Eric E. Sumner Award, an IEEE Technical Field Award, "for pioneering contributions to ultra-wide band communications science and technology." Professor Win is an IEEE Distinguished Lecturer and elected Fellow of the IEEE, cited "for contributions to wideband wireless transmission."Host: Prof. Robert Scholtz, scholtz@usc.edu
Location: Frank R. Seaver Science Center (SSC) - 319
Audiences: Everyone Is Invited
Contact: Mayumi Thrasher
