Compact decoding of punctured block codes

• US 8,516,352 B2
• Filed: 07/21/2009
• Issued: 08/20/2013
• 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): LAMARRE, GUY J
• Application Number:
  US12/506,327
• Publication Number:
  US 20110022921A1
• Time in Patent Office: 1,491 Days
• Field of Search: 714/755, 714/786, 714/790, 714/752
• US Class Current: 714/790
• CPC Class Codes: G06F 11/1068 in sector programmable memories, e.g. flash disk G06F11/1072 takes precedence
• CPC Class Codes: H03M 13/1111 Soft-decision decoding, e.g. by means of message passing or belief propagation algorithms
• CPC Class Codes: H03M 13/15 Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes H03M13/17 takes precedence
• CPC Class Codes: H03M 13/6362 by puncturing

Abstract

k input bits are encoded according to a code with which is associated a m×n=m+k parity check matrix H. The resulting codeword is punctured, with n′<n bits. The punctured codeword is exported to a corrupting medium such as a communication channel or a memory. A representation of the punctured codeword is imported from the corrupting medium and is decoded using a matrix H′ that is smaller than H. For example, H has at most m rows and fewer than n columns but more than n′ columns.

Claims

1. A method of porting k input bits, comprising:

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

(b) puncturing the codeword, thereby providing a punctured codeword of n′

<

n bits;

(c) exporting the punctured codeword to a corrupting medium;

(d) importing a representation of the punctured codeword from the corrupting medium;

(e) deriving a matrix H′

from H by merging pairs of rows in H, wherein the pairs of rows have one'"'"'s in different columns; and

(f) decoding the representation of the punctured codeword using the matrix H′

that has at most m rows and fewer than n′

−

columns but more than n′

columns.

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

3. The method of claim 1, wherein the puncturing includes eliminating n−

n′

selected bits from the codeword, and wherein the deriving of H′

from H is effected by steps including performing Gaussian elimination on H to set equal to zero elements 1 through m−

m″

of the columns of H that correspond to a number m″

<

n−

n′

of the selected bits, thereby producing a matrix H″

, H′

then being m−

m″

rows of H″

without the columns that correspond to the m″

of the selected bits.

4. The method of claim 3, wherein the Gaussian elimination is terminated when further Gaussian elimination would produce a matrix H′

that fails to satisfy a predetermined criterion of sparseness.

5. The method of claim 4, wherein the predetermined criterion of sparseness is that an average column degree of H′

is less than the lesser of 10 and one-quarter of a number of rows of H′

.

6. The method of claim 1, wherein the decoding includes exchanging messages between the rows of H′

and the columns of H′

.

7. The method of claim 1, wherein the corrupting medium is a transmission medium, wherein the exporting includes transmitting the punctured codeword via the transmission medium, and wherein the importing includes receiving the representation of the punctured codeword from the transmission medium.

8. The method of claim 1, wherein the corrupting medium is a storage medium, wherein the exporting includes storing the punctured codeword in the storage medium, and wherein the importing includes reading the representation of the punctured codeword from the storage medium.

9. A memory device comprising:

(a) a memory, and

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

(i) an encoder for;

(A) encoding the input bits according to a code with which is associated a parity check matrix H that has m rows and n=m+k columns, thereby producing a codeword of n bits,

(B) puncturing the codeword, thereby providing a punctured codeword of fewer than n bits, and

(ii) a decoder for decoding a representation of the punctured codeword that has been read from the memory, the decoding being effected using a matrix H′

that has at most m rows and fewer than n columns but more than n′

columns, wherein the matrix H′

is derived from H by merging pairs of rows in H and the pairs of rows have one'"'"'s in different columns and wherein H and H′

are stored in a same array within the memory.

10. 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 k input bits according to a code with which is associated a parity check matrix H that has m rows and n=m+k columns, thereby producing a codeword of n bits,

(B) puncturing the codeword, thereby providing a punctured codeword of n′

<

n bits,

(C) storing the punctured codeword in the first memory,

(D) reading a representation of the punctured codeword from the first memory,

(E) deriving a matrix H′

from H by merging pairs of rows in H, wherein the pairs of rows have one'"'"'s in different columns, and

(F) decoding the representation of the punctured codeword using the matrix H′

that has at most m rows and fewer than n columns but more than n′

columns, and

(ii) a processor for executing the code.

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

from H.

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

(a) program code for encoding k input bits according to a code with which is associated a parity check matrix H that has m rows and n=m+k columns, thereby producing a codeword of n bits;

(b) program code for puncturing the codeword, thereby providing a punctured codeword of n′

<

n bits;

(c) program code for storing the punctured codeword in a memory;

(d) program code for reading a representation of the punctured codeword from the memory;

(e) program code for deriving a matrix H′

from H by merging pairs of rows in H, wherein the pairs of rows have one'"'"'s in different columns; and

(f) program code for decoding the representation of the punctured codeword using the matrix H′

that has at most m rows and fewer than n columns but more than n′

columns.

13. A communication system comprising:

(a) a transmitter including;

(i) an encoder for;

(A) encoding k input bits according to a code with which is associated a parity check matrix H that has m rows and n=m+k columns, thereby producing a codeword of n bits, and

(B) puncturing the codeword, thereby providing a punctured codeword of fewer than n bits, and

(ii) a modulator for transmitting the punctured codeword via a communication channel as a modulated signal; and

(b) a receiver including;

(i) a demodulator for receiving the modulated signal from the communication channel and for demodulating the modulated signal, thereby providing a representation of the punctured codeword, and

(ii) a decoder for decoding the representation of the punctured codeword using a matrix H′

that has at most m rows and fewer than n columns but fewer than n′

columns, wherein the matrix H′

is derived from H by merging pairs of rows in H and wherein the pairs of rows have one'"'"'s in different columns.

14. A method of recovering k input 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 m rows and n=m+k columns and that have been exported to a corrupting medium as a punctured codeword produced by eliminating n−

n′

selected bits from the codeword, the method comprising;

(a) importing a representation of the punctured codeword from the corrupting medium;

(b) deriving a matrix H′

from H by merging pairs of rows in H, wherein the pairs of rows have one'"'"'s in different columns; and

(c) decoding the representation of the punctured codeword using the matrix H′

that has at most m rows and fewer than n columns but more than n′

columns.

15. The method of claim 14, wherein the first code is a block code.

16. The method of claim 14, wherein the deriving H′

from H is effected by steps including performing Gaussian elimination on H to set equal to zero elements 1 through m−

m″

of the columns of H that correspond to a number m″

<

n−

n′

of the selected bits, thereby producing a matrix H″

, H′

then being m−

m″

rows of H″

without the columns that correspond to the m″

of the selected bits.

17. The method of claim 16, wherein the Gaussian elimination is terminated when further Gaussian elimination would produce a matrix H′

that fails to satisfy a predetermined criterion of sparseness.

18. The method of claim 17, wherein the predetermined criterion of sparseness is that an average column degree of H′

is less than the lesser of 10 and one-quarter of a number of rows of H′

.

19. The method of claim 16, wherein the decoding includes exchanging messages between the rows of H′

and the columns of H′

.

20. A decoder for decoding a representation of a punctured codeword, the punctured codeword having been produced by eliminating n−

n′

selected bits from a codeword of n bits, the codeword having been produced by encoding k input bits according to a code with which is associated a parity check matrix H that has m rows and n=m+k columns, the decoder comprising;

(a) a code reduction module for deriving a matrix H′

from H by merging pairs of rows in H, wherein the pairs of rows have one'"'"'s in different columns; and

(b) a decoding module for decoding the representation of the punctured codeword using the matrix H′

that has at most m rows and fewer than n columns but more than n′

columns.

21. A receiver comprising:

(a) a demodulator for receiving a modulated signal from a communication channel and for demodulating the modulated signal to provide a representation of a punctured codeword that had been produced by eliminating n−

n′

selected bits from a codeword of n bits, the codeword having been produced by encoding k input bits according to a code with which is associated a parity check matrix H that has m rows and n=m+k columns;

(b) a code reduction module for deriving a matrix H′

from H by merging pairs of rows in H, wherein the pairs of rows have one'"'"'s in different columns; and

(c) a decoding module for decoding the representation of the punctured codeword using the matrix H′

that has at most m rows and fewer than n columns but more than n′

columns.