As described in U.S. patent application Ser. No. 10/839,995, which is incorporated by reference herein, a low-density parity-check (LDPC) code is a linear block code specified by a parity-check matrix H. In general, an LDPC code is defined over a Galois Field GF(q), q≧2. If q=2, the code is a binary code. All linear block codes can be described as the product of a k-bit information vector s1×k with a code generator matrix Gk×n to produce an n-bit codeword x1×n, where the code rate is r=k/n. The codeword x is transmitted through a noisy channel, and the received signal vector y is passed to the decoder to estimate the information vector S1×k.
Given an n-dimensional space, the rows of G span the k-dimensional codeword subspace C, and the rows of the parity-check matrix Hm×n span the m-dimensional dual space C⊥, where m=n−k. Since x=sG and GHT=0, it follows that xHT=0 for all codewords in subspace C, where “T” (or “T”) denotes matrix transpose. In the discussion of LDPC codes, this is generally written asHxT=0T,  (1)where 0 is a row vector of all zeros, and the codeword x=[s p]=[s0, s1, . . . , sk−1, p0, p1, . . . , pm−1], where p0, . . . , pm−1 are the parity-check bits; and s0, . . . , sk−1 are the systematic bits, equal to the information bits within the information vector.
For an LDPC code the density of non-zero entries in H is low, i.e., there are only a small percentage of 1's in H, allowing better error-correcting performance and simpler decoding than using a dense H. A parity-check matrix can be also described by a bipartite graph. The bipartite graph is not only a graphic description of the code but also a model for the decoder. In the bipartite graph, a codeword bit (therefore each column of H) is represented by a variable node on the left, and each parity-check equation (therefore each row of H) is represented by a check node on the right. Each variable node corresponds to a column of H and each check node corresponds to a row of H, with “variable node” and “column” of H referred to interchangeably, as are “check node” and “row” of H. The variable nodes are only connected to check nodes, and the check nodes are only connected to variable nodes. For a code with n codeword bits and m parity bits, variable node vi is connected to check node cj by an edge if codeword bit i participates in check equation j, i=0, 1, . . . , n−1, j=0, 1, . . . , m−1. In other words, variable node i is connected to check node j if entry hji of the parity-check matrix H is 1. Mirroring Equation (1), the variable nodes represent a valid codeword if all check nodes have even parity.
An example is shown below to illustrate the relationship between the parity-check matrix, the parity-check equations, and the bipartite graph. Let an n=12, rate−½ code be defined by
                              H          =                                                                      [                                                                                    1                                                                    0                                                                    1                                                                    0                                                                    0                                                                    0                                                                    1                                                                    1                                                                    0                                                                    0                                                                    0                                                                    0                                                                                                            0                                                                    1                                                                    0                                                                    0                                                                    1                                                                    0                                                                    0                                                                    1                                                                    1                                                                    0                                                                    0                                                                    0                                                                                                            0                                                                    0                                                                    1                                                                    0                                                                    0                                                                    1                                                                    1                                                                    0                                                                    1                                                                    1                                                                    0                                                                    0                                                                                                            1                                                                    0                                                                    0                                                                    1                                                                    0                                                                    0                                                                    0                                                                    0                                                                    0                                                                    1                                                                    1                                                                    0                                                                                                            0                                                                    1                                                                    0                                                                    0                                                                    1                                                                    0                                                                    0                                                                    0                                                                    0                                                                    0                                                                    1                                                                    1                                                                                                            0                                                                    0                                                                    0                                                                    1                                                                    0                                                                    1                                                                    1                                                                    0                                                                    0                                                                    0                                                                    0                                                                    1                                                                              ]                                }                                            ︸                n                                      ⁢            m                          ,                            (        2        )            with the left side portion corresponding to k (=6) information bits s, the right side portion corresponding to m (=6) parity bits p. Applying (1), the H in (2) defines 6 parity-check equations as follows:
                    {                                                                                                  x                    0                                    +                                      x                    2                                    +                                      x                    6                                    +                                      x                    7                                                  =                0                                                                                                                              x                    1                                    +                                      x                    4                                    +                                      x                    7                                    +                                      x                    8                                                  =                0                                                                                                                              x                    2                                    +                                      x                    5                                    +                                      x                    6                                    +                                      x                    8                                    +                                      x                    9                                                  =                0                                                                                                                              x                    0                                    +                                      x                    3                                    +                                      x                    9                                    +                                      x                    10                                                  =                0                                                                                                                              x                    1                                    +                                      x                    4                                    +                                      x                    10                                    +                                      x                    11                                                  =                0                                                                                                                              x                    3                                    +                                      x                    5                                    +                                      x                    6                                    +                                      x                    11                                                  =                0.                                                                        (        3        )            H also has the corresponding bipartite graph shown in FIG. 1.
As discussed above, the receiver obtains a contaminated version y of the transmitted codeword x. To decode y and determine the original information sequence s, an iterative decoding algorithm, such as belief propagation, is applied based on the bipartite graph. Soft information in the format of log-likelihood ratio (LLRs) of the codeword bits is passed between the bank of variable nodes and the bank of check nodes. The iteration is stopped either when all check equations are satisfied or a maximum allowed iteration limit is reached.
A structured LDPC code design starts with a small mb×nb base matrix Hb, makes z copies of Hb, and interconnects the z copies to form a large m×n H matrix, where m=mb×z, n=nb×z. Using the matrix representation, to build an H from Hb each 1 in Hb is replaced by a z×z permutation submatrix (square subblock), and each 0 in Hb is replaced by a z×z all-zero submatrix. This procedure essentially maps each edge of Hb to a vector edge of length z in H, each variable node of Hb to a vector variable node of length z in H, and each check node of Hb to a vector check node of length z in H. The benefits of vectorizing a small matrix Hb to build a large matrix H are:                1. By using a different values of z, codes of rate kb/nb, where kb=nb−mb, can be designed for many different information sequence sizes k=z×kb from a single base matrix Hb.        2. Memory requirements are greatly reduced. With a structured LDPC design, only the base matrix Hb and the permutation for its 1's need to be stored, which requires significantly less memory since Hb is typically much smaller than H and the permutation can be very simple.        3. Encoding and decoding can be performed on groups of bits rather than by single bits. For example, a group of z messages can be fetched from memory, permuted, and passed between a vector variable node and a vector check node.        
Although the structured LDPC design philosophy greatly reduces the implementation complexity, a technique does not exist for designing the base matrix and assigning the permutation matrices for a given target H size which results in a LDPC code that has good error-correcting performance and can be efficiently encoded and decoded. Therefore, a need exists for a method and apparatus for designing a structured H and a method and apparatus for encoding and decoding data utilizing the structured H matrix.
USPTO Backgrounds
USPTO Backgrounds