Patent Publication Number: US-10778251-B2

Title: Method and apparatus for encoding quasi-cyclic low-density parity check codes

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application claims the benefit of Provisional Application No. 62/714,607, filed Aug. 3, 2018, the entire contents of each of which are hereby incorporated by reference as if fully set forth herein. 
    
    
     FIELD OF INVENTION 
     The present invention generally relates to error correction coding for information transmission, storage and processing systems, such as wired and wireless communications systems such as optical communication systems, computer memories, mass data storage systems. More particularly, it relates to encoding method and apparatus for block codes such as low-density parity check (LDPC) codes, and more specifically to LDPC codes with block parity check matrices, called quasi-cyclic (QC) LDPC codes. 
     BACKGROUND OF THE INVENTION 
     Low-Density Parity Check (LDPC) Codes 
     Error correcting codes play a vital role in communication, computer, and storage systems by ensuring the integrity of data. The past decade has witnessed a surge in research in coding theory which resulted in the development of efficient coding schemes based on low-density parity check (LDPC) codes. Iterative message passing decoding algorithms together with suitably designed LDPC code ensembles have been shown to approach the information-theoretic channel capacity in the limit of infinite codeword length. LDPC codes are standardized in a number of applications such as wireless networks, satellite communications, deep-space communications, and power line communications. 
     For a (N, K) LDPC code with length N, dimension K, the parity check matrix (PCM) H of size M×N=(N−K)×N (assuming that H is full rank), is composed of a small number of ones. We denote the degree of the j-th column, i.e. the number of ones in the j-th column, by d v (j), 1≤j≤N. Similarly, we denote the degree of the i-th row, i.e. the number of ones in the i-th row, by d c (i), 1≤i≤M. Further, we define the maximum degree for the rows and columns: 
     
       
         
           
             
               
                 
                   
                     γ 
                     = 
                     
                       
                         max 
                         
                           1 
                           ≤ 
                           j 
                           ≤ 
                           N 
                         
                       
                       ⁢ 
                       
                         
                           d 
                           v 
                         
                         ⁡ 
                         
                           ( 
                           j 
                           ) 
                         
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     ρ 
                     = 
                     
                       
                         max 
                         
                           1 
                           ≤ 
                           i 
                           ≤ 
                           M 
                         
                       
                       ⁢ 
                       
                         
                           d 
                           c 
                         
                         ⁡ 
                         
                           ( 
                           i 
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
     When the number of ones in the columns and the rows of H is constant, the LDPC code is called regular, otherwise the LDPC code is said irregular. For regular LDPC codes, we have γ=d v =d v =d v (j), 1≤j≤N, and ρ=d c =d c (i), 1≤i≤M. The (d v , d c )-regular LDPC code ensemble represents a special interesting type of LDPC codes. For this type, the code rate is R=K/N=1−d v /d c  if the PCM H is full rank. 
     If a binary column vector of length N, denoted x=[x 1 , x 2 , . . . , x N ] T , is a codeword, then it satisfies Hx=0, where the operations of multiplication and addition are performed in the binary field GF(2), and 0 is the length-M all-zero column vector. x T  denotes the transposition of x, both for vectors and matrices. An element in a matrix can be denoted indifferently by H m,n  or H(m, n). Similarly, an element in a vector is denoted by x n  or x(n). The horizontal concatenation, respectively vertical concatenation, of vectors and matrices is denoted [A, B], respectively [A; B]. 
     Quasi-Cyclic LDPC Codes The present invention particularity relates to the class of quasi-cyclic LDPC codes (QC-LDPC). In QC-LDPC codes, the PCM H is composed of square blocks or submatrices of size L×L, as described in Equation (2), in which each block H i,j  is either (i) a all-zero L×L block, or (ii) a circulant permutation matrices (CPM). 
     
       
         
           
             
               
                 
                   H 
                   = 
                   
                     [ 
                     
                       
                         
                           
                             H 
                             
                               1 
                               , 
                               1 
                             
                           
                         
                         
                           
                             H 
                             
                               1 
                               , 
                               2 
                             
                           
                         
                         
                           … 
                         
                         
                           
                             H 
                             
                               1 
                               , 
                               
                                 N 
                                 b 
                               
                             
                           
                         
                       
                       
                         
                           
                             H 
                             
                               2 
                               , 
                               1 
                             
                           
                         
                         
                           
                             H 
                             
                               2 
                               , 
                               2 
                             
                           
                         
                         
                           … 
                         
                         
                           
                             H 
                             
                               2 
                               , 
                               
                                 N 
                                 b 
                               
                             
                           
                         
                       
                       
                         
                           ⋮ 
                         
                         
                           ⋮ 
                         
                         
                           ⋮ 
                         
                         
                           ⋮ 
                         
                       
                       
                         
                           
                             H 
                             
                               
                                 M 
                                 b 
                               
                               , 
                               1 
                             
                           
                         
                         
                           
                             H 
                             
                               
                                 M 
                                 b 
                               
                               , 
                               2 
                             
                           
                         
                         
                           … 
                         
                         
                           
                             H 
                             
                               
                                 M 
                                 b 
                               
                               , 
                               
                                 N 
                                 b 
                               
                             
                           
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
     A CPM is defined as the power of a primitive element of a cyclic group. The primitive element is defined, for example, by the L×L matrix, α, shown in Equation (3) for the case of L=8. As a result, a CPM α k , with k∈{0, . . . , L−1} has the form of the identity matrix, shifted k positions to the left. Said otherwise, the row-index of the nonzero value of the first column of α k , is k+1. The value of k is referred to as the CPM value. The main feature of a CPM is that it has only a single nonzero element in each row/column and can be defined by its first row/column together with a process to generate the remaining rows/columns. The simplicity of this process translates to a low hardware resources needed for realizing physical connections between subsets of codeword bits and parity check equations in an LDPC encoder or decoder. 
     
       
         
           
             
               
                 
                   α 
                   = 
                   
                     [ 
                     
                       
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           1 
                         
                       
                       
                         
                           1 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                       
                       
                         
                           0 
                         
                         
                           1 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                       
                       
                         
                           0 
                         
                         
                           0 
                         
                         
                           1 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                       
                       
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           1 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                       
                       
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           1 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                       
                       
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           1 
                         
                         
                           0 
                         
                         
                           0 
                         
                       
                       
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           1 
                         
                         
                           0 
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
     The PCM of a QC-LDPC code can be conveniently represented by a base matrix (or protograph matrix) B, with M b  rows and N b  columns which contains integer values, indicating the powers of the primitive element for each block H i,j . Consequently, the dimensions of the base matrix are related to the dimensions of the PCM the following way: M=M b  L, N=N b  L, and K=K b L (assuming that H is full rank). An example of matrices H and B for M b ×N b =4×5 and L=8 is shown in Equation (4). 
     
       
         
           
             
               
                 
                   
                     H 
                     = 
                     
                       [ 
                       
                         
                           
                             
                               α 
                               7 
                             
                           
                           
                             
                               α 
                               1 
                             
                           
                           
                             
                               α 
                               4 
                             
                           
                           
                             
                               α 
                               3 
                             
                           
                           
                             0 
                           
                         
                         
                           
                             
                               α 
                               2 
                             
                           
                           
                             0 
                           
                           
                             
                               α 
                               3 
                             
                           
                           
                             I 
                           
                           
                             
                               α 
                               4 
                             
                           
                         
                         
                           
                             
                               α 
                               4 
                             
                           
                           
                             
                               α 
                               6 
                             
                           
                           
                             0 
                           
                           
                             I 
                           
                           
                             
                               α 
                               2 
                             
                           
                         
                         
                           
                             I 
                           
                           
                             
                               α 
                               2 
                             
                           
                           
                             
                               α 
                               7 
                             
                           
                           
                             0 
                           
                           
                             
                               α 
                               5 
                             
                           
                         
                       
                       ] 
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     B 
                     = 
                     
                       [ 
                       
                         
                           
                             7 
                           
                           
                             1 
                           
                           
                             4 
                           
                           
                             3 
                           
                           
                             
                               - 
                               ∞ 
                             
                           
                         
                         
                           
                             2 
                           
                           
                             
                               - 
                               ∞ 
                             
                           
                           
                             3 
                           
                           
                             0 
                           
                           
                             4 
                           
                         
                         
                           
                             4 
                           
                           
                             6 
                           
                           
                             
                               - 
                               ∞ 
                             
                           
                           
                             0 
                           
                           
                             2 
                           
                         
                         
                           
                             0 
                           
                           
                             2 
                           
                           
                             7 
                           
                           
                             
                               - 
                               ∞ 
                             
                           
                           
                             5 
                           
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
     where I=α 0  is the identity matrix, and by convention α −∞ =0 is the all-zero L×L matrix. 
     General Circulant Matrices 
     In this invention, the blocks H i,j  are square L×L matrices, which are either a CPM or a all-zero block. However, the process of encoding a codeword x cannot be made from the PCM, but from a generator matrix G, as explained in paragraph 006. There are rare exceptions where the encoding can be performed directly with H, like in the case of low density generator matrices (LDGM) codes, but we do not discuss those cases in this disclosure. 
     General circulant matrices, not restricted to single CPMs, can appear during the process of computing G from H. A circulant matrix C is defined by the sum of w CPM with distinct powers: 
                   C   =       ∑     k   =   1     w     ⁢     α     i   k                 (   5   )               
where i k ≠i k′ , 0≤i k ≤L−1 and 0≤i k′ ≤L−1, ∀(k, k′). In this definition, w is called the weight of circulant C, and we have 0≤w≤L. Special cases of circulants are: (i) when w=0, the circulant is the all-zero block, (ii) when w=1, the circulant is a CPM.
 
     Encoding 
     This invention pertains to LDPC codes and their encoders and is applicable to any QC-LDPC code class, regular or irregular. 
     A codeword of an LDPC code, x=[x 1 , x 2 , . . . , x N ] T , is created from a vector of information bits u=[u 1 , u 2 , . . . , u K ] T , following the equation x=G u, where G is a generator matrix of the code. Without loss of generality, we assume that G is put in a systematic form, and that the codeword is organized as 
                   x   =     [         u           r         ]             (   6   )               
where r=[r 1 , r 2 , . . . , r M ] T  is the vector of redundancy bits.
 
     In general, a generator matrix G can be obtained from a parity check matrix H by computing the reduced row echelon form of H, by means of Gaussian Elimination (GE). Since H is composed of circulants, and it is known that the inverse of a circulant matrix is also a circulant matrix, it follows that G is also composed of circulants, although not necessarily reduced to CPMs. The encoding equation becomes: 
                   x   =       [         u           r         ]     =       Gu   ⇒   x     =       [         u           r         ]     =       [         I           P         ]     ⁢           ⁢   u                   (   7   )               
where P is a dense matrix composed of general circulants.
 
     For QC-LDPC codes, the GE process can be performed at the circulant level, making use only of operations on circulant matrices (multiplications, additions, inverse). This also means that the leading coefficients used to pivot the matrix during GE are themselves circulant matrices. Two operations can increase the weights of the circulants:
         When the leading coefficient is found, one needs to compute its inverse to create an identity block at the pivoting location on the main diagonal. If the leading coefficient is not a CPM, its inverse is usually a large weight circulant,   After the leading coefficient is turned into the identity, the corresponding block-row is combined with the other remaining block-rows in order to build the block-row echelon form. This combination of block-rows creates also large weight circulants.       

     An alternative of using a direct inverse of matrix H is to transform it into an upper triangular matrix, using a greedy Sparse Gaussian Elimination. In GE, one can stop the process when the block-row echelon form has been found, that is when the resulting matrix is in upper triangular form. For a matrix which contains all-zeros blocks and a small number of CPM, the Gaussian Elimination algorithm can be constrainted such that the resulting upper triangular matrix is the sparsest possible. Indeed, if the reduced block-row echelon form is unique and corresponds to the inverse of the original matrix, its block-row echelon form is not unique and depends on the sequence of leading coefficients that are used to perform the Gaussian Elimination. In other words, depending on the sequence of leading coefficients, one can get different encoding matrices with different sparseness. The encoding equation become 
                   Hx   =     0   ⇒     [           H   1                 H   2     ⁢           ]     ⁡     [         u           r         ]       =       0   ⇒         H   1     ⁢   u     +       H   2     ⁢   r         =   0                         (   8   )               
where H 1  is a dense matrix of size M b ×K b  composed of general circulants, and H 2  is an upper triangular matrix (at the block level), of size M b ×M b , also composed of general circulants. The encoder proceeds in two steps: (i) the first step consists in computing the parity check values of the first part of Equation (8), c=H 1  u, (ii) the second step recursively computes the values of the redundancy bits r using backward propagation, since the matrix H 2  is upper triangular.
 
     To summarize, matrices P or (H 1 , H 2 ) are used to perform the encoding, depending on the chosen encoding procedure. Those matrices are usually composed of general circulant blocks with large weights, typically of the order of L/2, where L is the circulant size. From the hardware complexity standpoint, it is advantageous to design design QC-LDPC codes for which the corresponding encoding matrix is as sparse as possible:
         1. first, the number of operations involved in (7) and (8) grows linearly with the density of matrices P and (H 1 , H 2 ). If those matrices have large weights, hardware implementations of (7) or (8) would suffer from either a large complexity, or a limited throughput. Having circulant blocks with large weights in the encoding matrices is not compliant with our objective of having an encoder with low complexity and high throughput.   2. matrices P and (H 1 , H 2 ) may contain a combination of circulant blocks with large weight, and others with low weights (even some CPM). However, the circuits that implement sparse circulant multiplication or dense circulant multiplication are different. As a result, an encoder using (7) or (8) would need a special circuit for the sparse multiplication, and a another circuit for dense multiplication, which is not optimal in terms of hardware re-use and lead to unnecessary large complexity.       

     It is therefore highly beneficial to consider an encoding procedure where the encoding matrices are sparse, composed of circulant blocks with low weights. The sparseness of the encoding matrix is not ensured by the classical encoding methods. We propose in this invention a method to use a very sparse representation of the encoding matrix, in order to obtain an encoding architecture which has both low complexity and high throughput. 
     Layers and Generalized Layers of QC-LDPC Codes 
     For a base matrix B of size (M b , N b ), the rows (or block-rows of H) are referred to as horizontal layers (or row layers). The concept of layer has been introduced originally for the case of regular array based QC-LDPC codes, where the base matrix is full of CPMs, and contains no α −∞ , i.e., no all-zero L×L block. 
     The concept of layers in a base matrix can be further extended to the concept of generalized layer (GL). The definition follows:
         A generalized layer is defined as the concatenation of two or more layers of the base matrix, such that in each block-column of the generalized layer there is at most one CPM while its other elements are all-zero blocks.   A full generalized layer has further the property that each block-column contains exactly one CPM.       

     This definition ensures that for a QC-LDPC code with maximum column degree γ, the PCM can be organized with at least γ GLs. For simplicity, we will assume that the number of GLs is always equal to the maximum column degree γ. 
       FIG. 1  shows an example of a PCM organized in γ=4 full GLs, indicated by  101 ,  102 ,  103  and  104 . In this example, each of the GL contains 4 simple layers, for a total of M b =16 block-rows in the base matrix. In general, each GL may contain a different number of block-rows, as long as the GL constraint in above definition is satisfied. In this example, the first GL  101  indicated in grey is composed of the first four block-rows of the base matrix. 
     In a PCM with a generalized layers structure, the block-rows of each generalized layer may be organized in an arbitrary order, and do not necessarily contain consecutive block-rows. In  FIG. 2 , we show an example of the matrix of  FIG. 1 , for which the block-rows of each GL have been regularly interleaved. Although the block-rows of the GL are not consecutive, this organization of a PCM still has the property that each GL contains a maximum of one non-zero block per column of the GL. For example the block rows  201 , shown in grey, indicates the block-rows which compose GL 1 , which are deduced from GL 1  in  FIG. 1  by block-row interleaving. 
     The purpose of the GL organization of the PCM is to be able to perform processing of at least γ PCM blocks in parallel, without data access conflicts. This allows a larger degree of parallelism in the encoder/decoder algorithms, and leads to higher processing throughputs. Although the concept of layers and generalized layers for QC-LDPC codes has been introduced in the literature to improve the efficiency of the LDPC decoders, we show in this disclosure that such structure can also be beneficial for the QC-LDPC encoder. 
     QC-LDPC with Minimum Row-Gap Between Circulants 
     The organization of H in generalized layers is proposed to improve the throughput of the encoder. However, in order to reach very high throughputs, the PCM needs to have other constraints, with respect to the location of the CPM in each block-row. This constraint, that will be used in the description of this invention, is called gap constraint, and reflects the number of all-zero blocks that are between two consecutive CPM in the same block-row of H. On  FIG. 1 , we show an example of two consecutive circulants in the first block-row of H which are separated by three all-zero blocks. The gap between these two circulants is gap=4 blocks. 
     Let b i  be the vector which stores the positions of nonzero blocks in the i-th row of the base matrix B. The vector b i  is a length d c (i) vector, such that B i,b     i,k    is a CPM and B i,j  with j≠b i,k  is a all-zero block. Let us further denote the gap profile of row i by the vector gap i  such that
 
gap i,k   =b   i,k+1   −b   i,k  1≤ k≤d   c ( i )−1  (9)
 
     For example, for the matrix in (4), we have b 3 =(1, 2, 4, 5), and gap 3 =(1, 2, 1). 
     For the whole QC-LDPC matrix, the minimum gap is defined as: 
     
       
         
           
             
               
                 
                   
                     gap 
                     * 
                   
                   = 
                   
                     
                       min 
                       
                         1 
                         ≤ 
                         i 
                         ≤ 
                         
                           M 
                           b 
                         
                       
                     
                     ⁢ 
                     
                       { 
                       
                         
                           min 
                           
                             1 
                             ≤ 
                             k 
                             ≤ 
                             
                               
                                 
                                   d 
                                   c 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   i 
                                   ) 
                                 
                               
                               - 
                               1 
                             
                           
                         
                         ⁢ 
                         
                           { 
                           
                             gap 
                             
                               i 
                               , 
                               k 
                             
                           
                           } 
                         
                       
                       } 
                     
                   
                 
               
               
                 
                   ( 
                   10 
                   ) 
                 
               
             
           
         
       
     
     Obviously, any QC-LDPC code has minimum gap*=1. As explained later in this disclosure, using QC-LDPC codes with a constraint on the minimum gap*&gt;1 allows to derive encoders with larger throughputs. The gap constraint gap*&gt;1 can be enforced by direct design of the PCM or the BM of the QC-LDPC code, or by re-arrangement of the columns. 
     SUMMARY OF THE INVENTION 
     The present invention relates to encoding of LDPC codes. In particular it relates to encoding of LDPC codes whose parity check matrices are organized in blocks. More specifically it relates to block matrices that are circulant permutation matrices, in which case the code is called quasi-cyclic (QC) QC-LDPC codes. 
     The present invention relates to a method and hardware apparatus to implement LDPC encoders in order to achieve both high encoding throughput as well low hardware resource usage. This is achieved by imposing various constraints on the structure of the parity check matrix and tayloring the hardware processing units to efficiently utilize these specific structural properties, in the process of computing the redundancy bits from the information bits, and combining them into a codeword. 
     The method of the present invention is directed in utilizing the organization of the parity check matrices of QC-LDPC codes into block-rows and block-columns. The block-rows of the parity check matrix are referred to as layers. 
     The method of the present invention can be used to implement encoding algorithms and devise hardware architectures for QC-LDPC codes. In the class of codes whose parity check matrices also contain all-zero blocks, codes with regular or irregular distribution of all-zero blocks and non-zero blocks inside the parity check matrix can be encoded using the present invention. 
     Additionally, in some embodiments, the method of the present invention imposes the constraints with respect to the relative locations of the non-zero blocks in each block-row. More specifically, the constraints relate to the minimal number of all-zero blocks that must separate any two consecutive non-zero blocks in any given block-row. This separation is referred to as the gap constraint. The advantage of said gap constraint is in improving processing throughput. 
     Additionally, in some embodiments, the method of the present invention organizes the parity check matrix into generalized layers, composed of the concatenation of several block-rows. Each generalized layer of the parity check matrix contains at most one non-zero block in each block-column. The advantage of generalized layers is that they allow parallelization of processing of the blocks of the parity check matrix without data access conflicts, which in turn increases the encoding throughput. 
     In some embodiments, each generalized layer contains the same number of block-rows, and in preferred embodiments, the parity check matrix has as many generalized layers as the maximum block-column degree. The block rows that compose the generalized layers can be chosen in an arbitrary way: consecutive, interleaved or irregular. 
     The method of the present invention achieves high throughput and low hardware usage by imposing an additional specific structure, called the three-region structure, to the parity check matrix, and utilizing a method for computing redundancy bits from information bits adapted to this specific structure. 
     The three-region structure of the parity check matrix described in this invention is a decomposition of said matrix into three regions, (R 1 , R 2 , R 3 ), wherein each region is processed by a specific method and a specific apparatus, while the apparata for processing different regions share a common hardware architecture. The present invention relates to a method and hardware apparatus to implement said three-region processing. 
     Various features of the present invention are directed to reducing the processing complexity with an hardware-efficient encoder apparatus by utilizing the three-region structure of the QC-LDPC code, In addition, it utilizes the gap constraint as well as composition, structure and position of generalized layers. From an implementation standpoint, the three-region encoding method of the present invention has the advantage of reducing the amount of resource required to implement the encoder. 
     In the present invention, the N b  block-columns of the parity check matrix are partitioned into three regions R 1 , R 2  and R 3 , defined by sub-matrices with N u , N t  and N s  block-columns, respectively. In the present invention, the sub-matrix in the region R 2  is block-upper triangular, and the sub-matrix in the region R 3  contains an invertible N s ×N s  block matrix S concatenated on the top of a (M b −N s )×N s  all-zero block-matrix. In some embodiments, additional structures are imposed on the three regions. In some embodiments, the sub-matrix in the region R 1  is organized into said generalized layers, and has a minimum gap constraint of at least 2 in all its blocks-rows. In some embodiments, the sub-matrix in the region R 2  is also organized into generalized layers, and has a minimum gap constraint of at least 2 for all the non-zero blocks of its diagonal. 
     In accordance with one embodiment of the present invention, the computation of redundancy bits involves computation of parity check bits, wherein blocks of information bits are processed in parallel, producing M b  blocks of parity check bits. These M b  blocks of parity check bits are initialized by multiplying information vector with the sub-matrix in region R 1 , and then processed using the sub-matrix of region R 2 . The upper triangular structure of the sub-matrix in the region R 2  facilitates a recursive computation of the parity check bits in region R 2 . Once the processing for regions R 1  and R 2  is finished, a small portion of N s  blocks of parity check bits are used to compute the last set of redundancy bits. One feature of the present invention is that the size N s  of the invertible matrix S in region R 3  is much smaller than the number of block-rows, which further reduces the computational resources needed to multiply its inverse S −1  with the N s  blocks of parity check bits, which computes the remaining set of N s  blocks of redundancy bits. 
     Additional features of the present invention are directed to reducing the hardware resource and delay of the storage and processing of the inverse S −1 . While all the submatrices in all regions are sparse, including the matrix S, the method of present invention ensures that the inverse matrix A=S −1  is also sparse. This feature additionally reduces storage requirements of hardware for processing of the matrix A. 
     Since the matrix S contains blocks of circulant permutation matrices and all-zero blocks, its inverse A is composed of circulant matrices and all-zero blocks, but the weight of circulant matrices in A may in general be large, usually of the order of half the circulant size. The method of the present invention is directed to using the matrices that have low-weight inverses, very much smaller than the circulant size. 
     One embodiment of the present invention capitalizes on the fact that the maximum circulant weight in the j-th block-column of A is no larger than w max,j . This allows to process sequentially the j-th block-column of A, performing only multiplications with circulant permutation matrices. 
     One feature of the present invention is that the encoding method can be implemented in hardware using a single architecture of the circuit, for the three regions R 1 , R 2  and R 3 . This implementation allows a maximum hardware re-use, and therefore minimizes the amount of resource needed to build the encoding circuit. In each region, the inputs, outputs, and control instructions of the hardware model are though different. 
     It will be seen in the detailed disclosure that the objects set forth above are efficiently attained and, because some changes may be made in carrying out the proposed method without departing from the spirit and scope of the invention, it is intended that all matter contained in the description and shown in the accompanying drawings shall be interpreted as illustrative and not in a limiting sense. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       For a more complete understanding of the invention, reference is made to the following description and accompanying drawings, in which: 
         FIG. 1  shows the organization of PCM H in d v =4 Generalized Layers; 
         FIG. 2  shows the organization of PCM H in Generalized Layers with interleaved rows; 
         FIG. 3  illustrates the structure of the disclosed parity check matrix; 
         FIG. 4  describes the top level common hardware for implementing the encoder, with two parts: a) Core encoding hardware, and b) Accumulator hardware; 
         FIG. 5  describes the encoding hardware in Region R 1 , with two parts: a) Core encoding hardware, and b) Accumulator hardware; 
         FIG. 6  describes the encoding hardware usage in Region R 2 , with two parts: a) Core encoding hardware, and b) Accumulator hardware; 
         FIG. 7  illustrates the procedure of expansion of a dense block-circulant matrix into a sparse representation; 
         FIG. 8  describes the encoding hardware usage in Region R 3  for first and second instruction types, with two parts: a) Core encoding hardware, and b) Accumulator hardware; and 
         FIG. 9  describes the encoding hardware usage in Region R 3  for third and fourth instruction types, with two parts: a) Core encoding hardware, and b) Accumulator hardware. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     Sparse Structure of the Parity Check Matrix H 
     In the present invention, the parity check matrix of an QC-LDPC code will be organized with the following form 
                   H   =     [       U       M   u     ×     N   u         ⁢          T       M   t     ×     N   t              ⁢           S       N   s     ×     N   s                   0       (       M   b     -     N   s       )     ×     N   s                 ]             (   11   )               
where 0 (M     b     −N     s     )×N     s    is an all-zero matrix.
 
     Similarly to the PCM H, the matrices (U, T, S) are composed of circulant blocks, and for ease of presentation, the dimensions of the submatrices are indicated in number of circulant blocks. This means that, following the notations of paragraph 0004,
 
 M   b   =M   u   =M   t =( N   t   +N   s )  (12)
 
 N   b =( N   u   +N   t   +N   s )  (13)
 
 K   b   =N   u   (14)
 
     The PCM is organized into three regions:
         Region R 1 : composed of the matrix U M     u     ×N     u   , which is a block matrix composed of a subset of the block columns of H,   Region R 2 : composed of the matrix T M     t     ×N     t   , which is block upper-triangular, i.e. T (M     t     −N     t     )+i,j =0 ∀ j &gt;N t −i, 0≤i≤N t −1,   Region R 3 : composed of the matrix S N     s     ×N     s    and an all-zero (M b −N s )×N s  block-matrix. The matrix S is a square block matrix and is assumed to be full rank and invertible.       

     An example of PCM with such structure is shown in  FIG. 3 . The matrix H is shown on  300 , with its decomposition in submatrices: the block matrix U  301 , the upper-triangular matrix T  302 , the square matrix S  303 , and finally the all-zero matrix 0 (M     b     −N     s     )×N     s    matrix  304 . 
     The present invention comprises also PCM deduced from the structure shown in (11) by any block-row and/or block-column permutation. 
     Organization of the PCM in Generalized Layers, with Minimum Gap 
     In a preferred embodiment of this invention, the PCM H is organized in generalized layers, which in turn imposes the constraint that the submatrices (U, T, S) are also organized in generalized layers. 
     For illustration purposes, we follow the organization of the interleaved generalized layers presented in paragraph 0007, other arrangements may be possible, and any other organization of the block-rows in GLs obtained through permutations of block-rows is also covered with this invention. As a non-limiting illustrative example, the structure of a PCM organized in GLs is shown in  FIG. 3  in the case of γ=4 GLs, each one composed of exactly M b /γ=4 block-rows. In general, the number of block-rows in each GL can be different. 
     In the example of figure  FIG. 3 , the k-th generalized layer GL k  is composed of the following M b /γ block-rows:
 
[ H   γi+k,1   ,H   γi+k,2   , . . . ,H   γi+k,N     b   ] 0≤ i&lt;M   b /γ  (15)
 
     The same block-row indices in matrices (U, T, S) compose the generalized layer GL k  for the corresponding submatrices. 
     In preferred embodiments of this invention, the matrices U and T further have gap constraints on their block-rows to help improving the throughput of the encoder. For the matrix U, we assume that each and every block-row has a minimum gap≥2. For the matrix T, we assume that, in each and every block-row, the gap between the diagonal block and the previous block is at least gap≥3. In the example of  FIG. 3 , the minimum gap for the diagonal blocks of T is gap=3, reached for the row-blocks j=6, j=8, j=11, j=12 and j=16. We do not assume any gap constraint for the non-diagonal blocks of T. 
     The combination of the GL organization and the gap constraints allows to derive a high-throughput architecture for region R 1  and region R 2  encoding. 
     Codeword Structure 
     The codeword x can be written as 
                   x   =     [           x   1               x   2             ⋮             x     N   b             ]             (   16   )               
where x j , 1≤j≤N b  is a binary column vector of length L. Now the equation H x=0 can be written as
 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             
                               H 
                               
                                 1 
                                 , 
                                 1 
                               
                             
                             ⁢ 
                             
                               x 
                               1 
                             
                           
                           + 
                           
                             
                               H 
                               
                                 1 
                                 , 
                                 2 
                               
                             
                             ⁢ 
                             
                               x 
                               2 
                             
                           
                           + 
                           … 
                           + 
                           
                             
                               H 
                               
                                 1 
                                 , 
                                 
                                   N 
                                   b 
                                 
                               
                             
                             ⁢ 
                             
                               x 
                               
                                 N 
                                 b 
                               
                             
                           
                         
                         = 
                         0 
                       
                       ⁢ 
                       
                         
 
                       
                       ⁢ 
                       
                         
                           H 
                           
                             2 
                             , 
                             1 
                           
                         
                         ⁢ 
                         
                           x 
                           1 
                         
                       
                       + 
                       
                         
                           H 
                           
                             2 
                             , 
                             2 
                           
                         
                         ⁢ 
                         
                           x 
                           2 
                         
                       
                       + 
                       … 
                       + 
                       
                         
                           H 
                           
                             2 
                             , 
                             
                               N 
                               b 
                             
                           
                         
                         ⁢ 
                         
                           x 
                           
                             N 
                             b 
                           
                         
                       
                     
                     = 
                     0 
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   ⋮ 
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       
                         
                           H 
                           
                             
                               M 
                               b 
                             
                             , 
                             1 
                           
                         
                         ⁢ 
                         
                           x 
                           1 
                         
                       
                       + 
                       
                         
                           H 
                           
                             
                               M 
                               b 
                             
                             , 
                             2 
                           
                         
                         ⁢ 
                         
                           x 
                           2 
                         
                       
                       + 
                       … 
                       + 
                       
                         
                           H 
                           
                             
                               M 
                               b 
                             
                             , 
                             
                               N 
                               b 
                             
                           
                         
                         ⁢ 
                         
                           x 
                           
                             N 
                             b 
                           
                         
                       
                     
                     = 
                     0 
                   
                 
               
               
                 
                   ( 
                   17 
                   ) 
                 
               
             
           
         
       
     
     All the operations in this disclosure are described as block computation in GF(2), that is using only L×L circulant blocks, e.g. H i,j  and binary vectors of length L, e.g. x j . In particular, the multiplication of x j  by a CPM is equivalent to a simple circular shift of the binary values in x j . With the definitions in 0004, the PCM and the exponents in the base matrix B are related as 
               H     i   ,   j       =       α     B     i   ,   j         .           
We have:
 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             H 
                             
                               i 
                               , 
                               j 
                             
                           
                           ⁢ 
                           
                             x 
                             j 
                           
                         
                         = 
                         
                           x 
                           j 
                         
                       
                     
                     
                       
                         
                           if 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             B 
                             
                               i 
                               , 
                               j 
                             
                           
                         
                         = 
                         0 
                       
                     
                   
                 
               
               
                 
                   ( 
                   18 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         
                           
                             H 
                             
                               i 
                               , 
                               j 
                             
                           
                           ⁢ 
                           
                             x 
                             j 
                           
                         
                         = 
                         
                           
                             [ 
                             
                               
                                 x 
                                 
                                   
                                     B 
                                     
                                       i 
                                       , 
                                       j 
                                     
                                   
                                   + 
                                   1 
                                 
                               
                               , 
                               
                                 x 
                                 
                                   
                                     B 
                                     
                                       i 
                                       , 
                                       j 
                                     
                                   
                                   + 
                                   2 
                                 
                               
                               , 
                               … 
                               ⁢ 
                               
                                   
                               
                               , 
                               
                                 x 
                                 L 
                               
                               , 
                               
                                 x 
                                 1 
                               
                               , 
                               … 
                               ⁢ 
                               
                                   
                               
                               , 
                               
                                 x 
                                 
                                   B 
                                   
                                     i 
                                     , 
                                     j 
                                   
                                 
                               
                             
                             ] 
                           
                           T 
                         
                       
                     
                     
                       
                         
                           if 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             B 
                             
                               i 
                               , 
                               j 
                             
                           
                         
                         ≥ 
                         1 
                       
                     
                   
                 
               
               
                 
                   ( 
                   19 
                   ) 
                 
               
             
           
         
       
     
     The hardware implementation of operation (18) is usually done using Barrel Shifters, such that H i,j  x j  is the barrel-shifted version of x j . 
     In the present invention, the codewords are further organized following the structure of the PCM described in paragraph 0036. We re-write Equation (16) as 
                   x   =     [         u           t           s         ]             (   20   )               
where u is the vector of information bits,
 
                   [         t           s         ]           
is the vector of redundancy bits, and
 
     
       
         
           
             
               
                 
                   
                     u 
                     = 
                     
                       [ 
                       
                         
                           
                             
                               u 
                               1 
                             
                           
                         
                         
                           
                             
                               u 
                               2 
                             
                           
                         
                         
                           
                             ⋮ 
                           
                         
                         
                           
                             
                               u 
                               
                                 N 
                                 u 
                               
                             
                           
                         
                       
                       ] 
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     t 
                     = 
                     
                       [ 
                       
                         
                           
                             
                               t 
                               1 
                             
                           
                         
                         
                           
                             
                               t 
                               2 
                             
                           
                         
                         
                           
                             ⋮ 
                           
                         
                         
                           
                             
                               t 
                               
                                 N 
                                 t 
                               
                             
                           
                         
                       
                       ] 
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     s 
                     = 
                     
                       [ 
                       
                         
                           
                             
                               s 
                               1 
                             
                           
                         
                         
                           
                             
                               s 
                               2 
                             
                           
                         
                         
                           
                             ⋮ 
                           
                         
                         
                           
                             
                               s 
                               
                                 N 
                                 s 
                               
                             
                           
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   21 
                   ) 
                 
               
             
           
         
       
     
     The binary column vectors u j , t j , and s j  are of length L, and for clarity, N u =K b  is the length of the information vector (the number of length-L sub-vectors in u), and N t +N s =M b  is the length of the redundancy vector. 
     Parity Checks Vector Structure 
     The encoding process involves computation of the vector of parity checks, denoted by c: 
     
       
         
           
             
               
                 
                   c 
                   = 
                   
                     [ 
                     
                       
                         
                           
                             c 
                             1 
                           
                         
                       
                       
                         
                           
                             c 
                             2 
                           
                         
                       
                       
                         
                           ⋮ 
                         
                       
                       
                         
                           
                             c 
                             
                               M 
                               b 
                             
                           
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   22 
                   ) 
                 
               
             
           
         
       
     
     Similar to the structure of the codeword vector, the vector of parity checks is also defined at the block level, i.e. c i  is a vector of L binary values. The parity checks are used to compute the vector of redundancy bits, and at the end of the encoding process, we must have H x=c=0. 
     Let us further define the vector of temporary parity checks, denoted c (j) , 1≤j≤N b , which contain the values of the parity checks using only the first j columns of H: 
     
       
         
           
             
               
                 
                   
                     [ 
                     
                       
                         
                           
                             c 
                             1 
                             
                               ( 
                               j 
                               ) 
                             
                           
                         
                       
                       
                         
                           
                             c 
                             2 
                             
                               ( 
                               j 
                               ) 
                             
                           
                         
                       
                       
                         
                           ⋮ 
                         
                       
                       
                         
                           
                             c 
                             
                               M 
                               b 
                             
                             
                               ( 
                               j 
                               ) 
                             
                           
                         
                       
                     
                     ] 
                   
                   = 
                   
                     
                       [ 
                       
                         
                           
                             
                               H 
                               
                                 1 
                                 , 
                                 1 
                               
                             
                           
                           
                             
                               H 
                               
                                 1 
                                 , 
                                 2 
                               
                             
                           
                           
                             … 
                           
                           
                             
                               H 
                               
                                 1 
                                 , 
                                 j 
                               
                             
                           
                         
                         
                           
                             
                               H 
                               
                                 2 
                                 , 
                                 1 
                               
                             
                           
                           
                             
                               H 
                               
                                 2 
                                 , 
                                 2 
                               
                             
                           
                           
                             … 
                           
                           
                             
                               H 
                               
                                 2 
                                 , 
                                 j 
                               
                             
                           
                         
                         
                           
                             ⋮ 
                           
                           
                             ⋮ 
                           
                           
                             ⋮ 
                           
                           
                             ⋮ 
                           
                         
                         
                           
                             
                               H 
                               
                                 
                                   M 
                                   b 
                                 
                                 , 
                                 1 
                               
                             
                           
                           
                             
                               H 
                               
                                 
                                   M 
                                   b 
                                 
                                 , 
                                 2 
                               
                             
                           
                           
                             … 
                           
                           
                             
                               H 
                               
                                 
                                   M 
                                   b 
                                 
                                 , 
                                 j 
                               
                             
                           
                         
                       
                       ] 
                     
                     ⁡ 
                     
                       [ 
                       
                         
                           
                             
                               x 
                               1 
                             
                           
                         
                         
                           
                             
                               x 
                               2 
                             
                           
                         
                         
                           
                             ⋮ 
                           
                         
                         
                           
                             ⋮ 
                           
                         
                         
                           
                             ⋮ 
                           
                         
                         
                           
                             
                               x 
                               j 
                             
                           
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   23 
                   ) 
                 
               
             
           
         
       
     
     The vector of temporary parity checks will be useful for explaining the three sequential steps of the encoding process. Note that from the definition of the PCM, the final temporary parity checks vector is equal to the all zero vector, c (N     b     ) =c=0. 
     Parity Checks Vector Structure with Generalized Layers 
     In a preferred embodiment of this invention, the PCM is organized in γGLs. This means that the vector of temporary parity checks can be partitioned in γ parts, each and every part corresponding to one GL. As an illustrative example, the vector of temporary parity checks c (j)  corresponding to the PCM of figure  FIG. 3  can be partitioned into γ=4 parts: 
                       GL   1     :     [       c   1     (   j   )       ;     c   5     (   j   )       ;     c   9     (   j   )       ;     c   13     (   j   )         ]       ⁢     
     ⁢       GL   2     :     [       c   2     (   j   )       ;     c   6     (   j   )       ;     c   10     (   j   )       ;     c   14     (   j   )         ]       ⁢     
     ⁢       GL   3     :     [       c   3     (   j   )       ;     c   7     (   j   )       ;     c   11     (   j   )       ;     c   15     (   j   )         ]       ⁢     
     ⁢       GL   4     :     [       c   4     (   j   )       ;     c   8     (   j   )       ;     c   12     (   j   )       ;     c   16     (   j   )         ]               (   24   )               
because according to  FIG. 3 , the GL 1  consists of block-rows 1, 5, 9 and 13, GL 2  consists of block-rows 2, 6, 10 and 14, etc.
 
     In this preferred embodiment, each part of the temporary parity checks vector can be stored in a separate memory, and computed using Equation (23) using a separate circuit. 
     Encoding Using Structure of H 
     In this paragraph, we describe the global encoding process that composes the main purpose of this invention, and we will describe in details each step in the next paragraphs. 
     According to Equation (11), the PCM is composed of three regions (R 1 , R 2 , R 3 ), which results in the decomposition of the encoding process into three steps, as explained below. 
     With the notations of paragraphs 0036 and 0038, Equation (17) can be now written as 
     
       
         
           
             
               
                 
                   
                     Uu 
                     + 
                     Tt 
                     + 
                     
                       
                         [ 
                         
                           
                             
                               S 
                             
                           
                           
                             
                               0 
                             
                           
                         
                         ] 
                       
                       ⁢ 
                       s 
                     
                   
                   = 
                   0. 
                 
               
               
                 
                   ( 
                   25 
                   ) 
                 
               
             
           
         
       
     
     The K b  blocks u 1 , u 2 , . . . , u K     b    contain the information bits and can be chosen freely. The vectors t and s contain the redundancy bits, and they must be calculated from (25). 
     The three sequential steps of the encoding process are defined as follows:
         Step 1: The first step computes the temporary parity checks vector c (K     b     )  using only region R 1 , i.e. c (K     b     ) =U u.   Step 2: The second step computes the first sub-vector of redundancy bits t using only region R 2 , with the values of c (K     b     )  as input. Another output of the second step is a new vector of temporary parity checks c (K     b     +N     t     ) , equal to c (K     b     +N     t     ) =U u+T t.   Step 3: The third step computes the second sub-vector of redundancy bits s using only region R 3 , with the values of c (K     b     +N     t     )  as input.       

     After the completion of the above three steps, the vector of redundancy bits [t; s] is assembled from the sub-vectors t and s and the encoded codeword x=[u; t; s] is obtained. 
     Reusable Hardware for Encoding of Regions R 1 , R 2  and R 3    
     As mentioned in paragraph 0041, the encoder is decomposed into three steps, each one based on a different structure of the corresponding sub-matrix of H. For the efficient hardware realization of the encoder, it is desirable to design an architecture which uses the same hardware units for all regions, since it allows to re-use the same circuit for the sequential processing of the three steps. 
     This invention proposes a single architecture for all three regions of the encoder, which is described in this paragraph. This single architecture is specifically oriented toward the preferred embodiment of the invention described in paragraph 0037, i.e. when the PCM is organized in γGLs, and the minimum gap of matrix U is gap*≥2. 
       FIG. 4  shows the schematic of the core of the encoder (indicated with a)), together with the details of the accumulator implementation, (indicated with b)). The particular example is shown for the case of γ=4. This same hardware model will be used for all three regions. The core of the encoder is composed of multiplexers  401  and  407 , merging logic  402 , and γ accumulators ( 403 ,  404 ,  405 ,  406 ). It also contains a recycle stream  413  which is included to render the hardware general enough to be used for all three regions. The details about how the recycle stream differ in each region are given in later paragraphs. 
     The core input  414  is composed of data, whose nature depends on the region being processed. In region R 1 , the inputs to the core are the information bits u. In region R 2  and R 3 , the input to the core is not used. The multiplexer block  401  is in charge of selecting the correct data to be sent to the merger block  402 , which could be either new input data for region R 1  processing, or the data from the recycle stream  413  for region R 2  and R 3  processing. 
     The merger block  402  processes the instructions received from the instruction stream  415  and associates them with data coming from  401 . The merger block contains a set of registers to store the data, in case they need to be used by several instructions. An instruction may also indicate that the merger block should pause for several clock cycles without consuming more instructions. 
     Each accumulator is in charge of a different GL, i.e. stores and updates its part of the data, and therefore contains a memory which stores L M b /γ bits, where M b /γ is the number of block-rows in a GL. The processed data is not the same in all regions: in regions R 1  and R 2 , the data stored in the accumulator are temporary parity check bits c (j) , while in region R 3 , the data are redundancy bits s. Thanks to the organization of the PCM in GLs, one and only one block of data (L bits) is accessed in parallel in each accumulator, and so memory  411  has a width of L and a depth of M b /γ. We refer to the contents of address a in memory k as mem k,a , 1≤k≤γ. The inputs/outputs to an accumulator are then the following:
         d in : L bits of data, indicated by  416 ,   b: the CPM value, telling the barrel shifter how much to shift the data by,   a: the address in the memory of the data that will be read and updated,   en: signal to enable the writing of the updated data to the memory,   d out : L bits of data, output from accumulator.       

     The information d in  and b go to the barrel shifter  410  which produces d bs =α b  d in , where α b  is the CPM being processed. According to the definition of the base matrix B (4), the shift value b is equal to the exponent b j,i  for the i-th column and the j-th row of the PCM. The address a is read from the memory  411  to get mem k,a  which is then XOR-ed with the barrel shifted data to obtain the accumulated binary values d out =mem k,a +d bs . The computed data d out  is written back to the same address in the memory and serves as output to the unit. The pipes  408  and  409  may or may not be necessary to keep the pipeline lengths matching for different paths. 
     The instructions  415  received by the core control how the data are processed. An example of the instruction structure is given with the following items:
         addresses: the γ addresses of the data sent to the accumulators,   shifts: the γ CPM values for the barrel shifters, sent to the accumulators,   updates: the γ enable signals for writing in the accumulator memories,   output: a bit that indicates whether the data should be output on stream  417 ,   recycle: a bit that indicates whether the accumulator outputs should be recycled,   selected: address for Mux B  408 ,   consume: whether the merging block  402  should take data from Mux A  401  or continue to use existing data,   pause: used by the merging block  402  to know when to pause for a given number of clock cycles.       

     Encoding of Region R 1    
     The encoding step corresponding to region R 1  consists of the computation of the temporary parity checks c (K     b     )  using the formula c (K     b     ) =U u: 
     
       
         
           
             
               
                 
                   
                     [ 
                     
                       
                         
                           
                             c 
                             1 
                             
                               ( 
                               
                                 K 
                                 b 
                               
                               ) 
                             
                           
                         
                       
                       
                         
                           
                             c 
                             2 
                             
                               ( 
                               
                                 K 
                                 b 
                               
                               ) 
                             
                           
                         
                       
                       
                         
                           ⋮ 
                         
                       
                       
                         
                           
                             c 
                             
                               M 
                               b 
                             
                             
                               ( 
                               
                                 K 
                                 b 
                               
                               ) 
                             
                           
                         
                       
                     
                     ] 
                   
                   = 
                   
                     
                       [ 
                       
                         
                           
                             
                               U 
                               
                                 1 
                                 , 
                                 1 
                               
                             
                           
                           
                             
                               U 
                               
                                 1 
                                 , 
                                 2 
                               
                             
                           
                           
                             … 
                           
                           
                             
                               U 
                               
                                 1 
                                 , 
                                 
                                   K 
                                   b 
                                 
                               
                             
                           
                         
                         
                           
                             
                               U 
                               
                                 2 
                                 , 
                                 1 
                               
                             
                           
                           
                             
                               U 
                               
                                 2 
                                 , 
                                 2 
                               
                             
                           
                           
                             … 
                           
                           
                             
                               U 
                               
                                 2 
                                 , 
                                 
                                   K 
                                   b 
                                 
                               
                             
                           
                         
                         
                           
                             ⋮ 
                           
                           
                             ⋮ 
                           
                           
                             ⋮ 
                           
                           
                             ⋮ 
                           
                         
                         
                           
                             
                               U 
                               
                                 
                                   M 
                                   b 
                                 
                                 , 
                                 1 
                               
                             
                           
                           
                             
                               U 
                               
                                 
                                   M 
                                   b 
                                 
                                 , 
                                 2 
                               
                             
                           
                           
                             … 
                           
                           
                             
                               U 
                               
                                 
                                   M 
                                   b 
                                 
                                 , 
                                 
                                   K 
                                   b 
                                 
                               
                             
                           
                         
                       
                       ] 
                     
                     ⁡ 
                     
                       [ 
                       
                         
                           
                             
                               u 
                               1 
                             
                           
                         
                         
                           
                             
                               u 
                               2 
                             
                           
                         
                         
                           
                             ⋮ 
                           
                         
                         
                           
                             ⋮ 
                           
                         
                         
                           
                             ⋮ 
                           
                         
                         
                           
                             
                               u 
                               
                                 K 
                                 b 
                               
                             
                           
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   26 
                   ) 
                 
               
             
           
         
       
     
     This computation can be done sequentially, column by column, from column j=1 to column j=K b  of U. Since H is sparse, U is sparse as well, and the j-th column of U is composed of d v (j) non-zero blocks. Let (i 1 , . . . , i d     v     (j) ) be the block indices of the non-zero blocks, with 1≤i k ≤M b . For ease of presentation, the column index is dropped from these notations. The process of encoding for region R 1  is described in Algorithm 1. 
     
       
         
           
               
             
               
                   
               
               
                 Algorithm 1: Encoding of region R 1   
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
            
               
                   
                 Input: vector of information bits u, region R 1  of the PCM U 
               
               
                   
                 Output: vector of temporary parity checks c (K     b     )   
               
               
                   
                 Step-a: initialize c (0)  = 0 
               
               
                   
                 for j = 1 to K b  do 
               
               
                   
                  | Step-b: compute the block indices of the non-zero blocks, 
               
               
                   
                  | (i 1  ,...,i d     v     (j) ), 
               
               
                   
                  | Step-c: compute the updated parity check values, 
               
               
                   
                  | for k = 1 to d v (j) do 
               
               
                   
                  | | c i     k     (j)  = c i     k     (j−1)  + U i     k     ,j  u j   
               
               
                   
                  | end 
               
               
                   
                 end 
               
               
                   
               
            
           
         
       
     
     The values of the temporary parity checks along the encoding process do not need to be stored, as only the last values c (K     b     )  are needed for the next step. The temporary parity check values can be efficiently stored into a single vector, initialized to 0 and updated sequentially using Algorithm 1. 
     In a preferred embodiment of the invention, the PCM is organized in γ interleaved generalized layers, such that the d v  (j) non-zero blocks in each and every column of U belong to a different generalized layer. A simple example of the preferred embodiment is when the QC-LDPC code is strictly regular, with d v (j)=d v =γ. In this case, the matrix U is formed with d v  generalized layers, each of one containing exactly one non-zero block per column. Under this preferred embodiment, the d v (j) computations of Step-c in Algorithm 1 can be performed in parallel, using a multiplicity of d v (j) circuits, without any memory access violation. Further details about the hardware realization of this step are described in the next paragraph. 
     Hardware Realization of Encoding of Region R 1    
       FIG. 5  shows the schematic of a) the core of the encoder, and b) the details of the accumulator implementation. The thick arrows indicate the flow of data and instructions during the processing of region R 1 . 
     In this region, the data which are processed by the accumulators ( 503 ,  504 ,  505 ,  506 ) are temporary parity checks, c (j) , 1≤j≤K b . Each one of the γ accumulators stores and updates its part of the temporary parity check bits. For the example of GL organization given in  FIG. 3 , the accumulator  503  is in charge of storing and processing the temporary parity check bits of the first GL, [c 1   (j) ; c 5   (j) ; c 9   (j) ; c 13   (j) ]. 
     The process of encoding for region R 1  is described in Algorithm 1. The parity check values c (j)  are split into γ parts, each of one being associated with one of the γGLs. The values in c (j)  corresponding to a specific GL are not necessarily consecutive, and are arranged in accordance with the GL organisation of the PCM (refer to paragraph 0007). Recall that the number of non-zero blocks in each column j is lower than than the number of GLs, d v (j)≤γ, and that each one of the non-zero block belong to a different GL. As a consequence, all the parity check bits for the j-th column, 
             [       c     i   1       (   j   )       ;   …   ⁢           ;     c     i       d   v     ⁡     (   j   )           (   j   )         ]         
can be updated in parallel, with no memory access violation, both for reading and writing.
 
     During the processing of column j in region R 1  the information bits u j  arrive as input to the encoder core  514 . For the j-th column, we indicate by b k,j  the shift value corresponding to the single non-zero block in the k-th GL, such that 
               α     b     k   ,   j         =       U       i   k     ,   j       .           
The address in memory  511  for the temporary parity checks being processed by the k-th accumulator for column j is denoted by a k,j . Both the shift values b k,j , and addresses a k,j  arrive as part of the instruction  515 . u j  is sent to all γ accumulators. While the first accumulator  503  receives b 1,j  and a 1,j , the second accumulator  504  receives b 2,j  and a 2,j  and so on. The accumulators use the information bits, shift values, and addresses to update the values of c i     k     (j)  stored in their memories.
 
     The critical path during R 1  is equal to the number of clock cycles taken to read the memory  511 , do the XOR with the barrel shifted data, and write the updated value back to the memory. If this process takes τ 1  clock cycles, it follows that a minimum gap of gap*=τ 1  in matrix U is necessary to achieve maximum throughput. A value of gap*=2 is usually sufficient to achieve high frequency for the synthesized architecture. 
     Encoding of Region R 2    
     In the region R 2 , the encoder computes the first set of redundancy bits t, as well as the updated values of the temporary parity check vector c (K     b     +N     t     ) . Thanks to the special structure of the matrices T and S, this second step of encoding can be performed with a very simple algorithm, and then a very simple hardware implementation, which we explain thereafter. 
     Since the temporary parity check c (K     b     )  are already computed from region R 1  and available, the Equation (25) becomes: 
     
       
         
           
             
               
                 
                   
                     c 
                     
                       ( 
                       Kb 
                       ) 
                     
                   
                   = 
                   
                     Tt 
                     + 
                     
                       
                         [ 
                         
                           
                             
                               S 
                             
                           
                           
                             
                               0 
                             
                           
                         
                         ] 
                       
                       ⁢ 
                       s 
                     
                   
                 
               
               
                 
                   ( 
                   27 
                   ) 
                 
               
             
           
         
       
     
     In the last N s  block-columns of the PCM, only the first N s  block-rows contain non-zero blocks, and the M b −N s  last block-rows of these columns are all-zero. As a result, the last N t =M b −N s  equations of the system (27) do not depend on s nor on S, and may be solved using solely the knowledge of T and c (K     b     ) . Solving the last N t =M b −N s  equations of the system (27) corresponds to the processing of region R 2 , and produces the vector of redundancy bits t. In addition, the matrix T is upper triangular and the encoding process for region R 2  can be performed by a simple backward iterative encoding process. Equation (27) can be written as: 
     
       
         
           
             
               
                 
                   
                     [ 
                     
                       
                         
                           
                             c 
                             1 
                             
                               ( 
                               
                                 K 
                                 b 
                               
                               ) 
                             
                           
                         
                       
                       
                         
                           ⋮ 
                         
                       
                       
                         
                           
                             c 
                             
                               N 
                               s 
                             
                             
                               ( 
                               
                                 K 
                                 b 
                               
                               ) 
                             
                           
                         
                       
                       
                         
                           
                             c 
                             
                               
                                 N 
                                 s 
                               
                               + 
                               1 
                             
                             
                               ( 
                               
                                 K 
                                 b 
                               
                               ) 
                             
                           
                         
                       
                       
                         
                           
                             c 
                             
                               
                                 N 
                                 s 
                               
                               + 
                               2 
                             
                             
                               ( 
                               
                                 K 
                                 b 
                               
                               ) 
                             
                           
                         
                       
                       
                         
                           ⋮ 
                         
                       
                       
                         
                           
                             c 
                             
                               M 
                               b 
                             
                             
                               ( 
                               
                                 K 
                                 b 
                               
                               ) 
                             
                           
                         
                       
                     
                     ] 
                   
                   = 
                   
                     
                       [ 
                       
                         
                           
                             
                               T 
                               
                                 1 
                                 , 
                                 1 
                               
                             
                           
                           
                             
                               T 
                               
                                 1 
                                 , 
                                 2 
                               
                             
                           
                           
                             … 
                           
                           
                             
                               T 
                               
                                 1 
                                 , 
                                 
                                   N 
                                   t 
                                 
                               
                             
                           
                           
                             
                               S 
                               
                                 1 
                                 , 
                                 1 
                               
                             
                           
                           
                             … 
                           
                           
                             
                               S 
                               
                                 1 
                                 , 
                                 
                                   N 
                                   s 
                                 
                               
                             
                           
                         
                         
                           
                             ⋮ 
                           
                           
                             ⋮ 
                           
                           
                             ⋮ 
                           
                           
                             ⋮ 
                           
                           
                             ⋮ 
                           
                           
                             ⋮ 
                           
                           
                             
                                 
                             
                           
                         
                         
                           
                             
                               T 
                               
                                 
                                   N 
                                   s 
                                 
                                 , 
                                 1 
                               
                             
                           
                           
                             
                               T 
                               
                                 
                                   N 
                                   s 
                                 
                                 , 
                                 2 
                               
                             
                           
                           
                             … 
                           
                           
                             
                               T 
                               
                                 
                                   N 
                                   s 
                                 
                                 , 
                                 
                                   N 
                                   t 
                                 
                               
                             
                           
                           
                             
                               S 
                               
                                 
                                   N 
                                   s 
                                 
                                 , 
                                 1 
                               
                             
                           
                           
                             … 
                           
                           
                             
                               S 
                               
                                 
                                   N 
                                   s 
                                 
                                 , 
                                 
                                   N 
                                   s 
                                 
                               
                             
                           
                         
                         
                           
                             
                               T 
                               
                                 
                                   
                                     N 
                                     s 
                                   
                                   + 
                                   1 
                                 
                                 , 
                                 1 
                               
                             
                           
                           
                             
                               T 
                               
                                 
                                   
                                     N 
                                     s 
                                   
                                   + 
                                   1 
                                 
                                 , 
                                 2 
                               
                             
                           
                           
                             … 
                           
                           
                             
                               T 
                               
                                 
                                   
                                     N 
                                     s 
                                   
                                   + 
                                   1 
                                 
                                 , 
                                 
                                   N 
                                   t 
                                 
                               
                             
                           
                           
                             0 
                           
                           
                             … 
                           
                           
                             0 
                           
                         
                         
                           
                             
                               T 
                               
                                 
                                   
                                     N 
                                     s 
                                   
                                   + 
                                   2 
                                 
                                 , 
                                 1 
                               
                             
                           
                           
                             
                               T 
                               
                                 
                                   
                                     N 
                                     s 
                                   
                                   + 
                                   2 
                                 
                                 , 
                                 2 
                               
                             
                           
                           
                             … 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             … 
                           
                           
                             0 
                           
                         
                         
                           
                             ⋮ 
                           
                           
                             ⋮ 
                           
                           
                             ⋮ 
                           
                           
                             ⋮ 
                           
                           
                             ⋮ 
                           
                           
                             ⋮ 
                           
                           
                             
                                 
                             
                           
                         
                         
                           
                             
                               T 
                               
                                 
                                   M 
                                   b 
                                 
                                 , 
                                 1 
                               
                             
                           
                           
                             0 
                           
                           
                             … 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             … 
                           
                           
                             0 
                           
                         
                       
                       ] 
                     
                     ⁡ 
                     
                       [ 
                       
                         
                           
                             
                               t 
                               1 
                             
                           
                         
                         
                           
                             
                               t 
                               2 
                             
                           
                         
                         
                           
                             ⋮ 
                           
                         
                         
                           
                             
                               t 
                               
                                 N 
                                 t 
                               
                             
                           
                         
                         
                           
                             
                               s 
                               1 
                             
                           
                         
                         
                           
                             ⋮ 
                           
                         
                         
                           
                             
                               s 
                               
                                 N 
                                 s 
                               
                             
                           
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   28 
                   ) 
                 
               
             
           
         
       
     
     As can be seen from Equation (28), the last equation of this system allows to get the first vector of redundancy bits t 1  with a very simple operation.
 
 t   1   =T   M     b     ,1   −1    c   M     b     (K     b     )   (29)
 
     where T M     b     ,1   −1  is the inverse of the CPM in the block indexed by (M b , 1) of T, which is itself a CPM. 
     Still using the upper-triangular property of T, we can proceed recursively from j=1 to j=N t  to compute the set of redundancy bits t j , 1≤j≤N t . Moreover, from the definition of the vector of temporary parity checks, the j-th equation can be simplified in the following way: 
     
       
         
           
             
               
                 
                   
                     t 
                     j 
                   
                   = 
                   
                     
                       
                         T 
                         
                           
                             
                               M 
                               b 
                             
                             - 
                             
                               ( 
                               
                                 j 
                                 - 
                                 1 
                               
                               ) 
                             
                           
                           , 
                           j 
                         
                         
                           - 
                           1 
                         
                       
                       ⁡ 
                       
                         ( 
                         
                           
                             c 
                             
                               
                                 M 
                                 b 
                               
                               - 
                               
                                 ( 
                                 
                                   j 
                                   - 
                                   1 
                                 
                                 ) 
                               
                             
                             
                               ( 
                               
                                 K 
                                 - 
                                 b 
                               
                               ) 
                             
                           
                           + 
                           
                             
                               ∑ 
                               
                                 k 
                                 = 
                                 1 
                               
                               
                                 j 
                                 - 
                                 1 
                               
                             
                             ⁢ 
                             
                               
                                 T 
                                 
                                   
                                     
                                       M 
                                       b 
                                     
                                     - 
                                     
                                       ( 
                                       
                                         j 
                                         - 
                                         1 
                                       
                                       ) 
                                     
                                   
                                   , 
                                   k 
                                 
                               
                               ⁢ 
                               
                                 t 
                                 k 
                               
                             
                           
                         
                         ) 
                       
                     
                     = 
                     
                       
                         T 
                         
                           
                             
                               M 
                               b 
                             
                             - 
                             
                               ( 
                               
                                 j 
                                 - 
                                 1 
                               
                               ) 
                             
                           
                           , 
                           j 
                         
                         
                           - 
                           1 
                         
                       
                       ⁢ 
                       
                         c 
                         
                           
                             M 
                             b 
                           
                           - 
                           
                             ( 
                             
                               j 
                               - 
                               1 
                             
                             ) 
                           
                         
                         
                           ( 
                           
                             
                               K 
                               b 
                             
                             + 
                             
                               ( 
                               
                                 j 
                                 - 
                                 1 
                               
                               ) 
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   30 
                   ) 
                 
               
             
           
         
       
     
     Using Equations (28) and (30), one can deduce the process for encoding in region R 2 , described in Algorithm 2. Similarly to the encoding in region R 1 , the matrix T is composed of a subset of columns of the matrix H, and therefore is sparse. The j-th column of T is composed of d v (j) non-zero blocks. Let (i 1 , . . . , i d     v     (j) ) be the block indices of the non-zero blocks, with 1≤i k ≤(M b −j+1). 
     
       
         
           
               
             
               
                   
               
               
                 Algorithm 2: Encoding of region R 2   
               
               
                   
               
             
            
               
                   
               
            
           
           
               
            
               
                 Input: vector of temporary parity checks c (K     b     ) , region R 2  of the PCM T 
               
               
                 Output: vector of temporary parity checks c (K   b    +N     t     ) , first set of 
               
               
                 redundancy bits t 
               
               
                 for j = 1 to N t  do 
               
               
                  | Step-a: compute t j  from Equation (30), 
               
               
                  | Step-b: compute the block indices of the non-zero blocks in column 
               
               
                  |  j of T: (i 1 ,...,i d     v     (j) ), 
               
               
                  | Step-c: compute the updated parity check values: 
               
               
                  | for k = 1 to d v (j) do 
               
               
                  | | c i     k     (K   b   +j) = c   i     k     K   b    +(j−1)  + T i     k,j    t j   
               
               
                  | end 
               
               
                 end 
               
               
                   
               
            
           
         
       
     
     The values of the temporary parity checks along the encoding process do not need to be stored, as only the last values c (K     b     +N     t     )  are needed for the third step. The temporary parity check values can be efficiently stored into a single vector, initialized to c (K     b     )  and updated sequentially using Algorithm 2. 
     In a preferred embodiment of the invention, the PCM is organized in γ interleaved generalized layers, such that the d v (j) non-zero blocks in each and every column of U belong to different generalized layers. An example of the preferred embodiment is when the QC-LDPC code is strictly regular, with d v (j)=d v =γ. In this case, the matrix T is formed of d v  generalized layers, each of one containing exactly one non-zero block per column. Under this preferred embodiment, the d v (j) computations of Step-c in Algorithm 2 can be performed in parallel, using a multiplicity of d v (j) circuits, without any memory access violation. Further details on the hardware realization of this step are described in the next paragraph. 
     Hardware Realization of Encoding of Region R 2    
     To simplify the description of the hardware for the encoding of region R 2 , we assume without loss of generality that the CPM on the diagonal of T are identity matrices. Note that one can easily enforce this constraint for any QC-LDPC code following the structure of (11), by simple block-row and block-column transformations. With this constraint Step-a in Algorithm 2 simplifies to 
               t   j     =     c       M   b     -     (     j   -   1     )         (       K   b     +     (     j   -   1     )       )             
where j is the column index within region R 2 .
 
     Since the temporary parity checks c are stored in the accumulator memories, outputting the values of the L redundancy bits t j  requires a simple reading the correct address from the correct memory and outputting those L bits. The rest of the processing for region R 2  reduces to updating the values of c i     k   , as described in Step-c of Algorithm 2. 
       FIG. 6  shows the path of data and instructions required to process one column in region R 2 . The input of the core  614  is not used in this region. Two sequential use of the hardware, driven by two different instructions  615  are necessary to process one column. The processing associated with the first instruction, named stage 2a, is shown in thick solid arrows, and the processing associated with the second instruction, named stage 2b, is shown in thick dashed arrows. The recycle stream  613  is shown as have solid and half dashed because it is produced by the first instruction, but used as input by the second instruction. 
     During stage 2a, the first instruction contains the memory addresses a k,j  of 
               c       M   b     -     (     j   -   1     )         (       K   b     +     (     j   -   1     )       )       ,         
used in the k-th accumulator, and an indicator telling in which memory, i.e. in which accumulator, the values are stored. This last instruction is used by Mux B  607 . In the example drawn in  FIG. 6 , the temporary parity check values are stored in accumulator  606 . The value of
 
             c       M   b     -     (     j   -   1     )         (       K   b     +     (     j   -   1     )       )           
goes in the recycle stream  613 , where it is acted upon by the second instruction.
 
     During stage 2b, the second instruction tells to output 
             c       M   b     -     (     j   -   1     )         (       K   b     +     (     j   -   1     )       )           
on the core output  617  and also send it as input to the γ accumulators, where together with the addresses a k,j  and shift values b k,j  from the second instruction, it is used to update the
 
             c     i   k       (       K   b     +   j     )           
values.
 
     The time between stage 2a and stage 2b processing depends on the length of the pipeline given by the thick solid line. To achieve high throughput, the first instruction and second instruction for different columns are interleaved. Table 1 shows an example of how the instructions might be interleaved if the pipeline for the first instruction takes three clock cycles. 
     
       
         
           
               
               
             
               
                 TABLE 1 
               
               
                   
               
               
                 Clock Cycle 
                 Instruction 
               
               
                   
               
             
            
               
                 1 
                 first instruction for j = 0 
               
               
                 2 
                 pause 
               
               
                 3 
                 first instruction for j = 1 
               
               
                 4 
                 second instruction for j = 0 
               
               
                 5 
                 first instruction for j = 2 
               
               
                 6 
                 second instruction for j = 1 
               
               
                 7 
                 first instruction for j = 3 
               
               
                 8 
                 second instruction for j = 2 
               
               
                 9 
                 . . . 
               
               
                   
               
            
           
         
       
     
     To allow this interleaving it is desirable that the pipeline for the first instruction takes an odd number of clock cycles. 
     In region R 2 , the time τ 1  to read and then update the memory is not the critical path anymore. The time τ 2  between reading from a temporary parity check associated with the diagonal, to updating the parity check associated in a different memory, becomes dominant. This path goes from the memory  611  out of the accumulator  606 , through Mux B  607 , Mux A  601 , merging block  602 , back into a different accumulator, through the pipe  608 , barrel shifter  610 , XOR  612  and finally back to the memory  611 . The final writing in the memory must be completed before reading the diagonal parity for that memory address. For example, if τ 2  is 5 clock cycles, then a gap=3 is necessary between the diagonal block and the other blocks of the same block-row, for the throughput to be maximum. Indeed, A path which takes 5 clock cycles imposes a gap constraint on the corresponding block-row of gap=3 since two instructions are required for every column. A gap=3 means that there will be 6 clock cycles between the first instruction of the first column, and the first instruction of the next column which requires that updated data. These 6 clock cycles are sufficient for a pipeline of length τ 2 =5. 
     For blocks outside the diagonal, the gap constraint is more relaxed. If the pipeline length for τ 1  is 2 clock cycles, then no gap constraint is imposed since we already need 2 clock cycles to process each column. As mentioned in paragraph 0044, a pipeline length of 2 clock cycles for τ 1  is usually sufficient to achieve high frequency for the synthesized architecture. 
     Encoding of Region R 3    
     In the region R 3 , the encoder computes the last part of the codeword, i.e. the vector of redundancy bits s, using: 
     
       
         
           
             
               
                 
                   
                     c 
                     
                       ( 
                       
                         
                           K 
                           b 
                         
                         + 
                         
                           N 
                           t 
                         
                       
                       ) 
                     
                   
                   = 
                   
                     
                       Uu 
                       + 
                       Tt 
                     
                     = 
                     
                       
                         [ 
                         
                           
                             
                               S 
                             
                           
                           
                             
                               0 
                             
                           
                         
                         ] 
                       
                       ⁢ 
                       s 
                     
                   
                 
               
               
                 
                   ( 
                   31 
                   ) 
                 
               
             
           
         
       
     
     The first N s  equations of the system in Equation (31) are sufficient to get those values: 
                     c     1   :     N   s         (       K   b     +     N   t       )       =       [           c   1     (       K   b     +     N   t       )                 c   2     (       K   b     +     N   t       )               ⋮             c     N   s       (       K   b     +     N   t       )             ]     =       [           S     1   ,   1             S     1   ,   2           …         S     1   ,     N   s                   S     2   ,   1             S     2   ,   2           …         S     2   ,     N   s                 ⋮       ⋮       ⋮       ⋮             S       N   s     ,   1             S       N   s     ,   2           …         S       N   s     ,     N   s               ]     ⁡     [           s   1               s   2             ⋮             s     N   s             ]                 (   32   )               
where
 
             c     1   :     N   s         (       K   b     +     N   t       )           
gather the first N s  values of vector c (K     b     +N     t     )  
 
     In this disclosure, the matrix S is assumed to have full rank, and therefore is invertible. Let A=S −1  denote its inverse. The vector of redundancy bits s is computed using: 
     
       
         
           
             
               
                 
                   s 
                   = 
                   
                     
                       
                         S 
                         
                           - 
                           1 
                         
                       
                       ⁢ 
                       
                         c 
                         
                           1 
                           : 
                           
                             N 
                             s 
                           
                         
                         
                           ( 
                           
                             
                               K 
                               b 
                             
                             + 
                             
                               N 
                               t 
                             
                           
                           ) 
                         
                       
                     
                     = 
                     
                       Ac 
                       
                         1 
                         : 
                         
                           N 
                           s 
                         
                       
                       
                         ( 
                         
                           
                             K 
                             b 
                           
                           + 
                           
                             N 
                             t 
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   33 
                   ) 
                 
               
             
           
         
       
     
     As explained in paragraph 006, A is composed of possibly large weight circulant blocks. Let w i,j  denote the weight of the circulant in A i,j . The typical weight of an inverse of a general circulant is close to L/2, which could lead to a large hardware complexity and/or a low encoding throughput. Although this invention applies to arbitrary matrices with any inverse weight, the efficiency of our encoder relies on matrices S for which the inverse is composed of low weight circulants, i.e. w i,j &lt;&lt;L/2, 1≤i, j≤Ns. We obtain such low weight inverse matrix by an optimized selection of the CPM shifts in S. Some examples are given in paragraphs 0049 and 0050. 
     This invention describes how to utilize a sparse representation of matrix A by relying on a special technique, described as follows. First, A is expanded into a rectangular matrix E, composed only of CPMs. Let us recall that A is composed of general circulant blocks, with weights w i,j , 1≤i,j≤N s . Each block in A can be written as: 
                     A     i   ,   j       =       ∑     k   =   1       w     i   ,   j         ⁢     A     i   ,   j       (   k   )                 (   34   )               
where A i,j   (k) , ∀k is a CPM.
 
     Let w max,j =max i  {w i,j } be the maximum circulant weight in block-column j of A, 1≤j≤N s . When the weight of a circulant is smaller than the maximum weight of the corresponding column, we further impose that A i,j   (k) =0, for w i,j ≤k≤w max,j , such that: 
     
       
         
           
             
               
                 
                   
                     
                       A 
                       
                         i 
                         , 
                         j 
                       
                     
                     = 
                     
                       
                         
                           ∑ 
                           
                             k 
                             = 
                             1 
                           
                           
                             w 
                             
                               i 
                               , 
                               j 
                             
                           
                         
                         ⁢ 
                         
                           A 
                           
                             i 
                             , 
                             j 
                           
                           
                             ( 
                             k 
                             ) 
                           
                         
                       
                       = 
                       
                         
                           ∑ 
                           
                             k 
                             = 
                             1 
                           
                           
                             w 
                             
                               
                                 ma 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 x 
                               
                               , 
                               j 
                             
                           
                         
                         ⁢ 
                         
                           A 
                           
                             i 
                             , 
                             j 
                           
                           
                             ( 
                             k 
                             ) 
                           
                         
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     1 
                     ≤ 
                     i 
                     ≤ 
                     
                       N 
                       s 
                     
                   
                 
               
               
                 
                   ( 
                   35 
                   ) 
                 
               
             
           
         
       
     
     The expanded matrix E is composed of the concatenation of columns deduced from Equation (35): 
                   E   =     [           A     1   ,   1       (   1   )           …         A     1   ,   1       (     w       ma   ⁢           ⁢   x     ,   1       )           …       …       …         A     1   ,     N   s         (   1   )           …         A     1   ,     N   s         (     w       m   ⁢           ⁢   ax     ,     N   s         )                 A     2   ,   1       (   1   )           …         A     2   ,   1       (     w       m   ⁢           ⁢   ax     ,   1       )           …       …       …         A     2   ,     N   s         (   1   )           …         A     2   ,     N   s         (     w       m   ⁢           ⁢   a   ⁢           ⁢   x     ,     N   s         )               ⋮       ⋮       ⋮       ⋮       ⋮       ⋮       ⋮       ⋮       ⋮             A       N   s     ,   1       (   1   )           …         A       N   s     ,   1       (     w       m   ⁢           ⁢   ax     ,   1       )           …       …       …         A       N   s     ,     N   s         (   1   )           …         A       N   s     ,     N   s         (     w       m   ⁢           ⁢   ax     ,     N   s         )             ]             (   36   )               
and we denote by E j  the expansion of the j-th block-column of A, such that E=[E 1 , . . . , E N     s   ]. E is therefore a sparse rectangular matrix, of size (N s , Σ j  w max,j ), composed only of CPMs.
 
     An example of the expansion from A to E is shown in figure  FIG. 7 , for the case of N s =4. The matrix of the circulant weights for the inverse A is shown with  701 . The matrix E is shown with  702 , and the four columns of A are expanded into four block matrices (E 1 , E 2 , E 3 , E 4 ) labeled  703  to  706 . The gray blocks represent the locations of the CPMs, while the white blocks indicate that the block is all-zero. We show the general case where the maximum column weights w max,j  may be different from each other. In this example, we have w max,1 =3, w max,2 =4, w max,3 =2 and w max,4 =4. We can also see with this example that the expanded matrix has an irregular distribution of the number of CPM in each column. Let us denote by d v (j,n) the number of CPM in the n-th column of E j . 
     The encoding of the redundancy bits s can be made using E instead of A, since (33) can be written as: 
                   s   =       [       E   1     ,   …   ⁢           ,     E     N   s         ]     ⁡     [           c   1     (       K   b     +     N   t       )               ⋮             c   1     (       K   b     +     N   t       )               ⋮           ⋮             c     N   s       (       K   b     +     N   t       )               ⋮             c     N   s       (       K   b     +     N   t       )             ]               (   37   )               
where c j   (K     b     +N     t     )  is copied w max,j  times in the right hand side vector c. The Algorithm 3 is used to compute the second set of redundancy bits s, deduced from Equation (37). In the algorithm, E j (i,n) represents the CPM in the i-th row and the n-th column of matrix E j .
 
     For example in the matrix E of  FIG. 7 , the matrix E 3    705  can be written as 
     
       
         
           
             
               
                 
                   
                     E 
                     3 
                   
                   = 
                   
                     [ 
                     
                       
                         
                           
                             
                               E 
                               3 
                             
                             ⁡ 
                             
                               ( 
                               
                                 1 
                                 , 
                                 1 
                               
                               ) 
                             
                           
                         
                         
                           0 
                         
                       
                       
                         
                           
                             
                               E 
                               3 
                             
                             ⁡ 
                             
                               ( 
                               
                                 2 
                                 , 
                                 1 
                               
                               ) 
                             
                           
                         
                         
                           
                             
                               E 
                               3 
                             
                             ⁡ 
                             
                               ( 
                               
                                 2 
                                 , 
                                 2 
                               
                               ) 
                             
                           
                         
                       
                       
                         
                           
                             
                               E 
                               3 
                             
                             ⁡ 
                             
                               ( 
                               
                                 3 
                                 , 
                                 1 
                               
                               ) 
                             
                           
                         
                         
                           
                             
                               E 
                               3 
                             
                             ⁡ 
                             
                               ( 
                               
                                 3 
                                 , 
                                 2 
                               
                               ) 
                             
                           
                         
                       
                       
                         
                           
                             
                               E 
                               3 
                             
                             ⁡ 
                             
                               ( 
                               
                                 4 
                                 , 
                                 1 
                               
                               ) 
                             
                           
                         
                         
                           
                             
                               E 
                               3 
                             
                             ⁡ 
                             
                               ( 
                               
                                 4 
                                 , 
                                 2 
                               
                               ) 
                             
                           
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   38 
                   ) 
                 
               
             
           
         
       
     
     
       
         
           
               
             
               
                   
               
               
                 Algorithm 3: Encoding of region R 3   
               
               
                   
               
             
            
               
                   
               
            
           
           
               
            
               
                 Input: vector of temporary parity checks c 1:Ns   (K   b    +   N     t     ) , sparse inverse 
               
               
                 representation E of region R 3  of the PCM 
               
               
                 Output: second set of redundancy bits s 
               
               
                 Step-a: initialize s = 0 
               
               
                 for j = 1 to N s  do 
               
               
                  | for n = 1 to w max,j  do 
               
               
                  | | Step-b: compute the block indices of the non-zero blocks in column 
               
               
                  | |  n of E j : (i 1 ,...,i d     v     (j,n) ), 
               
               
                  | | Step-c: compute the updated redundancy bits: 
               
               
                  | | for k = 1 to d v (j,n) do 
               
               
                  | | s i     k    = s i     k    + E j (i k , n) c j   (K   b    +   N     t     )   
               
               
                  | | end 
               
               
                  | end 
               
               
                 end 
               
               
                   
               
            
           
         
       
     
     In a preferred embodiment of the invention, the size of the matrix S is chosen to be a multiple of the number of generalized layers γ, N s =l γ. This preferred embodiment allows to re-use for region R 3  the hardware developed for region R 1  and R 2 , as explained in the next paragraph. Two use case of this preferred embodiment are described in paragraphs 0049 and 0050. 
     Hardware Realization of Encoding of Region R 3    
     There are two steps to output the second set of redundancy bits s in region R 3 . 
     First the vector 
             c     1   :     N   s         (       K   b     +     N   t       )           
is multiplied by the sparse representation E of inverse matrix A (37) and the resulting bits s are stored in the accumulator memories. We refer to this as stage 3a. Once computed, the values of s are read from the accumulator memories and output to  817 . We refer to this second step as stage 3b.
 
     During stage 3a, the values of s need to be iteratively updated and stored in the accumulators  803  to  806 . In principle, one would need an use additional memory to store s, but here we will capitalize on the special structure of the PCM (11). Indeed, at the end of region R 2  processing, thanks to the upper triangular structure of T, the temporary parity checks 
             c         N   s     +   1     :     M   b         (       K   b     +     N   t       )           
are all zero, and do not need to be updated or used during the processing of region R 3 . We propose in this invention to use N s /γ addresses of the available memory in each of the γ accumulator memories  811 , to store the values of s. For example, one could use the memory addresses which correspond to
 
     
       
         
           
             
               c 
               
                 
                   
                     N 
                     s 
                   
                   + 
                   1 
                 
                 : 
                 
                   2 
                   ⁢ 
                   
                     N 
                     s 
                   
                 
               
               
                 ( 
                 
                   
                     K 
                     b 
                   
                   + 
                   
                     N 
                     t 
                   
                 
                 ) 
               
             
             . 
           
         
       
     
     The processing for stage 3a is similar to the processing in region R 2 . The core input  814  is not used, and the main difference is that after the value of c j  is read from an accumulator memory, the values of s are updated w max,j  times, instead of one update in region R 2 . During the w max,j  updates corresponding to Step-c in Algorithm 3, the values of c j  are hold in registers in the merge module  802 . In total, for stage 3a, there is then a sequence of N s  read instructions to retrieve the values of the temporary parity checks 
               c     1   :     N   s         (       K   b     +     N   t       )       ,         
and Σ 1≤j≤N     s    w max,j  update instructions to compute the values of redundancy bits s and store them in the accumulator memories, at the addresses of
 
     
       
         
           
             
               c 
               
                 
                   
                     N 
                     s 
                   
                   + 
                   1 
                 
                 : 
                 
                   2 
                   ⁢ 
                   
                     N 
                     s 
                   
                 
               
               
                 ( 
                 
                   
                     K 
                     b 
                   
                   + 
                   
                     N 
                     t 
                   
                 
                 ) 
               
             
             . 
           
         
       
     
       FIG. 8  shows the flow of instructions and data during the processing of stage 3a. The processing of the read instruction is shown as solid thick arrows, and the processing of an update instruction is shown as dashed thick arrows. 
     As in region R 2 , we can also interleave the instructions to maximize the throughput, but with more pauses in the sequence because of the fact that there are more update instructions than read instructions. Table 2 shows an example of a sequence of interleaved instructions to calculate s, for the case of N s =γ=4, when the inverse matrix A has maximum weights w max,1 =3, w max,2 =2, w max,3 =1 and w max,4 =4. 
     
       
         
           
               
               
             
               
                 TABLE 2 
               
               
                   
               
               
                 Clock Cycle 
                 Instruction 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
            
               
                 1 
                 read instruction for block-column 1 
               
               
                 2 
                 pause 
               
               
                 3 
                 pause 
               
               
                 4 
                 update instruction 1 for block-column 1 
               
               
                 5 
                 pause 
               
               
                 6 
                 update instruction 2 for block-column 1 
               
               
                 7 
                 read instruction for block-column 2 
               
               
                 8 
                 update instruction 3 for block-column 1 
               
               
                 9 
                 pause 
               
               
                 10 
                 update instruction 1 for block-column 2 
               
               
                 11 
                 read instruction for block-column 3 
               
               
                 12 
                 update instruction 2 for block-column 2 
               
               
                 13 
                 read instruction for block-column 4 
               
               
                 14 
                 update instruction 1 for block-column 3 
               
               
                 15 
                 pause 
               
               
                 16 
                 update instruction 1 for block-column 4 
               
               
                 17 
                 pause 
               
               
                 18 
                 update instruction 2 for block-column 4 
               
               
                 19 
                 pause 
               
               
                 20 
                 update instruction 3 for block-column 4 
               
               
                 21 
                 pause 
               
               
                 22 
                 update instruction 4 for block-column 4 
               
               
                   
               
            
           
         
       
     
     Once s is calculated and stored in the accumulator memories, stage 3b begins and the values of s are read from the accumulator memories and output to the stream  917 . For each of the N s  values of s, one read instruction and one output instruction is required.  FIG. 9  shows the flow of data and instructions for stage 3b. The processing of the read instruction is shown as solid thick arrows, and the processing of an output instruction is shown as dashed thick arrows. The read and output instructions for each s i  can be interleaved to improve the throughput, as described in Table 3 for the case of N s =γ=4. 
     
       
         
           
               
               
             
               
                 TABLE 3 
               
               
                   
               
               
                 Clock Cycle 
                 Instruction 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
            
               
                 1 
                 read instruction for s 1   
               
               
                 2 
                 pause 
               
               
                 3 
                 read instruction for s 2   
               
               
                 4 
                 output instruction for s 1   
               
               
                 5 
                 read instruction for s 3   
               
               
                 6 
                 output instruction for s 2   
               
               
                 7 
                 read instruction for s 4   
               
               
                 8 
                 output instruction for s 3   
               
               
                 9 
                 pause 
               
               
                 10 
                 output instruction for s 4   
               
               
                   
               
            
           
         
       
     
     Region R 3  Encoding with S of Size (N s ×N s )=(γ×γ) 
     In a preferred embodiment of the invention, the matrix S has the size of the number of generalized layers N s =γ. Let us recall that S must be full rank to be able compute its inverse. For this purpose, the CPM organization in S has to follow some constraints, and the values of the CPM S i,j  have also to be chosen carefully. 
     In the preferred embodiment described in this paragraph, the CPM S i,j  are chosen so that the following constraints are satisfied:
         the matrix S is full rank,   the matrix S has a given girth g&gt;4,   the inverse matrix A is composed of low weight circulants.       

     We give several examples with two different structures of such matrices, for the special case of γ=4. Generalizations to other values of γ or other organizations of the CPM in S can be easily derived from these examples. In these examples of the preferred embodiment, the matrix S has size 4×4 blocks, and therefore a minimum of 3 all-zero blocks are necessary to make it full rank.
         1. In the first structure, denoted S3 g , we present solutions for the choice of CPM in S when the number of all-zero blocks is equal to 3, and the girth of the Tanner graph corresponding to S is equal to g. Without loss of generality, we can assume that the CPM in the first block-row and the first block-column of S are equal to the Identity matrix, i.e. S 1,j =S i,1 =α 0 , ∀(i,j). Indeed, with any other choice of the CPM, the first block-row and the first block-column of S can be transformed into α 0  by matrix transformation. Also without loss of generality, we assume that the 3 all-zero blocks are organized in the following manner:       

     
       
         
           
             
               
                 
                   
                     S 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       3 
                       g 
                     
                   
                   = 
                   
                     
                       [ 
                       
                         
                           
                             
                               α 
                               0 
                             
                           
                           
                             
                               α 
                               0 
                             
                           
                           
                             
                               α 
                               0 
                             
                           
                           
                             
                               α 
                               0 
                             
                           
                         
                         
                           
                             
                               α 
                               0 
                             
                           
                           
                             0 
                           
                           
                             
                               S 
                               
                                 2 
                                 , 
                                 3 
                               
                             
                           
                           
                             
                               S 
                               
                                 2 
                                 , 
                                 4 
                               
                             
                           
                         
                         
                           
                             
                               α 
                               0 
                             
                           
                           
                             
                               S 
                               
                                 3 
                                 , 
                                 2 
                               
                             
                           
                           
                             0 
                           
                           
                             
                               S 
                               
                                 3 
                                 , 
                                 4 
                               
                             
                           
                         
                         
                           
                             
                               α 
                               0 
                             
                           
                           
                             
                               S 
                               
                                 4 
                                 , 
                                 2 
                               
                             
                           
                           
                             
                               S 
                               
                                 4 
                                 , 
                                 3 
                               
                             
                           
                           
                             0 
                           
                         
                       
                       ] 
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   39 
                   ) 
                 
               
             
           
         
       
         
         
           
             Any other location of the 3 all-zero blocks can be obtained by performing blockrow/column permutations. The six CPMs (S 2,3 , S 2,4 , S 3,2 , S 3,4 , S 4,2 , S 4,3 ) are chosen such that S3 g  has girth g, is full rank, and its inverse A has the lowest possible sum of its maximum column weight, i.e. such that Σ j=1   4  w max,j  is minimum. 
             2. In the second structure, denoted S4 g , we present solutions for the choice of CPM in S when the number of all-zero blocks in S is equal to 4, and the girth of the Tanner graph corresponding to S is equal to g. The reason in considering 4 all-zero blocks instead of 3 as in the previous structure is that the weights of the circulants in the inverse A are generally smaller. Generalizations to matrices S with more than 4 zeros are also allowed, as long as S is full rank. Like in the previous structure, we can assume that the CPM in the first block-row and the first block-column of S are equal to the Identity matrix, and that the all-zero blocks are organized in the following manner: 
           
         
       
    
     
       
         
           
             
               
                 
                   
                     S 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       4 
                       g 
                     
                   
                   = 
                   
                     [ 
                     
                       
                         
                           0 
                         
                         
                           
                             α 
                             0 
                           
                         
                         
                           
                             α 
                             0 
                           
                         
                         
                           
                             α 
                             0 
                           
                         
                       
                       
                         
                           
                             α 
                             0 
                           
                         
                         
                           0 
                         
                         
                           
                             S 
                             
                               2 
                               , 
                               3 
                             
                           
                         
                         
                           
                             S 
                             
                               2 
                               , 
                               4 
                             
                           
                         
                       
                       
                         
                           
                             α 
                             0 
                           
                         
                         
                           
                             S 
                             
                               3 
                               , 
                               2 
                             
                           
                         
                         
                           0 
                         
                         
                           
                             S 
                             
                               3 
                               , 
                               4 
                             
                           
                         
                       
                       
                         
                           
                             α 
                             0 
                           
                         
                         
                           
                             S 
                             
                               4 
                               , 
                               2 
                             
                           
                         
                         
                           
                             S 
                             
                               4 
                               , 
                               3 
                             
                           
                         
                         
                           0 
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   40 
                   ) 
                 
               
             
           
         
       
     
     The six CPMs (S 2,3 , S 2,4 , S 3,2 , S 3,4 , S 4,2 , S 4,3 ) are chosen such that S4 g  has girth g, is full rank, and its inverse A has the lowest possible sum of its maximum column weight, i.e. such that Σ j=1   4  w max,j  is minimum. 
     Six examples of the preferred embodiment following structures S3 g  and S4 g  are given in equations (41) to (46), for different values of the target girth g E {6, 8, 10}, and a circulant size L=32. In each example, we report the CPMs chosen in matrix S, and the matrix of circulant weights W of its inverse. Generalization to other circulant sizes L or other girths g are obtained using the same constrained design as described in this paragraph. Note the given examples are not unique, and that there exist other CPM choices that lead to the same value of Σ j=1   4  w max,j . 
     As one can see, the weights of the circulants in W are quite low, especially for girth g=6 or g=8. 
     
       
         
           
             
               
                 
                   
                     S 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       3 
                       6 
                     
                   
                   = 
                   
                     
                       
                         [ 
                         
                           
                             
                               0 
                             
                             
                               
                                 α 
                                 0 
                               
                             
                             
                               
                                 α 
                                 0 
                               
                             
                             
                               
                                 α 
                                 0 
                               
                             
                           
                           
                             
                               
                                 α 
                                 0 
                               
                             
                             
                               0 
                             
                             
                               
                                 α 
                                 1 
                               
                             
                             
                               
                                 α 
                                 16 
                               
                             
                           
                           
                             
                               
                                 α 
                                 0 
                               
                             
                             
                               
                                 α 
                                 16 
                               
                             
                             
                               0 
                             
                             
                               
                                 α 
                                 15 
                               
                             
                           
                           
                             
                               
                                 α 
                                 0 
                               
                             
                             
                               
                                 α 
                                 1 
                               
                             
                             
                               
                                 α 
                                 17 
                               
                             
                             
                               0 
                             
                           
                         
                         ] 
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       W 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         3 
                         6 
                       
                     
                     = 
                     
                       [ 
                       
                         
                           
                             0 
                           
                           
                             3 
                           
                           
                             3 
                           
                           
                             3 
                           
                         
                         
                           
                             3 
                           
                           
                             3 
                           
                           
                             2 
                           
                           
                             2 
                           
                         
                         
                           
                             3 
                           
                           
                             2 
                           
                           
                             3 
                           
                           
                             2 
                           
                         
                         
                           
                             3 
                           
                           
                             2 
                           
                           
                             2 
                           
                           
                             3 
                           
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   41 
                   ) 
                 
               
             
             
               
                 
                   
                     S 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       3 
                       8 
                     
                   
                   = 
                   
                     
                       
                         [ 
                         
                           
                             
                               
                                 α 
                                 0 
                               
                             
                             
                               
                                 α 
                                 0 
                               
                             
                             
                               
                                 α 
                                 0 
                               
                             
                             
                               
                                 α 
                                 0 
                               
                             
                           
                           
                             
                               
                                 α 
                                 0 
                               
                             
                             
                               0 
                             
                             
                               
                                 α 
                                 1 
                               
                             
                             
                               
                                 α 
                                 2 
                               
                             
                           
                           
                             
                               
                                 α 
                                 0 
                               
                             
                             
                               
                                 α 
                                 25 
                               
                             
                             
                               0 
                             
                             
                               
                                 α 
                                 28 
                               
                             
                           
                           
                             
                               
                                 α 
                                 0 
                               
                             
                             
                               
                                 α 
                                 30 
                               
                             
                             
                               
                                 α 
                                 4 
                               
                             
                             
                               0 
                             
                           
                         
                         ] 
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       W 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         3 
                         8 
                       
                     
                     = 
                     
                       [ 
                       
                         
                           
                             2 
                           
                           
                             3 
                           
                           
                             3 
                           
                           
                             3 
                           
                         
                         
                           
                             3 
                           
                           
                             3 
                           
                           
                             4 
                           
                           
                             4 
                           
                         
                         
                           
                             3 
                           
                           
                             4 
                           
                           
                             3 
                           
                           
                             4 
                           
                         
                         
                           
                             3 
                           
                           
                             4 
                           
                           
                             4 
                           
                           
                             3 
                           
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   42 
                   ) 
                 
               
             
             
               
                 
                   
                     S 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       3 
                       10 
                     
                   
                   = 
                   
                     
                       
                         [ 
                         
                           
                             
                               
                                 α 
                                 0 
                               
                             
                             
                               
                                 α 
                                 0 
                               
                             
                             
                               
                                 α 
                                 0 
                               
                             
                             
                               
                                 α 
                                 0 
                               
                             
                           
                           
                             
                               
                                 α 
                                 0 
                               
                             
                             
                               0 
                             
                             
                               
                                 α 
                                 1 
                               
                             
                             
                               
                                 α 
                                 3 
                               
                             
                           
                           
                             
                               
                                 α 
                                 0 
                               
                             
                             
                               
                                 α 
                                 9 
                               
                             
                             
                               0 
                             
                             
                               
                                 α 
                                 17 
                               
                             
                           
                           
                             
                               
                                 α 
                                 0 
                               
                             
                             
                               
                                 α 
                                 11 
                               
                             
                             
                               
                                 α 
                                 25 
                               
                             
                             
                               0 
                             
                           
                         
                         ] 
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       W 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         3 
                         10 
                       
                     
                     = 
                     
                       [ 
                       
                         
                           
                             12 
                           
                           
                             13 
                           
                           
                             5 
                           
                           
                             13 
                           
                         
                         
                           
                             13 
                           
                           
                             13 
                           
                           
                             14 
                           
                           
                             10 
                           
                         
                         
                           
                             5 
                           
                           
                             12 
                           
                           
                             15 
                           
                           
                             12 
                           
                         
                         
                           
                             13 
                           
                           
                             10 
                           
                           
                             14 
                           
                           
                             13 
                           
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   43 
                   ) 
                 
               
             
             
               
                 
                   
                     S 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       4 
                       6 
                     
                   
                   = 
                   
                     
                       
                         [ 
                         
                           
                             
                               0 
                             
                             
                               
                                 α 
                                 0 
                               
                             
                             
                               
                                 α 
                                 0 
                               
                             
                             
                               
                                 α 
                                 0 
                               
                             
                           
                           
                             
                               
                                 α 
                                 0 
                               
                             
                             
                               0 
                             
                             
                               
                                 α 
                                 0 
                               
                             
                             
                               
                                 α 
                                 16 
                               
                             
                           
                           
                             
                               
                                 α 
                                 0 
                               
                             
                             
                               
                                 α 
                                 16 
                               
                             
                             
                               0 
                             
                             
                               
                                 α 
                                 0 
                               
                             
                           
                           
                             
                               
                                 α 
                                 0 
                               
                             
                             
                               
                                 α 
                                 0 
                               
                             
                             
                               
                                 α 
                                 16 
                               
                             
                             
                               0 
                             
                           
                         
                         ] 
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       W 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         4 
                         6 
                       
                     
                     = 
                     
                       [ 
                       
                         
                           
                             2 
                           
                           
                             1 
                           
                           
                             1 
                           
                           
                             1 
                           
                         
                         
                           
                             1 
                           
                           
                             2 
                           
                           
                             1 
                           
                           
                             1 
                           
                         
                         
                           
                             1 
                           
                           
                             1 
                           
                           
                             2 
                           
                           
                             1 
                           
                         
                         
                           
                             1 
                           
                           
                             1 
                           
                           
                             1 
                           
                           
                             2 
                           
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   44 
                   ) 
                 
               
             
             
               
                 
                   
                     S 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       4 
                       8 
                     
                   
                   = 
                   
                     
                       
                         [ 
                         
                           
                             
                               0 
                             
                             
                               
                                 α 
                                 0 
                               
                             
                             
                               
                                 α 
                                 0 
                               
                             
                             
                               
                                 α 
                                 0 
                               
                             
                           
                           
                             
                               
                                 α 
                                 0 
                               
                             
                             
                               0 
                             
                             
                               
                                 α 
                                 0 
                               
                             
                             
                               
                                 α 
                                 1 
                               
                             
                           
                           
                             
                               
                                 α 
                                 0 
                               
                             
                             
                               
                                 α 
                                 14 
                               
                             
                             
                               0 
                             
                             
                               
                                 α 
                                 16 
                               
                             
                           
                           
                             
                               
                                 α 
                                 0 
                               
                             
                             
                               
                                 α 
                                 15 
                               
                             
                             
                               
                                 α 
                                 30 
                               
                             
                             
                               0 
                             
                           
                         
                         ] 
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       W 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         4 
                         8 
                       
                     
                     = 
                     
                       [ 
                       
                         
                           
                             2 
                           
                           
                             3 
                           
                           
                             3 
                           
                           
                             3 
                           
                         
                         
                           
                             3 
                           
                           
                             2 
                           
                           
                             3 
                           
                           
                             3 
                           
                         
                         
                           
                             3 
                           
                           
                             3 
                           
                           
                             2 
                           
                           
                             3 
                           
                         
                         
                           
                             3 
                           
                           
                             3 
                           
                           
                             3 
                           
                           
                             2 
                           
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   45 
                   ) 
                 
               
             
             
               
                 
                   
                     S 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       4 
                       10 
                     
                   
                   = 
                   
                     
                       
                         [ 
                         
                           
                             
                               0 
                             
                             
                               
                                 α 
                                 0 
                               
                             
                             
                               
                                 α 
                                 0 
                               
                             
                             
                               
                                 α 
                                 0 
                               
                             
                           
                           
                             
                               
                                 α 
                                 0 
                               
                             
                             
                               0 
                             
                             
                               
                                 α 
                                 1 
                               
                             
                             
                               
                                 α 
                                 3 
                               
                             
                           
                           
                             
                               
                                 α 
                                 0 
                               
                             
                             
                               
                                 α 
                                 25 
                               
                             
                             
                               0 
                             
                             
                               
                                 α 
                                 21 
                               
                             
                           
                           
                             
                               
                                 α 
                                 0 
                               
                             
                             
                               
                                 α 
                                 27 
                               
                             
                             
                               
                                 α 
                                 13 
                               
                             
                             
                               0 
                             
                           
                         
                         ] 
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       W 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         4 
                         10 
                       
                     
                     = 
                     
                       [ 
                       
                         
                           
                             4 
                           
                           
                             9 
                           
                           
                             5 
                           
                           
                             9 
                           
                         
                         
                           
                             5 
                           
                           
                             4 
                           
                           
                             5 
                           
                           
                             5 
                           
                         
                         
                           
                             5 
                           
                           
                             9 
                           
                           
                             4 
                           
                           
                             9 
                           
                         
                         
                           
                             5 
                           
                           
                             5 
                           
                           
                             5 
                           
                           
                             4 
                           
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   46 
                   ) 
                 
               
             
           
         
       
     
     Region R 3  Encoding with S of Size (N s ×N s )=(lγ×lγ) 
     We present in this paragraph a preferred embodiment of the invention, when the size of the matrix S is l times the number of GLs, with l&gt;1. For ease of presentation, we present only the case of γ=4 and l=2. One skilled in the art can easily extend this example to larger values of 1, and other values of γ. 
     Although applicable to any matrix S of size (l γ×l γ), the implementation of region R 3  described in paragraphs 0047 and 0048 can become cumbersome when the matrix S is large. This is due to the fact that the inverse of S when l≥2 is generally not sparse anymore, which leads to a large increase in computational complexity or an important decrease of the encoding throughput. 
     Instead, we propose in this invention to impose a specific structure on the matrix S, which allows to make a recursive use of the encoder presented in paragraph 0049 for γ×γ matrices. The proposed structure is presented in the following equation for γ=4: 
     
       
         
           
             
               
                 
                   S 
                   = 
                   
                     [ 
                     
                       
                         
                           
                             
                               
                                 
                                   S 
                                   
                                     1 
                                     , 
                                     1 
                                   
                                 
                               
                               
                                 0 
                               
                               
                                 0 
                               
                               
                                 0 
                               
                             
                             
                               
                                 0 
                               
                               
                                 
                                   S 
                                   
                                     2 
                                     , 
                                     2 
                                   
                                 
                               
                               
                                 0 
                               
                               
                                 0 
                               
                             
                             
                               
                                 0 
                               
                               
                                 0 
                               
                               
                                 
                                   S 
                                   
                                     3 
                                     , 
                                     3 
                                   
                                 
                               
                               
                                 0 
                               
                             
                             
                               
                                 0 
                               
                               
                                 0 
                               
                               
                                 0 
                               
                               
                                 
                                   S 
                                   
                                     4 
                                     , 
                                     4 
                                   
                                 
                               
                             
                           
                         
                         
                           
                             S 
                             ′ 
                           
                         
                       
                       
                         
                           
                             S 
                             ″ 
                           
                         
                         
                           
                             
                               
                                 0 
                               
                               
                                 0 
                               
                               
                                 0 
                               
                               
                                 0 
                               
                             
                             
                               
                                 0 
                               
                               
                                 0 
                               
                               
                                 0 
                               
                               
                                 0 
                               
                             
                             
                               
                                 0 
                               
                               
                                 0 
                               
                               
                                 0 
                               
                               
                                 0 
                               
                             
                             
                               
                                 0 
                               
                               
                                 0 
                               
                               
                                 0 
                               
                               
                                 0 
                               
                             
                           
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   47 
                   ) 
                 
               
             
           
         
       
     
     where S′ and S″ are γ×γ matrices following the constraints of paragraph 0049, i.e. S′=S3 g , or S′=S4 g , and S″=S3 g , or S″=S4 g . This means in particular that S′, respectively S″, have both low weight inverses, denoted A′, respectively A″. 
     One can expand the inverse into their sparse representation, following Equation (36), to obtain matrices E′, respectively E″. Encoding the vector of redundancy bits s using the structure (47) requires therefore two recursive steps of the method that was presented in paragraph 0047:
         1. Use Algorithm 3 with inputs       

             c       (     γ   +   1     )     :     2   ⁢   γ         (       K   b     +     N   t       )           
and matrix E″, to obtain the vector of redundancy bits [s 1 ; . . . ; s γ ],
         2. Accumulate the temporary parity check bits       

             c     1   :   γ       (       K   b     +     N   t       )           
with the newly computed redundancy bits:
 
     
       
         
           
             
               
                 
                   
                     c 
                     
                       1 
                       : 
                       γ 
                     
                     
                       ( 
                       
                         
                           K 
                           b 
                         
                         + 
                         
                           N 
                           t 
                         
                         + 
                         γ 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       c 
                       
                         1 
                         : 
                         γ 
                       
                       
                         ( 
                         
                           
                             K 
                             b 
                           
                           + 
                           
                             N 
                             t 
                           
                         
                         ) 
                       
                     
                     + 
                     
                       
                         [ 
                         
                           
                             
                               
                                 S 
                                 
                                   1 
                                   , 
                                   1 
                                 
                               
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                           
                           
                             
                               0 
                             
                             
                               
                                 S 
                                 
                                   2 
                                   , 
                                   2 
                                 
                               
                             
                             
                               0 
                             
                             
                               0 
                             
                           
                           
                             
                               0 
                             
                             
                               0 
                             
                             
                               
                                 S 
                                 
                                   3 
                                   , 
                                   3 
                                 
                               
                             
                             
                               0 
                             
                           
                           
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               
                                 S 
                                 
                                   4 
                                   , 
                                   4 
                                 
                               
                             
                           
                         
                         ] 
                       
                       ⁡ 
                       
                         [ 
                         
                           
                             
                               
                                 s 
                                 1 
                               
                             
                           
                           
                             
                               ⋮ 
                             
                           
                           
                             
                               ⋮ 
                             
                           
                           
                             
                               
                                 s 
                                 γ 
                               
                             
                           
                         
                         ] 
                       
                     
                   
                 
               
               
                 
                   ( 
                   48 
                   ) 
                 
               
             
           
         
       
         
         
           
             3. Use Algorithm 3 with inputs 
           
         
       
    
             c     1   :   γ       (       K   b     +     N   t     +   γ     )           
and matrix E′, to obtain the vector of redundancy bits [s γ+1 ; . . . ; s 2γ ],
 
     At the end of these three steps, we finally obtain the vector of redundancy bits [s 1 ; . . . ; s γ ; s γ+1  . . . ; s 2γ ] to complete the codeword. The hardware realization of this preferred embodiment is based on the use of the hardware presented in paragraph 0048. 
     Encoding with Two Regions Only: R 1  and R 3    
     There are situations when the dimensions of the PCM are not sufficiently large to allow an organization in three regions as described in Equation (11). Indeed, when N s =M b , it results from equations (12)-(14) that N t =0 and the region R 2  does not exist. The structure of the PCM becomes: 
                   H   =     [       U       M   u     ×     N   u         |           S       N   s     ×     N   s                   0       (       M   b     -     N   s       )     ×     N   s                 ]             (   49   )               
and the codeword has only two parts, i.e. x=[u; s].
 
     In such case, the invention presented in this disclosure consists of only two sequential steps:
         Step 1: The first step computes the temporary parity checks vector c (K     b     )  using region R 1 , i.e. c (K     b     ) =U u. The step corresponding to region R 2  is skipped since c (K     b     +N     t     ) =c (K     b     ) ,   Step 2: The second step computes the vector of redundancy bits s using R 3 , with the values of c (K     b     )  as input.       

     The methods and hardware implementations related to regions R 1  and R 3  remain unchanged, and follow the descriptions of paragraphs 0043, 0044, 0047 and 0048. In the case of N s =M b =γ, the region R 3  is implemented as in paragraph 0049, and in the case of N s =M b =lγ, the region R 3  is implemented as in paragraph 0050.