US 6,549,998 B1 · Address generator for interleaving data

Abstract

An interleaver generates a valid interleaved data address for each iteration i of the mapping by the interleaver without employing a multiplication operation. The interleaver includes an address generator comprises two counters, bit-reverse and index tables, and an accumulation register array. The interleaver further comprises two adders, two registers storing tentative address values addressi and addressi+1, and select logic including a comparator, two buffers, and a multiplexer (mux). Two counters are employed to allow the interleaver to generate at least one valid address for each iteration, and a tentative address is generated from each output value of the two counters. Each iteration generates an output interleaved address. A tentative address is generated by using a portion of the counter value as an address to select a corresponding entry from each of the bit-reverse and index tables and the accumulation register array. The selected values from the index table and accumulation register array are combined in an adder. The value selected from the bit-reverse table is appended to the combination of the selected values from the index table and accumulation register array to form the tentative address. The tentative address generated from the first counter value is compared with a threshold value, and, based on the comparison, one of the two tentative addresses is selected as the output interleaved address. Before beginning the next iteration, the accumulated value used in generating the valid output interleaved address is updated to a new accumulated value. If not all output interleaved addresses have been generated, the counters are incremented by the same increment value, the increment value dependent upon the comparison with the threshold value, and the next iteration begins.

Claims22

Dependent claims

A method of generating an interleaved address for one of a sequence of data values comprising the steps of:

(a) generating at least two counter values, each counter value having a predetermined offset from each other counter value;
(b) retrieving a bit-reversed value, an index value, and an accumulated value 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;
(c) forming a tentative address for each counter value from the corresponding bit-reversed, index, and accumulated values;
(d) comparing one or more tentative addresses with a threshold to generate a select value, the threshold based on the length of the sequence of data values;
and
(e) setting the interleaved address as one of the tentative addresses based on the select value.

3 more elements

Circuit for generating an interleaved address for one of a sequence of data values comprising:

a counter generating at least two counter values, each counter value having a predetermined offset from each other counter value and a portion of each counter value provided as a corresponding address signal, wherein, for each of the counter values, one of a plurality of bit-reversed values, one of a plurality of index values, and one of a plurality of accumulated values are identified by the corresponding address signal;
an adder generating, for each counter value, a combination of the index and accumulated values identified by the corresponding address signal of the counter value, wherein a tentative address is generated for each counter value by appending the bit-reverse value identified by the corresponding address signal to the combination provided by the adder for the corresponding counter value;
and
a comparator providing a select signal based on a comparison of one or more tentative addresses with a threshold, the threshold based on the length of the sequence of data values;
wherein the interleaved address is set as one of the tentative addresses based on the select signal.

2 more elements

A computer-readable medium having stored thereon a plurality of instructions, the plurality of instructions including instructions which, when executed by a processor, cause the processor to implement a method of generating an interleaved address for one of a sequence of data values, the method comprising the steps of:

(a) generating at least two counter values, each counter value having a predetermined offset from each other counter value;
(b) retrieving a bit-reversed value, an index value, and an accumulated value 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;
(c) forming a tentative address for each counter value from the corresponding bit-reversed, index, and accumulated values;
(d) comparing one or more tentative addresses with a threshold to generate a select value, the threshold based on the length of the sequence of data values;
and
(e) setting the interleaved address as one of the tentative addresses based on the select value.

3 more elements

Dependencies are inferred from the claim text.

Address generator for interleaving data

Life of this patent

Address generator for interleaving data

Life of this patent

Abstract

Claims22