Patent Publication Number: US-8977924-B2

Title: Optimized mechanism to simplify the circulant shifter and the P/Q kick out for layered LDPC decoder

Description:
FIELD OF THE INVENTION 
     The present invention is directed generally toward low-density parity-check (LDPC) codes and more particularly toward efficient LDPC matrixes and decoding architecture. 
     BACKGROUND OF THE INVENTION 
     In most real signal transmission applications there can be several sources of noise and distortions between the source of the signal and its receiver. As a result, there is a strong need to correct mistakes in the received signal. As a solution for this task one should use some coding technique with adding some additional information (i.e., additional bits to the source signal) to ensure correcting errors in the output distorted signal and decoding it. One type of coding technique utilizes low-density parity-check (LDPC) codes. LDPC codes are used because of their fast decoding (linearly depending on codeword length) property. 
     Iterative decoding algorithms allows a high degree of parallelism in processing, favoring the design of high throughput architectures of the related decoder. However, routing congestion and memory collision might limit a practical exploitation of the inherent parallelism a decoding algorithm. In order to solve this problem, codes are designed with a block structure (having blocks of size P) that naturally fit with the vectorization of the decoder architecture, thus guaranteeing a collision-free parallelism of P. 
     Joint code-decoder design techniques and the possibility of vectorizing the decoder architecture permit a reduction in the iteration latency, because P processing units work in parallel. Consequently, higher throughputs can be achieved with decoder architectures using more than P processing units in parallel; but because of the memory collision problem, the complexity overhead (or even the latency overhead in such processing that cannot be done in parallel) can be significant. 
     Consequently, it would be advantageous if an apparatus existed that is suitable for efficiently decoding LDPC code words in a layered architecture. 
     SUMMARY OF THE INVENTION 
     Accordingly, the present invention is directed to a novel method and apparatus for efficiently decoding LDPC code words in a layered architecture. 
     On embodiment of the present invention is an LDPC matrix architecture configured for use in a layered LDPC decoding architecture. 
     It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and are not restrictive of the invention claimed. The accompanying drawings, which are incorporated in and constitute a part of the specification, illustrate an embodiment of the invention and together with the general description, serve to explain the principles. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The numerous objects and advantages of the present invention may be better understood by those skilled in the art by reference to the accompanying figures in which: 
         FIG. 1  shows a block diagram of a computer system useful for implementing embodiments of the present invention; 
         FIG. 2  shows a general parity check matrix for a LDPC decoder; 
         FIG. 3  shows a circulant matrix representing an element in a parity check matrix; 
         FIG. 4  shows a system architecture for a layered LDPC decoder; 
         FIG. 5  shows an absolute shift value matrix; 
         FIG. 6  shows a delta shift value matrix; 
         FIG. 7  shows an optimized parity check matrix for a layered LDPC decoder; 
         FIG. 8  shows an optimized system architecture for a layered LDPC decoder; and 
         FIG. 9  shows a flowchart of a method for processing an optimized LDPC parity check matrix. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     Reference will now be made in detail to the subject matter disclosed, which is illustrated in the accompanying drawings. The scope of the invention is limited only by the claims; numerous alternatives, modifications and equivalents are encompassed. For the purpose of clarity, technical material that is known in the technical fields related to the embodiments has not been described in detail to avoid unnecessarily obscuring the description. 
     Referring to  FIG. 1 , a block diagram of a computing device useful for implementing embodiments of the present invention is shown. The computing device may include a processor  100  and memory  102  connected to the processor  100  to store compute executable program code. The processor  100  may implement a multi-layered architecture for LDPC decoding. 
     Referring to  FIG. 2 , a general parity check matrix for a LDPC decoder is shown. In a parity check matrix, each column  200 ,  202 ,  204 ,  206  represents a check node and each row  208 ,  210 ,  212 ,  214  represents a variable node. Connections between variable nodes and check nodes are represented in the parity check matrix wherever the matrix contains a non-zero value. Each non-zero value in the parity check matrix (P 1,1 , P 1,n , P 1,2 , P c     2   , P c     i     −1,i , P c     1     ,1 , P c     i     ,i , P c     n     ,n ) may be a circulant matrix. 
     Referring to  FIG. 3 , a circulant matrix representing an element in a parity check matrix is shown such as shown in  FIG. 2 . Circulant matrixes are square matrixes that are fully defined by a single column. A circulant matrix according to the present invention may include columns having zero elements  300  and non-zero elements  302  that may be defined as an element over a Galois Field having 2 q  elements. 
     Referring to  FIG. 4 , a system architecture for a layered LDPC decoder is shown. The layered LDPC decoder may include a ping-pong (LPQ) memory  400 . The LPQ memory  400  may store P type messages, Q type messages, log likelihood ratios (LLRs) or some combination or variation thereof. The LPQ memory  400  may receive an initial LLR. The LPQ memory  400  may be connected, through a first additive element  402 , to a first shifter element  404 . The first shifter element  404  may also be connected to the output of a first MUX  426 . The first MUX  426  may receive an absolute (ABS) shift value and a delta shift value as further defined herein. The first MUX  426  may select and send a value to the first shifter element  404 . The first shifter element  404  may bit-shift the signal received from the LPQ memory  400  and the first MUX  426 . The first shifter element  404  may then send the bit-shifted signal to a first alignment element  406 , a second alignment element  410  and a second bit-shifter element  408 . The second alignment element  410  may align the bit-shifted signal from the first bit-shifting element  410  to produce a P type message. P type messages are a-posteriori probability (APP) messages computed for a group of variable nodes. 
     A second MUX  412  may receive a bit-shifted signal from the second bit-shifter element  408  and an aligned signal from the first alignment element  406 . The second MUX  412  may select and send a signal to a second additive element  414 . The output from the second additive element  414  may comprise a Q type message. Q type messages are messages sent from a group of variable nodes to a group of check nodes. The Q type message from the second additive element  414  and the P type message from the second alignment element  410  may each be received by a third MUX  428  to produce a multiplexed P/Q signal that may comprise an updated LLR that may be received by the LPQ memory  400 . 
     The second additive element  414  may also send its Q type message output to a check node unit (CNU) array  416 . The CNU array  416  may include a series of comparators for comparing bits in one or more Q type messages. The output from the CNU array  416  may be sent to a register array  418  and a Q sign memory  420 . The register array  418  may store variables from one or more CNUs from the CNU array  416 . The Q sign memory  420  may store Q sign bits. 
     The signal from the register array  418  may be sent to a first capacitance-to-voltage (C2V) generator  422 . The output from the Q sign memory  420  may be sent to a second C2V generator  424 . The output from the second C2V generator  424  (comprising an old R value) may be sent to the second additive element  414  to be combined with the output from the second MUX  412 . The output from the first C2V generator  422  (comprising a new R value) may then be sent to the first additive element  402  to be combined with an LLR from the LPQ memory  400 . 
     By updating the LPQ memory  400  through the second MUX  428  and updating the CNU array  416  through the third MUX  412 , the system may iteratively adjust R values in a layered architecture until the system reaches a stable output. The system of  FIG. 4  may be operative to decode a generalized LDPC code, but the system requires elements that increase latency and power consumption. 
     Referring to  FIG. 5 , an absolute shift value matrix is shown. In  FIG. 5 , “0” means no shift; h i,j  means right shift h i,j  position; “x” means no operation (related to zeros-sub-matrices in the parity check matrix). The absolute shift value matrix is a matrix of values used by a hard decision (HD) memory to shift already shifted hard decisions to their original order (input order) to perform a convergence check. Each column  500 ,  502 ,  504 ,  506  may include shift values with the last shift value in each column  500 ,  502 ,  504 ,  506  equal to zero. Each row  508  may have a weight that is an even or odd number. Layered decoder processes may process a predefined number of non-zero matrices (the elements in the absolute shift value matrix except “x”) in a row  508 . The absolute shift value matrix may include zero elements  510  corresponding to identity sub-matrices in the parity-check matrix of the LDPC code. 
     Referring to  FIG. 6 , a delta shift value matrix is shown. The delta shift value matrix is a matrix of values used by layered decoder processes to shift all shifted hard decisions and LLRs that are already shifted by a previous layer processing. For example, in a first layer, data from a first circulant may be shifted by h 1,1  and stored in LPQ memory; then in a second layer, the data in the LPQ memory may be read and shifted by h 1,2 -h 1,1  for a total offset of h 1,2 . Each column  600 ,  602 ,  604 ,  606  may include shift values with a sum equal to zero. Layered decoder processes may process a predefined number of non-zero matrices in a row  608 . The delta shift value matrix may include “x” elements  610  corresponding to zero matrixes in the parity-check matrix of the LDPC code. 
     Referring to  FIG. 7 , an optimized parity check matrix for a layered LDPC decoder is shown. An optimized parity check matrix may be a K×L matrix having zero elements  702 , non-zero elements defined by a circulant matrix such as shown in  FIG. 3  or zero matrices, and identity matrixes  704  which are shown in the very last non-zeros matrices of each column. 
     Referring to  FIG. 8 , an optimized system architecture for a layered LDPC decoder is shown. The optimized layered LDPC decoder may utilize an optimized layered parity check matrix such as shown in  FIG. 7 . The layered LDPC decoder may include LLR ping-pong (LPQ) memory  800 . The LPQ memory  800  may store P type messages, Q type messages, log likelihood ratios (LLRs) or some combination or variation thereof. The LPQ memory  800  may receive an initial LLR. The LPQ memory  800  may be connected, through a first additive element  802 , to a shifter element  804 . The shifter element  804  may also receive a delta shift value such as defined in  FIG. 6 . The shifter element  804  may then send a bit-shifted signal to a second additive element  814  and a MUX  828 . The bit-shifted signal from the shifter element  804  may be a P type message. The output from the second additive element  814  may comprise a Q type message. The MUX  828  may produce a multiplexed P/Q signal that may comprise an updated LLR that may be received by the LPQ memory  800 . 
     The second additive element  814  may also send its Q type message output to a CNU array  816 . The CNU array  816  may include a series of comparators for comparing bits in one or more Q type messages. The output from the CNU array  816  may be sent to a register array  818  and a Q sign memory  820 . The register array  818  may store variables from one or more CNUs from the CNU array  816 . The Q sign memory  820  may store Q sign bits. 
     The signal from the register array  818  may be sent to a first C2V generator  822 . The output from the Q sign memory  820  may be sent to a second C2V generator  824 . The output from the second C2V generator  824  (comprising an old R value) may be sent to the second additive element  814  to be combined with the output from shifter element  804 . The output from the first C2V generator  822  (comprising a new R value) may then be sent to the first additive element  802  to be combined with an LLR from the LPQ memory  800 . 
     By updating the LPQ memory  800  through the MUX  828  and updating the CNU array  816  through the shifter element  804 , the system may iteratively adjust R values in a layered architecture until the system reaches a stable output. The system of  FIG. 8  may be operative to decode an optimized LDPC code. 
     Referring to  FIG. 9 , a flowchart of a method for processing an optimized LDPC parity check matrix is shown. The method may include receiving  900  an initial LLR. The initial LLR may be stored  902  in a LPQ memory. The LLR may be shifted  904  based on a delta shift value from a delta shift value matrix. Values from two or more variable nodes may be compared  906  to one or more check nodes. Information from such comparison may be stored  908  in a register array. Q sign bit from such comparison may be stored  910  in a Q sign memory. A C2V generator may generate  912  a voltage based on information in the register array. A C2V generator may also generate  914  a C2V message based on Q sign bits in a Q sign memory. 
     The C2V message based on the stored information may be combined  916  with an LLR stored in a LPQ memory and the result shifted  904  based on a delta shift value from a delta shift matrix to produce a P type message. Likewise, the C2V message based on the Q sign bits may be combined  918  with a bit shifted LLR value to produce a Q type message. A multiplexer may select  920  elements of the P type message and Q type message to produce a signal, and the resulting signal may be stored  902  in a LPQ memory. 
     By this method, a system for decoding a LDPC code in a layered architecture may utilize an optimized LDPC parity check matrix for low latency. 
     It is believed that the present invention and many of its attendant advantages will be understood by the foregoing description, and it will be apparent that various changes may be made in the form, construction, and arrangement of the components thereof without departing from the scope and spirit of the invention or without sacrificing all of its material advantages. The form herein before described being merely an explanatory embodiment thereof, it is the intention of the following claims to encompass and include such changes.