Interlacer, coding device, permutation method, coding...

Details Interlacer, coding device, permutation method, coding... Interlacer, coding device, permutation method, coding...

1998-12-30

2002-04-09

Decady, Albert (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S701000

Reexamination Certificate

active

06370670

ABSTRACT:

The present invention concerns a coding device, a coding method, a decoding device and method and systems implementing them.
It applies just as 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.
The invention finds an application in the field of convolutional codes. When the latter are used to implement an iterative decoding, these codes are greatly improved when their coders contain a permutation device. In this case, they are normally referred to as “turbocodes” and the corresponding iterative decoder is referred to as a “turbodecoder”.
On these subjects, documents which serve 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 a 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 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 a size 256×256.
According to another method, in an article entitled “Weight distributions for turbo-codes using random and nonrandom permutations” published by Jet Propulsion Laboratory, with “TDA Progress Report”, number 42-122, of Aug. 15, 1995, Messrs. DOLINAR and DIVSALAR considered the permutations which, by 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, they give only one example where k is a power of 2. In addition, they do not discuss the possible reciprocal influence of the choice of the permutation device and of that of the elementary convolutional coders (
2
,
1
) to be used to generate 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 signal
oise ratio values and measuring the minimum value of this ratio for which a predetermined value of the probability of error on the binary values is reached.
However, the use of simulations as an evaluation tool can lead to a few problems.
For example, the permutation device with k=65536=256×256, mentioned above, is chosen, and a predetermined error probability equal to 10
−5
is chosen to simulate 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.
A possible method for remedying this situation is to produce a harmonious and conjoint 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, as a function of the position of the binary information in the permutation device.
Another problem concerns the lack of algebraic tools for specifying the permutation devices. It will be useful to have available means for specifying a selection of permutation devices having a performance representative of the set of all the permutation devices.
The invention concerns principally the transmission of information represented by sequences of binary symbols:
u
=(
u
0
, u
1
, . . . , u
k−1
),
referred to as “sequences of information”, which will be coded in a triplet of binary sequences,
v
=(
a, b, c
),
each of these sequences a, b and c, being, by itself, representative of the sequence u.
In the remainder of the description, in order to represent a sequence u, the form u=(u
0
, u
1
, . . . , u
k−1
), is used indifferently along with 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, its is known, in order to determine 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 the polynomial, for example g(x)=1+x+x
3
, corresponding, according to the representation in a 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
by 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 interlacer which associates the permuted sequence
a
* with the sequence a, specifies a coder which will be referred to as a “turbocoder”. All the sequences which a specified turbocoder can produce will be referred to as “turbocode”.
In the remainder of the description, the term “first coder”, will be given to the elementary recursive convolutional coder which produces the sequence b and “second coder” will be given to the one which produces the sequences c.
The polynomial divisions used are of the type consisting of division according to ascending powers, 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 iterative decoding which is powerful, relatively simple and inexpensive.
To implement it, several questions are posed.
I/ How to choose the polynomials g(x), h
1
(x) et 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 interlacers, that is to say of 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 taking the terms in this table in succession 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 interlacer 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 of the sequence a is six and if s=5 and t=3, the interlacer 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) in the third example, the permutation chosen is random.
III/ How to avoid the division defining b(x) not having a remainder? and
IV/ How to avoid the divis

Affiliated with

Also associated with

Rating

Interlacer, coding device, permutation method, coding... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Interlacer, coding device, permutation method, coding..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interlacer, coding device, permutation method, coding... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2828851