This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In general, these works should not be reposted without the explicit permission of the copyright holder.
Publications
P. S. Nguyen, A. Yedla, H. D. Pfister, and K. R. Narayanan, “Spatially-coupled codes and threshold saturation on intersymbol-interference channels,” in preparation for IEEE Transactions on Information Theory.
A. Yedla, P. S. Nguyen, H. D. Pfister, and K. R. Narayanan, “Universal codes for multi-terminal problems via spatial coupling,” in preparation for IEEE Transactions on Information Theory.
P. S. Nguyen, H. D. Pfister, and K. R. Narayanan, “On multiple decoding attempts for Reed-Solomon codes: A rate-distortion approach,” in IEEE Transactions on Information Theory, vol. 57, pp. 668-691, Feb. 2011.
A. Yedla, Y. Y. Jian, P. S. Nguyen, and H. D. Pfister, “A simple proof of threshold saturation for coupled vector recursions,” submitted to IEEE Inform. Theory Workshop (ITW), 2012.
A. Yedla, Y. Y. Jian, P. S. Nguyen, and H. D. Pfister, “A simple proof of threshold saturation for coupled scalar recursions,” submitted to The 7th International Symposium on Turbo Codes & Iterative Information Processing (ISTC), 2012. arXiv
P. S. Nguyen, A. Yedla, H. D. Pfister, and K. R. Narayanan, “On the maximum a posteriori decoding thresholds of multiuser systems with erasures,” accepted to IEEE International Symposium on Information Theory (ISIT), Boston, MA, July 2012.
P. S. Nguyen, A. Yedla, H. D. Pfister, and K. R. Narayanan, “Threshold saturation of spatially-coupled codes on intersymbol-interference channels,” accepted to IEEE International Conference on Communications (ICC), Ottawa, Canada, June 2012.
A. Yedla, P. S. Nguyen, H. D. Pfister, and K. R. Narayanan, "Universal codes for the Gaussian MAC via spatial coupling,’’ in Proc. 49th Annual Allerton Conference on Communication, Control, and Computing, Monticello, IL, Sep. 2011. arXiv
P. S. Nguyen, H. D. Pfister, and K. R. Narayanan, “A rate-distortion exponent approach to multiple decoding attempts for Reed-Solomon codes,” in Proc. IEEE International Symposium on Information Theory (ISIT), Austin, TX, June 2010.
P. S. Nguyen, H. D. Pfister, and K. R. Narayanan, “A rate-distortion perspective on multiple decoding attempts for Reed-Solomon codes,” in Proc. 47th Annual Allerton Conference on Communication, Control, and Computing, Monticello, IL, Sep. 2009.
Research highlights
Recently, it has been observed that terminated low-density-parity-check (LDPC) convolutional codes (or spatially-coupled codes) appear to approach the capacity universally across the class of binary memoryless channels. This is facilitated by the “threshold saturation” effect whereby the belief-propagation (BP) threshold of the spatially-coupled ensemble is boosted to the maximum a-posteriori (MAP) threshold of the underlying constituent ensemble.
We consider the universality of spatially-coupled codes over intersymbol-interference (ISI) channels as well as multi-user communications, e.g., the noisy Slepian-Wolf problem and the two-user multiple-access channel (MAC), under joint iterative decoding. More specifically, we empirically show that threshold saturation also occurs for the considered problems. 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.
Since MAP decoder of regular LDPC codes can achieve the “capacity region”, the observed threshold saturation implies that it is possible for spatially-coupled codes to universally approach the whole “capacity region” with BP decoding. For system with erasure noise, some interesting analyses can be further obtained. In addition, the convolutional structure of the codes also allows us to consider a windowed decoder with less decoding complexity but still exhibits good performance.
One popular approach to soft-decision decoding of Reed–Solomon (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 present a novel framework based on rate-distortion (RD) theory to analyze these multiple-decoding algorithms. By defining an appropriate distortion measure between an error pattern and an erasure pattern, the successful decoding condition, for a single errors-and-erasures 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 performance-versus-complexity tradeoff of multiple errors-and-erasures decoding of RS codes.
This initial result is also extended a few directions. The rate-distortion exponent (RDE) is computed to give more precise results for moderate blocklengths. Multiple trials of algebraic soft-decision (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.