The design of efficient, and low complexity, coding and decoding algorithms is a critical component in the optimization of wireless and wire-line networks. Recent years have witnessed the emergence of new powerful paradigms, e.g., belief propagation, as well as the revival of classical approaches, e.g., sequential decoding, for the design of decoding algorithms. This proposal seeks a deeper theoretical foundation for the design and analysis of efficient decoding algorithms, along with the associated code ensembles, by building on this recent progress. The overarching goal of the proposed research is to unify under one framework the class of algorithms that exploit the power of local constraints, e.g., the linear programming or belief propagation decoders and generalization thereof, with the class of algorithms that optimize a global cost function, e.g., tree search decoders. The proposed research benefits from our preliminary results that establish interesting connections between different decoding schemes (as detailed in the sequel). Our results are expected to elucidate the properties of known algorithms and inspire the design of more powerful decoders. Our investigations will start with the traditional point-to-point scenario where the complexity of the model ranges from the simplified binary erasure channel to the challenging multi-path fading channel. In the latter case, our work will target a joint detection and decoding approach and consider, explicitly, the associated signal processing tasks, e.g., the preprocessing stage which will be defined rigorously in the sequel. Our research will then proceed to investigate three distinct categories of multi-user channels. The first thrust will focus on the outage-limited multiple access channel where efficient decoding algorithms that achieve the optimal diversity-multiplexing tradeoff will be pursued. The same line of work will also seek code ensembles and decoding algorithms that achieve the capacity of the compound multiple access channel (CMAC), one of the few examples where the celebrated successive cancellation decoder fails to achieve capacity. The CMAC model captures the essential characteristics of delay-limited multiple access channels with limited transmitter channel state information. The study of the broadcast channel (i.e., downlink) is our second research thrust where low complexity and high performance dirty paper codes and rateless codes will be constructed. Within this context, classical works on tree search source coding will be revisited in order to construct low complexity vector quantization stage for the dirty-paper coding scheme. The third research thrust will be devoted to cooperative channels. Here, our efforts will seek to characterize the diversity-multiplexing tradeoff of the cooperative interference channel along with the associated optimal coding and decoding algorithms. This work will build on the intimate relationship between the CMAC and the interference channel. Finally, inspired by our recent work in the area, novel approaches for cooperative lattice coding and decoding algorithms will be unveiled. The intellectual merit of the proposed research lies in the fundamental nature of the posed questions and the expected contributions to information and coding theories. New bridges between information theory, from one side, and optimization and algebraic number theories, from the other side, will be built. Furthermore, analytical tools, as well as efficient numerical methods, that aid in the design and analysis of decoding algorithms will be pursued. The PIs, with collective expertise in information theory, coding theory, wireless communications, and signal processing, form a qualified team for undertaking the research plan. This project builds on recent results from the PIs' ongoing collaboration. The proposed theoretical research is expected to have a broad impact on the information theory and signal processing communities. Furthermore, the anticipated results will contribute to the design of efficient encoding/decoding algorithms which percolate through many applications (please refer to the support letters from Texas Instruments and ST Microelectronics). On the educational front, graduate students at the two participating institutions will be heavily involved in the research activities.
