System and method for multi-dimensional encoding and decoding

• US 8,468,431 B2
• Filed: 06/28/2011
• Issued: 06/18/2013
• Est. Priority Date: 07/01/2010
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: DensBits Technologies Ltd. (Broadcom, Inc.)
• Inventors: Steiner, Avi, Sabbag, Erez, Segal, Avigdor, Bar, Ilan, Sterin, Eli
• Primary Examiner(s): Ton, David
• Application Number:
  US13/171,211
• Publication Number:
  US 20120005560A1
• Time in Patent Office: 721 Days
• Field of Search: 375/316, 375/240.18, 375/340, 370/464, 714/752, 714/792, 714/780, 714/794
• US Class Current: 714/780
• CPC Class Codes: G06F 11/10 Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
• CPC Class Codes: H03M 13/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/152 Bose-Chaudhuri-Hocquenghem [BCH] codes
• CPC Class Codes: H03M 13/19 Single error correction without using particular properties of the cyclic codes, e.g. Hamming codes, extended or generalised Hamming codes
• CPC Class Codes: H03M 13/23 using convolutional codes, e.g. unit memory codes
• CPC Class Codes: H03M 13/2918 with error correction codes in three or more dimensions, e.g. 3-dimensional product code where the bits are arranged in a cube
• CPC Class Codes: H03M 13/2927 Decoding strategies
• CPC Class Codes: H03M 13/293 with erasure setting
• CPC Class Codes: H03M 13/2945 using at least three error correction codes H03M13/2957 takes precedence
• CPC Class Codes: H03M 13/2948 Iterative decoding H03M13/2957 takes precedence
• CPC Class Codes: H03M 13/2957 Turbo codes and decoding
• CPC Class Codes: H03M 13/43 Majority logic or threshold decoding
• CPC Class Codes: H03M 13/6561 Parallelized implementations

Abstract

A system and method is provided for decoding a set of bits using a plurality of hypotheses, for example, each independently tested on-the-fly. Initial bit states and associated reliability metrics may be received for the set of bits. A current hypothesis may be decoded for correcting the set of bits, wherein the current hypothesis defines different bit states and associated reliability metrics for the set of bits. If decoding the current hypothesis is not successful, a subsequently ordered hypothesis may be decoded, wherein the hypotheses are ordered such that their associated reliability metric is a monotonically non-decreasing sequence. Decoding may proceed iteratively until the current hypothesis is successful.

Claims

1. A method for decoding a set of bits using a processor, the method comprising:

receiving initial bit states and associated reliability metrics for the set of bits;

decoding a current hypothesis for correcting the set of bits, wherein the current hypothesis defines different bit states and associated reliability metrics for the set of bits; and

if decoding the current hypothesis is not successful, decoding a subsequently ordered hypothesis, wherein the hypotheses are ordered such that their associated reliability metric is a monotonically non-decreasing sequence.

2. The method of claim 1 comprising generating each subsequent hypothesis after decoding the current hypothesis for on-the-fly enumeration of error correction hypotheses.

3. The method of claim 1, wherein each pair of current and subsequent hypotheses are decoded in consecutive clock cycles.

4. The method of claim 1, wherein the hypotheses are ordered from a relatively higher to a relatively lower likelihood that the associated hypotheses correct errors.

5. The method of claim 1, wherein if decoding the current hypothesis is successful, stopping decoding.

6. The method of claim 5, wherein decoding the current hypothesis is successful if the reliability metrics associated with the set of bits corrected by the hypothesis satisfies a threshold condition or is the greatest among reliability metrics of all the other hypotheses.

7. The method of claim 1, wherein the reliability metrics are values in a finite uniform grid of one or more dimensions.

8. The method of claim 7, wherein the finite uniform grid is an integer grid.

9. The method of claim 7, wherein the reliability metrics in the finite uniform grid are incremented according to a monotonic measure using a linear ordering operation.

10. The method of claim 7, wherein the reliability metric associated with each hypothesis is a sum of absolute value log-likelihood ratio (sum-|LLR|) of the bit states of each hypothesis mapped to values in the uniform field and are incremented in a monotonically increasing order.

11. The method of claim 1, wherein the different hypotheses are used to correct the set of bits for soft decoding or to correct more errors than are defined by component codes encoding the set of bits for hard decoding.

12. A system for decoding a set of bits, the system comprising:

a memory to store the set of bits; and

a processor to receive initial bit states and associated reliability metrics for the set of bits, to decode a current hypothesis for correcting the set of bits, wherein the current hypothesis defines different bit states and associated reliability metrics for the set of bits, and, if decoding the current hypothesis is not successful, to decode a subsequently ordered hypothesis, wherein the hypotheses are ordered such that their associated reliability metric is a monotonically non-decreasing sequence.

13. The system of claim 12, wherein the processor generates each subsequent hypothesis after decoding the current hypothesis for on-the-fly enumeration of error correction hypotheses.

14. The system of claim 12, wherein the processor decodes each pair of current and subsequent hypotheses in consecutive clock cycles.

15. The system of claim 12, wherein the hypotheses are ordered from a relatively higher to a relatively lower likelihood that the associated hypotheses correct errors.

16. The system of claim 12, wherein if decoding the current hypothesis is successful, the processor stops decoding.

17. The system of claim 16, wherein decoding the current hypothesis is successful if the reliability metrics associated with the set of bits corrected by the hypothesis satisfies a threshold condition or is the greatest among reliability metrics of all the other hypotheses.

18. The system of claim 12, wherein the reliability metrics are values in a finite uniform grid of one or more dimensions.

19. The system of claim 18, wherein the finite uniform grid is an integer grid.

20. The system of claim 18, wherein the processor uses a linear ordering operation to order the hypotheses such that their associated reliability metrics are ordered according to a monotonic measure.

21. The system of claim 18, wherein the reliability metric associated with each hypothesis is a sum of absolute value log-likelihood ratio (sum-|LLR|) of the bit states of each hypothesis mapped to values in the uniform field and the processor orders the hypotheses such that their associated mapped sum-|LLR| values are monotonically increasing.

22. The system of claim 12, wherein the processor uses different hypotheses to correct the set of bits for soft decoding or to correct more errors than are defined by component codes encoding the set of bits for hard decoding.