COMPACT DECODING OF PUNCTURED BLOCK CODES
First Claim
Patent Images
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; and
(f) using H′
to decode the representation of the punctured codeword.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
22 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; and(f) using H′
to decode the representation of the punctured codeword. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
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.
-
-
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, and(ii) a processor for executing the code. - View Dependent Claims (10)
-
-
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 in 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. - View Dependent Claims (12)
-
-
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 non 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 m′
=m−
(n−
n′
) rows and n′
columns and that is derived from H by merging selected rows of H.
-
-
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; and(c) using H′
to decode the representation of the punctured codeword. - View Dependent Claims (15, 16, 17, 18)
- n′
-
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. - View Dependent Claims (20)
- n′
-
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. - View Dependent Claims (22)
-
Specification