Error detection/correction and fault detection/recovery – Pulse or data error handling – Data formatting to improve error detection correction...
Reexamination Certificate
2000-02-28
2004-03-02
Chung, Phung M. (Department: 2784)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Data formatting to improve error detection correction...
Reexamination Certificate
active
06701467
ABSTRACT:
FIELD OF INVENTION
The invention concerns an interleaver device for interleaving a data set comprising a data processor for running an interleaver under the control of driving means and an input means for inputting the data set to be interleaved and output means for outputting the interleaved data set.
BACKGROUND OF INVENTION
Such interleaver devices are specially useful in mobile telephones.
An interleaver is usually applied on informations transmitted on a radio channel between two radio stations.
In other technical fields, interleavers are also used for instance on data stored on a magnetic tape or a laser disk.
Turbo decoders have proved to offer near Shannon limit error protection in the case of white additive gaussian noise. One key feature of the Turbo encoder is an interleaver.
Interleaving data with a depth of N consists in:
writing N consecutive symbols of data into a buffer of size of N symbols, i
th
written symbol is written at position (i−1), and then
read them in another order given by some permutation I of {0, . . . , N−1}. i
th
read symbol is read from position I(i−1).
In other words if i is the original position of a symbol in an input block, then I
−1
(i) is its position in the output block, where I
−1
denotes the inverse permutation of I.
Deinterleaving data with a depth of N consists in:
writing N consecutive symbols of data into a buffer of size of N symbols, i
th
written symbol is written at position I(i−1), and
then and then read them in another order given by some permutation I on {0, . . . , N−1}. i
th
read symbol is read from position i−1.
To implement the interleaver and the deinterleaver, function is needed that provides the mapping I. With some simple permutation I, this mapping can be computed by a simple analytical formula that can be quickly evaluated on any known per se processing means. For instance if the interleaver is a rectangular interleaver with L lines and C columns, we have:
N=L·C
∀
i
∈{0
, . . . , N
−1
}I
−1
(
i
)=(
i
div
C
)+(
i
mod
C
)·
L
(1)
In this formula (x div y) stands for the quotient of x divided by y in an Euclidian division and (x mod y) stands for the remainder in the same division.
The way this formula is to be understood is quite simple: a rectangular interleaver consists of an array of L lines and C columns. The input data is written along the lines and read along the column.
If l is line number (from 0 to L−1) and c is a column number (from 0 to C−1) of some written symbol then writing along the line comes to:
c=i
mod
C
(2)
l=i
div
C
(3)
that is to say:
i=l·C+c
(4)
l and c are the co-ordinate of the (i+1)
th
written symbol.
Reading along the columns comes to:
I
−1
(
i
)=
l+c·L
(5)
Note that as a matter of fact, equations (4) and (5) are similar when column and line roles are inverted. By substituting equations (3) and (2) in equation (5), we get equation (1) that shows that the I mapping can be obtained by simple arithmetic computations in the case of a rectangular interleaver.
However interleavers so simple as the rectangular interleaver do not always fit the needs of a forward error coding technique. In particular, in the case of the turbo encoding, the rectangular interleaver shows very poor performance. The interleaver to be used in the turbo encoder must be more random than the regular rectangular interleaver, and however not completely random as it must still keep some good properties of spacing interleaved symbols.
The simplest way to implement that kind of interleaver is to use a table where the i
th
entry in the table is the value of I(i−1). The size of the table is directly derived from N, that is to say that at least s(N) bits are needed to implement the table where:
s
(
x
)=
x
·┌log
2
(
x
)┐ (6)
log
2
(x) denotes the logarithm in base two of x, and ┌x┐ denotes the ceiling of x, that is to say the least integer not less than x. When N grows bigger, then the amount of memory needed to store the table also grows bigger.
SUMMARY OF INVENTION
The aim of the invention is to provide an interleaver device which can run with very little memory to store the definition of the interleaver, even if the interleaver definition is very complex.
To this end, the invention relates to an interleaver device as defined in claim 1.
According to particular embodiments, the interleaver device may include one or more of the features defined in subclaims.
The invention proposes a method to build interleavers that are not so regular as the plain rectangular interleaver and nevertheless use far less memory than a completely tabulated interleaver.
In the case of a mobile telephone, due to real time constraint, it might be necessary to tabulate the interleaver of the invention to be able to use it, since processing the values might take too much time. However the definition can be very concise, thus holding little space in ROM. The interleaver table can held in RAM and computed off-line, during connection establishment. After call completion, the RAM can be reused for another purpose. Thus, even if the interleaver needs to be tabulated into RAM for effective use, this is all the same favourable, because the RAM can be used for something else when the call type does not need the interleaver.
Another advantage of having a concise definition from which a very large interleaver can be generated, is that a great variety of interleavers can be defined in the ROM memory, and only one of them selected at connection time.
In a particular embodiment, the interleaver definition could be transmitted over the air, as a parameter of the connection. The interleaver definition would have to follow the mobile telephone if during a hand over of the site where the interleaving is performed in the network is changed. Therefore, the next site would need to compute or select the table fast if enough during the hand over preparation time.
REFERENCES:
patent: 5136588 (1992-08-01), Ishijima
patent: 5592492 (1997-01-01), Ben-Efraim et al.
patent: 5907560 (1999-05-01), Spruyt
patent: 2 507 844 (1982-12-01), None
patent: WO 95/18489 (1995-07-01), None
patent: WO 96/37050 (1996-11-01), None
patent: WO 97/05702 (1997-02-01), None
Chung Phung M.
Mitsubishi Electric Telecom Europe
LandOfFree
Interleaver device and method for interleaving a data set does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Interleaver device and method for interleaving a data set, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interleaver device and method for interleaving a data set will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3292240