Granted Patent B2

US 8,386,552 · App. 12/211,892 · Granted Feb 26, 2013

Abstract

Claims (39)

1. In a data processing system having a twiddle factor unit, a method for performing a mixed-radix discrete Fourier transform (DFT) having a block size, N, and a maximum block size, Nmax, wherein the maximum block size includes a radix that is not a power of 2, the method comprising:

receiving a delta value at an input of the twiddle factor unit, the delta value representing a ratio of a modified maximum block size to the block size, wherein the modified maximum block size is a power of 2;

using the delta value to obtain a step size for generating indices of a look-up table stored within the twiddle factor unit, wherein the look-up table stores real and imaginary components of twiddle factors corresponding to a set of block sizes of the DFT; wherein the look-up table includes a precoded communication signal based on the twiddle factors; and

in response to each generated index, outputting from the look-up table, a real and imaginary component of the twiddle factor corresponding to the DFT having the block size N, and providing the precoded communication signal for an up-link transmission to a base station.

2. The method of claim 1 , further comprising:

receiving a time domain signal; and

using the real and imaginary components of the twiddle factor to generate a frequency domain signal corresponding to the time domain signal.

3. The method of claim 2 , wherein the time domain signal is further characterized as a non-precoded communication signal.

4. The method of claim 2 , wherein the time domain signal is further characterized as a precoded communication signal.

5. The method of claim 1 , further comprising using the delta value to obtain a starting value for generating the indices.

6. The method of claim 5 , wherein the using the delta value to obtain a starting value comprises using the delta value to obtain a plurality of starting values, each corresponding to a different twiddle factor generator, each twiddle factor generator including a look-up table.

7. The method of claim 6 , further comprising:

using the step size and the plurality of starting values to generate corresponding indices for each of the different twiddle factor generators, wherein each twiddle factor generator, in response to each corresponding generated index, in parallel, outputs a real and imaginary component of a twiddle factor.

8. The method of claim 1 , further comprising rounding each generated index prior to outputting the real and imaginary component of the twiddle factor.

9. The method of claim 1 , wherein the block size, N, includes a radix that is not a power of 2.

10. A data processing system which performs a mixed-radix discrete Fourier transform (DFT) having a block size, N, and a maximum block size, Nmax, wherein the maximum block size includes a radix that is not a power of 2, the data processing system comprising:

a twiddle factor unit which outputs a plurality of twiddle factors, the twiddle factor unit comprising:

an input which receives a delta value representing a ratio of a modified maximum block size to the block size, wherein the modified maximum block size is a power of 2;

an increment calculator which uses the delta value to generate a step size;

a start value calculator which uses the delta value to generate a plurality of start values; and

a plurality of twiddle factor generators, each twiddle factor generator comprising a first look-up table storing first components of twiddle factors corresponding to a set of block sizes of the DFT and a second look-up table storing second components of the twiddle factors corresponding to the set of block sizes of the DFT, wherein the first look-up table and second look-up table includes a precoded communication signal based on the twiddle factors; and wherein each twiddle factor generator uses the step size and a corresponding one of the plurality of start values to generate indices for each of the first and second look-up tables, and, in response to each generated index, provides a real component and an imaginary component, from the first and second look-up tables, of a twiddle factor corresponding to the DFT having the block size, N, and provides the precoded communication signal for an up-link transmission to a base station.

11. The data processing system of claim 10 , further comprising:

an input which receives a time domain signal;

an arithmetic logic unit which applies the twiddle factors corresponding to the DFT having the block size, N, to generate a frequency domain signal corresponding to the time domain signal.

12. The data processing system of claim 10 , wherein each twiddle factor generator further comprises a rounding unit which rounds each generated index prior to providing the real and imaginary components of the twiddle factor corresponding to the DFT having the block size, N.

13. The data processing system of claim 10 , further comprising:

an input which receives a precoded communication signal; and

circuitry which uses the twiddle factors corresponding to the DFT having the block size, N, to decode the communication signal.

14. The data processing system of claim 10 , wherein the block size, N, includes a radix that is not a power of 2.

15. A method, comprising:

receiving a discrete Fourier transform (DFT) block size, N, wherein the block size N includes a first radix that is a power of 2 and a second radix that is not a power of 2;

generating an exponent corresponding to each of the first radix and the second radix;

using the generated exponents to generating a first delta value representing a ratio of a maximum block size to the block size, wherein the maximum block size includes at least one radix that is not a power of 2;

generating a second delta value representing a ratio of a modified maximum block size to the block size, wherein the modified maximum block size is a power of 2;

based on the second delta value, generating at least one look-up table corresponding to twiddle factors of the DFT having the block size, N; and

storing the at least one look-up table for use in performing a DFT transform of a communications signal.

16. The method of claim 15 , wherein generating the at least one look-up table comprises:

generating a first look-up table corresponding to first components of the twiddle factors of the DFT having the block size, N; and

generating a second look-up table corresponding to second components of the twiddle factors of the DFT having the block size, N, wherein, for each twiddle factor, the first component is one of a real or imaginary component and the second component is another one of the real or the imaginary component.

Assignments (16)