System and method for multi-dimensional decoding

• US 8,700,970 B2
• Filed: 02/28/2011
• Issued: 04/15/2014
• 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): LAMARRE, GUY J
• Application Number:
  US13/036,796
• Publication Number:
  US 20110214039A1
• Time in Patent Office: 1,142 Days
• Field of Search: 714/755, 714/786, 714/799, 714/746, 714/797
• US Class Current: 714/755
• 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 decoding data. Multi-dimensional encoded data may be received that potentially has errors. The multi-dimensional encoded data may encode each input bit in a set of input bits multiple times in multiple different dimensions to generate encoded bits. The encoded bits may be decoded in at least one of the multiple dimensions. If one or more errors are detected in a plurality of encoded bits in the at least one of the multiple dimensions, an intersection sub-set of the encoded data may be decoded that includes data encoding the same input bits encoded by the plurality of encoded bits in at least a second dimension of the multiple dimensions. The values of the input bits by decoding the intersection sub-set may be changed.

Claims

1. A method for decoding data, the method comprising:

receiving multi-dimensional encoded data potentially having errors, wherein the multi-dimensional encoded data comprises encoded bits generated by encoding each input bit in a set of input bits multiple times in multiple different dimensions;

performing a first dimension decoding of all the encoded bits, wherein the performing of the first dimension decoding comprises marking locations of one or more errors found during the first dimension decoding, if detecting the one or more errors during the first dimension decoding, without making suggested corrections to one or more potentially erroneous encoded bits associated with the one or more errors found during the first dimension decoding;

performing a second dimension decoding of each second dimension code component that comprises at least one of the one or more potentially erroneous encoded bits associated with the one or more errors found during the first dimension decoding, while not encoding second dimension code components that do not include any one of the one or more potentially erroneous encoded bits associated with the one or more errors found during the first dimension decoding;

wherein the performing of the second dimension decoding comprises marking locations of one or more errors found during the second dimension decoding, if detecting the one or more errors during the second dimension decoding, without making suggested corrections to one or more potentially erroneous encoded bits associated with the one or more errors found during the second dimension decoding;

performing a third dimension decoding of each third dimension code component that comprises at least one of the one or more potentially erroneous encoded bits associated with the one or more errors found during the first dimension decoding, while not encoding third dimension code components that do not include any one of the one or more potentially erroneous encoded bits associated with the one or more errors found during the first dimension decoding;

wherein the performing of the third dimension decoding comprises marking locations of one or more errors found during the third dimension decoding, if detecting the one or more errors during the third dimension decoding, without making suggested corrections to one or more potentially erroneous encoded bits associated with the one or more errors found during the third dimension decoding; and

determining whether to change one or more values of the one or more potentially erroneous encoded bit associated with the one or more errors found during the first dimension decoding in response to (a) the suggested corrections to the one or more potentially erroneous encoded bits associated with the one or more errors found during the first dimension decoding;

(b) the suggested corrections to the one or more potentially erroneous encoded bits associated with the one or more errors found during the second dimension decoding; and

(c) the suggested corrections to the one or more potentially erroneous encoded bits associated with the one or more errors found during the third dimension decoding.

2. The method of claim 1, comprising changing a value of an encoded bit if the encoded bit is associated with at least two errors found during at least two dimensions of the first, second and third dimensions.

3. The method of claim 1 wherein a performing of a certain dimension encoding out of the first, second and third dimensions comprises detecting an error in an encoded bit by comparing between outcomes the certain dimension decoding of different hypotheses that differ from each other by a value of the encoded bit.

4. The method according to claim 1 wherein at least one of the first, second and third dimension decoding includes soft decoding.

5. The method according to claim 1 wherein the multi-dimensional encoded data is arranged in an array that has rows and columns and comprises multiple folded codewords, wherein each folded codeword spans along more than a single row or column of the array;

wherein the first and third dimension decoding are applied on single rows of the array; and

wherein the second dimension decoding is applied on single rows of the array.

6. The method according to claim 1 further comprising:

performing a fourth dimension decoding of each fourth dimension code component that comprises at least one of the one or more potentially erroneous encoded bits associated with the one or more errors found during the first dimension decoding, while not encoding fourth dimension code components that do not include any one of the one or more potentially erroneous encoded bits associated with the one or more errors found during the first dimension decoding;

wherein the performing of the fourth dimension decoding comprises marking locations of one or more errors found during the fourth dimension decoding, if detecting the one or more errors during the fourth dimension decoding, without making suggested corrections to one or more potentially erroneous encoded bits associated with the one or more errors found during the fourth dimension decoding;

performing a fifth dimension decoding of each fifth dimension code component that comprises at least one of the one or more potentially erroneous encoded bits associated with the one or more errors found during the first dimension decoding, while not encoding fifth dimension code components that do not include any one of the one or more potentially erroneous encoded bits associated with the one or more errors found during the first dimension decoding;

wherein the performing of the fifth dimension decoding comprises marking locations of one or more errors found during the fifth dimension decoding, if detecting the one or more errors during the fifth dimension decoding, without making suggested corrections to one or more potentially erroneous encoded bits associated with the one or more errors found during the fifth dimension decoding;

determining whether to change one or more values of the one or more potentially erroneous encoded bit associated with the one or more errors found during the first dimension decoding in response to (a) the suggested corrections to the one or more potentially erroneous encoded bits associated with the one or more errors found during the first dimension decoding;

(b) the suggested corrections to the one or more potentially erroneous encoded bits associated with the one or more errors found during the second dimension decoding;

(c) the suggested corrections to the one or more potentially erroneous encoded bits associated with the one or more errors found during the third dimension decoding;

(d) the suggested corrections to the one or more potentially erroneous encoded bits associated with the one or more errors found during the fourth dimension decoding; and

(e) the suggested corrections to the one or more potentially erroneous encoded bits associated with the one or more errors found during the fifth dimension decoding.

7. The method of claim 6, comprising changing a value of an encoded bit if the encoded bit is associated with at least three errors found during at least three dimensions of the first, second, third, fourth and fifth dimensions.

8. The method according to claim 6 wherein the multi-dimensional encoded data is arranged in an array that has rows and columns and comprises multiple folded codewords, wherein each folded codeword spans along more than a single row or column of the array;

wherein the first, third and fifth dimension decoding are applied on single rows of the array; and

wherein the second and fourth dimension decoding are applied on single rows of the array.

9. A system for decoding data, the system comprising a processor and a decoder;

wherein the processor is arranged to receive multi-dimensional encoded data potentially having errors, wherein the multi-dimensional encoded data comprises encoded bits generated by encoding each input bit in a set of input bits multiple times in multiple different dimensions; and

wherein the decoder is arranged to;

perform a first dimension decoding of all the encoded bits, wherein the a performing of the first dimension decoding comprises marking locations of one or more errors found during the first dimension decoding, if detecting the one or more errors during the first dimension decoding, without making suggested corrections to one or more potentially erroneous encoded bits associated with the one or more errors found during the first dimension decoding;

perform a second dimension decoding of each second dimension code component that comprises at least one of the one or more potentially erroneous encoded bits associated with the one or more errors found during the first dimension decoding, while not encoding second dimension code components that do not include any one of the one or more potentially erroneous encoded bits associated with the one or more errors found during the first dimension decoding;

wherein a performing of the second dimension decoding comprises marking locations of one or more errors found during the second dimension decoding, if detecting the one or more errors during the second dimension decoding, without making suggested corrections to one or more potentially erroneous encoded bits associated with the one or more errors found during the second dimension decoding;

perform a third dimension decoding of each third dimension code component that comprises at least one of the one or more potentially erroneous encoded bits associated with the one or more errors found during the first dimension decoding, while not encoding third dimension code components that do not include any one of the one or more potentially erroneous encoded bits associated with the one or more errors found during the first dimension decoding;

wherein a performing of the third dimension decoding comprises marking locations of one or more errors found during the third dimension decoding, if detecting the one or more errors during the third dimension decoding, without making suggested corrections to one or more potentially erroneous encoded bits associated with the one or more errors found during the third dimension decoding; and

determine whether to change one or more values of the one or more potentially erroneous encoded bit associated with the one or more errors found during the first dimension decoding in response to (a) the suggested corrections to the one or more potentially erroneous encoded bits associated with the one or more errors found during the first dimension decoding;

(b) the suggested corrections to the one or more potentially erroneous encoded bits associated with the one or more errors found during the second dimension decoding; and

(c) the suggested corrections to the one or more potentially erroneous encoded bits associated with the one or more errors found during the third dimension decoding.

10. The system of claim 9, wherein the decoder is arranged to change a value of an encoded bit if the encoded bit is associated with at least two errors found during at least two dimensions of the first, second and third dimensions.

11. The system of claim 9 wherein the decoder is arranged to perform a certain dimension encoding out of the first, second and third dimensions by detecting an error in an encoded bit by comparing between outcomes the certain dimension decoding of different hypotheses that differ from each other by a value of the encoded bit.

12. The system according to claim 9 wherein the decoder is arranged to perform soft decoding during at least one of the first, second and third dimension decoding.

13. The system according to claim 9 wherein the multi-dimensional encoded data is arranged in an array that has rows and columns and comprises multiple folded codewords, wherein each folded codeword spans along more than a single row or column of the array;

wherein the decoder is arranged to apply the first and third dimension decoding on single rows of the array; and

to apply the second dimension decoding on single rows of the array.

14. The system according to claim 9 wherein the decoder is further arranged to:

perform a fourth dimension decoding of each fourth dimension code component that comprises at least one of the one or more potentially erroneous encoded bits associated with the one or more errors found during the first dimension decoding, while not encoding fourth dimension code components that do not include any one of the one or more potentially erroneous encoded bits associated with the one or more errors found during the first dimension decoding;

wherein a performing of the fourth dimension decoding comprises marking locations of one or more errors found during the fourth dimension decoding, if detecting the one or more errors during the fourth dimension decoding, without making suggested corrections to one or more potentially erroneous encoded bits associated with the one or more errors found during the fourth dimension decoding;

perform a fifth dimension decoding of each fifth dimension code component that comprises at least one of the one or more potentially erroneous encoded bits associated with the one or more errors found during the first dimension decoding, while not encoding fifth dimension code components that do not include any one of the one or more potentially erroneous encoded bits associated with the one or more errors found during the first dimension decoding;

wherein a performing of the fifth dimension decoding comprises marking locations of one or more errors found during the fifth dimension decoding, if detecting the one or more errors during the fifth dimension decoding, without making suggested corrections to one or more potentially erroneous encoded bits associated with the one or more errors found during the fifth dimension decoding; and

determine whether to change one or more values of the one or more potentially erroneous encoded bit associated with the one or more errors found during the first dimension decoding in response to (a) the suggested corrections to the one or more potentially erroneous encoded bits associated with the one or more errors found during the first dimension decoding;

(b) the suggested corrections to the one or more potentially erroneous encoded bits associated with the one or more errors found during the second dimension decoding;

(c) the suggested corrections to the one or more potentially erroneous encoded bits associated with the one or more errors found during the third dimension decoding;

(d) the suggested corrections to the one or more potentially erroneous encoded bits associated with the one or more errors found during the fourth dimension decoding; and

(e) the suggested corrections to the one or more potentially erroneous encoded bits associated with the one or more errors found during the fifth dimension decoding.

15. The system of claim 14, wherein the decoder is arranged to change a value of an encoded bit if the encoded bit is associated with at least three errors found during at least three dimensions of the first, second, third, fourth and fifth dimensions.

16. The system according to claim 9 wherein the multi-dimensional encoded data is arranged in an array that has rows and columns and comprises multiple folded codewords, wherein each folded codeword spans along more than a single row or column of the array;

wherein decoder is arranged to apply the first, third and fifth dimension decoding on single rows of the array; and

to apply the second and fourth dimension decoding on single rows of the array.

17. A non-transitory computer readable medium that stores instructions that once executed by the computer cause the computer to execute the stages of:

receiving multi-dimensional encoded data potentially having errors, wherein the multi-dimensional encoded data comprises encoded bits generated by encoding each input bit in a set of input bits multiple times in multiple different dimensions;

performing a first dimension decoding of all the encoded bits, wherein the performing of the first dimension decoding comprises marking locations of one or more errors found during the first dimension decoding, if detecting the one or more errors during the first dimension decoding, without making suggested corrections to one or more potentially erroneous encoded bits associated with the one or more errors found during the first dimension decoding;

performing a second dimension decoding of each second dimension code component that comprises at least one of the one or more potentially erroneous encoded bits associated with the one or more errors found during the first dimension decoding, while not encoding second dimension code components that do not include any one of the one or more potentially erroneous encoded bits associated with the one or more errors found during the first dimension decoding;

wherein the performing of the second dimension decoding comprises marking locations of one or more errors found during the second dimension decoding, if detecting the one or more errors during the second dimension decoding, without making suggested corrections to one or more potentially erroneous encoded bits associated with the one or more errors found during the second dimension decoding;

performing a third dimension decoding of each third dimension code component that comprises at least one of the one or more potentially erroneous encoded bits associated with the one or more errors found during the first dimension decoding, while not encoding third dimension code components that do not include any one of the one or more potentially erroneous encoded bits associated with the one or more errors found during the first dimension decoding;

wherein the performing of the third dimension decoding comprises marking locations of one or more errors found during the third dimension decoding, if detecting the one or more errors during the third dimension decoding, without making suggested corrections to one or more potentially erroneous encoded bits associated with the one or more errors found during the third dimension decoding; and

determining whether to change one or more values of the one or more potentially erroneous encoded bit associated with the one or more errors found during the first dimension decoding in response to (a) the suggested corrections to the one or more potentially erroneous encoded bits associated with the one or more errors found during the first dimension decoding;

(b) the suggested corrections to the one or more potentially erroneous encoded bits associated with the one or more errors found during the second dimension decoding; and

(c) the suggested corrections to the one or more potentially erroneous encoded bits associated with the one or more errors found during the third dimension decoding.

18. The non-transitory computer readable medium of claim 17, that stores instructions for changing a value of an encoded bit if the encoded bit is associated with at least two errors found during at least two dimensions of the first, second and third dimensions.

19. The non-transitory computer readable medium of claim 17 wherein a performing of a certain dimension encoding out of the first, second and third dimensions comprises detecting an error in an encoded bit by comparing between outcomes the certain dimension decoding of different hypotheses that differ from each other by a value of the encoded bit.

20. The non-transitory computer readable medium according to claim 17 wherein at least one of the first, second and third dimension decoding includes soft decoding.

21. The non-transitory computer readable medium according to claim 17 wherein the multi-dimensional encoded data is arranged in an array that has rows and columns and comprises multiple folded codewords, wherein each folded codeword spans along more than a single row or column of the array;

wherein the first and third dimension decoding are applied on single rows of the array; and

wherein the second dimension decoding is applied on single rows of the array.

22. The non-transitory computer readable medium according to claim 17 that stores instructions for:

performing a fourth dimension decoding of each fourth dimension code component that comprises at least one of the one or more potentially erroneous encoded bits associated with the one or more errors found during the first dimension decoding, while not encoding fourth dimension code components that do not include any one of the one or more potentially erroneous encoded bits associated with the one or more errors found during the first dimension decoding;

wherein the performing of the fourth dimension decoding comprises marking locations of one or more errors found during the fourth dimension decoding, if detecting the one or more errors during the fourth dimension decoding, without making suggested corrections to one or more potentially erroneous encoded bits associated with the one or more errors found during the fourth dimension decoding;

performing a fifth dimension decoding of each fifth dimension code component that comprises at least one of the one or more potentially erroneous encoded bits associated with the one or more errors found during the first dimension decoding, while not encoding fifth dimension code components that do not include any one of the one or more potentially erroneous encoded bits associated with the one or more errors found during the first dimension decoding;

wherein the performing of the fifth dimension decoding comprises marking locations of one or more errors found during the fifth dimension decoding, if detecting the one or more errors during the fifth dimension decoding, without making suggested corrections to one or more potentially erroneous encoded bits associated with the one or more errors found during the fifth dimension decoding; and

determining whether to change one or more values of the one or more potentially erroneous encoded bit associated with the one or more errors found during the first dimension decoding in response to (a) the suggested corrections to the one or more potentially erroneous encoded bits associated with the one or more errors found during the first dimension decoding;

(b) the suggested corrections to the one or more potentially erroneous encoded bits associated with the one or more errors found during the second dimension decoding;

(c) the suggested corrections to the one or more potentially erroneous encoded bits associated with the one or more errors found during the third dimension decoding;

(d) the suggested corrections to the one or more potentially erroneous encoded bits associated with the one or more errors found during the fourth dimension decoding; and

(e) the suggested corrections to the one or more potentially erroneous encoded bits associated with the one or more errors found during the fifth dimension decoding.

23. The non-transitory computer readable medium of claim 22 that stores instructions for changing a value of an encoded bit if the encoded bit is associated with at least three errors found during at least three dimensions of the first, second, third, fourth and fifth dimensions.

24. The non-transitory computer readable medium according to claim 17 wherein the multi-dimensional encoded data is arranged in an array that has rows and columns and comprises multiple folded codewords, wherein each folded codeword spans along more than a single row or column of the array;

wherein the first, third and fifth dimension decoding are applied on single rows of the array; and

wherein the second and fourth dimension decoding are applied on single rows of the array.