Compact decoding of punctured block codes

• US 8,375,278 B2
• Filed: 07/21/2009
• Issued: 02/12/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,342
• Publication Number:
  US 20110022922A1
• Time in Patent Office: 1,302 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/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′ is m′=m−(n−n′)×n′ and is derived by merging selected rows of H.

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;

(e) deriving, by merging selected rows of H, a matrix H′

that has m′

=m−

(n−

n′

) rows and n′

columns, wherein merging selected rows of H is terminated when further merging of the selected rows would produce a matrix H′

that fails to satisfy a predetermined criterion of sparseness; and

(f) using H′

to decode the representation of the punctured codeword.

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

3. The method of claim 1, wherein m is an even number, wherein H′

is derived by merging pairs of rows of H, wherein m′

=m/2, wherein n′

=n−

m′

, and wherein H is designed such that the pairs of rows have one'"'"'s in different columns resulting in H′

being a right regular matrix.

4. The method of claim 3, wherein H′

is derived from H by merging pairs of consecutive rows of H.

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 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, 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 m′

=m−

(n−

n′

) rows and n′

columns and that is derived from H by merging selected rows of H, wherein merging selected rows of H is terminated when further merging of the selected rows would produce a matrix H′

that fails to satisfy a predetermined criterion of sparseness and wherein H and H′

are stored in a same array within the memory.

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

=m−

(n−

n′

) rows and n′

columns, and that is derived from H by merging selected rows of H, wherein merging selected rows of H is terminated when further merging of the selected rows would produce a matrix H′

that fails to satisfy a predetermined criterion of sparseness, 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 m′

=m−

(n−

n′

) rows and n′

columns and that is derived from H by merging selected rows of H, wherein merging selected rows of H is terminated when further merging of the selected rows would produce a matrix H′

that fails to satisfy a predetermined criterion of sparseness.

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 n′

<

n bits, and

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

(b) a receiver including;

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

=m−

(n−

n′

) rows and n′

columns and that is derived from H by merging selected rows of H, wherein merging selected rows of H is terminated when further merging of the selected rows would produce a matrix H′

that fails to satisfy a predetermined criterion of sparseness.

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;

(b) deriving, by merging selected rows of H, a matrix H′

that has m′

=m−

(n−

n′

) rows and n columns, wherein merging selected rows of H is terminated when further merging of the selected rows would produce a matrix H′

that fails to satisfy a predetermined criterion of sparseness; and

(c) using H′

to decode the representation of the punctured codeword.

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

16. The method of claim 14, wherein m is an even number, wherein H′

is derived by merging pairs of rows of H, wherein m′

=m/2, and wherein n′

=n−

m′

.

17. The method of claim 16, wherein H′

is derived from H by merging pairs of consecutive rows of H.

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 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 providing a codeword of n bits, and then eliminating n-n′

selected bits from the codeword, the decoder comprising;

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

that has m′

=m−

(n−

n) rows and n′

columns and that is derived from H by merging selected rows of H, wherein merging selected rows of H is terminated when further merging of the selected rows would produce a matrix H′

that fails to satisfy a predetermined criterion of sparseness.

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 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 providing a codeword of n bits, and then eliminating n−

n′

selected bits from the codeword; and

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

that has m′

=m−

(n−

n′

) rows and n′

columns and that is derived from H by merging selected rows of H, wherein merging selected rows of H is terminated when further merging of the selected rows would produce a matrix H′

that fails to satisfy a predetermined criterion of sparseness.

22. The receiver of claim 21, further comprising:

(c) a code reduction module for deriving H′

from H.