Methods and systems for parallelizing high throughput iterative decoders

Abstract

Methods and systems are disclosed for decoding codewords, wherein codewords comprise at least one circulant and are stored in a first dimension of a matrix, and wherein each circulant in a codeword is associated with a location in a second dimension in the matrix. The method includes determining whether a first location in a second dimension of a first circulant of a first codeword corresponds to a second location in the second dimension of a second circulant of a second codeword. The method includes, in response to determining that the first location does not correspond to the second location, decoding the first and second circulant with a first decoding process. The method includes, in response to determining that the first location corresponds to the second location, decoding the first and second circulant with a second decoding process.

What is claimed is: 
     
       1. A method for decoding codewords stored in a memory unit, wherein codewords comprise at least one circulant and are stored in a first dimension of a matrix in the memory unit, and wherein each circulant in a codeword is associated with a location in a second dimension in the matrix in the memory unit, the method comprising:
 determining, by an overlap comparator on a decoder circuit, whether a first memory location in a second dimension of a first circulant of a first codeword stored in the memory unit corresponds to a second memory location in the second dimension of a second circulant of a second codeword stored in the memory unit; 
 in response to determining that the first memory location does not correspond to the second memory location, decoding, by a flipping element on the decoder circuit, the first circulant based on an odd current instant syndrome obtained from a syndrome memory unit; and 
 in response to determining that the first memory location corresponds to the second memory location, decoding, by a multiplexor on the decoder circuit, the first circulant and the second circulant based on the odd current instant syndrome and an even current instant syndrome obtained from the syndrome memory unit. 
 
     
     
       2. The method of  claim 1 , wherein determining whether the first memory location corresponds to the second memory location further comprises comparing a first address of the first memory location of the first circulant and a second address of the second memory location of the second circulant. 
     
     
       3. The method of  claim 1 , further comprising:
 retrieving a third circulant of the first codeword from a raw memory; 
 generating flips by the flipping element, in the first circulant based on an instant syndrome and the third circulant; and 
 storing the first circulant in a current memory. 
 
     
     
       4. The method of  claim 1 , further comprising:
 generating flips by the flipping element in the first circulant; 
 receiving an old instant syndrome; and 
 generating a current instant syndrome based on the old instant syndrome and the first circulant. 
 
     
     
       5. The method of  claim 1 , further comprising:
 decoding the first codeword in parallel with the second codeword, wherein the first codeword is decoded using an odd portion of the decoder circuit and the second codeword is decoded using an even portion of the decoder circuit. 
 
     
     
       6. The method of  claim 1 , further comprising:
 generating a combined current instant syndrome based on the odd current instant syndrome and the even current instant syndrome. 
 
     
     
       7. The method of  claim 1 , further comprising:
 determining if a first offset for the odd current instant syndrome corresponds to a second offset for the even current instant syndrome; and 
 in response to determining that the first offset corresponds to the second offset, generating a combined current instant syndrome based on one of the odd current instant syndrome and the even current instant syndrome. 
 
     
     
       8. The method of  claim 1 , further comprising:
 determining if the first circulant has been flipped based on a value of a flag; and 
 in response to determining that the first circulant has been flipped, retrieving a third circulant of the first codeword from a raw memory. 
 
     
     
       9. The method of  claim 1 , further comprising:
 generating a threshold value based on a value of a flag associated with the first circulant; and 
 determining whether to flip a value of the first circulant based on the threshold value. 
 
     
     
       10. The method of  claim 1 , further comprising:
 receiving the first circulant and the second circulant simultaneously from an odd portion and an even portion respectively of a memory through a data path. 
 
     
     
       11. A system for decoding codewords stored in a memory unit, wherein codewords comprise at least one circulant and are stored in a first dimension of a matrix in the memory unit, and wherein each circulant in a codeword is associated with a location in a second dimension in the matrix in the memory unit, the system comprising: the memory unit configured to store a first circulant of a first codeword and a second circulant of a second codeword; a syndrome memory unit configured to store an odd current instant syndrome and an even current instant syndrome; and a decoder circuit including: an overlap comparator configured to determine whether a first memory location in a second dimension of the first circulant of the first codeword corresponds to a second memory location in the second dimension of the second circulant of the second codeword, a flipping element configured to in response to determining that the first memory location does not correspond to the second memory location, decode the first circulant based on the odd current instant syndrome obtained, and a multiplexor configured to in response to determining that the first memory location corresponds to the second memory location, decode the first circulant and the second circulant based on the odd current instant syndrome and the even current instant syndrome obtained from the syndrome memory unit. 
     
     
       12. The system of  claim 11 , wherein the overlap comparator is further configured to, when determining whether the first memory location corresponds to the second memory location, compare a first address of the first memory location of the first circulant and a second address of the second memory location of the second circulant. 
     
     
       13. The system of  claim 11 , wherein the flipping element is further configured to:
 retrieve a third circulant of the first codeword from a raw memory; 
 generate flips in the first circulant based on an instant syndrome and the third circulant; and 
 store the first circulant in a current memory. 
 
     
     
       14. The system of  claim 11 , wherein the flipping element is further configured to:
 generate flips in the first circulant; 
 receive an old instant syndrome; and 
 generate a current instant syndrome based on the old instant syndrome and the first circulant. 
 
     
     
       15. The system of  claim 11 , wherein the decoder circuit further includes circuitry configured to:
 decode the first codeword in parallel with the second codeword, wherein the first codeword is decoded using an odd portion of the decoder circuit and the second codeword is decoded using an even portion of the decoder circuit. 
 
     
     
       16. The system of  claim 11 , wherein the multiplexor is further configured to: generate a combined current instant syndrome based on the odd current instant syndrome and the even current instant syndrome. 
     
     
       17. The system of  claim 11 , wherein the multiplexor is further configured to:
 determine if a first offset for the odd current instant syndrome corresponds to a second offset for the even current instant syndrome; and 
 in response to determining that the first offset corresponds to the second offset, generate a combined current instant syndrome based on one of the odd current instant syndrome and the even current instant syndrome. 
 
     
     
       18. The system of  claim 11 , wherein the decoder circuit further includes circuitry configured to:
 determine if the first circulant has been flipped based on a value of a flag; and 
 in response to determining that the first circulant has been flipped, retrieve a third circulant of the first codeword from a raw memory. 
 
     
     
       19. The system of  claim 11 , wherein the decoder circuit further includes circuitry configured to:
 generate a threshold value based on a value of a flag associated with the first circulant; and 
 determine whether to flip a value of the first circulant based on the threshold value. 
 
     
     
       20. The system of  claim 11 , wherein the decoder circuit further includes circuitry configured to: receive the first circulant and the second circulant simultaneously from an odd portion and an even portion respectively of the memory unit through a data path.