Method and system for generating low density parity check codes

Abstract

An approach for generating a structured Low Density Parity Check (LDPC) codes is provided. Structure of the LDPC codes is provided by restricting a certain part of the parity check matrix to be lower triangular, hence enabling a very simple encoding method that does not require the generator matrix of the code. The approach can also exploit the unequal error protecting capability of LDPC codes on transmitted bits to provide extra error protection to more vulnerable bits of high order modulation constellations (such as 8-PSK (Phase Shift Keying)). Additionally, an efficient decoding scheme is described where both bit nodes and check nodes are partitioned into groups. The edge values associated with each of the group can be placed together in memory simultaneously for bit nodes groups and check nodes groups. This architecture allows the multiple edges to be fetched from memory at a single clock cycle. A method of designing the parity check matrix that ensures the fetching of all the adjacent edges for a group of bit nodes or check nodes in a few clock cycles is described. The above approach is particularly applicable to bandwidth constrained communication systems requiring high data rates.

What is claimed is:  
     
         1 . A method for generating low density parity check (LDPC) codes, the method comprising: 
 transforming a received input message into a LDPC codeword using only a parity check matrix of the LDPC codes without using a generator matrix of the LDPC codes; and    outputting the LDPC codeword.    
     
     
         2 . A method according to  claim 1 , wherein a predetermined triangular portion of the parity check matrix in the transforming step has zero values, the method further comprising: 
 storing values of the parity check matrix to facilitate generation of the parity bits associated with the LDPC codes.    
     
     
         3 . A method according to  claim 1 , wherein a predetermined triangular portion of the parity check matrix in the transforming step has zero values after row or column permutation, the method further comprising: 
 storing values of the parity check matrix to facilitate generation of the parity bits associated with the LDPC codes.    
     
     
         4 . A method according to  claim 1 , further comprising: 
 modulating the LDPC code according to a modulation scheme including one of 8-PSK (Phase Shift Keying), 16-QAM (Quadrature Amplitude Modulation), and QPSK (Quadrature Phase Shift Keying).    
     
     
         5 . A computer-readable medium bearing instructions for generating linear block codes, said instruction, being arranged, upon execution, to cause one or more processors to perform the method of  claim 1 .  
     
     
         6 . A method for supporting encoding of linear block codes, the method comprising: 
 mapping higher order signal constellation bits to bit nodes of a parity check matrix corresponding to the linear block codes,    wherein vulnerable bits of the signal constellation are mapped to the bit nodes with at least three edges.    
     
     
         7 . A method according to claims  6 , wherein the signal constellation includes one of 8-PSK (Phase Shift Keying), 16-QAM (Quadrature Amplitude Modulation), and QPSK (Quadrature Phase Shift Keying).  
     
     
         8 . A computer-readable medium bearing instructions for generating linear block codes, said instruction, being arranged, upon execution, to cause one or more processors to perform the method of  claim 6 .  
     
     
         9 . A method for supporting encoding of linear block codes, the method comprising: 
 mapping higher order signal constellation bits to bit nodes of a parity check matrix corresponding to the linear block code,    wherein vulnerable bits of the signal constellation are mapped to the bit nodes with number of edges no less than that of more reliable bits.    
     
     
         10 . A method according to  claim 9 , wherein the signal constellation includes one of 8-PSK (Phase Shift Keying), 16-QAM (Quadrature Amplitude Modulation), and QPSK (Quadrature Phase Shift Keying).  
     
     
         11 . A computer-readable medium bearing instructions for generating linear block codes, said instruction, being arranged, upon execution, to cause one or more processors to perform the method of  claim 9 .  
     
     
         12 . A method for generating low density parity check (LDPC) codes, the method comprising: 
 transforming a received input message into a LDPC codeword using only a parity check matrix of the LDPC codes without using a generator matrix of the LDPC codes;    applying an outer code to the LDPC codeword; and    outputting the LDPC codeword with the applied outer code.    
     
     
         13 . A method according to  claim 12 , wherein the outer code in the applying step includes one of a Bose, Chaudhuri, and Hocquenghem (BCH) code, a Reed-Solomon (RS) code, and a Hamming code.  
     
     
         14 . A method for generating low density parity check (LDPC) code, the method comprising: 
 placing contents of edges for a group of bit nodes next to one another in memory; and    simultaneously placing contents of edges for a group of check nodes next to one another in the memory.    
     
     
         15 . A method according to  claim 14 , further comprising: 
 accessing the memory to retrieve edge values associated with a group of bit nodes or a group of check nodes in a single clock cycle.    
     
     
         16 . A computer-readable medium bearing instructions for generating linear block codes, said instruction, being arranged, upon execution, to cause one or more processors to perform the method of  claim 14 .  
     
     
         17 . A system for generating low density parity check (LDPC) codes, the system comprising: 
 means for transforming a received input message into a LDPC codeword using only a parity check matrix of the LDPC codes without using a generator matrix of the LDPC codes; and    means for outputting the LDPC codeword.    
     
     
         18 . A system according to  claim 17 , wherein a predetermined triangular portion of the parity check matrix has zero values, the system further comprising: 
 means for storing values of the parity check matrix to facilitate generation of the parity bits associated with the LDPC codes.    
     
     
         19 . A system according to  claim 17 , wherein a predetermined triangular portion of the parity check matrix has zero values after row or column permutation, the system further comprising: 
 means for storing values of the parity check matrix to facilitate generation of the parity bits associated with the LDPC codes.    
     
     
         20 . A system according to  claim 17 , further comprising: 
 modulating the LDPC code according to a modulation scheme including one of 8-PSK (Phase Shift Keying), 16-QAM (Quadrature Amplitude Modulation), and QPSK (Quadrature Phase Shift Keying).    
     
     
         21 . A method for processing low density parity check (LDPC) codes, the method comprising: 
 decoding via a LDPC decoder received LDPC codes; and    iteratively regenerating signal constellation bit metrics into the LDPC decoder after every or several LDPC decoder iterations.