Low density parity check decoder
A method and system for decoding low density parity check (LDPC) codes. A method includes performing block parallel processing that initiates processing all non-zero block columns of a plurality (M) of rows of a layer of an LDPC matrix in each clock cycle, where M≤p, and p is a total number of rows in a layer of the LDPC matrix; and updating a P message responsive to determination of a final state for each row of the LDPC matrix. The LDPC matrix includes layers, each comprising a plurality (M) of rows that are processed per clock cycle. Each of the plurality of rows of each of the layers is datawise independent of the rows processed during a previous NP_MAX clock cycles and at least one row in each layer is datawise dependent on a row of an immediately preceding layer, and NP_MAX is greater than one.
1 . A method for decoding a low density parity check (LDPC) code, comprising:
performing block parallel processing that initiates processing all non-zero block columns of a plurality (M) of rows of a layer of an LDPC matrix in each clock cycle, and wherein M≤p, and p is a total number of rows in a layer of the LDPC matrix; and
updating a P message responsive to determination of a final state for each row of the LDPC matrix,
wherein the LDPC matrix comprises a plurality of layers, each of the layers comprising a plurality (M) of rows that are processed per clock cycle,
wherein each of the plurality of rows of each of the layers is datawise independent of the rows processed during a previous number (NP_MAX) of clock cycles and at least one row in each layer is datawise dependent on a row of an immediately preceding layer, and
wherein NP_MAX is greater than one.
2 . The method of claim 1 , further comprising generating a Q message by combining an R message with a P message.
3 . The method of claim 1 , further comprising permuting the P message.
4 . The method of claim 3 , wherein the P message is permuted by a difference of permutation of a block currently being processed and permutation of a block previously processed, wherein the block currently being processed and the block previously processed are in a same block column of the LDPC matrix.
5 . The method of claim 4 , wherein the permuting comprises an M×M permutation, and wherein the method further comprises permuting P messages for M rows of the LDPC matrix, where p is the circulant size, and M<=p.
6 . The method of claim 1 , further comprising subtracting an R message from a permuted P message to generate a Q message.
7 . The method of claim 1 , further comprising selecting one of an updated P message and a channel log-likelihood ratio (LLR) for storage in a P memory, wherein a channel LLR is selected to initialize decoding.
8 . The method of claim 1 , further comprising selecting an R message from a plurality of previously generated possible R messages based on at least a message index value and a sign bit.
9 . The method of claim 1 , wherein the LDPC matrix is quasi-cyclic.
10 . The method of claim 1 , wherein each of the plurality (M) of rows for which processing is initiated in a given clock cycle comprises non-zero entries only in different columns from non-zero entries of rows for which processing is initiated during the previous NP_MAX clock cycles.
11 . A method for decoding a low density parity check (LDPC) code, comprising:
performing block parallel processing of an LDPC matrix;
selectably processing in parallel a first plurality (dc1) of block columns of a plurality (M1) of rows of a layer of a first LDPC matrix, where:
dc1 is a check node degree of a block row of the first LDPC matrix;
p1 is a total number of rows of the block row of a first LDPC matrix; and
M1<=p1; and
selectably processing in parallel a second plurality (dc2) of block columns of a plurality (M2) of rows of a layer of a second LDPC matrix, where:
dc2 is a check node degree of a block row of the second LDPC matrix, and dc1 is different from dc2;
p2 is a total number of rows of the block row of the second LDPC matrix;
M2<=p2; and
M2 is different from M1.
12 . The method of claim 11 , further comprising:
partitioning a vector of input values into a plurality of sub-vectors;
determining a first minimum value and a second minimum value for each sub-vector; and
determining a first minimum and a second minimum of the vector based on the first minimum value and second minimum value of the sub-vectors.
13 . The method of claim 11 , further comprising configuring an array of reconfigurable minimum finder units to perform the block parallel processing, selectably process the first plurality (dc1) of block columns, and selectably process the second plurality (dc2) of block columns.