Abstract:
A method and system for constructing a generator matrix is disclosed. The method includes: receiving a parity check matrix H, wherein the parity check matrix H includes multiple circulant sub-matrices; rearranging the parity check matrix H by column and row permutations to obtain a rearranged parity check matrix H′; and constructing the generator matrix G based on the rearranged parity check matrix H′.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    Noon The present application claims the benefit under 35 U.S.C. §119(e) of U.S. Provisional Application Ser. No. 61/805,270, filed Mar. 26, 2013. Said U.S. Provisional Application Ser. No. 61/805,270 is hereby incorporated by reference in its entirety. 
     
    
     TECHNICAL FIELD 
       [0002]    The present invention relates to the field of error correction and particularly to a quasi-cyclic low-density parity-check encoder. 
       BACKGROUND 
       [0003]    In information theory, a low-density parity-check (LDPC) code is a linear error correcting code, which is commonly used as a method of transmitting a message over a noisy transmission channel. 
       SUMMARY 
       [0004]    Accordingly, an embodiment of the present disclosure is directed to a method for constructing a generator matrix using a computer processor. The method includes: receiving a parity check matrix H, wherein the parity check matrix H includes multiple circulant sub-matrices; rearranging the parity check matrix H by column and row permutations to obtain a rearranged parity check matrix H′; and constructing the generator matrix G based on the rearranged parity check matrix H′. 
         [0005]    A further embodiment of the present disclosure is directed to a system for constructing a generator matrix. The system includes a generator matrix construction module configured for: receiving a parity check matrix H, wherein the parity check matrix H includes multiple circulant sub-matrices; rearranging the parity check matrix H by column and row permutations to obtain a rearranged parity check matrix H′; and constructing the generator matrix G based on the rearranged parity check matrix H′. The system further includes a generator matrix memory in communication with the generator matrix construction module. The generator matrix memory is configured for storing the generator matrix G constructed. 
         [0006]    An additional embodiment of the present disclosure is directed to a computer-readable device having computer-executable instructions for performing a method for constructing a generator matrix. The method includes: receiving a parity check matrix H having a plurality of q×q circulant sub-matrices; rearranging the parity check matrix H by column and row permutations to obtain a rearranged parity check matrix H′; and constructing the generator matrix G based on H′. 
         [0007]    It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and are not necessarily restrictive of the invention as claimed. The accompanying drawings, which are incorporated in and constitute a part of the specification, illustrate embodiments of the invention and together with the general description, serve to explain the principles of the invention. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0008]    The numerous advantages of the present invention may be better understood by those skilled in the art by reference to the accompanying figures in which: 
           [0009]      FIG. 1  is a block diagram illustrating a quasi-cyclic low-density parity-check encoder (QC LDPC) encoder; 
           [0010]      FIG. 2  is a block diagram illustrating a parity update circuit for completing q updates in q cycles; 
           [0011]      FIG. 3  is a flow diagram illustrating a method for generating a partially sparse generator matrix in accordance with an embodiment of the present disclosure; 
           [0012]      FIG. 4  is an illustration depicting a rearranged parity check matrix and its corresponding generator matrix, wherein q=128, M=19, N=155, and t=11. 
           [0013]      FIG. 5  is a circuitry diagram illustrating an exemplary sparse multiplication circuit that supports up to 16 sparse circulant multiplications in 16 cycles with circulant size 128 and throughtput requirement of 8 bits per clock cycle; 
           [0014]      FIG. 6A  is a first portion of a circuitry diagram illustrating an exemplary 128-bit barrel shifter (rotator) for the sparse multiplication circuit of  FIG. 5 ; 
           [0015]      FIG. 6B  is a second portion the circuitry diagram illustrating the exemplary 128-bit barrel shifter (rotator) for the sparse multiplication circuit of  FIG. 5 ; 
           [0016]      FIG. 6C  is a third portion the circuitry diagram illustrating the exemplary 128-bit barrel shifter (rotator) for the sparse multiplication circuit of  FIG. 5 ; 
           [0017]      FIG. 6D  is a fourth portion the circuitry diagram illustrating the exemplary 128-bit barrel shifter (rotator) for the sparse multiplication circuit of  FIG. 5 ; 
           [0018]      FIG. 6E  is a fifth portion the circuitry diagram illustrating the exemplary 128-bit barrel shifter (rotator) for the sparse multiplication circuit of  FIG. 5 ; 
           [0019]      FIG. 6F  is a sixth portion the circuitry diagram illustrating the exemplary 128-bit barrel shifter (rotator) for the sparse multiplication circuit of  FIG. 5 ; 
           [0020]      FIG. 6  is an illustration of the relative positions of  FIGS. 6A through 6F  forming the combined circuitry diagram; and 
           [0021]      FIG. 7  is a block diagram illustrating a system for generating a partially sparse generator matrix in accordance with an embodiment of the present disclosure. 
       
    
    
     DETAILED DESCRIPTION 
       [0022]    Reference will now be made in detail to the presently preferred embodiments of the invention, examples of which are illustrated in the accompanying drawings. 
         [0023]    Low-density parity-check (LDPC) codes can be constructed from circulant permutation matrices, and such LDPC codes are commonly referred to as quasi-cyclic (QC) LDPC codes. Encoding of QC LDPC codes is described in: Efficient Encoding of Quasi-Cyclic Low-Density Parity-Check Codes, Zongwang Li et al., IEEE Transactions on Communications, Vol. 54, No. 1 (January 2006), which is herein incorporated by reference in its entirety. 
         [0024]    QC LDPC codes are commonly described by their sparse parity check matrix that defines the null space of the code. A parity check matrix is generally given in a circulant block form: 
         [0000]    
       
         
           
             H 
             = 
             
               [ 
               
                 
                   
                     
                       H 
                       
                         1 
                         , 
                         1 
                       
                     
                   
                   
                     
                       H 
                       
                         1 
                         , 
                         2 
                       
                     
                   
                   
                     … 
                   
                   
                     
                       H 
                       
                         1 
                         , 
                         N 
                       
                     
                   
                 
                 
                   
                     
                       H 
                       
                         2 
                         , 
                         1 
                       
                     
                   
                   
                     
                       H 
                       
                         2 
                         , 
                         2 
                       
                     
                   
                   
                     … 
                   
                   
                     
                       H 
                       
                         2 
                         , 
                         N 
                       
                     
                   
                 
                 
                   
                     ⋮ 
                   
                   
                     ⋮ 
                   
                   
                     ⋱ 
                   
                   
                     ⋮ 
                   
                 
                 
                   
                     
                       H 
                       
                         M 
                         , 
                         1 
                       
                     
                   
                   
                     
                       H 
                       
                         M 
                         , 
                         2 
                       
                     
                   
                   
                     … 
                   
                   
                     
                       H 
                       
                         M 
                         , 
                         N 
                       
                     
                   
                 
               
               ] 
             
           
         
       
     
         [0000]    Wherein each sub-matrix H i,j  is a q×q circulant matrix and is either a zero matrix or a circulant permutation matrix, i.e. with a column and row weight of one. This constraint reduces the encoder/decoder complexity and simplifies the code search process. 
         [0025]    In coding theory, a generator matrix is a basis for a linear code, generating all its possible codewords. For a given QC LDPC matrix, there exists a generator matrix G in circulant block form: 
         [0000]    
       
         
           
             G 
             = 
             
               [ 
               
                 
                   
                     I 
                   
                   
                     0 
                   
                   
                     … 
                   
                   
                     0 
                   
                   
                     
                       G 
                       
                         1 
                         , 
                         1 
                       
                     
                   
                   
                     
                       G 
                       
                         1 
                         , 
                         2 
                       
                     
                   
                   
                     … 
                   
                   
                     
                       G 
                       
                         1 
                         , 
                         M 
                       
                     
                   
                 
                 
                   
                     0 
                   
                   
                     I 
                   
                   
                     … 
                   
                   
                     0 
                   
                   
                     
                       G 
                       
                         2 
                         , 
                         1 
                       
                     
                   
                   
                     
                       G 
                       
                         2 
                         , 
                         2 
                       
                     
                   
                   
                     … 
                   
                   
                     
                       G 
                       
                         2 
                         , 
                         M 
                       
                     
                   
                 
                 
                   
                     ⋮ 
                   
                   
                     ⋮ 
                   
                   
                     ⋱ 
                   
                   
                     ⋮ 
                   
                   
                     ⋮ 
                   
                   
                     ⋮ 
                   
                   
                     ⋱ 
                   
                   
                     ⋮ 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     … 
                   
                   
                     I 
                   
                   
                     
                       G 
                       
                         
                           N 
                           - 
                           M 
                         
                         , 
                         1 
                       
                     
                   
                   
                     
                       G 
                       
                         
                           N 
                           - 
                           M 
                         
                         , 
                         2 
                       
                     
                   
                   
                     … 
                   
                   
                     
                       G 
                       
                         
                           N 
                           - 
                           M 
                         
                         , 
                         M 
                       
                     
                   
                 
               
               ] 
             
           
         
       
     
         [0000]    Wherein each sub-matrix G i,j  is of the same size as H i,j  (i.e., q×q) and is also in a circulant form. 
         [0026]      FIG. 1  is a block diagram illustrating a QC LDPC encoder  100 . M parity generator blocks  102  are utilized for the encoding process. Typically, the i-th parity generator block (Parity Gen i) takes q user bits at its input (where q is the circulant size described above) and computes parity updates from those q user bits for the i-th block. To perform such updates, the i-th Parity Gen block needs to know the sub-matrix G j,i , where j corresponds to the j-th block of q user bits currently processed. Therefore, in this implementation, each Parity Gen block  102  requires q flip-flops to store one row of a sub-matrix of G (loaded from the Generator matrix memory  104 ), q flip-flops to store q parity bits and logic circuit that updates the parity. 
         [0027]      FIG. 2  is a block diagram illustrating a parity update circuit. It is noted that the parity update circuit complexity depends on the number of cycles available. For instance, if the required throughput allows the circuit to complete each update in q cycles, then q 2-input AND gates and 1 q-input XOR gate can be utilized as illustrated in  FIG. 2 , which has a relatively small complexity. However, if the required throughput dictates the computation to be completed in q/n cycles, the complexity increases n times. 
         [0028]    Now, it is noted that while the sub-matrices H i,j  are low density (sparse), sub-matrices G i,j  are usually dense. However, if the generator matrix G can be arranged so that some of the G i,j  sub-matrices are sparse circulants (i.e. zero circulants or circulants that contain just one ‘1’ in each column/row), the efficiency of the parity generation process can be improved. 
         [0029]    In accordance with an embodiment of the present disclosure, a method and system to construct partially sparse generator matrix for a quasi-cyclic low-density parity-check encoder is disclosed. 
         [0030]    Referring to  FIG. 3 , a flow diagram illustrating a method  300  for generating a partially spare generator matrix is shown. Upon receiving a parity check matrix H in step  302 , step  304  rearranges the parity check matrix H by column and row permutations into the following form: 
         [0000]    
       
         
           
             
               H 
               ′ 
             
             = 
             
               [ 
               
                 
                   
                     
                       H 
                       
                         u 
                          
                         
                             
                         
                          
                         1 
                       
                     
                   
                   
                     
                       I 
                       t 
                     
                   
                   
                     
                       0 
                       
                         t 
                         × 
                         
                           ( 
                           
                             M 
                             - 
                             t 
                           
                           ) 
                         
                       
                     
                   
                 
                 
                   
                     
                       H 
                       
                         u 
                          
                         
                             
                         
                          
                         2 
                       
                     
                   
                   
                     
                       H 
                       
                         p 
                          
                         
                             
                         
                          
                         1 
                       
                     
                   
                   
                     
                       H 
                       
                         p 
                          
                         
                             
                         
                          
                         2 
                       
                     
                   
                 
               
               ] 
             
           
         
       
     
       Wherein 
       [0031]    
       
         
           
             
               
                 rank 
                  
                 
                   ( 
                   
                     H 
                     ′ 
                   
                   ) 
                 
               
               = 
               
                 rank 
                  
                 
                   [ 
                   
                     
                       
                         
                           I 
                           t 
                         
                       
                       
                         
                           0 
                           
                             t 
                             × 
                             
                               ( 
                               
                                 M 
                                 - 
                                 t 
                               
                               ) 
                             
                           
                         
                       
                     
                     
                       
                         
                           H 
                           
                             p 
                              
                             
                                 
                             
                              
                             1 
                           
                         
                       
                       
                         
                           H 
                           
                             p 
                              
                             
                                 
                             
                              
                             2 
                           
                         
                       
                     
                   
                   ] 
                 
               
             
             , 
             
               
 
             
              
             
               and 
                
               
                 
 
               
               [ 
               
                 
                   
                     
                       I 
                       t 
                     
                   
                   
                     
                       0 
                       
                         t 
                         × 
                         
                           ( 
                           
                             M 
                             - 
                             t 
                           
                           ) 
                         
                       
                     
                   
                 
                 
                   
                     
                       H 
                       
                         p 
                          
                         
                             
                         
                          
                         1 
                       
                     
                   
                   
                     
                       H 
                       
                         p 
                          
                         
                             
                         
                          
                         2 
                       
                     
                   
                 
               
               ] 
             
           
         
       
     
         [0000]    is the part of the parity check matrix that corresponds to parity bits. It is noted that H′ is by definition also a QC LDPC matrix consists of q×q circulants. 
         [0032]    More specifically, as illustrated in  FIG. 4 , for a given parity check matrix H, the H matrix can be rearranged by column and row permutations into the form depicted as H′ in  FIG. 4 . 
         [0033]    In accordance with an embodiment of the present disclosure, the larger the size t of the identity matrix in H′ , the larger the sparse part of the generator matrix G. In one embodiment, step  304  rearranges the parity check matrix H by column and row permutations to maximize the size t of the identity matrix through an exhaustive search. 
         [0034]    Once the rearranged matrix H′ is obtained, step  306  then constructs the generator matrix G based on this rearranged matrix H′. More specifically, the generator matrix G is constructed as: 
         [0000]        G=[I   N−M    H   u1   T    {tilde over (G)}   T ] 
         [0000]    Wherein H u1   T  is the transpose of H u1  and is in block circulant form, and {tilde over (G)} T  is the dense part of the generator matrix constructed in systematic-circulant form using a similar process as described in sections III and V of: Efficient Encoding of Quasi-Cyclic Low-Density Parity-Check Codes, Zongwang Li et al., IEEE Transactions on Communications, Vol. 54, No. 1 (January 2006). The generator matrix G constructed in this manner is depicted in  FIG. 4 , which also illustrates the relative size comparison between matrices H′ and G. 
         [0035]    It is noted that every row of G is a codeword, and The rows in G span the null space of H. For arbitrary input row vector u containing user data, codeword in the code defined by H is of the form c=u·G=[u p1 p2], where parity bits p1 and p2 are computed as: p1=u×H u1   T  and p2=u×{tilde over (G)} T . 
         [0036]    In one embodiment, the computation of {tilde over (G)} T  is carried out in two steps. First, rows i=1, q+1, 2q+1 . . . of the G matrix are computed. Since the i-th row in G is orthogonal to H and also to [H u2 , H p1 , H p2 ], the following equation is valid: 
         [0000]        h   u2   (i)   +H   p1   ·h   u1   (i)   +H   p2   ·{tilde over (g)}   (i) =0 
         [0000]    Wherein superscript (i) denotes the i-th column of the corresponding matrix (e.g. h u2   (i)  is the i-th column of H u2 ). Since all variables except for {tilde over (g)} (i)  is known, the value of {tilde over (g)} (i)  can be computed based on this equation accordingly. In cases when H p2  is non-invertible, a generalized inverse of H p2  (which may not be unique) can be utilized. Subsequently, once rows i=1, q+1, 2q+1 . . . of the G matrix are computed, the remaining rows can be obtained as QC shifts of the rows already computed. 
         [0037]    It is contemplated that the generator matrix G constructed in this manner is partially sparse, which improves the efficiency of the parity generation process. For instance, a subset of circulant multiplications corresponding to the sparse circulants can be efficiently implemented with barrel shifters, therefore reducing the number of gates per number of parities computed in a single clock cycle. In addition, memory requirements for storing sparse circulants (zero circulants or circulants with column/row weight of one) are much smaller than memory requirements for storing dense circulants. 
         [0038]    More specifically, for sparse circulants, a q-bit barrel shifter can provide q parity updates in one clock cycle. For instance, if it is required to update q parities in 16 cycles, in the traditional encoder design, q/16 parity update circuits from  FIG. 2  are needed for each circulant G i,j . However, in accordance with an embodiment of the present disclosure, if the sub-matrix G i,j  being processed is sparse, one q-bit barrel shifter can provide support for up to 16×q parity updates within 16 cycles, significantly reducing the total gate count as well as the memory size. 
         [0039]    For illustrative purposes, suppose q=128 and the throughput requires 8 bits per clock cycle, which means a total of 16 cycles can be used to update all parities from q input bits.  FIG. 5  shows an exemplary sparse multiplication circuit capable of satisfying this throughput requirement for sparse circulant multiplication. Since a 2 n  bit barrel shifter can be implemented with n×2 n 2×1 MUX, an exemplary 128-bit barrel shifter for sparse circulant multiplication can be implemented using 7×128 2×1 MUX, or the equivalent of 896 XOR and 1792 AND gates. This exemplary barrel shifter (rotator) is depicted in  FIG. 6  for illustrative purposes. In addition to the barrel shifter, the sparse circulant multiplier also needs 128 2-input XOR gates for parity updates and 128 16×1 MUX, or the equivalent of 1920 XOR and 3840 AND gates for parity selection. All together, the exemplary 128-bit sparse circulant multiplier contains zero (0) flip-flops, 2.875K XOR gates and 5.5K AND gates, and is capable of processing 16×128 parity updates within 16 cycles. 
         [0040]    As shown, for sub-matrices G i,j  that are sparse, utilizing q-bit barrel shifter (rotator) to process circulant multiplications is significantly more efficient than using conventional parity update circuits. For sub-matrices G i,j  that are dense, on the other hand, any conventional parity update circuit can be utilized. Again, as mentioned previously, in certain embodiments it is advantageous to conduct an exhaustive search to maximize the size t of the identity matrix in H′ in order to maximize the sparse part of the generator matrix G, which in turn improves the efficiency of the parity update process. 
         [0041]    Referring to  FIG. 7 , a block diagram illustrating a system  700  for generating a partially spare generator matrix is shown. In one embodiment, a parity check matrix H is provided as input to the generator matrix construction module  702 . The generator matrix construction module  702  includes a computer processor in communication with a computer-readable device having computer-executable instructions for performing the method  300  as described above. The output of the generator matrix construction module  702 , i.e., the generator matrix G, is then stored in a generator matrix memory  704 , which will then be used for the QC LDPC coding process as described above. 
         [0042]    It is to be understood that the present disclosure may be conveniently implemented in forms of a software package. Such a software package may be a computer program product which employs a computer-readable storage medium including stored computer code which is used to program a computer to perform the disclosed function and process of the present invention. The computer-readable medium may include, but is not limited to, any type of conventional floppy disk, optical disk, CD-ROM, magnetic disk, hard disk drive, magneto-optical disk, ROM, RAM, EPROM, EEPROM, magnetic or optical card, or any other suitable media for storing electronic instructions. 
         [0043]    It is understood that the specific order or hierarchy of steps in the foregoing disclosed methods are examples of exemplary approaches. Based upon design preferences, it is understood that the specific order or hierarchy of steps in the method can be rearranged while remaining within the scope of the present invention. The accompanying method claims present elements of the various steps in a sample order, and are not meant to be limited to the specific order or hierarchy presented. 
         [0044]    It is believed that the present invention and many of its attendant advantages will be understood by the foregoing description. It is also believed that it will be apparent that various changes may be made in the form, construction and arrangement of the components thereof without departing from the scope and spirit of the invention or without sacrificing all of its material advantages. The form herein before described being merely an explanatory embodiment thereof, it is the intention of the following claims to encompass and include such changes.