Image analysis – Image compression or coding
Reexamination Certificate
1999-11-08
2003-05-06
Johns, Andrew W. (Department: 2621)
Image analysis
Image compression or coding
C714S701000, C714S781000
Reexamination Certificate
active
06560362
ABSTRACT:
The present invention concerns an interleaver, an encoding device, a permutation method, a encoding method, a decoding device and method and systems using them.
It applies equally well to the encoding of data representing a physical quantity, to the encoding 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 serial or hybrid convolutional codes. When the latter are used for implementing an iterative decoding, these codes are greatly improved when their encoders 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”.
Serial turbocodes relate to the serial concatenation of two convolutional encoders separated by an interleaver. The decoding method is iterative. Hybrid turbocodes have an architecture which is both serial and parallel.
The second encoder of a serial turbo-encoder is always systematic and recursive.
On these subjects, documents which serve as references are:
the articles 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 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, with regard to parallel turbo-encoding,
the articles “Serial concatenation of interleaved codes: Performance analysis, design and iterative decoding”, Benedetto, Montorsi, (Univ. Politecnico di Torino, Italy), Divsalar, Pollara, (JPL, USA), TDA progress report, 42-126, August 1996; and “Hybrid concatenated codes and iterative decoding”, Divsalar, Pollara, (JPL, USA), TDA progress report, 42-130, August 1997, with regard to serial or hybrid turbo-encoding.
However, the formation of the permutation devices is far from being completely mastered. For example, 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.
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 over 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 convolutional encoders in order to guarantee a reasonable uniformity of the error rate over 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.
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,
and a sequence formed by permutation of the binary data of the sequence
u
will be denoted by
u
*.
The polynomial divisions used are of the type of division according to ascending powers, well known to persons skilled in the art. They use modulo 2 arithmetic.
The simultaneous return to the zero state of the convolutional encoders used in a turbo-encoder is a classic problem.
The present invention intends to propose families of interleavers which guarantee the return to zero of the convolutional encoders used as components in a serial or hybrid turbo-encoder.
To that end, according to a first of its aspects, the present invention relates to an encoding method, characterised in that:
1/ it takes into account:
two predetermined integers M
1
and M
2
, equal to or greater than 1,
a number K, greater than or equal to 1, of sequences a
i
(i=1, . . . ,K) of binary data representing a physical quantity, each sequence a
i
having:
a polynomial representation a
i
(x) which is a multiple of a predetermined polynomial g
i
(x), and
a number of binary data items equal to the product of any integer number M and the integer N
0
, the smallest integer such that the polynomial x
N0
+1 is divisible by each of the polynomials g
i
(x);
2/ it has an operation of convolutional encoding of the sequences a
i
into K+M
2
so-called “intermediate” sequences d
i
,
3/ it has a first production operation for a number (K+M
2
)*M
1
of so-called “permuted” sequences”, d
ij
*, (i=1, . . . ,K+M
2
; j=1, . . . ,M
1
), each sequence d
ij
*
being obtained by a permutation of the corresponding sequence d
i
, the said permutation being, in a representation where the binary data items of each sequence d
i
are written, row by row, Into a table with N
0
columns and M rows, the result of any number of so-called elementary permutations, each of which:
either has the property of transforming the cyclic code of length N
0
and with generator polynomial g
i
(x) into an equivalent cyclic code with generator polynomial g
ij
(x) which may be equal to g
i
(x), and acts by permutation on the N
0
columns of the table representing d
i
,
or is any permutation of the symbols of a column of the said table; and
having, in consequence, a polynomial representation d
ij
*(x) which is equal to a polynomial product c
ij
(x)g
ij
(x),
4/ it has a second production operation for M
1
redundant sequences, the polynomial representation of which is equal to &Sgr;f
ij
(x)c
ij
(x), for i=1, . . . , K+M
2
and j=1, . . . ,M
1
, each polynomial f
ij
(x) being a polynomial of degree at most equal to the degree of the polynomial g
ij
(x) with the same indices i and j.
Above, there have been introduced, in a representation where the binary data items of the sequence
a
are arranged in a table of N
0
columns and M rows, the successions of permutations taken from the set of permutations having, on the one hand, the automorphisms of the binary cyclic code of length N
0
and with generator polynomial g(x), permuting between them the columns of the table and, on the other hand, the permutations working solely on data of one and the same column and permuting between them at least two of the said data items.
The inventors have, discovered that all these successions of permutations, and only these, guarantee that, for any polynomial a(x) whose division by g(x) leaves a null remainder, the permuted polynomial a*(x) has the same property.
For a study of the conditions governing the choice of the g
ij
's, the reader can refer to page 234 of the book by Mrs F. J. MAC WILLIAMS and Mr N. J. A. SLOANE “
The theory or error
-
correcting codes
” published by the publisher North-Holland in 1977, the seventh impression of which took place in 1992).
All the choices described in the present invention include the interleavers described in the two articles mentioned above. Thus the performances expressed in terms of error rate as a function of the signal
oise ratio can be improved without increasing the complexity of the turbo-encoder nor t
Le Dantec Claude
Piret Philippe
LandOfFree
Encoding and interleaving device and method for serial or... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Encoding and interleaving device and method for serial or..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Encoding and interleaving device and method for serial or... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3074859