Realizing method and device of fast Fourier transform
Realizing method and device of fast Fourier transform
 CN 101,551,790 A
 Filed: 04/03/2008
 Published: 10/07/2009
 Est. Priority Date: 04/03/2008
 Status: Active Application
First Claim
1. fast fourier transform implementation method is carried out Fourier transform after being used for the data that receive are overflowed control, it is characterized in that, comprising:
 According to the exponent number of the data that receive, predetermined interval is divided into a plurality of subranges;
Obtain the shift value of each data in the data that receive, and therefrom obtain the shift value of absolute value maximum, wherein, described shift value is represented the position relation of the residing subrange of described data with respect to the appointment subrange in described a plurality of subranges;
Utilize the described shift value of absolute value maximum that described each data are made amendment respectively, obtain corresponding to the new data behind described each data modification;
Described new data is carried out fast fourier transform.
Chinese PRB Reexamination
Abstract
The invention provides a realizing method of fast Fourier transform, which is used for controlling the overflow of received data and then carrying out the Fourier transform. The realizing method of the fast Fourier transform comprises the following steps: dividing a predetermined area into a plurality of subareas according to the exponent number of received data; obtaining a shifting value of each datum of the received data and also obtaining a shifting value with a maximal absolute value from the obtained shifting values; utilizing the shifting value with the maximal absolute value to respectively modify each datum and obtaining new modified data corresponding to each datum; and carrying out the fast Fourier transform for the new data, wherein the shifting values express the position relation of the subarea where the data locating relative to a pointed subarea of the subareas. Besides, the invention also provides a realizing device of the fast Fourier transform. The invention can ensure the calculation precision under the precondition of overflow control and can also reduce the utilization of circuit resources, lower the circuit cost and enhance the qualification rate of circuits.

4 Citations
A kind of device for realizing Fast Fourier Transform (FFT)  
Patent #
CN 107,291,660 A
Filed 06/15/2017

Current Assignee

Fast Fourier transform system based on residue number system  
Patent #
CN 102,184,160 A
Filed 05/18/2011

Current Assignee

Signal harmonic analysis method for using fast triangularform Fourier transform  
Patent #
CN 105,137,176 A
Filed 08/12/2015

Current Assignee

Blockfloatingpoint method for FFT (fast Fourier transform) processor  
Patent #
CN 106,354,693 A
Filed 08/29/2016

Current Assignee

No References
10 Claims

1. fast fourier transform implementation method is carried out Fourier transform after being used for the data that receive are overflowed control, it is characterized in that, comprising:

According to the exponent number of the data that receive, predetermined interval is divided into a plurality of subranges; Obtain the shift value of each data in the data that receive, and therefrom obtain the shift value of absolute value maximum, wherein, described shift value is represented the position relation of the residing subrange of described data with respect to the appointment subrange in described a plurality of subranges; Utilize the described shift value of absolute value maximum that described each data are made amendment respectively, obtain corresponding to the new data behind described each data modification; Described new data is carried out fast fourier transform.


2. method according to claim 1 is characterized in that described predetermined interval is set to [0,1].

3. method according to claim 1 and 2 is characterized in that, the processing that described predetermined interval is divided into described a plurality of subranges is specially:
Utilize following formula to determine the size in each subrange according to the exponent number of the described data that receive;
[1/2 ^{N1}, 1/2 ^{n}), wherein, n=0,1,2 ..., m, and m is the exponent number of the described data that receive.

4. method according to claim 3 is characterized in that, determines that the processing of the shift value of described each data is specially:

Described a plurality of subranges are numbered since 1 with interval order from big to small, and with the subrange of maximum as described appointment subrange; Determine the shift value of described each data;
SHIFT=4Tk respectively by following formula, wherein, SHIFT is a shift value, and Tk is the numbering in the residing subrange of data.


5. method according to claim 3, it is characterized in that, in described a plurality of data is under the situation of nonreal number, for described each data, determines its real part and the imaginary part numbering in residing subrange respectively, and determine the shift value of described each data according to following formula:
 SHIFT=3min (nxk, nyk), wherein, SHIFT is the shift value of data, nxk is that the subrange at the real part place of described data number subtracts 1, and nyk is that the subrange at the imaginary part place of described data number subtracts 1.

6. method according to claim 1 is characterized in that, the processing that utilizes the described shift value of absolute value maximum that described each data are made amendment respectively is specially:

If the described shift value of absolute value maximum is a positive number, then described each data multiply by 2 SHIFT power respectively, and wherein, SHIFT is a shift value; If the described shift value of absolute value maximum is a negative, then described each data are respectively divided by 2SHIFT power, and wherein, SHIFT is a shift value.


7. according to each described method in the claim 1 to 6, it is characterized in that be not under the data conditions in described subrange in existence, the exponent number of the described data that the shift value of these data is set to receive adds 1.

8. according to each described method in the claim 1 to 6, it is characterized in that, after carrying out described fast fourier transform, further comprise:
According to reference information, the data of carrying out after the fast fourier transform are regulated, specifically comprise;
will carry out that data after the fast fourier transform multiply by t power of 2 or divided by 2 t power, wherein, t is the natural number of determining according to described reference information.

9. fast fourier transform implement device carries out Fourier transform after being used for the data that receive are overflowed control, it is characterized in that, comprising:

Power detector, be used for exponent number according to the data that receive, predetermined interval is divided into a plurality of subranges, and the shift value that obtains each data in the data that receive, and therefrom obtain the shift value of absolute value maximum, wherein, described shift value is represented the position relation of the residing subrange of described data with respect to the appointment subrange in described a plurality of subranges; First power governor is used to utilize the described shift value of absolute value maximum that described each data are made amendment respectively, obtains corresponding to the new data behind described each data modification; Fourier transform module is used for described new data is carried out fast fourier transform.


10. device according to claim 9 is characterized in that, further comprises:
Second power governor, be used for according to reference information, the data of carrying out after the fast fourier transform are regulated, specifically comprise;
will carry out that data after the fast fourier transform multiply by t power of 2 or divided by 2 t power, wherein, t is the natural number of determining according to described reference information.
Specification(s)