Data element interleaving/deinterleaving

Details Data element interleaving/deinterleaving Data element interleaving/deinterleaving

1998-01-27

2001-02-20

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

06192493

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention concerns the interleaving and deinterleaving of data elements in consecutive data blocks of a digital signal.
The data elements can be binary elements or symbols, or groups of bits such as words occupying time slots in a frame of a time-division or frequency-division multiplex signal. The blocks can be protocol data units, for example, such as packets or frames, or data fields in packets or frames, or lines or fields of a digital television signal. To give one more example, a block can comprise PQ bits divided into P groups each of Q bits frequency-division multiplexed onto P respective carriers.
2. Description of the Prior Art
In an emitter, interleaving consists in ordering the elements in each block in a manner differing from the initial order of the elements so that initially consecutive data elements are separated by a relatively large number of other data elements in the block of interleaved elements to be emitted. Thus interleaving contributes to at least partial alleviation of the phenomenon of fading on a transmission path between the emitter and a receiver by introducing time-domain or frequency-domain diversity into the digital signal. In practice the data elements for forming blocks of interleaved elements are interleaved in an interleaver connected for example to the output of an error correcting encoder, also known as a channel encoder, and to the input of a modulator. Conversely, the initial digital signal is reconstituted in the receiver by deinterleaving interleaved elements in each block using a deinterleaver for example connected between a demodulator and a channel decoder.
In one implementation known in itself interleaving consists in writing the data elements of each block in their natural order of arrival into a memory circuit and then reading the data elements of the block in accordance with a predetermined interleaving function.
The memory circuit comprises two RAM memories arranged in parallel and each containing N data element cells. The integer N denotes the number of data elements in each block. One of the memories is being written while the other memory is being read in one block period in two, and vice versa in the next block period. If n varying from 0 through N−1 denotes the rank of a data element in an incoming block and t denotes the duration of a data element, the data elements e
0
, . . . e
n
, . . . e
N−1
of a first incoming block BE
0
of duration Nt are written successively at times 0, . . . nt, . . . (N−1)t into the cells of a first of the memories having addresses 0, . . . n, . . . N−1. Then, during the next block period [Nt, (2Nt−1)) t], the data elements of a second incoming block BE
1
are written into the cells of the second memory while the data elements of the first preceding block BE
0
are read in the first memory using read addresses P(0), . . . P(n), . . . P(N−1). P denotes the predetermined interleaving function which establishes a biunivocal correspondence between a write address n and a read address P(n). After all the elements of the first block have been read in their entirety in the first memory, the second memory is read using the address function P(n) to interleave the data elements of the second block. Thus the blocks with an even rank are read and written in the first memory and the blocks with an odd rank are read and written in the second memory.
To reduce the cost of interleaving, consideration can be given to using only a single memory of size N having an incoming data bus for the incoming blocks of elements and an outgoing data bus for the interleaved elements of the outgoing blocks. If W(nt) and R(nt) denote the write and read addresses at time nt of a block period, in each unit time period nt it is necessary to read a data element of a previously written block and to write a data element of a subsequent block in the same cell. In other words, it is necessary to satisfy the equation W(nt)=R(nt).
Assuming that the memory is emptied in order to write into it a first incoming block B
0
, the elements e
0, 0
to e
0
, (N−1) of the block B
0
are written successively into the cells with addresses R
0
(0t)=0 through R
0
((N−1) t)=N−1. In the second following block period, in the cells with addresses R
1
(0t)=P(0) through R
1
((N−1)t)=P(N−1), the interleaved elements of the first block B
0
are read successively in accordance with the interleaving function P, and the elements e
1, 0
through e
1
, (N−1) of the next block B
1
are written successively. Thus the read address R
1
(nt) at time nt in the second block period is equal to the write address W
0
(P(n)t)=P(n). More generally, for the block of rank k the following recurrence equation must be satisfied:
R
k
(
nt
)=W
k−1
(P(
n
)
t
),
i.e., R
k
(nt)=R
k−1
(P(n)t).
Knowing that R
0
(nt)=n, then R
1
(nt)=P(n), . . . thus R
k
(nt)=P
k
(n).
Accordingly the element of rank P(n) of the block B
k−1
that was written at time P(n)t of the period for writing block B
k−1
is read at time nt of the period for writing the next block B
k
and has the rank n in the interleaved block. This time correspondence is equivalent to that between the reading of the element e
n
of one block in one of the two memories at time P(n)t and the writing of the element e
n
at time nt during the previous block period, as in the known implementation.
To apply the interleaving function P to each block write/read period, a series of addresses must be produced that is different from one write/read period to the next. If k increases and N is large, it is very difficult to produce all the series of addresses.
Nevertheless, for particular interleaving functions, an addressing cycle appears. After q block write/read periods, the initial series of addresses 0 through N−1 recurs:
R
q
(
nt
)=W
q
(
nt
)=
n
In other words, the minimal integer q satisfying the equation P
q
(n)=n is relatively small.
For example, an interleaving function of the type
P(
n
)=(
a
.(
n
+1)+
b
)[modulo N]
defined in patent application FR-A-2706054 satisfies this objective. For example, if n varies from 0 to N−1=16, a=4 and b=0, with reference to
FIG. 2
of the aforementioned patent application, q=4 series of addresses are needed to find again to the initial series of addresses 0 through 16, as shown in the following table:
n
P(n)
P
2
(n)
P
3
(n)
P
4
(n) = n
0
4
3
16
0
1
8
2
12
1
2
12
1
8
2
3
16
0
4
3
4
3
16
0
4
5
7
15
13
5
6
11
14
9
6
7
15
13
5
7
8
2
12
1
8
9
6
11
14
9
10
10
10
10
10
11
14
9
6
11
12
1
8
2
12
13
5
7
15
13
14
9
6
11
14
15
13
5
7
15
16
0
4
3
16
OBJECT OF THE INVENTION
The present invention aims to reduce the addressing cycle inherent to the use of a single memory for interleaving data elements block by block and consequently to reduce the complexity of the means needed to produce the memory addresses. The equation P
q
(n)=n, that is to say P
4
(n)=n from the above table, imposes a high constraint on the function P.
SUMMARY OF THE INVENTION
Accordingly, a method of modifying the order, i.e. interleaving (or deinterleaving), of data elements in first and second blocks transmitted alternately and each having N data elements with ranks n lying between 0 and N−1, N being an integer, is characterized in that the data elements with ranks 0, . . . n, . . . N−1 in the first blocks are ordered in accordance with the successive ranks A(0), A(n), . . . A(N−1) and the data elements with numbers 0, . . . n, . . . N−1 in the second blocks are ordered in accordance with the successive ranks A
−1
(0), . . . A
−1
(n), . . . A
−1
(N), A and A
−1
being different first and second functions such that A
−1
(A(n))=n.
In practice, the following operations are performed in a memory having N data element cells with addre

Affiliated with

Also associated with

Rating

Data element interleaving/deinterleaving does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Data element interleaving/deinterleaving, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data element interleaving/deinterleaving will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2611985