The following two important problems are considered in the paper: constructing a low density parity check code on a bipartite graph and rapid encoding of this code. For a given constituent code, the first problem solving is reduced to constructing and investigation of pa- rameters of the matrix describing connections of two vertex subsets of a regular bipartite graph (biadjacency matrix). It is convenient to treat the such matrix as a support-matrix of a code word. We propose a number of constructions that essentially extend the region of accessible parameters of the such matrices including these providing graphs without 4-cycles. Biadjacency matrices of regular bipartite graphs without 4-cycles are treated also as the incidence matrices of symmetric combinatorial configurations. This contributes to understanding and solving of the first problem. The second problem solving leads to search of such support-matrix transforma- tions that maximize the encoding speed and allow us to find non trivial complexity estimates.
The following two important problems are considered in the paper: constructing a low density parity check code on a bipartite graph and rapid encoding of this code. For a given constituent code, the first problem solving is reduced to constructing and investigation of pa- rameters of the matrix describing connections of two vertex subsets of a regular bipartite graph (biadjacency matrix). It is convenient to treat the such matrix as a support-matrix of a code word. We propose a number of constructions that essentially extend the region of accessible parameters of the such matrices including these providing graphs without 4-cycles. Biadjacency matrices of regular bipartite graphs without 4-cycles are treated also as the incidence matrices of symmetric combinatorial configurations. This contributes to understanding and solving of the first problem. The second problem solving leads to search of such support-matrix transforma- tions that maximize the encoding speed and allow us to find non trivial complexity estimates.
The notion of product block codes, whose generator matrix is the tensor product of the constituent generator matrices, is well established. Typically, they have good performance and a decoding algorithm with complexity on the order of the complexity of the decoding algorithms of the constituent codes. There has been much recent attention on the construction of bipartite graphs for low density parity check codes whose parity check matrices are the incidence matrices of right versus left vertices of the graph. The relation of the properties of the incidence matrix to code performance is difficult to establish precisely, although some guidelines are available. Two types of incidence matrix constructions are given here that show promise. In the first instance, a combinatorial construction is given, and, secondly, two types of graph products are considered for their application to LDPC codes.
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.
Abstract Recent breakthroughs in forward error correction, in the form of low-density parity-check(LDPC) and turbo codes, have seen the promise of near Shannon limit information trans-mission realised. The deterministic construction of good codes, for LDPC codes in par-ticular, is currently the subject of intense interest in the research and development com-munity. This thesis adds to this field, developing methods and supporting theory for thedesign of algebraic LDPC codes using incidence structures from combinatorial designs.The benefits of this approach are guaranteed code properties, parameter flexibility, easeof implementation and reduced encoding complexity.In the first part of this thesis Steiner 2-designs and partial geometries are used toprovide systematic constructions of regular LDPC codes with Tanner graphs free of 4-cyclesandwithdeterministiccodeproperties. Drawingextensivelyfromexistingincidencestructures we present new families of algebraic LDPC codes with benefits over traditionalrandomly constructed regular codes, particularly where small-to-medium length codes areconcerned. We focus in particular on exploring the effect of different design propertieson the code parameters by deriving the rate, minimum distance, girth, and stopping setdistribution of LDPC codes from designs.In the second part of this thesis resolvable designs are employed to create regularLDPC codes free of 4-cycles with the parameter flexibility and decoding performance ofrandomly constructed regular LDPC codes. Employing resolvability greatly extends theclass of LDPC codes that can be algebraically constructed. These codes can offer sig-nificant implementation advantages due to the deterministic structure of their resolutionclasses and in some cases their simple encoding.A shortcoming of LDPC codes is their potentially high encoding complexity, whichis generally quadratic in the code length. Finding computationally efficient encodersis therefore critical for LDPC codes to be considered as serious contenders for futuregenerations of forward error correction devices. As a result the purpose of the last part ofthis thesis is to design codes which have the graph-based properties necessary to performwell with sum-product decoding but which are also cyclic or quasi-cyclic and so can beencoded simply. The main focus is regular codes but we also extend our constructionof quasi-cyclic codes to produce irregular LDPC codes with simple linear-time encodingcircuits.
I proposed a new algorithm for the allocation of g- values to the binary vectors. An infinite family of simple graphs in generated by placing copies of polygons in parallel such that degree of each vertex is three. We call them polygon graphs. Since polygon graphs are bipartite therefore they can be used as Tanner graphs to generate low density parity check codes. An incidence structure defined on these polygon graphs in named as polygon semi design. Rows of incidence matrix are reduced by deleting rows from the bottom one by one. These matrices serve as parity check matrices to define low density parity check codes for various dimensions. Size of the stopping sets in the associated Tanner graphs of LDPC codes determine the performance of codes over binary erasure channel. The generated polygon semi regular LDPC codes are simulated and their performance is presented by BER. plots. There exists polygon semi regular LDPC codes e.g. (25,4,17), (49,6,19) etc. The LDPC codes of girth 6 presented by Vera Pless has parameters (25,4,10), (49,6,14). This shows a significant improvement in terms of minimum distance.
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.
In this paper, a new type of edge coloring of graphs together with an algorithm for such an edge coloring is presented to construct some column-weight three low-density parity-check (LDPC) codes whose Tanner graphs are free of 4-cycles. This kind of edge coloring is applied on some well-known classes of graphs such as complete graphs and complete bipartite graphs to generate some column-weight 3 LDPC codes having flexibility in terms of code length and rate. Interestingly, the constructed (3, k)-regular codes with regularities k = 4, 5,..., 22 have lengths n = 12, 20, 26, 35, 48, 57, 70, 88, 104, 117, 140, 155, 176, 204, 228, 247, 280, 301, 330, having minimum block length compared to the best known similar codes in the literature. In addition to linear complexity of generating such parity-check matrices, they can be considered as the base matrices of some quasi-cyclic (QC) LDPC codes with maximum achievable girth 18, which inherit the low-complexity encoder implementations of QC-LDPC codes. Simulation results show that the QC-LDPC codes with large girth lifted from the constructed base matrices have good performances and outperform random codes, progressive edge growth LDPC codes, some finite fields and group rings based QC-LDPC codes and also have a close competition to the standard IEEE 802. 16e (WiMAX) code.