Product code iterative decoding

Details Product code iterative decoding Product code iterative decoding

1999-12-17

2002-10-01

Ton, David (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Error/fault detection technique

C714S804000

Reexamination Certificate

active

06460162

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention relates to a method of iteratively decoding product codes. The invention also relates to a transmission method and a transmission system using a decoding method of this kind.
The invention relates to decoding product codes of block linear codes. It applies to the field of channel coding for transmission. A typical transmission channel comprises a binary source, a coder, a modulator which transmits on a channel, a demodulator at the output of the channel, and a decoder which supplies the binary signal. The purpose of channel coding is to reduce the power needed to achieve a given bit error rate. French Patent Application No. 97 12594 filed on Oct. 9, 1997, whose title [in translation] is “Product code block coding method applicable in particular to coding an ATM cell”, gives a description of the basic concepts of channel coding and transmission, and may be referred to for further details. To the degree that the invention relates to channel decoding, the other elements of the transmission system—such as source coding and modulation to demodulation as a function of the transmission medium—are not explained further.
It is conventional to use redundant codes and product codes for coding. A code C
1
is generally characterized by a triplet (n
1
, k
1
, d
1
), where k
1
is the number of input bits of the code, n
1
is the number of output bits of the code and d
1
is the minimum Hamming distance of the code. Applying a code of this kind to a k-tuplet (x
1
, . . . , x
k
) supplies an n-tuplet (x
1
, . . . , X
k
, x
k+1
, . . . , x
n
) with n−k redundant bits.
The expression “product code” refers to the successive application of two codes C
1
and C
2
, in the following manner. Consider k
1
.k
2
bits, in the form of k
2
words each of k
1
bits. A code C
1
(n
1
, k
1
, d
1
) is applied to the k
2
words of k
1
bits and k
2
words of n
1
bits are obtained. Stored in matrix form, the k
2
words of n
1
bits form n
1
columns, the j
th
column being formed of the j
th
bit of each of k
2
words. A code C
2
(n
2
, k
2
, d
2
) is applied to each of these n
1
columns of k
2
bits to obtain n
1
words of n
2
bits. Applying a product code of the above kind changes from k
1
.k
2
bits to n
1
.n
2
bits, with n
1
.n
2
−k
1
.k
2
redundant bits. If the codes are linear, this produces n
2
rows of words of code C
1
or n
1
columns of words of code C
2
. The product code is a code having the parameters (n
1
.n
2
, k
1
.k
2
, d
1
.d
2
). The encoding order is immaterial, and the same results are obtained by coding the rows first, as described above, or by coding the columns first. Product codes of the above kind are described in the literature on channel coding. The French application referred to above and FIG. 2 of FR-A-2 712 760 explain in detail the principle of coding by means of a product code of the above kind.
The problem with product codes of the above kind is decoding at the demodulator output. Sets of values of bits (generally modulated in the form ±1) are obtained at the output of the demodulator, accompanied by noise. The value received, accompanied by noise, which is a real value, is referred to as a “soft” value. The value ±1, i.e. the corresponding binary value, obtained for a threshold-based decision on the value received is referred to as a “firm” value. Hereinafter the expression “firm word” means a binary word and the expression “soft word” means a word actually received, formed of real values.
On transmission with coding by a product code, a set
R
={r
i,j
} of n
1
.n
2
real values (soft values) is obtained at the output of the demodulator. Decoding consists in determining the word of the product code C
1
.C
2
to which the soft values correspond, according to some particular performance criterion. If the noise is additive Gaussian white noise, the optimum solution is to look for the product code word which minimizes the euclidean distance to the received soft word
R
. This criterion of the maximum likelihood is impossible in practice, once the product k
1
.k
2
routinely exceeds a few hundred.
Various solutions have therefore been proposed to the problem of decoding product codes. The most immediate solution consists in taking firm decisions on each bit of the received soft word and successively decoding the rows and then the columns, as firm decisions, by applying a decoder of the code C
2
to the columns and then a decoder of the code C
1
to the rows. This solution is a long way short of the optimum and cannot achieve the theoretical gain of a product code because it does not use all the information received from the transmission channel.
FR-A-2 712 760 proposes an algorithm for iterative decoding of product codes C
1
.C
2
in which the columns or rows of the matrix formed from the received product code word are decoded iteratively and successively. For each column or row, i.e. for each word of the code C
2
or C
1
received accompanied by noise (received soft word), the above document proposes to use a modified Chase algorithm for decoding, to be more precise:
generating a set of firm words of the code C
2
or C
1
a priori close to the received soft word in the corresponding row or column,
calculating the Euclidean distance between the various firm words and the received soft word, and
choosing as the received code word whichever of the various firm words is at the minimum distance from the soft word actually received.
To generate the set of firm words of the code C
2
(or C
1
) a priori close to the received soft word, the above document proposes:
to mark the least reliable
p
components of the soft word received,
to construct
q
test binary sequences from the
p
least reliable components,
to construct
q
binary words to be decoded from the above sequences of binary tests and a current binary value of the decoded word, which current binary value is initialized at the outset by a binary approximation of each of the received bits, and
to decode the
q
binary words with a Berkelamp decoder (algebraic decoder) to obtain q′ code words, and if necessary to verify that the q′ words obtained are words of the code C
2
(or C
1
).
The construction of the a binary words and their decoding by the above algorithm is inefficient: the
q
words generated are words of the code C
2
(or C
1
), but are not necessarily different. There is obtained at the output of the decoder a number q′ of different code words which is less than the number
q
of words generated.
Also, the above method works only with codes for which there exists an algebraic decoder. Implementing algebraic decoders necessitates calculations in the Gallois body and a complex architecture.
A doctoral thesis submitted to the Paris ENST by Juing Fang in 1986, whose title [in translation] is “Weighted decoding of block linear codes”, describes a soft input algorithm for decoding a block linear code. The algorithm is optimum in the maximum likelihood sense and does not explicitly use the algebraic structure of the code. It supplies at the output a firm code word with maximum likelihood. The algorithm is one of many soft input to firm output decoding algorithms and there is no suggestion of using lists to generate a soft output.
SUMMARY OF THE INVENTION
The invention proposes a solution to the problem of iterative decoding of product codes which enables faster and more efficient decoding and which applies to all types of code, not only those for which there is an algebraic decoder.
Decoding product codes is not a mathematical problem, but rather a serious technical problem in the transmission field. It is applied directly to decoding values of received product code words or bits at the output of the demodulator of a transmission channel.
To be more precise, the invention proposes a method of soft input to soft output decoding of a word (
s
) of a block linear code of dimension
k
and length
n
, received from a transmission channel, comprising the steps of:
generating a list of

Affiliated with

Also associated with

Rating

Product code iterative decoding does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Product code iterative decoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Product code iterative decoding will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3000045