SYSTEM AND METHOD FOR MULTI-DIMENSIONAL DECODING

• US 20110214039A1
• Filed: 02/28/2011
• Published: 09/01/2011
• 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
• Granted Patent: US 8,700,970 B2
• Time in Patent Office: Days
• US Class Current: 714/797
• 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 using a processor, the method comprising:

receiving multi-dimensional encoded data potentially having errors, wherein the multi-dimensional encoded data encodes each input bit in a set of input bits multiple times in multiple different dimensions to generate encoded bits;

decoding the encoded bits 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, decoding an intersection sub-set of the encoded data comprising data encoding the same input bits encoded by the plurality of encoded bits in at least a second dimension of the multiple dimensions; and

changing the values of said same input bits by decoding the intersection sub-set.

2. The method of claim 1, wherein said decoding comprises a hard decoding and the set of input bits comprises hard bit information and not soft bit information.

3. The method of claim 1, wherein said same plurality of encoded bits are encoded by at least one different component code in each different dimension.

4. The method of claim 1, comprising decoding an entire encoded set of input bits in at least one of the multiple dimensions and, only if no new errors are corrected by decoding the entire set after a predetermined number of one or more consecutive decoding iterations, decoding the intersection sub-set of encoded data.

5. The method of claim 4, wherein the entire encoded set of input bits are decoded in a first of the multiple dimensions and only the intersection sub-set of encoded data are decoded in the second or greater of the multiple dimensions.

6. The method of claim 4, wherein the entire encoded set of input bits is decoded by one or both decoding processes selected from the group consisting of:

majority decoding in which errors are marked in the encoded data in each of the multiple dimensions and corrected if the same errors are found in the encoded data in a majority or an above threshold number of dimensions of the multiple dimensions and limited corrections decoding in which corrections are only accepted up to a predetermined maximum number of corrections.

7. The method of claim 1, comprising marking decoded data as reliable and rejecting suggested corrections to alter the marked reliable decoded data as false corrections.

8. The method of claim 1, wherein the multiple dimensions are ordered and each second or greater dimension of the multi-dimensional encoded data encodes input bits arranged in two or more dimensions of a multi-dimensional data structure.

9. The method of claim 8, wherein the multi-dimensional data structure is a two-dimensional data array.

10. The method of claim 8, wherein the multi-dimensional data structure is a three-dimensional rectangular prism.

11. The method of claim 1, wherein the encoded data is systematic data comprising the original set of input bits being encoded and redundancy bits.

12. The method of claim 1, wherein the encoded bits in a sub-set of the multiple dimensions are decoded.

13. The method of claim 1, wherein the multi-dimensional storage structure is stored in flash memory.

14. A system for decoding data, the system comprising:

a processor to receive multi-dimensional encoded data potentially having errors, wherein the multi-dimensional encoded data encodes each input bit in a set of input bits multiple times in multiple different dimensions to generate encoded bits; and

a decoder to decode the encoded bits in at least one of the multiple dimensions, wherein if one or more errors are detected in a plurality of encoded bits in the at least one of the multiple dimensions, the decoder decodes an intersection sub-set of the encoded data comprising data encoding the same input bits encoded by the plurality of encoded bits in at least a second dimension of the multiple dimensions and wherein the decoder changes the values of said same input bits by decoding the intersection sub-set.

15. The system of claim 14 comprising multiple decoders, wherein each of the multiple decoders decodes each input bit in a different one of the multiple dimensions.

16. The system of claim 14 comprising a flash memory to store the multi-dimensional encoded data retrieved by the processor.

17. The system of claim 14, wherein the decoder is a hard decoder and the set of input bits comprises hard bit information and not soft bit information.

18. The system of claim 14, wherein the decoder decodes an entire encoded set of input bits in at least one of the multiple dimensions and, only if no new errors are corrected by decoding the entire set after a predetermined number of one or more consecutive decoding iterations, the decoder decodes the intersection sub-set of encoded data.

19. The system of claim 18, wherein the multiple dimensions are ordered and the decoder decodes the entire encoded set of input bits in a first of the multiple dimensions and decodes only the intersection sub-set of encoded data in the second or greater of the multiple dimensions.

20. The system of claim 14, wherein the decoder decodes the encoded bits in a sub-set of the multiple dimensions.

21. The system of claim 14, wherein the decoder marks decoded data as reliable and rejects suggested corrections to alter the marked reliable decoded data as false corrections.

22. The system of claim 14 comprising a multi-dimensional data structure, wherein the multiple dimensions of the multi-dimensional encoded data are ordered and each second or greater dimension of the multi-dimensional encoded data represents input bits arranged in two or more dimensions of the multi-dimensional data structure.

23. The system of claim 14, wherein the encoded data is systematic data comprising the original set of input bits being encoded and redundancy bits.