Size limited multi-dimensional decoding

• US 9,136,876 B1
• Filed: 06/13/2013
• Issued: 09/15/2015
• Est. Priority Date: 06/13/2013
• 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): Rizk, Sam
• Application Number:
  US13/917,069
• Time in Patent Office: 824 Days
• US Class Current: 1/1
• CPC Class Codes: H03M 13/152 Bose-Chaudhuri-Hocquenghem [BCH] 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/2948 Iterative decoding H03M13/2957 takes precedence
• 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]
• CPC Class Codes: H03M 13/6591 Truncation, saturation and clamping

Abstract

A system, computer readable medium and a method for multi-dimensional decoding. The method may include calculating, for each single code component of multiple code components and for each dimension of the multi-dimensional decoding, multiple first candidates and assigning a first reliability score for each first candidate; selecting, for each single code component and for each dimension, a second candidate out of the multiple first candidates in response to first reliability scores of the multiple first candidates; selecting, per dimension, multiple third candidates out of all second candidates associated with the dimension, in response to reliability information related to the second candidates associated with the dimension; selecting fourth candidates out of third candidates of all dimensions; wherein a number of the fourth candidates is smaller than a number of the third candidates of all dimensions; wherein the fourth candidates are indicative of locations of bits to be evaluated; and applying a multi-dimensional soft decoding process on the multiple code components.

Claims

1. A method for multi-dimensional decoding, the method comprises:

calculating, for each single code component of multiple code components and for each dimension of the multi-dimensional decoding, multiple first candidates and assigning a first reliability score for each first candidate;

selecting, for each single code component and for each dimension, a second candidate out of the multiple first candidates in response to first reliability scores of the multiple first candidates;

selecting, per dimension, multiple third candidates out of all second candidates associated with the dimension, in response to reliability information related to the second candidates associated with the dimension;

selecting fourth candidates out of third candidates of all dimensions;

wherein a number of the fourth candidates is smaller than a number of the third candidates of all dimensions;

wherein the fourth candidates are indicative of locations of bits to be evaluated; and

applying a multi-dimensional soft decoding process on the multiple code components.

2. The method according to claim 1, comprising selecting each second candidate as a most reliable first candidate out of the multiple first candidates.

3. The method according to claim 1, wherein the selecting of the multiple third candidates is responsive to reliability information related to second candidates associated with the dimension and to second most reliable first candidates.

4. The method according to claim 3, wherein the selecting is responsive to a difference between reliability levels of most reliable and second most reliable second candidates and reliability levels of second most reliable first candidates that are associated with the second candidates.

5. The method according to claim 1, wherein the selecting of the fourth candidates comprises evaluating multiple combinations of third candidates and rejecting at least one combination of third candidates.

6. The method according to claim 5, comprising evaluating a combination of third candidates of a certain dimension by initializing a next dimension decoding by a certain decoder state obtained by applying the combination of the third candidates of the certain dimension.

7. The method according to claim 1, comprising selecting the multiple third candidates in response to the reliability information related to the second candidates associated with the dimension and in response to third candidates number constraint.

8. The method according to claim 1, comprising selecting the fourth candidates in response to reliability scores of the third candidates.

9. The method according to claim 1, comprising selecting the fourth candidates in response to reliability scores of the third candidates and in response to reliability scores of second candidates associated with the third candidates.

10. The method according to 1, comprising selecting the fourth candidates in response to reliability information related to the third candidates and in response to fourth candidate number limitation.

11. The method according to claim 1, comprising determining that the applying of the multi-dimensional soft decoding process failed;

changing at least one number limitations related to at least one of the first, second, third and fourth candidates and repeating the stages of calculating multiple first candidates, selecting a second candidate for each single code component and for each dimension, selecting, per dimension, multiple third candidates, selecting fourth candidates and applying the multi-dimensional soft decoding process.

12. The method according to claim 1, comprising altering reliability scores related to a selected candidate out of the first, second, third and fourth candidates, after selecting the selected candidate to reflect the selecting of the selected candidate.

13. The method according to claim 12, wherein the altering comprises changing a value of reliability score by changing an absolute value of the reliability score without changing a sign of the reliability score.

14. The method according to claim 12, wherein the altering comprises changing a value of reliability score by changing a sign of the reliability score.

15. The method according to claim 12, comprising altering reliability scores related to the selected candidate in response to values of the reliability scores of the selected candidate prior to the altering.

16. The method according to claim 12, comprising resetting reliability scores related to the selected candidate.

17. The method according to claim 1 comprising rejecting candidates out of the first, second and third candidates by comparing the candidates to thresholds;

wherein the method comprises altering the thresholds.

18. A method for multi-dimensional decoding, the method comprises:

selecting candidates for soft multi-dimensional decoding of multiple code components to provide selected candidates by performing multiple iterations of a process that comprises;

calculating reliability information associated with a current set of candidates;

selecting out of the set of candidates a next set of candidates in response to the reliability information associated to the current set of candidates and candidate number constraint candidate number constraint that defines a maximal number of candidates; and

defining the next set of candidates as the current set of candidates; and

applying a multi-dimensional decoding process on the current components.

19. The method according to claim 18, wherein the reliability information of at least one current set of candidates comprises most reliable previous set candidates and second most reliable previous set candidates.

20. The method according to claim 18, comprising evaluating changes in values of bits located at the locations indicated by the fourth candidates.

21. The method according to claim 18, wherein the performing of the multiple iterations of the process comprises executing at least two of the following stages:

selecting, for each single code component and for each dimension, a second candidate out of the multiple first candidates in response to first reliability scores of the multiple first candidates;

selecting, per dimension, multiple third candidates out of all second candidates associated with the dimension, in response to reliability information related to the second candidates associated with the dimension;

selecting fourth candidates out of third candidates of all dimensions;

wherein a number of the fourth candidates is smaller than a number of the third candidates of all dimensions;

wherein the fourth candidates are indicative of locations of bits to be evaluated;

and applying a multi-dimensional soft decoding process on the multiple code components.

22. A non-transitory computer readable medium that includes instructions to be executed by a computerized system and include instructions for:

selecting candidates for soft multi-dimensional decoding of multiple code components to provide selected candidates by performing multiple iterations of a process that comprises;

calculating reliability information associated with a current set of candidates;

selecting out of the set of candidates a next set of candidates in response to the reliability information associated to the current set of candidates and candidate number constraint that defines a maximal number of candidates; and

defining the next set of candidates as the current set of candidates; and

applying a multi-dimensional decoding process on the current components.