Compact decoding of punctured codes

• US 9,397,699 B2
• Filed: 09/03/2009
• Issued: 07/19/2016
• Est. Priority Date: 07/21/2009
• Status: Active Grant

• Current Assignee: Ramot at Tel Aviv University Limited (Tel Aviv University)
• Original Assignee: Ramot at Tel Aviv University Limited (Tel Aviv University)
• Inventors: Sharon, Eran, Alrod, Idan, Litsyn, Simon
• Primary Examiner(s): Torres, Joseph D
• Application Number:
  US12/553,117
• Publication Number:
  US 20110022927A1
• Time in Patent Office: 2,511 Days
• Field of Search: 714/751, 714/758, 714/781, 714/790, 714/763
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1068 in sector programmable memories, e.g. flash disk G06F11/1072 takes precedence
• CPC Class Codes: H03M 13/1105 Decoding
• CPC Class Codes: H03M 13/1157 Low-density generator matrices [LDGM]
• CPC Class Codes: H03M 13/1174 Parity-check or generator matrices built from sub-matrices representing known block codes such as, e.g. Hamming codes, e.g. generalized LDPC codes
• CPC Class Codes: H03M 13/3707 Adaptive decoding and hybrid decoding, e.g. decoding methods or techniques providing more than one decoding algorithm for one code
• CPC Class Codes: H03M 13/6306 Error control coding in combination with Automatic Repeat reQuest [ARQ] and diversity transmission, e.g. coding schemes for the multiple transmission of the same information or the transmission of incremental redundancy H03M13/3761, H03M13/3769 and H03M13/635 take precedence
• CPC Class Codes: H03M 13/6362 by puncturing
• CPC Class Codes: H03M 13/6502 Reduction of hardware complexity or efficient processing

Abstract

k information bits are encoded according to a code with which is associated a parity check matrix H that has n columns. The entire resulting codeword is stored in a storage medium. At least n′<n bits of a representation of the codeword are read from the storage medium and an attempt is made to decode only the n′ bits using a matrix H′ that has fewer columns than H. Typically, H has m=n−k rows and H′ has m−(n−n′) rows and n′ columns. If the attempt fails, one or more additional bits are read from the storage medium, if necessary, and are combined with the n′ bits, and the decoding attempt is repeated using a matrix H′″ that has more columns than H′.

Claims

1. A method of storing and retrieving k information bits, comprising:

(a) encoding the k information bits according to a code with which is associated a parity check matrix H that has n columns, thereby producing a codeword of n bits;

(b) storing the entire codeword in a storage medium;

(c) reading n′

bits of a representation of the codeword from the storage medium, wherein n′

is selected based on a punctured codeword c′ and

represents fewer than n bits; and

(d) attempting to decode only the n′

bits of the representation of the codeword using a matrix H′

that has fewer columns than H, and, in an instance in which attempting to decode only the n′

bits of the representation of the codeword using H′

fails;

reading the at least one more bit of the representation of the codeword from the storage medium and attempting to decode the n′

bits of the representation of the codeword together with the at least one more bit of the representation of the codeword.

2. The method of claim 1, wherein the code is a block code.

3. The method of claim 1, wherein H has m=n−

k rows and wherein H′

has m′

=m−

(n−

n) rows and n′

columns.

4. The method of claim 3, further comprising:

(e) deriving H′

from H.

5. The method of claim 4, wherein the deriving of H′

from H is effected by steps including performing Gaussian elimination on H.

6. The method of claim 5, wherein the Gaussian elimination is performed to set equal to zero elements 1 through m′

of the columns of H that correspond to the bits of the representation of the codeword that are not read from the storage medium, thereby producing a matrix H″

, H′

then being rows 1 through of H″

without the columns that correspond to the bits of the representation of the codeword that are not read from the storage medium.

7. The method of claim 1, further comprising:

(e) if the attempting to decode only the n′

bits of the representation of the codeword using H′

fails;

attempting to decode the n′

bits of the representation of the codeword together with the at least one more bit of the representation of the codeword, using a matrix H′

″

that has more columns than H′

.

8. The method of claim 7, wherein, if the attempting to decode only the n′

bits of the representation of the codeword using H′

fails, H′

″

is identical to H, and the attempt to decode the n′

bits of the representation of the codeword together with the at least one more bit of the representation of the codeword is an attempt to decode all n bits of the representation of the codeword using H.

9. The method of claim 7, wherein n ′

<

n−

1, and wherein, if the attempting to decode only the n′

bits of the representation of the codeword using H′

fails, H′

″

has fewer columns than H, and the attempt to decode the n′

bits of the representation of the codeword together with the at least one more bit of the representation of the codeword is an attempt to decode fewer than all n bits of the representation of the codeword using H′

″

.

10. The method of claim 1, wherein the a punctured codeword c′

includes only the k information bits of codeword C that comprises both information bits and redundancy bits.

11. A memory device, comprising:

(a) a memory; and

(b) a controller for storing information bits in the memory and for recovering the information bits from the memory, the controller including;

(i) an encoder for encoding the information bits according to a code with which is associated a parity check matrix H that has n columns, thereby producing a codeword of n bits,

(ii) circuitry for storing the entire codeword in the memory and for reading n′

bits of a representation of the codeword from the storage medium, wherein n′

is selected based on a punctured codeword c′ and

represents fewer than n bits, and

(iii) a decoder for attempting to decode only the n′

<

n bits of the representation of the codeword, the decoding being effected using a matrix H′

that has fewer columns than H, and, in an instance in which attempting to decode only the n′

bits of the representation of the codeword using H′

fails;

the circuitry is further configured for reading the at least one more bit of the representation of the codeword from the storage medium and the decoder is further configured for attempting to decode the n′

bits of the representation of the codeword together with the at least one more bit of the representation of the codeword.

12. A system comprising:

(a) a first memory; and

(b) a host of the first memory including;

(i) a second memory having stored therein code for managing the first memory by steps including;

(A) encoding information bits according to a code with which is associated a parity check matrix H that has n columns, thereby producing a codeword of n bits,

(B) storing the entire codeword in the first memory,

(C) reading n′

bits of a representation of the codeword from the storage medium, wherein n′

is selected based on a punctured codeword c′ and

represents fewer than n bits, and

(D) attempting to decode only the n′

bits of the representation of the codeword using a matrix H′

that has fewer columns than H, and, in an instance in which attempting to decode only the n′

bits of the representation of the codeword using H′

fails;

reading the at least one more bit of the representation of the codeword from the storage medium, and

(ii) a processor for executing the code.

13. The system of claim 12, wherein the code for managing the first memory also includes code for deriving H′

from H.

14. A non-transitory computer-readable storage medium having embodied thereon computer-readable code for managing a memory, the computer-readable code comprising:

(a) program code for encoding information bits according to a code with which is associated a parity check matrix H that has n columns, thereby producing a codeword of n bits;

(b) program code for storing the entire codeword in the memory;

(c) program code for reading n′

bits of a representation of the codeword from the storage medium, wherein n′

is selected based on a punctured codeword c′ and

represents fewer than n bits; and

(d) program code for attempting to decode only the n′

bits of the representation of the codeword using a matrix H′

that has fewer columns than H, and, in an instance in which attempting to decode only the n′

bits of the representation of the codeword using H′

fails;

program code for reading the at least one more bit of the representation of the codeword from the storage medium and program code for attempting to decode the n′

bits of the representation of the codeword together with the at least one more bit of the representation of the codeword.

15. The computer-readable storage medium of claim 14, wherein the computer-readable code further comprises:

(e) program code for deriving H′

from H.

16. A method of recovering k information bits that have been encoded as a codeword of n bits according to a code with which is associated a parity check matrix H that has n columns, the entire codeword having been stored in a storage medium, the method comprising:

(a) reading n′

bits of a representation of the codeword from the storage medium, wherein n′

is selected based on a punctured codeword c′ and

represents fewer than n bits; and

(b) attempting to decode only the n′

bits of the representation of the codeword using a matrix H′

that has fewer columns than H, and, in an instance in which attempting to decode only the n′

bits of the representation of the codeword using H′

fails;

reading the at least one more bit of the representation of the codeword from the storage medium and attempting to decode the n′

bits of the representation of the codeword together with the at least one more bit of the representation of the codeword.

17. The method of claim 16, wherein the code is a block code.

18. The method of claim 16, wherein H has m=n−

k rows and wherein H′

has m′

=m−

(n−

n) rows and n′

columns.

19. The method of claim 18, further comprising:

(e) deriving H′

from H.

20. The method of claim 19, wherein the deriving of H′

from His effected by steps including performing Gaussian elimination on H.

21. The method of claim 20, wherein the Gaussian elimination is performed to set equal to zero elements 1 through m′

of the columns of H that correspond to the bits of the representation of the codeword that are not read from the storage medium, thereby producing a matrix H″

, H′

then being rows 1 through m′

of H″

without the columns that correspond to the bits of the representation of the codeword that are not read from the storage medium.

22. The method of claim 16, further comprising:

(c) if the attempting to decode only the n′

bits of the representation of the codeword using H′

fails;

attempting to decode the n′

bits of the representation of the codeword together with at least one more bit of the representation of the codeword, using a matrix H′

″

that has more columns than H′

.

23. The method of claim 22, wherein, if the attempting to decode only the n′

bits of the representation of the codeword using H′

fails, H″

is identical to H, and the attempt to decode the n′

bits of the representation of the codeword together with the at least one more bit of the representation of the codeword is an attempt to decode all n bits of the representation of the codeword using H.

24. The method of claim 22, wherein n′

<

n−

1, and wherein, if the attempting to decode only the n′

bits of the representation of the codeword using H′

fails, H′

″

has fewer columns than H, and the attempt to decode the n′

bits of the representation of the codeword together with the at least one more bit of the representation of the codeword is an attempt to decode fewer than all n bits of the representation of the codeword using H′

″

.

25. A decoder for decoding a codeword of n bits, the codeword having been produced by encoding information bits according to a code with which is associated a parity check matrix that has n columns, the entire codeword having been stored in a storage medium, n′

bits of a representation of the codeword having been read from the storage medium, wherein n′

is selected based on a punctured codeword c′ and

represents fewer than n bits, the decoder comprising;

(a) a decoding module for attempting to decode only the n′

bits of the representation of the codeword using a matrix H′

that has fewer columns than H, and, in an instance in which attempting to decode only the n′

bits of the representation of the codeword using H′

fails;

reading the at least one more bit of the representation of the codeword from the storage medium and attempting to decode the n′

bits of the representation of the codeword together with the at least one more bit of the representation of the codeword.

26. The decoder of claim 25, further comprising:

(b) a feedback module for requesting at least one more bit of the representation of the codeword in case the decoding fails.