Recent Research SummaryPhysicsBased Deep Learning for FiberOptic Communications
Fiberoptic communication links carry virtually all intercontinental data traffic and are often referred to as the Internet backbone. The signal evolution in an optical fiber is implicitly described by the nonlinear Schrödinger equation, which is schematically illustrated in the above figure. In this research, we explore the close connection between the propagation dynamics in optical fiber and deep learning. Our main observation is that the mathematical structure that results from applying spatial discretization methods (in particular the socalled splitstep method) to the nonlinear Schrödinger equation is very similar to the structure of a conventional deep neural network with multiple layers. In a nutshell, the main idea is to obtain a machinelearning model by properly parameterizing the splitstep method and viewing the linear steps as general linear functions, similar to the weight matrices in neural network. Compared to applying large neural networks (e.g., for signal equalization purposes), such physicsbased machinelearning models are appealing because they incorporate important domain knowledge about the propagation dynamics directly into the model structure and obey wellestablished physical principles like symmetry and locality in order to reduce the number of trainable parameters. Moreover, these models also allow us to examine and interpret the learned solutions in order to understand why they perform well.
Capacity via SymmetryEarly work on algebraic codes often paid special attention to the symmetry of the code. With the rise of sparse random codes and iterative decoding, the idea that symmetry alone could lead to good performance started to seem rather implausible. However, in a breakthrough, we have shown that symmetry is actually sufficient to achieve capacity. Specifically, we proved that sequences of errorcorrecting codes with doublytransitive permutation groups achieve capacity on erasure channels under symbolwise maximum a posteriori (MAP) decoding. While the proof only holds for erasure channels, we believe the same result holds for general symmetric channels. This discovery was made independently by two groups: {Santhosh Kumar and myself} and {Shrinivas Kudekar, Marco Mondelli, Eren Sasoglu, and Ruediger Urbanke}. This result solves the open problem of whether or not ReedMuller codes achieve capacity for some rate bounded away from 0 and 1. This was a posted open problem from the 2015 Simons Institute program on Information Theory and the subject of a 1994 conjecture by Dumer and Farrell. It has also been discussed by many others including Arikan, Abbe, Shpilka, and Widgerson. The same result also holds for primitive narrowsense BCH codes and other classes of highly symmetric algebraic codes. Finally, the result for erasure channels has been extended to the quantum erasure channel and sequences of cyclic codes whose blocklengths have the proper numerology (e.g., increasing prime lengths suffice). The conference paper was selected as Best Paper at STOC 2016 and the journal paper received the 2021 Information Theory Society Paper Award.
Simple Proofs of Threshold Saturation for SpatiallyCoupled SystemsFrom 20112012, Kudekar, Richardson, and Urbanke showed that lowdensity paritycheck (LDPC) convolutional codes (or spatiallycoupled codes) can approach capacity on the binary erasure channel (BEC) and binaryinput memoryless symmetric channels. The mechanism behind this spectacular performance is the threshold saturation phenomenon, which is characterized by the beliefpropagation noise threshold of the spatiallycoupled ensemble increasing to an intrinsic noise threshold (e.g., the MAP threhold) defined by the uncoupled system. While these results are quite impressive, the proof technique in the above work leads to long and complicated proofs. Our main result is a simple proof technique that establishes threshold saturation for a general class of spatiallycoupled systems. It is based on potential functions and both simplifies and generalizes most previous results in this area.
Universality of SpatiallyCoupled Codes for Multiuser ProblemsA noisy SlepianWolf problem is considered where two correlated sources are separately encoded and transmitted over two independent binary memoryless symmetric channels. Each channel capacity is assumed to be characterized by a single parameter which is not known at the transmitter. The receiver has knowledge of both the source correlation and the channel parameters. We call a system universal if it retains nearcapacity performance without channel knowledge at the transmitter. Kudekar et al. recently showed that terminated lowdensity paritycheck (LDPC) convolutional codes (a.k.a. spatiallycoupled LDPC ensembles) can have beliefpropagation thresholds that approach their maximum aposteriori thresholds. This was proven for binary erasure channels and shown empirically for binary memoryless symmetric channels. They also conjectured that the principle of spatial coupling is very general and the phenomenon of threshold saturation applies to a very broad class of graphical models. In this research, we derive an area theorem for the joint decoder and empirically show that threshold saturation occurs for this problem. As a result, we demonstrate nearuniversal performance for this problem using the proposed spatiallycoupled coding system. A similar result has also been obtained for the 2user multipleaccess channel.
Combining Queueing and Coding for FiniteState ChannelsThis research considers the relationship between coderate selection and queueing performance for communication systems subject to timevarying channel conditions. While errorcorrecting codes offer protection against channel uncertainties, there exists a natural tradeoff between the enhanced protection of lowrate codes and the rate penalty imposed by additional redundancy. In the limiting regime where codewords are asymptotically long, this tradeoff is wellunderstood and characterized by the Shannon capacity. However, for delaysensitive communication systems and finite block lengths, a complete characterization of this tradeoff is not fully developed. This research offers a new perspective on the queueing performance of communication systems with finite block lengths operating over correlated erasure channels. A rigorous framework that links code rate to overall system performance for random codes is presented and guidelines are identified for coderate selection in delaysensitive systems.
SpatiallyCoupled Codes for ISI ChannelsRecently, it has been observed that terminated lowdensityparitycheck (LDPC) convolutional codes (or spatiallycoupled codes) appear to approach the capacity universally across the class of binary memoryless channels. This is facilitated by the threshold saturation effect whereby the beliefpropagation (BP) threshold of the spatiallycoupled ensemble is boosted to the maximum aposteriori (MAP) threshold of the underlying constituent ensemble. We consider the universality of spatiallycoupled codes over intersymbolinterference (ISI) channels under joint iterative decoding. More specifically, we empirically show that threshold saturation also occurs in this case. This can be observed by identifying the EXIT/GEXIT curves that naturally obey the general area theorem. From these curves, the corresponding MAP and the BP thresholds are then numerically obtained and threshold saturation is observed.
Linear Programming Decoding of LDPC codes on FiniteState ChannelsThis research considers the jointdecoding problem for finitestate channels (FSCs) and lowdensity paritycheck (LDPC) codes. First, the linearprogramming (LP) decoder for binary linear codes is extended to jointdecoding of binaryinput FSCs. In particular, we provide a rigorous definition of LP jointdecoding pseudocodewords that enables evaluation of the pairwise error probability between codewords and pseudocodewords in AWGN. This leads naturally to a provable upper bound on decoder failure probability. If the channel is a finitestate intersymbol interference channel, then the joint LP decoder also has the maximumlikelihood (ML) certificate property and all integervalued solutions are codewords. After deriving these results, we discovered some elements were equivalent to earlier work by Flanagan on linearprogramming receivers. In the second part, we develop an efficient iterative solver for the joint LP decoder discussed in the first part. Next, we extend the approach of iterative approximate LP decoding, proposed by Vontobel and Koetter and analyzed by Burshtein, to this problem. By taking advantage of the dualdomain structure of the jointdecoding LP, we obtain a convergent iterative algorithm for joint LP decoding whose structure is similar to BCJRbased turbo equalization (TE). The result is a joint iterative decoder whose periteration complexity is similar to that of TE but whose performance is similar to that of joint LP decoding. The main advantage of this decoder is that it appears to provide the predictability of joint LP decoding and superior performance with the computational complexity of TE. One expected application is coding for magnetic storage where the required blockerror rate is extremely low and system performance is difficult to verify by simulation.
SoftDecision Decoding via Multiple Decoding Attempts for ReedSolomon CodesOne popular approach to softdecision decoding of ReedSolomon (RS) codes is based on using multiple trials of a simple RS decoding algorithm in combination with erasing or flipping a set of symbols or bits in each trial. We consider a novel framework based on ratedistortion (RD) theory to analyze these multipledecoding algorithms. By defining an appropriate distortion measure between an error pattern and an erasure pattern, the successful decoding condition, for a single errorsanderasures decoding trial, becomes equivalent to distortion being less than a fixed threshold. Finding the best set of erasure patterns also turns into a covering problem that can be solved asymptotically by RD theory. Thus, the proposed approach can be used to understand the asymptotic performanceversuscomplexity tradeoff of multiple errorsanderasures decoding of RS codes. This initial result is also extended a few directions. The ratedistortion exponent (RDE) is computed to give more precise results for moderate blocklengths. Multiple trials of algebraic softdecision (ASD) decoding are analyzed using this framework. Analytical and numerical computations of the RD and RDE functions are also presented. Finally, simulation results show that sets of erasure patterns designed using the proposed methods outperform other algorithms with the same number of decoding trials.
Compressed Sensing and CodingThis work began with the observation that compressed sensing can be seen as realnumber extension of syndrome sourcecoding. Since coding over the real numbers is akin to using a very large alphabet, we applied coding techniques designed for large alphabets to compressed sensing. In particular, we used lowdensity measurement matrices with verification decoding and were able to derive rigorous sparsity thresholds based on density evolution.
Achieving Capacity with Bounded ComplexityThis work provided the first capacityachieving code ensembles for the binary erasure channel whose iterative decoding complexity (per information bit) is bounded as the gap to capacity vanishes. First, we designed irregular repeat accumulate (IRA) codes where all systematic bits were punctured. Later, we found a systematic construction based on accumulate repeat accumulate (ARA) codes.
On the Capacity of FiniteState ChannelsThis work is based on a simple Monte Carlo algorithm that estimates information rates of finitestate intersymbolinterference channels. Before this, the best approach was very complex and yielded only loose bounds. This algorithm (which was also discovered independently by Arnold and Loeliger) stimulated enough interest in this area that, a few years later, these capacities can now be computed to almost any desired accuracy. This work was later extended to provably design irregular LDPC codes that achieve the i.i.d. capacity of some erasure channels with memory.
