Block interleaver and de-interleaver with buffer to reduce...

Details Block interleaver and de-interleaver with buffer to reduce... Block interleaver and de-interleaver with buffer to reduce...

2000-07-05

2003-09-23

Moise, Emmanuel L. (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Data formatting to improve error detection correction...

C714S701000, C714S702000, C341S081000, C711S217000

Reexamination Certificate

active

06625763

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to block interleaver and de-interleaver structures for changing the orders of values in a data stream.
RELATED ART
Interleavers are memory structures widely used in wireless communications, where streams of data (e.g., voice data) must be transmitted through the air from a source device to a receiver. Groups of sequential bits in these streams of data are subject to noise errors (i.e., value changes during transmission) in the presence of a burst noise event or during fading of the transmission signal.
To protect against noise, conventional systems implement error correction schemes in which the source device adds redundant bits to the data stream, and the receiver implements an algorithm to detect and correct noise errors. Most error correction schemes work reasonably well as long as the erroneous bits are spread throughout the bit stream (after the addition of the error-correction bits). Unfortunately, these error correction schemes fail to correct continuous sequences of erroneous bits.
An interleaver/de-interleaver system is typically used to enable the correction of continuous sequences of erroneous bits in the transmitted data stream. In such a system, an interleaver is provided in the source device to scramble the order of the bits of the data stream prior to transmission. A de-interleaver is provided in the receiver to de-scramble the order of the bits after transmission, thereby reconstructing the data stream in the original order. A noise event occurring during transmission will therefore corrupt sequential bits in the scrambled data stream, which correspond with non-sequential bits in the original data stream. Thus, after the de-interleaver de-scrambles the order of the bits, the erroneous bits will be spread throughout the data stream. A conventional error correction scheme can then be applied to the data stream provided by the de-interleaver to correct the erroneous bits. A basic description of interleavers is provided in U.S. Pat. No. 3,652,998 by Forney.
A commonly used method of interleaving is block interleaving. In this method, the data to be transmitted is divided to blocks, typically of equal length. Each block is interleaved separately. At the receiver, blocks are de-interleaved and concatenated again to form a continuous bit stream.
In a simple interleaving scheme, a special random access memory (RAM) is used to perform the interleaving. Sequential data values are written into the RAM in row order, and then read out of the RAM in column order. In this manner, the sequential data values are scrambled. For example, sequential data values D
1
-D
12
would be written into a 3×4 RAM in row order as defined below in Table 1.
TABLE 1
Column 1
Column 2
Column 3
Row 1
D1
D2
D3
Row 2
D4
D5
D6
Row 3
D7
D8
D9
Row 4
D10
D11
D12
When the data values are sequentially read from columns
1
,
2
and
3
of the RAM (i.e., in column order), the order of the data values D
1
-D
12
will be: D
1
, D
4
, D
7
, D
10
, D
2
, D
5
, D
8
, D
11
, D
3
, D
6
, D
9
, and D
12
. This is the order in which the data values are transmitted.
Although Table 1 defines a block interleaver having a size of twelve bits, in practice, much longer interleaver blocks are used to protect against longer bursts of noise and fading periods. For example, interleaver blocks of more than 20,000 bits are used in most of the 3
rd
generation telephony standards (when high bit rates are transmitted).
More complex block interleaver schemes include permutation of order in which the columns are read. For example, data values might be sequentially read from columns
1
,
3
and
2
of the RAM. In this case, the order of the transmitted data values will be D
1
, D
4
, D
7
, D
10
, D
3
, D
6
, D
9
, D
12
, D
2
, D
5
, D
8
and D
11
.
Static RAM (SRAM) devices are typically used to implement block interleavers. Because an access of a large SRAM device consumes a relatively high power, it is desirable to minimize the number of SRAM accesses in the process of block interleaving.
In general, power consumption of an SRAM device may be reduced if the memory word width is large, so that several bits are accessed at the same time. But for a block interleaver, the SRAM device is written in rows and read in columns. If the SRAM block interleaver is arranged so that each row stores one or more memory words, then each write operation to the SRAM block interleaver can be performed one or more word at a time, in a power-efficient manner. However, read operations from the SRAM block interleaver must be performed in a per-column manner, with one memory-read cycle required for every bit read (a full word will be read, but only one of the bits will be used).
Returning to Table 1, and assuming a word length of 3 bits (a full row), the block interleaver will be written during four cycles. Thus, during a first cycle, data values D
1
-D
3
are written to Row
1
, during a second cycle, data values D
4
-D
6
are written to Row
2
, during a third cycle, data values D
7
-D
9
are written to Row
3
, and during a fourth cycle, data values D
10
-D
12
are written to Row
4
.
It will take twelve cycles to extract the twelve data values D
1
-D
12
from the block interleaver. Table 2 defines these twelve cycles.
TABLE 2
Cycle
Action
1
Extract D1 by reading Row 1 (D1, D2, D3) and
ignoring D2, D3
2
Extract D4 by reading Row 2 (D4, D5, D6) and
ignoring D5, D6
3
Extract D7 by reading Row 3 (D7, D8, D9) and
ignoring D8, D9
4
Extract D10 by reading Row 4 (D10, D11, D12) and
ignoring D11, D12
5
Extract D2 by reading Row 1 (D1, D2, D3) and
ignoring D1, D3
6
Extract D5 by reading Row 2 (D4, D5, D6) and
ignoring D4, D6
7
Extract D8 by reading Row 3 (D7, D8, D9) and
ignoring D7, D9
8
Extract D11 by reading Row 4 (D10, D11, D12) and
ignoring D10, D12
9
Extract D3 by reading Row 1 (D1, D2, D3) and
ignoring D1, D2
10
Extract D6 by reading Row 2 (D4, D5, D6) and
ignoring D4, D5
11
Extract D9 by reading Row 3 (D7, D8, D9) and
ignoring D7, D8
12
Extract D12 by reading Row 4 (D10, D11, D12) and
ignoring D10, D11
In general, if the word length is W and the block interleaver memory size is M bits, where M is a multiple of W, then an interleaving procedure will have a duration of M/W write cycles and M read cycles.
If an SRAM block interleaver is selected where columns are configured to store words, then M/W read cycles will be required, thereby making the read operations more efficient. However, such a configuration would require M write cycles, thereby making the write operations less efficient. As a result, power consumption will remain high.
It would therefore be desirable to have a block interleaver capable of overcoming the deficiencies of the described prior art, thereby exhibiting reduced power consumption.
SUMMARY
The present invention provides a block interleaver that includes a relatively small register file and a larger interleaver RAM. In one embodiment, the size of the interleaver RAM is larger than the size of the register file by at least one order of magnitude. As a result, the register file consumes significantly less power than the interleaver RAM for similar operations.
The register file is used for intermediate storage of the data values (bits or symbols) in a sequential input data stream. Data values to be written into the interleaver RAM are first written to the register file in a column order. Then, the data values are transferred from the register file to the interleaver RAM in a row order. This transfer is performed using write operations to the interleaver RAM, wherein the width of the write operations is equal to the full width of the interleaver RAM. In one embodiment, the data values are written to the interleaver RAM in a staggered row order. In another embodiment, the data values are written to the interleaver RAM in a row order, which is selected to implement a permutation of a column order of the original data stream.
Data values are then read from the interleaver RAM in a row order, thereby creating an interleaved data stream. Each of these read operations has a width eq

Affiliated with

Also associated with

Rating

Block interleaver and de-interleaver with buffer to reduce... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Block interleaver and de-interleaver with buffer to reduce..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Block interleaver and de-interleaver with buffer to reduce... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3067051