Pulse or digital communications – Receivers
Reexamination Certificate
1999-04-21
2004-10-26
Tran, Khai (Department: 2631)
Pulse or digital communications
Receivers
Reexamination Certificate
active
06810091
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a deinterleaver for deinterleaving data that has been transmitted in an interleaved format.
It is common practice in communications equipment, data storage devices, etc. to interleave transmitted data for suppressing burst errors produced in data transfer and to restore the data at the receiver by use of a deinterleaver.
The following interleaving/deinterleaving technique is known in the art. As shown in
FIG. 6
, with respect to interleaved data, 32 bits of data comprise a word, and 32 words (1024 bits) comprise a block. In each block, each word is separated into four phases a-d, and data is multiplexed so that words with four alternating phases are arranged. In transmitting data, bit lines and word lines are interchanged to interleave a block of data. In particular, each data item as shown in
FIG. 6
is identified by [phase name], [word number], and ([bit number]). After the interleaving process is completed, data is transmitted, 1 bit at a time, in the order a
0
(
0
) , b
0
(
0
) , c
0
(
0
) , d
0
(
0
) , a
1
(
0
) , . . . , d
6
(
31
), a
7
(
31
), b
7
(
31
), c
7
(
31
), d
7
(
31
).
Data interleaved in the above matter have been deinterleaved by a deinterleaver having the following structure. The deinterleaver is comprised of a first 1024-bit RAM permitting data to be read and written, 1 bit at a time, to interchange bit lines and word lines; a second 1024-bit RAM for separation of phases; and the respective address counters for the first RAM and second RAM. Let RA[
9
,
8
,
7
,
6
,
5
) be the higher significant 5-bit address lines for specifying higher significant addresses of the 1024 bits in the first RAM permitting data to be read and written, 1 bit at a time, and RA[
4
,
3
,
2
,
1
,
0
] be the lower significant 5-bit address lines for specifying lower significant addresses. The output from the address counter consisting of 10 bits for addressing is divided into higher significant 5 bits and lower significant 5 bits, which are indicated by CA[
9
,
8
,
7
,
6
,
5
] and CA[
4
,
3
,
2
,
1
,
0
], respectively. For convenience, RA[
9
,
8
,
7
,
6
,
5
] is given by RA[
9
:
5
].
The higher significant 5-bit output CA[
9
:
5
] and the lower significant 5 bit output CA[
4
:
0
] can be alternately coupled to the address lines RA[
9
:
5
] and RA[
4
:
0
] by selectors. Thus, whenever writing of a block of data is completed, the higher significant 5-bit output and the lower significant 5-bit output from the address counter are interchanged and the data written to RAM is read out. Every subsequent block written to RAM is directly written into the address from which data has been just read out. Consequently, bit lines and word lines are interchanged.
Specifically, with respect to the first block, the higher significant 5-bit output and the lower significant 5-bit output from the address counter are not interchanged and written without modification as illustrated in FIG.
7
. In this figure, the rows indicate higher significant addresses
0
-
31
in the RAM specified by the higher significant 5-bit output from the address counter and the columns indicate lower significant addresses
0
-
31
specified by the lower significant 5-bit output. For convenience, the higher and lower significant addresses are represented in decimal notation and in the description given below, decimal notation is also used. Similar rules are applied to the addresses in the storage device specified by higher and lower significant addresses. With respect to the first block, writing is done in the direction of rows. As a result, data is written into the RAM while interchanging the word lines and bit lines of the original data format shown in FIG.
6
. Then, the higher significant 5 bits and the lower significant 5 bits of the output from the address counter are interchanged and read out in the direction of columns. More specifically, with respect to the lower significant address
0
shown in
FIG. 7
, data is read out up to higher significant addresses
0
-
31
. Then, with respect to lower significant address
1
, data are read out up to higher significant addresses
0
-
31
. In this way, data is read out up to the final lower significant address
31
. The word lines and bit lines are again interchanged to regain the original data format shown in
FIG. 6
, in outputting data. One bit of data is output at a time in the order a
0
(
0
), a
0
(
1
), a
0
(
31
), b
0
(
0
), . . . , b
0
(
31
), c
0
(
0
), . . . , c
0
(
31
), d
7
(
0
), d
7
(
31
). Simultaneously with the reading, data in the second block is written, 1 bit at a time, into the address just read out. When the writing of the data in the second block is complete, a data array as shown in
FIG. 8
is obtained. Subsequently, the higher significant bits and the lower significant bits of the output from the address counter are again interchanged and data is read out. Concurrently, data in the third block are written as it is into the address of the data just read.
Words with phases a-d cyclically appear at the output data of the RAM. It is necessary to perform phase separation (i.e., words must be rearranged according to each of the phases a-d). Therefore, an output consisting of an array of words with the alternating phases a-d is once stored in the second 1024-bit RAM in the same format as shown in FIG.
6
. Then, the first four words are read by means of a separate address counter. Thus, all the words with the phase a are read out of RAM. Next, all the words with the phase b are read out. Similar reading operations are performed for the phases c and d. In consequence, phase separation is done. Hence, data is read, 1 bit at a time, from the second RAM in the order a
0
(
0
), a
0
(
1
), . . . , a
0
(
31
), a
1
(
0
), a
1
(
31
), . . . , a
7
(
31
), b
0
(
0
), . . . , b
7
(
31
), . . . , d
7
(
31
).
As described above, the prior art deinterleaver rearranges bit lines and word lines of data and then separates words according to the phases. Therefore, two RAMs for holding data and associated address counters have been required. For this reason, a memory having a capacity twice as large as the data amount of data in a block is required. Furthermore, a control unit for this memory is necessary. Consequently, the size of the deinterleaver is increased and its structure is complicated.
SUMMARY OF THE INVENTION
Accordingly, in the present invention, word lines and bit lines in each block where plural phases are cyclically assigned to each word are interchanged to deinterleave interleaved data. At this time, bit lines and word lines of the data are rearranged and simultaneous phase separation is performed in the manner described below.
A storage means has a storage area being a capacity corresponding to one block of data. The storage area has individual storage locations addressed by higher and lower significant addresses. Each bit of the above-described data is stored in each individual storage location in the storage means. Data is read, 1 bit at a time, from the storage means by specifying higher and lower significant addresses in turn. A newly incoming data item is written into the storage location just read out. Whenever a block of data is written, first and second count signals for specifying higher and lower significant addresses, respectively, are interchanged. At this time, a counting rule about the first and second count signals is cyclically changed as the phase is cyclically changed. In this manner, the word lines and bit lines are rearranged. A deinterleaved output is produced such that words are arranged according to phase. This can reduce the whole storage capacity to the amount of data corresponding to a block. Hence, the size of the apparatus can be reduced, and the structure can be simplified, thereby resulting in a highly cost-effective deinterleaver.
With a deinterleaver in accordance with the present invention, a word of data consists of 2
n
bits
Garces John C.
Lutzker Joel E.
Nippion Precision Circuits, Inc.
Schulte Roth & Zabel LLP
Tran Khai
LandOfFree
Digital data deinterleaver does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Digital data deinterleaver, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Digital data deinterleaver will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3300856