arXiv:1612.03279 · Albanian Journal of Mathematics

GRAPH BASED LINEAR ERROR CORRECTING CODES

Monika Polak

Published Jun 15, 2016• 1 citation

Abstract

In this article we present a construction of error correcting codes, that have representation as very sparse matrices and belong to the class of Low Density Parity Check Codes. LDPC codes are in the classical Hamming metric. They are very close to well known Shannon bound. The ability to use graphs for code construction was first discussed by Tanner in 1981 and has been used in a number of very effective implementations. We describe how to construct such codes by using special a family of graphs introduced by Ustimenko and Woldar. Graphs that we used are bipartite, bi-regular, very sparse and do not have short cycles C4. Due to the very low density of such graphs, the obtained codes are fast decodable. We describe how to choose parameters to obtain a desired code rate. We also show results of computer simulations of BER (bit error rate) of the obtained codes in order to compare them with other known LDPC codes.

DOI: 10.51286/albjm/1482081770

Related papers

Low-density parity-check codes

Sarah J. Johnson

Introduction In this chapter we introduce low-density parity-check (LDPC) codes, a class of error correction codes proposed by Gallager in his 1962 PhD thesis 12 years after error correction codes were first introduced by Hamming (published in 1950). Both Hamming codes and LDPC codes are block codes: the messages are broken up into blocks to be encoded at the transmitter and similarly decoded as separate blocks at the receiver. While Hamming codes are short and very structured with a known, fixed, error correction ability, LDPC codes are the opposite, usually long and often constructed pseudo-randomly with only a probabilistic notion of their expected error correction performance. The chapter begins by presenting parity bits as a means to detect and, when more than one is employed, to correct errors in digital data. Block error correction codes are described as a linear combination of parity-check equations and thus defined by their parity-check matrix representation. The graphical representation of codes by Tanner graphs is presented and the necessary graph theoretic concepts introduced. In Section 2.4 iterative decoding algorithms are introduced using a hard decision algorithm (bit flipping), so that the topic is developed first without reference to probability theory. Subsequently the sum–product decoding algorithm is presented. This chapter serves as a self-contained introduction to LDPC codes and their decoding. It is intended that the material presented here will enable the reader to implement LDPC encoders and iterative decoders.

Cambridge University Press eBooksNov 19, 20095 citations

Low-Density Parity-Check Codes

W.E. Ryan, Shu Lin

Low-density parity-check (LDPC) codes are a class of linear block codes with implementable decoders, which provide near-capacity performance on a large set of data-transmission and data-storage channels. LDPC codes were invented by Gallager in his 1960 doctoral dissertation and were mostly ignored during the 35 years that followed. One notable exception is the important work of Tanner in 1981, in which Tanner generalized LDPC codes and introduced a graphical representation of LDPC codes, now called a Tanner graph. The study of LDPC codes was resurrected in the mid 1990s with the work of MacKay, Luby, and others [3–6], who noticed, apparently independently of Gallager's work, the advantages of linear block codes with sparse (low-density) parity-check matrices. This chapter introduces LDPC codes and creates a foundation for further study of LDPC codes in later chapters. We start with the fundamental representations of LDPC codes via parity-check matrices and Tanner graphs. We then learn about the decoding advantages of linear codes that possess sparse parity-check matrices. We will see that this sparseness characteristic makes the code amenable to various iterative decoding algorithms, which in many instances provide near optimal performance. Gallager of course recognized the decoding advantages of such low-density parity-check codes and he proposed a decoding algorithm for the BI-AWGNC and a few others for the BSC. These algorithms have received much scrutiny in the past decade, and are still being studied.

Cambridge University Press eBooksSep 17, 20096 citations

Recursive construction of LDPC codes

Shunliang Mei

To reduce the cycles in the Tanner graph which may affect the code performance,a recursive method to construct low-density parity-check(LDPC) codes was proposed.The method used a parity-check matrix of a short LDPC code as its mother matrix upon which a long code was constructed with circulant permutation matrices.By choosing the circulant permutation matrix parameters properly,the number of cycles having a given length in the Tanner graph of the constructed long codes were equal to or less than that of the short code.Either regular or irregular LDPC codes were constructed.Simulation results show that the LDPC codes constructed by this method have very low error-floor and almost no performance degradation due to their special structure as compared with random LDPC codes.

Journal of Tsinghua University(Science and Technology)Jan 1, 20070 citations

A random construction of LDPC codes using a sub-optimal search algorithm

Seif Shebl, Nawal Ahmed El-Fishawy, Atef Abou Elazm +1 more

In this paper, a method for constructing Low-Density Parity-Check (LDPC) codes of good performance in terms of Bit Error Rate (BER) using a computer search algorithm is presented. First, LDPC codes and encoding along with its Tanner graph representation is described. Then, a detailed description of the proposed construction algorithm is given. A Modified Shortest-Path (MSP) Algorithm of lower complexity is applied to obtain a code graph of the desired structure. The proposed algorithm works directly on the parity-check matrix of the LDPC code. The parity-check matrix of the code is constructed column by column subject to the bit-degree and girth constraints. Using the proposed algorithm, both regular and irregular LDPC codes have been constructed. Furthermore, not only have the girth been improved but also the rate of LDPC codes. Finally, by simulation results the constructed codes were shown to perform well over an additive white Gaussian noise (AWGN) channel.

National Radio Science ConferenceJan 1, 20091 citation

Construction of Cycle-free LDPC Codes

Fengfan Yang

The linear block code is called a binary Low-Density Parity-Check code if whose parity-check matrix is a sparse matrix. For the features of parity-check matrix, a LDPC code can be illustrated by a Tanner graph. Cycles, especially short cycles in the Tanner graph, lead to inefficient decoding and prevent the decoding algorithm from converging to the optimal decoding result. In this paper, a simple algorithm of constructing four-cycle-free regular A(n,d_v,d_c)LDPC codes, d_v3, is introduced. And we analyse the relationship between the performance and the cycle.

Journal of Yunnan University for NationalitesJan 1, 20050 citations

Construction of low density parity check codes without short cycles

Lizhi Wu

With the rapid expansion of communication networks, there has been an increasing demand for efficient and reliable digital data transmission and storage systems. Many efficient codes have been developed. The LDPC code is one of them. In this thesis, the sum-product algorithm is used in the decoding of LDPC codes. Some schemes for encoding LDPC codes have been studied. In particular, two methods of producing regular H matrices have been attempted that include short cycles of length four with code rates of 0.5, and we present three schemes of finding regular H matrices which do not include short cycles of length four with code rate being 0.5. The effect of short cycles in the bipartite graph of regular LDPC codes has been considered. The simulation results show that the BER performances of regular H matrices that do not include short cycles of length four based on BPSK or 8PSK on AWGN channel is better than those of regular H matrices that include short cycles of length four. In conclusion, in order to obtain good performance with LDPC code, one should design H matrix related to bipartite graph without short cycles.

Jan 1, 20030 citations