Structured de-interleaving scheme for product code decoders

Abstract

A structured interleaving/de-interleaving scheme enables efficient implementation of encoding/decoding based on two-dimensional product codes (2D PC). An encoder has an integrated architecture that performs structured interleaving and PC coding in an integrated manner in which locations in the interleaved data stream are related to row and column indices for the 2D PC coding based on closed-form expressions. In one embodiment, a corresponding decoder implements two-stage low-density parity-check (LDPC) decoding based on the same relationships between locations in the interleaved data stream and row and column indices for the LDPC decoding.

1. A decoding-apparatus-implemented method for decoding a codeword generated by encoding and interleaving a set of L 2  original data values having an original sequence, the method comprising:
 (a) receiving the codeword having L 2  original data values, L row parity values, and L column parity values; and 
 (b) applying low-density parity-check decoding to the codeword to generate a decoded codeword, wherein:
 the L 2  original data values correspond to an (L×L) original block of data; 
 the original block corresponds to the L 2  original data values arranged in rows and columns of non-contiguous original data values in the original block; 
 each row parity value corresponds to an application of a row parity operation to a different row of non-contiguous original data values in the original block; 
 each column parity value corresponds to an application of a column parity operation to a different column of non-contiguous original data values in the original block; 
 the codeword comprises the L 2  original data values in the original sequence and interleaved with the L row parity values and the L column parity values; and 
 step (b) comprises generating the decoded codeword based on the non-contiguity of the original data values in the rows and columns of the original block. 
 
 
     
     
       2. The method of  claim 1 , wherein:
 the original block corresponds to the original sequence of the L 2  original data values arranged in a diagonal pattern in the original block; and 
 step (b) comprises applying the diagonal pattern in generating the decoded codeword. 
 
     
     
       3. The method of  claim 1 , wherein the codeword corresponds to an (L+1)×(L+1) augmented block of data comprising:
 the L row parity values correspond to Column  0  of the augmented block; 
 the L column parity values correspond to Row  0  of the augmented block; 
 the L 2  original data values correspond to Rows  1 -L and Columns  1 -L of the augmented block; and 
 step (b) comprises retrieving the decoded codeword from the augmented block based on non-contiguity of the original data values in the row and columns of the augmented block. 
 
     
     
       4. The method of  claim 3 , wherein, according to the structured interleaving, locations S in the codeword for the L 2 +2L values in the augmented block correspond to:
     n =mod( S,L+ 1) 
     m =mod(mod( S,L+ 1)+floor( S,L+ 1)), L+ 1), 
 
       where:
 S runs from 1 to L 2 +2L; 
 mod (x, y) is a modulo function that returns the integer remainder from an integer division of x by y; 
 floor (x, y) is a floor function that returns the integer result of the integer division of x by y; 
 n is a row index in the augmented block for the S th  codeword location, where nε{0, . . . , L}; 
 m is a column index in the augmented block for the S th  codeword location, where mε{0, . . . , L}; and 
 step (b) comprises retrieving the decoded codeword from the augmented block based on the locations S. 
 
     
     
       5. The method of  claim 1 , further comprising the step of de-interleaving the decoded codeword by removing the parity values from the decoded codeword, wherein locations of the parity values in the decoded codeword are based on one or more closed-form mathematical expressions. 
     
     
       6. An apparatus for decoding a codeword generated by encoding and interleaving a set of L 2  original data values having an original sequence, the apparatus adapted to:
 (a) receive the codeword having L 2  original data values, L row parity values, and L column parity values; and 
 (b) apply low-density parity-check (LDPC) decoding to the codeword to generate a decoded codeword, wherein:
 the L 2  original data values correspond to an (L×L) original block of data; 
 the original block corresponds to the L 2  original data values arranged in rows and columns of non-contiguous original data values in the original block; 
 each row parity value corresponds to an application of a row parity operation to a different row of non-contiguous original data values in the original block; 
 each column parity value corresponds to an application of a column parity operation to a different column of non-contiguous original data values in the original block; 
 the codeword comprises the L 2  original data values in the original sequence and interleaved with the L row parity values and the L column parity values; and 
 the apparatus is adapted to generate the decoded codeword based on the non-contiguity of the original data values in the rows and columns of the original block. 
 
 
     
     
       7. The apparatus of  claim 6 , wherein the apparatus comprises an LDPC decoder comprising:
 row encoding logic adapted to map a current location in the codeword to a row index of a corresponding (L+1)×(L+1) augmented block of data; 
 column encoding logic adapted to map the current codeword location to a column index of the augmented block; 
 a first LDPC decoding stage adapted to partially decode L rows and L columns of the augmented block to generate a partially decoded augmented block; and 
 a second LDPC decoding stage adapted to further decode L rows and L columns of the partially decoded augmented block to generate a fully decoded augmented block, wherein:
 the first LDPC decoding stage comprises L row decoders and L column decoders; 
 the second LDPC decoding stage comprises L row decoders and L column decoders; 
 the row index generated by the row encoding logic is used to direct (1) a current value of the augmented block to a corresponding row decoder in the first stage and (2) a current value of the partially decoded augmented block to a corresponding row in the second stage; and 
 the column index generated by the column encoding logic is used to direct (1) a current value of the augmented block to a corresponding column decoder in the first stage and (2) a current value of the partially decoded augmented block to a corresponding column in the second stage. 
 
 
     
     
       8. The apparatus of  claim 7 , wherein:
 the row encoding logic evaluates a first closed-form mathematical expression to calculate the row index n for the current codeword location S; and 
 the column encoding logic evaluates a second closed-form mathematical expression to calculate the column index m for the current codeword location S. 
 
     
     
       9. The apparatus of  claim 8 , wherein:
 the first closed-form mathematical expression corresponds to:
     n =mod( S,L+ 1) 
 
 the second closed-form mathematical expression corresponds to:
     m =mod(mod( S,L+ 1)+floor( S,L+ 1)), L+ 1). 
 
 
     
     
       10. The apparatus of  claim 6 , further comprising a de-interleaver adapted to de-interleave the decoded codeword by removing the parity values from the decoded codeword, wherein locations of the parity values in the decoded codeword are based on one or more closed-form mathematical expressions. 
     
     
       11. The apparatus of  claim 6 , wherein:
 the original block corresponds to the original sequence of the L 2  original data values arranged in a diagonal pattern in the original block; and 
 the apparatus is adapted to apply the diagonal pattern in generating the decoded codeword. 
 
     
     
       12. An apparatus for decoding a codeword generated by encoding and interleaving a set of L 2  original data values having an original sequence, the apparatus adapted to:
 (a) receive the codeword having L 2  original data values, L row parity values, and L column parity values; and 
 (b) apply low-density parity-check (LDPC) decoding to the codeword to generate a decoded codeword, wherein:
 the L 2  original data values correspond to an (L×L) original block of data; 
 each row parity value corresponds to an application of a row parity operation to a different row of the original block; 
 each column parity value corresponds to an application of a column parity operation to a different column of the original block; 
 the codeword comprises the L 2  original data values in the original sequence and interleaved with the L row parity values and the L column parity values; and 
 the apparatus comprises an LDPC decoder comprising:
 row encoding logic adapted to map a current location in the codeword to a row index of a corresponding (L+1)×(L+1) augmented block of data; 
 column encoding logic adapted to map the current codeword location to a column index of the augmented block; 
 a first LDPC decoding stage adapted to partially decode L rows and L columns of the augmented block to generate a partially decoded augmented block; and 
 a second LDPC decoding stage adapted to further decode L rows and L columns of the partially decoded augmented block to generate a fully decoded augmented block, wherein:
 the first LDPC decoding stage comprises L row decoders and L column decoders; 
 the second LDPC decoding stage comprises L row decoders and L column decoders; 
 the row index generated by the row encoding logic is used to direct (1) a current value of the augmented block to a corresponding row decoder in the first stage and (2) a current value of the partially decoded augmented block to a corresponding row in the second stage; and 
 the column index generated by the column encoding logic is used to direct (1) a current value of the augmented block to a corresponding column decoder in the first stage and (2) a current value of the partially decoded augmented block to a corresponding column in the second stage. 
 
 
 
 
     
     
       13. The apparatus of  claim 12 , wherein:
 the row encoding logic evaluates a first closed-form mathematical expression to calculate the row index n for the current codeword location S; and 
 the column encoding logic evaluates a second closed-form mathematical expression to calculate the column index m for the current codeword location S. 
 
     
     
       14. The apparatus of  claim 13 , wherein:
 the first closed-form mathematical expression corresponds to:
     n =mod( S,L+ 1) 
 
 the second closed-form mathematical expression corresponds to:
     m =mod(mod( S,L+ 1)+floor( S,L+ 1)), L+ 1).