A method of constructing the half-rate QC-LDPC codes with linear encoder, maximum column weight three and inevitable girth 26
Li Peng
Wuhan National Laboratory for Optoelectronics, School of Electronic Information and Communications in Huazhong University of Science and Technology, Wuhan, China, 430074
Email address:
To cite this article:
Li Peng. A Method of Constructing the Half-Rate QC-LDPC Codes with Linear Encoder, Maximum Column Weight Three and Inevitable Girth 26. Communications. Vol. 2, No. 3, 2014, pp. 22-34. doi: 10.11648/j.com.20140203.11
Abstract: This paper presents a method of constructing the half-rate irregular quasi-cyclic low-density parity-check codes which can provide linear encoding algorithm and their H-matrices may contain almost the least "1" elements comparing with H-matrices of all existing LDPC codes. This method shows that three kinds of special structural matrices, respectively named as S-matrix, M-matrix and A-matrix, are defined and constructed. With regard to the arbitrary large structural girth based on A-matrix, its general pattern is conceived and its basic rule is proved. A general method of constructing M-matrix with the inevitable girth larger than 24 is introduced by using generalized block design and treating A-matrix as its sub-matrix. S-matrix is generated by substituting specially circular-shift values for non-zero elements in M-matrix. Combining H^{d}-matrix generated from lifting the S-matrix and H^{p}-matrix with the approximate lower triangular array structure forms the H-matrix, i.e. H=[H^{d} H^{p}], which defines a class of half-rate irregular QC-LDPC codes with maximum column weight 3 and inevitable girth of length 26. Simulation tests show that the performance of the presented QC-LDPC code can achieve the signal-noise-ratio of below 2dB at the bit-error-rate of 10^{-5}, which is comparable with the performance of the practical QC-LDPC codes in industrial Standard, but the complication of the former owing to the least "1" elements in H-matrix is lower than that of the later, as well as the storage requirement is smaller.
Keywords: Quasi-Cycle Low-Density Parity-Check (QC-LDPC) Code, Sparse Parity-Check Matrix, Girth, Generalized Block Design
1. Introduction
The irregular quasi-cyclic low-density parity-check (QC- LDPC) codes with linear encodable structure, here called the practical codes, are adopted by several IEEE industrial Standards [1-2] because of their perfect performance, inherently parallelizable decoding algorithm and linear encoding algorithm which are well suited for hardware implementation. Since the methods of constructing these practical codes have not yet been published up to now, besides it is necessary to probe into whether there are better practical codes (i.e., lower complexity and/or better performance, as well as algebraic structural codes), the method of designing the structural QC-LDPC codes has been a research hotspot in the field of error correcting codes in recent years [4-9,11,13].
The LDPC code defined by partitioned parity-check matrix, H-matrix for short, first appeared in appendix C of Gallager’s Ph.D dissertation in [3]. At the beginning, a special array structure, named as the array codes in [4], was studied. Later then, the general array structure, named as the quasi-cycle (QC)-LDPC code, had received enormous attention, because each sub-matrix in H-matrix can be generated by simply circular-shifting an identity matrix in [5-6] and the H-matrix can be implemented by shift register in [7]. An important parameter in the process of studying the LDPC codes is strongly considered, and it is girth. The performance of a LDPC code with iterative decoding strongly depends on the girth which is defined as the length of the shortest cycle in a Tanner graph associated with the H-matrix. In [5-6,8,9], the girth structure of full-element QC-LDPC codes is studied, and a significant conclusion is that the girth of length , called the evitable girth or the free girth, can be eliminated by designing circular-shift value, and one kind of girth of length larger than at least can not be eliminated and this girth is called the inevitable girth. Here the term "inevitable girth", introduced in [9], means that this girth can not be eliminated by designing the circular-shift value, or the "inevitable girth" is independent of the size of sub-matrix and the circular-shift value. For the convenience of elaboration, girth or cycle in an H-matrix is divided into two classes: the free girth (cycle) and the inevitable girth (cycle). If there are four "1" elements at four crossing positions of any two rows and any two columns within H-matrix of defining a QC-LDPC code, like the type , the paper [7] called this case unsatisfying row-column (RC) constraint, then the Tanner graph associated with this H-matrix contains the free girth of length 4. If an H-matrix does not contain such submatrix as the type , then the H-matrix is thought of as satisfying RC-constraint and there is no any free girth of length 4 in its Tanner graph. Many papers describes that if there is no free girth of length 4 in Tanner graph of an H-matrix, then the LDPC codes defined by this H-matrix performs perfect. But this paper effectively observes that it is not enough just to eliminate the free 4-girth in Tanner graph of H-matrix, especially for those cases that the maximum column weigh of an H-matrix is 3 or the maximum degree of its Tanner graph is 3, only eliminating the free girth of length larger than 4, such as 6, 8, 10 and so on, and making the inevitable girth as larger as possible, can make the LDPC code have good performance.
In order to eliminate the inevitable girth of length 12, the model matrix, M-matrix for short, corresponding to the H-matrix of QC-LDPC codes must be sparse matrix instead of full-one matrix, or the H-matrix must consist of partial permutation submatrices and partial full-zero submatrices, or the shift matrix, S-matrix for short, is an sparse matrix rather than a full-element matrix. Here the definitions involving M-matrix and S-matrix are available in section 2.2.
From the application point of view, the less the H-matrix contains "1" elements, the lower the complications of encoders and decoders for the QC-LDPC codes are. Therefore, the investigation of H-matrix with small column weight has been paid attention to [5-6,12,13]. The paper [12] studied the regular QC-LDPC codes with column weight three. The paper [13] discussed the irregular QC-LDPC codes with column weight three and two which gives perfect performance. But there is less report about the irregular QC-LDPC codes with column weight three and two under the constraint of framework of the linear encodable structure. In this paper, the author will pay attention to the algebraic method of constructing the practical irregular QC-LDPC codes with maximum column weight 3 as well as their girth structures under the constraint of framework available linear encoding algorithm.
The paper [9] investigated the protograph code and built up the concept of the inevitable girth with length, for all subgraph patterns which are used to construct protograph codes. In this paper, the matrix corresponding to this subgraph pattern which can form an inevitable girth is called the atom matrix, A-matrix for short. The girth of an A-matrix is expanded from of the protograph to of . The general construction of A-matrix is defined and the general rule of its structural girth is proved. The author uses two A-matrices and the method of generalized block design to construct an M-matrix, which is called as the model matrix or also the base matrix of H-matrix in some papers, and guarantees that there is no 4-cycle in H-matrix with approximate lower triangular array. In fact, the design of H-matrix is simply transformed into the design of M-matrix and S-matrix, and the design of the M-matrix is divided further on into the design of A-matrix.
The contributions of this paper are summarized as follows:
1) A-matrix with arbitrary large inevitable girth is defined and created, and its general structural features are discussed and proved. The inevitable girth in a (0,1)-matrix can be generated by means of algebraic method rather than computer searching method, and the size of inevitable girth is any positive integer rather than only restricted to [9].
2) An half-rate irregular H-matrix with linear encoding algorithm, column weight three and two and without 4-cycle is exactly constructed for the first time and its tanner exactly contains two inevitable girths of length 26 or maybe even large.
3) It is declared for the first time that H-matrix without 4-cycle performs badly over the additive white Gaussian noise (AWGN) channel and with belief propagation (BP) iterative decoding algorithm and binary phase-shift keying (BPSK) modulation, and the performance of H-matrix under the same environment can be improved only if the small free cycles, such as 6, 8, 10, 12 and so on, are eliminated at the greatest extent or completely and the inevitable girth is as large as possible in Tanner graph of this H-matrix.
4) A simulation result with practical application is first presented, this it is that the group of different code-length and half-rate irregular QC-LDPC codes defined by H-matrix with linear encoder based on approximate lower triangular array matrix and maximum column weight three perform within 1.9dB from the Shannon limit at the BER of 10^{-5}, in addition, they have the lowest complication because of the least "1" elements in H-matrix and occupy the least memory because of maximum column weight three comparing with the existing practical half-rate irregular QC-LDPC codes in multiple industrial standards.
The outline of the paper is as follows. Section 2 describes the basic knowledge which will be used in this paper. Section 3 investigates the general rule of arbitrary large girth in A-matrix. Section 4 presents a method of constructing M-matrix by means of two A-matrices. Section 5 discusses some consideration of S-matrix and Section 6 gives the results of the digital simulation for the presented QC-LDPC codes. Finally, Section 7 concludes the paper.
2. Preliminaries
2.1. A Practical Framework of Irregular QC-LDPC Codes
A practical framework of the sparse parity check matrix, H-matrix for short, which is used to define the irregular QC-LDPC codes is the following array:
(1)
where the -matrix with the size is an approximate lower triangular array matrix which can provide linear encoding algorithm and the -matrix with the size is an array; is the size of sub-matrix and ; is either a full-zero matrix or a permutation matrix and is an identity matrix; the subscript is either the circular-left-shift value (CSV) of a permutation matrix if is a permutation matrix or a symbol, denoted as "", if is a full-zero matrix, , , , denotes that the set only contains a symbol "". In addition, three matrices at three positions, such as the first, th and last positions within the most-left column of , are simple identity matrix instead of circular-shift permutation matrix, because CSVs either consume clock period or occupy memory cells, or even both. The meaning of what is called "practical framework" is that the approximate lower triangular array of in H-matrix can complete the linear encoding operation.
2.2. Definition of Several Special Matrices
Definition 1 [shift matrix]: All subscript values s are extracted from all sub-matrix s in -matrix of (1) and form the following sparse integer matrix:
(2)
then matrix of (2) is called the shift matrix or subscript matrix, S-matrix for short.□
Definition 2 [model matrix]: If one creates a matrix in such way that one makes all permutation matrices in -matrix of (1) be substituted by 1’s and all full-zero matrices by 0’s, then this new matrix is called the model matrix of -matrix of (1), M-matrix for short. M-matrix is a binary matrix. □
Definition 3 [atom matrix]: For any positive integer and , let . If and two binary matrices satisfy the following structural constraints, respectively
1) For a matrix, there must exist only one row which has maximum weight 3 and each of the other rows has minimum weight 2; there must exist only one column which has maximum weight 3 and each of the other columns has minimum weight 2;
2) For a matrix, there must exist only one row which has maximum weight 4 and each of the other rows has minimum weight 2; the weight of each column among columns is 2;
then both and matrices are called the atom matrix, A-matrix for short, denoted as and . □
A mandatory provision for an A-matrix is that an A-matrix must contain at least a "0" element or an A-matrix is not a full-1 matrix. For the convenience of description, the author calls the matrix, such as or , the pseudo atom matrix.
If an H-matrix is completely formed by a group of permutation matrices, then the H-matrix is regular and the corresponding S-matrix is formed by purity integers, which is called full-element S-matrix (FS-matrix). If an H-matrix is formed by partial permutation matrices and partial full-zero matrices, then the H-matrix is either regular or irregular and the corresponding S-matrix is formed by partial integers and partial symbols, denoted as in this paper, which is called the sparse S-matrix (SS-matrix).
Because of (1) is fixed, the main task is to design - matrix in this paper. For this goal, this paper is concerned with the structural design of M-matrix corresponding to the - matrix, and it is required that this M-matrix satisfies the following constraint:
1) M-matrix itself satisfies the RC constraint;
2) There is no two adjacent "1" elements at each column of M-matrix;
3) Any two of three positions, such as the first, th and last positions, on each of columns in the M-matrix are not occupied by "1" elements at the same time.
The above constraints 2) and 3) avoid the 4-cycle between and . Therefore, the above three constraints guarantee that the H-matrix of (1) does not contain the free girth of length 4.
2.3. Necessary and Sufficient Condition of Girth
In Theorem 2.1 of the paper [6], Fossorier gave the necessary and sufficient condition for the Tanner graph of H-matrix defined in (1) to have a girth , . This condition is also suited to M-matrix and A-matrix. For S-matrix of (2), the author makes the following modification.
Theorem 1: If the difference (or ) of element values of two positions on any row (column) in the S-matrix defined by (2) exists, then a necessary and sufficient condition for the Tanner graph representation of -matrix formed through lifting the S-matrix to have a girth at least is
(or ) () (3)
for all ,, all and , , all and ,, with , and .
Note that because symbol of S-matrix results in the difference not to exist, expression (3) is only a sufficient condition when S-matrix is sparse.
If one draws a horizontal line between any two elements on any one of rows and a vertical line between any two elements on any one of columns in S-matrix, then the closed path formed by horizontal lines and vertical lines demonstrates the structure of a cycle or a girth in S-matrix. Through lifting the S-matrix by using a group of permutation matrices, the corresponding -matrix contains such structural cycles or girths. From Theorem 1, the next corollary follows.
Corollary 2: For any rows in S-matrix of (2), if the sum of any difference values ’s equals zero, then the horizontal lines corresponding to the difference values must generate a closed path formed by lines. Conversely, if horizontal lines can form a cycle of length , then the sum of the difference values must equal zero. □
From Theorem 1 and Corollary 2, the next corollary follows.
Corollary 3: If there is a girth whose length is in S-matrix, then there is also a -girth of same structure in corresponding M-matrix. □
Obviously, the method of drawing horizontal and vertical lines in M-matrix can be used to investigate the girth characteristic of M-matrix. Because the distribution of all 1’s in M-matrix is still complex, so the girth characteristic of A-matrix which can be used to construct M-matrix is considered firstly. From a structural girth point of view, an A-matrix can be seen as a basic unit of an M-matrix (shown as in Fig. 3).
Note that interpretation of terminology. The same-row horizontal lines mean that there are two or more horizontal lines on the same row, which corresponds to two or more subscript differences on the same row. The different-row horizontal lines mean that all horizontal lines are located on different rows. The horizontal lines in an A-matrix have the following corollary.
Corollary 4: The following cases are naturally satisfied in an A-matrix:
1) On the row containing only two "1" elements, there must exactly be two same-row horizontal lines whose length is same.
2) On the row containing only three "1" elements, there must exactly be three same-row horizontal lines in which the sum of lengths of any two horizontal lines must be equal to the length of the remaining one.
3) On the row containing only four "1" elements, there must exactly be four same-row horizontal lines such that two cases appear: either the sum of length of three horizontal lines equals the length of the remaining one or the sum of length of any two horizontal lines equals the sum of length of the remaining two.
2.4. Structural Characters of Inevitable Girth
Researches show that the girth 4, 6, 8 and 10 in a full-element S-matrix (FS-matrix) can be eliminated by designing element values (circular-shift values) of S-matrix by means of algebraic method and computer searching method. For example, in the paper [5], under the strict constraint of structure parameters , that is that must be prime and all shift values must satisfy the constraint of elements in a multiplicative group which means a set of integers modulo , i.e., , , , , an efficient arrangement of all elements generates a FS-matrix in which the cycles formed by lines can be eliminated and the girth is at least . Thus a significant conclusion is that the girth 12 in a FS-matrix is inevitable. In other words, the model matrix corresponding to a FS-matrix is a full-1 matrix and includes many pseudo A-matrices like the type in which there must be inevitable girth 12. One can still infer that if a sub-matrix in an M-matrix is filled to the full of "1" elements, then there must be inevitable girth 12 in this M-matrix. Furthermore, if all elements on six crossing positions of any two non-neighbor rows (columns) and any three non-neighbor columns (rows) in any an M-matrix are filled by six "1" elements, then there exists inevitable girth 12 in this M-matrix. If one wants to destroy the structure of the inevitable girth 12 in a pseudo A-matrix, farther in an M-matrix including any number of pseudo A-matrices, as long as he/she substitutes one "0" element for any one of six "1" elements in the pseudo A-matrix, then the girth 12 in this pseudo A-matrix can be eliminated.
The paper [9] gives some A-matrices with girth larger than 12 by means of the searching method of computer. These A-matrices are seen as the subgraph patterns of the protograph codes and include girth , . Generally, the structures of inevitable girth of length have a general pattern as follows:
The following makes an A-matrix with inevitable girth 14 as an example in order to explain its structural characteristics. An has the following structural characteristic: its size is ; the total number of non-zero elements is 7, the total number of zero elements is ; the distribution of column weight is that any a column has three 1’s and the other two columns include two 1’s respectively; the distribution of row weight is that any a row has three 1’s and the other two rows include two 1’s respectively; in particular, contains at least two free 4-girths (observing all A-matrices in the following set of ). For a in Fig. 1, (a) shows the case of seven horizontal lines, (b) shows the case of the inevitable girth of length14, (c) shows that a contains two free girths of length 4 and (d) shows that a contains one free cycle of length 6 .
Fig. 1. (a) shows 7 horizontal lines, (b) shows an inevitable 14-girth in , (c) shows two 4-cycles in and (d) shows one 6-cycle in .
All A-matrices with inevitable girth form a set . According to the definition of A-matrix, the author enumerated all 18 elements in this set as follows:
Similarly, one can analyze the structural characteristics of the other A-matrices with inevitable girth , but it is difficult for a person to enumerate all A-matrices in the sets , and . One also observes that contains two free 4-cycles and one free 8-cycle, contains one free 4-cycle, one free 6-cycle and one free 8-cycle, and contains one free 4-cycle, one free 6-cycle and one free 10-cycle. All these free cycles can easily be destroyed by designing circular-shift values.
3. Girth Structure of Atom Matrix
Without loss of generality, the author will deduce the general structural characteristic with regard to arbitrarily large girth in an A-matrix with arbitrary size .
Theorem 5 [the structural rule of girth in an A-matrix]: Let be an arbitrary positive integer.
1. Let be an odd number and be the size of an A-matrix. If , then there exactly exists an inevitable girth except those free girth and free cycles smaller than and equal to in this A-matrix which can be denoted as .
2. Let be an even number, or be the size of an A-matrix and . If , then there exactly exists an inevitable girth except those free girth and free cycles smaller than and equal to in this A-matrix or in its transposed matrix, which can be denoted as or , respectively.
Proof: According to the definition of A-matrix and Corollary 4, there always exist , and "1" elements which can generate , and horizontal lines in three , and A-matrices, respectively. Due to for an odd number or for an even number , then there exist a closed path formed by horizontal lines and vertical lines in each of three A-matrices , and . Obviously, this closed path of lenght is independent of the subscript value and the size of permutation matrix and is only dependent of the size of an A-matrix. Therefore, this closed path of lenght in each of three A-matrices is an inevitable cycle .
In each of three A-matrices, all "1" elements take part in constructing this inevitable cycle , so there is no superabundant "1" elements that can form an inevitable cycle larger than . Furthermore, if any one of "1" elements does not take part in constructing this inevitable cycle , then the remnant "1" elements can not generate an inevitable cycle less than or equal to , despite the fact that they can form several free cycles and free girth less than or equal to . So this inevitable cycle in each of three A-matrices is the minimum inevitable cycle , that is, it is an inevitable girth . □
According to the rule of Theorem 5, one can design an A-matrix with any large girth. Next, the author will gave two examples about how to design the A-matrix with inevitable girth and.
Example 1: Let which is an even number. According to the rule 2) of Theorem 5, one has and . So he/she gets an A-matrix in which the weight of each of six columns is 2; the distribution of row weight is that any row has four "1" elements and each of the other four rows has two "1" elements. This distribution of row weight can generate at least 12 horizontal lines. Therefore, one can get an A-matrix with an inevitable girth of length 24 shown as in Fig. 2 (a).
(a)
(b)
Fig. 2. (a) shows the girth 24 of the A-matrix and (b) shows the girth 50 of the A-matrix .
Example 2: Let which is an odd number. According to the rule 1) of Theorem 5, one has . So he/she gets a matrix in which the distribution of row weight is that any row has three "1" elements and each of the other eleven rows has two "1" elements. The distribution of column weight is the same as the distribution of row weight. This distribution of row weight can generate 25 horizontal lines. Therefore, one can get an A-matrix with an inevitable girth of length 50 shown as in Fig. 2 (b).
Obviously, A-matrices and have a lot of patterns which can form the sets of and , respectively. In other words, the problem of constructing an A-matrix with any large girth based on Theorem 5 is a multi-solution problem and the A-matrix with determinate structural characteristic can form a solution set, which hints that the distribution of all "1" elements in an A-matrix has a random-like characteristic under the constraint of a fixed framework of "A-matrix" which is determined by the parameter and some deterministic distribution of row weight and column weight. For any positive integer , a A-matrix (or A-matrix) must exactly contain an inevitable girth of length (or ) and three free girths of length less than (or ).
4. Design M-Matrix by Using A-Matrix
This Section will describe a method how to construct an M-matrix by selecting several elements in the set formed by A-matrix.
Firstly, let and is an odd number, according to the definition 3 of atom matrix, the author constructs an A-matrix in which there are thirteen "1" elements and the distribution of row weight is that any row, for example the first row, among six rows has three 1’s and each of the other five rows has two 1’s. According to 1) and 2) of Corollary 4, thirteen "1" elements can generate thirteen horizontal lines. According to the rule 1) of Theorem 5, the thirteen horizontal lines form an inevitable girth of length 26. The presented A-matrix , in fact selected from the set , has the following general pattern:
(4)
The requirement of selecting this is that there is no any 4-cycle and 6-cycle in it. Observe the distribution of thirteen "1" elements in of (4) and discover that eight "1" elements with the subscript 1 or 2 respectively form an 8-cycle and ten "1" elements with the subscript 3 form a 10-cycle. The -matrix with an inevitable 26-girth indeed does not contain 4-cycle and 6-cycle, therefore, its free girth is at least 8. It's worth noting that the A-matrix of (4), whose meaningful characteristics are to contain an inevitable 26-girth, two free 8-girths and one free 10-cycle and not to contain any free 4-cycle and free 6-cycle, is not the only pattern, and here is constructed by using observation method. In particular, the author constructed of (4) by using the following constraints: i) there is no such column that contains two adjacent "1" elements in it; ii) it satisfies RC-constraint; iii) there is no any free 6-cycle in it.
Secondly, the author constructs an M-matrix by using the above A-matrix , where is any positive integer. In this M-matrix, there only exists an inevitable 26-girth, two free 8-girths and a free 10-cycle formed by an A-matrix , and the new columns are either the full-0 columns or the full-1 columns. Those new columns of weight 1 are selected randomly and the position of each "1" element is arranged randomly, but the distribution of all "1" elements in these new columns must guarantee not to generate any new cycle. That is, the M-matrix does not contain the free 4-cycle, the free 6-cycle and the inevitable girth of length less than 26. Therefore, its free girth is also at least 8 and its inevitable girth is also exactly 26. Let , then the M-matrix generate the new six columns in which there are a full-0 column and five full-1 columns. For example, this M-matrix may have the following pattern:
(5)
Thirdly, the author constructed an M-matrix by stacking up two M-matrices similarly to (5). This M-matrix is required in such way that it has the same row and column weights all of which are equal to three and does exactly not contain 4-cycle. In order to achieve the aim, the positions of ten indeterminate "1" elements in the M-matrix need to be considered carefully. As long as those columns of weight 1 in two M-matrices are suitably placed and the same two A-matrices of (4) are properly arranged at the top left corner and the bottom right corner, respectively, in the M-matrix, then this new created M-matrix can guarantee not to contain 4-cycle. However, the distribution of ten indeterminate "1" elements must generate 6-cycle. Here comes into being a research proposition that in an M-matrix with row and column weight 3, whether or not there must be any free 6-cycle. The design procedure of this M-matrix is shown in Fig. 3.
For , let the M-matrix corresponding to - matrix in (1) be constructed by in Fig. 3. In the sequence, the author will give a method to determine the positions of ten indeterminate "1" elements in .
Fig. 3. shows the process of constructing an M-matrix without 4-cycle and with two inevitable girths of length 26, and the new 6, 8, 10-cycles formed by ten "1" elements and indicated by the subscripts 1, 2, 3, respectively.
Because its row and column weights are 3, this M-matrix contains thirty-six "1" elements in which the positions of twenty-six "1" elements are given by two inevitable 26-girths and the positions of ten "1" elements are not known. The author used trituple to denote row coordinates of three "1" elements on each column in , so one can get the below twelve trituples:
(6)
where positive integer denote the row coordinates of unknown positions of ten "1" elements in . Considering constraints 1) and 2) in sub-section 2.1, one can deduce the range of ten unknown numbers : , , , . Further considering constraints 2) and 3) in sub-section 2.1, one can get and , and . So (6) is changed into the following pattern by bringing and into (6):
(7)
From (7), one can get and in order to avoid the 4-girth in. The remaining issues is to determine eight unknown numbers,, and .The author borrows five parameters and some concepts of BIBD based on combinatorial design theory in [10] in order to solve . Let the number of varieties denote the number of rows of , the number of blocks the number of columns, the column weight, the row weight and means that any pair of varieties occurs exactly once in blocks which is equivalent that does not contain any free 4-cycle. Because do not satisfy the constraint , this block design is not a BIBD and the author call it the generalization block design. Under the condition of satisfying the constraints 1), 2) and 3) in the sub-section 2.1 for, there are some limited collections of blocks with regard to. The author selected and from a collection of enumerating all blocks which satisfy the above series of constraints and formed the following exact twelve trituples :
(8)
Fig. 3 shows the structure of -matrix in which many new cycles of length 6, 8 and 10 are generated. For example, six "1" elements with the subscript 1 show a free 6-cycle, eight "1" elements with the subscript 2 show a free 8-cycle and ten "1" elements with the subscript 3 shows a free 10-cycle. Although it is difficult for one to determine the number and the structure of all free 6, 8 and 10-cycles in , one can conclude that there is no the free girth of length 4 in and its girth is at least 6.
Many paper reported that if an H-matrix does not contain any free girth of length 4, then the LDPC code defined by it can provide perfect performance. But this is not always the case, especially when the maximum column weight is 3. If one regards in Fig. 3 as the M-matrix corresponding to of (1), uses thirty-six identity matrices to lift all "1" elements in and twenty-five identity matrices to lift all -submatrices in of (1), then one can create an H-matrix without the free girth of length 4. Nevertheless the QC-LDPC code defined by this H-matrix performs badly which can be seen from the simulation testing curves in Fig. 5 of Section 5, where there are three dot lines respectively with code length which show the bad performance in the signal-noise-rate (SNB) of below 7 dB at the bit-error-rate (BER) of 10^{-6}. In consideration of the above simulation results, researchers need to use a group of circular-shift permutation matrix rather than identity matrix to lift M-matrix corresponding to of (1) in order to eliminate the small free cycles, such as free 6, 8 and 10 cycles, as more as possible or completely. Therefore, the next section will discuss how to design the circular shift values in S-matrix.
5. Designing S-Matrix and Digital Simulation
Once M-matrix is determined by twelve trituples of (8), then the corresponding S-matrix possesses the fixed structure, and the remaining problem is to determine the value of each element in S-matrix. In fact, designing S-matrix is to find out the CSVs which are placed the positions determined by twelve trituples of (8). There are many papers introducing the methods of designing full-element shift (FS)-matrix, for example, multiplication group ^{4-5, 11} and addition group ^{11}. But there are few papers investigating how to construct the sparse shift (SS) matrix. A viable method is first to design a FS-matrix without free 4-cycle by using the algebraic method and then to use the predesign M-matrix without free 4-cycle to mask this FS-matrix so as to obtain a SS-matrix which is the desired result. In this paper, the author choose a group of the existing CSVs from the base model matrix of the half-rate QC-LDPC codes in IEEE 802.16e Standard to create a SS-matrix. This treatment method is based on two thoughts. On the one hand, the half-rate irregular QC-LDPC codes with maximum column weight three in the framework of (1) has not been reported by far to be able to provide the good performance, for example, below 2dB at the BER of 10^{-5}; on the other hand, the main goal of this paper is to demonstrate by means of the simulation tests whether or not there exists such the H-matrix, with maximum column weight 3 and the inevitable girth 26 under the constraint of the framework of (1), that it can define the half-rate irregular QC-LDPC codes with the above perfect performance. Therefore, the author had extracted the CSVs from the half-rate QC-LDPC code of Standard [1] and formed the following twelve trituples of circular-shift values according to the position coordinates provided by twelve trituples of (8):
(9)
According to (1), (8) and (9), one can get an H-matrix of (10) at the top of the next page.
All 36 shift values are determined in such way that seven among the twelve tripules of (9) is in 1-1 correspondence with the shift values of seven columns with column weight 3 in the base model matrix which corresponds to the half-rate -matrix in IEEE 802.16e, and one of the other five tripules is formed by selecting arbitrarily and respectively three values from each of five columns with column weight 6. Note that in H-matrix of (10), the shift values of the thirteen positions in one inevitable girth of length 26 are the same as those in another, respectively.
(10)
As each column of -matrix array of (10) contains only three circular shift permutation matrixes, so that the simplified representation of -matrix can be formed as follows. One can define a number pair with subscript: which is used to denote the position of each shift value in SS-matrix corresponding to -matrix, where the subscript value denotes the column index of SS-matrix corresponding to -matrix of (10), denotes the row index of the shift values on the th column and denotes the shift values on the th column and theth row in the SS-matrix. Then this SS-matrix can be represented as the following 36 number pairs:
The above simplified representation of -matrix provides a kind of storage structure for H-matrix in memorizer.
Remark 1: Under the framework of (1) with maximum column weight 3 and the inevitable girth at least 26, the H-matrix of (10) is not the only one. If one reselects the A-matrix similar to (4), or redesigns the twelve trituples like (8) which has many selection schemes, or uses the optimizing searching method or the algebraic method to construct the SS-matrix, then he/she can obtain an H-matrix different from (10) under the same framework. The H-matrix obtained by the above methods can still guarantee a group of different-length half-rate irregular QC-LDPC codes to perform below 2dB at the BER of 10^{-5}.
Remark 2: The method of constructing the M-matrix introduces the randomness from two aspects. On the one hand, the set contains selectable solutions from which the author chose a of (4). Although the of (4) is designed by considering the following constrains: first no 4-cycle and then satisfy three conditions in Section 2.2 through integrated into account the arrangement of two matrices in M-matrix, the aspect of similar to (4) still has thousands of ways. So the of (4) is a random-like atom matrix. On the other hand, in the process of constructing -matrix, the uncertain distribution of ten "1" elements introduces the randomness. Therefore, the method of constructing M-matrix is a random-like method. In this paper, the SS-matrix is constructed by using random method, but in fact, one can basically use the algebraic method to construct the SS-matrix. For example, firstly, the FS-matrix is constructed by means of the method of addition group and multiplication group in [11]; secondly, the SS-matrix can be formed by applying in Fig. 3 to mask the above FS-matrix. So this method of constructing SS-matrix is not completely algebraic method because of the random-like property of .
6. Simulation Results
For the 1/2 rate irregular QC-LDPC codes defined by H-matrix of (10), the author tested the performance of the lowest point of the characteristic curve in the coordinate system formed by the signal-noise-ratio (SNR) and the bit error rate (BER) for the different code lengths from to by the ergodic positive integer of the circular shift permutation submatrix size from to in order to obtain a set of codes in which all codes of different length perform below 2 dB at the BER of 10^{-5}. If one modifies (8) and/or (9) under the same framework, then the code length contained in this set is changed. In the other word, the trituples different from (8) and/or (9) can generate the different code set of various code lengths.
Table 1 gives one set of the half-rate irregular QC-LDPC codes with various code lengths defined by H-matrix of (10) in which each code length is less than 1200 and the SNR of each code is between 2dB and 3dB when the BER is 10^{-5}. Table 2 gives another code set in which each code length is larger than 1200 and the SNR of each code is below 2dB when the BER is 10^{-5}. The first column of two Tables gives the index of the code number in the code set.
In the following, the 1/2 codes of several length is selected from the code sets in Table 1 and 2, their error performances over the AWGN channel with belief propagation (BP) iterative decoding algorithm and binary phase-shift keying (BPSK) modulation are computed. The maximum number of decoding iterations is 50.
Fig. 4 shows the performance comparisons between the half-rate short-length irregular QC-LDPC codes listed in Table 1 and those adopted by IEEE 802.16e and IEEE 802.11n Standard. Three codes selected from Table 1 have code length whose corresponding sizes of the circular shift permutation matrices are , respectively. Three codes selected from IEEE 802.16e Standard have code lengths and their submatrix sizes , which are approximate or equal to the sizes of the presented codes, respectively. IEEE 802.11n Standard only adopts a short code of length and its submatrix has the size .
number | Code length (N) | Information length (K) | Size of submatrix (n) |
1 | 504 | 252 | 21 |
2 | 696 | 348 | 29 |
3 | 720 | 360 | 30 |
4 | 840 | 420 | 35 |
5 | 912 | 456 | 38 |
6 | 984 | 492 | 41 |
7 | 1056 | 528 | 44 |
8 | 1128 | 564 | 47 |
From Fig. 4, it is seen that the selected codes from Table 1 (three solid lines) outperform the Standard codes (three dot lines for IEEE 802.16e and one dash line for IEEE 802.11n). In addition, Fig. 4 also reveals the Standard codes have the error floor (see the dot line with the circle corresponding to the code of length in IEEE 802.16e Standard and the dash line with the nabla symbol corresponding to the code of length in IEEE 802.11n Standard) and the ups and downs change of BER within the small-range of SNR (see the dot line with triangular symbol corresponding to the code of in IEEE 802.16e Standard). In addition, the maximum column weight of the half-rate QC-LDPC codes is 6 in IEEE 802.16e Standard and 12 in IEEE 802.11n Standard, but the half-rate QC-LDPC codes defined by (10) has only the maximum column weight 3. The simulation tests in Fig. 4 indicates that for the case of short-length codes, the half-rate irregular QC-LDPC codes defined by the H-matrix similar to (10) perform not only in slightly better performance and but also in lower complexity than those adopted by the Standards.
Number | Code length(N) | Information length (K) | Size of sub matrix(n) |
1 | 3288 | 1644 | 137 |
2 | 3720 | 1860 | 155 |
3 | 3816 | 1908 | 159 |
4 | 3864 | 1932 | 161 |
5 | 3888 | 1944 | 162 |
6 | 4032 | 2016 | 168 |
7 | 4080 | 2040 | 170 |
8 | 4152 | 2076 | 173 |
9 | 4344 | 2172 | 181 |
10 | 4488 | 2244 | 187 |
11 | 4704 | 2352 | 196 |
12 | 4800 | 2400 | 200 |
13 | 4896 | 2448 | 204 |
14 | 5112 | 2556 | 213 |
15 | 7584 | 3792 | 316 |
16 | 8232 | 4116 | 343 |
17 | 8304 | 4152 | 346 |
18 | 8784 | 4392 | 366 |
19 | 8904 | 4452 | 371 |
20 | 9648 | 4824 | 402 |
21 | 10656 | 5328 | 444 |
Fig. 5 shows the performance comparisons of the codes defined by (1) in which array -matrix is constructed between by lifting the circular shift permutation matrices for in Fig. 3, like (10) and by lifting the identity matrix without circular shift values for the same . Three solid lines within 2dB at the BER of 10^{-5}, which show the performance of the half-rate irregular QC-LDPC codes with circular shift values, outperform three dot lines near 7dB at the BER of 10^{-5}, which show the performance of those neither circular shift values nor 4-girth, in about 5dB or more, for the code length corresponding to the submatrix sizes , respectively.
The reason of distinctive performance between two groups of codes with the same M-matrix but the different lifting cases can be analyzed as follows. According to the necessary and sufficient condition of the existence of girth of S-matrix in Theorem 1, one can analyze the case of the cycles in H-matrix of (10). It is necessary for one to list the expressions of the algebraic sum of the circular shift values of those cycles emphasized by left superscripts and left subscripts in H-matrix of (10). There are three types of cycles in H-matrix of (10).
Type one: Two 8-cycles and one 10-cycle formed by the subscript 1, 2 and 3 in (4) may correspondingly be exhibited by the left superscript 1, 2 and 3 in of (10) as the possible formation of four 8-cycles and two 10-cycles, and the algebraic sum of the circular shift values of these potential free (for simplification, these two words are omitted in the following) cycles are calculated as follows.
For 8-cycle with left superscript 1, one can get:
.
For 8-cycle with left superscript 2, one can get:
For 10-cycle with left superscript 3, one can get:
Fig. 5. Performance comparison of the 1/2 rate irregular QC-LDPC codes with length for with CSV and without CSV.
Type two: One 6-cycle, one 8-cycle and one 10-cycle indicated by the subscript 1, 2 and 3 within -matrix in Fig. 3 undoubtedly are expanded into 6-cycles, 8-cycles and 10-cycles if is lifted by identity matrix. If is lifted by circular shift permutation matrix, such as -matrix of (10), then the three cycles within -matrix in Fig. 3 are exhibited by left subscript 4, 5 and 6 in of (10), and the algebraic sum of the circular shift values of these potential free cycles are calculated as follows:
for 6-cycle;
for 8-cycle;
for 10-cycle.
Type three: The first, the sixth, the seventh, the tenth and the twelfth columns in -matrix of (10) combining with the bidiagonal matrix of -matrix of (10) can generate the following eight free 6-cycles:
, this 6-cycle appears two times;
, this 6-cycle appears two times;
, this 6-cycle appears one time;
, this 6-cycle appears one time;
, this 6-cycle appears two times.
In addition, the maximum free cycles formed by combining the second and the forth columns of with those corresponding columns of are two potential free 22-cycles, and their algebraic sums of circular shift values are and , respectively. The other potential free cycles between and , such as 8, 10, 12, 14, 16, 18, 20 potential free cycles, can also be observed and analyzed. Although, it is difficult to enumerate all potential free cycles within H-matrix of (10), the author thought that the above three types should be able to explain some problems.
One can observe from the above analyses with regard to the algebraic sums of circular shift values that the sun of each algebraic sum for each submatrix size in Table 1 and 2 is not equal to zero in most situations, that is to say all potential free cycles of the above three types have been deleted to a large extent, which results in that the codes based on circular-shifting permutation matrix is superior to the codes based on the identity matrix in spite of no 4-cycle.
From the above analyses about the sun of circular shift values for potential free cycles in H-matrix, the author can dauntlessly conjecture without proof that there must exist such proposition that the girth in H-matrix of (1) is just the inevitable girth of length , each of those potential free cycles of length less than is likely to be deleted by the applicable circular shift values whose sun for each , for example in Table 1 and 2, is not equal to zero.
7. Conclusion and Future Work
Under the framework of the QC-LDPC codes with linear encodable structure, the maximum column weight three and the inevitable girth of length at least (), the design of a sparse parity check matrix can be decomposed into the design of the atom matrix, the medal matrix and the sparse shift matrix. The atom matrix will be investigated with the aid of the mathematic tool of graph theory. The medal matrix is constructed by means of the block design based on combinatorial mathematics. The design of shift matrix needs to use the multiplicative group and the addition group over the finite field as well as block design based on combinatorial mathematics. The inevitable girth of the full-element shift matrix is exactly 12, and that of the sparse shift matrix may be arbitrary size only if the size of the framework is not the limit. Under the condition of deleting the free girth by means of circular shift values, the size of girth for the QC-LDPC codes under the presented framework depends on the size of the inevitable girth, and generally, the performance of the codes can be improved as the size of the inevitable girth increases.
Under the constraint of the framework presented in this paper, the future research work has three points. First is to find out the fixed structural A-matrix with the inevitable girth as large as possible from the sets and . Second is to design M-matrix without 4-cycle and 6-cycle. Third is to investigate the algebraic method how to construct sparse shift matrix in which all free cycles less than an inevitable girth can be deleted by means of circular shift values.
Acknowledgements
This work was supported by the National Natural Science Foundation of China under Grant No. 61071069.
References