Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-11-08
2004-07-20
Tu, Christine T. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S781000
Reexamination Certificate
active
06766489
ABSTRACT:
The present invention concerns a method and a device for adapting turbocoders and the associated decoders to sequences of variable length and systems using them.
It applies equally well to the coding of data representing a physical quantity, to the coding of data in the form of codes capable of modulating a physical quantity, to the decoding of data modulated signals, and to the decoding of data representing physical quantities. These data can, for example, represent images, sounds, computer data, electrical quantities or stored data.
The invention finds an application in the field of convolutional codes. When the latter are used for implementing an iterative decoding, these codes are greatly improved when their coders contain a permutation device. In this case, they are usually referred to as “turbocodes” and the corresponding iterative decoder is referred to as a “turbodecoder”.
On these subjects, documents which serve as references are, on the one hand, the article by Messrs. C. BERROU, A. GLAVIEUX and P. THITIMAJSHIMA entitled “
Near Shannon limit error
-
correcting coding and decoding: turbocodes
” published with the reports of the “ICC'93” conference, 1993, pages 1064 to 1070, and, on the other hand, the article by Messrs. C. BERROU and A. GLAVIEUX entitled “
Near Optimum error
-
correcting coding and decoding: turbo
-
codes
” published by IEEE Transactions on Communication, Volume COM-44, pages 1261 to 1271, in October 1996.
However, the formation of the permutation devices is far from being completely mastered. In general, this device uses square or rectangular matrices which are written into one row after another and read from one column after another. These matrices are generally very large, for example 256×256 in size.
According to another method, in an article entitled “
Weight distributions for turbo
-
codes using random and nonrandom permutations
” published by the Jet Propulsion Laboratory, with “TDA Progress Report”, number 42-122, on 15 Aug. 1995, Messrs. DOLINAR and DIVSALAR consider the permutations which, numbering the k information item positions between 0 and k−1, move the binary information items placed in a position i to a position e i+f, for “well-chosen” values of e and f.
In this document, they give only one example where k is a power of 2. Moreover, they do not discuss the possible mutual effect of the choice of the permutation device and that of the elementary convolutional coders (
2
,
1
) to be used for generating the coded sequences produced by the turbocoder (
3
,
1
).
The evaluation of the corresponding turbocode consists of simulating its use on a transmission channel with different values of signal
oise ratio and of measuring the minimum value of this ratio for which a predetermined value of error probability on the binary values is reached.
However, the use of simulations as an evaluation tool can lead to a few problems.
Let, for example, the permutation device with k=65536=256×256, mentioned above, be considered, and let a predetermined error probability equal to 10
−5
be chosen for simulating the performance of a turbocode using this device. Consequently, the mean number of errors on the binary values per 256×256 block will be close to 1, but it will not be known whether each item of binary information has the same error probability. This error probability could be quite high for binary values having an “unfortunate” position in the permutation device and this probability could be much lower for more “fortunate” positions.
One possible way for remedying this situation is to carry out a harmonious and joint design of the permutation device and the two convolutional coders in order to guarantee a reasonable uniformity of the error rate on the binary values after decoding, according to the position of the binary information in the permutation device.
Another problem concerns the lack of algebraic tools for specifying the permutation devices. It would be useful to have available means making it possible to specify a selection of permutation devices having performances representative of the set of all the permutation devices.
The invention principally concerns the transmission of information represented by sequences of binary symbols:
u
=(
u
0
,u
1
, . . . ,u
k−1
),
referred to as “information sequences”, which will be coded into a triplet of binary sequences,
v
=(
a
,
b
,
c
),
each of these sequences
a
,
b
and
c
being, on its own, representative of the sequence
u
.
In the remainder of the description, for representing a sequence
u
, the form
u
=(u
0
, u
1
, . . . , u
k−1
), and the associated polynomial form:
u
(
x
)=
u
0
x
0
+u
1
x
1
+ . . . +u
k−1
x
k−1
are used indiscriminately.
Equivalent notations will be used for the sequences
a
,
b
and
c
. Using this second representation, the following is known for determining the triplet
v
=(
a
,
b
,
c
):
choosing a(x)=u(x);
choosing b(x)=u(x).h
1
(x)/g(x),
where g(x) is a polynomial, for example g(x)=1+x+x
3
, corresponding, according to the sequential representation, to the sequence (1, 1, 0, 1); and h
1
(x) is a polynomial, for example h
1
(x)=1+x+x
2
+x
3
, corresponding to the sequence (1, 1, 1, 1); and
referring to as
a
*, a sequence formed by permutation of the binary data items of the sequence
a
, choosing c(x)=a*(x).h
2
(x)/g(x)
where h
2
(x) is a polynomial, for example h
2
(x)=(1+x
2
+x
3
) corresponding to the sequence (1, 0, 1, 1).
Any choice of the polynomials g(x), h
1
(x), h
2
(x) and of the permutation specifying the interleaver which associates the permuted sequence
a
* with the sequence
a
, specifies a coder which will be referred to as a “turbocoder”. The set of sequences which can be produced by a specified turbocoder will be referred to as a “turbocode”.
In the remainder of the description, the elementary recursive convolutional coder which produces the sequence
b
is referred to as the “first coder”, and the one which produces the sequence
c
is referred to as the “second coder”.
The polynomial divisions used are of the division according to ascending powers type, well known to persons skilled in the art. They use modulo 2 arithmetic. The sequences
a
,
b
and
c
are binary sequences and in the general case the divisions which define
b
and
c
have a remainder.
This type of coding method has the advantage of lending itself to an effective iterative decoding which is not very complex and not very expensive.
For implementing it, a number of questions arise:
I/ How are the polynomials g(x), h
1
(x) and h
2
(x) chosen?
II/ How is the permutation of the terms of the sequence
a
which produces the sequence
a
* chosen ? Among the choices proposed, three examples of interleavers, that is to say operators which permute the terms of the sequence
a
, in order to form the sequence
a
*, are given below:
A) in the first example, after having arranged the terms of
a
in a rectangular table, successively row by row and, for each row, from left to right, the sequence
a
* is formed by successively taking, from this table, the terms column after column and, for each column, from top to bottom. For example, in the case of sequences of six terms and the use of a table of two rows of three columns, the interleaver transforms the sequence
a
=(a
0
, a
1
, a
2
, a
3
, a
4
, a
5
) into the sequence
a
*=(a
0
, a
3
, a
1
, a
4
, a
2
, a
5
).
B) in a second example, the i-th term (i=0, 1, 2, . . . ) a*
i
of the sequence
a
* is chosen as being the term a
j
of the sequence
a
, with j=s.i+t calculated modulo the number of terms in the sequence
a
, s and t being integers. For example, if the number of terms in the sequence
a
is six and if s=5 and t=3, the interleaver transforms the sequence
a
=(a
0
, a
1
, a
2
, a
3
, a
4
, a
5
) into the sequence
a
*=(a
3
, a
2
, a
1
, a
0
, a
5
, a
4
).
C) i
Le Dantec Claude
Piret Philippe
No associations
LandOfFree
Device and method of adapting turbocoders and the associated... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Device and method of adapting turbocoders and the associated..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Device and method of adapting turbocoders and the associated... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3239333