COMPACT DECODING OF PUNCTURED CODES
First Claim
1. A method of storing and retrieving k information bits, comprising:
- (a) 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;
(b) storing the entire codeword in a storage medium;
(c) reading at least n′
<
n bits of a representation of the codeword from the storage medium; 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.
1 Assignment
0 Petitions
Accused Products
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′.
104 Citations
29 Claims
-
1. A method of storing and retrieving k information bits, comprising:
-
(a) 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; (b) storing the entire codeword in a storage medium; (c) reading at least n′
<
n bits of a representation of the codeword from the storage medium; 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. 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 at least n′
<
n bits of a representation of the codeword from the memory, 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.
-
-
13. 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 at least n′
<
n bits of a representation of the codeword from the first memory, 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(ii) a processor for executing the code. - View Dependent Claims (14)
-
-
15. 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 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 at least n′
<
n bits of a representation of the codeword from the memory; 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. - View Dependent Claims (16)
-
-
17. 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 at least n′
<
n bits of a representation of the codeword from the storage medium; 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. - View Dependent Claims (18, 19, 20, 21, 22, 23, 24, 25, 26, 27)
-
-
28. 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, at least n′
- <
n bits of a representation of the codeword having been read from the storage medium, 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. - View Dependent Claims (29)
- <
Specification