System and method for avoiding error mechanisms in layered iterative decoding
View Patent ↗A low-density parity check (LDPC) decoder is provided for decoding low-density parity check (LDPC) encoded data wherein the processing order of the layers of the LDPC parity check matrix are rearranged during the decode process in an attempt to avoid error mechanisms brought about by the iterative nature of the LDPC belief propagation decoding process, such as stopping sets and trapping sets.
1. A method for avoiding an error mechanism during the decoding of encoded data, the method comprising:
receiving a plurality of log-likelihood ratios (LLRs) at a decoder, each of the plurality of LLRs representing one of a plurality of bits of a codeword encoded using a parity check matrix having a plurality of layers;
performing iterative decoding of the plurality of LLRs utilizing a layered iterative decoding process following a first processing order of the plurality of layers of the parity check matrix to provide a codeword estimate of the encoded codeword until the codeword estimate is determined to be a valid codeword or until a maximum number of iterations of the iterative decoding is reached using the first processing order of the plurality of layers of the parity check matrix; and
if a maximum number of iterations of the iterative decoding is reached and the codeword estimate is not determined to be a valid codeword, performing iterative decoding of the plurality of LLRs utilizing a layered iterative decoding process following a second processing order of the plurality of layers of the parity check matrix, wherein the second processing order of the plurality of layers of the parity check matrix is a different processing order than the first processing order of layers, to provide a codeword estimate of the encoded codeword until the codeword estimate is determined to be a valid codeword or until the maximum number of iterations of the iterative decoding is reached using the second processing order of the plurality of layers of the parity check matrix.
2. The method of claim 1 , wherein the codeword is a low density parity check (LDPC) encoded codeword and the layered iterative decoding process is an LDPC decoding process.
3. The method of claim 1 , wherein receiving the LLRs further comprises receiving the LLRs from a nonvolatile memory storage module.
4. The method of claim 1 , wherein the layered iterative decoding process is a layered min-sum decoding process.
5. The method of claim 1 , wherein the layered iterative decoding process is a sum-product decoding process.
6. The method of claim 1 , wherein the error mechanism is selected from the group consisting of a stopping set and a trapping set.
7. The method of claim 1 , wherein performing iterative decoding may be performed over multiple iterations and wherein a different processing order of the plurality of layers of the parity check matrix is followed for each iteration of the layered iterative decoding process.
8. The method of claim 1 , wherein performing iterative decoding of the LLRs utilizing a layered iterative decoding process following a first processing order of the plurality of layers of the parity check matrix to provide a codeword estimate of the encoded codeword, further comprises:
performing check node processing for each layer of the parity check matrix associated with the encoded codeword following the first processing order of the plurality of layers of the parity check matrix;
performing variable node processing for each layer of the parity check matrix following the first processing order of the plurality of layers of the parity check matrix; and
performing a check of the codeword estimate of the encoded codeword to determine if the codeword estimate is a valid codeword.
9. The method of claim 1 , wherein performing iterative decoding of the LLRs utilizing a layered iterative decoding process following a second processing order of the plurality of layers of the parity check matrix to provide a codeword estimate of the encoded codeword, further comprises:
performing check node processing for each layer of the parity check matrix associated with the encoded codeword following the second processing order of the plurality of layers of the parity check matrix;
performing variable node processing for each layer of the parity check matrix following the second processing order of the plurality of layers of the parity check matrix; and
performing a check of the codeword estimate of the encoded codeword to determine if the codeword estimate is a valid codeword.
10. The method of claim 1 , where each layer is identified as one or more circulant rows in the parity check matrix associated with the encoded codeword.
11. A decoder for decoding encoded data, the encoded data comprising a plurality of log-likelihood ratios (LLRs), each of the plurality of LLRs representing one of a plurality of bits of a codeword encoded using a parity check matrix having a plurality of layers, the decoder comprising circuitry for:
performing iterative decoding of the plurality of LLRs utilizing a layered iterative decoding process following a first processing order of the plurality of layers of the parity check matrix to provide a codeword estimate of the encoded codeword until the codeword estimate is determined to be a valid codeword or until a maximum number of iterations of the iterative decoding is reached using the first processing order of the plurality of layers of the parity check matrix; and
if a maximum number of iterations of the iterative decoding is reached and the codeword estimate is not determined to be a valid codeword, performing iterative decoding of the plurality of LLRs utilizing a layered iterative decoding process following a second processing order of the plurality of layers of the parity check matrix, wherein the second processing order of the plurality of layers of the parity check matrix that is a different processing order than the first processing order of layers, to provide a codeword estimate of the encoded codeword until the codeword estimate is determined to be a valid codeword or until the maximum number of iterations of the iterative decoding is reached using the second processing order of the plurality of layers of the parity check matrix.
12. The decoder of claim 11 , wherein the codeword is a low density parity check (LDPC) encoded codeword and the layered iterative decoding process is an LDPC decoding process.
13. The decoder of claim 11 , further comprising an iteration counter to determine if the maximum number of iterations of the iterative decoding is reached.
14. The decoder of claim 11 , further comprising a layer ordering circuit for determining the first processing order and the second processing order of the plurality of layers of the parity check matrix.
15. The decoder of claim 11 , wherein the layered iterative decoding process is a layered min-sum decoding process.
16. The decoder of claim 11 , wherein the layered iterative decoding process is a layered sum-product decoding process.
17. The decoder of claim 11 , wherein the error mechanism is selected from the group consisting of a stopping set and a trapping set.
18. The decoder of claim 11 , wherein performing iterative decoding may be performed over multiple iterations and wherein the layer ordering circuit identifies a different processing order of the plurality of layers of the parity check matrix to be followed for each iteration of the layered iterative decoding process.
19. The decoder of claim 11 , wherein the circuitry for performing decoding of the LLRs utilizing a layered iterative decoding process following a first processing order of the plurality of layers of the parity check matrix to provide a codeword estimate of the encoded codeword, further comprises:
a check node processor having circuitry for performing check node processing for each layer of the parity check matrix associated with the encoded codeword following the first processing order of the plurality of layers of the parity check matrix;
a variable node processor coupled to the check node processor, the variable node processor having circuitry for performing variable node processing for each layer of the parity check matrix following the first processing order of the plurality of layers of the parity check matrix; and
a codeword estimate check processor coupled to the variable node processor, the codeword estimate check processor having circuitry for performing a check of the codeword estimate of the encoded codeword to determine if the codeword estimate is a valid codeword.
20. The decoder of claim 11 , where each layer comprises one or more rows in the parity check matrix associated with the encoded codeword.
21. An LDPC decoder for decoding low-density parity check (LDPC) encoded data, the LDPC encoded data comprising a plurality of log-likelihood ratios (LLRs), each of the plurality of LLRs representing one of a plurality of bits of an LDPC codeword encoded using a parity check matrix having a plurality of layers, the decoder comprising:
decoding circuitry for performing iterative decoding of the plurality of LLRs utilizing a layered iterative decoding process following a first processing order of the plurality of layers of the parity check matrix to provide a codeword estimate of the encoded codeword until the codeword estimate is determined to be a valid codeword or until a maximum number of iterations of the iterative decoding is reached using the first processing order of the plurality of layers of the parity check matrix; and if a maximum number of iterations of the iterative decoding is reached and the codeword estimate is not determined to be a valid codeword, performing iterative decoding of the plurality of LLRs utilizing a layered iterative decoding process following a second processing order of the plurality of layers of the parity check matrix, wherein the second processing order of the plurality of layers of the parity check matrix is a different processing order than the first processing order of layers, to provide a codeword estimate of the encoded codeword until the codeword estimate is determined to be a valid codeword or until the maximum number of iterations of the iterative decoding is reached using the second processing order of the plurality of layers of the parity check matrix; and
a layer ordering circuit coupled to the decoding circuitry, the layer ordering circuit for determining the first processing order of the plurality of layers of the parity check matrix and for determining the second processing order of the plurality of layers of the parity check matrix.