Novel Analysis and Design Tools for Low-Density Parity-Check Codes

Norwegian-Estonian Research Cooperation Programme

This project has received funding from the Norwegian Financial Mechanism 2009-2014 under the grant EMP133.



LDPC codes have become a standard in contemporary digital wired and wireless communications, and in data storage. They are widely used in a broad variety of mobile communications systems, satellite communications, computer hard drives and flash memories. The key reasons for the success of LDPC codes are their high resistance to noise and efficient encoding and, especially, decoding algorithms.

Typically, practical decoders for LDPC codes employ iterative message-passing algorithms, which are applied to so-called Tanner graphs, bipartite graphs describing parity-check matrices of the codes. These decoders are very fast and efficient in correcting errors in the regime of high to medium bit error rate (BER). However, in the regime of very low BER, which is extremely important for data storage and optical communications, the performance is limited by the existence of so-called error floors, associated with the particular representation of the code. This phenomenon is a serious obstacle towards the development of LDPC codes of practical importance for data storage and optical communications.

Optimization of the Tanner graph of an LDPC code was found to be very important in improving performance and weakening the effect of the error floor. Yet, unfortunately, our understanding of causes for poor performance of LDPC codes in the error-floor regime is still rather limited. Today, the optimization of practical LDPC codes is done experimentally, partly due to a limited set of tools in the arsenal of the code designer.

In this project, we aim at design of more efficient and reliable LDPC codes, new decoding methods for LDPC codes, new analytical tools for LDPC codes, as well as at a variety of more general questions related to design and use of graph-based error-correcting codes.

Collaborators

University of Tartu, Estonia University of Bergen, Norway University of Valladolid, Spain

Scientific discussion in Bergen, February 2014

Scientific discussion in Bergen, October 2015

Publications 

Journal papers 

  • I.E. Bocharova, B.D. Kudryashov, V. Skachek, E. Rosnes, O. Ytrehus, ML and Near-ML Decoding Performance of LDPC Codes over BEC: Bounds and Decoding Algorithms, preprint, Aug 2017.

  • A. Barbero, O. Ytrehus, Rate (n-1)/n Systematic MDS Convolutional Codes over GF(2m), submitted, May 2017.

  • I.E. Bocharova, B.D. Kudryashov, V. Skachek, Y. Yakimenka, BP-LED decoding algorithm for LDPC codes over AWGN channels, submitted, May 2017.

  • D.N.K. Jayakody, V. Skachek, B. Chen, Spatially-Coupled LDPC Coding in Cooperative Wireless Networks, EURASIP Journal on Advances in Signal Processing, February 2016.

  • B. Chen, D.N.K. Jayakody, M.F. Flanagan, Low-Density Lattice Coded Relaying with Joint Iterative Decoding, IEEE Transactions on Communications, vol. 63 (12), pp.4824-4837, Oct. 2015.

  • E. Rosnes, M. A. Ambroze, and M. Tomlinson, On the minimum stopping distance of array low-density parity-check codes, IEEE Transactions on Information Theory, vol. 60, no. 9, pp. 5204-5214, Sep. 2014.

  • E. Rosnes, M. Helmling, and A. Graell i Amat, Minimum pseudoweight analysis of 3-dimensional turbo codes, IEEE Transactions on Communications, vol. 62, no. 7, pp. 2170-2182, Jul. 2014.

    • Conference papers 

  • I.E. Bocharova, B.D. Kudryashov, V. Skachek, Y. Yakimenka, Distance Properties of Short LDPC Codes and their Impact on the BP, ML and Near-ML Decoding Performance, Proc. 5th International Castle Meeting on Coding Theory and its Applications (5ICMCTA), Vihula, Estonia, August 2017.

  • D.G.M. Mitchell and E. Rosnes, Edge spreading design of high rate array-based SC-LDPC codes, Proc. IEEE International Symposium on Information Theory (ISIT), Aachen, Germany, June 2017.

  • I.E. Bocharova, B.D. Kudryashov, V. Skachek, Y. Yakimenka, Average Spectra for Ensembles of LDPC Codes and Applications, Proc. IEEE International Symposium on Information Theory (ISIT), Aachen, Germany, June 2017.

  • I.E. Bocharova, B.D. Kudryashov, V. Skachek, Performance of ML Decoding for Ensembles of Binary and Nonbinary Regular LDPC Codes of Finite Lengths, Proc. IEEE International Symposium on Information Theory (ISIT), Aachen, Germany, June 2017.

  • Y. Yakimenka and E. Rosnes, On failing sets of the interval-passing algorithm for compressed sensing, 54th Annual Allerton Conf. Commun., Control, and Computing, Monticello, IL, USA, Sep. 2016.

  • A. Rajaram, D.N.K. Jayakody, V. Skachek, Store-Then-Cooperate: Energy Harvesting Scheme in Cooperative Relay Networks, Proc. International Symposium on Wireless Communication Systems (ISWCS), Poznan, Poland, Sept. 2016.

  • D. N. K. Jayakody and E. Rosnes, Spatially-coupled LDPC coding in threshold-based lossy forwarding scheme, Proc. 84th IEEE Veh. Tech. Conf. (VTC-Fall), Montreal, Canada, Sep. 2016.

  • I.E. Bocharova, B.D. Kudryashov, E. Rosnes, V. Skachek, O. Ytrehus, Wrap-Around Sliding-Window Near-ML Decoding of Binary LDPC Codes over the BEC, Proc. 9th International Symposium on Turbo Codes and Iterative Information Processing (ISTC), Brest, France, Sept. 2016.

  • E. Rosnes and M. Helmling, On adaptive linear programming decoding of nonbinary linear codes over prime fields, Proc. 9th International Symposium on Turbo Codes and Iterative Information Processing (ISTC), Brest, France, Sept. 2016.

  • I.E. Bocharova, B.D. Kudryashov, V. Skachek, Y. Yakimenka, Low Complexity Algorithm Approaching the ML Decoding of Binary LDPC Codes, Proc. IEEE International Symposium on Information Theory (ISIT), Barcelona, Spain, July 2016.

  • E. Rosnes and M. Helmling, Constructing valid convex hull inequalities for single parity-check codes over prime fields, Proc. IEEE International Symposium on Information Theory (ISIT), Barcelona, Spain, July 2016.

  • D.N.K. Jayakody, V. Skachek, B. Chen, Spatially-Coupled LDPC Coding in Cooperative Wireless Networks, IEEE Wireless Communications and Networking Conference (WCNC), Qatar, April 2016.

  • E. Rosnes and M. Helmling, On adaptive linear programming decoding of linear codes over GF(8), Proc. Information Theory and Applications (ITA), La Jolla, CA, Jan.-Feb. 2016.

  • D.K. Nguyen, D.N.K. Jayakody, H. Ochi, Soft Information Relaying Scheme with Transceiver Hardware Impairments in Cognitive Networks, Proc. 10th International Conference on Information, Communications and Signal Processing (ICICS), Singapore. Dec 2-4, 2015.

  • I. Kubjas, V. Skachek, Data Dissemination Problem in Wireless Networks, Proc. 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton, IL, USA, October 2015.

  • E. Rosnes, A. Graell i Amat, Analysis of spatially-coupled counter braids, Proc. IEEE Information Theory Workshop (ITW), Jeju, South Korea, October 2015.

  • E. Rosnes, On the minimum distance of array-based spatially-coupled low-density parity-check codes, Proc. IEEE Internatonal Symposium on Information Theory (ISIT), Hong Kong, China, Jun. 2015

  • D.N.K. Jayakody, J. Li, Optimum Power Allocation for LDPC coded Soft Forwarding Scheme in Wireless Networks, Proc. 81st IEEE Vehicular Technology Conference, VTC2015-Spring, Glasgow, UK, May 2015.

  • Y. Yakimenka, V. Skachek, Refined Upper Bounds on Stopping Redundancy of Binary Linear Codes, Proc. IEEE Information Theory Workshop (ITW), Jerusalem, Israel, April - May 2015.

  • E. Rosnes and M. Helmling, On adaptive linear programming decoding of ternary linear codes, Proc. IEEE Information Theory Workshop (ITW), Jerusalem, Israel, April - May 2015.

  • A. Barbero, O. Ytrehus, A Coding-based Approach to Robust Shortest-path Routing, Proceedings of the 4th International Castle Meeting on Coding Theory and its Applications (4ICMCTA), Pamela, Portugal, 2015.

  • E. Rosnes, Spatially-coupled counter braids, Proc. IEEE Information Theory Workshop (ITW), Hobart, Australia, Nov. 2014, pp. 188-192.

  • M. Helmling, E. Rosnes, S. Ruzika, and S. Scholl, Efficient maximum-likelihood decoding of linear block codes on binary memoryless channels, Proc. IEEE International Symposium on Information Theory (ISIT), Honolulu, HI, Jun./Jul. 2014, pp. 2589-2593.

  • E. Rosnes, M. A. Ambroze, and M. Tomlinson, An upper bound on the minimum distance of array low-density parity-check codes, Proc. IEEE International Symposium on Information Theory (ISIT), Honolulu, HI, Jun./Jul. 2014, pp. 3155-3159.

    • Theses 

  • A. Rajaram, Energy Harvesting in Cooperative Communications, Master's Thesis, University of Tartu, June 2016.

  • Y. Yakimenka, Optimization of Parity-Check Matrices of LDPC Codes, Master's Thesis, University of Tartu, June 2014.

  • I. Kubjas, Set reconcilliation, Master's Thesis, University of Tartu, June 2014.


    • Other activities 

    Poster presenations 

  • I. Kubjas, Data dissemination problem in wireless networks, IEEE European School of Information Theory, Zandvoort, The Netherlands, April 2015.

  • Y. Yakimenka, Refined Upper Bounds on Stopping Redundancy of Binary Linear Codes, SP Coding School, Campinas, Brazil, January 2015.

  • I. Kubjas, Set reconcilliation, IEEE European School of Information Theory, Tallinn, Estonia, April 2014.


    • Selected talks 

  • E. Rosnes, Spatially-Coupled Counter Braids, New Mexico State University, Las Cruces, NM, USA, 28 October 2016.

  • D.N.K. Jayakody, Network-Coded Soft Forwarding-based Distributed LDPC Coding Scheme, Design and Application of Random Network Codes (DARNEC'15), Istanbul, Turkey, 2-4 Nov. 2015.

  • A. Barbero and O. Ytrehus, Network coding for cyclic networks, Mathematical Coding Theory in Multimedia Streaming, BIRS, Banff, Canada, 2015.

  • A. Barbero and O. Ytrehus, Message merging for routing, Recent Advances in Practical Network Coding and Distributed Storage, COST Action IC1104 workshop, Novi Sad, Serbia, June 2015.

  • I. Kubjas, Data dissemination problem in wireless networks, Recent Advances in Practical Network Coding and Distributed Storage, COST Action IC1104 workshop, Novi Sad, Serbia, June 2015.

  • D.N.K. Jayakody and J. Li, A Soft Network Coded Forwarding Scheme for Multiple Access Relay Systems, 13th COST Action IC1004 Workshop, Valencia, Spain, 5-7 May 2015.

  • M. Helmling, E. Rosnes, and S. Ruzika, On maximum-likelihood decoding of polar codes, invited talk at IEEE Information Theory Workshop (ITW), Jerusalem, Israel, April-May 2015.

  • E. Rosnes and A. Graell i Amat, On the analysis of spatially-coupled counter braids, Information Theory and Applications (ITA), San Diego, CA, USA, February 2015.

  • D.N.K. Jayakody, Coded Cooperative Communication, Workshop on Algebra, Number Theory, and their Applications to Communications and Computing (ANTA), Aalto University, Finland, January 2015.

  • D.N.K. Jayakody, A Soft Network Coded Multilevel Forwarding Scheme for Multiple Access Relay Systems, Centre for Wireless Communications, University of Oulu, Finland, January 2015.

  • Y. Yakimenka, Optimisation of parity-check matrices of LDPC codes, Joint Estonian-Latvian Theory Days, Ratnieki, Latvia, October 2014.

  • I. Kubjas, Data exchange over arbitrary wireless networks, Joint Estonian-Latvian Theory Days, Ratnieki, Latvia, October 2014.


    • Conference organization 

    5-th International Castle Meeting on Coding Theory and Applications, Vihula Manor, Estonia, August 28th -- 31st, 2017.


    Contact: Vitaly Skachek
    Institute of Computer Science
    University of Tartu
    J. Liivi 2, Tartu 50409, Estonia
    Phone: +372 737 6418
    Vitaly (dot) Skachek (at) ut (dot) ee