Constructing LDPC Codes from Partition and Latin-Style Splicing
Guohua Zhang Yulin Hu Qinwei He
cs.IT math.IT





























































































A novel method guaranteeing nondecreasing girth is presented for constructing longer low-density parity-check (LDPC) codes from shorter ones. The parity-check matrix of a shorter base code is decomposed into N (N≥ 2) non-overlapping components with the same size. Then, these components are combined together to form the parity-check matrix of a longer code, according to a given N× N Latin square. To illustrate this method, longer quasi-cyclic (QC) LDPC codes are obtained with girth at least eight and satisfactory performance, via shorter QC-LDPC codes with girth eight but poor performance. The proposed method naturally includes several well-known methods as special cases, but is much more general compared with these existing approaches.




LDPC codes, Quasi-cyclic, Girth, Latin square, Greatest common divisor




Constructing LDPC Codes from Partition and Latin-Style Splicing
    Guohua Zhang, 
        Yulin Hu, 
        and Qinwei He 
Guohua Zhang is with the China Academy of Space Technology, Xi'an, People's Republic of China. 


Email: zhangghcast@163.com
Yulin Hu and Qinwei He are with the Institute for Theoretical Information Technology, RWTH Aachen university, Aachen, Germany.

    May 3, 2018
=========================================================================================================================================================================================================================================================================================================================















§ INTRODUCTION
 QC-LDPC codes have gained significant attention, due to their strength of facilitating simple encoders and decoders. It is generally accepted <cit.><cit.> that girth is one important factor (among others), affecting performance of LDPC codes.
There have been a large number of specific methods for constructing QC-LDPC codes with decent or large girth. However, except for a couple of methods, such as <cit.><cit.><cit.>, general skills to obtain longer codes with nondecreasing girth from shorter ones are rarely available. In this Letter, a new such method is proposed to design longer compound QC-LDPC codes from shorter base codes, while the girth of former is equal to or greater than that of the latter. On the basis of some shorter codes (from greatest-common-divisor, viz.,  GCD method <cit.>) with girth eight but unsatisfactory performance, the resultant longer codes not only possess a girth at least eight but also outperform some well-known specific classes of QC-LDPC codes. The strength of the new method lies in simplicity (using only simple operations of partition and splicing) and flexibility (applicable to any base code).



§ PRELIMINARIES
 An LDPC code is defined as the null space of a sparse parity-check matrix (PCM). If a PCM has a constant column (resp. row) weight of J (resp. L), then it yields a (J,L)-regular code. Generally, the PCM of a QC-LDPC code is an array of circulants, which may include zero matrix (ZM), circulant permutation matrix (CPM) or summation of distinct CPMs.
An LDPC code with PCM H can be represented by its associated Tanner graph, TG(H), and the length of the shortest cycle in the graph is called girth (or girth of the code/PCM). Denote by g(H) the girth of H. If H is an array of P× P CPMs/ZMs, then it can be completely determined by P and an exponent matrix E with entries in the set {∞, 0,1,⋯,P-1}, where ∞ corresponds to a P× P ZM and any other entry (say e) to a P× P identity matrix with rows cyclically shifted to the right by e (mod P) positions <cit.>. For this case, H and its girth can also be denoted by H(E,P) and g(E,P), respectively.

Let Z_N={0,1,⋯,N-1}. A Latin square of order N <cit.> is an N× N array in which each cell contains a symbol from Z_N, such that each
symbol occurs exactly once in each column and each row.



§ A GENERAL METHOD FROM PARTITION AND LATIN-STYLE SPLICING (PS)
 The base PCM H_0 is assumed to be an m× n array of P× P matrices over GF(2). Clearly, the PCM of a QC-LDPC code is a special case of H_0.
Given an integer N≥ 2, select N masking matrices M_k (0≤ k≤ N-1) of size m× n defined over the integer set {0,1}, such that the ordinary summation ∑_k=0^N-1M_k equals an m× n all-one matrix. Let A=[a_i,j] (0≤ i,j≤ N-1) be a Latin square of order N.
From H_0, a new mPN× nPN PCM H can be obtained by

    [
      [     H_0⊗ f(M_a_0,0)     H_0⊗ f(M_a_0,1)                   ⋯   H_0⊗ f(M_a_0,N-1);     H_0⊗ f(M_a_1,0)     H_0⊗ f(M_a_1,1)                   ⋯   H_0⊗ f(M_a_1,N-1);                   ⋮                   ⋮                   ⋱                   ⋮;   H_0⊗ f(M_a_N-1,0)   H_0⊗ f(M_a_N-1,1)                   ⋯ H_0⊗ f(M_a_N-1,N-1);                     ]]

where f(M) maps each 0 (resp. 1) in M to a P× P zero (resp. all-one) matrix over GF(2), and ⊗ is an element-by-element multiplication
defined by x ⊗ y=1 if and only if x=y=1.

Theorem 1: g(H)≥ g(H_0).

Proof: According to the definitions of M's and Latin square A, two adjacent edges within TG(H) correspond to two adjacent edges within TG(H_0). Therefore, if there is a cycle of length 2l in TG(H), then there must exist a corresponding cycle with the same length in TG(H_0). This completes the proof.

It is easily seen that the row/column weight distribution of H is the same as that of H_0, and the designed rate for H equals that for H_0. For P=1, H_0 corresponds to an LDPC code not necessarily with a special structure, that is to say, H_0 can be an arbitrary binary matrix. This suggests that the new method is applicable to any base code. If H_0 is an m× n array of P× P CPMs/ZMs, then H (Equ.1) can be described by (via its exponent matrix)

    E=
    [
      [     E_0⊗̃M_a_0,0     E_0⊗̃M_a_0,1                ⋯   E_0⊗̃M_a_0,N-1;     E_0⊗̃M_a_1,0     E_0⊗̃M_a_1,1                ⋯   E_0⊗̃M_a_1,N-1;                ⋮                ⋮                ⋱                ⋮;   E_0⊗̃M_a_N-1,0   E_0⊗̃M_a_N-1,1                ⋯ E_0⊗̃M_a_N-1,N-1;                  ]]

where E_0 is the exponent matrix of H_0.
The notation ⊗̃ stands for an element-by-element operation defined by x ⊗̃ 0=∞, and x ⊗̃ 1=x, where x∈{∞, 0,1,⋯,P-1}.

A Special Case: Let N=2 and n=Km. Suppose that both M_0 and M_1 are 1× K arrays of K identical m× m matrices. Let M_0=[X,⋯,X], where each element in the lower-triangle (including diagonal) of X is '1', and '0' elsewhere. Define M_1=1_m× n-M_0. Then, E can be obtained from E_0 by

    [
      [ E_0⊗̃M_a_0,0 E_0⊗̃M_a_0,1; E_0⊗̃M_a_1,0 E_0⊗̃M_a_1,1;              ]],
    A=
    [
      [ a_0,0 a_0,1; a_1,0 a_1,1;       ]]=
    [
      [ 0 1; 1 0;   ]]


Clearly, the above E is equivalent to that investigated in <cit.> (Section VII). It is pointed out <cit.> that g(E,P) is ensured to be at least 6, provided g(E_0,P)≥ 6. The method in this Letter, however, is more general in the sense that N is not limited to 2, and n and m can be selected arbitrarily. Moreover, given an arbitrary E_0 with g(E_0,P)=2g_0, Theorem 1 guarantees an exponent matrix E with g(E,P)≥ 2g_0.

Example 1: Given an exponent matrix
 
    E_0=
    [
      [ 0 0 0 0; 0 1 3 4; 0 2 6 5;   ]]

it is easily checked that g(E_0,P)=4 for any P≥ 7, as there is an equation (1-2)+(5-4)=0 (mod P) regardless of P. Set N=2, and define

    M_0=
    [
      [ 1 1 1 1; 1 1 1 1; 1 0 0 1;   ]],
    A=
    [
      [ a_0,0 a_0,1; a_1,0 a_1,1;       ]]
    =
    [
      [ 0 1; 1 0;   ]]

Then, M_1=1_3× 4-M_0.
Thus, the new method yields

    E=
    [
      [ E_0⊗̃M_0 E_0⊗̃M_1; E_0⊗̃M_1 E_0⊗̃M_0;          ]]
    =
    [
      [ 0 0 0 0        ; 0 1 3 4        ; 0     5   2 6  ;         0 0 0 0;         0 1 3 4;   2 6   0     5;   ]]

It is readily verified that g(E,P)=8 for any P≥ 7.


§ COMPARISON WITH EXISTING METHODS
 There exist some general methods to construct longer compound LDPC codes with nondecreasing girth from one or several shorter base code(s). The column splitting method <cit.> is capable of improving on the flexibility of code length and increase code rate by splitting each column of a PCM with large column weight into several columns. The method in <cit.> yields a longer QC-LDPC codes with girth at least 2g (2g=6 or 8) from two shorter QC-LDPC codes both with girth at least 2g. This method extends the row weight of QC-LDPC code (hence code rate increased), but only ensure a girth not exceeding eight even if both base codes have a girth larger than eight. The Chinese-remainder-theorem (CRT) method <cit.> can be employed to construct longer QC-LDPC codes by combining two shorter base QC-LDPC codes. The girth of the resultant code is not smaller than the maximal girth of the two base codes. Obviously, the new method is different from all the aforementioned methods.

Besides, if the Latin square A is selected as [a_i,j]=[i-j (mod N)], then Equ. (1) is reduced to the PCM of spatially coupled LDPC block codes <cit.>. The base matrices of the terminated ensembles and the tail-biting counterpart (Equ. (8) and Equ. (10) in <cit.>) are the same as the partial matrix and the whole matrix of E, respectively. However, since A generally possesses many forms different from the above choice, E and H are generally not identical to those of the spatially coupled LDPC codes.



§ SIMULATIONS
 The application of the new general method is illustrated by several examples. Set A as [a_i,j]=[i-j (mod N)]. Given a matrix M_0, set M_1=1_m× n-M_0, and let M_k=O (2≤ k≤ N-1) if N≥ 3. The matrix M_0 can be selected by different ways, in which three options are considered in this Letter. (a) For diagonal (D) partition, let M_0=[X,⋯, X], where X is an m× m matrix with 0's in diagonal and 1's elsewhere. (b) For triangle (T) partition, M_0=[X,⋯, X], where X(i,j)=1 for 0≤ j≤ i (0≤ i≤ m-1) and 0 elsewhere; and (c) For Hamming-like (H) partition, M_0 is a 0-1 m× n matrix in which the columns are as distinct as possible. For simulations, a BI-AWGN channel with BPSK modulation and SPA with 50 iterations are assumed.

Example 2: From the GCD construction <cit.>, E_0=[0,1,L,L+1]^T·[0,1,⋯, L-1] (mod P) is chosen as the base exponent matrix, where P=64 and L=8. Set N=4. For H partition, M_0 can be selected as

    M_0=
    [
      [ 1 0 1 1 1 0 0 0; 1 1 0 1 0 1 0 0; 1 1 1 0 0 0 1 0; 0 1 1 1 0 0 0 1;   ]]

From D,T and H partitions, three PS (4,8)-regular QC-LDPC codes are obtained with girth at least eight. For comparison purpose, a girth-8 GCD code and a girth-6 quad.-cong. code, both (4,8)-regular, are generated. The GCD code is obtained by setting E=[0,1,L,L+1]^T·[0,1,⋯,L-1] (mod P) where P=256 and L=8, and the quad.-cong. code is randomly constructed by the method <cit.> with a prime CPM size 257. From Fig.1, it is observed that the GCD code performs the worst, the PS-D and PS-T codes better, and the PS-H code the best, which can be partly explained by the fact that during the simulation, codewords with weight 14, 16, 16 are found for codes from GCD, PS-D and PS-T methods, respectively, and no codewords with small weight occur for the PS-H code. Moreover, the PS-H code noticeably outperform the well-known random quad.-cong. code.





Example 3: According to the GCD construction <cit.>, set E_0=[0,1,L,L+1]^T·[0,1,⋯, L-1] (mod P) as the base exponent matrix, where P=144 and L=12. Let N=3, and for H partition set

    M_0=
    [
      [ 1 0 1 1 1 0 0 1 1 0 0 0; 1 1 0 1 1 1 0 0 0 1 0 0; 1 1 1 0 0 1 1 0 0 0 1 0; 0 1 1 1 0 0 1 1 0 0 0 1;   ]]

From T and H partitions, two PS (4,12)-regular QC-LDPC codes are obtained with girth at least eight. A (4,12)-regular girth-8 GCD code is also generated by the exponent matrix [0,1,L,L+1]^T·[0,1,⋯, L-1] (mod P), where P=432 and L=12. A (4,12)-regular quad.-cong code is randomly generated with girth 6; besides, a (4,12)-regular QC-PEG code <cit.> is obtained with girth 8, the PCM of which is a 12× 36 array composed of 142 CPMs, 289 ZMs and one summation of two CPMs. We observe in Fig.2 that the PS-H code performs better than the quad.-cong code and the QC-PEG code, while the GCD and PS-T counterparts both suffer from error floor partly due to their relatively poor distance property (during the simulation, codewords with weight 14 and 12 exist for the GCD code and PS-T code, respectively, and no codewords with small weight is found for the PS-H code).



§ CONCLUSION
 By non-overlapping partition and Latin-square-style splicing, a general method (PS) preserving girth is proposed to yield longer LDPC codes from shorter base ones. Numerical results show that the codes generated by combining PS method (using Hamming-like partition) with some poor base codes perform very well compared with the well-known QC-PEG and quad.-cong. codes. Finally, it should be pointed out that by applying the new method to some explicitly constructed base codes with large girth (e.g. <cit.>, <cit.>), type-1 QC-LDPC codes with large girth such as <cit.><cit.> can be easily constructed.































  

§ ACKNOWLEDGMENTS


  

§ ACKNOWLEDGMENT



This work was supported by the National Natural Science Foundation of China under grant 61471294.





























1

F04
M. P. C. Fossorier:`Quasi-cyclic low-density parity-check codes from circulant permutation matrices', IEEE Trans. Inf. Theory, 2004, 50, (8), pp. 1788-1793

LK04
Z. Li and B. V. K. V. Kumar:`A class of good quasi-cyclic low-density parity check codes based on progressive edge growth graph', Proc. Asilomar Conf. Signals, Syst. Comput., Nov. 7-10, pp. 1990-1994, 2004.

KLF01
Y. Kou, S. Lin, M. P. C. Fossorier:`Low-density parity check codes based on finite geometries: a rediscovery and new results', IEEE Trans. Inform. Theory, 2001, 47, (7), pp. 2711-2736

MMY07
W. Matsumoto, Y. Miyata, H. Yoshida:`A study on QC-LDPC codes with girth 8 or 10 for broadband communications', IEICE Technical Report, 2007,  CS2007-27, pp. 31-35

MYP06
S. Myung, K. Yang:`A combining method of quasi-cyclic LDPC codes by the Chinese remainder theorem', IEEE Commun. Lett., 2005, 9, (9), pp. 823-825.

ZSW13
G. Zhang, R. Sun, X. Wang:`Construction of girth-eight QC-LDPC codes from greatest common divisor', IEEE Commun. Lett., 2013, 17, (2), pp. 369-372

WZZYS
J. Wang, G. Zhang, Q. Zhou, Y. Yang, R. Sun:`Explicit constructions for type-1 QC-LDPC codes with girth at least ten', IEEE Information Theory Workshop, Hobart, TAS, Australia, Nov. 2-5, 436-440, 2014.

Zhang16
G. Zhang:`Type-II quasi-cyclic low-density parity-check codes from Sidon sequences', Electron. Lett., 2016, 52, (5), pp. 367-369

TLZL06
Y. Tai, L. Lan, L. Zeng, S. Lin, K. A. S. Abdel-Ghaffar:`Algebraic construction of quasi-cyclic LDPC codes for the AWGN and erasure channels', IEEE Trans. Commun., 2006, 54, (10), pp. 1765-1774




MLC15
D. G. M. Mitchell, M. Lentmaier, D. J. Costello:`Spatially coupled LDPC codes constructed from protographs', IEEE Trans. Inf. Theory, 2015, 61, (9), pp. 4866-4889

HHY08
C. Huang, J. Huang, C. Yang:`Construction of quasi-cyclic LDPC codes from quadratic congruences', IEEE Commun. Lett., 2008, 12, (4),  pp. 313-315

KNCS06
S. Kim, J.-S. No, H. Chung, D.-J. Shin:`On the girth of Tanner (3,5) quasi-cyclic LDPC codes', IEEE Trans. Inf. Theory, 2006, 52, (4), pp. 1739-1744

GM12
M. Gholami, F.S. Mostafaiee:`On the girth of Tanner (3, 7) quasi-cyclic LDPC codes', Trans. Comb., 2012, 1, (2), pp. 1-16

ZM17
G. Zhang, R. Mathar:`Explicit constructions for type-1 QC-LDPC codes with girth 12', IEEE Commun. Lett., 2017, 17, (9), pp. 1822-1825











































