Hardware-Efficient Low Density Parity Check Code for Digital Communications

Abstract

A network element receiving signals from the network over a communications channel via transceiver circuitry. The network element has a host interface for communicating to a host system, decoded signals corresponding signals received from the network. Demodulator circuitry demodulates the signals into a data stream. Circuitry for decoding the data stream according to a sequence of operations is provided. The sequence of operations includes receiving a set of input values corresponding to input nodes of the macro parity check matrix. Estimating a check node value using values of other input nodes contributing to the parity check sum. Evaluating a probability value using the estimates of the check node values for that input node. The The operations are repeated until termination point is reached.

What is claimed is: 
     
         1 - 33 . (canceled) 
     
     
         34 . A network element, comprising:
 transceiver circuitry for receiving signals from the network over a communications channel; and   processor circuitry, comprising:
 a host interface for communicating, to a host system, decoded signals corresponding to the signals received from the network; 
 demodulator circuitry, for demodulating signals received from the network into a data stream; and 
 circuitry for decoding the data stream according to a sequence of operations comprising:
 receiving a set of input values corresponding to input nodes of the macro parity check matrix; 
 for each of the input nodes, over each of a plurality of parity check sums of the LDPC code, estimating a check node value using values of other input nodes contributing to the parity check sum; 
 for each of the input nodes, evaluating a probability value using the estimates of the check node values for that input node; and 
 repeating the estimating steps until reaching a termination criterion. 
 
   
     
     
         35 . The network element of  claim 34 , wherein the decoding circuitry comprises programmable logic circuitry;
 and further comprising:
 program memory for storing a sequence of program instructions; 
 wherein the programmable logic circuitry executes the sequence of program instructions to decode the data stream to perform the estimating and repeating operations. 
   
     
     
         36 . The network element of  claim 34 , wherein the decoding circuitry comprises:
 a check node memory for storing estimates of check node values associated with each of the input nodes over each of a plurality of parity check sums of the LDPC code;   a parallel adder coupled to the check node memory, for combining a group of check node values associated with a row of the parity check matrix with probability value estimates for input nodes corresponding to the group of check node values, to produce a plurality of extrinsic estimates;   a parity check update circuit, for updating the estimates of the check node values using the extrinsic estimates, each updated estimate of the check node values associated with an input node;   a plurality of bit update circuits, each for updating a probability value estimate corresponding to an input node;   routing circuitry, for routing each updated estimate of the check node values to the one of the plurality of bit update circuits associated with its corresponding input node; and   rerouting circuitry, for routing each updated probability value from the bit update circuits to the parallel adder.   
     
     
         37 . The network element of  claim 34 , wherein the transceiver circuitry comprises:
 RF circuitry for performing analog demodulation, amplification, and filtering of RF signals received over the communications channel.   
     
     
         38 . The network element of  claim 37 , further comprising:
 an antenna coupled to the RF circuitry.   
     
     
         39 . The network element of  claim 34 , wherein each permutation matrix corresponding to a non-zero entry of the macro matrix is a cyclically shifted identity matrix. 
     
     
         40 . The network element of  claim 39 , wherein an offset for each of the cyclically shifted identity matrices corresponds to the block row and block column of the permutation matrix in the macro matrix. 
     
     
         41 - 57 . (canceled) 
     
     
         58 . A node in an orthogonal frequency division multiplexing (OFDM) communications system, comprising:
 a receiver for receiving an OFDM signal stream containing data encoded according to a low density parity check (LDPC) code represented by a macro matrix having zero-valued and non-zero-valued entries arranged in block rows and block columns and in which each zero-valued entry corresponds to a p×p zero-valued matrix and each non-zero-valued entry corresponds to a p×p permutation matrix that has at most a single “1” entry in each row and each column and “0” entries elsewhere to define a parity check matrix, wherein the block columns of the macro matrix are grouped so that at most one column has a “1” entry in any row, and wherein the columns of the parity check matrix correspond to input nodes and the rows of the parity check matrix correspond to parity check sums, the receiver comprising:
 a demodulator for demodulating signals received from the network into a data stream; and 
 decoder circuitry, coupled to receive the data stream from the demodulator, and comprising:
 a check node memory for storing estimates of check node values associated with each of the input nodes over each of a plurality of parity check sums of the LDPC code; 
 a parallel adder coupled to the check node memory, for combining a group of check node values associated with a row of the parity check matrix with probability value estimates for input nodes corresponding to the group of check node values, to produce a plurality of extrinsic estimates; 
 a parity check update circuit, for updating the estimates of the check node values using the extrinsic estimates, each updated estimate of the check node values associated with an input node; 
 a plurality of bit update circuits, each for updating a probability value estimate corresponding to an input node; 
 routing circuitry, for routing each updated estimate of the check node values to the one of the plurality of bit update circuits associated with its corresponding input node; and 
 rerouting circuitry, for routing each updated probability value from the bit update circuits to the parallel adder. 
 
   
     
     
         59 . The network node of  claim 58 , wherein each of the plurality of bit update circuits is associated with a group of the block columns of the macro matrix;
 and wherein each of the plurality of bit update circuits comprises:
 first and second column sum memories; 
 a received data memory; 
 an incoming adder, having a first input coupled to the routing circuitry; 
 a demultiplexer, having an input coupled to the output of the incoming adder, and having outputs coupled to the first and second column sum memories; 
 a cross-switching multiplexer, having inputs coupled to outputs of the first and second column sum memories, and having a first output coupled to a second input of the incoming adder; 
 an outgoing adder, having a first input coupled to a second output of the cross-switching multiplexer, and having an output coupled to the rerouting circuitry; and 
 control circuitry, for controlling the addressing of the memories and for controlling the demultiplexer and the cross-switching multiplexer so that incoming data from the routing circuitry is being accumulated by the incoming adder in one of the first and second column sum memories, while the other of the first and second column sum memories is presenting an output to the outgoing adder that is being combined with corresponding contents of the received data memory. 
   
     
     
         60 . The network node of  claim 58 , wherein the parity check update circuit comprises a plurality of parity check update circuits, for updating the estimates of the check node values over a plurality of rows of the parity check matrix in parallel. 
     
     
         61 . The network node of  claim 58 , wherein successive portions of the extrinsic estimates for a parity check matrix row are applied to the parity check update circuit in successive cycles;
 wherein the parity check update circuit is for combining the successive portions of the extrinsic estimates to produce updated estimates of the check node values for the parity check matrix row;   and wherein one or more of the plurality of bit update circuits processes updated estimates of check node values for a first portion of the parity check matrix row in a first cycle, and processes updated estimates of check node values for a second portion of the parity check matrix row in a later cycle.   
     
     
         62 . The network node of  claim 58 , wherein successive portions of the extrinsic estimates for a parity check matrix row are applied to the parity check update circuit in successive cycles;
 wherein the parity check update circuit comprises:
 a first lookup table for producing first function values from extrinsic estimates for a parity check matrix row; 
 an augmented adder tree for generating a sum of the first function values; 
 a plurality of adders for applying corresponding ones of the first function values to the sum; 
 a second lookup table for producing second function values from the outputs of the plurality of adders; 
 sign correction functions for correcting the sign of the second function values from the sum, to produce the parity check values for the parity check matrix row; and 
 a two-stage accumulator, at the output of the augmented adder tree, for accumulating successive sums into a full sum; 
 wherein the first lookup table, the second lookup table, the plurality of adders, and the sign correction functions operate on successive data portions for the matrix row in successive cycles, the plurality of adders using the full sum from the two-stage accumulator; 
 so that the parity check update circuit generates successive portions of the parity check values for the matrix row in successive cycles. 
   
     
     
         63 . The network node of  claim 58 , wherein the check node memory is arranged in rows and columns;
 and wherein the check node memory is for storing the estimates of check node values for a first row of the parity check matrix in a first row of the check node memory, and also for storing at least some of the estimates of check node values for a second row of the parity check matrix in the first row of the check node memory.   
     
     
         64 . A low density parity code stored by a storage media, comprising:
 a macro matrix having zero-valued and non-zero-valued entries arranged in block rows and block columns and in which each zero-valued entry corresponds to a p×p zero-valued matrix and each non-zero-valued entry corresponds to a p×p permutation matrix that has at most a single “1” entry in each row and each column and “0” entries elsewhere to define a parity check matrix,   wherein the block columns of the macro matrix are grouped so that at most one column has a “1” entry in any row,   and wherein the columns of the parity check matrix correspond to input nodes and the rows of the parity check matrix correspond to parity check sums.   
     
     
         65 . The code of  claim 64 , wherein each permutation matrix corresponding to a non-zero entry of the macro matrix is a cyclically shifted identity matrix. 
     
     
         66 . The code of  claim 66 , wherein an offset for each of the cyclically shifted identity matrices corresponds to the block row and block column of the permutation matrix in the macro matrix.