Source Polarization-Adjusted Convolutional Codes. T. Kann, S. Kudekar, and M. R. Bloch. In the proceedings of 2023 IEEE International Symposium on Information Theory, Apr.
Design of Low-Density Parity-Check Codes for 5G New Radio. Tom Richardson and Shrinivas Kudekar. In IEEE Communications Magazine: Key Technologies for 5G New Radio, March 2018.
We consider data communication across parallel data buses between chips. Technology scaling has two major effects. The distance between the wires in parallel buses decreases and the voltage swing also decreases. Decreasing distance between wires in the bus increases the coupling capacitance between neighboring wires. Decreasing voltage swing introduces more errors along each wire. As a consequence, the delay and energy dissipation across the bus increases. Schemes to combat the delay and energy dissipation involve constraint-avoidance codes (CAC) and those to improve resilience to noise involve error-correction codes (ECC). State-of-the-art methods CAC encode the information bits and send the parity-bits, generated by the ECC, by providing enough shielding wires between them and the wires carrying information bits. This results in inefficient communication. We provide a novel joint ECC and CAC design which uses much lesser number of wires than state-of-the-art while providing the same delay and energy benefits.
Joint Crosstalk-Avoidance and Error-Correction Coding for Parallel Data Buses. Urs Niesen and Shrinivas Kudekar. Submitted to IEEE Transactions on Information Theory.
A Look-ahead encoder for Parallel Data Buses. Urs Niesen and Shrinivas Kudekar. To be submitted.
In this work we prove that Reed-Muller codes achieve capacity under MAP decoding when transmitting over the binary erasure channel (BEC). The proof technique combines area theorem of iterative decoding and thresholding of monotone functions from computer science.
Reed-Muller Codes Achieve Capacity on the Binary Erasure Channel under MAP Decoding. Shrinivas Kudekar, Marco Mondelli, Eren Sasoglu and Ruediger Urbanke. In the proceedings of the 48th ACM Symposium on Theory of Computing (STOC), Cambridge, USA, 2016. (2016 ACM Symposium on Theory of Computing Best Paper Award)
Comparing the Bit-MAP and Block-MAP Decoding Thresholds of Reed-Muller Codes on BMS Channels. Shrinivas Kudekar, Marco Mondelli, Eren Sasoglu and Ruediger Urbanke. In the proceedings of the International Symposium on Information Theory (ISIT), Barcelona, Spain, 2016.
In this work we consider the analysis and behavior of the belief-propagation decoder when the resources for computation are finite. We show analytically that the belief-propagation threshold degrades gracefully with the saturation of the internal messages to some maximum value. Stability of density evolution is, on the other hand, rather strongly effected by saturation and the asymptotic qualitative effect of saturation is similar to reduction by one of variable node degree.
The Effect of Saturation on Belief Propagation Decoding of LDPC Codes. Shrinivas Kudekar, Tom Richardson, Aravind Iyengar. In the proceedings of International Symposium on Information Theory (ISIT) 2014, Hawaii, USA.
Analysis of Saturated Belief Propagation Decoding of Low-Density Parity-Check Codes. Shrinivas Kudekar, Tom Richardson and Aravind Iyengar. Accepted to IEEE Transactions on Information Theory, 2016.
We describe the fundamental mechanism which explains why "convolutional-like" or spatially coupled codes perform so well. In essence, the spatial coupling of the individual code structure has the effect of increasing the belief-propagation (BP) threshold of the new ensemble to its maximum possible value, namely the maximum-a-posteriori (MAP) threshold of the underlying ensemble. For this reason we call this phenomenon threshold saturation. This gives an entirely new way of approaching capacity. We also demonstrate that the threshold saturation phenomena is quite general and is applicable to many problems in computer and communication science and signal processing. A survey of the research papers on Spatially coupled codes can be found at Spatially Coupled Codes and the principle of Threshold Saturation.
Spatially Coupled Ensembles Universally Achieve Capacity under Belief Propagation. Shrinivas Kudekar, Tom Richardson, Ruediger Urbanke. (Proof for spatially coupled codes achieving capacity with low-complexity BP decoding over general channels)
Threshold Saturation via Spatial Coupling: Why Convolutional LDPC Ensembles Perform so well over the BEC. Shrinivas Kudekar, Tom Richardson, Ruediger Urbanke. IEEE Transactions on Information Theory, February, 2011. (2013 Information Theory Society Best Paper Award)
Threshold Saturation via Spatial Coupling: Why Convolutional LDPC Ensembles Perform so well over the BEC. Shrinivas Kudekar, Tom Richardson, Ruediger Urbanke. In the proceedings of IEEE International Symposium on Information Theory (ISIT), Texas, U.S.A 2010.
Threshold Saturation on BMS Channels via Spatial Coupling. Shrinivas Kudekar, Cyril Measson, Tom Richardson, Ruediger Urbanke. In the proceedings of IEEE 6th International Symposium on Turbo Codes and Iterative Information Processing, Brest, France, 2010.
The Effect of Spatial Coupling on Compressive Sensing. Shrinivas Kudekar and Henry D. Pfister. Invited paper, 48th Annual Allerton Conference on Communication, Control and Computing, 2010, Illinois, U.S.A. (Spatial Coupling in Compressed Sensing)
Threshold Saturation on Channels with Memory via Spatial Coupling. Shrinivas Kudekar and Kenta Kasai. In proceedings of IEEE International Symposium on Information Theory (ISIT), St. Petersburg, Russia, 2011.
Spatially Coupled Codes over the Multiple Access Channel. Shrinivas Kudekar and Kenta Kasai. In proceedings of IEEE International Symposium on Information Theory (ISIT), St. Petersburg, Russia, 2011.
Existence and Uniqueness of GEXIT Curves via the Wasserstein Metric. Shrinivas Kudekar, Tom Richardson, Ruediger Urbanke. Invited paper, IEEE Information Theory Workshop (ITW), Paraty, Brazil, 2011.
Wave-Like Solutions of General One-Dimensional Spatially Coupled Systems. Shrinivas Kudekar, Tom Richardson, Ruediger Urbanke. In preparation.
In our first work we propose and analyze linear programming (LP) based detectors for data transmission over two dimensional ISI channels (magnetic and optical storage). In the second work we propose improved LP decoding of low-density parity-check codes. For both problems we enhance the basic LP decoder by a novel idea. We identify cycles in their graphical models which are frustrated. Then we triangulate the frustrated cycle and add the resulting constraints to the LP decoder thus ensuring that these cycles do not cause problems.
Linear Programming based Receivers for Detection of Two-Dimensional Intersymbol Interference Channels. Shrinivas Kudekar, Jason K. Johnson, Misha Chertkov. In proceedings of IEEE International Symposium on Information Theory (ISIT), St. Petersburg, Russia, 2011.
Improved Linear Programming Decoding using Frustrated Cycles. Shrinivas Kudekar, Jason K. Johnson, Misha Chertkov. In proceedings of IEEE Information Theory Workshop (ITw), Paraty, Brazil, 2011.
Codes based on sparse parity-check matrices have been deployed successfully for efficient transmission of information over a variety of practically important channels. A thorough analysis of sparse parity-check codes on the binary erasure channel (BEC) has given sharp bounds on the performance of the optimal maximum a posteriori (MAP) decoder. This analysis is based on combinatorial methods and cannot be extended to the case of general channels such as additive white Gaussian noise channel. We prove that the replica solution of statistical physics provides a rigorous lower bound on the optimal performance to all sparse graph codes for transmission over general channels. In another part of our work we show that the lower bound is sharp, when considering transmission over the BEC. We accomplish this by extending the recently developed interpolation method of spin glass theory in statistical physics, to a class of sparse codes.
Decay of Correlations for Sparse Graph Error Correcting Codes. Shrinivas Kudekar, Nicolas Macris. In SIAM Journal on Discrete Mathematics, 2010.
Sharp Bounds for MAP Decoding of General Irregular Low-Density Parity Check Codes. Shrinivas Kudekar, Nicolas Macris. In IEEE Transactions on Information Theory, Volume 55, Issue 10, 2009.
Computing the Conditional Entropy Using the Interpolation Method. Satish Babu Korada, Shrinivas Kudekar, Nicolas Macris. Submitted to IEEE Transactions on Information Theory.
Decay of Correlations in Low-Density Parity Check Codes: Low Noise Regime. Shrinivas Kudekar, Nicolas Macris. In the proceedings of IEEE International Symposium on Information Theory (ISIT), Seoul, South Korea, 2009.
Concentration of Magnetization for Linear Block Codes. Satish Babu Korada, Shrinivas Kudekar, Nicolas Macris. In the proceedings of IEEE International Symposium on Information Theory (ISIT), Toronto, Canada, 2008.
Decay of Correlations: An Application to Low-Density Parity Check Codes. Shrinivas Kudekar and Nicolas Macris. In the proceedings of IEEE 5th International Symposium on Turbo Codes and Related Topics, Lausanne, Switzerland, 2008.
Proof of replica formulas in the high noise regime for communication using Low-Density Generator Matrix Codes. Shrinivas Kudekar and Nicolas Macris. In the proceedings of Information Theory Workshop (ITW), Porto, Portugal, 2007.
Exact solution for the Conditional Entropy of Poissonian Low-Density Parity Check Codes over the Binary Erasure Channel. Satish Babu Korada, Shrinivas Kudekar, Nicolas Macris. In the Proceedings of IEEE International Symposium on Information Theory (ISIT), Nice, France, 2007.
Sharp Bounds for MAP Decoding of General Irregular Low-Density Parity Check Codes. Shrinivas Kudekar, Nicolas Macris. In the Proceedings of IEEE International Symposium on Information Theory (ISIT), Seattle, USA, 2006.
We consider lossy compression of a binary symmetric source by means of a low-density generator-matrix code. We derive two lower bounds on the rate distortion function which are valid for any low-density generator-matrix code with a given node degree distribution L(x) on the set of generators and for any encoding algorithm. These bounds show that, due to the sparseness of the code, the performance is strictly bounded away from the Shannon rate-distortion function. In this sense, our bounds represent a natural generalization of Gallager's bound on the maximum rate at which low-density parity-check codes can be used for reliable transmission. Our bounds are similar in spirit to the technique recently developed by Dimakis, Wainwright, and Ramchandran, but they apply to individual codes
Lower Bounds on the Rate-Distortion Function of Individual Low-Density Generator Matrix Codes. Shrinivas Kudekar and Ruediger Urbanke. In the proceedings of IEEE 5th International Symposium on Turbo Codes and Related Topics, Lausanne, Switzerland, 2008.
Learning TCP--Adaptive Congestion Detection for Heterogeneous Networks. Ajay Kumar Singh, Abhishek Jain, Abhay Karandikar, Shrinivas Kudekar and Sachin Katti. In National Conference on Communications 2004, India.
Survey Propagation Inspired Algorithms for Satisfiability. Shrinivas Kudekar, Nicolas Macris and Ruediger Urbanke. LTHC-REPORT-2008-002.
Exact Free Energy of Dilute p-spin Model. Shrinivas Kudekar, Nicolas Macris. LTHC-REPORT-2008-001.