Interleaved encoding

• US 9,584,159 B1
• Filed: 07/03/2014
• Issued: 02/28/2017
• Est. Priority Date: 07/03/2014
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Inventors: Weingarten, Hanan, Steiner, Avi
• Primary Examiner(s): Tu, Christine
• Application Number:
  US14/323,857
• Time in Patent Office: 971 Days
• Field of Search: 714/758, 714/701, 714/804, 714/745, 714/752
• US Class Current: 1/1
• CPC Class Codes: H03M 13/2703 the interleaver involving at least two directions
• CPC Class Codes: H03M 13/2903 Methods and arrangements specifically for encoding, e.g. parallel encoding of a plurality of constituent codes
• CPC Class Codes: H03M 13/2906 using block codes H03M13/2957 takes precedence
• CPC Class Codes: H03M 13/611 Specific encoding aspects, e.g. encoding by means of decoding

Abstract

A method for interleaved multi-dimensional encoding, the method may include receiving or generating a first version of a group of bits and a second version of the group of bits, wherein the first and second versions differ from each other by an arrangement of bits of the group of bits; and encoding the first and second versions of the groups of bits in an interleaved manner; wherein the encoding comprises calculating at least one codeword component of the first version by encoding a set of bits of the first version and at least a portion of a redundancy of at least one data entity of the second version and calculating at least one codeword component of the second version by encoding a set of bits of the second version and at least a portion of a redundancy of at least one data entity of the first version.

Claims

1. A method for interleaved multi-dimensional encoding, comprising:

receiving or generating a first version of a group of bits and a second version of the group of bits, wherein the first and second versions differ from each other by an arrangement of bits of the group of bits; and

encoding, by an encoder, the first and second versions of the groups of bits in an interleaved manner;

wherein the encoding comprises;

calculating at least one codeword component of the first version by encoding a set of bits of the first version and at least a portion of a redundancy of at least one data entity of the second version and

calculating at least one codeword component of the second version by encoding a set of bits of the second version and at least a portion of a redundancy of at least one data entity of the first version.

2. The method according to claim 1 wherein the encoding comprises calculating a minority of codeword components of the first version in response to at least portions of data entities of the second version and calculating a majority of codeword components of the first version regardless of the at least portions of data entities of the second version.

3. The method according to claim 1 wherein the encoding comprises calculating a majority of codeword components of the first version in response to at least portions of data entities of the second version and calculating a minority of codeword components of the first version regardless of the at least portions of data entities of the second version.

4. The method according to claim 1 wherein at least a portion of a redundancy of a certain data entity of the second version affects a calculation of only a single codeword component of the first version.

5. The method according to claim 1 comprising calculating a certain codeword component of a version of the first and second versions without taking into account a redundancy of another codeword of another version of the first and second versions.

6. The method according to claim 1 wherein at least a portion of a redundancy of a certain data entity of the second version affects a calculation of multiple codeword components of the first version.

7. The method according to claim 1 wherein one or more codeword components of the first version differ by length from one or more codeword components of the second version.

8. The method according to claim 1 wherein two or more codeword components of a same version out of the first and second versions differ by length from each other.

9. The method according to claim 1 wherein the encoding comprises:

calculating a first codeword component by encoding a first data entity that belongs to the first version;

calculating a second codeword component by encoding, before a completion of an encoding of the first version, a second data entity that belongs to the second version and at least a portion of the first codeword component;

calculating a third codeword component by encoding a third data entity that belongs to the first version and at least a portion of the second codeword component;

calculating a fourth codeword component by encoding a fourth data entity that belongs to the second version and at least a portion of the third codeword component.

10. The method according to claim 8 wherein the at least portion of the second codeword component comprises one or more second codeword component redundancy bits.

11. The method according to claim 1 wherein the encoding comprises:

calculating a first codeword component by encoding a first data entity that belongs to the first version;

calculating a second codeword component by encoding a second data entity that belongs to of the second version;

calculating a third codeword component by encoding, before a completion of an encoding of the first version, a third data entity that belongs to the first version and at least a portion of the second codeword component;

calculating a fourth codeword component by encoding a fourth data entity that belongs to the second version and at least a portion of the first codeword component.

12. The method according to claim 1 wherein the multi-dimensional encoding comprises encoding multiple (K) versions of the group of bits that correspond to K dimensions;

wherein the method further comprises jointly encoding portions of redundancies of a K'"'"'th dimension and portions of redundancies of a lower than K dimension to provide joint redundancy.

13. The method according to claim 12 wherein the joint redundancy comprises multiple joint redundancy units, wherein at least one joint redundancy unit is generated by encoding at least a portion of a K'"'"'th dimension redundancy unit and at least a portion of a (K−

q)'"'"'th redundancy portion, q being a positive integer that ranges between 1 and (K−

1).

15. The method according to claim 13 wherein the joint redundancy comprises multiple joint redundancy units, wherein at least one joint redundancy unit is generated by encoding at least a portion of a last dimension redundancy unit and at least a portion of the non-last redundancy portion.

14. A method for multi-dimensional encoding, the method comprises:

encoding, by an encoder, multiple versions of a group of bits that correspond to multiple dimensions; and

jointly encoding portions of redundancies of a last dimension of the multiple dimensions and portions of redundancies of a not-last dimension to provide joint redundancy.

16. A method for decoding an interleaved multi-dimensional codeword, the method comprises:

receiving a multi-dimensional codeword that was encoded in an interleaved manner; and

decoding, by a decoder, the multi-dimensional codeword;

wherein the multi-dimensional codeword that was encoded in an interleaved manner; and

decoding, by a decoder, the multi-dimensional codeword;

wherein the multi-dimensional codeword was calculated by receiving or generating a first version of a group of bits and a second version of the group of bits, wherein the first and second versions differ from each other by an arrangement of bits of the group of bits;

an encoding the first and second versions of the groups of bits in the interleaved manner;

wherein the encoding comprises;

calculating at least one codeword component of the first version by encoding a set of bits of the first version and at least a portion of a redundancy of at least one data entity of the second version and calculating at least one codeword component of the second version by encoding a set of bits of the second version and at least a portion of a redundancy of at least one data entity of the first version.

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

receiving or generating a first version of a group of bits and a second version of the group of bits, wherein the encoding comprises;

calculating at least one codeword component of the first version by encoding a set of bits of the first version and at least a portion of a redundancy of at least one data entity of the second version and

calculating at least one codeword component of the first version by encoding a set of bits of the first version and at least a portion of a redundancy of at least one data entity of the second version and

calculating at least one codeword component of the second version by encoding a set of bits of the second version and at least a portion of a redundancy of at least one data entity of the first version.

18. A memory controller comprising an encoder;

wherein the memory controller is arranged to receive or generate a first version of a group of bits and a second version of the group of bits, wherein the first and second versions differ from each other by an arrangement of bits of the group of bits; and

wherein the encoder is arranged to encode the first and second versions of the groups of bits in an interleaved manner;

wherein the encoding comprises;

calculating at least one codeword component of the first version by encoding a set of bits of the first version and at least a portion of a redundancy of at least one data entity of the second version and

calculating at least one codeword component of the second version by encoding a set of bits of the second version and at least a portion of a redundancy of at least one data entity of the first version.