Error detection/correction and fault detection/recovery – Pulse or data error handling – Data formatting to improve error detection correction...
Reexamination Certificate
2000-02-25
2003-09-23
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Data formatting to improve error detection correction...
C714S786000
Reexamination Certificate
active
06625762
ABSTRACT:
The present invention concerns an interleaving method and device used by systems for turbocoding or turbodecoding binary sequences, which may be 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 able to modulate a physical quantity, to the decoding of data-modulated signals, and to the decoding of data representing a physical quantity. These data can, for example, represent images, sounds, computer data, electrical quantities or stored data.
In general terms, a turbocoder uses at least two recursive convolutional coders and at least one permutation circuit also referred to as an interleaving circuit or interleaver. The corresponding iterative decoder is referred to as a turbodecoder.
Turbodecoders are nowadays envisaged for use in third-generation mobile systems, notably for certain data services.
On these subjects, documents served as a reference 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 conference “ICC'93”, 1993, pages 1064 to 1070, and on the other hand of 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.
The construction of permutation devices is far from being perfectly mastered. In general, this device uses square or rectangular matrices in which one row after another is written and one column after another is read. These matrices are generally very large, for example of size 256×256.
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, Aug. 15, 1995, Messrs. DOLINAR and DIVSALAR consider the permutations which, numbering the k information positions between 0 and k−1, move the binary information placed at a position i to a position e i+f, for “well chosen” values of e and f.
In this document, the authors give only one example where k is a power of 2. In addition, the authors do not discuss the possible mutual influence of the choice of the permutation device and the choice of the elementary convolutional coders (2, 1) to be used for generating the coded sequences produced by the turbocoder (3, 1).
The evaluation of one or more interleavers and a turbocode using them generally consists of simulating the use of the turbocode on a transmission channel with different values of the signal
oise ratio and measuring the minimum value of this ratio for which a predetermined error probability on the binary values is reached.
However, the use of simulations as an evaluation tool can lead to a few problems. In particular, the consequences of a non-return to zero are concealed.
For example, the permutation device will be considered with k=65536=256×256, mentioned above, and a predetermined error probability equal to 10
−5
will be chosen for simulating the performance of a turbocode using this device. Consequently, the mean number of errors on the binary values per block of 256×256 will be close to 1, but it will not be known whether each binary information item has the same error probability. This error probability could be fairly high for binary values having an “unlucky” position in the permutation device, and this probability could be much smaller for more “lucky” positions.
One possible method for remedying this situation is to produce a harmonious conjoint design of the permutation device and two convolutional coders in order to guarantee 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 could be useful to have available means for specifying a selection of permutation devices having performances representing the set of all the permutation devices.
The invention concerns mainly 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 as a triplet of binary sequences,
v=
(
a, b, c
),
each of these sequences a, b and c, by itself, representing the sequence u.
In the remainder of the description, use is made indifferently, for representing a sequence u, of 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
.
Equivalent notations will be used for the sequences a, b and c. Using this second representation, it is known, for determining the triplet v=(a, b, c):
to choose a(x)=u(x);
to choose 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 representation in sequence, 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
calling a* a sequence formed by permutation of the binary data of the sequence a, to choose 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, specify the coder which will be referred to as a “turbocoder”. All the sequences which can produce a specified turbocoder will be referred to as a “turbocode”.
In the remainder of the description, the elementary recursive convolutional coder which produces the sequences b will be referred to as the “first coder”, and the one which produces the sequence c will be referred to as the “second coder”.
The polynomial divisions used are of the division according to increasing 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 a high-performance iterative decoding, of low complexity and inexpensive.
For implementing the turbocoding, several questions arise:
I/ How to choose the polynomials g(x), h
1
(x) and h
2
(x)?
II/ How to choose the permutation of the terms of the sequence a which produces the sequence a*?
Amongst 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 stored 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 taking the terms successively from this table 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 of 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
) in the sequence a*=(a
3
, a
2
, a
1
, a
0
, a
5
, a
4
).
C) in the third example
Canon Kabushiki Kaisha
Chase Shelly A
De'cady Albert
Fitzpatrick ,Cella, Harper & Scinto
LandOfFree
Interleaving device and method for turbocoding and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Interleaving device and method for turbocoding and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interleaving device and method for turbocoding and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3097570