KR101722798B1 - Compact decoding of punctured codes - Google Patents

Abstract

The k input bits are encoded according to the code associated with the mxn (n = m + k) parity check matrix H. The generated code word with bits n < n is punctured. The puncturing codeword is sent to a communication medium such as a communication channel or memory. A sample of the punctured codeword is taken from the kerning medium and decoded using a matrix H 'smaller than H. For example, H 'is derived from m' = m to (n-n ') x n' and merging the selected rows of H. Alternatively, H has at most m rows and columns less than n but not equal to n '. Alternatively, H has a row smaller than m '= m - (n - n') and a column smaller than n '.

Description

[0001] COMPACT DECODING OF PUNCTURED CODES [0002]

The present invention relates to punctured codes, and more particularly to a method and apparatus for efficiently decoding puncturing codewords.

A conventional conventional error control strategy in time-varying channels is a rate based on available CSI (channel state information), also referred to as rate adaptability, . One effective way to implement such a coding strategy is to use a single code and puncture the code in a rate-compatible fashion, i.e. rate-compatible punctured code (RCPC) will be. In this manner, the transmitter punctually and systematically punctures the parity bits in the codeword, and the location of the punctured symbols is known to the receivers / receivers. Because the low-rate (base-code) decoder is compatible with other high-speed decoders, the RCPC does not require the additional complexity of rate adaptation. Also, in conjunction with an automatic repeat request (ARQ), the RCPC allows the sender to continue to send redundancies.

Let's look at the linear block code defined by the generator matrix Γ. To encode information vector b, Γ is multiplied by the right side of b to generate a codeword vector c.

c = b? (1)

Γ is associated with one or more parity check matrices H and satisfies the following matrix equation for all codeword vectors c of the code. For example, if vector satisfies equation (2), vector c is dependent on the code.

Hc = 0 (2)

In general, Γ, H, and c are defined on the Galois field GF (2), the elements of Γ, H, and c are 0 or 1, and the additional field elements are implemented as integer addition modulo 2 do.

In most cases, when a rate compatible puncturing code (RCPC) is implemented, only a fraction of the bits of the codeword c are either carried on the channel (communication scenario) or stored in the memory device (storage application). It is assumed that the location of the transmitted bits is known to both the transmitter and the receiver (of the communication system or storage device). The bit transmitted or stored in c 'is referred to as c' as a sub-codeword. c 'may also be referred to herein as "punctured code word ". The bit received (or read by the memory reading device) by the communication receiver is typically referred to as the 'noisy version' dlau of c ', hereinafter referred to as the' representation 'of c' the sub-code received by the resue of notation may still be denoted by c '.

The conventional way of decoding c providing a sample of sub-code word c 'is treated as "erasures" of puncturing bit c. During decoding, a bit is inserted into c 'so that the number of bits of c' is backed up to the total number of c, and then the code of the original matrix equation (2) is decoded while a specific value do. This procedure for decoding punctured codewords is referred to below as "erasure decoding ".

A low density parity check (LDPC) code will be described below to provide a complete example of erasure decoding.

The LDPC code is a linear binary block code, and its parity-check matrix or matrix H is low density (or sparse). 1, the LDPC parity check matrix H includes a set V of N bits (N = 13 in FIG. 1), a set C of M check nodes (M = 10 in FIG. 1) Is equivalent to a sparse bipartite "tanner graph" G = (V, C, E) with a set E of connecting edges (E = The bit code corresponds to a code word bit, and the check node corresponds to parity-check constraints on a bit. One bit node is connected to the check node by an edge, and this bit node is joined. In the matrix representation of the code on the left side of Figure 1 (matrix H in equation (2)), the edge connecting the bit node i and the check node j is a non-zero matrix at the intersection of row (row) j and column (Hereinafter referred to as a "none-zero matrix") element.

"는 "XOR"를 나타낸다.
Next, the first and last check nodes of FIG. 1 represent the equivalent rows of equation (1). sign "

Quot; indicates "XOR ".

The LDPC code may be decoded using iterative message passing decoding algorithms. These algorithms operate by exchanging messages between bit nodes and check nodes along the edge of an underline bipartite graph representing the code. The decoder is provided with an initial estimate of the code bits (based on the communication channel output or the read memory content). These initial estimates can be refined and improved by adding parity-check constraints, where the bits satisfy a valid codeword according to equation (2). This is done by exchanging information between a bit node representing a code word bit and a check node representing a parity-check restriction on a code word bit, using a message going along the graph edge.

In a iterative decoding algorithm, it is common to use a "soft" bit estimation scheme in which both bit estimation and reliability of bit estimation are obtained.

The bit estimates conveyed by a message going along a graph edge can be represented in various forms. A common measure representing the soft estimate of the bit v is equal to the log-likelihood ratio (LLR).

Here, the term "current constraints and observations" refers to various parity-check constraints that are taken into account, such as the sequence of symbols received from the communication channel corresponding to the bits participating in these parity checks, to be. The sign of LLR provides a bit estimate, for example a positive LLR corresponds to v = 0 and a negative LLR corresponds to v = 1. The magnitude of the absolute magnitude of the LLR provides the reliability of the estimate, for example, | LLR | = 0 means that the estimate can not be fully trusted, and | LLR | = +/- ∞, Bit value is known.

Returning to decoding of punctured codewords by "erasure decoding ", if H is a parity-check matrix of LLP codes, decoding is performed on a tangent graph associated with H, while LLR = 0 as initial LLR, Is assigned to all bits of the codeword (i. E., All punctured bits of c) that are not bits of word c '.

Such erasure decoding may be applied to other types of codes, such as BCH codes.

Generally, "erasure decoding" is more complex and slower to converge than normal decoding. Also typically, the code is a systematic code, which encodes an input data bit such as codeword c by appending a rendition bit to the data bit, and the punctured bit is selected from the rendition bits, It is not necessary to decode the bit. The method of directly decoding the sub-code word c ', which is generally the same as the information bits of c, and extracting the information bits has a considerable advantage.

Defintions

The method of the present invention described below is applicable to the encoding and decoding of punctured codewords in two or more different circumstances. One environment is to store data on a storage medium and retrieve data from the storage medium. Another environment is to transmit data to the transmission medium and receive data from the transmission medium. Therefore, the concepts of "storing" and "transmitting" are generalized to the concept of data "exporting", and the concepts of "retrieving" and "receiving" are concepts of "importing" Generalized. Data "store" and "transfer" are all special cases of data "send" and data "retrieve" and "receive" are both special cases of data retrieval. Quot; on "may be used herein as data" porting. &Quot;

A common example of a storage medium is a memory and a common example of a transmission medium is a communication channel. Both the storage medium and the transmission medium are examples of "corrupting" media. "Corrupt" media is a medium in which the imported data may not be the same as the transmitted data due to an error in the data sent to the medium.

As used herein, "encoding" can be understood to mean the conversion of an information vector ("b" in equation (1)) into a codeword ("c" in equation (1)). As used herein, "decoding" can be understood to mean converting a sample of code words into the original encoded information vector. The decoded which is fetched from the coercive medium is a "representation" of the codeword, but not the codeword itself, since the fetched can be corrupted (or altered) by the noise on the transmitted. Strictly speaking, a matrix H or an equivalent tanner graph, as used for decoding by message passing, is only used to reconstruct the original code word and not used to provide the original information vector, It is well known to those skilled in the art how to recover a source information vector given a codeword. Also, in the case of the organization code, the codeword is a simple connection of the original information vector and the parity bit, so that the original information vector can be easily restored. It should be understood that using a matrix to the extent that it decodes a codeword sample in the appended claims means using the matrix such that the matrix can be used to decode a sample of codewords.

It is an object of the present invention to provide a method and apparatus for efficiently decoding a punctured codeword.

According to the present invention there is provided a method of porting k input bits comprising the steps of: (a) generating a first code associated with a parity check matrix H with m rows and n (n = m + k) Encoding an input bit according to a predetermined number of bits, whereby an n-bit code word is generated; (b) puncturing the codeword so that n < n bits of punctured codeword are provided; (c) exporting the punctured codeword to a corrupting medium; (d) importing a representation of the punctured codeword from the killing medium; (e) merging selected columns of H to derive a matrix H 'with m' = m - (n - n ') row and n'columns; And (f) using H 'to decode a sample of the punctured codeword.

According to the present invention there is provided a memory device,

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

(i) Encoder -

(A) encoding an input bit according to a code associated with a parity check matrix H with m rows and n (n = m + k) columns to generate an n-bit code word,

(B) puncturing a code word to provide a punctured code word less than n;

(ii) Decoder - The decoder decodes a sample of punctured codewords read from memory, where decoding is done using a matrix H 'with m' = m - (n-n ') row and n' columns H 'is derived from H by merging the selected columns of H.

According to another embodiment of the present invention, a system is provided,

(a) a first memory; And

(b) a host of the first memory,

Wherein the host comprises: (i) a second memory in which a code for managing a first memory is stored, and (ii) a processor for executing the code,

The first memory comprising:

(A) encoding a k input bit according to a code associated with a parity check matrix H having m rows and n (n = m + k) columns,

(B) puncturing the codeword to provide a punctured codeword of n '< n,

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

(D) reading a sample of punctured codewords from a first memory,

(E) decoding a sample of the punctured codeword using matrix H 'derived from H by merging the selected columns of H with m' = m - (n - n ') rows and n' And the like.

According to another embodiment of the present invention there is provided a computer-readable storage medium having recorded thereon a computer-readable code for managing a memory,

The computer readable code comprising:

(a) program code for encoding an k input bit according to a code associated with a parity check matrix H with m rows and n (n = m + k) columns to produce an n-bit code word,

(b) program code for puncturing a codeword to provide a punctured codeword of n '< n bits,

(c) program code for storing puncturing codewords in the memory,

(d) program code for reading a specimen of punctured codewords from memory,

(e) program code for decoding a sample of punctured codewords using matrix H 'derived from H by m' = m - (n-n ') row and n' columns and merging selected columns of H .

According to another embodiment of the present invention, there is provided a communication system including (a) a transmission apparatus and (b) a reception apparatus, wherein (a) the transmission apparatus includes (i) an encoder and (ii) The receiving apparatus includes (i) a demodulator and (ii) a decoder,

(i)

(A) encoding a k input bit according to a first code associated with a parity check matrix H with m rows and n (n = m + k) columns to produce an n-bit code word,

(B) puncturing a code word to provide a punctured code word less than n,

(ii) the modulator transmits a punctured codeword as a modulated signal over a communication channel,

(i) a demodulator receives a modulated signal from a communication channel and demodulates the modulated signal to provide a sample of punctured codewords,

(ii) The decoder decodes a sample of punctured codewords using a matrix H 'derived from H by merging the selected columns of H with m' = m - (n-n ') rows and n' .

In accordance with another embodiment of the present invention, an n-bit code word is encoded according to a first code associated with a parity check matrix H with m rows and n (n = m + k) There is provided a method for recovering a k input bit sent to a killing medium as a punctured code word generated by removing a k input bit from a k-

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

(b) deriving H 'from H by merging a selected column of H with m' = m - (n-n ') row and n' columns;

(c) using H 'to decode a sample of the punctured codeword using the matrix H'.

According to another embodiment of the present invention there is provided a decoder for decoding a punctured codeword sample, wherein the punctured codeword is generated by removing nn 'selected bits from an n-bit codeword, Is generated by encoding an input bit according to a first code associated with a parity check matrix H with m rows and n (n = m + k) columns,

(a) a decoding module that decodes a sample of punctured codewords using a matrix H 'derived from H by merging selected columns of H with m' = m - (n-n ') rows and n' .

According to another embodiment of the present invention, there is provided a receiver,

(a) a demodulator that receives a modulated signal from a communication channel and provides a sample of the punctured codeword generated by demodulating the modulated signal to remove nn 'selected bits from the n-bit codeword, wherein the codeword is a k input Bits in accordance with a first code associated with a parity check matrix H with m rows and n columns (n = m + k); And

(b) a decoding module that decodes a sample of punctured codewords using a matrix H 'derived from H by merging selected columns of H with m' = m - (n-n ') rows and n' .

According to another embodiment of the present invention there is provided a method of porting k input bits comprising the steps of (a) generating a parity check matrix H with m rows and n (n = m + k) Encoding an input bit in accordance with a code associated with the code word, whereby an n-bit code word is generated; (b) puncturing the codeword so that n < n bits of punctured codeword are provided; (c) exporting the punctured codeword to a corrupting medium; (d) importing a representation of the punctured codeword from the killing medium; (e) decoding a sample of the punctured codeword using a matrix H 'having at most m rows and columns smaller than n and greater than n'.

According to another embodiment of the present invention, there is provided a memory device comprising: (a) a memory, (b) a controller for storing k input bits in the memory and recovering input bits from memory, Quot;

(i) Encoder -

(A) encoding an input bit according to a first code associated with a parity check matrix H with m rows and n (n = m + k) columns to produce an n-bit code word,

(B) puncturing a code word to provide a punctured code word less than n;

(ii) Decoder - The decoder includes decoding a sample of punctured codewords read from memory using up to m rows and a matrix H 'having a number of columns smaller than n and greater than n'.

According to another embodiment of the present invention, a system is provided,

(a) a first memory; And (b) a host in the first memory,

Wherein the host comprises: (i) a second memory in which a code for managing a first memory is stored, and (ii) a processor for executing the code,

The first memory comprising:

(A) encoding a k input bit according to a code associated with a parity check matrix H having m rows and n (n = m + k) columns,

(B) puncturing the codeword to provide a punctured codeword of n '< n,

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

(D) reading a sample of punctured codewords from a first memory,

(E) decoding a sample of the punctured codeword using a matrix H 'having at most m rows and a number of columns that is less than n and greater than n'.

According to another embodiment of the present invention there is provided a computer-readable storage medium having recorded thereon a computer-readable code for managing a memory,

The computer readable code comprising:

(a) program code for encoding an k input bit according to a first code associated with a parity check matrix H with m rows and n (n = m + k) columns to generate an n-bit code word,

(b) program code for puncturing a codeword to provide a punctured codeword of n '< n bits,

(c) program code for storing puncturing codewords in the memory,

(d) program code for reading a specimen of punctured codewords from memory,

(e) program code for decoding samples of the punctured codeword using a matrix H 'having a maximum of m rows and a number of columns less than n and greater than n'.

According to another embodiment of the present invention, there is provided a communication system including (a) a transmission apparatus and (b) a reception apparatus, wherein (a) the transmission apparatus includes (i) an encoder and (ii) The receiving apparatus includes (i) a demodulator and (ii) a decoder,

(i)

(A) encoding a k input bit according to a code associated with a parity check matrix H having m rows and n (n = m + k) columns, to generate an n-bit code word,

(B) puncturing a code word to provide a punctured code word less than n,

(ii) the modulator transmits a punctured codeword as a modulated signal over a communication channel,

(i) a demodulator receives a modulated signal from a communication channel and demodulates the modulated signal to provide a sample of punctured codewords,

(ii) The decoder decodes a sample of the punctured codeword using up to m rows and a matrix H 'having a number of columns smaller than n and greater than n'.

According to another embodiment of the present invention, a code is encoded as an n-bit code word according to a first code associated with a parity check matrix H with m rows and n (n = m + k) There is provided a method for recovering a k input bit sent to a killing medium as a punctured code word generated by removing from a word,

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

(b) decoding a sample of the punctured codeword using a matrix H 'having a maximum of m rows and a number of columns less than n and greater than n'.

According to another embodiment of the present invention there is provided a decoder for decoding a punctured codeword sample, wherein the punctured codeword is generated by removing nn 'selected bits from an n-bit codeword, Is generated by encoding an input bit according to a code associated with a parity check matrix H with m rows and n (n = m + k) columns,

(a) a decoding module that decodes a sample of punctured codewords using matrices H 'having a maximum of m rows and a number of columns less than n and greater than n'.

According to another embodiment of the present invention, there is provided a receiver,

(a) a demodulator that receives a modulated signal from a communication channel and provides a sample of the punctured codeword generated by demodulating the modulated signal to remove nn 'selected bits from the n-bit codeword, wherein the codeword is a k input Bit by encoding according to a code associated with a parity check matrix H with m rows and n (n = m + k) columns; And

(b) a decoding module that decodes a sample of the punctured codeword using a matrix H 'having at most m rows and a number of columns less than n and greater than n'.

According to another embodiment of the present invention there is provided a method of porting k input bits comprising the steps of (a) generating a parity check matrix H with m rows and n (n = m + k) Encoding an input bit in accordance with a code associated with the code word, whereby an n-bit code word is generated; (b) puncturing the codeword so that n < n bits of punctured codeword are provided; (c) exporting the punctured codeword to a corrupting medium; (d) importing a representation of the punctured codeword from the killing medium; (e) decoding a sample of the punctured codeword using a matrix H 'having a row less than m' = m - (n - n ') and a column less than n'.

According to another embodiment of the present invention, there is provided a memory device comprising: (a) a memory, (b) a controller for storing k input bits in the memory and recovering input bits from memory, Quot;

(i) Encoder -

(A) encoding an input bit according to a first code associated with a parity check matrix H with m rows and n (n = m + k) columns to produce an n-bit code word,

(B) puncturing a code word to provide a punctured code word less than n;

(ii) Decoder - The decoder decodes a sample of punctured codewords read from memory using a matrix H 'with columns less than m' = m - (n - n ') and columns less than n'; .

According to another embodiment of the present invention, a system is provided,

(a) a first memory; And (b) a host in the first memory,

Wherein the host comprises: (i) a second memory in which a code for managing a first memory is stored, and (ii) a processor for executing the code,

The first memory comprising:

(A) encoding a k input bit according to a code associated with a parity check matrix H having m rows and n (n = m + k) columns,

(B) puncturing the codeword to provide a punctured codeword of n '< n,

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

(D) reading a sample of punctured codewords from a first memory,

(E) decoding a sample of the punctured codeword using a matrix H 'having a row less than m' = m - (n - n ') and a column less than n'.

According to another embodiment of the present invention there is provided a computer-readable storage medium having recorded thereon a computer-readable code for managing a memory,

The computer readable code comprising:

(a) program code for encoding an k input bit according to a first code associated with a parity check matrix H with m rows and n (n = m + k) columns to generate an n-bit code word,

(b) program code for puncturing a codeword to provide a punctured codeword of n '< n bits,

(c) program code for storing puncturing codewords in the memory,

(d) program code for reading a specimen of punctured codewords from memory,

(e) program code for decoding a sample of the punctured codeword using a matrix H 'having a row less than m' = m - (n - n ') and a column less than n'.

According to another embodiment of the present invention, there is provided a communication system including (a) a transmission apparatus and (b) a reception apparatus, wherein (a) the transmission apparatus includes (i) an encoder and (ii) The receiving apparatus includes (i) a demodulator and (ii) a decoder,

(i)

(A) encoding a k input bit according to a code associated with a parity check matrix H having m rows and n (n = m + k) columns, to generate an n-bit code word,

(B) puncturing a code word to provide a punctured code word less than n,

(ii) the modulator transmits a punctured codeword as a modulated signal over a communication channel,

(i) a demodulator receives a modulated signal from a communication channel and demodulates the modulated signal to provide a sample of punctured codewords,

(ii) The decoder decodes a sample of the punctured codeword using a matrix H 'with columns smaller than m' = m - (n - n ') and columns smaller than n'.

According to another embodiment of the present invention, a code is encoded as an n-bit code word according to a first code associated with a parity check matrix H with m rows and n (n = m + k) There is provided a method for recovering a k input bit sent to a killing medium as a punctured code word generated by removing from a word,

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

(b) decoding a sample of the punctured codeword using a matrix H 'having a row less than m' = m - (n-n ') and a column less than n'.

According to another embodiment of the present invention there is provided a decoder for decoding a punctured codeword sample, wherein the punctured codeword is generated by removing nn 'selected bits from an n-bit codeword, Is generated by encoding an input bit according to a code associated with a parity check matrix H with m rows and n (n = m + k) columns,

(a) a decoding module that decodes a sample of the punctured codeword using a matrix H 'having a row less than m' = m - (n - n ') and a column less than n'.

According to another embodiment of the present invention, there is provided a receiver,

(a) a demodulator that receives a modulated signal from a communication channel and provides a sample of the punctured codeword generated by demodulating the modulated signal to remove nn 'selected bits from the n-bit codeword, wherein the codeword is a k input Bit by encoding according to a code associated with a parity check matrix H with m rows and n (n = m + k) columns; And

(b) a decoding module that decodes a sample of the punctured codeword using a matrix H 'having a row less than m' = m - (n - n ') and a column less than n'.

In most embodiments of the first method for porting k input bits, the input bits are encoded according to a first code associated with the mxn parity check matrix H, where n = m + k. The encoding procedure produces an n-bit code word. The n-bit codeword is punctured so that a punctured codeword of bits of n '< n is provided. The punctured codeword is sent to the calling medium. A sample of the punctured codeword is taken from the calling media. A sample of punctured codewords is decoded using H 'less than H, with H' = m '= m - (n - n') rows and n 'columns. H 'is derived from H by combining the selected rows of H.

Preferably, the first code is a block code.

Preferably, H 'is the parity check matrix of the second code and the punctured codeword is the codeword of the second code.

In most embodiments of this method, m is an even number, m '= m / 2, n' = n - m 'and H' is derived by merging the row pair of H. Preferably H ' is derived from H by incorporating a consecutive row pair of H.

Preferably, decoding includes exchanging messages between rows and columns of H ', such as LDPC. As described above, the exchange of messages between the rows and columns of the parity check matrix is equivalent to the exchange of messages between the bit nodes of the tanner graph and the check nodes.

In some embodiments of the first method, the killing medium is a transmission medium. The sending of punctured codewords involves the transmission of punctured codewords via the communication medium. Retrieving a specimen of punctured codewords involves receiving a specimen of punctured codewords from the transmission medium.

In another embodiment of the first method, the killing medium is a storage medium. The sending of the punctured codeword includes storing the punctured codeword in the storage medium. Importing a specimen of punctured codewords comprises reading a specimen of punctured codewords from a storage medium.

A memory device using a first method of topping k input bits comprises a memory and a controller. The controller stores the input bits in the memory and retrieves the input bits from the memory. The controller includes an encoder and a decoder. The encoder encodes the input bits according to matrix H and punctures the generated codewords to provide punctured codewords. The decoder decodes a sample of the punctured codeword read from memory using the matrix H '.

A system using a first method of porting k input bits comprises a host of a first memory and a first memory. The host includes a second memory and a processor. The second memory has a code for managing the first memory in accordance with the first method of porting the k input bits as applied to the storage medium. The processor executes this code. The scope of the appended claims includes a computer-readable storage medium having recorded thereon computer readable code for managing a first memory in accordance with a first method of porting k input bits.

A communication system using a first method of porting k input bits comprises a transmitter and a receiver. The transmitter includes an encoder and a modulator. The encoder encodes the input bits according to matrix H and punctures the generated codewords to provide punctured codewords. The modulator transmits the punctured codeword as a modulated signal across the communication channel. The receiver includes a demodulator and a decoder. The demodulator receives the modulated signal from the communication channel and demodulates the modulated signal to provide a sample of the punctured codeword. The decoder uses a matrix H 'to decode a sample of punctured codewords.

k input to the kerning medium as a punctured code word that is encoded as an n-bit code word according to a first code associated with the parity check matrix H and removed from the code word, In most embodiments of the first method for recovering bits, a sample of punctured codewords is a sample of punctured codewords taken from the corrupting medium. A sample of punctured codewords is decoded using a matrix H 'smaller than H, and H' has m '= m - (n - n') rows and n 'columns. H 'is derived from H by merging selected rows of H.

Preferably, the first code is a block code.

Preferably, H 'is the parity check matrix of the second code and the punctured codeword is the codeword of the second code.

In most embodiments of this method, m is an even number, m '= m / 2, n' = n - m 'and H' is derived by merging the row pair of H. Preferably H ' is derived from H by incorporating a consecutive row pair of H.

Preferably, decoding includes exchanging messages between rows and columns of H ', such as LDPC. As described above, the exchange of messages between the rows and columns of the parity check matrix is equivalent to the exchange of messages between the bit nodes of the tanner graph and the check nodes.

to decode a sample of punctured codewords generated by encoding k input bits according to the code associated with mxn = m + k parity check matrix H and removing nn 'selected bits from the codeword to provide n bits of codeword Decoder includes a decoding module that decodes a sample of the punctured codeword using a matrix H 'less than H, and H' has m '= m - (n-n') row and n 'columns. H 'is derived from H by merging selected rows of H.

In most embodiments of the decoder, m is an even number, m '= m / 2, n' = n - m ', and H' is derived by concatenating the row pair of H.

Preferably, the decoder includes a code reduction module to derive H 'from H.

The receiver includes a demodulator and a decoding module. The demodulator receives a modulated signal from the communication channel and provides a sample of the punctured codeword by demodulating the modulated signal, wherein the sample of the punctured codeword is m x n = m + k parity Is generated by encoding the k input bits according to the code associated with the check matrix H and removing nn 'selected bits from the codeword. The decoding module decodes a sample of the punctured codeword using a matrix H 'smaller than H, and H' has m '= m - (n - n') row and n 'columns. H 'is derived from H by merging selected rows of H.

In most embodiments of the receiver, m is an even number, m '= m / 2, n' = n - m ', and H' is derived by concatenating the row pair of H.

Preferably the receiver comprises a code reduction module to derive H 'from H.

In most embodiments of the second method for porting k input bits, the input bits are encoded according to the code associated with the mxn parity check matrix H, where n = m + k. The encoding procedure produces an n-bit code word. The n-bit codeword is punctured so that a punctured codeword of bits of n '< n is provided. The punctured codeword is sent to the calling medium. A sample of the punctured codeword is taken from the calling media. A sample of the punctured code word is decoded using H 'less than H, where H' has a maximum m rows and columns smaller than n and greater than nn '.

Preferably, the first code is a block code.

Preferably, H 'is the parity check matrix of the second code and the punctured codeword is the codeword of the second code.

Preferably, the second method comprises deriving H 'from H'. More preferably, the puncturing of the codeword comprises removing nn 'selected bits from the codeword, and the derivation of H' from H 'comprises removing H' corresponding to the number of bits of m ''<n-n' And performing Gaussian elimination on H so that the first m-m '' element of the column is set to zero. That is, the Gaussian erasure set sets the first element of the column of H to zero, corresponding to some bits of the code word selected for erasure. H 'is the m-m &quot; row of the generated matrix without a zero-out column. Preferably, m '' is found by continuing Gaussian elimination and terminating Gaussian elimination at a point where the generated matrix H 'does not meet a predetermined criterion for sparse. One useful criterion for sparse is that the average column degree of H 'is less than 10 and less than 1/4 of the low number of H'.

Preferably, decoding includes exchanging messages between rows and columns of H ', such as LDPC. As described above, the exchange of messages between the rows and columns of the parity check matrix is equivalent to the exchange of messages between the bit nodes of the tanner graph and the check nodes.

In some embodiments of the second method, the killing medium is a transmission medium. The sending of punctured codewords involves the transmission of punctured codewords via the communication medium. Retrieving a specimen of punctured codewords involves receiving a specimen of punctured codewords from the transmission medium.

In another embodiment of the second method, the killing medium is a storage medium. The sending of the punctured codeword includes storing the punctured codeword in the storage medium. Importing a specimen of punctured codewords comprises reading a specimen of punctured codewords from a storage medium.

A memory device using a second method of porting k input bits comprises a memory and a controller. The controller stores the input bits in the memory and retrieves the input bits from the memory. The controller includes an encoder and a decoder. The encoder encodes the input bits according to matrix H and punctures the generated codewords to provide punctured codewords. The decoder decodes a sample of the punctured codeword read from memory using the matrix H '.

A system using a second method of porting k input bits comprises a host of a first memory and a first memory. The host includes a second memory and a processor. The second memory is recorded with a code managed by the first memory according to a second method of porting k input bits as applied to the storage medium. The processor executes this code. The scope of the appended claims includes a computer-readable storage medium having recorded thereon computer readable code for managing a first memory in accordance with a first method of porting k input bits.

A communication system using a second method of porting k input bits comprises a transmitter and a receiver. The transmitter includes an encoder and a modulator. The encoder encodes the input bits according to matrix H and punctures the generated codewords to provide punctured codewords. The modulator transmits the punctured codeword as a modulated signal across the communication channel. The receiver includes a demodulator and a decoder. The demodulator receives the modulated signal from the communication channel and demodulates the modulated signal to provide a sample of the punctured codeword. The decoder uses a matrix H 'to decode a sample of punctured codewords.

k input to the kerning medium as a punctured code word that is encoded as an n-bit code word according to a first code associated with the parity check matrix H and removed from the code word, In most embodiments of the second method for recovering bits, a sample of punctured codewords is a sample of punctured codewords taken from the corrupting medium. A sample of the punctured code word is decoded using a matrix H 'that is less than H, and H' has a column that is less than n maximum m rows and n and greater than nn '.

Preferably, the first code is a block code.

Preferably, the method comprises deriving H 'from H. More preferably, the step of deriving H 'from H is performed in such a manner that the first m-m''elements of the column of H corresponding to the number of bits of m''<n-n' selected for erase are set to zero, And performing an erase operation. That is, Gaussian elimination zeroes the first element of the column of H corresponding to some bits of the code word selected for erasure. H 'is the m-m &quot; row of the generated matrix without a zero-out column. Preferably, m '' is found by continuing Gaussian elimination and terminating Gaussian elimination at a point where the generated matrix H 'does not meet a predetermined criterion for sparse. One useful criterion for sparse is that the average column degree of H 'is less than 10 and less than 1/4 of the low number of H'.

Preferably, decoding includes exchanging messages between rows and columns of H ', such as LDPC. As described above, the exchange of messages between the rows and columns of the parity check matrix is equivalent to the exchange of messages between the bit nodes of the tanner graph and the check nodes.

A decoder that decodes a sample of punctured codewords generated by removing nn 'selected bits from an n-bit codeword generated by encoding a k input bit according to a code associated with a mxn = m + k parity check matrix H, And a decoding module for decoding a sample of codewords using a matrix H 'less than H, where H' has a maximum mrow and a column smaller than n and greater than nn '.

Preferably, the decoder includes a code reduction module to derive H 'from H. More preferably, the step of deriving H 'from H is performed so that the first m-m''elements of the column of H corresponding to the number of bits m''<n-n' of the code word selected for erasure are set to zero Lt; RTI ID = 0.0 &gt; Gaussian &lt; / RTI &gt; That is, Gaussian elimination zeroes the first element of the column of H corresponding to some bits of the code word selected for erasure. H 'is the m-m &quot; row of the generated matrix without a zero-out column. Preferably, m '' is found by continuing Gaussian elimination and terminating Gaussian elimination at a point where the generated matrix H 'does not meet a predetermined criterion for sparse. One useful criterion for sparse is that the average column degree of H 'is less than 10 and less than 1/4 of the low number of H'.

The receiver includes a demodulator and a decoding module. A demodulator receives a modulated signal from a communication channel and provides a sample of the punctured codeword by demodulating the modulated signal, wherein the sample of punctured codewords is a code word of k &lt; RTI ID = 0.0 &gt; And removing nn 'selected bits from the generated n-bit code word by encoding the input bit. The decoding module decodes a sample of the punctured codeword using a matrix H 'less than H, where H' has a maximum mrow and a column less than n and greater than nn '.

Preferably the receiver comprises a code reduction module to derive H 'from H. More preferably, the step of deriving H 'from H is performed so that the first m-m''elements of the column of H corresponding to the number of bits m''<n-n' of the code word selected for erasure are set to zero Lt; RTI ID = 0.0 &gt; Gaussian &lt; / RTI &gt; That is, Gaussian elimination zeroes the first element of the column of H corresponding to some bits of the code word selected for erasure. H 'is the m-m &quot; row of the generated matrix without a zero-out column. Preferably, m '' is found by continuing Gaussian elimination and terminating Gaussian elimination at a point where the generated matrix H 'does not meet a predetermined criterion for sparse. One useful criterion for sparse is that the average column degree of H 'is less than 10 and less than 1/4 of the low number of H'.

In most embodiments of the third method for porting k input bits, the input bits are encoded according to a first code associated with the mxn parity check matrix H, where n = m + k. The encoding procedure produces an n-bit code word. The n-bit codeword is punctured so that a punctured codeword of bits of n '< n is provided. The punctured codeword is sent to the calling medium. A sample of the punctured codeword is taken from the calling media. A sample of the punctured code word is decoded using H 'less than H, where H' has a row less than m '= m - (n - n') and a column less than n '.

Preferably, the first code is a block code.

Preferably, H 'is the parity check matrix of the second code and the punctured codeword is the codeword of the second code.

Preferably, the third method comprises deriving H 'from H. More preferably, the puncturing of the codeword comprises removing nn 'selected bits from the codeword, and the derivation of H' from H 'comprises removing the first m' elements of the column of H corresponding to the number of bits of the codeword selected for erasure And performing Gaussian elimination on the H phase so as to set to zero. H 'is the selected row of the generator matrix with no column corresponding to the other bits connected to only the bits selected by H, and no zero out column.

Preferably, decoding includes exchanging messages between rows and columns of H ', such as LDPC. As described above, the exchange of messages between the rows and columns of the parity check matrix is equivalent to the exchange of messages between the bit nodes of the tanner graph and the check nodes.

In some embodiments of the third method, the killing medium is a transmission medium. The sending of punctured codewords involves the transmission of punctured codewords via the communication medium. Retrieving a specimen of punctured codewords involves receiving a specimen of punctured codewords from the transmission medium.

In another embodiment of the third method, the killing medium is a storage medium. The sending of the punctured codeword includes storing the punctured codeword in the storage medium. Importing a specimen of punctured codewords comprises reading a specimen of punctured codewords from a storage medium.

A memory device using a third method of porting k input bits comprises a memory and a controller. The controller stores the input bits in the memory and retrieves the input bits from the memory. The controller includes an encoder and a decoder. The encoder encodes the input bits according to matrix H and punctures the generated codewords to provide punctured codewords. The decoder decodes a sample of the punctured codeword read from memory using the matrix H '.

A system using a third method of porting k input bits comprises a host of a first memory and a first memory. The host includes a second memory and a processor. The second memory has a code for managing the first memory in accordance with a third method of porting k input bits as applied to the storage medium. The processor executes this code. The scope of the appended claims includes a computer readable storage medium having computer readable code recorded thereon for managing a first memory in accordance with a third method of porting k input bits.

A communication system using a third method of porting k input bits comprises a transmitter and a receiver. The transmitter includes an encoder and a modulator. The encoder encodes the input bits according to matrix H and punctures the generated codewords to provide punctured codewords. The modulator transmits the punctured codeword as a modulated signal across the communication channel. The receiver includes a demodulator and a decoder. The demodulator receives the modulated signal from the communication channel and demodulates the modulated signal to provide a sample of the punctured codeword. The decoder uses a matrix H 'to decode a sample of punctured codewords.

k input to the kerning medium as a punctured code word that is encoded as an n-bit code word according to a first code associated with the parity check matrix H and removed from the code word, In most embodiments of the third method for recovering bits, a sample of the punctured codeword is fetched from the killing medium. A sample of the punctured codeword is decoded using a matrix H 'smaller than H, and H' has a column that is smaller than a smaller row n 'of m' = m - (n - n ').

Preferably, the first code is a block code.

Preferably H 'is the parity check matrix of the second code and the puncturing code is the codeword of the second code.

Preferably, the method comprises deriving H 'from H. More preferably, deriving H 'from H comprises removing selected bits of n-n' from the codeword, wherein the derivation of H 'to H' comprises deleting H-columns corresponding to the bits of the selected codeword And performing a Gaussian erase on the H phase so as to set the first m ' H 'is the selected row of the generator matrix with no zero-out column and no more than one column corresponding to the other bits connected to only the bits selected by H.

Preferably, decoding includes exchanging messages between rows and columns of H ', such as LDPC. As described above, the exchange of messages between the rows and columns of the parity check matrix is equivalent to the exchange of messages between the bit nodes of the tanner graph and the check nodes.

A decoder that decodes a sample of punctured codewords generated by removing nn 'selected bits from an n-bit codeword generated by encoding a k input bit according to a code associated with a mxn = m + k parity check matrix H, A decoding module for decoding a sample of codewords using a matrix H 'less than H, and H' has a column that is smaller than row n 'that is less than m' = m - (n - n ').

Preferably, the decoder includes a code reduction module to derive H 'from H. More preferably, deriving H 'from H comprises performing Gaussian erasure on H so that the first m' element of the column of H corresponding to the bits of the code word selected for erasure is set to zero. H 'is the selected row of the generator matrix with no zero-out column and no more than one column corresponding to the other bits connected to only the bits selected by H.

The receiver includes a demodulator and a decoding module. A demodulator receives a modulated signal from a communication channel and provides a sample of the punctured codeword by demodulating the modulated signal, wherein the sample of punctured codewords is a code word of k &lt; RTI ID = 0.0 &gt; And removing nn 'selected bits from the generated n-bit code word by encoding the input bit. The decoding module decodes a sample of the punctured codeword using a matrix H 'smaller than H, and H' has a column smaller than row n 'that is smaller than m' = m - (n - n ').

Preferably the receiver comprises a code reduction module to derive H 'from H. More preferably, deriving H 'from H comprises performing Gaussian erasure on H so that the first m' element of the column of H corresponding to the bits of the code word selected for erasure is set to zero. H 'is the selected row of the generator matrix with no zero-out column and no more than one column corresponding to the other bits connected to only the bits selected by H.

According to the present invention, a method and apparatus capable of efficiently decoding a punctured codeword can be provided.

Brief Description of the Drawings Figure 1 shows how an LDPC code can be represented as either a sparse parity check matrix or a tanner graph.
Figure 2 illustrates the conversion of a parity check matrix H to a small scale matrix H 'for decoding punctured codewords.
FIGS. 3 and 4 are simplified schematic high-level block diagrams of a decoder that efficiently decodes a sample of punctured codewords. FIG.
5 is a high-level schematic block diagram of a flash memory device whose controller includes the decoder of FIG. 3 or the decoder of FIG. 4;
6 is a detailed view of Fig.
Figure 7 is a high-level schematic block diagram of a memory system in which most of the functionality of the controller of Figure 5 is emulated by software.
FIG. 8 is a high-level schematic block of a communication system in which the receiver includes the decoder of FIG. 3 or the decoder of FIG. 4;
Figure 9 shows the context of a third variant of the inventive method;
10 is a tanner graph showing the conversion from H to H 'according to a third variant of the invention.

The theory and operation of efficient decoding of punctured codewords will now be described with reference to the accompanying drawings.

The system of H has m × n, ie, H has m rows and n columns. H is the parity check matrix of code C, and the course suggests that c is of length n (i.e., c has n elements). The puncturing codeword c 'is derived from c by eliminating any of the predefined coordinates of c. The length of c 'is n'. Of course n '<n. The set of all punctured codewords is the code itself labeled C '. Preferably, the information bits of the original code C are not punctured, so that the puncturing code C 'has the same size as C (i.e., the same number of codewords) but has a small redundancy bit.

Given H, c ', n, m and n', the reduced matrix code H 'is computed. If c is a code word satisfying equation (2), then the punctured sub-codeword c' .

H'c '= 0 (3)

The matrix H 'made as follows is less than H (fewer rows and / or columns), so decoding of c' according to equation (3) is easier and less effective than applying erasure decoding for equation (2) Complex.

The order m x n of a given H, the length of a given c ', the order m' x n 'of the matrix H' is computed, where m '= m- (n-n').

For all columns associated with the punctured bits of c, H 'aims to get all zeros in the selected m' row of H, e.g., the first m 'row of H, with a Gaussian elimination algorithm Gaussian elimination algorithm. After this goal is achieved, the first m 'row of the matrix H''modified by H''represents the reduced code, and the punctured bits do not participate in the code because they are multiplied by zero in all test equations .

Thus, the scaled code can be represented by taking only the n 'column of H''associated with the first m' row of H '' and the unperforated bit (called the punch bit). H 'is zero in the first m' row of H '' and is the first m 'row of H''that does not have a column of H''corresponding to the bit punched. For example, n = 4096 and bits 4000, 4010, 4020, 4030 and 4040 of c are punctured (n '= 4091) and the column of H''in the first m' row of H ' 4010, 4020, 4030, and 4040, and H 'is the first m' row of H '' having no columns 4000, 4010, 4020, 4030,

For example, consider parity check matrix H with code having the form shown in FIG. In this case, the submatrix associated with the perforated bit in the lower portion of the matrix and the upper portion of the matrix has the same structure, so that the upper half of the matrix is replaced by the upper sum (modulo 2) Generates a first m 'row associated with the bit and a matrix H''with all zeros in the column. H and H &quot; all span the same linear subspace (span), since H and H &quot; only perform a row operation to generate H &quot; from H, Matrix. H 'is derived from H''by erasing except for the first m' row of H '' and the first n 'column of H'', resulting in (m-m') n ' And becomes a parity check matrix.

Also in this embodiment, the matrix H 'is derived to the minimum number of row operations (in this case one operation per row) applied to each row. Thus, the number of 1's in each row of H 'is at most twice the number of 1's in the row of H's. If H is less than H ', it can be considered as a sparse. Thus, if the original code is an LDPC code, the reduced code H 'is considered LDPC code, which can be efficiently decoded by generating a tanner graph of the code and performing a message passing algorithm.

In most implementations, the number of row operations performed on H is limited to protect certain attributes, such as sparse.

3 is a high-level block diagram that schematically illustrates a decoder 60 for implementing efficient puncturing decoding as described above. The puncturing decoder 60 includes a code reduction module 62 and a decoder module 64. The input to the decoder 60 is a sample of the code matrix H and a sub-code word c '(in which noise and corruption may occur). The reduced code matrix H 'is computed (preferably once in a code reduction module 62) and then stored in a local volatile or nonvolatile memory (not shown), followed by a sample of the sub-code word c' And supplied to the decoder module 64 together. The output of the decoder module 64 is a decoded codeword, which contains the information content of the original sub-codeword c '. This information is the same as the information content of the original codeword c.

4 is a high-level block diagram schematically illustrating another decoder 80 for implementing efficient puncturing decoding as described above. In addition to the code reduction module 82 and the decoder module 84, the decoder 80 includes a non-volatile memory 86 for storing the code matrix H. [ The input to the decoder 80 is information such as a sample of the sub-code word c '(which may cause noise and error) and an index of the bits of c punctured to produce c', which generates H ' And informs the column code reduction module 82 which column of the hash is output to the first m 'row of H. Code collapse module 82 stores H 'in the memory 86 or local non-volatile memory (not shown) for calculating H' as needed and preferably storing H 'in the local area. At the decoder 60, H 'is provided to the decoder module 84 along with the sub-codeword c'. The output of the decoder module 84 is a decoded codeword.

The code reduction modules 62, 82 and decoder modules 64, 84 may be implemented in hardware, firmware, software, or a combination thereof, as will be apparent to those skilled in the art.

5 is a high-level schematic block diagram of a flash memory device. The memory cell array 1 including a plurality of memory cells M arranged in a matrix form includes a column control circuit 2, a row control circuit 3, a C-source control circuit 4 and a CP- ) Control circuit 5. [0033] The column control circuit 2 reads the data stored in the memory cell M and determines the state of the memory cell M during the write operation and controls the potential level of the bit line BL for write or write inhibition Is connected to the bit line (BL) of the memory cell array (1). The row control circuit 3 is connected to a word line WL to select one of the word lines WL and to apply a read voltage and to write to the bit line potential level controlled by the column control circuit 2 And applies an erase voltage combined with the voltage of the p-type region where the memory cell M is formed. The C-source control circuit 4 controls the common source line connected to the memory cell M. [ The CP-well control circuit 5 controls the cp-well voltage.

The data stored in the memory cell M is read by the column control circuit 2, output to the external I / O line via the I / O line, and output to the data input / output buffer 6. The program data stored in the memory cell is input to the data input / output buffer 6 via the external I / O line and transferred to the column control circuit 2. The external I / O line is connected to the controller 20.

The command data for controlling the flash memory device is input to a command interface connected to an external control line connected to the controller 20. [ The command data notifies the flash memory which operation is requested. The input command is input to the state machine 8 which controls the column control circuit 2, the row control circuit 3, the c-source control circuit 4, the cp-well control circuit 5 and the data input / output buffer 6, . The state machine 8 can output state data of the flash memory such as READY / BUSY or PASS / FAIL.

The controller 20 is connected to or connectable to a host system such as a personal computer, a digital camera, or a PDA. The host initiates commands such as reading data from the memory array 1 or storing data in the memory array, and provides or receives such data. The controller 20 converts these instructions into instruction signals that can be interpreted or executed by the instruction circuit 7. The controller 20 typically includes a buffer memory for user data that is read from or written to the memory array. Of course, it is the current trend to integrate the memory array and the control circuitry of the device together on one or more integrated circuit chips. The memory device may be implemented as part of the host system and may be included in a removable memory card in a mating socket of the host system. Such a card may be included with a complete memory device or controller and a memory array with associated peripheral circuitry or may be provided on a separate card.

FIG. 6 is a partial enlarged view of the diagram, in which the controller 20 includes an encoder 52 for encoding user data received from a host as one or more punctured codewords, An R / W circuit 54 for instructing the instruction circuit 7 to store the punctured code word in the memory cell array 1 and to retrieve the stored punctured code word from the memory cell array 1, and a decoder 30, May be the decoder 60 of FIG. 3 or the decoder 80 of FIG. 4 and may decode a sample of punctured codewords as retrieved by the circuit 54.

Conventionally, RCPC has been considered to be applicable only to time-varying communication channels. Memory, such as flash memory, that gradually becomes unstable over time is also a time-varying corrupting medium. The controller 20 first uses a relatively large number of puncturing bits and gradually reduces the number of memory cell arrays 1 as the stability of the memory cell array 1 deteriorates over time.

7 is a high-level block diagram of the system 100 in which most of the functions of the controller 20 are enabled by software. The system 100 includes a processor 102 and four memory devices, namely, a RAM 104, a boot ROM 106, a mass storage device (hard disk 108), and a modified flash memory device of FIG. (112), all communicating via the common bus (114). The difference between the flash memory device of Figure 5 and the flash memory device 112 is that the controller of the flash memory device 112 functions only as an interface to the bus 114 and the remaining functions of the controller 20 of Figure 5 A user application executed by the processor 102 and emulated by the flash memory drive code 110 stored in the mass storage device 108 and executed by the processor 102, Interfacing and managing the flash memory of the flash memory device 112. FIG. In addition to the conventional function of the flash memory drive code, the drive code 110 is also related to the puncturing encoding and decoding of the code word stored in the memory cell array 1 and read from the memory cell array 1, Emulates the function of the controller 20 of FIG. The drive code 110 is typically included in the operating system of the system 100, but may be an independent code.

Components of the system 100 other than the flash memory device 112 form the host 120 of the flash memory device 112. The mass storage device 108 is an example of a computer-readable storage medium including a computer-readable driver for efficient punctured decoding as described above. Another example of such a computer readable medium includes a read only memory such as a CD containing such code.

Although the methods and decoders described herein are primarily described for use in data storage systems, the method of the present invention is applicable to communication systems, particularly those that rely on wave propagation through noisy transmission media System.

8 is a high-level block circuit diagram of a communication system 200 that includes a transmitter 210, a channel 203, The transmitter 210 includes an encoder 201 and a modulator 202. The receiver 212 includes a demodulator 204 and a decoder 206 and the decoder 206 may be one of the decoders 60 of Fig. 3 or the decoder 80 of Fig. Encoder 201 receives the message and generates a corresponding puncturing codeword. The modulator 202 digitally modulates the resulting punctured codeword, for example BPSK, QPSK or multi-valued QAM, and delivers the resulting modulated signal to the receiver 212 over channel 203. At receiver 212, demodulator 204 receives a modulated signal from channel 203 and digitally demodulates the received modulated signal, e.g., BPSK, QPSK, or multi-valued QAM. As described above, the decoder 206 decodes the final sample of the punctured codeword of the original.

In a variation of the above method for efficient decoding of punctured codewords, H 'is derived from H by merging groups of rows of H rather than Gaussian elimination. For each group, the number of 1's in each column associated with the punctured bits must be even, and the modulo 2 addition of the rows of the group adds 0 to their 1's.

A special case of middle is to merge the pairs of rows of H. m must be a positive number in this particular case. The resulting matrix of H 'has m / 2 rows and nm / 2 columns. The parity check matrix of FIG. 2 is an example of a matrix H, from which H 'can be derived by merging pairs of rows. In this case, m = 2m '. The merging is performed by modulo 2 addition of a pair (row 1 and row m '+ 1), pair (row 2 and row m' + 2), ..., pair (row m 'and row 2m'). The matrix H is also preferably designed so that the merged rows have their one in the other column (except for the column associated with the puncturing bits). In this way, if all rows of H have the same number of ones, then all rows of H 'have the same number of ones. This characteristic is desirable for iterative decoding, and a correct regular LDPC can be designed to obtain a near optimal error correction capability. This organizational structure also contributes to efficient decoder hardware design.

In this variation, H and H 'may be stored in the same array in non-volatile memory 86 of decoder 80. For each row of H, only the index of the column with row 1 is stored. If H is a regular matrix (matrix with row roots having the same number of ones), the index is simply stored in succession and the code reduction module 82 knows that a new row of H starts after a predetermined number of indexes have been sent Storage can be much simpler. If the H merged row is designed to have one of them in a different column, then H 'does not need to store H' because H 'is then generated by the merge row of H. The index of the "1" element of the merged row of H is the index of the "1"

If H 'is derived by concatenating the successive rows of H (merging of the first and second rows of H, merging of the third and fourth rows of H, ..., of the m-1 and m rows of H Decoder 80 is implemented either in un-punctured decoding (of a sample of n-element unperforated codewords) with H or un-punctured decoding (of a sample of n'-element unperforated codewords) using H ' It is possible.

A second variant of the above-described method is directed to a method of potential disadvantages. For matrix H 'with m' rows, full Gaussian elimination may produce a matrix H 'with sparse that is insufficient for use in decoding by message passing. Experimental experience shows that a useful criterion for sparse is the average column rank of H ', for example, the average number of 1's per column of H', less than 10 and also the number of rows of H 'divided by 4 It should be small. For good LDPC codes, the average column rank of the parity check matrix is between 3 and 4. Gaussian removal from H to H 'is carried out until the removal of the other column of H produces a non-sparse matrix H' according to this criterion. Next, during decoding, conventional erasure decoding is used to control the puncturing bits for which the corresponding column of H has not been removed.

One example of a third variant of the above method is shown in Fig. 9, which shows a bipartite graph representing LDPC codes divided into a plurality of sections in the following manner.

1) a set V of bit nodes into t divided sub-sets V ₁ , V ₂ , ..., V _t ) (therefore V = V ₁ U V ₂ U ... U V _t )

2) forming a respective subset of a check node Ci to include all the check nodes connected to a bit node as a stand-in for the sub-SEB V _i V _i of the bit nodes

3) Form a subset C _J of outer check nodes that contains all the check nodes that are not in any previously generated check node subset, for example C _J = C \ (C ₁ UC ₂ U ... UC _t )

4) Divide graph G into t sub-graphs G ₁ , G ₂ , .., G _t such that Gi = (V _i , C _i , E ⁱ ), where E _i is the bit node in V _i and C _i Lt; / RTI &gt; is the set of edges connected between the check nodes in the block. The edge is connected to set CJ by E _J (E _J = E \ (E ₁ U E ₂ U ... U E _t )).

In this embodiment, the graph G is processed by iteration of the decoding phase according to a specific message passing schedule, and exchanges messages along the graph edge in the following order in each decoding phase.

· I = 1 to t

1. _{Send a} message from the check node c? _{C J} to the bit node v? V _i along the edge in E _J , as shown by the R _CJVi message in FIG. As shown in Figure 9 in the R _CiVi messages, check node _i is set from c∈C messages to the bit node v∈V _i to zero. The initial bit estimate is set for all bits v? V _i , as shown in the Pvi message in FIG. The R _CJVi message is the result of activating the decoder for another t-1 sub-graph G _k , k ≠ i before this step. If the other sub-graphs have not yet been processed, their corresponding message Q _vicJ in Fig. 9 is set to an initial bit estimate as read from memory or received from the communication channel. The initial (LLR) estimate of the puncturing bits is equally zero.

2. It performs one or more iterations by sending a message from the bit node in V _i to the check node in C _i along the edge in E _i based on the schedule. This is shown in Fig. 9 as Q _vici and R _civi messages.

3. Transmit the message from the bit node in V _i to the check node in C _J along the edge in E _J. This is shown in Fig. 9 as Q _vicJ message.

Decoding continues until the decoder converges to a valid codeword while satisfying all parity-check constraints, or until the maximum number of allowed decapsulation phases is reached. The stopping criteria for message passing in each sub-graph are similar, repeating until the maximum number of branches or allowed iterations is reached when all parity-check constraints in this sub-graph are satisfied. Typically, the maximum allowed number of iterations can vary from one sub-graph to another or from activation of one decoder to the other.

In some implementations in this regard, the check nodes in C _J are connected only to the bit nodes corresponding to the puncturing bits. The exchange of messages in the separated sub-graph G _i is performed using a matrix H 'which ignores the bits associated with only punctured bits by H with puncturing bits. FIG. 10 is a tanner graph showing how H 'is derived from H. FIG. The numbered circle is a bit node. The numbered rectangle is a check node. The tanner graph of Fig. 10 represents the concept of the third variant and need not be used in the context of Fig. The matrix H corresponding to the tenor graph of FIG. 10 is as follows.

(4)

(4)

Bits 7, 8, and 9 are punctured. H 'is derived by omitting the modulo-2 addition of rows 1 and 4, rows 2 and 5, rows 3 and 6, and the last row and last four columns.

(5)

(5)

A method for ideal punctured decoding, a limited embodiment of an apparatus and system using this method has been described. It will, however, be evident that various modifications, alterations, and other applications of the method, apparatus, and system may be made within the scope of the present invention.

Claims (44)

A method for porting k input bits,
(a) encoding an input bit according to a first code associated with a parity check matrix H with m rows and n (n = m + k) columns, whereby an n-bit code word is generated;
(b) puncturing the codeword so that n &lt; n bits of punctured codeword are provided;
(c) exporting the punctured codeword to a corrupting medium;
(d) importing a representation of the punctured codeword from the killing medium;
(e) deriving a matrix H 'from the matrix H by merging pairs of rows of the matrix H, the pair of rows having a 1 in different columns; And
(f) decoding a sample of the punctured codeword using the matrix H 'having at most m rows and a number of columns less than n and not equal to n', where H 'is the parity check of the second code Matrix, and the punctured codeword is a codeword of the second code -
Gt; k &lt; / RTI &gt; input bits.
The method according to claim 1,
Wherein the first code is a block code. &Lt; RTI ID = 0.0 &gt; 11. &lt; / RTI &gt;
The method according to claim 1,
Decoding includes exchanging a message between a node of a tanner graph corresponding to a row of H 'and a node of a tanner graph corresponding to a column of H' )How to.
The method according to claim 1,
Wherein the calling media is a transmission medium,
Wherein said transmitting step comprises transmitting a punctured codeword through said transmission medium and said fetching step comprises receiving a punctured codeword sample from said transmission medium. How to port.
The method according to claim 1,
Wherein the calling media is a storage medium,
Wherein the step of sending includes storing punctured codewords in the storage medium and the fetching step comprises reading a sample of punctured codewords from the storage medium. lt; / RTI &gt;
delete The method according to claim 1,
H 'has more than n' columns,
The puncturing step includes removing n-n ' selected bits from the codeword,
The step of deriving H 'from H
performing Gaussian elimination on H such that the elements 1 through m-m &quot; of the H columns corresponding to m &quot;< n-n selected bits are set equal to zero M &quot; of H ''' where there is no column corresponding to a selected bit of m '&apos;, so that a matrix H &quot; )How to.
8. The method of claim 7,
Wherein the Gaussian cancellation is terminated when another Gaussian cancellation produces a matrix H 'that does not satisfy a predetermined criterion of sparseness.
9. The method of claim 8,
Wherein the predetermined criterion of the sparse is to port the k input bits where the average column degree of H 'is less than a small of one-fourth of the number of rows of 10 and H'.
The method according to claim 1,
H 'has a row smaller than m' = m- (n-n ') and a column smaller than n'
The puncturing step includes removing nn 'selection bits from the codeword,
The step of deriving H 'from H comprises performing Gaussian elimination on H such that elements 1 through m' of the columns of H corresponding to the selected bit are set equal to zero, H &quot; is generated, and H 'is a selected row of H''without at least one column corresponding to another bit connected by H, with no column corresponding to the selected bit and only the selected bit. / RTI &gt;
(a) a memory, and
(b) a controller for storing k input bits in the memory and recovering input bits from the memory,
The controller comprising:
(i) Encoder -
(A) encoding an input bit according to a first code associated with a parity check matrix H with m rows and n (n = m + k) columns to produce an n-bit code word,
(B) puncturing a codeword to provide a punctured codeword of n 'bits less than n; And
(ii) Decoder - the decoder decodes a sample of the punctured codeword read from the memory, wherein the decoding is performed using a matrix H 'having a maximum of m rows and a number of columns less than n and not equal to n' , H 'is the parity check matrix of the second code, the punctured codeword is the codeword of the second code, the matrix H' is derived from the matrix H by merging the pair of rows of the matrix H, Characterized in that the pair of rows has one in the different columns and the H and H 'are stored in the same array in the memory
Memory device.
(a) a first memory; And
(b) a host of the first memory,
The host,
(i) a second memory in which a code for managing a first memory is stored, and
(ii) a processor for executing the code,
The first memory comprising:
(A) encoding a k input bit according to a first code associated with a parity check matrix H with m rows and n (n = m + k) columns to produce an n-bit code word,
(B) puncturing the codeword to provide a punctured codeword of n '< n,
(C) storing a punctured codeword in a first memory,
(D) reading a sample of punctured codewords from a first memory,
(E) deriving a matrix H 'from the matrix H by merging a pair of rows of the matrix H, the pair of rows having a 1 in different columns; And
(F) decoding a sample of punctured codewords using the matrix H 'with a maximum of m rows and a number of columns less than n and not equal to n', where H 'is the parity check of the second code Matrix and a punctured codeword is a code word of a second code.
delete 13. The method of claim 12,
H 'has more than n' columns,
The puncturing may include removing n-n ' selected bits from the codeword,
Wherein deriving H 'from H comprises:
performing a Gaussian erasure on H such that elements 1 through m-m &quot; of the columns of H corresponding to m &quot;< n-n selected bits are set equal to zero, The matrix H &quot; is generated, and H 'becomes the m-m &quot; low of H''without a column corresponding to the selected bit of m''.
15. The method of claim 14,
Wherein said Gaussian cancellation is terminated when another Gaussian cancellation produces a matrix H 'that does not satisfy a predetermined criterion of sparseness.
16. The method of claim 15,
Wherein the predetermined criterion of the sparse is that the number of average columns of H 'is less than a small of one-fourth of the number of rows of 10 and H'.
13. The method of claim 12,
H 'has a row smaller than m' = m- (n-n ') and a column smaller than n'
The puncturing may include removing nn 'selection bits from the codeword,
The step of deriving H 'from H comprises performing Gaussian elimination on H such that elements 1 through m' of the columns of H corresponding to the selected bit are set equal to zero, H &quot; is generated, and H 'is the selected row of H''without at least one column corresponding to the other bits connected by H, with no column corresponding to the selected bit and only the selected bit.
A computer-readable storage medium having recorded therein computer readable code for managing a memory,
The computer readable code comprising:
(a) program code for encoding an k input bit according to a first code associated with a parity check matrix H with m rows and n (n = m + k) columns to generate an n-bit code word,
(b) program code for puncturing a codeword to provide a punctured codeword of n '< n bits,
(c) program code for storing puncturing codewords in the memory,
(d) program code for reading a specimen of punctured codewords from memory,
(e) program code for deriving a matrix H 'from the matrix H by merging a pair of rows of the matrix H, the pair of rows having a 1 in different columns, and
(f) a program code for decoding a sample of a punctured codeword using a matrix H 'having at most m rows and a number of columns less than n and not equal to n', where H 'is a parity check Matrix and the punctured code word is a code word of a second code. &Lt; Desc / Clms Page number 13 &gt;
delete 19. The method of claim 18,
H 'has more than n' columns,
Puncturing includes removing n-n ' selected bits from the codeword,
The program code for deriving H 'from H
and program code for performing Gaussian elimination on H such that elements 1 through m-m &quot; of columns of H corresponding to m &quot;< n-n selected bits are set equal to zero, Wherein the matrix H &quot; is generated, and H 'is the m-m &quot; low of H''without a column corresponding to the selected bit of m''. A computer-readable storage medium having recorded thereon.
21. The method of claim 20,
Wherein said Gaussian cancellation is terminated when another Gaussian cancellation produces a matrix H 'that does not satisfy a predetermined criterion of sparseness. Storage medium.
22. The method of claim 21,
Characterized in that the predetermined criterion of the sparse is that the number of average columns of H 'is smaller than a small of 1/4 of the number of rows of H ' and the computer readable code for managing the memory Readable storage medium.
19. The method of claim 18,
H 'has a row smaller than m' = m- (n-n ') and a column smaller than n'
Puncturing includes removing nn 'selection bits from the codeword,
The program code for deriving H 'from H comprises program code for performing Gaussian elimination on H such that elements 1 through m' of the columns of H corresponding to the selected bit are set equal to zero, H &quot; is a selected row of H '' without at least one column corresponding to the other bits connected by H, with no column corresponding to the selected bit and only the selected bit. Readable storage medium having recorded thereon computer readable code for managing a computer readable medium.
A communication system comprising (a) a transmission device and (b) a receiving device,
(a) the transmission apparatus comprises (i) an encoder and (ii) a modulator,
(b) the receiving device comprises (i) a demodulator and (ii) a decoder,
(i)
(A) encoding a k input bit according to a first code associated with a parity check matrix H with m rows and n (n = m + k) columns to produce an n-bit code word,
(B) puncturing the codeword to provide a punctured codeword of n 'bits less than n,
(ii) the modulator transmits a punctured codeword as a modulated signal over a communication channel,
(i) a demodulator receives a modulated signal from a communication channel and demodulates the modulated signal to provide a sample of punctured codewords,
(ii) the decoder decodes a sample of the punctured codeword using a matrix H 'having a maximum of m rows and a number of columns less than n and not equal to n', where H 'is the parity check matrix of the second code, Wherein the punctured code word is a code word of a second code and derives the matrix H 'from the matrix H by merging the pair of rows of the matrix H, and wherein the pair of rows has one in the different columns Communication system.
bit code word according to a first code associated with a parity check matrix H with m rows and n (n = m + k) columns, where n 'is less than n and nn' CLAIMS 1. A method for recovering a k input bit sent to a calling medium as a punctured code word generated by removing from a word,
(a) importing a representation of a punctured codeword from a corrupting medium;
(b) deriving a matrix H 'from the matrix H by merging a pair of rows of the matrix H, the pair of rows having a 1 in different columns;
(c) decoding a sample of the punctured codeword using a matrix H 'having at most m rows and a number of columns less than n and not equal to n', where H 'is a parity check matrix of the second code And the punctured code word is a code word of a second code. &Lt; Desc / Clms Page number 21 &gt;
26. The method of claim 25,
Wherein the first code is a block code.
26. The method of claim 25,
Wherein said decoding includes exchanging messages between a node of a tanner graph corresponding to a row of H 'and a node of a tanner graph corresponding to a column of H' Way.
delete 26. The method of claim 25,
H 'has more than n' columns,
Puncturing includes removing n-n ' selected bits from the codeword,
The step of deriving H 'from H
performing a Gaussian erasure on H such that elements 1 through m-m &quot; of the columns of H corresponding to m &quot;< n-n selected bits are set equal to zero, The matrix H &quot; is generated, and H 'becomes the m-m &quot; low of H''without the column corresponding to the selected bit of m''.
30. The method of claim 29,
Wherein the Gaussian cancellation is terminated when another Gaussian cancellation generates a matrix H 'that does not satisfy a predetermined criterion of sparseness.
31. The method of claim 30,
Wherein the predetermined criterion of the sparse is that the number of average columns of H 'is less than a small of one-fourth of the number of rows of 10 and H'.
26. The method of claim 25,
H 'has a row smaller than m' = m- (n-n ') and a column smaller than n'
Puncturing includes removing nn 'selection bits from the codeword,
The step of deriving H 'from H comprises performing Gaussian elimination on H such that elements 1 through m' of the columns of H corresponding to the selected bit are set equal to zero, H &quot; is generated, and H 'is a selected row of H''without at least one column corresponding to another bit connected by H, with no column corresponding to the selected bit and only the selected bit. &Lt; / RTI &gt;
A decoder for decoding a punctured codeword sample, wherein the punctured codeword is generated by removing nn 'selected bits from an n-bit codeword , where n' is less than n, k input bits according to a first code associated with a parity check matrix H having m rows and n columns (n = m + k) columns,
(a) a decoding module that decodes a sample of punctured codewords using a matrix H 'having at most m rows and a number of columns that are less than n and not equal to n', where H 'is a parity check The punctured code word is a code word of a second code and the matrix H 'is derived from the matrix H by merging the pair of rows of the matrix H, and the pair of rows has a 1 in the different columns -
And a decoder for decoding the punctured codeword samples.
delete 34. The method of claim 33,
H 'has more than n' columns,
Puncturing includes removing n-n ' selected bits from the codeword,
Deriving H 'from H,
performing a Gaussian elimination on H such that elements 1 through m-m &quot; of columns of H corresponding to m &quot;< n-n selected bits are set equal to zero, H &quot; is generated, and H ' is m-m &quot; low of H &quot; with no column corresponding to the selected bit of m &quot;.
36. The method of claim 35,
Wherein the Gaussian cancellation is terminated when another Gaussian cancellation produces a matrix H 'that does not satisfy a predetermined criterion of sparseness. &Lt; Desc / Clms Page number 21 &gt;
37. The method of claim 36,
Wherein the predetermined criterion of the sparse is that the number of average columns of H 'is less than a small of one-fourth of the number of rows of 10 and H'.
34. The method of claim 33,
H 'has a row smaller than m' = m- (n-n ') and a column smaller than n'
Puncturing includes removing nn 'selection bits from the codeword,
Deriving H 'from H comprises performing Gaussian elimination on H such that elements 1 through m' of the H columns corresponding to the selected bit are set equal to zero, such that matrix H 'Quot; is generated, and H 'is a selected row of H''without at least one column corresponding to the other bits connected by H with only the selected bit and no corresponding column for the selected bit. / RTI &gt;
(a) a demodulator that receives a modulated signal from a communication channel and provides a sample of the punctured codeword generated by demodulating the modulated signal to remove nn 'selected bits from the n-bit codeword, where n' The codeword being generated by encoding the k input bits according to a first code associated with a parity check matrix H with m rows and n columns (n = m + k); And
(b) a decoding module that decodes a sample of punctured codewords using a matrix H 'having a maximum of m rows and a number of columns less than n and not equal to n', where H 'is the parity check of the second code The punctured code word is a code word of a second code and the matrix H 'is derived from the matrix H by merging the pair of rows of the matrix H, and the pair of rows has a 1 in the different columns -;
&Lt; / RTI &gt;
delete 40. The method of claim 39,
H 'has more than n' columns,
Puncturing includes removing n-n ' selected bits from the codeword,
Deriving H 'from H,
performing a Gaussian elimination on H such that elements 1 through m-m &quot; of columns of H corresponding to m &quot;< n-n selected bits are set equal to zero, H &quot; is generated, and H 'is m-m &quot; low of H''having no column corresponding to the selected bit of m''.
42. The method of claim 41,
Wherein the Gaussian elimination is terminated when another Gaussian cancellation produces a matrix H 'that does not satisfy a predetermined criterion of sparseness.
43. The method of claim 42,
Wherein the predetermined criterion of the sparse is that the number of the average columns of H 'is smaller than the smaller of 1/4 of the number of rows of 10 and H'.
40. The method of claim 39,
H 'has a row smaller than m' = m- (n-n ') and a column smaller than n'
Puncturing includes removing nn 'selection bits from the codeword,
Deriving H 'from H comprises performing Gaussian elimination on H such that elements 1 through m' of the H columns corresponding to the selected bit are set equal to zero, such that matrix H ''Is generated, and H' is the selected row of H '' without at least one column corresponding to the other bits connected by H with only the selected bit and no corresponding column to the selected bit.

Images