Description
Low-Density Parity-Check (LDPC) codes have become a standard in contemporary digital wired and wireless communications, and in data storage. The key reasons for the success of LDPC codes are their high resistance to noise and efficient encoding. However, in the regime of very low bit error rate, which is 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. The goal of the project is to develop new methods and techniques for design of efficient LDPC codes, and new decoding techniques, which could potentially lead to more efficient communications and data storage systems. By using collaboration between the groups in Tartu and Bergen, new tools and methods for design of efficient codes could potentially be developed.
Summary of project results
Low-density parity-check (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 their efficient decoding algorithms. Typically, practical decoders for LDPC codes employ iterative message-passing algorithms, which are applied to so-called Tanner graphs, or bipartite graphs determined by the parity-check matrices of the codes. These decoders are very fast and efficient in correcting errors. Optimization of LDPC codes and their decoding algorithms is very important in improving their performance. Yet, unfortunately, our understanding of causes of failures of LDPC codes 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 the project the techniques for construction of more efficient and reliable LDPC codes, new decoding methods for LDPC codes, new analytical tools for LDPC codes, as well as a variety of more general questions related to design and use of graph-based error-correcting codes were studied. A novel method for decoding of LDPC codes on a channel with Gaussian noise was developed. In the proposed method, first, a standard belief-propagation decoder is applied, then a certain number of positions in a data vector is erased by using a combination of a reliability criterion and a set of masks. This gives a system of linear equations, where the list of candidate solutions can be produced. This approach allowed us to improve the efficiency of the decoding. Another idea, which was explored in this project, is to add a number of extra linear equations, without changing the code. These additional equations allow for detecting more inconsistences in the data than before, without significant increase in complexity. By expanding on this idea, we obtained theoretical estimates on the number of additional equations that are to be added. The parameters of an important family of codes called array-based spatially-coupled LDPC codes were investigated. By using computer-based analysis, the parameters of different codes in this family were compared, and some good and bad codes were identified.
Summary of bilateral results
The progress of the project has greatly benefited from the exchange of expertise between Estonian and Norwegian partners. The researchers from Estonia cooperated with the Selmer Center of the University of Bergen, which is one of the main centers for research on coding theory and cryptography in Europe. The Norwegian partner has offered complementary expertise to the researchers of Estonia. The project allowed to establish an active scientific collaboration between Estonian and Norwegian partners and to establish expertise in LDPC codes in the participating countries. A number of research visits between Tartu and Bergen were accomplished. During these visits, the members of the research teams shared their experience and ideas, and carried out joint work. The project served as a basis for training of graduate students and postdoctorants. A number of articles related to the project were published in the scientific literature. The results were also presented in a number of international conferences. The researchers from Estonia and from the Selmer center have organised the 5th Castle Meeting on Coding Theory and Applications in Vihula, Estonia, August 28-31, 2017 – a good initiative since this advertises the project and the joint research of the involved research groups. The organization of an international conference always opens up new collaborations, both for the participants and for the organizers of the conference. This will lead to new future research results.