1. Field of the Invention
The present invention relates generally to a communication system using linear block codes, and more particularly, to a transmission/reception apparatus and method for generating linear block codes in a specific form.
2. Description of the Related Art
In wireless communication systems, link performances are significantly degraded by various noises, fading, and Inter-Symbol Interference (ISI) of channels. Therefore, to realize high-speed digital communication systems requiring high data throughput and reliability, such as a next-generation mobile communication system, a digital broadcasting system, and a mobile Internet system, it is important to develop technologies for coping with the noises, fading, and ISI. Recently, error-correcting codes have been studied to improve communication reliability by efficiently restoring information distortion.
A Low-Density Parity Check (LDPC) code will be referred to herein as an example of a linear block code, but the present invention is not limited to the LDPC code.
The LDPC code is commonly represented using a graph representation, and its many characteristics can be analyzed by graph theory and methods based on algebra and probability theory. Generally, a graph model of channel codes is not only useful in code description, but also can be regarded as a communication network in which vertexes exchange messages through edges, if information about encoded bits are mapped to vertexes in the graph and relationships between the bits are mapped to edges in the graph, thus making it possible to derive a natural decoding algorithm. For example, in a trellis, which is a kind of graph, a derived decoding algorithm may include the well known Viterbi algorithm, and Bahl, Cocke, Jelinek, and Raviv (BCJR) algorithm.
The LDPC code is generally defined as a parity check matrix, and can be represented using a bipartite graph, which is referred to as a Tanner graph. In the bipartite graph, vertexes are divided into two different types, and the LDPC code is represented by a bipartite graph including vertexes called variable nodes and check nodes. The variable nodes are mapped to encoded bits on a one to one basis.
FIG. 1 illustrates an example of a parity check matrix H1 of an LDPC code, which includes four rows and eight columns.
Referring to FIG. 1, by having eight columns, the parity check matrix H1 generates a length-8 codeword in an LDPC code, and its columns are mapped to eight encoded bits on a one to one basis.
FIG. 2 illustrates a Tanner graph corresponding to the parity check matrix H1 of FIG. 1.
Referring to FIG. 2, the Tanner graph of the LDPC code includes eight variable nodes x1 202, x2 204, x3 206, x4 208, x5 210, x6 212, x7 214, and x8 216, and four check nodes 218, 220, 222, and 224. An i-th column and a j-th row of the parity check matrix H1 of the LDPC code are mapped to a variable node xi and a j-th check node, respectively. In addition, a value of 1, i.e., a non-zero value, at the point where an i-th column and a j-th row of the parity check matrix H1 of the LDPC code cross each other, means that an edge connecting the variable node xi to the j-th check node exists on the Tanner graph as illustrated in FIG. 2.
In the Tanner graph of the LDPC code, a degree of each of a variable node and a check node indicates the number of edges connected to the node, and is equal to the number of entries whose values are not ‘0’ in a row or a column corresponding to the node in the parity check matrix of the LDPC code. For example, in FIG. 2, degrees of the variable nodes x1 202, x2 204, x3 206, x4 208, x5 210, x6 212, x7 214, and x8 216 are 4, 3, 3, 3, 2, 2, 2, and 2, respectively, and degrees of the check nodes 218, 220, 222 and 224 are 6, 5, 5 and 5, respectively. In addition, the number of entries whose values are not ‘0’ in columns of the parity check matrix H1 in FIG. 1, which correspond to the variable nodes in FIG. 2, are identical to their associated degrees of 4, 3, 3, 3, 2, 2, 2, and 2, respectively, and the number of entries whose values are not ‘0’ in rows of the parity check matrix H1 in FIG. 1, which correspond to the check nodes in FIG. 2, are identical to their associated degrees of 6, 5, 5, and 5, respectively.
In order to express degree distribution for nodes of an LDPC code, assuming that a ratio of the number of variable nodes with degree=i to the total number of variable nodes is fi, and a ratio of the number of check nodes with degree=j to the total number of check nodes is gi, in the LDPC code corresponding to FIGS. 1 and 2, f2=4/8, f3=3/8, and f4=1/8; fi=0 for i≠2, 3, 4; g5=3/4 and g6 1/4; and gi=0 for j≠5, 6. If a length of a codeword in an LDPC code, i.e., the number of columns in a parity check matrix, is N and the number of rows is N/2, a density of entries whose values are not ‘0’ in the entire parity check matrix having the above degree distribution is calculated in accordance with Equation (1) below.
                                                        2              ⁢                                                          ⁢                              f                2                            ⁢              N                        +                          3              ⁢                                                          ⁢                              f                3                            ⁢              N                        +                          4              ⁢                                                          ⁢                              f                4                            ⁢              N                                            N            ·                          N              /              2                                      =                  5.25          N                                    (        1        )            
In Equation (1), the density of ‘1’ decreases with an increase in N in the parity check matrix. Generally, because for an LDPC code, the density of non-zero entries is inversely proportional to the codeword length N, an LDPC code with a large value for N has a very low density. The wording ‘low density’ in the name of the LDPC code was derived from this principle.
FIG. 3 is a diagram illustrating a schematic structure of an LDPC code. Specifically, FIG. 3 illustrates characteristics of a parity check matrix of an LDPC code having a specific structure. For reference, the LDPC code illustrated in FIG. 3 has been adopted as standard technology in European digital broadcasting standards such as DVB-S2, DVB-T2, and DVB-C2.
Referring to FIG. 3, N1 denotes a length of a codeword in an LDPC code, K1 denotes a length of an information word, and (N1−K1) denotes a length of parity bits. In addition, integers M1 and q are defined by q=(N1−K1)/M1. K1/M1 is also an integer. For convenience of description, the parity check matrix of FIG. 3 will be assumed to be a first parity check matrix H1.
In the parity check matrix of FIG. 3, a parity part (corresponding parity bits) including K1-th to (K1−1)-th columns has a structure in a dual diagonal shape. Therefore, as to degree distribution of the columns corresponding to the parity part, all columns have a degree of 2, except for the last column having a degree of 1.
In the parity check matrix, an information word part consisting of 0-th to (K1−1)-th columns has a structure, which is formed according to the following rules.
Rule (1): A total of K1/M1 column groups are generated by grouping K1 columns for the information word into M1 groups in the parity check matrix. Each column in each column group is formed according to Rule (2) below.
Rule (2): First, locations of 1 in each 0-th column in an i-th column group (where i=0, 1, . . . , K1/M1−1) are determined. A degree of a 0-th column in an i-th column group is represented by Di. If locations of rows with 1 are Ri,0(1), Ri,0(2), . . . , Ri,0(Di), then locations Ri,j(k) (k=1, 2, . . . , Di) of rows with 1 in a j-th column (where j=1, 2, . . . , M1−1) in an i-th column group can be defined as shown Equation (2) below.Ri,j(k)=Ri,(j-1)(k)+q mod(Ni−K1)  (2)k=1, 2, . . . , Di, i=0, 1, . . . , K1/M1−1, j=1, 2, . . . , M1−1
According to the rules above, degrees of columns in an i-th (i=0, 1, . . . , K1/M1−1) column group are all Di.
As a more detailed example, as to each 0-th column in each of three column groups for N1=30, K1=15, M1=5, q=3, location information of rows with 1 can be represented as follows. For example, if {0, 1, 2} is a 0-th column group, {0, 1, 2} indicates that 1 exists in a 0-th row, a 1-st row and a 2-nd row in a 0-th column in the 0-th column group.R1,0(1)=0,R1,0(2)=1, R1,0(3)=2,R2,0(1)=0,R2,0(2)=11, R2,0(3)=13,R3,0(1)=0,R3,0(2)=10, R3,0(3)=14,
For information about rows with 1 in each 0-th column in each column group, only location information may be represented on a column group basis for convenience, as follows:
                       0                    1                    2                            0                    11                    13                            0                    10                    14            
That is, the sequence sequentially represents information about rows with 1 for a 0-th column in an i-th column group.
By making a parity check matrix using the information in the above detailed example, and Rules (1) and (2), an LDPC code having the same concept as that of the LDPC code with the structure of FIG. 3 may be generated as illustrated in FIG. 4.
Next, reference will be made to a process of performing LDPC encoding using the parity check matrix.
For convenience, information bits with a length K1 are represented by (i0, i1, . . . , iK1-1) and parity bits with a length N1−K1 are represented by (p0, p1, . . . , pN1-K1-1). An LDPC code described in detail below has characteristics of N1=16200, K1=10800, M1=360, and q=15.
Encoding Method of an LDPC Code
Step 1: Parity bits are initialized.p0=p1= . . . =pN1-K1-1=0
Step 2: Information about rows with 1 in a 0-th column in a first column group of an information word is called from information about the stored parity check matrix.                R1,0(1)=0,R1,0(2)=2084,R1,0(3)=1613,R1,0(4)=1548,R1,0(5)=1286,R1,0(6)=1460,R1,0(7)=3196,R1,0(8)=4297,R1,0(9)=2481,R1,0(10)=3369,R1,0(11)=3451,R1,0(12)=4620,R1,0(13)=2622        
Using the called information and information bit i0, specific parity bits px are updated as shown in Equation (3) below, where x is a value of R1,0(k), for k=1, 2, . . . , 13.p0=p0⊕i0,p2048=p2048⊕i0,p1613=p1613⊕i0, p1548=p1548⊕i0,p1286=p1286⊕i0,p1460=p1460⊕i0, p3196=p3196⊕i0,p4297=p4297⊕0,p2481=p2481⊕i0, p3369=p3369⊕i0,p3451=p3451⊕i0,p4620=p4620⊕i0, p2622=p2622⊕i0  (3)
In Equation (3), ⊕ represents binary addition, and px=px⊕i0 is exchangeable with px←px⊕i0.
Step 3: For the next 359 information bits i1, i2, . . . , i359 succeeding i0, a value of Equation (4) below is obtained.{x+(m mod M1)×q} mod(N1−K1),m=1,2, . . . ,359  (4)
In Equation (4), x is a value of R1,0(k), for k=1, 2, . . . , 13. It is to be noted that Equation (4) is similar in concept to Equation (2).
Using the values obtained in Equation (4), an operation similar to that of Equation (3) is performed. That is, p{x+(m mod M1)×q} mod(N1-K) is updated for im.
For example, for m=1, i.e., for i1, p{x+q} mod(N1-K1) is updated as shown in Equation (5) below.p15=p15⊕i1,p2099=p2099⊕i1,p1628=p1628⊕i1, p1563=p1563⊕i1,p1301=p1301⊕i1,p1475=p1475⊕i1, p3211=p3211⊕i1,p4312=p4312⊕i1,p2496=p2496⊕i1, p3384=p3384⊕i1,p3466=p3466⊕i1,p4635=p4635⊕i1, p2637=p2637⊕i  (5)
It is to be noted that in Equation (5), q=15. The above process is performed in a similar manner for m=1, 2, . . . , 359.
Step 4: Like in Step 2, information about R2,0(k) (k=1, 2, . . . , 13) is called for a 361st information bit i=360 to update specific parity bits px, where x is R2,0(k). For the next 359 information bits succeeding i361, i362, . . . , i719 succeeding i=360, p{x+(m mod M1)×q mod(N1-K1)}, (for m=361, 362, . . . , 719) are updated by applying Equation (4) in a similar manner.
Step 5: For each of 360 information bit groups, Steps 2, 3, and 4 are repeated. Finally, parity bits are determined using Equation (6) below.pi=pi⊕pi−1,i=1,2, . . . ,N1−K1−1  (6)
In Equation (6), bits pi are parity bits that have completely undergone LDPC encoding.
Accordingly, using the above-described LDPC encoding method, encoding is performed through Steps 1 through 5.
It is well known that performances of common LDPC codes are closely related to cycle characteristics of the Tanner graph. In particular, it has been determined through experimentation that performance degradation may occur if there are many short-length cycles in the Tanner graph. Therefore, to design LDPC codes having excellent performance, cycle characteristics on the Tanner graph should be considered.
Briefly, the cycle characteristics are the number of nodes by which an edge has passed while in the Tanner graph, the edge starting at one variable node returns to the variable node after passing by at least one check node and other variable nodes. For example, in FIG. 2, a path of 202->218->204->220->202 may be construed as one cycle. It is important to design LDPC codes such that such cycle characteristics have an optimal length, which is neither too short nor long.
However, it is very difficult to design a parity check matrix of a very large LDPC code whose codeword length is about tens of thousands of bits, considering cycle characteristics on the Tanner graph. Actually, no design method has yet been proposed, which improves cycle characteristics of LDPC codes having the specific structure of FIG. 3. In reality, in LDPC codes having the above structure, an error floor is observed at a high Signal to Noise Ratio (SNR), because optimization of cycle characteristics on the Tanner graph is not considered.
Accordingly, for designing LDPC codes having the specific structure of FIG. 3, an efficient method is required, which designs a parity check matrix while improving cycle characteristics.
Additionally, in European digital broadcasting standards using the LDPC code, the possible number of lengths of a coded block of the LDPC code is only two due to the limited use of the code, and to support even these two block lengths, different parity check matrixes are stored.
However, to apply LDPC codes to an actual communication system, the LDPC codes should be designed to be suitable to data throughput required in the communication system. Particularly, LDPC codes having various block lengths are required to support various data throughputs upon a user's request, not only in adaptive communication systems utilizing Hybrid Automatic Retransmission reQuest (HARQ) and Adaptive Modulation and Coding (AMC), but also in a communication system supporting various broadcast services.
In addition, because storing an independent parity check matrix for each block length of an LDPC code reduces memory efficiency, there is a need to study a new method for efficiently supporting various block lengths from the given existing parity check matrix, without designing a new parity check matrix.
USPTO Backgrounds
USPTO Backgrounds