Abstract: One of the mostadvanced classes of channel codes is the class of Low Density Parity Check (LPDC)codes, specified by parity check matrix ‘A’. The structured regularconstruction of matrix ‘A’ makes the hardware implementation simpler andreduces decoder complexity. We proposed a novel flexible method to construct structuredregular LDPC codes, based on Gray-code representations in our earlier work. Theconvergence in Sum Product Algorithm depends on the length of cycles in Tannergraph of LDPC codes, i.
e., the decoder performance of these codes can beimproved by avoiding short cycles in A-matrix. In this paper, a method to avoid short cycles is presented. The computationalcomplexities of LDPC codes with column-weight two is low and are efficient fordata storage and partial response channels.
The BER performance of the obtained Gray-code based column-weight twoLDPC codes is reported and it is noticedthat they are comparable to that of QC-LDPC codes and Gallager’s random codes.Keywords: Gray codes, Tanner graph, Short cycles, Girth, Gallagercodes, Column-weight two QC-LDPC codes, BER. I. Introduction In 1962, Robert Gallager proposed Low-DensityParity-Check codes.
The error correcting performance of LDPC codes have beenshown to be close to Shannon’s channel capacity limits 1 2. Unfortunately,Gallager’s remarkable discovery was mostly ignored by coding researchers foralmost 20 years due to the high complexity and memory requirements of theencoding and decoding operations. LDPC codes are rediscovered by David MacKay in1996 3 and he showed their capacity-approaching performance using iterativedecoding techniques. Some of the parameters have to beconsidered in the construction of parity check matrix. Structured constructionreduces hardware complexity and the cost of encoders and decoders 456. Largegirth tends to improve the code performance by speeding up the convergence ofiterative decoding where as small ones especially of length four degrade theperformance 7. Hence, LDPC codes with large girth are preferred.
Differentmethods for constructing LDPC codes with large girth are available inliterature. The minimum distance is an important property of the code whichdictates error rate performance achievable under optimal decoding. Minimumdistance of the code grows linearly with code length, ‘n’ for column weight ?3and logarithmically with column weight of two 1. Thus, the performanceof column-weight two codes is lower comparatively. But, column-weight two codesare more suitable for partial response channels.
They can be employed in thesystems where the inter-symbol-interference (ISI) is prominent. These codes aresuitable for high-speed applications such as magnetic recording or opticalcommunication 8 9. Their structure can usually be exploited for anefficient implementation and they can be encoded with low complexity. They exhibitbetter block error performance 9. Concatenation of Reed-Solomon codes withcolumn-weight two LDPC codes promise better error correcting codes for datastorage applications 10. Thereare several suggested methods for constructing column-weight two LDPC codes.Graphical models are used in 10 to construct girth 10 and 20 codes. However,the suggested graphical models are limited to 1/2 and 1/3 code rates.
In 10, QC-LDPCcodes are constructed but limited to girth 12. In 11, finite geometry is usedto construct a (k,k) quasi-cyclic LDPC code which is then converted intoa (2,k) LDPC code, where k is the row-weight and 2 is thecolumn-weight. The size and the rate of the obtained codes are limited by thefinite geometry approach which does not have flexibility in size and matrix configuration.In 12, the distance graph isconverted into a Tanner graph to construct column-weight two codes.
Inthis paper, we have used our novel flexible algorithm proposed in 13 toconstruct column-weight two structured regular LDPC codes, based on Gray-Code representations(GC-LDPC), without short cycles, and reported their performance with respect todifferent row weights, code rates, code lengths and number of iterations. Therest of the paper is organized as follows: Section II presents the proposedalgorithm for constructing flexible Gray-Code based LDPC codes. Construction ofcolumn-weight two codes with different girths is briefed in sections III and IV.In section V, the proposed algorithm to construct parity check matrix without shortcycles is presented. Bit Error Rate (BER) performance of obtained codes ispresented in Section VI. Section VII has concluding remarks. II. CODE CONSTRUCTION ALGORITHMLet’A’ be the parity-check matrix with ‘m’ parity-check equations, i.
e., A is m ×n matrix, where ‘n’ is the code length. Let’Y’ be the decimal point set of these parity check equations i.e., the elementsof point set ‘Y’ be Y = {Y1, Y2, Y3 ,………., Y?,Y?+1 } where ‘?’ is the row weight of A-matrix.
The elements of thisset can be selected using the following equation:Case 1: For row-weight ‘?’ even: Select Y1=0,point set Y = {Y1, Y2, Y3, ………., Y?,Y?+1 }. The remaining elements of set Y can be selected by using thefollowing equation,Y i + 1 = 2Yi + 1; for i = 1,2,3,…..,?+1Case 2: For row-weight ‘?’ odd: Select Y1=1,point set Y = {Y1, Y2, Y3 ,……….
, Y?}.The remaining elements of set Y can be selected by using the same equation,Y i + 1 = 2Yi + 1; for i = 1,2,3,…..,? The proposed method is based onGallager’s method of construction of LDPC codes. For (?, ?) LDPC code, where’?’ is row-weight and ‘?’ is column-weight, the A-matrix is constructed byconcatenating ‘?’ number of sub-matrices vertically. The transpose of A-matrixis given below:A? = A1, A2, A3,……..,A? Finally, these matrix elements arerepresented in Gray codes.
The proposed algorithm gives the systematic way ofselecting the decimal numbers using the design equation. Table 1 shows thevarious code rates, lengths and densities of A-matrix with column-weight twoand column-weight three codes, for different row-weights. Table 1 Coderates, densities and code lengths under different row-weight ? andcolumn-weight ? Row-weight (?) Density of H Code length (n) Column-weight(?) ? = 2 ? = 3 Code rate (1-?/?) Code-rate (1-?/?) 4 0.200 20 0.500 0.250 5 0.
200 25 0.600 0.400 6 0.142 42 0.666 0.500 7 0.142 49 0.714 0.
571 8 0.111 72 0.750 0.625 9 0.111 81 0.777 0.666 10 0.090 110 0.
800 0.700 III. COLUMN-WEIGHT TWO LDPC CODES WITHGIRTH 8 The parity check matrix ‘A’ ofcolumn-weight two is constructed with two sub-matrices A1 and A2as discussed below:Constructionof A1: The point set ‘Y’ can be selected according to the required row-weight.The elements of this set form the first row of A1.
The subsequentrows of A1 are obtained by cyclically shifting the elements of firstrow, to right, until the first row repeats. Constructionof A2: Theelements of the first row of A1, in reverse order, form the firstrow of A2. The subsequent rows are obtained by cyclically shiftingthe elements of first row, to right, until the first row of A2repeats. The A-matrix isobtained by concatenating these A1 and A2 sub-matricesvertically as, A? = A1,A2Illustration: The sub-matrix A1, for row-weight 4, can be constructed usingthe first five decimal values from the designed point set. The first row of A1is formed directly from the point set.
The second and subsequent rows areobtained by circularly shifting the first and preceding rows to the right,respectively, as shown below: Similarly, A2 is constructed as discussedbefore. The A-matrix is obtained by concatenating these A1 and A2sub-matrices vertically as, A? = A1, A2. The girthobtained with this construction method is eight, which can be verified with thecorresponding structure graph. Codeexpansion:The matrix ‘A’ constructed for anyselected value of ?, is called a ‘base matrix’ of row-weight ‘?’ and it is amatrix with minimum size 2? × ?2. Let the size of this matrix be (m×n).For example, 6´9 is the minimum size of the matrixfor ?=3and it is a base matrix for row-weight 3. The base matrix can be expanded to differentlevels as shown in the Table 2.
In expansion level 1, each ‘1’ in base matrix,is replaced by a corresponding ?´? matrix inwhich it appears and a ‘0’ is replaced by a ?´? zero matrix. The size of expanded matrix in level 1will be (m? × n?). This is the base matrix for expansion level 2. Let the sizeof this matrix be (p × q). In expansion level 2, each ‘1’ in the expandedmatrix of level 1, is replaced by a (p? × q?) block of a base matrix and a ‘0’ isreplaced by zero matrix of same size. The same procedure is followed forexpansion of level 3 and so on. The minimum distance of thecode is at least one more than the ?.
Table 2 Code Sizeand Code Rates for (n, 2, ?) Codewith Girth Eight ? Min. size Level 1 Level 2 Level 3 Code-rate 3 6´9 18´27 54×81 162×243 1/3 5 10×25 50×125 250×625 1,250×3,125 3/5 7 14×49 98×343 686×2,401 4,802×16,807 5/7 IV. CONSTRUCTION OF COLUMN-WEIGHT TWO CODES WITHGIRTH 12 It is reported in 10 that decoding performanceimproves with higher girth. Hence, we modified our proposed algorithm to achievea girth of 12. The proposed method is based on block-wise construction. All theelements of the selected set are arranged in a column to get an elementaryblock C1. Some minor modifications are made on the elementary blockC1 to obtain the other blocks C2 and C3.
Thefollowing steps indicate the construction method: The elements of point set ‘Y’, arranged vertically, form column of C1. The bottom element of C1 is shifted to the top row and other subsequent rows are shifted down to their succeeding rows to obtain block C2. Similarly, the top two elements of C1, are shifted to the bottom and the remaining elements are shifted up, to their preceding rows to obtain block C3. By concatenating three C1 blocks horizontally, the sub-matrix A1 is formed. Similarly, the sub-matrix A2 is obtained by horizontal concatenation of C1, C2 and C3. Finally, the decimal elements of the designed blocks are represented in their corresponding Gray codes to obtain the column-weight two matrix ‘A’ as below: Asan illustration, let required row weight be ?=3 and i=7 for a (n, 2, ?) code.
The elements of blockC1 are, Y = {Y1, Y2, Y3,………., Y7}.Representing these elements in 7-bit Gray code, the size of block C1is 7×7. The elements of block C2 are Y = {Y7, Y1,Y2, … Y6}. Similarly, block C3 is constructed using set Y= {Y3, Y4, … Y1, Y2}.
Matrix ‘A’ isconstructed using these three blocks. The code can be expanded as explained insection III. V. PROPOSED ALGORITHM TOCONSTRUCTA-MATRIX WITHOUT SHORTCYCLES OF 4 AND 6 Shortcycles in parity check matrix: If the number of 1’s thatare in common between any two columns is greater than ‘1’, then 4-length cycleexists. To avoid 4-length cycle, no two rows must share ‘1’ in more than onecolumn. In Figure 1(a), the decimal values Yi in row raand Yi in row rb, belonging to the column cc shouldnot share any other decimal value Yj in any other column cdin the same rows, where 1 ? (i, j) ? ?.
If there are no four edges connecting Yiand Yj as shown, then there is no 4-cycle in the LDPC code. Similarly,Figure 1 (b) shows the shape of a 6-cycle. Here, Yi , Yj and Yk are the integersselected from the design equation to construct A-matrix where 1? (i, j, k) ? ?.(a) (b) Figure 1: Shapes of4-cycle and 6-cycle Figure 2.Shapes of all possible 6-cycles The possible six different shapes of 6-cycles are shown in Figure 2.
IfA-matrix does not contain the set of edges connected in any one of the showntypes, then there is no 6-cycle in the LDPC code. In any of these six differentshapes, it can be observed that, if the length of the longest edge is the sumof the lengths of the smaller edges, then there exists 6-length cycle. In thissection, we prove that the proposed algorithm is free of short cycles of 4 and6.
Lemma-1: If A-matrix is constructed using the proposed method, there is no 4-lengthcycle in ‘A’.Proof: 1 3 7 15 31 1 3 7 15 31 31 1 3 7 15 31 1 3 7 1515 31 1 3 7 A1 15 31 1 3 7 A17 15 31 1 3 7 15 31 1 33 7 15 31 1 3 7 15 31 1 31 15 7 3 1 31 15 7 3 11 31 15 7 3 1 31 15 7 33 1 31 15 7 A2 3 1 31 15 7 A27 3 1 31 15 7 3 1 31 1515 7 3 1 31 15 7 3 1 31 Figure3 Figure 4 In Figure 3, the element ‘1’(Yi) belonging to row 1 and another ‘1’ (Yi) belonging torow 7, both appear in the first column. Let the length of the edge, {Yi, Yi}, connecting these two elements be L1.
It can be noticed that there is no other edge of length L1 connectingany of the same elements Yj, i.e., {Yj, Yj}, that belong to the same rows, namely, 1 and7. Hence, in the proposed construction method, there are no 4-cycles inthe matrix A.
Lemma-2: If a matrix ‘A’is constructed by proposed method,there he longest edge is no 6- cycle in A. Proof:In Figure 4, let{Yi,Yi}be the edge connecting two 1’s in first column and we assume that the edgeconnecting two same elements {Yk, Yk} is the longestlength among the three edges. It can be noticed that, there is no other edgeconnecting any of the two same elements such that the sum of the two edges isequal to the longest edge. In the devised algorithm, there is no other edgethat forms 6-cycle. Thus, there are no short cycles of 6 in the parity checkmatrix. VI. PERFORMANCE SimulationsThe base matrix constructed using Graycode representations results in codes that are too small for practical use. Anexpansion method is therefore needed to get larger codes.
Each “0” entry in thematrix is replaced by a p´p zero sub-matrixand each “1” entry is replaced by a shifted p´p identitysub-matrix. The expanded code is larger than the base matrix by a factor of pand has girth at least that of the base matrix. Using shifted identitysub-matrices simplifies addressing in hardware implementation 14.Decodingperformance of obtained codes was measured using bit-error rate (BER)simulations on AWGN channel with BPSK modulation. The received waveform was demodulatedand decoded by Logarithmic Sum-Product Algorithm. Obtained codes show good BERperformances approaching BER of 10-4 between 3 and 4 dB SNR. Fig. 5 showsperformance of these codes with different number of row weights and differentlengths, but with the same column weights of two.
To demonstrate theerror-correcting performance, we constructed rate-1/2 LDPC codes using theproposed method. For the purpose of comparison, we also constructed Gallager’scodes and QC-LDPC codes. Both codes are good codes for comparison and areconstructed with the same parameters as that of proposed codes.The GC-LDPC codes are obtained using theproposed method. Performance curves of (1600, 2, 4) GC-LDPC codes are comparedto those of QC-LDPC codes 12 of same size and rate and shown in Fig. 6. The obtainedcodes perform similar to QC-LDPC codes up to 4.0 dB SNR.
The advantage of GC-LDPCcodes is their regular structure which makes it much easier to implement theirencoders and decoders.Fig.7 shows the performance comparison of obtained codes with that of (1600, 2, 4)random Gallager’s codes. The BER performance of the proposed codes is veryclose to Gallager’s random codes and QC-LDPC codes. In 15, LDPC codes areconstructed using MacKay encoder which is also comparable to these codes. Fig. 5. GC-LDPC codes for Fig.
6.GC-LDPC and QC-LDPC codes Fig. 7.
GC-LDPC and Gallager’s codes different row weights of samelengths ofsame lengths VII. ConclusionConstruction of structured regularcolumn-weight two LDPC codes based on Gray-code representations is described.These codes are systematically constructed and are generated using a set ofdecimals selected from the defined equation.
The construction method providesthe flexibility in rates and lengths. As the short cycles in parity check matrixdegrade the performance of LDPC decoder, the devised algorithm also provides a method for constructing LDPC codeswithout short cycles 4 and 6. The BER performance of column weight two codes ispresented, and it is noticed that they are comparable to the standard column-weighttwo QC- LDPC codes and Gallager’s random codes.
