COMPACT DECODING OF PUNCTURED BLOCK CODES

• US 20110022920A1
• Filed: 07/21/2009
• Published: 01/27/2011
• 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: Alrod, Idan, Sharon, Eran, Litsyn, Simon
• Granted Patent: US 8,516,351 B2
• Time in Patent Office: Days
• US Class Current: 714/752
• 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/152 Bose-Chaudhuri-Hocquenghem [BCH] codes
• 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 fewer than m′=m−(n−n′) rows and fewer than n′ columns.

Claims

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

(a) encoding the input bits according to a first 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; and

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

that has fewer than m′

=m−

(n−

n′

) rows and fewer than n′

columns.

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

3. The method of claim 1, further comprising:

(f) deriving H′

from H.

4. The method of claim 3, 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′

of the columns of H that correspond to the selected bits, thereby producing a matrix H″

, H′

then being selected rows of H″

without the columns that correspond to the selected bits and without at least one column that corresponds to another bit that is connected, by H, only to the selected bits.

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

and the columns of H′

.

6. 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.

7. 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.

8. 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 in 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 fewer than m′

=m−

(n−

n′

) rows and fewer than n′

columns.

9. 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, and

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

that has fewer than m′

=m−

(n−

n′

) rows and fewer than n′

columns, and

(ii) a processor for executing the code.

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

from H.

11. 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; and

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

that has fewer than m′

=m−

(n−

n′

) rows and fewer than n′

columns.

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

(f) program code for deriving H′

from H.

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 fewer than m′

=m−

(n−

n′

) rows and fewer than n columns.

14. A method of recovering k input bits that have been encoded as a codeword of n bits according to a first 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; and

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

that has fewer than m′

=m−

(n−

n′

) rows and fewer than n′

columns.

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

16. The method of claim 14, further comprising:

(c) deriving H′

from H.

17. The method of claim 16, 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′

of the columns of H that correspond to the selected bits, thereby producing a matrix H″

, H′

then being selected rows of H″

without the columns that correspond to the selected bits and without at least one column that corresponds to another bit that is connected, by H, only to the selected bits.

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

and the columns of H′

.

19. 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 decoding module for decoding the representation of the punctured codeword using a matrix H′

that has fewer than m′

=m−

(n−

n′

) rows and fewer than n′

columns.

20. The decoder of claim 19, further comprising:

(b) a code reduction module for deriving H′

from H.

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; and

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

that has fewer than m′

=m−

(n−

n′

) rows and fewer than n′

columns.

22. The receiver of claim 21, further comprising:

(c) a code reduction module for deriving H′

from H.