Invited Speakers
Speakers |
Abstract |
|
Erdal Arikan, Bilkent University, Turkey |
|
|
Claude Berrou, Telecom Bretagne, France |
|
|
Richard E. Blahut, University of Illinois, USA |
The Missed Message of the Cutoff Rate |
|
Giovanni Corazza, University of Bologna, Italy |
|
|
Merouane Debbah, Supélec, France |
|
|
David Declercq, Ecole Nationale Supérieure de l'Electronique et de ses Applications, France |
Finite Alphabet Iterative Decoding (FAID) of the (155,64,20) Tanner Code |
|
Muriel Medard, Massachusets Institute of Technology, USA |
Scalar-linear Solvability of Matroidal Networks Associated with Representable Matroids |
|
Andrea Montanari, Stanford University, USA |
Message Passing Algorithms, Random Convex Problems, and the Risk of the LASSO |
|
Ralf Müller, Norwegian University of Science and Technology, Norway |
Iterative Channel Estimation, Detection, and Decoding in Large CDMA Systems |
|
Charbel Abdel Nour, Telecom Bretagne, France |
Designing Practical Diversity Schemes for Next Generation Broadcasting Applications |
|
Li Ping, City University of Hong Kong, Hong Kong |
|
|
Anant Sahai, University of California Berkeley, USA |
|
|
Jossy Sayir, University of Cambridge, UK |
Design of Non-binary Decoders using the Role Model Framework |
|
R. Michael Tanner, University of Illinois at Chicago, USA |
Graph-message Passing: Graphs, Messages, Limitations, and Challenges |
|
Andrew Thangaraj, Indian Institute of Technology Madras, India |
|
|
Yeong-Luh Ueng, National Tsing Hua University, Taiwan |
|
|
Ruediger Urbanke, Ecole Polytechnique Fédérale de Lausanne, Switzerland |
Invited Speakers Abstracts
Author: Erdal Arikan
Title: “From Sequential Decoding to Polar Codes”
Abstract: Polar coding is a technique for constructing provably capacity-achieving codes with low encoding and decoding complexity. This technique has its origin in efforts to improve the cutoff rate of sequential decoding. In this talk, we will recount the history of such efforts by reviewing the works of Elias, Pinsker, Stiglitz, Falconer, Massey, and connecting them to polar coding.
Authors: Claude Berrou and Vincent Gripon
Title: “Coded Hopfield Networks”
Abstract: Error-correcting coding is introduced in associative memories based on Hopfield networks in order to increase the storage diversity as well as the recall robustness in presence of erasures and errors. To achieve this, the graph associated with the classical Hopfield network is transformed into a bipartite graph in which incoming information is linked to orthogonal or quasi-orthogonal codes. Whereas learning is similar to that of classical (i.e. Hebbian) Hopfield networks, memory retrieval relies on error correction decoding which offers strong discrimination properties between the memorized patterns.
Authors: Richard E. Blahut
Title: “The Missed Message of the Cutoff Rate”
Authors: Giovanni E. Corazza, Aravind R. Iyengar, Marco Papaleo, Paul H. Siegel, Alessandro Vanelli-Coralli, Jack K. Wolf
Title: “Latency Constrained Protograph-based LDPC-CC”
Abstract: We propose a windowed decoding scheme for Protograph-based LDPC Convolutional codes (LDPC-CC) that allows us to efficiently trade-off decoding performance for gains in latency. We study the performance of regular LDPC-CC with the windowed decoding scheme. In particular, we show that the class of LDPC-CC proposed in the literature with good Belief Propagation performance is ill-suited for windowed decoding. Further, we establish properties of code ensembles with good windowed decoding performance over erasure channels with and without memory.
Author: Mérouane Debbah
Title: “Learning in Cognitive Networks”
Abstract: In this paper, we develop a framework for bringing intelligence in the devices
in the context of multi-user communications where the transmitter/receiver need to interact with the dynamic environment to find out their optimal strategy The learning problem arises when the devices do not know the quality of service required nor the last actions produced by the other devices. Using the theory of learning games, we study what kind of equilibria and non-equilibria might arise as a consequence of the long-run process of learning.
Authors: David Declercq, Ludovic Danjean, Shiva K. Planjery, Bane Vasic and Erbao Li
Title: “Finite Alphabet Iterative Decoding (FAID) of the (155,64,20) Tanner Code”
Abstract: It is now well established that Iterative Decoding approaches the performance of Maximum Likelihood Decoding of sparse graph codes, asymptotically in the block length. For a finite length sparse code, iterative decoding fails on specific subgraphs generically termed as trapping sets. Trapping sets give rise to error floor, an abrupt degradation of the code error performance in the high signal to noise ratio regime. In this paper, we will study a recently introduced class of quantized iterative decoders, for which the messages are defined on a finite alphabet and which successfully decode errors on subgraphs that are uncorrectable by conventional decoders such as the min-sum or the belief propagation. A case study of the quantized iterative decoding of the (155,64,20) Tanner code will be the focus of the study.
Author: Andrea Montanari
Title: “Message Passing Algorithms, Random Convex Problems, and the Risk of the LASSO”
Abstract: The problem of estimating a high-dimensional vector from a set of linear observations arises in a number of engineering disciplines. It becomes particularly challenging when the underlying signal has some non-linear structure that needs to be exploited. I will present a new class of iterative algorithms inspired by probabilistic graphical models and statistical mechanics ideas, that appear to be asymptotically optimal in specific contexts. The analysis of these algorithms allows to prove remarkably sharp results on the asymptotic behavior of some families of random convex problems. I will in particular discuss the mean square error for LASSO estimation in the context of compressed sensing problems.
Author: Anthony Kim and Muriel Medard
Title: “Scalar-linear Solvability of Matroidal Networks Associated with Representable Matroids”
Abstract: We study matroidal networks introduced by Dougherty et al., who showed that if a network is scalar-linearly solvable over some finite field, then the network is a matroidal network associated with a representable matroid over a finite field. In this paper, we prove the converse. It follows that a network is scalar-linearly solvable if and only if the network is a matroidal network associated with a representable matroid over a finite field and that determining scalar-linear solvability of a network is equivalent to finding a representable matroid over a finite field and a valid network-matroid mapping. As a consequence, we obtain a correspondence between scalar-linearly solvable networks and representable matroids over finite fields. We note that this result, combined with the construction method due to Dougherty et al., can generate potentially new scalarlinearly solvable networks.
Author: Ralf Müller
Title: “Iterative Channel Estimation, Detection, and Decoding in Large CDMA Systems”
Abstract: An iterative receiver for the CDMA multiple-access channel is analyzed in the large-system limit by means of the replica method in multi-path fading. Extrinsic information is fed back from the single-user channel decoders to the multiuser detector and the channel estimator. Both the channel estimator and the multiuser detector can be described by equivalent decoupled single-user systems and analyzed separately. Spectral efficiency is optimized with respect to the required training overhead. Furthermore, a new training method by means of biased signaling is proposed and shown to be superior to training symbols.
Author: Charbel Abdel Nour and Catherine Douillard
Title: “Designing Practical Diversity Schemes for Next Generation Broadcasting Applications”
Abstract: Diversity techniques are known to improve receiver performance under severe channel conditions. Signal Space Diversity (SSD) has been lately adopted into the second generation of the terrestrial digital video broadcasting standard DVB-T2. In this paper, practical applications to diversity schemes with SSD are elaborated. Iterative processing at the receiver side can improve error correcting performance. An extension to Multiple Input Multiple Output (MIMO) schemes under different scenarios is presented. Flexibility in terms of decoding complexity and throughput of the proposed constructions make these diversity schemes particularly suited for next generation mobile standards.
Author: Li Ping
Title: “Joint Diversity Coding, Beam-forming and Water-filling for MIMO-OFDM Systems with Uncertain Channel State Information”
Abstract: Different transmission strategies have been studied for MIMO-OFDM systems with different situations related to the channel state information at transmitter (CSIT), e.g.,
- space-time-frequency coding for channels without CSIT, and
- eigenmode beam-forming and water-filling (i.e., optimized resource allocation) for channels with perfect CSIT.
For the latter case, system performance is usually sensitive to the inaccuracy in CSIT. In this talk, we present a unified scheme applicable to situations with and without CSIT, as well as with partial CSIT. The new scheme is very robust and can best exploit the available knowledge on channel even if it is unreliable. The new scheme involves a linear pre-coding transmitter and a low-cost iterative LMMSE receiver. The pre-coder design is straightforward, which avoids the complexity in using multiple FEC codes in conventional water-filling. Numerical results demonstrate that the new scheme can provide significant performance gain compared with the existing options.
Author: Pulkit Grover, Kristen Ann Woyach, Hari Palaiyanur and Anant Sahai
Title: “An Interference-aware Perspective on Decoding Power”
Abstract: Traditionally, coding has been seen as a way of saving transmit power: capacity-approaching codes require minimal transmitted energy-per-bit given the bandwidth available. But because transmit power is often smaller than decoding power at short distances, many recent wireless system designs continue to use uncoded transmission!
We first observe that in wireless systems that both generate and face interference, coding serves another purpose (assuming interference is treated as noise): it allows a system to support a higher density of transmitter-receiver pairs. Bringing decoding power into the picture, we propose an approach to investigate which code/decoder to use and whether to use any coding at all. It turns out that the code’s gap to capacity determines how high the maximum supportable link density can be when power is plentiful, whereas the code’s decoding complexity governs what link densities can be supported at low power. Various theoretical models have been proposed in order to develop such a system-level understanding. Decoding for expander codes has often taken a message-centric perspective, where an energy cost is paid whenever a message is passed along a wire. Alternatively, one can consider models that are node/iteration-centric where iterations incur a cost per node. It turns out that such iteration-centric perspectives shed interesting light on the required cost scaling as the gap to capacity becomes small. However, we must go beyond that to appropriately abstract and discuss the key implications of decoding circuit issues such as bounded wire density, parasitic resistance and capacitance, leakage current, noisy/quantized messages, etc. on the tradeoffs of interest.
Author: Jossy Sayir
Title: “Design of Non-binary Decoders Using the Role Model Framework”
Abstract:The role model framework was introduced by the author as an approach to numerically optimize decoder components in iterative decoders. Iterative decoder components are normally designed by applying Bayesian theory under an independence assumption that holds for asymptotically large block lengths. However, in order to reduce complexity it is often necessary to depart from the Bayesian design and resort to approximations. There are few theoretical guidelines for these approximations, and methods are compared using performance assessment via simulations. Previous joint work by the author with G. Lechner introduced the concept of post-processing that adds a Bayesian component following the approximation to optimize the performance under the constraints dictated by the choice of the approximation. It is difficult however to obtain a closed form expression for this Bayesian post-processing stage in many relevant cases. The role model framework transforms the problem of finding the Bayesian post-processor into a divergence minimization problem that can be solved numerically using standard convex optimization techniques. In this paper, we will study a number of applications of the role model framework to non-binary iterative decoders and show the performance gains achievable by this method.
Author: R. Michael Tanner
Title: “Graph-Message Passing: Graphs, messages, limitations, and challenges”
Abstract: Error-correction in digital communications broke through long-standing complexity barriers with the advent of turbo-codes and the revival of low-density parity check codes, both using graph-based message-passing decoders. The idea of localized message-passing was used long before in problems from physics, such as the solution to Laplace’s equations with boundary conditions using relaxation algorithms and other problems amenable to finite element analysis. Algorithms to solve such partial differential equations often create a dynamical system intended to converge to the desired solution as a stable point. In many physics problems, the graph is “naturally” determined. In coding, the graph is designed to specify a high-quality code and an effective low-complexity decoding algorithm, requiring graphs with connectivity that poses inherent challenges for decoder architectures. Decoders create non-linear dynamical systems that have the codewords as fixed points. The theories establishing decoder convergence do not yet fully characterize their dynamics. Implementation questions have led to the study of graphs and their communication requirements, and how the required messages can be made simplest to pass and to process. The strategy of designing graphs to solve large-scale systems of equations has found success in other domains, where previously decomposed and suboptimal solutions can be improved integrating message-passing algorithms.
Authors: Andrew Thangaraj, Nanda T. Suresh, Arunkumar Subramanian, Matthieu Bloch and Steven W. McLaughlin
Title: “Coding for Strong and Weak Secrecy in Wiretap Channels”
Abstract: In the wiretap channel model, symbols transmitted through a main channel to a legitimate receiver are observed by an eavesdropper across a wiretapper's channel. The goal of coding for wiretap channels is to facilitate error-free decoding across the main channel, while ensuring zero information transfer across the wiretapper's channel. Strong secrecy requires the total information transfer to the eavesdropper to tend to zero, while weak secrecy requires the per-symbol information transfer to go to zero. In this paper, we will consider coding methods for binary wiretap channels with a noiseless main channel and a BEC or a BSC wiretapper's channel. We will provide conditions and codes that achieve strong and weak secrecy for the BEC case. For the BSC case, we will discuss some existing coding methods and develop additional criteria for secrecy.
Author: Yeong-Luh Ueng
Title: “Interblock Memory for Turbo Trellis Coded Modulation”
Abstract: This paper presents a turbo trellis coded modulation (TTCM) scheme for which the encoding is implemented by serially concatenating a demultiplexer, a multilevel delay processor, and a signal mapper to the encoder of a binary turbo code. Through the delay processor and the signal mapper, interblock memory is introduced between consecutive binary turbo codewords. The proposed TTCM can be decoded based on the demapper and the binary turbo decoder. We can design a TTCM with a rate of 2 bits per 8PSK symbol and a pinch-off limit of 3.08 dB which is only 0.18 dB away from the capacity (2.9 dB).
Author: Ruediger Urbanke
Title: “BP 4 MAP: Better Performance For Many Arduous Problems”
Abstract: A key focus of modern coding theory is to study the interplay between the structure of codes and their decoding performance. E.g., it is well known that for standard irregular ensembles degree-two variable nodes play a crucial role, both in terms of the error floor performance as well as for thresholds. Other important notions of structure in this realm are, e.g., protographs, multi-edge types, or structured permutations.
I will focus on the particular stucture which emerges when codes are “coupled”. This structure was introduced by Zigangirov and Feldstrom in the form of convolutional LDPC codes in 1999. It has since been studied extensively and it is well known that codes of this form have excellent performance. I will quickly review why these codes perform so well. Simplifying slightly, the structure magically ensures that the BP performance for these codes is equal to their MAP performance. I will then survey some of the many extensions within coding, communications, and computer science where the same principle applies and outline some of the many remaining questions in this area.