Abstract A column‐weight LDPC code with the parity‐check matrix is called decomposable if there exists a permutation on the rows of , such that can be decomposed into column‐weight one matrix. In this paper, some variations of edge coloring of graphs are used to construct some column‐weight three decomposable LDPC codes with girths at least six and eight. Applying the presented method on several known classes of bipartite graphs, some classes of column‐weight three decomposable LDPC codes are derived having flexibility in length and rate. Interestingly, the constructed parity‐check matrices based on the proper edge coloring of graphs can be considered as the base matrix of some high rate column‐weight three quasi‐cyclic (QC) LDPC codes with maximum‐achievable girth 20. The paper also leads to a simple characterization of elementary trapping sets of the decomposable codes based on the chromatic index of the corresponding normal graphs. This characterization corresponds to a simple search algorithm finds all possible existing elementary trapping sets in a girth‐6 or girth‐8 column‐weight 3 LDPC code which are layered super set of a short cycle in the Tanner graph of the code. Simulation results indicate that the QC‐LDPC codes with large girths lifted from the constructed base matrices have good performances over AWGN channel.
Abstract A column‐weight LDPC code with the parity‐check matrix is called decomposable if there exists a permutation on the rows of , such that can be decomposed into column‐weight one matrix. In this paper, some variations of edge coloring of graphs are used to construct some column‐weight three decomposable LDPC codes with girths at least six and eight. Applying the presented method on several known classes of bipartite graphs, some classes of column‐weight three decomposable LDPC codes are derived having flexibility in length and rate. Interestingly, the constructed parity‐check matrices based on the proper edge coloring of graphs can be considered as the base matrix of some high rate column‐weight three quasi‐cyclic (QC) LDPC codes with maximum‐achievable girth 20. The paper also leads to a simple characterization of elementary trapping sets of the decomposable codes based on the chromatic index of the corresponding normal graphs. This characterization corresponds to a simple search algorithm finds all possible existing elementary trapping sets in a girth‐6 or girth‐8 column‐weight 3 LDPC code which are layered super set of a short cycle in the Tanner graph of the code. Simulation results indicate that the QC‐LDPC codes with large girths lifted from the constructed base matrices have good performances over AWGN channel.
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.
One of the phenomena that causes high decoding failure rates is trapping sets. Characterization of (a,b) elementary trapping sets (ETSs), their graphical properties and the lower bounds on their size in variable regular LDPC codes with column weights 3, 4, 5 and 6, where a is the size of the ETS and b is the number of degree-one check nodes, have been an interesting subject among researchers. Although progressive-edge-growth method (PEG) to construct LDPC codes free of an specific ETS has been proposed in the literature, it is mostly applied to LDPC codes with column weight 3. In this paper, we focus on constructing QC-LDPC codes with column weight 4 whose Tanner graphs are free of small ETSs. Using coloring the edges of the variable node (VN) graph corresponding to an ETS, we provide the sufficient conditions to obtain QC-LDPC codes with column weight 4, girth 6 and free of (5,b) ETSs, where b≤4, and (6,b) ETs, where b≤2. Moreover, for (4,n)-regular QC-LDPC codes with girth 8, we present a method to remove (7,4) ETSs from Tanner graphs.
In this paper, some well-structured block designs are presented whose incidence matrices can be considered as the mother matrices of some regular and irregular column-weight three quasi cyclic low-density parity-check codes of girth 20. The class of LDPC codes derived from our construction possesses much more flexibility in terms of code length and rate. Moreover, the length of the regular constructed codes with rate at most 0.5 is at least 4.9 times smaller than the length of the voltage graph LDPC codes with the same rate and girth. Simulation results show that the constructed codes outperform progressive edge growth, repeat accumulate and random LDPC codes.
This paper,based on algebra and graph,proposes a method for constructing structured low-density parity-check(LDPC) codes.In this method,the authors design a connected graph with three kinds of special path to ensure that the Tanner graph of the parity check matrix mapped from the connected graph is without short cycles.The construction method results in two classes of(3,k)-regular quasi-cyclic LDPC codes with girth 8 and 12 respectively.Furthermore,by extending this construction method,two classes of LDPC codes with column weight 2,whose girths are respectively 16 and 24,can be obtained.The simulation studies show that these codes can achieve better performance than randomly constructed regular LDPC codes over AWGN channels with iterative decoding.At the BER of 10-5,the new proposed(3,6)-regular(4356,2205) QC-LDPC code performs 1.48dB from the Shannon limit.Moreover,it outperforms the random regular LDPC code of comparable parameters by 0.1dB.For the new proposed structured LDPC codes with column weight 2,they can achieve about 2dB coding gains with respect to the random regular LDPC codes with similar block lengths and code rates.
In this study, a method is presented to construct column weight 3 (CW3) low‐density parity‐check (LDPC) codes using three‐partite graphs. Let G b be a bipartite graph and N g be the set of all minimum length cycles in G b . Using G b and N g , a three‐partite graph denoted G ( G b , N g ), or simply G t , is formed. Let T be the set of length 3 cycles in G t and T a be the set of three element subsets of vertices in G t such that each of these subsets form a subgraph with no edges in G t and has precisely one element in each section of G t . Furthermore, let H be the binary matrix in which the set of rows represent the set of vertices of G t , the columns represent the elements of V := T ∪ T a , and h ij = 1 if and only if the i th vertex of G t belongs to the j th three element set in V . Then H is a CW3 binary matrix. Using the Tanner graph representing H , a recursive construction for CW3 LDPC codes is provided. Applying a simple restriction on T and T a , codes free of length 4 cycles are generated. Euclidean and finite geometry codes are used as the base codes for generating new CW3 LDPC codes. Results are presented which show that these new codes perform well in an additive white Gaussian noise (AWGN) channel with the iterative sum‐product decoding algorithm.
Quasi-cyclic low-density parity-check (QC-LDPC) codes have efficient hardware implementation and excellent correcting performance. However, the existence of trapping sets can affect the decoding performance. In this letter, a novel class of QC-LDPC codes based on integer sequence with column weight 3 and girth at least 8 is proposed. If the numbers in the sequence are different, the QC-LDPC codes free of elementary trapping sets (a,b) witha≤10and${b} \leq $3 can be constructed. The row weight of the parity check matrix can be arbitrary and we give a lower bound of the circulant permutation matrix (CPM) size. Simulation results show that the generated codes have good performance with low error floor over AWGN channels.