Low density parity-check (LDPC) codes were first proposed by Gallager in 1962, and then “rediscovered” by MacKay in 1996. LDPC codes have been shown to achieve an outstanding performance that is very close to the Shannon transmission limit.
LDPC codes are based on a binary parity-check matrix H with n columns and m=n−k rows that has the following properties:                1. Each row consists of ρ number of “ones;”        2. Each column consists of γ number of “ones;”        3. The number of “ones” in common between any two columns, denoted as λ, is no greater than one; and        4. Both ρ and γ are small compared to the length of the code and the number of rows in H.        
For every given binary source message u={u0, . . . , uk−1} of length k, the LDPC encoder builds a binary codeword v={v0, . . . , vn−1} of length n where (n>k), such that Hv=0. The codeword consists of two parts. The first k bits of the codeword are equal to the bits of the source message. The other n−k bits of the codeword are the so-called parity-check bits p={p0, . . . , pn−k−1}. The main task of the encoder is to calculate these parity-check bits p for the given input message u.
To simplify matrix operations, the parity check matrix can be composed of ργ cells. The cells are arranged in ρ columns and γ rows, as given below.
  H  =      (                                        H                          0              ,              0                                                …                                      H                          0              ,                              ρ                -                1                                                                          …                          …                          …                                                  H                                          γ                -                1                            ,              0                                                …                                      H                                          γ                -                1                            ,                              ρ                -                1                                                          )  
Each cell is a t×t permutation matrix (n=ρt, n−k=γt). It contains exactly one value of “one” in every row and every column. Therefore, properties (1), (2), and (4) as listed above are satisfied by the construction of the matrix. An example of a cell-based parity-check matrix with k=32, n=56, γ=3, and ρ=7 is depicted in FIG. 2.
Matrix H can be considered as a concatenation of two sub matrices: A and B. Matrix A contains k columns and (n−k) rows. It includes the first k columns of H. Matrix B is a square matrix that contains (n−k) columns and (n−k) rows. It includes the last (n−k) columns of matrix H. The source equation Hv=0 can then be rewritten as Au+Bp=0, or Bp=x, where x=Au. Therefore, the calculation of the parity-check bits can be performed in two steps:                1. Calculate vector x by performing multiplication of the matrix A and the source message u; and        2. Calculate vector p by solving the linear system Bp=x.        
All existing LDPC encoder implementations divide the calculation of the parity-check bits into these two steps as explained above.
Matrix A is a so-called “low-density” matrix, in that it contains just a small number of “ones,” and so can be efficiently stored in a memory. An especially compact representation of matrix A is achieved if the matrix has the cell-based structure as described above. The simple structure of matrix A allows an efficient implementation of the first step.
The most difficult part of the encoding process is the second step. Different solutions have been proposed to accomplish this step, but the existing solutions either require too much computational effort, work with a very limited and inefficient matrix B, or use different structures for the matrices A and B and, therefore, complicate the decoder structure.
Some methods use a two-diagonal matrix B. In this case, step 2 can be performed very fast, but the simulation results show that this code is relatively weak. The reason for this is that many columns have only two “ones.” Another problem with this code is that the decoder must take into account the different structures of A and B. Therefore, the decoder becomes more complicated. In reality, this code does not fully satisfy the four conditions presented above, in that different columns of the parity-check matrix have a different number of “ones.” Such codes are generally called irregular LDPC codes.
In other methods, the matrix B is selected to be a non-singular matrix. According to such methods, B−1 exists and p=B−1x. To find the parity-check bits, the inverse matrix B−1 is multiplied by the vector x. The problem with this method is that the matrix B−1 is not a low-density matrix anymore. Some significant additional resources are needed to store this matrix and to efficiently perform the multiplication. Another problem with this approach is that we cannot compose the matrix B from permutation sub matrices, because matrices based on permutation cells are always singular. This means that the matrices A and B have different structures, and once again the decoder becomes more complicated.
What is needed, therefore, is a method that overcomes problems such as those described above, at least in part.