Coded data generation or conversion – Digital code to digital code converters – To or from interleaved format
Reexamination Certificate
2000-10-31
2002-06-11
Young, Brian (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from interleaved format
Reexamination Certificate
active
06404360
ABSTRACT:
The invention lies within the general field of information transfer methods. It concerns more particularly a method and device for interleaving data forming part of a transmission or reception method.
The invention finds its place in the general field of the coding of data with a view to their transmission or reception, for example by a radio system. Conventionally there are known in this field coders of the particular type known as “turbocoders” (and the associated decoding devices known as “turbodecoders”) described for example in previous patents by the same applicant. Such a turbocoder and the associated decoder use one or more data interleaving devices.
The object of the present invention is an interleaving and deinterleaving method, intended to form part of such a so-called “turbocoding” method and the associated turbodecoding method.
The present invention applies equally well to the coding of data representing a physical quantity, to the coding of data able to modulate a physical quantity, to the decoding of modulated signals in the form of data, and to the decoding of data representing physical quantities or to the management of data transmissions. These data can, for example, represent images, sounds, computer data, electrical quantities or stored data.
When convolutional coders are used for implementing an iterative decoding using elementary decoders with soft inputs and outputs, these codes are greatly improved when their coders contain a permutation device, also referred to as an “interleaver”, a permutation device making it possible to return to the initial sequence then being called a “deinterleaver”. In this case, they are normally referred to as turbocoders 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 supplies a so-called “turbocoded” sequence
the operation performed by the turbodecoder is referred to as “turbodecoding”, and this operation supplies a “turbodecoded” sequence.
On these subjects, documents which serve as a reference are, on the one hand, the articles by C. Berrou, A. Glavieux and P. Thitimajshima entitled “
Near Shannon Limit Error
-
Correcting Coding and Decoding: Turbocodes”
published in the proceedings of the ICC'93 conference, 1993, pages 1064 to 1070, and on the other hand the article by C. Berrou and A. Glavieux entitled “
Near Optimum Error
-
Correcting Coding and Decoding: Turbocodes”
published in IEEE Transactions on Communications, Volume 44, pages 1261 to 1271, in October 1996.
The aim of the present invention is to propose more efficient interleavers for a turbocoder, that is to say ones making it possible to obtain a greater minimum distance. This is particularly important when the signal to noise ratio of the channel is relatively high, since this can then reduce the decoding error rate and consequently avoid having to send again data wrongly received.
It should be stated briefly here that a turbocode has a different behaviour depending on the value of the signal to noise ratio of the channel. If the signal to noise ratio is high, the minimum weight of the non-zero words of the turbocode and the number of these words of minimum weight predominate in the determination of the performance of the turbodecoder. On the other hand, if the signal to noise ratio is low, it appears that it is the number of code words with a weight close to a value greater than or equal to the minimum weight of the code which influences the performance of the turbodecoder.
The invention relates, in a first aspect, to a permutation method, characterised in that it makes an output rank from 0 to r·m−1 correspond to each input rank from 0 to r·m−1, the said method including the following steps:
E1—a matrix S having r rows and m columns is considered, filled row by row by the successive numbers from 0 to r·m−1,
E2—each column in said matrix S is divided into a predetermined number &lgr; of sub-columns, such that r/&lgr; is not prime,
E3—the sub-columns of S equal in number to &lgr;·m are designated by S
&lgr;1
&lgr;2
with 0≦&lgr;
1
≦&lgr;−1 and 0≦&lgr;
2
≦m−1 where &lgr;
2
refers to the column of S where S
&lgr;1
&lgr;2
appears and &lgr;
1
refers to the position of the sub-column S
&lgr;1
&lgr;2
in the column of index &lgr;
2
.
E4—each sub-column S
&lgr;1
&lgr;2
is then written in the form of a matrix with R rows and M columns (with r/&lgr;=RM) and in this form it is interleaved by an interleaver of the so-called “wheel” type defined by a circular permutation of each column of said matrix with R rows and M columns, said interleaver not being identity,
E5—this matrix with R rows and M columns is reconverted, after said circular permutations on its columns, into a sub-column S*
&lgr;1
&lgr;2
which will occupy, in a matrix S*, the same position as that occupied by S
&lgr;1
&lgr;2
in the matrix S,
E6—the permutation table consists of pairs each formed by an element of the matrix S and the element with the same position in the matrix S*.
Preferentially, the method also includes, in at least one column &lgr;
2
(0≦&lgr;
2
≦m−1) of the matrix S* a modification of the order of appearance of the sub-columns S*
&lgr;1
&lgr;2
in said column.
According to a preferred implementation, one and the same wheel interleaver is used for producing each of the sub-columns S*
&lgr;1
&lgr;2
of a given column &lgr;
2
of the matrix S*.
According to a particular implementation, the sub-columns with at least two columns of the matrix S* are produced by different wheel interleavers.
According to a more particular implementation, the m wheel interleavers used for interleaving the sub-columns in each column of the matrix S* are different.
Preferentially, the method also includes a step of permutation of the columns of S* with each other.
In a particular implementation of the methods described above, the initial matrix S has 2401 elements and is divided into 7 columns of 343 rows, each of these 7 columns itself being divided into 7 sub-columns of 49 elements.
In a preferred embodiment, one chooses: &lgr;=1. In other words, in this preferred embodiment, when implementing the steps described above, one works with full columns rather than with sub-columns.
To be specific, in this first aspect of the invention, this preferred embodiment relates to a permutation method, causing an output rank from 0 to r·m−1 to correspond to each input rank from 0 to r·m−1, the said method including the followings steps:
E1—a matrix S having r rows and m columns is considered, filled row by row by the successive numbers from 0 to r·m−1,
E2—the m columns of S are designated by S
l
with 0≦I≦m−1,
E3—each column S
l
is then written in the form of a matrix with R rows and M columns, where R and M satisfy RM=r, and in this form it is interleaved by an interleaver of the so-called “wheel” type, defined by a circular permutation of each column in said matrix with R rows and M columns, said interleaver not being identity,
E4—this matrix with R rows and M columns is reconverted, after said circular permutations on its columns, into a column S*
l
which will occupy, in a matrix S*, the same position as that occupied by S
l
in the matrix S,
E5—each column S*
l
in the matrix S* is permuted by means of a circular permutation,
E6—the permutation table consists of pairs each formed by an element of the matrix S and the element with the same position in the matrix S*.
It will be understood that in this way a permutation table has indeed been created which makes an output rank correspond to each input rank, this permutation table then advantageously being able to be used as a data transfer device, for example using convolutional data turbodecoding.
According to various provisions, possibly used in conjunction, favourable to an effective implementation of this preferred embodiment of the invention:
at least two columns in the matrix S* are obtained by using different whee
Le Dantec Claude
Piret Philippe
Canon Kabushiki Kaisha
Fitzpatrick ,Cella, Harper & Scinto
LandOfFree
Interleaving method for the turbocoding of data does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Interleaving method for the turbocoding of data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interleaving method for the turbocoding of data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2955856