Patent Publication Number: US-7900126-B2

Title: Systems and methods for reduced complexity LDPC decoding

Description:
RELATED APPLICATION INFORMATION 
     This application claims priority under 35 U.S.C. §119(e) to U.S. Provisional Patent Application Ser. No. 60/827,353, filed Sep. 28, 2006, entitled “Reduced-Complexity Algorithm for Decoding LDPC Codes,” which is incorporated herein by reference in its entirety as if set forth in full. 
    
    
     BACKGROUND 
     1. Field of the Invention 
     The embodiments described herein are related to methods for Low-Density Parity-Check decoding and more particularly to methods for achieving reduced complexity Low-Density Parity-Check decoders. 
     2. Background of the Invention 
     A Low-Density Parity-Check (LDPC) code is an error correcting code that provides a method for transferring a message over a noisy transmission channel. While LDPC techniques cannot guaranty perfect transmission, the probability of lost information can be made very small. In fact, LDPC codes were the first to allow data transmission rates at close to the theoretical maximum, e.g., the Shannon Limit. LDPC techniques use a sparse parity-check matrix, e.g., a matrix populated mostly with zeros, hence the term low-density. The sparse matrix is randomly generated subject to the defined sparsity constraint. 
     LDPC codes can be defined as both a matrix and in graphical form. An LDPC matrix will have a certain number of rows (M) and columns (N). The matrix can also be defined by the number of 1&#39;s in each row (w r ) and the number of 1&#39;s in each column (w c ). For a matrix to be considered low-density the following conditions should be met: w c &lt;&lt;N and w r &lt;&lt;M. An LDPC matrix can be regular or irregular. A regular LDPC matrix, is one in which w c  is constant for every column and w r =w c *(N/M) is also constant for every row. If the matrix is low-density but the number of 1&#39;s in each row or column is not constant, then such codes are called irregular LDPC code. 
     It will also be understood that an LDPC code can be graphically defined by its corresponding Tanner graph. Not only do such graphs provide a complete representation of the code, they also help to describe the decoding algorithm as explained in more detail below. A Tanner graph comprises nodes and edges. The nodes are separated into two distinctive sets, or types, and the edges connect the two different types of nodes. The two types of nodes in a Tanner graph are called the variable nodes (v-nodes) and check nodes (c-nodes), or parity check nodes. Thus, the Tanner graph will consist of M check nodes (the number of parity bits) and N variable nodes (the number of bits in a code word). A check node will then be connected to a variable node if there is a 1 in the corresponding element of the LDPC matrix. 
     The number of information bits can be represented as (K). A Generator Matrix (G K×N ) can then be defined according to the following:
 
 c   N×1   =G   N×K    d   K×1 , where
         d K×1 =a message or data word, and   c N×1 =a code word.       

     As can be seen, the code word c N×1  is generated by multiplying the message by the generator matrix. The subscripts are matrix notation and refer to the number of rows and columns respectfully. Thus, the data word and code word can be represented as single column matrices with K and N rows respectfully. 
     The parity check Matrix can be defined as H M×N c N×1 =0. 
     Accordingly,  FIG. 1  is a diagram illustrating a system  100  that includes a transmitter and a receiver. A portion  102  of the transmitter and a portion  110  of the receiver are shown for simplicity. Referring to  FIG. 1 , an encoder  104  converts a data word d K×1  into a code word c N×1  via application of the generator matrix G K×N . Modulator  106  can be configured to then modulate the code word c N×1  onto a carrier so that the code word can be wirelessly transmitted across channel  108  to the receiver. 
     In receive portion  110 , demodulator  112  can be configured to remove the carrier from the received signal; however, channel  108  will add channel effects and noise, such the signal produced by demodulator  112  can have the form: r N×1 =2/σ 2 (1−2 c N×1 )+w N×1 , where r is a multilevel signal. As a result of the noise and channel effects, some of data bits d will be lost in the transmission. In order to recover as much of the data as possible, decoder  114  can be configured to use the parity check matrix H M×N  to produce an estimate d′ K×1  of the data that is very close to the original data d K×1 . It will be understood that decoder  114  can be a hard decision decoder or a soft decision decoder. Soft decision decoders are more accurate, but also typically require more resources. 
     In order to illustrate the operation of LDPC codes, the following example is presented: 
     
       
         
           
             
               H 
               
                 3 
                 × 
                 6 
               
             
             = 
             
               [ 
               
                 
                   
                     1 
                   
                   
                     0 
                   
                   
                     1 
                   
                   
                     0 
                   
                   
                     1 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     1 
                   
                   
                     0 
                   
                   
                     1 
                   
                   
                     0 
                   
                   
                     1 
                   
                 
                 
                   
                     1 
                   
                   
                     1 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     1 
                   
                 
               
               ] 
             
           
         
       
     
     As can be seen, the example parity check matrix H is low density, or sparse. The first row of matrix H defines the first parity check node, or equation. As can be seen, the first parity check node will check received samples r 0 , r 2 , and r 4 , remembering that r is the multilevel signal produced by demodulator  112  in the receiver. The second parity check node, i.e., the second row of H, checks for received samples r 1 , r 3 , and r 5 , and the third parity check node checks samples r 0 , r 1 , and r 5 . In this example, there are three parity check nodes and six samples. The first and second parity check nodes are considered orthogonal, because they involve mutually exclusive sets of samples. 
     If it is assumed that K=3 and M=3, then the following is true: 
     
       
         
           
             
               
                 H 
                 
                   3 
                   × 
                   6 
                 
               
               ⁢ 
               
                 c 
                 
                   6 
                   × 
                   1 
                 
               
             
             = 
             
               
                 0 
                 ⇔ 
                 
                   
                     H 
                     
                       3 
                       × 
                       6 
                     
                   
                   ⁡ 
                   
                     [ 
                     
                       
                         
                           
                             d 
                             
                               3 
                               × 
                               1 
                             
                           
                         
                       
                       
                         
                           
                             p 
                             
                               3 
                               × 
                               1 
                             
                           
                         
                       
                     
                     ] 
                   
                 
               
               = 
               
                 
                   0 
                   ⇔ 
                   
                     
                       [ 
                       
                         
                           
                             1 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                         
                         
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             1 
                           
                         
                         
                           
                             1 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                         
                       
                       ] 
                     
                     ⁡ 
                     
                       [ 
                       
                         
                           
                             
                               d 
                               0 
                             
                           
                         
                         
                           
                             
                               d 
                               1 
                             
                           
                         
                         
                           
                             
                               d 
                               2 
                             
                           
                         
                         
                           
                             
                               p 
                               0 
                             
                           
                         
                         
                           
                             
                               p 
                               1 
                             
                           
                         
                         
                           
                             
                               p 
                               2 
                             
                           
                         
                       
                       ] 
                     
                   
                 
                 = 
                 0 
               
             
           
         
       
     
     This produces the following equations:
 
 d   0   +d   2   +p   1 =0
 
 d   1   +p   0   +p   2 =0
 
 d   0   +d   1   +p   2 =0
 
     These equations reduce to:
 
 p   0 =d 0  
 
 p   1   =d   0   +d   2  
 
 p   2   =d   0   +d   1  
 
     Thus, for example, if d=[0;1;0], then p=[0;0;1] and c=[0;1;0;0;0;1]. 
       FIG. 2  is a Tanner Graph illustrating the operation of H in the example above. As can be seen, the graph of  FIG. 2  has three parity check nodes  202 ,  204 , and  206 , and 6 variable nodes  208 ,  210 ,  212 ,  214 ,  216 , and  218 , which correspond to the bits of c. Parity check nodes  202 ,  204 , and  206  are connected with variable nodes  208 ,  210 ,  212 ,  214 ,  216 , and  218 , via edges  220 ,  222 ,  224 ,  226 ,  228 ,  230 ,  232 ,  234 , and  236  as dictated by the entries in H. In other words, each edge  220 ,  222 ,  224 ,  226 ,  228 ,  230 ,  232 ,  234 , and  236  should correspond to a 1 in H. 
     In an LDPC decoder, the operations of the parity check and variable nodes can be implemented by processors. In other words, each parity check node can be implemented by a parity check processor, and each variable check node can be implemented by a variable node processor. An LDPC decoder is then an iterative decoder that implements a message passing algorithm defined by H. 
     Unfortunately, conventional LDPC decoding techniques result in a high complexity, fully parallel decoder implementations where all the messages to and from all the check node processors have to be computed at every iteration in the decoding process. This leads to large complexity, increased resource requirements, and increased cost. 
     Hence, there are many current efforts devoted to reducing the complexity of check node message updating, while keeping the performance loss as small as possible. The most common simplification is the min-sum algorithm (MSA), which has greatly reduced the complexity of check node updates, but incurs a 0.3-0.4 dB degradation in performance relative to standard sum-product algorithm (SPA) check node implementations. To combat this performance degradation, modifications of the MSA using a normalization term and an offset adjustment term have also been proposed. Such solutions do have reduced performance loss compared with the more conventional MSA implementations, but there is still significant performance loss. In addition, two-dimensional MSA schemes have been proposed that can further improve the performance of MSA with some additional complexity. Thus, in conventional implementations, there is a constant trade-off between complexity and performance. 
     SUMMARY 
     Systems and methods for generating check node updates in the decoding of low-density parity-check (LDPC) codes are described below. The systems and methods described below use new approximations in order to reduce the complexity of implementing a LDPC decoder, while maintaining accuracy. The new approximations approximate the standard sum-product algorithm (SPA), and can reduce the approximation error of min-sum algorithm (MSA) and has almost the same performance as sum-product algorithm (SPA) under both floating precision operation and fixed-point operation. 
     In one aspect, a receiver can include a demodulator configured to receive a wireless signal, remove a carrier signal from the wireless signal and produce a received signal, and a Low Density Parity Check (LDPC) processor configured to recover an original data signal from the received signal. The LDPC processor can include a plurality of variable node processors configured to receive the received signal and generate variable messages based on the received signal, and a parity node processor configured to receive the variable messages and generate soft outputs based in the variable messages 
     In another aspect, a receiver comprises a demodulator configured to receive a wireless signal comprising an original data signal and a carrier signal, remove the carrier signal from the wireless signal, and produce a received signal, and a Low Density Parity Check (LDPC) processor coupled with the demodulator, the LDPC processor configured to recover the original data signal from the received signal. The LDPC processor comprises a plurality of variable node processors configured to generate variable messages based on the received signal, and a check node processor coupled with the plurality of variable node processors, the check node processor configured to implement an approximation of a sum product algorithm (SPA) using base 2 logarithm operations. 
     In still another aspect, the check node processor is configured to implement an approximation of a sum product algorithm (SPA) using base 2 logarithms and rounding all operand and results to the nearest integer. 
     In still another aspect, the check node processor comprises binary hardware circuits. 
     In still another aspect, the integers produced are limited to within ±A max =±(2 v−1 −1). 
     In still another aspect, the check node processor comprises v fixed point circuits including 1 bit for the signs of the integers and v−1 bits for the absolute value. 
     These and other features, aspects, and embodiments of the invention are described below in the section entitled “Detailed Description.” 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Features, aspects, and embodiments of the inventions are described in conjunction with the attached drawings, in which: 
         FIG. 1  is a diagram illustrating an example communication system that uses LDPC codes; 
         FIG. 2  is a diagram illustrating the operation of an exemplary parity check matrix; 
         FIG. 3  is a diagram illustrating an exemplary parity node processor; 
         FIG. 4  is a diagram illustrating the operation of an exemplary parity node processor; 
         FIG. 5  is a diagram illustrating the operation of an exemplary variable node processor; 
         FIG. 6  is a graph illustrating the simulated frame error rate (FER) performance under AWGN channel for float-point SPA float-point MSA and our proposed method with different quantization bits. 
         FIG. 7  is a graph illustrating the simulated frame error rate (FER) performance under AWGN channel for float-point SPA float-point MSA and our proposed method with different quantization bits. 
         FIG. 8  is a flow chart illustrating an example method of for performing a modified LDPC decoding. 
     
    
    
     DETAILED DESCRIPTION 
     In the descriptions that follow, certain example parameters, values, etc., are used; however, it will be understood that the embodiments described herein are not necessarily limited by these examples. Accordingly, these examples should not be seen as limiting the embodiments in any way. Further, the embodiments of an LDPC decoder described herein can be applied to many different types of systems implementing a variety of protocols and communication techniques, such as Bi-Phase Shift Keying (BPSK) modulation techniques, Quadrature Phase Shift Keying (QPSK) modulation techniques, or Quadrature Amplitude Modulation (QAM) techniques. Accordingly, the embodiments should not be seen as limited to a specific type of system, architecture, protocol, air interface, etc. unless specified. 
     A check node processor  302  of degree n is shown in  FIG. 3 . At each iteration, the outgoing soft messages {λ i,  i=1, 2, . . . n} are updated with the incoming soft messages {u i ,i=1,2, . . . n}. The outgoing soft message is defined as the logarithm of the ratio of probability that the corresponding bit is 0 or 1. 
     With the standard sum-product algorithm, the outgoing message is determined as follows: 
     
       
         
           
             
               
                 
                   
                     
                       λ 
                       i 
                     
                     = 
                     
                       2 
                       ⁢ 
                       
                         tanh 
                         
                           - 
                           1 
                         
                       
                       ⁢ 
                       
                         
                           ∏ 
                           
                             
                               j 
                               = 
                               1 
                             
                             
                               j 
                               ≠ 
                               i 
                             
                           
                           n 
                         
                         ⁢ 
                         tanh 
                       
                     
                   
                   ⁣ 
                   
                     
                       
                         u 
                         j 
                       
                       2 
                     
                     , 
                     
                       i 
                       = 
                       1 
                     
                     , 
                     
                       2 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       … 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         n 
                         . 
                       
                     
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
     The outgoing soft messages are then fed back to the variable node processors for use in generating outputs u i  during the next iteration; however, a soft message λ i  based on a variable node output from a particular node are not returned to that node. Thus, the j≠i constraint in the following term of (1): 
     
       
         
           
             
               
                 ∏ 
                 
                   
                     j 
                     = 
                     1 
                   
                   
                     j 
                     ≠ 
                     i 
                   
                 
                 n 
               
               ⁢ 
               tanh 
             
             ⁣ 
             
               
                 
                   u 
                   j 
                 
                 2 
               
               , 
               
                 i 
                 = 
                 1 
               
               , 
               
                 2 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 … 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 
                   n 
                   . 
                 
               
             
           
         
       
     
     This can also be illustrated with the aide of  FIG. 4 , which is a diagram illustrating the operation of parity node processor  202 . First, the LDPC decoder will initialize the variable data bits u 0 , u 1 , u 2  . . . u 6  of variable node processors  208 ,  210 ,  212 ,  214 ,  216 , and  218  with r 0 , r 1 , r 2 , . . . r 6 . Referring to  FIG. 4 , u 0   k−1 , u 2   k−1 , and u 4   k−1  are the variable messages sent from variable nodes  208 ,  212 , and  216  to parity node processor  202 . Parity node processor  202  operates on these messages and computes its messages λ k . For example, λ k (0→2) represents the message sent from parity node  202  to variable node  212  at the kth iteration. 
     The messages produced by parity node processor  202  can be defined using the following equations: 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             λ 
                             k 
                           
                           ⁡ 
                           
                             ( 
                             
                               0 
                               -&gt; 
                               0 
                             
                             ) 
                           
                         
                         = 
                         
                           2 
                           ⁢ 
                           
                             
                               tanh 
                               
                                 - 
                                 1 
                               
                             
                             ⁡ 
                             
                               [ 
                               
                                 
                                   tanh 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       
                                         u 
                                         2 
                                         
                                           k 
                                           - 
                                           1 
                                         
                                       
                                       2 
                                     
                                     ) 
                                   
                                 
                                 ⁢ 
                                 
                                   tanh 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       
                                         u 
                                         4 
                                         
                                           k 
                                           - 
                                           1 
                                         
                                       
                                       2 
                                     
                                     ) 
                                   
                                 
                               
                               ] 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         
                           
                             λ 
                             k 
                           
                           ⁡ 
                           
                             ( 
                             
                               0 
                               -&gt; 
                               2 
                             
                             ) 
                           
                         
                         = 
                         
                           2 
                           ⁢ 
                           
                             
                               
                                 tanh 
                                 
                                   - 
                                   1 
                                 
                               
                               ⁡ 
                               
                                 [ 
                                 
                                   
                                     tanh 
                                     ⁡ 
                                     
                                       ( 
                                       
                                         
                                           u 
                                           0 
                                           
                                             k 
                                             - 
                                             1 
                                           
                                         
                                         2 
                                       
                                       ) 
                                     
                                   
                                   ⁢ 
                                   
                                     tanh 
                                     ⁡ 
                                     
                                       ( 
                                       
                                         
                                           u 
                                           4 
                                           
                                             k 
                                             - 
                                             1 
                                           
                                         
                                         2 
                                       
                                       ) 
                                     
                                   
                                 
                                 ] 
                               
                             
                             . 
                           
                         
                       
                     
                   
                   
                     
                       
                         
                           
                             λ 
                             k 
                           
                           ⁡ 
                           
                             ( 
                             
                               0 
                               -&gt; 
                               4 
                             
                             ) 
                           
                         
                         = 
                         
                           2 
                           ⁢ 
                           
                             
                               tanh 
                               
                                 - 
                                 1 
                               
                             
                             ⁡ 
                             
                               [ 
                               
                                 
                                   tanh 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       
                                         u 
                                         0 
                                         
                                           k 
                                           - 
                                           1 
                                         
                                       
                                       2 
                                     
                                     ) 
                                   
                                 
                                 ⁢ 
                                 
                                   tanh 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       
                                         u 
                                         2 
                                         
                                           k 
                                           - 
                                           1 
                                         
                                       
                                       2 
                                     
                                     ) 
                                   
                                 
                               
                               ] 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
     Thus parity node processor  202  can be configured to implement the above equations (2). The soft messages produced by the parity nodes, e.g., parity node  202 , are then fed back to variable nodes  208 ,  210 ,  212 ,  214 ,  216 , and  218 , for use in the next iteration. 
     For example,  FIG. 5  is a diagram illustrating the operation of variable node processor  208 . Referring to  FIG. 5 , variable node processor  208  receives as inputs messages from parity node processors  202  and  206  and produces variable messages to be sent back to the same parity node processors  202  and  206 . In the example of  FIG. 4  and  FIG. 5 , hard decisions are taken on the multilevel variable u n   k  and checked to see if they meet the parity node equations defined above. If there is a match, or if a certain defined number of iterations is surpassed, then the decoder can be stopped. 
     Variable node processor  208  can be configured to implement the following equation:
 
 u   0   k   =u   ch,0 +λ k (0→0)+λ k (2→0),  (3)
         where u ch,0  is the message from the channel, which does not change with each iteration       

     It will be understood that the decoder described above can be implemented using hardware and/or software configured appropriately and that while separate parity check processors and variable node processors are described, these processors can be implemented by a single processor, such as a digital signal processor, or circuit, such as an Application Specific Integrated Circuit (ASIC); however, as mentioned above, implementation of a LDPC processor such as that described with respect to  FIGS. 2-5  can result in large complexity, stringent memory requirements, and interconnect complexity that can lead to bottlenecks. These issues can be exacerbated if multiple data rates are to be implemented. In other words, practical implementation if such a decoder can be limited. 
     Accordingly, using the systems and method described above, the resources, i.e., complexity, required to implement a parity node can be reduced, while still maintaining a high degree of precision. In certain embodiments, the complexity can be reduced even further through degree reduction techniques. In other words, the number of inputs to the parity node can be reduced, which can reduce the resources required to implement the parity node. It should also be noted that in many parity node implementations, the sign and the absolute value of the outgoing soft message are calculated separately. 
     Thus, a LDPC code with parity check matrix H of size M×N has M check nodes and N variable nodes. In the decoder, soft messages are propagated and updated iteratively between variable nodes and check nodes until they agree at a valid codeword. Otherwise, the decoding will terminated with failure. The updating algorithm at a variable node involves two kinds of input messages, the message from channel observation and the message from check nodes. 
     The soft message is defined as the logarithm ratio of probability: 
     From channel observation: 
     
       
         
           
             
               
                 
                   
                     
                       L 
                       ⁡ 
                       
                         ( 
                         m 
                         ) 
                       
                     
                     = 
                     ln 
                   
                   ⁣ 
                   
                     
                       
                         
                           p 
                           0 
                         
                         ⁡ 
                         
                           ( 
                           m 
                           ) 
                         
                       
                       
                         1 
                         - 
                         
                           
                             p 
                             0 
                           
                           ⁡ 
                           
                             ( 
                             m 
                             ) 
                           
                         
                       
                     
                     , 
                     
                       m 
                       ∈ 
                       
                         [ 
                         
                           1 
                           , 
                           … 
                           ⁢ 
                           
                               
                           
                           , 
                           N 
                         
                         ] 
                       
                     
                     , 
                     and 
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
     From check nodes: 
     
       
         
           
             
               
                 
                   
                     
                       
                         λ 
                         i 
                       
                       ⁡ 
                       
                         ( 
                         m 
                         ) 
                       
                     
                     = 
                     
                       ln 
                       ⁢ 
                       
                         
                           
                             p 
                             i 
                             c 
                           
                           ⁡ 
                           
                             ( 
                             m 
                             ) 
                           
                         
                         
                           1 
                           - 
                           
                             
                               p 
                               i 
                               c 
                             
                             ⁡ 
                             
                               ( 
                               m 
                               ) 
                             
                           
                         
                       
                     
                   
                   , 
                   
                     m 
                     ∈ 
                     
                       [ 
                       
                         1 
                         , 
                         … 
                         ⁢ 
                         
                             
                         
                         , 
                         N 
                       
                       ] 
                     
                   
                   , 
                   
                     i 
                     ∈ 
                     
                       C 
                       ⁡ 
                       
                         ( 
                         m 
                         ) 
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
           
         
       
         
         
           
             where m refers to the m-th variable node, i.e. the m-th bit in the codeword. 
           
         
       
    
     L(m) is the soft message from channel observation, p o (m) is the a posterior probability that the bit is 0 conditioned on the channel observation y(m). 
     C(m) in (5) is the set of check nodes connected to the m-th variable node. p c   i (m) is the probability estimated by check node i in C(m) that the m-th bit is 0. 
     For BPSK modulation and AWGN channel with unit gain and noise variance σ 2 , L(m) becomes: 
     
       
         
           
             
               
                 
                   
                     L 
                     ⁡ 
                     
                       ( 
                       m 
                       ) 
                     
                   
                   = 
                   
                     
                       
                         2 
                         ⁢ 
                         
                           y 
                           ⁡ 
                           
                             ( 
                             m 
                             ) 
                           
                         
                       
                       
                         σ 
                         2 
                       
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
     The variable node send message u i (m) to check node i. u i (m) is defined in the same way as in (4): 
                         u   i     ⁡     (   m   )       =     ln   ⁢         p   i   v     ⁡     (   m   )         1   -       p   i   v     ⁡     (   m   )               ,     m   ∈     [     1   ,   …   ⁢           ,   N     ]       ,     i   ∈       C   ⁡     (   m   )       .               (   7   )               
Where p i   v (m) is the probability estimated by variable node that the m-th bit is 0.
 
     The updating algorithm at a variable nodes can be described as: 
                       u   i     ⁡     (   m   )       =       ∑     j   ∈       C   ⁡     (   m   )       ⁢   \   ⁢   i         ⁢         λ   j     ⁡     (   m   )       .               (   8   )               
Where C(m)\i denotes the subset of C(m) with i excluded.
 
     The outgoing message from a check node to a variable node is a function of all incoming messages from all variable nodes connected to this check node except the one that the message will be send to, i.e.:
 
λ j ( m )=ƒ( u   j ( k ), kεV ( j )\ m ), jε[ 1, . . . , M],mεV ( j ).  (9)
 
where V(j) is the set of the variable nodes connected to the j-th check node.
 
     The standard updating algorithm for ƒin (9) is the sum-product algorithm (SPA) described above and presented again here: 
     
       
         
           
             
               
                 
                   
                     
                       λ 
                       j 
                     
                     ⁡ 
                     
                       ( 
                       m 
                       ) 
                     
                   
                   = 
                   
                     2 
                     ⁢ 
                     
                       tanh 
                       
                         - 
                         1 
                       
                     
                     ⁢ 
                     
                       
                         ∏ 
                         
                           k 
                           ∈ 
                           
                             
                               V 
                               ⁡ 
                               
                                 ( 
                                 j 
                                 ) 
                               
                             
                             ⁢ 
                             \ 
                             ⁢ 
                             m 
                           
                         
                       
                       ⁢ 
                       
                         tanh 
                         ⁢ 
                         
                           
                             
                               u 
                               j 
                             
                             ⁡ 
                             
                               ( 
                               k 
                               ) 
                             
                           
                           2 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   10 
                   ) 
                 
               
             
           
         
       
     
     This is equivalent to: 
     
       
         
           
             
               
                 
                   
                     
                       λ 
                       j 
                     
                     ⁡ 
                     
                       ( 
                       m 
                       ) 
                     
                   
                   = 
                   
                     
                       ⊕ 
                       
                         k 
                         ∈ 
                         
                           
                             V 
                             ⁡ 
                             
                               ( 
                               j 
                               ) 
                             
                           
                           ⁢ 
                           \ 
                           ⁢ 
                           m 
                         
                       
                     
                     ⁢ 
                     
                       
                         
                           u 
                           j 
                         
                         ⁡ 
                         
                           ( 
                           k 
                           ) 
                         
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   11 
                   ) 
                 
               
             
           
         
       
     
     The right hand of (11) stands for |V(j)|−1 successive ⊕ operations, which is a binary operator defined as: 
                       x   ⊕   y     ⁢     =   Δ     ⁢     ln   ⁢       1   +     ⅇ     x   -   y             ⅇ   x     +     ⅇ   y             ,           (   12   )               
for x, y real numbers. It can be shown that the ⊕ operator is commutative and associative.
 
     The variable node updating algorithm (8) only involves summations. Thus most of the decoding complexity comes from the check nodes which need large amount of the evaluation of logarithms and exponentials. A simplified version for SPA is min-sum algorithm (MSA) which uses a simple approximation to evaluate the ⊕ operation:
 
 x⊕y≈sgn ( x ) sgn ( y )min{| x|,|y|}.   (13)
 
     Though MSA is simple enough to be efficiently implemented with hardware, it has some performance loss compared with SPA. The amount of loss depends on the specific code structure and code rate, generally on the order of 0.3˜0.4 dB. Many more improvements have been published in the literature with better performance, even lossless compared with SPA. 
     Certain embodiments described herein modify SPA by replacing the base e logarithm ln in equations (3),(4) and (7) with base 2 logarithm log 2 , then (6) will become: 
                     L   ⁡     (   m   )       =         2   ⁢     y   ⁡     (   m   )             σ   2     ⁢     ln   ⁡     (   2   )           .             (   14   )               
and (12) becomes:
 
     
       
         
           
             
               
                 
                   
                     x 
                     ⊕ 
                     y 
                   
                   = 
                   
                     
                       log 
                       2 
                     
                     ⁢ 
                     
                       
                         
                           1 
                           + 
                           
                             2 
                             
                               x 
                               + 
                               y 
                             
                           
                         
                         
                           
                             2 
                             x 
                           
                           + 
                           
                             2 
                             y 
                           
                         
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   15 
                   ) 
                 
               
             
           
         
       
     
     All operands and results involved in the decoding algorithm described herein can be rounded to the nearest integers. Equations (14) and (15) then become: 
                       L   ⁡     (   m   )       ≈     Round   (       2   ⁢     y   ⁡     (   m   )             σ   2     ⁢     log   ⁡     (   2   )           )       ,     and   ⁢     
     (   16   )             (   16   )                   x   ⊕   y     )     ≈     Round   (       log   2     ⁢       1   +     2     x   +   y             2   x     +     2   y           )             (   17   )               
Where Round( ) denotes rounding the operand to the nearest integer.
 
     The right hand of (16) and (17) are approximations due to the round off error, which is smaller than 0.5. 
     Note that with (16), (8) and (17), the whole decoding algorithm only use integer operations. In particular, the integer power of 2 and the integer logarithm in (17) can be easily implemented with binary hardware circuits. Thus, the complexity of standard SPA implementations can be greatly reduced. Simulation results are produced below to show that the performance loss is within 0.1 dB. 
     Further, it can be shown that (17) is exactly equivalent to the following: 
     
       
         
           
             
               
                 
                   
                     
                       x 
                       ⊕ 
                       y 
                     
                     ≈ 
                     
                       
                         sign 
                         ⁡ 
                         
                           ( 
                           x 
                           ) 
                         
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         
                           sign 
                           ⁡ 
                           
                             ( 
                             y 
                             ) 
                           
                         
                         ⁡ 
                         
                           [ 
                           
                             
                               min 
                               ⁡ 
                               
                                 ( 
                                 
                                   
                                      
                                     x 
                                      
                                   
                                   , 
                                   
                                      
                                     y 
                                      
                                   
                                 
                                 ) 
                               
                             
                             - 
                             
                               ɛ 
                               ⁡ 
                               
                                 ( 
                                 
                                   
                                      
                                     x 
                                      
                                   
                                   , 
                                   
                                      
                                     y 
                                      
                                   
                                 
                                 ) 
                               
                             
                           
                           ] 
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   18 
                   ) 
                 
               
             
             
               
                 
                   
                     ɛ 
                     ⁡ 
                     
                       ( 
                       
                         a 
                         , 
                         b 
                       
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           1 
                         
                         
                           
                             
                                
                               
                                 a 
                                 - 
                                 b 
                               
                                
                             
                             ≤ 
                             
                               1 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               and 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               min 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 ( 
                                 
                                   a 
                                   , 
                                   b 
                                 
                                 ) 
                               
                             
                             &gt; 
                             1 
                           
                         
                       
                       
                         
                           0 
                         
                         
                           
                             else 
                             . 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   19 
                   ) 
                 
               
             
           
         
       
     
     Compare (18) and (19) with the MSA in (13), and it can be seen that the complexity is only slightly increased. It should be noted that in hardware implementations, decreasing by 1 is less complex than normal subtraction and testing of ≦1 and &gt;1 only requires some bit testing logic. 
     If all the integers involved in the algorithm are limited to within ±A max =±(2 v−1 −1), then the algorithm can be directly implemented with v bits fix point circuits where 1 bit for signs and v−1 bits for the absolute value. Except that (19) should be modified to: 
     
       
         
           
             
               
                 
                   
                     ɛ 
                     ⁡ 
                     
                       ( 
                       
                         a 
                         , 
                         b 
                       
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           1 
                         
                         
                           
                             
                                
                               
                                 a 
                                 - 
                                 b 
                               
                                
                             
                             ≤ 
                             
                               1 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               and 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               min 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 ( 
                                 
                                   a 
                                   , 
                                   b 
                                 
                                 ) 
                               
                             
                             &gt; 
                             
                               1 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               and 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               max 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 ( 
                                 
                                   a 
                                   , 
                                   b 
                                 
                                 ) 
                               
                             
                             &lt; 
                             
                               A 
                               max 
                             
                           
                         
                       
                       
                         
                           0 
                         
                         
                           
                             else 
                             . 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   20 
                   ) 
                 
               
             
           
         
       
     
     This is because when one input is A max , the real value may range in [A max , +∞], thus the real value for |a−b| is highly likely to be greater than one. 
     Accordingly, using the systems and method described above, the resources, i.e., complexity, required to implement a check node can be reduced, while still maintaining a high degree of precision. In certain embodiments, the complexity can be reduced even further through degree reduction techniques. In other words, the number of inputs to the check node can be reduced, which can reduce the resources required to implement the check node. It should also be noted that in many check node implementations, the sign and the absolute value of the outgoing soft message are calculated separately. 
       FIG. 6  and  FIG. 7  are graphs illustrating respectively the simulated frame error rate (FER) and bit error rate (BER) performance under AWGN channel for float-point SPA, float-point MSA and the method described herein with different quantization bits. The LDPC code is the irregular (1152, 576) ½-rate LDPC codes constructed according to 802.16eD12. The decoder use layered decoding with maximum iteration number as 30. The curves labeled as ‘SPA2’ refers to the proposed algorithm where all the operations are integer operation. The curve labeled as ‘SPA2 unlimited’ refers to the case where A max =∞. In computer simulation, this is in fact limited by the largest integer of the system. This curve reflects the impacts of round error in (17) and (18). It can be shown that the performance loss caused by round off error is less than 0.1 dB and limiting the integer to 5 bits (A max =15) will cause almost no further loss. 
     It should be noted that we are comparing with the float-point SPA and float-point MSA are being compared. These two algorithms require about 8 bits to keep the same performance if they are directly implemented with fixed-point circuits. 
       FIG. 8  is a flow chart illustrating an example method for performing LDPC decoding as described above. First, in step  802 , a signal can be received. In step  804 , the signal can be demodulated. In step  806 , the variable messages can be generated from the demodulated signal as an estimate of the data bits. In step  808 , an operation can be performed on the variable messages to approximate the value of the original signal. This approximation is based a sum product algorithm (SPA) using base 2 logarithm operations and rounding the resulting values, as described above. This approximation can be performed in accordance with equations 16 and 17. In step  810 , the result of step  808  can be evaluated to determine if the variable message matches the parity node equations. If there is a match or if a certain number of iterations is surpassed then the LDPC decoder can stop. 
     While certain embodiments of the inventions have been described above, it will be understood that the embodiments described are by way of example only. Accordingly, the inventions should not be limited based on the described embodiments. Rather, the scope of the inventions described herein should only be limited in light of the claims that follow when taken in conjunction with the above description and accompanying drawings.