Methods and apparatus for reordering data
View Patent ↗A data reordering system for determining addresses associated with a vector of transformed data and corresponding method of reordering transformed data, where the data reordering system includes: a first transform function coupled to a data vector and operable to provide the vector of transformed data; a reordering function, including a plurality of counters, that is operable to determine a plurality of offset addresses, with a, respective, offset address for each element in the vector of transformed data; and an adder operable to add a base address that corresponds to the first address to the each, respective, offset address to provide a sequence of addresses suitable for accessing the vector of transformed data to provide a re-sequenced vector of transformed data.
1. A method of reordering transformed data, the method comprising:
providing a sequence of transformed data;
determining, using a plurality of counters suitably arranged and selectively configured each with a programmable step size and programmable maximum value, an address for each element of the sequence of transformed data, the address defining an address relative to a first address for a first element of the sequence of transformed data, the address used to reorder the transformed data; and
using the sequence of transformed data in accordance with the address for each element of the sequence of transformed data,
wherein the determining an address further comprises concatenating the plurality of counters and wherein, when one counter reaches its corresponding maximum value, another counter begins to count to provide a count, and
wherein an output of the one counter is a sequence corresponding in part to the address for each element of the sequence of transformed data.
2. The method of claim 1 wherein the sequence of transformed data includes a sequence of Fast Fourier transform (FFT) coefficients from a mixed radix FFT and wherein the determining an address further comprises configuring each of the plurality of counters with a, respective, step size and maximum value each depending on a radix corresponding to each respective counter.
3. The method of claim 2 wherein the concatenating the plurality of counters occurs in an order based on a corresponding stage of transformation, and wherein, when a first counter reaches its corresponding maximum value, a second counter begins to count to provide a second count, the second count used to reinitialize the first counter, and
wherein an output of the first counter is a sequence of addresses comprising the address for each element of the sequence of transformed data.
4. The method of claim 1 wherein:
the providing a sequence of transformed data comprises providing a N point sequence of Fast Fourier transform (FFT) coefficients from a mixed radix FFT algorithm using R sequential radix r_i stages, the product of all r_i equal to N;
the determining an address further comprises concatenating R counters, with each counter programmed to have a step size and a maximum value that is a function of one or more of the r_i; and
when a given counter reaches its maximum value, a subsequent counter begins to count to provide a subsequent count that is used to reinitialize all earlier counters, and when an Rth counter reaches its maximum value, the method is complete and an output of a first counter is a sequence of addresses comprising the address for each element of the sequence of transformed data.
5. The method of claim 1 wherein the determining an address further comprises:
using a first counter to provide a pointer address;
using the pointer address to retrieve a first value from a lookup table (LUT);
using a second counter to provide a second value; and
combining the first value and the second value to provide the address.
6. The method of claim 5 further comprising bit reversing an output of the second counter to provide the second value and wherein the combining the first value and the second value further comprises adding the first value and the second value to provide the address.
7. The method of claim 5 wherein:
the providing a sequence of transformed data comprises providing a sequence of Fast Fourier transform (FFT) coefficients from a mixed radix FFT algorithm; and
the determining an address further comprises configuring the first counter with a first maximum value and configuring the second counter with a second maximum value.
8. The method of claim 7 wherein:
the configuring the first counter with a first maximum value further includes programming the first counter with a first maximum value that is based on a product of non radix 2 stages in the mixed radix FFT algorithm; and
the configuring the second counter with a second maximum value further comprises programming the second counter with a second maximum value based on a product of radix 2 stages in the mixed radix FFT algorithm.
9. The method of claim 7 further comprising loading the LUT with a number of entries based on the first limit value.
10. The method of claim 7 further comprising:
counting with the first counter from an initial value to the first maximum value; and
when the first counter reaches the first maximum value, triggering the second counter for a count and resetting the first counter to the initial value.
11. A data reordering system including circuitry for determining addresses associated with a vector of transformed data, the data reordering system comprising:
a first transform function coupled to a data vector and operable to provide the vector of transformed data;
a reordering function including a plurality of counters selectively configured each with a programmable step size and programmable maximum value, the reordering function operable to determine a plurality of offset addresses, with a, respective, offset address for each element in the vector of transformed data, each, respective, offset address defining an address relative to a first address for a first element in the vector of transformed data; and
an adder operable to add a base address, corresponding to the first address, to the each, respective, offset address to provide a sequence of addresses suitable for accessing the vector of transformed data to provide a re-sequenced vector of transformed data,
wherein the plurality of counters are concatenated in an order and wherein, when one counter reaches a predetermined value, another counter begins to count to provide another count, and
wherein an output of the one counter is a sequence corresponding in part to the address for each element of the sequence of transformed data.
12. The data reordering system of claim 11 further comprising a second transform function suitably configured to access the re-sequenced vector of transformed data and provide a vector of inverse transformed data.
13. The data reordering system of claim 12 further comprising a bit reversing function coupled to the adder and operable such that each of the sequence of addresses includes a bit reversed portion and the vector of inverse transformed data is in a linear order.
14. The data reordering system of claim 11 wherein the first transform function is operable to perform a mixed radix Fast Fourier transform (FFT) on the data vector and provide the vector of transformed data as a vector of Fast Fourier transform (FFT) coefficients and wherein each of the plurality of counters is programmed with a, respective, step size and maximum value.
15. The data reordering system of claim 14 wherein the plurality of counters are concatenated in an order based on a corresponding radix, and wherein, when a first counter reaches its corresponding maximum value, a second counter begins to count to provide a second count, the second count used to reinitialize the first counter, and
wherein an output of the first counter is a sequence of addresses comprising the offset address for each element of the vector of transformed data.
16. The data reordering system of claim 11 further comprising:
a look up table (LUT);
a first counter to provide a sequence of pointer addresses, the sequence of pointer addresses for retrieving a sequence of first values from the LUT; and
a second counter to provide a sequence of second values;
wherein the adder is further operable to combine, respective, first values and second values from the sequence of first values and the sequence of second values to provide the sequence of addresses.
17. The data reordering system of claim 16 further comprising:
a bit reversing function operable to bit reverse outputs of the second counter to provide the sequence of second values; and
wherein the adder is further operable to add, respective, first values and second values from the sequence of first values and the sequence of second values to provide the sequence of addresses.
18. The data reordering system of claim 16 :
wherein the first transform function is operable to perform a mixed radix Fast Fourier transform (FFT) on the data vector and provide the vector of transformed data as a vector of Fast Fourier transform (FFT) coefficients;
wherein the first counter is programmed with a first maximum value based on a product of all non radix 2 stages in the FFT and the second counter is programmed with a second maximum value based on a product of all radix 2 stages in the FFT; and
wherein the LUT comprises a LUT with a number of entries based on the first limit value.
19. The data reordering system of claim 18 wherein the first counter is operable to sequentially count from an initial value to the first maximum value; and
when the first counter reaches the first maximum value, trigger the second counter for a count and reset the first counter to the initial value.
20. A data reordering system including circuitry for determining addresses associated with a vector of transformed data, the data reordering system comprising:
a first transform function coupled to a data vector and operable to perform a mixed radix fast Fourier transform (FFT) to provide a vector of FFT coefficients;
a reordering function including a plurality of counters selectively configured each with a programmable step size and programmable maximum value, the reordering function operable to determine a plurality of offset addresses, with a, respective, offset address for each element in the vector of FFT coefficients, each, respective, offset address defining an address relative to a first address for a first element in the vector of FFT coefficients;
an adder operable to add a base address that corresponds to the first address to the each, respective, offset address to provide a sequence of addresses suitable for accessing the vector of FFT coefficients to provide a re-sequenced vector of FFT coefficients; and
a second transform function operable to access the vector of FFT coefficients in accordance with the sequence of addresses and provide a vector of inverse FFT data that is in monotonically increasing order,
wherein the plurality of counters are concatenated in an order based on a corresponding radix, and wherein, when a first counter reaches its corresponding maximum value, a second counter begins to count to provide a second count, the second count used to reinitialize the first counter, and
wherein an output of the first counter is a sequence of addresses comprising the offset address for each element of the vector of transformed data.