Efficient, programmable and scalable low density parity check decoder

Abstract

Novel design of an LDPC decoder suitable for a range of code-block sizes and bit-rates, also suitable for both ASIC and FPGA implementations, is provided, in which the overhead associated with correction data sent along the transmission channel can be minimized. An LDPC decoder can be optimized for either eIRA based or general H matrices. An H parity matrix can be constructed and/or manipulated to arrange the bit-node message “columns” to facilitate mapping to MPB “columns” and corresponding access via LUT pointer tables to minimize processing cycles so as to: (i) minimize address conflicts within the same MPB that will take multiple access cycles to resolve; (ii) minimize splitting of bit-node messages across MPB “columns” that will take multiple access cycles to resolve; and (iii) balance the bit-node computations across all the MPB/LUT “columns” so that they will complete their computations at nearly the same time.

1 - 6 . (canceled) 
     
     
         7 . A method of increasing processing efficiency in an LDPC decoder, comprising:
 constructing and/or manipulating an H parity matrix so as to arrange bit-node message “columns” to facilitate mapping to MPB “columns” of an LDPC decoder and corresponding access via LUT pointer tables to minimize processing cycles.   
     
     
         8 . The method of  claim 7 , wherein said minimization of processing cycles achieves one of (i) minimizing address conflicts within the same MPB that will take multiple access cycles to resolve; (ii) minimize splitting of bit-node messages across MPB “columns” that will take multiple access cycles to resolve; and (iii) balance the bit-node computations across all the MPB/LUT “columns” so that they will complete their computations at nearly the same time. 
     
     
         9 . A low density parity check decoder comprising:
 a plurality of message processing blocks arranged in a logical array;   a plurality of info bit processors, one for each column of said message processing blocks in said logical array;   a plurality of lookup table memories, one for each column of said message processing blocks in said logical array; and   a plurality of check message processors, one for each row of said message processing blocks in said logical array,   wherein said decoder iteratively operates to decode a data signal.   
     
     
         10 . The decoder of  claim 9  wherein said message processing blocks, informant bit processors, and lookup table memories are optimized for implementation in one of an ASIC or a FPGA. 
     
     
         11 . A low density parity check decoder optimized for a parity check matrix in eIRA format comprising:
 a plurality of message processing blocks arranged in a logical array;   a plurality of info bit processors, one for all but two columns of said message processing blocks in said logical array;   a plurality of lookup table memories, one for all but two columns of said message processing blocks in said logical array;   a plurality of check message processors, one for each row of said message processing blocks in said logical array;   wherein said decoder iteratively operates to decode an original data signal.   
     
     
         12 . The decoder of  claim 11 , wherein said message processing blocks, informant bit processors, and lookup table memories are optimized for implementation in one of an ASIC or a FPGA. 
     
     
         13 . The decoder of  claim 9 , wherein at least one of:
 said check message processors collect check messages from the MPBs and distribute final check-node message sums back to the MPBs to complete their check message computation,   the info bit message processor blocks collect bit-node messages from the MPBs and distribute final bit-node message sums back to the MPBs to complete their bit-node message computation, or   the check message processors and the information bit processors respectively contain soft symbol buffers and information bit buffers so that a next codeword can be loaded, and a previous codeword's computed information bits can be output while a current codeword is being decoded.   
     
     
         14 . The decoder of  claim 9 , further comprising at least one of:
 signal busses interconnecting the check message processors and bit information processors, said busses having multiplexed functionality for inter-block communication and soft symbol/informationbit input/output functions, or   an address conflict resolution and crossbar block, arranged to allow bit message computation requiring contributions from more that one MPB “column.”   
     
     
         15 . The decoder of  claim 9 , wherein the lookup table memories hold bit-node message memory access pointers required for computing bit messages on a column basis. 
     
     
         14 . The decoder of  claim 9 , wherein the info bit message processor blocks collect bit-node messages from the MPBs and distribute final bit-node message sums back to the MPBs to complete their bit-node message computation, and wherein at least one of:
 said bit-node message memory access pointers specify, for a given bit message column computation, which message location within a particular MPB is involved in the bit-node message summation, or   said bit-node message memory access pointers specify, for a given bit message column computation, which message location within a particular MPB is involved in the bit-node message summation, and if no location within the MPB is required, then a null pointer location can be specified and the MPB contributes zero to the sum.   
     
     
         15 . The decoder of  claim 11 , wherein at least one of:
 said check message processors collect check messages from the MPBs and distribute final check-node message sums back to the MPBs to complete their check message computation,   the info bit message processor blocks collect bit-node messages from the MPBs and distribute final bit-node message sums back to the MPBs to complete their bit-node message computation,   the check message processors and the information bit processors respectively contain soft symbol buffers, and information bit buffers so that a next codeword can be loaded, and a previous codeword's computed information bits can be output while a current codeword is being decoded, or   the lookup table memories hold bit-node message memory access pointers required for computing bit messages on a column basis.   
     
     
         16 . The decoder of  claim 11 , further comprising signal busses interconnecting the check message processors and bit information processors, said busses having multiplexed functionality for inter-block communication and soft symbol/information bit input/output functions. 
     
     
         17 . The decoder of  claim 11 , wherein the info bit message processor blocks collect bit-node messages from the MPBs and distribute final bit-node message sums back to the MPBs to complete their bit-node message computation, and wherein at least one of:
 said bit-node message memory access pointers specify, for a given bit message column computation, which message location within a particular MPB is involved in the bit-node message summation, or   said bit-node message memory access pointers specify, for a given bit message column computation, which message location within a particular MPB is involved in the bit-node message summation, and if no location within the MPB is required, then a null pointer location can be specified and the MPB contributes zero to the sum.