Electrical computers and digital processing systems: virtual mac – Task management or control – Process scheduling
Reexamination Certificate
1999-11-05
2003-10-28
Tu, Christine T. (Department: 2784)
Electrical computers and digital processing systems: virtual mac
Task management or control
Process scheduling
Reexamination Certificate
active
06638318
ABSTRACT:
The present invention concerns a coding device, a coding method, a decoding device and method and systems implementing 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 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 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 on the conference “ICC'93”, 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 permutation devices is as far from being perfectly mastered. In general this device uses square or rectangular matrices in which one line after another is written and one column after another is read. These matrices are generally very large, for example 256×256 in size.
A turbocoder with an efficiency of ⅓ can be considered to be a pair of convolutional systematic coders using divisor polynomials. The first coder produces a check sequence from the sequence of symbols to be coded u and the second coder produces a check sequence from an interleaved sequence u* obtained by interleaving the sequence u. In this context, the return to zero of the two coders, simultaneously, is a classic problem.
A first manner of resolving this was described in the publication “Frame oriented convolutional turbo-codes”, (C. BERROU et al.), Electronics Letters, Volume 32, No. 15, Jul. 18, 1996 p. 1362-1364, Stevenage, Herts, Great Britain.
Let the divisor polynomial of a turbocoder, that is to say of each elementary coder, be g(x). Let the degree of the polynomial g(x) be m and N
0
the smallest integer such that g(x) is a divisor of the polynomial x
N0
+1. Let also n be a multiple of N
0
: n=M N
0
.
In order to disclose the content of this publication, the sequence of symbols to be coded will be represented as a sequence of polynomials u(x)=&Sgr;
i=0 to n−1
u
i
x
i
. Thus each polynomial u(x) contains n binary symbols to be coded.
Let then u(x) be written as
u
(
x
)=&Sgr;
j=0 to N0−1
s
j
(
x
N0
)
x
i
.
where each polynomial s
j
(x) has a degree M−1.
With regard to
FIG. 1
, it will be understood that this set of writings can be represented as follows:
in a table
101
having N
0
columns, the symbols u
i
of the sequence u, are entered, row by row, from left to right and starting from the highest line and going towards the lowest line in the table;
the polynomials S
j
(x) are polynomials whose coefficients of increasing rankings are the symbols which are situated in the j
th
column in the table, entered, in order, from top to bottom.
Let S*
j
(x) then be another polynomial of degree M−1 obtained from S
j
(x) by permutation of its coefficients. For different values of j, the permutations producing S*
j
(x) from S
j
(x) can be different.
In the table
101
considered above, this amounts to stating that the coefficients of the polynomial S
j
*(x) are those of the j
th
column in the table, but in a different order from the coefficients of the polynomial S
j
(x).
If the table
102
corresponding to the polynomials S
j
*(x) is written in the same way as the table
101
corresponds to the polynomials S
j
(x), by juxtaposing the last line in the table
101
and the first in the table
102
, is found that each coefficient which is situated in the j
th
column in the table
101
is situated in the j
th
column in the table
102
.
Let then u*(x)=&Sgr;
j=0 to N0−1
s*
j
(x
N0
)x
i
be written and let:
i uu*(
x
)=
u
(
x
)+
x
n
u
*(
x
) be defined.
It is easy to show that uu*(x) is divisible by g(x). Therefore the coding of u(x) as v=[u, uu*/g] is possible with an exact division. The efficiency R of this coding is then given by R=nl(3n−m).
A second way of resolving the problem of the return to zero of the coder has been found by the inventors and is summarised below.
Let g(x) be the divisor polynomial of a turbocoder, that is to say of each coder. Let m be the degree of the polynomial g(x) and N
0
the smallest integer such that g(x) is a divisor of the polynomial x
N0
+1. For reasons described below, g(x) is considered to be a “polynomial without square” and this means that N
0
is an odd number.
Let also n be an odd multiple of N
0
: n=M N
0
.
A sequence of symbols u, of length n′=n−m, then has a polynomial representation u(x), of degree n−m−1, with binary coefficients, and this polynomial u(x) is precoded as:
a
(
x
)=
u
(
x
)+&Sgr;
i=n−m
n−1
a
i
x
i
where the m symbols a
i
are chosen so that a(x) is a multiple of g(x). In consequence of this precoding, if a(x) is a multiple of g(x), then a*(x)=a(x
e
) modulo x
n
+1 is also a multiple of g(x) for any value of e which is a power of 2.
In the remainder of the description, this type of interleaver and, by extension, the type of turbocoders which implement them, is called “x to x
e
”.
Here it is necessary to consider that g(x) has no multiple factor because, in general, a*(x) has the guarantee of being divisible solely by the irreducible factors of g(x).
The coded version of u is then given by v=[a, ah
1
/g, a*h
2
/g] where all the components are polynomials, and where, in particular, a*h
2
/g is also a polynomial, by virtue of the definition of a* and the choice of e as a power of 2.
The present invention aims to exploit conjointly the advantages of the teachings of the approaches mentioned above.
To this end, according to a first aspect, the present invention relates to a coding method, characterised in that: 1/ it takes into account:
a “polynomial without square” g(x),
N
0
, the smallest integer such that g(x) is a divisor of the polynomial x
N0
+1;
n, an odd multiple of N
0
;
a sequence u of n symbols u
i
to be coded; and
e, a power of 2 different from 1, for which the residue of e modulo N
0
is equal to 1,
2/ it includes:
an operation of forming a so-called “concatenated” sequence uu* consisting successively, on the one hand, of the sequence of symbols u, having n symbols, and on the other hand a sequence of symbols u* defined by its polynomial representation, u*(x)=u(x
e
) modulo x
n
+1,
an operation of coding the concatenated sequence, including at least one division of the concatenated sequence uu* by the polynomial g(x) in order to form a so-called “check” sequence.
Thus the present invention consists of using, as a specific interleaver, in the coding scheme disclosed in the publication by C. BERROU et al., interleavers identical to those used by the inventors and presented above, of the type “x to x
e
”, for which the residue of e modulo N
0
is equal to 1.
The advantages of the present invention are as follows:
It describes a specific non-trivial way for implementing the idea of the publication by C. BERROU;
provision is made for the regular structure of the interleaver which is the object of the present invention to have favourable effects on the type of residual error after decoding;
implementation of the invention is particularly simple since merely the knowledge of the values of n and
Le Dantec Claude
Piret Philippe
LandOfFree
Method and device for coding sequences of data, 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 Method and device for coding sequences of data, and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and device for coding sequences of data, and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3135754