Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-07-14
2004-08-24
Lamarre, Guy J. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S755000
Reexamination Certificate
active
06782504
ABSTRACT:
The field of the invention is that of coding digital data belonging to one or more source data sequences to be transmitted, or broadcasted, in particular in the presence of circuit transients, and decoding coded data thus transmitted.
More precisely, this invention relates to an improvement of the coding scheme known in particular as “turbo codes” (registered trademark), and more particularly of the permutation implemented thereby.
The general principle of this kind of coding is introduced in particular in French patent no. FR-9 105 280, entitled “Procédé de codage correcteur d'erreurs à au moins deux codages convolutifs systématiques paralléles, procédé de décodage itératif, module de décodage et décodeur correspondants”, and in the article by C. Berrou and A. Glavieux “Near Optimum Error Correcting Coding and Decoding: Turbo Codes” (IEEE Transactions on Communications, Volume 44, no. 10, pages 1261-1271, October 1996).
According to this technique, the implementation of “parallel concatenation” coding is suggested, based on using at least two elementary encoders. When decoding, this makes it possible to have two redundancy symbols from two distinct encoders. Between the two elementary encoders, a permutation means is implemented, so that each of these elementary encoders is supplied with the same digital source data, but taken in varying sequences.
An improvement of this kind of technique, for block coding (product codes), is described in the patent FR-9 313 858, and entitled “Turbo décodage des codes produits”, as well as in the article by O. Aitsab and R. Pyndiah “Performance of Reed Solomon block turbo code” (IEEE Globecom '96 Conference, Vol. 1/3, pages 121-125, London, November 1996).
To a relatively large extent, the performance of parallel concatenation convolutional “turbo codes” depends on the implemented permutation function. Indeed, it appears that a non-optimized choice of this function can lead to “turbo code” degradation, including in particular the occurrence of a gradient change in the error rate curve below 10
−5
and 10
−6
.
This phenomenon is all the more emphasized the higher the efficiency of the “turbo codes” under consideration, and the shorter the information blocks to be coded.
In the various documents quoted, permutation functions allowing to build “turbo codes” with good performance have been suggested.
In the patent FR-9 105 280, the elementary convolutional codes are binary, and permutations therefore take place directly on binary elements. More in general, many solutions for carrying out the permutation function in a parallel concatenation “turbo code” implementing binary convolutional codes have been suggested as part of third generation mobile phones (UMTS).
The patent FR-9 313 858, as well as the article by C. Berrou and M. Jezequel “Non-binary convolutional codes for turbo coding”, (Electronics Letters, Vol. 35, no. 1, pages 39-40, January 1999), also suggest using non-binary convolutional codes for building “turbo codes”. In this case, the permutation function therefore applies to the binary words (bit sets, e.g. pairs, or more generally n-pairs).
Generally speaking, the permutation function must of course allow to provide good dispersion of the elements from the information source and feeding the various parallel encoders, in order to create a strong random effect. Therefore, the distance properties of the composite encoder must be optimized, and in particular the minimum distance thereof maximized.
Thus, it is in particular an object of the invention to provide a parallel concatenation coding scheme (“turbo codes”) built from non-binary convolutional codes and having better permutation characteristics than those of known “turbo codes”.
More precisely, it is an object of the invention is to provide a parallel concatenation coding scheme optimizing the distance properties of the composite encoder (the “turbo code”), i.e. in particular maximizing the minimum distance thereof.
It is another object of the invention to provide such a coding scheme, creating a strong random effect on the data feeding the various elementary encoders, of course without modifying the dispersion effect.
It is also an object of the invention to provide such a coding scheme that is easy to implement in practice, at low cost, e.g. as an integrated circuit.
It is yet another object of the invention to provide such a coding scheme that is easy to implement for a very large number of application types.
These objects, as well as others that will be apparent more clearly hereafter, are achieved according to the invention by means of a digital source data coding scheme, implementing in parallel at least two elementary coding steps each taking into account all of said source data, and comprising a permutation step modifying the sequence of consideration of said source data between said elementary coding steps, wherein said source data is organized in source code words each comprising n binary source elements, n being greater than or equal to 2. According to the invention, said permutation step comprises:
a step of reversibly modifying the contents of at least some of said source code words, delivering modified code words;
a step of permutating the sequence of said source or modified code words.
In other words, the invention proposes to take effect at two levels, during the permutation step (the visual term of “permutation” is maintained here, but the terms of “shuffling”, or “processing” could be used advantageously, because, as will be apparent later on, it is possible to modify the value of certain binary elements). Indeed, on the one hand, the sequence of the code words (or multiples of n), and on the other hand, the contents of the latter (intra-word modification) is acted upon.
It will be noted that word permutation can just as well be performed before or after processing the words as such.
According to an advantageous embodiment, said step of permutating the code word sequence implements a uniform permutation applied to a block of N consecutive code words.
This technique is very easy to implement, and allows to achieve almost optimal efficiency.
It can be implemented advantageously using a memory containing N code words entered in the sequence from 0 to N−1 and reread in the sequence from j=P.i, i varying from 0 to N−1, P and N mutually being prime numbers.
Preferably, in this case, P is close to N.
According to a preferred approach of the invention, said contents modification is applied only to some of said code words. E.g., said contents modification is applied to every other code word.
Advantageously, said contents modification comprises a permutation of the sequence of binary elements within the code word under consideration.
According to another advantageous aspect, said contents modification comprises replacing at least one of the binary source elements of the code word under consideration with a combination of at least two of said binary source elements.
Said code words can in particular be pairs. However, they can of course more generally be multiples of n, whatever the value of n, greater than or equal to 2.
In the case of pairs, the combinations can associate with the source pair {a,b} at least one of the following modified pairs:
(a,b)
(b,a)
(a+b,b)
(b,a+b)
(a,a+b)
(a+b,a)
REFERENCES:
patent: 4394642 (1983-07-01), Currie et al.
patent: 5446747 (1995-08-01), Berrou
patent: 5898698 (1999-04-01), Bross
patent: 5996104 (1999-11-01), Herzberg
patent: 6023783 (2000-02-01), Divsalar et al.
patent: 6029264 (2000-02-01), Kobayashi et al.
patent: 2 675 971 (1992-10-01), None
patent: 2 712 760 (1995-05-01), None
patent: 99 07076 (1999-11-01), None
Aitsab, Omar; Pyndiah, Ramesh; “Performance of Reed-Solomon Block Turbo Code”; p. 121-125; IEEE 1996.
Berrou, C; Jezequel, M.; “Non-binary convolutional codes for turbo coding”, Jan. 7, 1999, vol. 35, No. 1; p. 39.
Berrou, C.; Glavieux, A.; “Near Optimum Error Correcting Coding and Decoding: Turbo-Codes”; p. 1261-1271; IEEE 1996.
French Search Report.
Berrou Claude
Glavieux Alain
Abraham Esaw
Groupe des Ecoles de Telecommunications
Lamarre Guy J.
Merchant & Gould P.C.
LandOfFree
Coding scheme and device with at least two parallel... 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 scheme and device with at least two parallel..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Coding scheme and device with at least two parallel... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3343648