Method and apparatus for reordering mixed radix fast Fourier transform outputs

Patent metadata

Field	Value
Publication number	US-9805000-B1
Application number	US-201514811981-A
Country	US
Kind code	B1
Filing date	Jul 29, 2015
Priority date	Jul 29, 2015
Publication date	Oct 31, 2017
Grant date	Oct 31, 2017

Abstract

Fast Fourier Transform (FFT) operates by decomposing a longer length input signal into many smaller length signals. The decomposition may be carried out in different number of smaller length signals at each stage. The number of smaller length signals at each stage is referred to as a radix. FFT may be implemented either with decimation in time or with decimation in frequency method. Depending on the method used, reordering of the input or the output data sequence may be required in order to get the data sequence in the correct order. Mixed radix FFT is an FFT structure that uses a combination of radixes. The reordering for mixed radix FFT by bit reversing or digit reversing the index has non-trivial complexity. A method and apparatus are disclosed that enable efficient and zero latency reordering of a data sequence for an FFT structure that uses a combination of two or more radixes.

First claim

The invention claimed is:

1. A method for reordering an index of a data point in a signal output from a Fast Fourier Transform (FFT) performed on an input signal by an FFT structure using a number of radix stages, wherein one of the radix stages is of a radix type different from a radix type of another of the radix stages, the method comprising:
generating, by a processing device, a reordered index for the data point in the signal output which is a natural order index of the data point in the signal output, in which the reordered index of the data point in the signal output is expressed using a base numbering convention as a base number having J digits, in which a value of J corresponds to a total number of the radix stages used in the FFT structure and in which each digit of the base number corresponds to a respective one radix stage of the radix stages,
wherein the processing device is configured as a base ripple counter including a plurality of stages corresponding respectively to the radix stages of the FFT structure,
wherein each of the stages corresponds to a mod-r counter of the base ripple counter, in which r is the radix of the corresponding radix stage in the FFT structure, and wherein the mod-r counters are arranged in a same order as an order in which the radix stages are arranged in the FFT structure,
wherein the mod-r counters are connected asynchronously such that a trailing edge of a most significant output of a first mod-r counter of a first stage of the stages triggers a second mod-r counter of a second stage of the stages, the second stage being next in the order after the first stage,
wherein the reordered index for the data point in the signal output has values respectively of the mod-r counters in the order of the mod-r counters, for the digits respectively of the base number, and
wherein the generating of the reordered index is started before the FFT on the input signal by the FFT structure is completed.

2. The method of claim 1 , further comprising:
clocking, by the processing device, the base ripple counter by a same clock used to control the FFT structure.

3. The method of claim 2 , wherein the reordered index for the data point in the signal output is available when the data point in the signal output is available from the FFT structure.

4. The method of claim 1 ,
wherein a weight of a given digit in the reordered index, the given digit being other than a least significant digit in the reordered index, is a product of a weight of a next least significant digit in the reordered index and a value of the radix corresponding to the next least significant digit, and
wherein a weight of the least significant digit in the reordered index is equal to one.

5. The method of claim 4 further comprising:
determining, by the processing device, for each of the digits of the reordered index, a product of a value of the digit and the weight of the digit, and
determining, by the processing device, a sum of the products, wherein the sum is a natural binary representation of an index value of the data point in the signal output.

6. The method of claim 1 , wherein the FFT structure implements a Decimation-In-Time (DIT) method or a Decimation-In-Frequency (DIF) method.

7. The method of claim 6 , wherein, when the FFT structure implements the Decimation-In-Time (DIT) method, the reordered index for the data point in the output signal is for a signal output from a FFT butterfly operation.

8. The method of claim 6 , wherein, when the FFT structure implements the DIF method, the reordered index for the data point in the output signal is for a signal input to a FFT butterfly operation.

9. An apparatus for reordering an index of a data point in a signal output from a Fast Fourier Transform (FFT) performed on an input signal by an FFT structure using a number of radix stage, wherein one of the radix stages is of a radix type different from a radix type of another of the radix stages, the apparatus comprising:
circuitry configured to generate a reordered index for the data point in the signal output which is a natural order index of the data point in the signal output, in which the reordered index of the data point in the signal output is expressed using a base numbering convention as a base number having J digits, in which a value of J corresponds to a total number of the radix stages used in the FFT structure and in which each digit of the base number corresponds to a respective one radix stage of the radix stages,
wherein the circuitry is configured as a base ripple counter including a plurality of stages corresponding respectively to the radix stages of the FFT structure,
wherein each of the stages corresponds to a mod-r counter of the base ripple counter, in which r is the radix of the corresponding radix stage in the FFT structure, and wherein the mod-r counters are arranged in a same order as an order in which the radix stages are arranged in the FFT structure,
wherein the mod-r counters are connected asynchronously such that a trailing edge of a most significant output of a first mod-r counter of a first stage of the stages triggers a second mod-r counter of a second stage of the stages, the second stage being next in the order after the first stage,
wherein the reordered index for the data point in the signal output has values respectively of the mod-r counters in the order of the mod-r counters, for the digits respectively of the base number, and
wherein the circuitry is configured to start to generate the reordered index before the FFT on the input signal by the FFT structure is completed.

10. The apparatus of claim 9 ,
wherein each of the stages is configured by least one flip-flop.

11. The apparatus of claim 9 ,
wherein clocking of the base ripple counter is by a same clock used to control the FFT structure.

12. The apparatus of claim 9 ,
wherein a weight of a given digit in the reordered index, the given digit being other than a least significant digit in the reordered index, is a product of a weight of a next least significant digit in the reordered index and a value of the radix corresponding to the next least significant digit, and
wherein a weight of the least significant digit in the reordered index is equal to one.

13. The apparatus of claim 12 ,
wherein the circuitry is configured to determine, for each of the digits of the reordered index, a product of a value of the digit and the weight of the digit, and
wherein the circuitry is configured to determine a sum of the products, wherein the sum is a natural binary representation of an index value of the data point in the signal output.

14. The apparatus of claim 9 , wherein the FFT structure implements a Decimation-In-Time (DIT) method or a Decimation-In-Frequency (DIF) method.

15. A wireless communication device comprising:
a receiver to receive an input signal; and
a processing device for reordering an index of a data point in a signal output from a Fast Fourier Transform (FFT) performed on the input signal by an FFT structure using a number of radix stages, wherein one of the radix stages is of a radix type different from a radix type of another of the radix stages,
where the processing device is configured to generate a reordered index for the data point in the signal output which is a natural order index of the data point in the signal output, in which the reordered index of the data point in the signal output is expressed using a base numbering convention as a base number having J digits, in which a value of J corresponds to a total number of the radix stages used in the FFT structure and in which each digit of the b

Assignees

• Mbit Wireless Inc

Inventors

• Jeyachandra Angelin
• Patel Bhaskar

Classifications

• G06F17/142 Primary

  Fast Fourier transforms, e.g. using a Cooley-Tukey type algorithm · CPC title