System and method for multi-dimensional decoding

• US 8,341,502 B2
• Filed: 02/28/2011
• Issued: 12/25/2012
• Est. Priority Date: 02/28/2010
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: DensBits Technologies Ltd. (Broadcom, Inc.)
• Inventors: Steiner, Avi, Weingarten, Hanan
• Primary Examiner(s): CHAUDRY, MUJTABA M
• Application Number:
  US13/036,622
• Publication Number:
  US 20110214029A1
• Time in Patent Office: 666 Days
• Field of Search: 714/774, 714/755
• US Class Current: 714/774
• CPC Class Codes: G06F 11/1012 using codes or arrangements adapted for a specific type of error G06F11/1048 takes precedence
• 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/2963 Turbo-block codes, i.e. turbo codes based on block codes, e.g. turbo decoding of product codes
• CPC Class Codes: H03M 13/451 using a set of candidate code words, e.g. ordered statistics decoding [OSD]

Abstract

A system and method for soft decoding data. A plurality of candidate error corrections may be generated to correct one or more data bits having soft bit information. Each candidate error correction may define suggested changes to the data bits and is associated with a soft bit value. The soft bit values associated the plurality of candidate error corrections may be mapped to a uniform scale, for example, a uniform finite or integer grid. The plurality of candidate error corrections may be ordered to have combined associated mapped values in a monotonically non-decreasing order. One or more of the plurality of candidate error corrections may be soft decoded in the order of the associated mapped values by a decoding operation for each candidate error correction therein with the associated non-mapped soft bit values.

Claims

1. A method for soft decoding multi-dimensional encoded data using a processor, the method comprising:

soft decoding a component code including hard bit values and soft bit information in a first dimension of multi-dimensional encoded data to generate a plurality of candidate error corrections, wherein each candidate defines a suggested change to the hard bit values and associated soft bit information for the component code;

selecting one of the plurality of candidate error corrections according to the associated soft bit information;

updating the component code by applying the selected candidate error correction to modify the hard bit values of the component code; and

iteratively repeating the steps of soft decoding, selecting and updating in one or more additional dimensions of multi-dimensional encoded data using the updated component code output generated in a dimension of a previous iteration.

2. The method of claim 1, wherein the soft bit information for the component code associated with each candidate error correction defines a probability that the component code is valid when the suggested change of the candidate is applied.

3. The method of claim 2, wherein the plurality of candidate error corrections is a sub-set of a set of all potential error corrections for the component code, which are associated with the greatest probabilities.

4. The method of claim 2, wherein the selected candidate error correction is selected that has the greatest probability.

5. The method of claim 1, wherein the selected candidate error correction is selected that has optimal soft bit information from among the plurality of candidate error corrections.

6. The method of claim 5, wherein the selected candidate error correction is selected if the optimal soft bit information is within a predetermined threshold value range.

7. The method of claim 5, wherein the selected candidate error correction is selected if the difference between the optimal soft bit information of the selected candidate error correction and a closest soft bit information to the optimal soft bit information of another candidate error correction in the plurality of candidate error corrections is within a predetermined threshold value range.

8. The method of claim 5, wherein the selected candidate error correction is selected if the ratio of the optimal soft bit information of the selected candidate error correction and a second soft bit information closest to the optimal soft bit information of another candidate error correction in the plurality of candidate error corrections is within a predetermined threshold value range.

9. The method of claim 1, comprising assigning a score to each of the pluralities of candidate error corrections according to a probability that the component code is valid when the suggested change of the candidate is applied.

10. The method of claim 9, wherein the score for each candidate error correction is a measure of the sum of absolute value log-likelihood ratios (sum-LLR) of the bits of the candidate error correction.

11. The method of claim 9 comprising incrementing or decrementing the score assigned to each candidate error correction that suggests changes that contradict changes suggested by candidate error corrections generated in the one or more additional dimensions.

12. The method of claim 1 comprising eliminating candidates in the plurality of candidate error corrections generated in the first dimension that suggest changes that contradict changes suggested by candidate error corrections generated in the one or more additional dimensions.

13. The method of claim 12, wherein the contradictory candidate error corrections generated in the one or more additional dimensions suggest re-inverting bits in the updated component code that were suggested to be inverted by one or more candidate error correction generated in the first dimension.

14. The method of claim 1 comprising early termination of said selecting, wherein if the soft bit information associated with applying a candidate error correction to the component code correspond to a greater than threshold probability that the correction is valid, selecting the candidate error correction without analyzing the soft bit information associated with the remaining candidate error corrections.

15. The method of claim 1, wherein if the soft bit information associated with applying the selected candidate error correction to the component code corresponds to a greater than threshold probability that the correction is valid, the soft bit information of the component code is modified to correspond to a maximum probability that the correction is valid.

16. The method of claim 15, wherein the soft bit information is re-set to a predetermined maximum probability value.

17. The method of claim 15, wherein the soft bit information is scaled according to a scaling function.

18. The method of claim 15, wherein if the updated component code is assigned maximum probability soft bit information in the first dimension, the updated component code is determined to be correct and bypasses further decoding in each of the one or more additional dimensions.

19. The method of claim 15, wherein the soft bit information comprises log-likelihood ratio (LLR) values of the data bits of the component code and the soft bit information is modified to maximum LLR values for each data bit of the component code.

20. The method of claim 15, wherein if no new errors are corrected in the data bits of the component code after a predetermined number of one or more consecutive decoding iterations, returning the modified soft bit information of the updated component code to the initial soft bit information.

21. The method of claim 20, wherein the modified soft bit probability of the updated component code is returned to the initial probability, but the modified hard bit values of the updated component code are retained.

22. The method of claim 21, wherein the absolute value of the log-likelihood ratios (LLRs) of the data bits of the component code are returned to the initial values, but the sign of the LLRs of the data bits of the component code are retained.

23. A system to soft decode multi-dimensional encoded data, the system comprising:

a soft decoder to soft decode a component code including hard bit values and soft bit information in a first dimension of multi-dimensional encoded data to generate a plurality of candidate error corrections, wherein each candidate defines a suggested change to the hard bit values and associated soft bit information for the component code, to select one of the plurality of candidate error corrections according to the associated soft bit information, to update the component code by applying the selected candidate error correction to modify the hard bit values of the component code, to iteratively repeat the steps of soft decoding, selecting and updating in one or more additional dimensions of multi-dimensional encoded data using the updated component code output generated in a dimension of a previous iteration.

24. The system of claim 23, wherein the soft decoder comprises multiple soft decoders, each decoding a different initial or updated version of the component code in each different one or more additional dimensions.

25. The system of claim 23 comprising a flash memory to store the multi-dimensional encoded data.

26. The system of claim 23, wherein the soft bit information for the component code associated with each candidate error correction defines a probability that the component code is valid when the suggested change of the candidate is applied.

27. The system of claim 26, wherein the plurality of candidate error corrections is a sub-set of a set of all potential error corrections for the component code, which are associated with the greatest probabilities.

28. The system of claim 26, wherein the soft decoder selects the candidate error correction from the first plurality of candidate error corrections that has the greatest probability.

29. The system of claim 23, wherein the soft decoder selects the candidate error correction from the first plurality of candidate error corrections that has optimal soft bit information.

30. The system of claim 29, wherein the soft decoder selects the candidate error correction if the optimal soft bit information is within a predetermined threshold value range.

31. The system of claim 29, wherein the soft decoder selects the candidate error correction if the difference between the optimal soft bit information of the selected candidate error correction and a closest soft bit information to the optimal soft bit information of another candidate error correction in the plurality of candidate error corrections is within a predetermined threshold value range.

32. The system of claim 29, wherein the soft decoder selects the candidate error correction if the ratio of the optimal soft bit information of the selected candidate error correction and a closest soft bit information to the optimal soft bit information of another candidate error correction in the plurality of candidate error corrections is within a predetermined threshold value range.

33. The system of claim 23, wherein the soft decoder assigns a score to each of the pluralities of candidate error corrections according to a probability that the component code is valid when the suggested change of the candidate is applied.

34. The system of claim 33, wherein the score for each candidate error correction is a measure of the sum of absolute value log-likelihood ratios (sum-LLR) of the bits of the candidate error correction.

35. The system of claim 33, wherein the soft decoder increments or decrements the score assigned for each candidate error correction that suggests changes that contradict changes suggested by candidate error corrections generated by the soft decoder in the one or more additional dimensions.

36. The system of claim 23, wherein the soft decoder eliminates candidates in the plurality of candidate error corrections generated in the first dimension that suggest changes that contradict changes suggested by candidate error corrections generated in the one or more additional dimensions.

37. The system of claim 36, wherein the contradictory candidate error corrections generated in the one or more additional dimensions suggest re-inverting bits in the updated component code that were suggested to be inverted by one or more candidate error correction generated in the first dimension.

38. The system of claim 23, wherein the soft decoder terminates said selecting before completion, wherein if the soft bit information associated with applying a candidate error correction to the component code correspond to a greater than threshold probability that the correction is valid, the soft decoder selects the candidate error correction without evaluating the soft bit information associated with the remaining candidate error corrections.

39. The system of claim 23, wherein if the soft bit information associated with applying the selected candidate error correction to the component code corresponds to a greater than threshold probability that the correction is valid, the soft decoder modifies the soft bit information of the component code to correspond to a maximum probability that the correction is valid.

40. The system of claim 39, wherein the soft decoder re-sets the soft bit information to a predetermined maximum probability value.

41. The system of claim 39, wherein the soft decoder scales the soft bit information according to a scaling function.

42. The system of claim 39, wherein if the updated component code is assigned maximum probability soft bit information in the first dimension, the soft decoder determines that updated component code is correct and bypasses further decoding in each of the one or more additional dimensions.

43. The system of claim 39, wherein the soft bit information comprises log-likelihood ratio (LLR) values of the data bits of the component code and the soft decoder modifies the soft bit information to maximum LLR values for each data bit of the component code.

44. The system of claim 39, wherein if the soft decoder corrects no new errors in the data bits of the component code after a predetermined number of one or more consecutive decoding iterations, the soft decoder returns the modified soft bit information of the updated component code to the initial soft bit information.

45. The system of claim 44, wherein the soft decoder returns the modified soft bit probability of the updated component code to the initial probability, but retains the modified hard bit values of the updated component code.

46. The system of claim 45, wherein the soft decoder returns the absolute value of the log-likelihood ratios (LLRs) of the data bits of the component code to the initial values, but retains the sign of the LLRs of the data bits of the component code.