Graph-Theoretic Methods and Applications

Graph-Theoretic Methods and Applications
  • LDPC Codes and Spatially Coupled Codes: Theory and Practice.  


Overview: Graph-based codes are extremely popular due to their excellent performance in a variety of settings and relative ease of implementations.

In the asymptotic setting, certain simplifying and averaging assumptions apply; this equips us with the ability to apply celebrated density evolution-like techniques.

In contrast,  finite-length code performance has been plagued by the mathematical sub optimality of the associated message passing decoders. In this setting, conventional code optimization methods are not adequate.

In this research, we tackle both domains. We develop a comprehensive theoretical analysis of several structured code families using tools from enumerative combinatorics, combinatorial graph theory, and matrix analysis. In the finite-length case in particular, we create a new code design methodology centered on the analysis of small graphical constructs that govern code performance in the high reliability regime. Our approach succinctly describes these problematic objects and offers principled ways of eliminating them; our mathematical machinery offers provable properties for the entire finite-length code family at once and thus enables system engineers to use designed codes with confidence. Furthermore, we use this methodology to develop low-cost decoder hardware implementations.

Recent results:

In our recent work, we have developed a new combinatorial framework for the analysis and design of finite-length spatially (SC) coupled codes. In particular, we have demonstrated that SC codes have superior properties to their LDPC counterparts in terms of code performance, by virtue of provably having fewer detrimental absorbing sets.

Current research focuses on extending our combinatorial machinery to a variety of channels and on analysis and design of multi-dimensional graph based codes suitable for ultra dense storage.

Representative publications:

  • B. Amiri, A. Reisizadeh, H. Esfahanizedeh, J. Kliewer, and L. Dolecek, “Optimized Design of Finite-Length Separable Circulant-Based Spatially-Coupled Codes: An Absorbing Set-Based Analysis,” submitted 2016.
  • S. Ranganathan, K. Vakilinia, L. Dolecek, D. Divsalar, and R. Wesel, “Some Results on Spatially-Coupled Protograph LDPC Codes,” ITA 2016.
  • B. Amiri, A. Reisizadeh, J. Kliewer, and L. Dolecek, “Optimized Array-Based Spatially-Coupled LDPC Codes: An Absorbing Set Approach,” in Proc. IEEE International Symposium on Information Theory (ISIT), Hong Kong, June, 2015.
  • D. J. Costello, Jr., L. Dolecek, T. E. Fuja, J. Kliewer, D. G. M. Mitchell, and R. Smarandache, “Spatially Coupled Sparse Codes: Theory and Practice,” IEEE Communications Magazine, vol 52 (7), pp. 168 — 176, July 2014.
  • L. Dolecek, D. Divsalar, Y. Sun and B. Amiri, “Non-Binary Protograph-Based LDPC Codes: Enumerators, Analysis, and Designs,” IEEE Transactions on Information Theory, vol. 60 (7), pp. 3913 — 3941, July 2014. 
  • Y. Toriyama, B. Amiri, L. Dolecek, and D. Markovic, “Logarithmic Quantization Scheme for Reduced Hardware Cost and Improved Error Floor in Non-Binary LDPC Codes,” in Proc. IEEE Globecom, Dec. 2014.
  • B. Amiri, J. Kliewer, and L. Dolecek, “Analysis and Enumeration of Absorbing Sets for Non-Binary Graph-Based Codes,” IEEE Transactions on Communications, vol. 62 (2), pp. 398 — 409, Feb. 2014. 
  • J. Wang, L. Dolecek and R. Wesel, “The Cycle Consistency Matrix Approach to Absorbing Sets in Separable Circulant-Based LDPC Codes,” IEEE Transactions on Information Theory, vol. 59(4), pp. 2293 — 2314, Apr. 2013.