# Patent

## Title
Encoding method and device for low density generator matrix codes

## Abstract

The present invention discloses an encoding method and device for Low Density Generator Matrix Codes (LDGC). Wherein, the method comprises: construct an LDGC mother code set using a plurality of LDGC with code rate R0 and different code lengths, wherein the LDGC mother code set has a uniform base matrix Gbuniform={(gi,jb)uniform}kb×nb; obtain length L of an intermediate variable according to a relationship between length K of an information bit sequence to be encoded in the LDGC mother code set and length L of the intermediate variable; obtain an expanding factor z for processing the base matrix using the length of the intermediate variable and the number of rows in the base matrix; process the base matrix using the expanding factor to obtain a binary generator matrix Gtmp, the front L rows and front L columns of which compose a triangular matrix; modify the binary generator matrix to obtain a modified binary generator matrix; take a matrix Gldgc composed of L rows and the front N+L−K columns of the modified binary generator matrix as a generator matrix of the information bit sequence to encode the information bit sequence.

## Background
FIELD OF THE INVENTION
The present invention relates to communication field, and more particularly, relates to an encoding method and device for Low Density Generator Matrix Codes, LDGC.
BACKGROUND OF THE INVENTION
Erasure channel is an important channel model. For example, when files are transmitted on the Internet, communications are based on data packets, and usually, each data packet is either received by a receiver without any mistake, or not received by the receiver at all. In the Transmission Control Protocol (TCP for short), an error-check and retransmission mechanism is used against network packet loss, i.e., a feedback channel from an input end to an output end is used to control data packets which need to be retransmitted. The receiver generates a retransmission control signal upon detecting a packet loss, until the complete data packet is received correctly; and the receiver also generates a receiving Acknowledgement (ACK) signal upon receiving a data packet. A sender also traces each data packet until it receives a feedback informing signal, otherwise, the sender starts a retransmission.
The data broadcasting service based on streaming mode and file downloading mode is a point-to-multipoint service, in which no feedback is allowed and the conventional error-check and retransmission mechanism cannot be used, and thus Forward Error Correction (FEC for short) needs to be used to ensure reliable transmission. Typical FECs in the application layer comprises RS codes (Reed-Solomon codes), Fountain codes etc. The RS codes are of high complexity in encoding and decoding, and usually are applicable only in the cases where the code length is small. LT codes (Luby Transform codes) and Raptor codes are two kinds of Fountain codes applicable in practice. The LT codes have linear encoding and decoding time, and thus have substantial improvement compared to the RS codes. The Raptor codes have higher decoding efficiency because of the use of pre-coding technique. The Raptor codes are used as the FEC encoding scheme in Multimedia Broadcast/Multicast Service (MBMS for short) and Digital Video Broadcasting (DVB for short) of 3GPP (3rd Generation Partnership Project).
Low Density Generator matrix Codes (LDGC for short) are linear block codes, and the nonzero elements in the generator matrix thereof are usually sparse. Meanwhile, the LDGC are also systematic codes, and the square matrix composed of the front k columns of the generator matrix thereof is generally an upper triangular or lower triangular matrix, the inversion of which can be computed by iteration method. The encoding of the LDGC is to compute an intermediate variable using the corresponding relation between the information bits and the intermediate variable in the systematic codes, and then, to obtain encoded codewords by multiplying the generator matrix by the intermediate variable. The decoding process of the LDGC is to first compute an intermediate variable using the generator matrix, and then, to compute the information bits using the conversion relation between the information bits and the intermediate variable. The LDGC are much lower than the Raptor codes in encoding complexity, can support the encoding of any information block length and any code rate, and are similar to the Raptor codes in performance which can be close to the theoretical optimal performance.
Compared to the structured Low Density Generator Matrix Codes (LDGC), the LT codes do not support the encoding mode of the systematic codes. Thus, the LT codes can not satisfy some practical FEC encoding requirements. The Raptor codes support the systematic codes, however, the Raptor codes need a separate pre-coding process, i.e., a pre-coding matrix is needed, thus, the encoding complexity is high. The LDGC directly use a generator matrix for encoding, without any additional pre-coding matrix. Moreover, since the backward substitution method is used in the encoding of the LDGC to solve the upper triangular (or lower triangular) formulae, the LDGC are much lower than the Raptor codes in encoding complexity. In a word, compared to the LT codes, the advantage of the LDGC lies in that it supports the systematic codes; and compared to the Raptor codes, the advantage of the LDGC lies in that it has a lower encoding complexity.
Comparing the LDGC codes with the Raptor codes of Fountain company, the encoding complexity of the Raptor codes is relatively high, while there is almost no encoding complexity for the LDGC codes because it is very easy to solve trigonometric formula; since the column weight of the LDGC codes is far lower than that of the Raptor codes, the decoding complexity of the Raptor codes is relatively high while that of the LDGC codes is relatively low; and it should be pointed out that since there is specific density distribution, the matrix density in Gaussian elimination process becomes lower and lower so as to ensure a very low complexity of decoding algorithm; since the physical layer generally can guarantee a low BLER (Block Error Rate), the overhead required is usually not more than 25%, at this time, the LDGC codes can further provide a specially effective decoding algorithm to ensure a far lower decoding complexity than that of Raptor codes; the generating process of encoding and decoding matrix is much easier and faster than that of Raptor codes; the storage of the encoding and decoding matrix is far smaller than that of Raptor codes, for example, in the embodiments of the present invention, only a uniform base matrix of 12*40 is needed to be stored; finally, the LDGC codes are relatively flexible, supporting an arbitrary information group length K and an arbitrary encoding rate r.
SUMMARY OF THE INVENTION
The invention provides an encoding method and device for LDGC, to improve flexibility of the code length of LDGC, reduce storage space of the base matrix so as to decrease complexity of code compiling.
The encoding method for LDGC according to the embodiments of the present invention comprises the following steps: step 1, construct an LDGC mother code using a plurality of LDGC with code rate R0 and different code length, wherein the LDGC mother code set has a uniform base matrix Gbuniform={(gi,jb)uniform}kb×nb,




  
    
      R
      0
    
    =
    
      
        k
        b
      
      
        n
        b
      
    
  
  ,




kb is the number of rows in the base matrix, and nb is the number of columns in the base matrix; step 2, obtain length L of an intermediate variable according to a relationship between length K of an information bit sequence to be encoded in the LDGC mother code set and length L of the intermediate variable; step 3, obtain an expanding factor z for processing the base matrix using the length of the intermediate variable and the number of rows in the base matrix; step 4, process the base matrix using the expanding factor to obtain a binary generator matrix Gtmp wherein the front L rows and the front L columns of the binary generator matrix compose a triangular matrix; and step 5, modify the binary generator matrix to obtain a modified binary generator matrix; and step 6, take a matrix Gldgc composed of L rows and the front N+L−K columns of the modified binary generator matrix as a generator matrix of the information bit sequence to encode the information bit sequence.

Wherein, step 4 comprises the following steps: step a, modify the base matrix using the expanding factor to obtain a modified base matrix Gbmodified={gi,jb}kb×nb; and step b, expand the modified base matrix using the expanding factor to obtain the binary generator matrix, wherein the binary generator matrix has a size of (kb×z)×(nb×z).
Wherein, the relationship between the length of the information bit sequence and the length of the intermediate variable is as follows: L=kb·ceil((p×K+q)/kb), wherein both p and q are constants greater than 0. Herein, kb=12, p=1.0235, q=30, ceil denotes a ceiling operation. The expanding factor is obtained using the length of the intermediate variable and the number of rows in the base matrix through following method: z=L/kb.
Wherein, in step a, all elements (gi,jb)uniform denoting nonzero subblock square matrixes in the base matrix are modified using the expanding factor. Specifically, if all nonzero subblock square matrixes of the base matrix are not z*z zero matrixes, the following modifying operation is performed to all elements (gi,jb)uniform denoting nonzero subblock square matrixes in the base matrix using the expanding factor: gi,jb=floor(z·(gi,jb)uniform/zmax) wherein zmax is a specific positive integer, herein, zmax=683, floor denotes a floor operation, and other elements remain unchanged.
Wherein, the binary generator matrix is constituted of kb×nb subblock square matrixes Pgi,jb with a size of z×z, wherein the subblock square matrix with a size of z×z is a zero matrix, a unit matrix, or a cycle shift matrix of a unit matrix. Specifically, if the element gi,jb of the modified base matrix is a numerical value (for example, −1) denoting a z*z zero matrix, the subblock square matrix Pgi,jb=0, wherein the subblock square matrix Pgi,jb has a size of z×z, otherwise, the subblock square matrix Pgi,jb=(P)gi,jb, wherein the subblock square matrix Pgi,jb has a size of z×z, and




  P
  =
  
    
      [
      
        
          
            0
          
          
            1
          
          
            0
          
          
            ...
          
          
            0
          
        
        
          
            0
          
          
            0
          
          
            1
          
          
            ...
          
          
            0
          
        
        
          
            ...
          
          
            ...
          
          
            ...
          
          
            ...
          
          
            ...
          
        
        
          
            0
          
          
            0
          
          
            0
          
          
            ...
          
          
            1
          
        
        
          
            1
          
          
            0
          
          
            0
          
          
            ...
          
          
            0
          
        
      
      ]
    
    .
  




Wherein, in step 5, if all L rows and the front L columns of the binary generator matrix compose an upper right triangular or a lower right triangular matrix, the column weight of column offset to column z−1 of the binary generator matrix is increased to be 2, wherein offset is a positive integer within the range of 0 to z/3.
Wherein, in step 5, if all L rows and the front L columns of the binary generator matrix compose an upper right triangular matrix, the element at row i−1, column i of the binary generator matrix is set to be 1, wherein i is within the range of 1 to z−1.
Wherein, in step 5, if all L rows and the front L columns of the binary generator matrix compose an upper right triangular matrix, if (i+1)<12×z, an element Gtmpi,i+1 at row i, column i+1 of the binary generator matrix is set to be 1, if (i+fix(z/12))<12×z, an element Gtmpi,i+fix(z/12) at row i, column i+fix(z/12) of the binary generator matrix is set to be 1, if (i+fix(z/4))<12×z, an element Gtmpi,i+fix(z/4) at row i, column (i+fix(z/4)) of the binary generator matrix is set to be 1, if (i+fix(z/3))<12×z, an element Gtmpi,i+fix(z/3) at row i, column(i+fix(z/3) of the binary generator matrix is set to be 1, wherein i is within the range of 11×z to 12×z−1, fix denotes a floor operation. In the case when i is within the range of 0 to 11×z−1, j is within the range of 11×z to 12×z−1, and Gtmpi,j=Gtmpi,j+Gtmpi,j+25*z+Gtmpi,j+26*z+Gtmpi,j+27*z+Gtmpi,j+28*z, if Gtmpi,j>1, the element Gtmpi,j at row i, column j of the binary generator matrix is set to be 1. Wherein, the number of rows in the base matrix is 12 and the number of columns is 40.
Wherein, in step 5, if all L rows and the front L columns of the binary generator matrix compose an upper right triangular matrix, the element at row i−1, column i of the binary generator matrix is set to be 1, wherein i is within the range of 1 to z−1.
Wherein, in step 5, if all L rows and the front L columns of the binary generator matrix compose an upper right triangular matrix, if (i+1)<12×z, an element Gtmpi,i+1 at row i, column i+1 of the binary generator matrix is set to be 1, if (i+fix(z/12))<12×z, an element Gtmpi,i+fix(z/12) at row i, column i+fix(z/12) of the binary generator matrix is set to be 1, if (i+fix(z/4))<12×z, an element Gtmpi,i+fix(z/4) at row i, column (i+fix(z/4)) of the binary generator matrix is set to be 1, if (i+fix(z/3))<12×z, an element Gtmpi,i+fix(z/3) at row i, column(i+fix(z/3) of the binary generator matrix is set to be 1, wherein i is within the range of 11×z to 12×z−1, fix denotes a floor operation. In the case when i is within the range of 0 to 11×z−1, j is within the range of 11×z to 12×z−1, and Gtmpi,j=Gtmpi,j+Gtmpi,j+25*z+Gtmpi,j+26*z+Gtmpi,j+27*z+Gtmpi,j+28*z, if Gtmpi,j>1, the element Gtmp at row i, column j of the binary generator matrix is set to be 1. Wherein, the number of rows in the base matrix is 12 and the number of columns is 40.
Wherein, in step 5, modify the modified binary generator matrix for the use of encoding, permuting some columns of the check bit part of the binary generator matrix, for the purpose of further improvement on the performance of LDGC codes when the overhead is very low.
For example, when the overhead is very low, the column weight of the check bit part of the binary generator matrix is relatively large (column weight>10), a column permutation is required to make some columns with a relatively light weight (column weight<5) appear in the check bit part of the binary generator matrix, codes performance thereby can be improved when the overhead is very low. Wherein, the above check bit part refers to column L+1 to the last column, and the above column permutation refers to position exchange between two columns. Finally, the above column permutation is not necessary.
Preferably, the matrix generating process from step 1 to step 5 is interpenetrated in the encoding process in step 6.
The device for generating a generator matrix for LDGC according to the embodiments of the present invention comprises: base matrix storing means, for storing a uniform base matrix Gbuniform of an LDGC mother code set constructed by a plurality of LDGC with code rate R0 and different code lengths, wherein




  
    
      R
      0
    
    =
    
      
        k
        b
      
      
        n
        b
      
    
  
  ,




kb is the number of rows in the base matrix, nb is the number of columns in the base matrix; matrix parameter calculating means, for calculating the length L of an intermediate variable according to a relationship between length K of an information bit sequence to be encoded in the LDGC mother code set and length L of the intermediate variable, and calculating an expanding factor z for processing the base matrix using the length of the intermediate variable and the number of rows in the base matrix; base matrix modifying means, for modifying the base matrix using the expanding factor to obtain a modified base matrix Gbmodified; base matrix expanding means, for expanding the modified base matrix using the expanding factor to obtain a binary generator matrix Gtmp, wherein all L rows and the front L columns of the binary generator matrix compose a triangular matrix; generator matrix modifying means, for modifying the binary generator matrix to obtain a modified binary generator matrix; and generator matrix extracting means, for extracting L rows and the front N+L−K columns of the modified binary generator matrix which is taken as a generator matrix GIdge for the use of encoding the information bit sequence, wherein N is the length of output codeword after encoding the information bit sequence.

Wherein, the relationship between the length of the information bit sequence and the length of the intermediate variable is as follows: L=kb·ceil((p×K+q)/kb), wherein both p and q are constants greater than 0. Herein, kb=12, p=1.0235, q=30, ceil denotes a ceiling operation. The matrix parameter calculating means obtains the expanding factor using the length of the intermediate variable and the number of rows in the base matrix through the following method: z=L/kb.
Wherein, the base matrix modifying means performs a modifying operation to the element (gi,jb)uniform denoting all nonzero subblock square matrixes in the base matrix using the expanding factor. Specifically, the base matrix modifying means performs the following modifying operation to the elements (gi,jb)uniform denoting all nonzero subblock square matrixes in the base matrix using the expanding factor: gi,jb=floor (z·(gi,jb)uniform/zmax), wherein zmax=683, floor denotes a floor operation.
Wherein, the binary generator matrix is constructed by kb×nb subblock square matrixes Pgi,jb with a size of z×z, wherein the subblock square matrix with a size of z×z is a zero matrix, a unit matrix, or a cycle shift matrix of a unit matrix. Specifically, if the element of the modified base matrix is an element (−1, for example) denoting z*z zero matrix, the subblock square matrix with a size of z×z Pgi,jb=0, otherwise, the subblock square matrix has a size of z×z Pgi,jb=(P)gi,jb, wherein




  P
  =
  
    
      [
      
        
          
            0
          
          
            1
          
          
            0
          
          
            ...
          
          
            0
          
        
        
          
            0
          
          
            0
          
          
            1
          
          
            ...
          
          
            0
          
        
        
          
            ...
          
          
            ...
          
          
            ...
          
          
            ...
          
          
            ...
          
        
        
          
            0
          
          
            0
          
          
            0
          
          
            ...
          
          
            1
          
        
        
          
            1
          
          
            0
          
          
            0
          
          
            ...
          
          
            0
          
        
      
      ]
    
    .
  




Wherein, if all L rows and the front L columns of the binary generator matrix compose an upper right triangular or a lower right triangular matrix, the generator matrix modifying means increases the column weight of the column offset to column z−1 of the binary generator matrix to be 2, and increases the column weight of column (kb−1)*z to column kb*z−1 of the binary generator matrix to be greater than or equal to 30, wherein offset is a positive integer within the range of 0 to z/3.
Wherein, if all L rows and the front L columns of the binary generator matrix compose an upper left triangular or a lower left triangular matrix, the generator matrix modifying means increases the column weight of column (kb−1)*z+offset to column kb*z−1 of the binary generator matrix to be 2, and increases the column weight of column 0 to column z of the binary generator matrix to be greater than or equal to 30, wherein offset is a positive integer within the range of 0 to z/3.
Wherein, if all L rows and the front L columns of the binary generator matrix compose an upper right triangular matrix, the generator matrix modifying means sets the element at row i−1, column i of the binary generator matrix to be 1, wherein i is within the range of 1 to z−1.
Wherein, if all L rows and the front L columns of the binary generator matrix compose an upper right triangular matrix, if (i+1)<12×z, the generator matrix modifying means sets an element Gtmpi,i+1 at row i, column i+1 of the binary generator matrix to be 1, if (i+fix(z/12))<12×z, the generator matrix modifying means sets an element Gtmpi,i+fix(z/12) at row i, column i+fix(z/12) of the binary generator matrix to be 1, if (i+fix(z/4))<12×z, the generator matrix modifying means sets an element Gtmpi,i+fix(z/4) at row i, column (i+fix(z/4)) of the binary generator matrix to be 1, if (i+fix(z/3))<12×z, the generator matrix modifying means sets an element Gtmpi,i+fix(z/3) at row i, column (i+fix(z/3) of the binary generator matrix to be 1, wherein i is within the range of 11×z to 12×z−1, fix denotes a floor operation, in the case when i is within the range of 0 to 11×z−1, j is within the range of 11×z to 12×z−1, and Gtmpi,j=Gtmpi,j+Gtmpi,j+25*z+Gtmpi,j+26*z+Gtmpi,j+27*z+Gtmpi,j+28*z, if Gtmpi,j>1, the generator matrix modifying means sets the element Gtmpi,j at row i, column j of the binary generator matrix to be 1.
Wherein, the generator matrix modifying means modifies the modified binary generator matrix for the use of encoding, and permuting some columns of the check bit part of the binary generator matrix, for the purpose of further improving on the performance of LDGC codes when the overhead is very low.
For example, when the overhead is very low, the column weight of the check bit part of the binary generator matrix is relatively large (column weight>10), then, a column permutation is required to make some columns with a relatively light weight (column weight<5) appear in the check bit part of the binary generator matrix, which can improve the code performance when the overhead is very low. Wherein, the above check bit part refers to column L+1 to the last column, and the above column permutation refers to a position exchange between two columns. Finally, the above column permutation is not necessary.
Preferably, the generating process of matrix is interpenetrated in the subsequent encoding process.
By means of the present invention, code length flexibility of LDGC can be improved, and storage space for the base matrix can be reduced, so as to decrease the complexity of the code compiling.



DESCRIPTION OF THE FIGURES
The figures herein are provided for further understanding of the present invention and compose a portion of the application. The exemplary embodiments of the present invention and the illustration thereof are used to explain the present invention, but do not compose an inappropriate limit to the present invention. In the figures:
FIG. 1 is a flow chart of a encoding method for LDGC according to one embodiment of the present invention; and
FIG. 2 is a block diagram of generating device of generator matrix for LDGC according to one embodiment of the invention.



DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS
With reference to the accompanying drawings, exemplary embodiments of the present invention will be described in detail.
With reference to FIG. 1, a coding method for LDGC according to the embodiments of the present invention is described. As shown in FIG. 1, the method comprises the following steps:
S102, confirm an LDGC mother code set, wherein the mother code set is constructed by a finite number of LDGC with code rate R0=3/10 and different code lengths, the mother code set has a base matrix



  
    
      G
      b
      uniform
    
    =
    
      
        {
        
          
            (
            
              g
              
                i
                ,
                j
              
              b
            
            )
          
          uniform
        
        }
      
      
        
          k
          b
        
        ×
        
          n
          b
        
      
    
  




  
    
      
        
          
            0
          
          
            434
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            78
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            366
          
          
            179
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            424
          
          
            404
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            217
          
          
            357
          
          
            
              -
              1
            
          
        
        
          
            
              -
              1
            
          
          
            0
          
          
            525
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            213
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            382
          
          
            33
          
          
            183
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            367
          
          
            433
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
        
        
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            0
          
          
            36
          
          
            587
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            410
          
          
            469
          
          
            419
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            223
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            76
          
          
            
              -
              1
            
          
        
        
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            0
          
          
            
              -
              1
            
          
          
            117
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            248
          
          
            246
          
          
            24
          
          
            308
          
          
            
              -
              1
            
          
          
            439
          
          
            13
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            116
          
          
            
              -
              1
            
          
        
        
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            0
          
          
            23
          
          
            
              -
              1
            
          
          
            160
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            182
          
          
            
              -
              1
            
          
          
            145
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            46
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            524
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            546
          
          
            200
          
        
        
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            0
          
          
            558
          
          
            
              -
              1
            
          
          
            631
          
          
            
              -
              1
            
          
          
            12
          
          
            668
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            554
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            230
          
          
            
              -
              1
            
          
        
        
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            0
          
          
            428
          
          
            307
          
          
            
              -
              1
            
          
          
            260
          
          
            390
          
          
            27
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            481
          
          
            
              -
              1
            
          
          
            55
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            177
          
          
            
              -
              1
            
          
        
        
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            0
          
          
            91
          
          
            643
          
          
            246
          
          
            327
          
          
            561
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            591
          
        
        
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            0
          
          
            490
          
          
            400
          
          
            118
          
          
            321
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            538
          
          
            191
          
          
            
              -
              1
            
          
        
        
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            0
          
          
            276
          
          
            481
          
          
            219
          
          
            318
          
          
            
              -
              1
            
          
          
            65
          
          
            649
          
          
            
              -
              1
            
          
          
            488
          
          
            
              -
              1
            
          
          
            450
          
          
            
              -
              1
            
          
          
            221
          
          
            
              -
              1
            
          
        
        
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            0
          
          
            155
          
          
            553
          
          
            158
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            217
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            302
          
          
            676
          
        
        
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            0
          
          
            48
          
          
            
              -
              1
            
          
          
            534
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            404
          
          
            545
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            634
          
          
            455
          
        
      
      ⁢
      
        
          
            582
          
        
        
          
            54
          
        
        
          
            191
          
        
        
          
            518
          
        
        
          
            340
          
        
        
          
            522
          
        
        
          
            
              -
              1
            
          
        
        
          
            371
          
        
        
          
            22
          
        
        
          
            253
          
        
        
          
            293
          
        
        
          
            324
          
        
      
      ⁢
      
        
          
            642
          
        
        
          
            405
          
        
        
          
            681
          
        
        
          
            
              -
              1
            
          
        
        
          
            535
          
        
        
          
            662
          
        
        
          
            
              -
              1
            
          
        
        
          
            665
          
        
        
          
            240
          
        
        
          
            99
          
        
        
          
            202
          
        
        
          
            255
          
        
      
      ⁢
      
        
          
            511
          
          
            565
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            294
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            45
          
        
        
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            659
          
          
            109
          
          
            
              -
              1
            
          
          
            392
          
          
            
              -
              1
            
          
        
        
          
            
              -
              1
            
          
          
            452
          
          
            226
          
          
            585
          
          
            
              -
              1
            
          
          
            592
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
        
        
          
            121
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            40
          
          
            
              -
              1
            
          
        
        
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            281
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
        
        
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            29
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
        
        
          
            
              -
              1
            
          
          
            31
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
        
        
          
            598
          
          
            
              -
              1
            
          
          
            113
          
          
            
              -
              1
            
          
          
            273
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
        
        
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            202
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
        
        
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
        
        
          
            487
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            144
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
        
        
          
            
              -
              1
            
          
          
            566
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            285
          
        
      
      ⁢
      
        
          
            577
          
          
            
              -
              1
            
          
          
            113
          
          
            
              -
              1
            
          
          
            42
          
          
            
              -
              1
            
          
        
        
          
            
              -
              1
            
          
          
            560
          
          
            387
          
          
            1
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
        
        
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            209
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
        
        
          
            214
          
          
            
              -
              1
            
          
          
            486
          
          
            620
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
        
        
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            276
          
          
            93
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
        
        
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            205
          
          
            650
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
        
        
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            298
          
          
            285
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
        
        
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            371
          
          
            13
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
        
        
          
            
              -
              1
            
          
          
            118
          
          
            107
          
          
            392
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
        
        
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            115
          
          
            496
          
          
            
              -
              1
            
          
          
            
              -
              1
            
          
        
        
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            309
          
          
            283
          
          
            384
          
          
            320
          
        
        
          
            
              -
              1
            
          
          
            
              -
              1
            
          
          
            203
          
          
            205
          
          
            670
          
          
            120
          
        
      
    
    ⁢
    
      

    
    ⁢
    
      
    
  



that has a size of kb×nb=12×40 and a uniform format. It should be pointed out that −1 is only used to denote z*z zero square matrix, which can also be denoted by some other identifiers, such as ∞.

S104, assume a binary information bit data flow s (s can be shown as D8AB13 using hexadecimal number) of 1*K=1*24 is encoded to generate 36-bit LDGC encoding codeword by the generator matrix generated by the method according to an embodiment of the present invention, then, K=24, N=36. Obtain length L of an intermediate variable according to a relationship L=kb·ceil((p×K+q)/kb)=12·ceil((p×K+q)/12) between length K of an information bit data flow and length L of the intermediate variable, wherein p=1.0235, q=30, ceil denotes a ceiling operation, L=60.
S106, obtain an expanding factor




  z
  =
  
    
      ceil
      ⁡
      
        (
        
          L
          
            k
            b
          
        
        )
      
    
    =
    
      
        60
        12
      
      =
      5
    
  




for processing the base matrix using the length of the intermediate variable and the number of columns in the base matrix.

S108, obtain a modified base matrix Gbmodified={gi,jb}kb×nb based on the base matrix Gbuniform and the expanding factor z=5, according to the following rounding (Scale+floor) modification formula. Wherein, all (gi,jb)uniform denoting nonzero subblock square matrix of Gbuniform are modified. Specifically, if for (gi,jb)uniform≠−1 (herein, −1 denotes z*z zero square matrix) denoting a nonzero subblock square matrix in which i is from 0 to kb−1=11 and j is from 0 to nb−1=39, an operation of gi,jb=floor(z·(gi,jb)uniform/zmax) is performed, wherein zmax=683.
S110, expand Gbmodified using the expanding factor z=5 to obtain a binary generator matrix Gtmp with a size of (kb×z)×(nb×z)=60×200. Wherein, Gtmp is constructed by kb×nb=12×40=480 subblock square matrixes with a size of z×z=5×5=25, and these subblock square matrixes are zero matrixes, or unit matrixes, or cycle shift matrixes of unit matrix, as shown below:




  Gtmp
  =
  
    
      [
      
        
          
            
              P
              
                g
                
                  0
                  ,
                  0
                
                b
              
            
          
          
            
              P
              
                g
                
                  0
                  ,
                  1
                
                b
              
            
          
          
            
              P
              
                g
                
                  0
                  ,
                  2
                
                b
              
            
          
          
            ...
          
          
            
              P
              
                g
                
                  0
                  ,
                  
                    
                      n
                      b
                    
                    -
                    1
                  
                
                b
              
            
          
        
        
          
            
              P
              
                g
                
                  1
                  ,
                  0
                
                b
              
            
          
          
            
              P
              
                g
                
                  1
                  ,
                  1
                
                b
              
            
          
          
            
              P
              
                g
                
                  1
                  ,
                  2
                
                b
              
            
          
          
            ...
          
          
            
              P
              
                g
                
                  1
                  ,
                  
                    
                      n
                      b
                    
                    -
                    1
                  
                
                b
              
            
          
        
        
          
            ...
          
          
            ...
          
          
            ...
          
          
            ...
          
          
            ...
          
        
        
          
            
              P
              
                g
                
                  
                    
                      k
                      b
                    
                    -
                    1
                  
                  ,
                  0
                
                b
              
            
          
          
            
              P
              
                g
                
                  
                    
                      k
                      b
                    
                    -
                    1
                  
                  ,
                  1
                
                b
              
            
          
          
            
              P
              
                g
                
                  
                    
                      k
                      b
                    
                    -
                    1
                  
                  ,
                  2
                
                b
              
            
          
          
            ...
          
          
            
              P
              
                g
                
                  
                    
                      k
                      b
                    
                    -
                    1
                  
                  ,
                  
                    
                      n
                      b
                    
                    -
                    1
                  
                
                b
              
            
          
        
      
      ]
    
    =
    
      
        P
        
          G
          b
          modified
        
      
      .
    
  




Wherein, if gi,jb=−1, Pgi,jb=0 is defined; otherwise, Pgi,jb=(P)gi,jb is defined. Wherein, P square matrix with a size of z×z has the following format:





  P
  =
  
    
      [
      
        
          
            0
          
          
            1
          
          
            0
          
          
            ...
          
          
            0
          
        
        
          
            0
          
          
            0
          
          
            1
          
          
            ...
          
          
            0
          
        
        
          
            ...
          
          
            ...
          
          
            ...
          
          
            ...
          
          
            ...
          
        
        
          
            0
          
          
            0
          
          
            0
          
          
            ...
          
          
            1
          
        
        
          
            1
          
          
            0
          
          
            0
          
          
            ...
          
          
            0
          
        
      
      ]
    
    .
  




S112, modify the systematic bit part of the generator matrix Gtmp.
If the binary generator matrix, i.e., all L rows and the front L columns of Gtmp, compose an upper right triangular matrix-, an element at row i−1, column i of the binary generator matrix is set to be 1, wherein i is within the range of 1 to z−1=4.
If the binary generator matrix, i.e., all L rows and the front L columns of Gtmp, compose an upper right triangular or a lower right triangular matrix, the column weight of column (kb−1)*z to column kb*z−1 of the binary generator matrix is increased to be greater than or equal to 30, wherein offset is a positive integer within the range of 0 to z/3. The specific method is: herein, kb=12, for i from 11×z=11×5=55 to 12×z−1=12×5−1=59, if (i+1)<12×z=12×5=60, Gtmpi,i+1=1; if (i+fix(z/12))=(i+fix(5/12))=i<12×z=12×5=60, Gtmpi,i+fix(5/12)=Gtmpi,i=1; if (i+fix(z/4))=(i+fix(2/4))=i<12×z=12×5=60, Gtmpi, i+fix(2/4)=Gtmpi, i=1; if (i+fix(z/3))=(i+fix(5/3))=I<12×z=12×5=60, Gtmpi, i+fix(2/3)=1. Further, for i from 0 to 11×z−1=11×5−1=54, j from 11×z=11×5=55 to 12×z−1=12×5−1=59, Gtmpi,j=Gtmpi,j+Gtmpi,j+25*z+Gtmpi,j+26*z+Gtmpi,j+27*z+Gtmpi,j+28*z=Gtmpi,j+Gtmpi,j+25*5+Gtmpi,j+26*5+Gtmpi,j+27*5+Gtmpi,j+28*5, if Gtmpi,j>1, the value of Gtmp is set to be 1. Wherein, Gtmpi,j denotes an element at row i, column j of matrix Gtmp, fix denotes a floor operation, and the addition therein is arithmetic addition.
Wherein, modify the modified binary generator matrix for the use of encoding, permuting some columns of the check bit part of the binary generator matrix, for the purpose of further improving on performance of LDGC codes when the overhead is very low.
For example, when the overhead is very low, the column weight of the check bit part of the binary generator matrix is relatively large (column weight>10), then, a column permutation is required to make some columns with a relatively light weight (column weight<5) appear in the check bit part of the binary generator matrix which can improve the performance of code when the overhead is very low. Wherein, the above check bit part refers to column L+1 to the last column, and the above column permutation refers to a position exchange between two columns. Finally, the above column permutation is not necessary.
S114, a matrix Gldgc composed of kb×z=60 rows and the front 3kb×z=360 columns of Gtmp is the matrix for the use of encoding.
S116, LDGC encoding process can be performed using Gldgc and input information.
For example, encode the input LDGC (the information bit sequence m) having length K=24, generate M=36 check bit sequences, and construct a codeword sequence Cldgc having length of 60=24+36 using the information bit sequence and the check bit sequence. It should be pointed out that addition in the encoding step refers to modulo-two addition.
Assume A0, A1, . . . , AK-1 refers to an information bit sequence m having length of K=24; B0, B1, . . . , BL-1 refers to an information bit sequence s after being filled with known bit having length of L=60; D0, D1, . . . , DL-1 refers to a intermediate variable sequence I having length of L=60; E0, E1, . . . , EN+d-1 refers to a codeword sequence C before filled bit being removed having length of N+d=72; F0, F1, . . . , FN-1 refers to the codeword sequence Cldgc before filled bit being removed having length of N=36; gji refers to an element at row j, column i of Gldgc. The specific encoding process includes the following steps:
a. add d=L−K=60−24=36 known sequences (1, 1, 1, 1, 1, 1 . . . ) after inputting an information bit sequence m to construct 1*L sequence s. Wherein, Bi=Ai (i=0, 1, . . . , K−1), Bi=1 (i=K, K+1, . . . , L−1).
b. since LDGC code is a systematic code, I*Gldgc (1:L,1:L)=I* Gldgc (1:60,1:60)=s. Since square matrix Gldgc (1:L,1:L)=Gldgc (1:60,1:60) composed of L rows, the front L columns of generator matrix Gldgc and a sequence s having length of L=60 are known, the intermediate variable I is then obtained by solving the formula, wherein Gldgc (1:L,1:L)=Gldgc (1:60,1:60) is a right upper triangular matrix, D0=B0,




  
    D
    i
  
  =
  
    
      B
      i
    
    +
    
      
        ∑
        
          j
          =
          0
        
        
          i
          -
          1
        
      
      ⁢
      
        
          D
          j
        
        ⁢
        
          g
          
            j
            ,
            i
          
        
        ⁢
        
          
        
        ⁢
        
          
            (
            
              
                i
                =
                1
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                L
                -
                1
              
            
            )
          
          .
        
      
    
  




c. calculate to obtain C having length of 1*72, according to C=I*Gldgc (1:L,1:N+d)=I*Gldgc (1:60,1:72). Wherein, Ei=Bi (i=0, . . . , L−1),




  
    E
    i
  
  =
  
    
      ∑
      
        j
        =
        0
      
      
        L
        -
        1
      
    
    ⁢
    
      
        D
        j
      
      ⁢
      
        g
        
          j
          ,
          i
        
      
      ⁢
      
        
      
      ⁢
      
        
          (
          
            
              i
              =
              L
            
            ,
            ...
            ⁢
            
              
            
            ,
            
              N
              +
              d
              -
              1
            
          
          )
        
        .
      
    
  




d. delete d=36 filled bits in step a, to generate an encoded codeword Cldgc having length of 1*N=1*36. Wherein, Fi=Ei (i=0, . . . , K−1), Fi=Ei+d (i=K, . . . , N−1).
It should be pointed out that the above encoding method also comprises that, the generating process of matrix from step 1 to step 5 also can be interpenetrated in the encoding process in step 6, that is, a part of matrix information is generated in real time, then a part of the encoding operation is performed, and another part of matrix information is generated and another part of the encoding operation is then performed, and so on and so forth until the whole encoding process is completed.
In the above encoding process, the embodiments of the present invention include two kinds of situation: one is firstly generating a complete matrix GIdge composed of row kb×z=60 and the front 3kb×z=360 columns, and then using the generated matrix GIdge to perform the encoding process of step a, step b, step c, and step d mentioned above; and
the other is directly performing the encoding process of step a, step b, step c, and step d, according to the real-time requirement of matrix coefficients in encoding steps b, c, the generating process of matrix (from step 1 to step 5) shall produce the part of matrix coefficient needed.
For example, when calculating Di in the encoding process, the generating process of matrix only needs to generate {gj,i} j=0, . . . , i −1 in real time, wherein i=1, . . . , L−1; when calculating Ei in the encoding process, the generating process of matrix only needs to generate {gj,i} j=0, . . . , L−1 in real time, wherein i=L, . . . ,N +d−1. In this way, the generating process of matrix is interpenetrated in the encoding process, and only a part of the matrix coefficient is required to be generated according to encoding, which is favorable for storage reduction.
It should be pointed out that the present invention is not limited to adopt the encoding method mentioned above.
With reference to FIG. 2, a generating device of generator matrix for LDGC according to one embodiment of the present invention is shown. As shown in FIG. 2, the device comprises: base matrix storing means 202, matrix parameter calculating means 204, base matrix modifying means 206, base matrix expanding means 208, generator matrix modifying means 210, and generator matrix extracting means 212. Wherein:

    
    
        the base matrix storing means is used for storing a uniform base matrix Gbuniform of an LDGC mother code set constructed by P LDGC with code rate R0 and different code lengths, wherein
    
    






  
    
      R
      0
    
    =
    
      
        k
        b
      
      
        n
        b
      
    
  
  ,




kb is the number of rows in the base matrix, nb is the number of columns in the base matrix.

The matrix parameter calculating means is used for calculating length L of an intermediate variable, according to a relationship between length K of an information bit sequence to be encoded in the LDGC mother code set and length L of the intermediate variable, and calculating an expanding factor z for processing the base matrix using the length L of the intermediate variable and the number of rows kb in the base matrix.
The base matrix modifying means is used for modifying the base matrix using the expanding factor z, to obtain a modified base matrix Gbmodified.
The base matrix expanding means is used for expanding Gbmodified using the expanding factor z to obtain a binary generator matrix Gtmp that has not been modified.
The generator matrix modifying means is used for modifying Gtmp, and increasing the column weight of some columns of Gtmp to obtain a modified Gtmp.
The generator matrix extracting means is used for extracting a matrix Gldgc composed of L rows and the front N+L−K columns of the modified Gtmp which is taken as an LDGC generator matrix.
Wherein, a relationship between the length of the information bit sequence and the length of the intermediate variable is as follows: L=kb·ceil((p×K+q)/kb), wherein kb=12, p=1.0235, q=30, ceil denotes a ceiling operation. The matrix parameter calculating means obtains the expanding factor using the length of the intermediate variable and the number of rows in the base matrix through the following method: z=L/kb.
Wherein, the base matrix modifying means modifies all (gi,jb)uniform denoting nonzero subblock square matrixes in the base matrix using the expanding factor. Specifically, the base matrix modifying means performs the following modifying operation to all elements denoting nonzero subblock square matrixes in the base matrix using the expanding factor: gi,jb=floor(z·(gi,jb)uniform/zmax, wherein zmax=683, floor denotes a floor operation.
Wherein, the binary generator matrix is composed of kb×nb subblock square matrixes Pgi,jb with a size of z×z, wherein the subblock square matrix with a size of z×z is a zero matrix, a unit matrix, or a cycle shift matrix of a unit matrix. Specifically, if the modified base matrix is an element denoting a z*z zero square matrix, the subblock square matrix with a size of z×z Pgi,jb=0, otherwise, subblock square matrix with a size of z×z, Pgi,jb=(P)gi,jb, wherein




  P
  =
  
    
      [
      
        
          
            0
          
          
            1
          
          
            0
          
          
            ...
          
          
            0
          
        
        
          
            0
          
          
            0
          
          
            1
          
          
            ...
          
          
            0
          
        
        
          
            ...
          
          
            ...
          
          
            ...
          
          
            ...
          
          
            ...
          
        
        
          
            0
          
          
            0
          
          
            0
          
          
            ...
          
          
            1
          
        
        
          
            1
          
          
            0
          
          
            0
          
          
            ...
          
          
            0
          
        
      
      ]
    
    .
  




Wherein, if all L rows and the front L columns of the binary generator matrix compose an upper right triangular matrix or a lower right triangular matrix, the generator matrix modifying means increases the column weight of column offset to column z−1 of the binary generator matrix to be 2, and increases the column weight of column (kb−1)*z to column kb*z−1 of the binary generator matrix to be greater than or equal to 30, wherein offset is a positive integer within the range of 0 to z/3.
If all L rows and the front L columns of the binary generator matrix compose an upper left triangular matrix or a lower left triangular matrix, the generator matrix modifying means increases the column weight of column (kb−1)*z+offset to column kb*z−1 of the binary generator matrix to be 2, and increases the column weight of column 11*z to column 12*z−offset of the binary generator matrix to be greater than or equal to 30, wherein offset is a positive integer within the range of 0 to z/3.
Wherein, the generator matrix modifying means modifies the modified binary generator matrix for the use of encoding, and permuting some columns of the check bit part of the binary generator matrix, for the purpose of further improving on performance of LDGC codes when the overhead is very low.
For example, when the overhead is very low, the column weight of the check bit part of the binary generator matrix is relatively large (column weight>10), then, a column permutation is required to make some columns with a relatively light weight (column weight<5) appear in the check bit part of the binary generator matrix, which can improve the performance of code when the overhead is very low. Wherein, the above check bit part refers to column L+1 to the last column, and the above column permutation refers to a position exchange between two columns. Finally, the above column permutation is not necessary.
It should be pointed out that: the above matrix generating device further comprises that the generating process of matrix also can be interpenetrated in the subsequent encoding process, that is, the matrix generating device generates a part of the matrix information in real time and then performs a part of the encoding operation, and then, the matrix generating device further generates another part of matrix information and performs another part of the encoding operation, and so on and so forth, until the whole encoding process is completed.
The above-mentioned content is only embodiments of the present invention and not used to limit the invention. For the person skilled in the art, the present invention can have various alterations and changes. Any modification, equivalent replacement, improvement, and etc. made to the present invention within the spirit and scope thereof should be contained in the claims appending the present invention.

## Claims

1. An encoding method for Low Density Generator Matrix Codes, LDGC, comprising the following steps:
step 1, constructing an LDGC mother code set using a plurality of LDGC with code rate R0 and different code lengths, wherein the LDGC mother code set has a uniform base matrix Gbuniform={(gi,jb)uniform}kb×nb,





  
    
      R
      0
    
    =
    
      
        k
        b
      
      
        n
        b
      
    
  
  ,




kb is the number of rows in the base matrix, and nb is the number of columns in the base matrix;
step 2, obtaining length L of an intermediate variable according to a relationship between length K of an information bit sequence to be encoded in the LDGC mother code set and length L of the intermediate variable;
step 3, obtaining an expanding factor z for processing the base matrix using the length of the intermediate variable and the number of rows in the base matrix;
step 4, processing the base matrix using the expanding factor to obtain a binary generator matrix Gtmp wherein the front L rows and the front L columns of the binary generator matrix compose a triangular matrix;
step 5, modifying the binary generator matrix to obtain a modified binary generator matrix; and
step 6, taking a matrix Gldgc composed of L rows and the front N+L−K columns of the modified binary generator matrix as a generator matrix of the information bit sequence to encode the information bit sequence.

2. The method according to claim 1, wherein step 4 comprises the following steps:
step a, modifying the base matrix using the expanding factor to obtain a modified base matrix Gbmodified={gi,jb}kb×nb,and
step b, expanding the modified base matrix using the expanding factor to obtain the binary generator matrix, wherein the binary generator matrix has a size of (kb×z)×(nb×z).

3. The method according to claim 2, wherein in step 2, the relationship between the length of the information bit sequence and the length of the intermediate variable is as follows: L =kb·ceil((p×K+q)/kb), wherein both p and q are constants greater than 0, ceil denotes a ceiling operation, wherein kb=12, p=1.0235, q=30.

4. The method according to claim 3, wherein in step 3, the expanding factor is obtained using the length of the intermediate variable and the number of rows in the base matrix through the following methods: z=L/kb, wherein the number of rows in the base matrix is 12, the number of columns is 40.

5. The method according to claim 4, wherein in step a, all elements (gi,jb)uniform denoting nonzero subblock square matrixes in the base matrix are modified using the expanding factor, wherein the following modifying operation is performed to all elements (gi,jb)uniform denoting nonzero subblock square matrixes in the base matrix using the expanding factor: gi,jb=floor(z·(gi,jb)uniform/zmax), wherein zmax is a specific positive integer, floor denotes a floor operation, wherein zmax=683.

6. The method according to claim 4, wherein in step b, the binary generator matrix is constituted of kb×nb subblock square matrixes Pgi,jb with a size of z×z, wherein the subblock square matrix with a size of z×z is a zero matrix, a unit matrix, or a cycle shift matrix of a unit matrix, wherein in step b, if the element gi,jb of the modified base matrix is a numerical value denoting a z×z zero matrix, the subblock square matrix Pgi,jb=0, wherein the subblock square matrix Pgi,jb has a size of z×z, otherwise, the subblock square matrix Pgi,jb=(P)gi,jb, wherein the subblock square matrix Pgi,jb has a size of z×z, and




  P
  =
  
    
      [
      
        
          
            0
          
          
            1
          
          
            0
          
          
            ...
          
          
            0
          
        
        
          
            0
          
          
            0
          
          
            1
          
          
            ...
          
          
            0
          
        
        
          
            ...
          
          
            ...
          
          
            ...
          
          
            ...
          
          
            ...
          
        
        
          
            0
          
          
            0
          
          
            0
          
          
            ...
          
          
            1
          
        
        
          
            1
          
          
            0
          
          
            0
          
          
            ...
          
          
            0
          
        
      
      ]
    
    .

7. The method according to claim 6, wherein in step 5, if the front L rows and the front L columns of the binary generator matrix compose an upper right triangular matrix, the column weight of column offset to column z−1 of the binary generator matrix is increased to be 2, wherein offset is a positive integer within the range of 0 to z/3, wherein the element at row i−1, column i of the binary generator matrix is set to be 1, wherein i is within the range of 1 to z−1.

8. The method according to claim 6, wherein in step 5, if the front L rows and the front L columns of the binary generator matrix compose an upper right triangular matrix, the column weight of column (kb−1)*z to column kb*z−1 of the binary generator matrix is increased to be greater than or equal to 30, wherein offset is a positive integer within the range of 0 to z/3, wherein if (i+1)<12×z, an element Gtmpi,i+1 at row i, column i+1 of the binary generator matrix is set to be 1, if (i+fix(z/12))<12×z, an element Gtmpi,i+fix(z/12) at row i, column i+fix(z/12) of the binary generator matrix is set to be 1, if (i+fix(z/4))<12×z, an element Gtmpi,i+fix(z/4) at row i, column (i+fix(z/4)) of the binary generator matrix is set to be 1, if (i+fix(z/3))<12×z, an element Gtmpi,i+fix(z/3) at row i, column(i+fix(z/3) of the binary generator matrix is set to be 1, wherein i is within the range of 11×z to 12×z−1, fix denotes a floor operation, in the case when i is within the range of 0 to 11×z−1, j is within the range of 11×z to 12×z−1, and Gtmpi,j=Gtmpi,j+Gtmpi,j+25*z+Gtmpi,j+26*z+Gtmpi,j+27*z+Gtmpi,j+28*z, if Gtmpi,j22 1, the element Gtmpi,j at row i, column j of the binary generator matrix is set to be 1.

9. The method according to claim 6, wherein in step 5, if the front L rows and the front L columns of the binary generator matrix compose a lower right triangular matrix, the column weight of column offset to column z−1 of the binary generator matrix is increased to be 2, and the column weight of column (kb−1)*z to column kb*z−1 of the binary generator matrix is increased to be greater than or equal to 30, wherein offset is a positive integer within the range of 0 to z/3, if the front L rows and the front L columns of the binary generator matrix compose an upper left triangular or a lower left triangular matrix, the column weight of column (kb−1)*z+offset to column kb*z−1 of the binary generator matrix is increased to be 2, and the column weight of column 11*z to column 12*z−offset of the binary generator matrix is increased to be greater than or equal to 30, wherein offset is a positive integer within the range of 0 to z/3.

10. The method according to claim 1, wherein in step 5, modifying the modified binary generator matrix for the use of encoding, permuting some columns of the check bit part of the binary generator matrix, wherein when overhead is very low, the column weight of the check bit part of the binary generator matrix is relatively large (column weight>10), some columns with relatively light weight (column weight <5) appear in the check bit part of the binary generator matrix due to the column permutation, wherein the column permutation refers to a position exchange between two columns.

11. The method according to claim 1, wherein the matrix generating process from step 1 to step 5 is interpenetrated in the encoding process in step 6.

12. A device for generating a generator matrix for Low Density Generator matrix Codes, LDGC, comprising:
base matrix storing means, for storing a uniform base matrix Gbuniform of an LDGC mother code set constructed by a plurality of LDGC with code rate R0 and different code lengths, wherein





  
    
      R
      0
    
    =
    
      
        k
        b
      
      
        n
        b
      
    
  
  ,




kb is the number of rows in the base matrix, nb is the number of columns in the base matrix;
matrix parameter calculating means, for calculating the length L of an intermediate variable according to a relationship between length K of an information bit sequence to be encoded in the LDGC mother code set and length L of the intermediate variable, and calculating an expanding factor z for processing the base matrix using the length of the intermediate variable and the number of rows in the base matrix;
base matrix modifying means, for modifying the base matrix using the expanding factor to obtain a modified base matrix Gbmodified;
base matrix expanding means, for expanding the modified base matrix using the expanding factor to obtain a binary generator matrix Gtmp, wherein the front L rows and the front L columns of the binary generator matrix compose a triangular matrix;
generator matrix modifying means, for modifying the binary generator matrix to obtain a modified binary generator matrix; and
generator matrix extracting means, for extracting L rows and the front N+L−K columns of the modified binary generator matrix, which is taken as a generator matrix Gldgc for the use of encoding the information bit sequence, wherein N is the length of output codeword after encoding the information bit sequence.

13. The device according to claim 12, wherein the relationship between the length of the information bit sequence and the length of the intermediate variable is as follows: L=kb·ceil ((p×K+q)/kb), wherein both p and q are constants greater than 0, ceil denotes a ceiling operation, wherein kb=12, p=1.0235, q=30.

14. The device according to claim 12, wherein the matrix parameter calculating means obtains the expanding factor using the length of the intermediate variable and the number of rows in the base matrix through the following method: z=L/kb, wherein the base matrix modifying means modifies the elements (gi,jb)uniform denoting all nonzero subblock square matrixes in the base matrix using the expanding factor, wherein the base matrix modifying means performs the following modifying operation to the elements (gi,jb)uniform denoting all nonzero subblock square matrixes in the base matrix using the expanding factor: gi,jb=floor(z·(gi,jb)uniform/zmax), wherein zmax is a specific positive integer, floor denotes a floor operation, wherein zmax=683.

15. The device according to claim 14, wherein the base matrix expanding means obtains the binary generator matrix, which is composed of kb×nb subblock square matrixes Pgi,jb with a size of z×z, by expanding the modified base matrix using the expanding factor wherein the subblock square matrix with a size of z×z is a zero matrix, a unit matrix, or a cycle shift matrix of a unit matrix, wherein if element gi,jb of the modified base matrix is a numerical value denoting z*z zero square matrix, the subblock square matrix Pgi,jb=0, wherein the subblock square matrix Pgi,jb has a size of z×z, otherwise, the subblock square matrix Pgi,jb =(P)gi,jb, wherein the subblock square matrix Pgi,jb has a size of z×z, and




  P
  =
  
    
      [
      
        
          
            0
          
          
            1
          
          
            0
          
          
            ...
          
          
            0
          
        
        
          
            0
          
          
            0
          
          
            1
          
          
            ...
          
          
            0
          
        
        
          
            ...
          
          
            ...
          
          
            ...
          
          
            ...
          
          
            ...
          
        
        
          
            0
          
          
            0
          
          
            0
          
          
            ...
          
          
            1
          
        
        
          
            1
          
          
            0
          
          
            0
          
          
            ...
          
          
            0
          
        
      
      ]
    
    .

16. The device according to claim 15, wherein the generator matrix modifying means modifies the binary generator matrix through the following method: if the front L rows and the front L columns of the binary generator matrix compose an upper right triangular matrix, the generator matrix modifying means increases the column weight of column offset to column z−1 of the binary generator matrix to be 2, wherein offset is a positive integer within the range of 0 to z/3, wherein the generator matrix modifying means sets the element at row i-1, column i of the binary generator matrix to be 1, wherein i is within the range of 1 to z−1.

17. The device according to claim 15, wherein the generator matrix modifying means modifies the binary generator matrix through the following method: if the front L rows and the front L columns of the binary generator matrix compose an upper right triangular matrix, the column weight of column (kb−1)*z to column kb*z−1 of the binary generator matrix is increased to be greater than or equal to 30, wherein offset is a positive integer within the range of 0 to z/3, wherein if (i+1)<12×z, the generator matrix modifying means sets an element Gtmpi,i+l at row i, column i+1 of the binary generator matrix to be 1, if (i+fix(z/12))<12×z, the generator matrix modifying means sets an element Gtmpi,i+fix(z/12) at row i, column i+fix(z/12) of the binary generator matrix to be 1, if (i+fix(z/4))<12×z, the generator matrix modifying means sets an element Gtmpi,i+fix(z/4) at row i, column (i+fix(z/4)) of the binary generator matrix to be 1, if (i+fix(z/3))<12×z, the generator matrix modifying means sets an element Gtmpi,i+fix(z/3) at row i, column (i+fix(z/3) of the binary generator matrix to be 1, wherein i is within the range of 11×z to 12×z−1, fix denotes a floor operation, in the case when i is within a range of 0 to 11×z−1, j is within the range of 11×z to 12×z−1, and Gtmpi,j=Gtmpi,j+Gtmpi,j+25*z+Gtmpi,j+26*z+Gtmpi,j+27*z+Gtmpi, j+28*z, if Gtmpi,j>1, the generator matrix modifying means sets the element Gtmpi,j at row i, column j of the binary generator matrix to be 1.

18. The device according to claim 15, wherein the generator matrix modifying means modifies the binary generator matrix through the following method: if the front L rows and the front L columns of the binary generator matrix compose a lower right triangular matrix, the generator matrix modifying means increases the column weight of column offset to column z−1 of the binary generator matrix to be 2, and increases the column weight of column (kb−1)*z to column kb*z−1 of the binary generator matrix to be greater than or equal to 30, wherein offset is a positive integer within the range of 0 to z/3, or the generator matrix modifying means modifies the binary generator matrix through following method: if the front L rows and the front L columns of the binary generator matrix compose an upper left triangular or a lower left triangular matrix, the generator matrix modifying means increases the column weight of column (kb−1)*z+offset to column kb*z−1 of the binary generator matrix to be 2, and increases the column weight of column 11*z to column 12*z−offset of the binary generator matrix to be greater than or equal to 30, wherein offset is a positive integer within the range of 0 to z/3.

19. The device according to claim 12, wherein the generator matrix modifying means modifies the modified binary generator matrix for the use of encoding, and permuting some columns of the check bit part of the binary generator matrix, wherein when overhead is very low, the column weight of the check bit part of the binary generator matrix is relatively large (column weight>10), some columns with relatively light weight (column weight<5) appear in the check bit part of the binary generator matrix due to the column permutation, wherein the column permutation refers to a position exchange between two columns.

20. The device according to claim 12, wherein the matrix generating process is interpenetrated in subsequent coding process.