Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-12-22
2003-06-10
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S755000, C714S787000
Reexamination Certificate
active
06578170
ABSTRACT:
The present invention concerns a coding device, a coding method, a decoding device and method 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 to implement 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”. For convenience:
the operation performed by the turbocoder is referred to as “turbocoding” and this operation provides a so-called “turbocoded” sequence, and
the operation performed by the decoder is referred to as “turbodecoding” and this operation provides a so-called “turbodecoded” sequence.
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 “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 permutation devices is far from being completely mastered. Certain of these devices use 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.
A parallel turbocoder of efficiency equal to ⅓ can be considered as a pair of convolutional systematic recursive coders with divisor polynomials such that 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 (or “permutation”) of the sequence u. In this context, the simultaneous return to zero of the two coders is a classic problem. One way of solving it has been found by the inventors and is summarized below.
With the aim of clarity, it will be assumed, subsequently, that the two divisor polynomials of the turbocoder are equal and referred to as g(x). Let m be the degree of the polynomial g(x) and let N
0
be the smallest integer such that g(x) is a divisor of the polynomial x
N0
+1. For reasons described below, a polynomial g(x) is chosen having no divisor which is the square of a polynomial of degree equal to or greater than 1, and this leads to N
0
being an odd number.
Also let n be an odd multiple of N
0
: n=M N
0
.
A sequence of symbols, u, then has a polynomial representation u(x), of degree n−m−1, with binary coefficients, and this polynomial u(x) is precoded into:
a
(
x
)=
u
(
x
)+&Sgr;
i=n−m to n−1
a
i
x
i
where the m binary symbols a
i
are chosen in such a way that a(x) is a multiple of g(x). As a consequence of this preceding and the chosen values of the parameters, 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, the permutation and interleaver type described above is referred to as “x to x
e
”.
Here, it is necessary to consider that g(x) has no multiple factor since, in general, a*(x) is guaranteed to be divisible only 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.
With general turbocodes, the decoding is essentially an iterative procedure (on this subject see the document by Messrs. BERROU and GLAVIEUX, “
Near optimum error
-
correcting and decoding: turbocodes
”, IEEE Trans. On Comm., Vol. COM-44, pages 1261 to 1271, October 1996).
The document by J. ANDERSEN is known, “
Turbocoding for deep space applications
”, proceedings IEEE 1995,
International Symposium on Information Theory,
Whistler, Canada, September 1995, in which a BCH code is used for correcting the residual errors. However, this solution has a fairly limited effectiveness in terms of residual error bit correction. The inventors observed that this last remark was particularly true in the case of the use of “x to x
e
” type interleavers.
The present invention aims to remedy these drawbacks. To this end, the present invention relates, according to a first aspect, to a method of coding a sequence of information symbols of polynomial representation u(x), including:
a turbocoding operation, and
an operation of transmitting, on a transmission channel, the sequence resulting from the turbocoding operation,
characterised in that it also includes, as a preliminary to the said turbocoding operation, at least one precoding operation during which there are added, to the said sequence u(x), redundant symbols which guarantee the divisibility of the precoded sequence by at least one predetermined polynomial which is:
a non-trivial multiple of the divisor polynomial used by the coder of the said turbocoder, a coder which acts on the precoded sequence, and
which is among the polynomials which have a high probability of dividing the polynomial representing a transmission error on the said channel.
The present invention relates, according to a second aspect, to a decoding method, characterised in that it takes into account:
at least one predetermined polynomial, and
a received sequence r capable of being the result of the coding of a sequence of information symbols of polynomial representation u(x) representing a physical quantity, the coding including a turbocoding, and guaranteeing the divisibility of a sequence to be turbocoded, a(x) representing the sequence u(x), by each predetermined polynomial,
and in that it includes:
an operation of turbodecoding the received sequence r into an estimated sequence â,
at least one operation of calculating the remainder of the division of the polynomial representation â(x) of the estimated sequence â, by a said predetermined polynomial.
The inventors, in fact, observed that the residual errors have, in the case described above (“x to x
e
”), a particular structure as far as the iterations of the decoder are continued until their result stabilizes. This particular structure makes them, generally, divisible by one or more predetermined polynomials.
The present invention aims to make use of this observation by proposing a method for detection or correction of these residual errors which is well adapted to the coding scheme described above.
By virtue of the provisions of the present invention, the processing (detection or correction) of residual errors, after turbodecoding, can be performed, on the one hand, on the received sequence and, on the other hand, on the sequence resulting from the division operation. The implementation of the method of the present invention is therefore particularly simple.
For example, the information sequence u(x) is precoded into a polynomial a(x)=u(x)+&Sgr;
i=n−m to n−1
a
i
x
i
, so that the sequence a(x) is a multiple, not only of the divisor polynomial of the turbocode, but also of other predetermined polynomials and of a generator polynomial denoted by q(x) of a binary BCH code, or more generally of a binary cyclic code, in length at least equal to n, and correcting s errors, where s is for example chosen equal to four.
This particular precoding necessitates a value of m higher
Le Dantec Claude
Piret Philippe
Baker Stephen M.
Canon Kabushiki Kaisha
Fitzpatrick ,Cella, Harper & Scinto
LandOfFree
Coding device and method, decoding device and method 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 Coding device and method, decoding device and method and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Coding device and method, decoding device and method and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3163097