Address generator for interleaving data

Details Address generator for interleaving data Address generator for interleaving data

2000-01-14

2003-04-15

Nguyen, Hiep T. (Department: 2187)

Electrical computers and digital processing systems: memory

Address formation

Combining two or more values to create address

C711S211000, C370S320000

Reexamination Certificate

active

06549998

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to processing of a data stream in a communication system, and, more particularly, to interleaving data bits in segments of a data stream.
2. Description of the Related Art
Interleaving is a commonly employed technique for processing a data stream in communication systems. Interleaving generally comprises receiving N+1 data values (where N+1 is the length of the data stream segment and N is an integer greater than one), and rearranging the order of the N+1 values. Interleaving may be employed, for example, to remove non-random sequences of values in a data stream, or may be employed to reduce effects of burst errors inserted into the data as the segment of data passes through a transmission medium. Such rearranging of data values may be considered to be a mapping ƒ(*) as illustrated in FIG.
1
. As shown in
FIG. 1
, an interleaver maps the address indices daddr (
0
) to daddr (
3
) of data values d(
0
)-d(
3
) in the segment to corresponding interleaved address indices addr (
0
) to addr (
3
) in the interleaved segment. A receiver reverses the interleaving of the data values by de-interleaving. The mapping may be of two forms. Either sequential data values are inserted into an interleaved output corresponding to the sequence of interleaved address indices (i.e., reading serial data into interleaved data in a buffer), or the sequence of interleaved address indices are used to access and output data values in corresponding memory addresses (i.e., reading serial data out of a buffer as interleaved data.
For example,
FIG. 2
shows a method of generating a sequence of interleaved addresses from a counter for a mapping operation ƒ(*) specified for an interleaver operating in accordance with the CDMA 2000 standard of the prior art for turbo encoding of data segments. In accordance with the CDMA 2000 standard, the frame size (N
turbo
+1) is the length of the segment of the data stream to be interleaved. The mapping operation ƒ(*) maps a linear sequence of data addresses {daddr(
0
), daddr(
1
), . . . , daddr(N
turbo
)} of the segment into a permuted sequence of interleaved data addresses {addr(
0
), addr(
1
), . . . , addr(N
turbo
)}.
At step
201
, an (n+5)-bit counter is initialized to 0, where n is the smallest integer such than the frame size (N
turbo
+1) is less than or equal to 2
n+5
. At step
202
, then most significant bits (MSBs) are extracted from the output value of the counter and one is added to the value formed from the n MSBs. At step
203
, the n least significant bits (LSBs) are retained from the result obtained in step
202
. At step
204
, the n-bit output value of a 32-entry look-up table (such as the table defined in the CDMA 2000 standard) is retrieved using the address formed from the 5 LSBs of the counter output of step
202
. At step
205
, the n-bit output value from the 32-entry look-up table obtained in step
204
is multiplied with the result of step
203
, and the n LSBs are retained from the result.
At step
206
, a tentative address is formed from the n LSBs obtained in step
205
. The tentative address is formed by (a) bit-reversal of the 5 LSBs of the counter output to form the 5 MSBs of the tentative address, and (b) appending the results of step
205
as the n LSBs of the tentative address. At step
207
, a test determines if the tentative output address value is less than or equal to N
turbo
. If the tentative address value is less than or equal to N
turbo
, then the address is accepted at step
208
as an interleaved data address of the interleaved segment. If the tentative address value is less than N
turbo
, then the tentative address is discarded at step
209
.
At step
210
, a test determines if all interleaved data addresses addr(
0
), addr(
1
), . . . , addr(N
turbo
) have been generated. If so, the mapping operation ends; otherwise, the counter is incremented at step
211
, and the mapping operation returns to step
202
to generate the next address.
For an implementation of an interleaver using the mapping operation shown in
FIG. 2
, a multiplier is employed in step
205
, and an extra iteration is required each time the tentative address formed at step
206
is not within the frame size.
SUMMARY OF THE INVENTION
In accordance with exemplary embodiments of the present invention, an interleaver includes a mapping operation that generates interleaved data addresses for a frame of data values without employing multiplication. In addition, embodiments of the present invention may generate valid interleaved data addresses for each iteration of the mapping operation.
An interleaver employing a mapping operating in accordance with the present invention generates an interleaved address for one sequence of data values by generating at least two counter values, each counter value having a predetermined offset from each other counter value. A bit-reversed value, an index value, and an accumulated value are retrieved for each of the counter values, wherein each of the bit-reversed, index, and accumulated values are identified by an address formed from a portion of the corresponding counter value. A tentative address is formed for each counter value from the corresponding bit-reversed, index, and accumulated values, and the one or more tentative addresses are compared with a threshold to generate a select value, the threshold based on the length of the sequence of data values. The interleaved address is then set as one of the tentative addresses based on the select value.
For further exemplary embodiments, a test determines whether an interleaved address is set for each of the sequence of data values, and, if not, each counter is incremented by a substantially equivalent increment value, the increment value determined by the counter value generating the tentative address set as the interleaved address. A new accumulated value is then set for the accumulated value identified by the portion of the corresponding counter value generating the tentative address set as the interleaved address, the new accumulated value representing one or more combinations of the index value identified by the corresponding portion of the counter value. An interleaver may repeat generating interleaved addresses until each of the sequence of data values is assigned to a corresponding interleaved address.


REFERENCES:
patent: 5638467 (1997-06-01), Chua et al.
patent: 6064664 (2000-05-01), Kim
patent: 6304581 (2001-10-01), Chen et al.
patent: 6314534 (2001-11-01), Agrawal et al.
patent: 6334197 (2001-12-01), Eroz et al.

Affiliated with

Also associated with

Rating

Address generator for interleaving 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 Address generator for interleaving data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Address generator for interleaving data will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3065014