CN101763338A - Mixed base FFT/IFFT realization device with changeable points and method thereof - Google Patents

Abstract

The invention discloses a mixed-radix FFT/IFFT realization device and method thereof with variable points. The present invention is a dual-purpose system of FFT and IFFT, which realizes that the number of points can be allocated; two blocks of RAM are used in the transformation process, one of which only stores the input data, and when each operation completes its first-level butterfly operation, the RAM can be used Accept the data of the next operation, and save time when completing multiple consecutive operations; in addition, the method of combining base 4 and base 2 is used to realize the number of points of the L power of 2 (L is a positive integer greater than or equal to 3) FFT and IFFT operations, in the butterfly operation, use block floating-point operations, which solves the data bit width expansion caused by multiplication and addition in the butterfly operation process, saves storage space, and at the same time performs original address storage operations on the results to achieve approximation of interstage flow. The method and device have the characteristics of simple control, high efficiency, flexible configuration, good scalability and the like.

Description

A mixed-radix FFT/IFFT implementation device and method with variable number of points

technical field

The invention relates to a device and a method for implementing a mixed-radix FFT/IFFT with variable points.

Background technique

Discrete Fourier transform (DFT) is the most basic and commonly used operation in the field of digital signal processing. We can use DFT to perform digital spectrum analysis or digital filtering on signals. In addition, it will also be used in the design and implementation of various digital systems. Use DFT. However, at the beginning of the DFT operation, there was no good algorithm proposed. Therefore, the computational complexity of completing the DFT of N-point data was O(N ² ); until 1965, Cooley and Tukey published in "Mathematics of Computation "The article "Analgorithm for the machine computation of complex Fourier series" was published, marking the official birth of the Fast Fourier Transform (FFT) algorithm.

The introduction of the FFT algorithm is regarded as an important milestone in the history of digital signal processing. It reduces the computational complexity of DFT from O(N ² ) to O(Nlog ₂ N), which solves the bottleneck in the implementation and application of digital signal processing. It has strong theoretical and engineering significance. In various application fields of digital signal processing at present, FFT algorithm still plays a pivotal role: for example, FFT algorithm, as the basic algorithm of time domain and frequency domain conversion, is a necessary prerequisite for us to carry out digital spectrum analysis. In digital communication, Speech signal analysis, image processing, radar, and biomedical engineering have extremely wide applications; for example, in the case of digital speech coding, digital filtering, radio interference array, etc., it is necessary to use special FFT equipment to deal with this Real-time and fast calculation; especially, due to the rapid development of field programmable gate array (FPGA) in recent years, FPGA is very suitable for implementing FFT algorithm. For example, FPGA manufacturers Altera and Xlinx have developed corresponding FFT IP cores, and the price It is very expensive and cannot be widely used, so in practical engineering applications, it is particularly important to develop an FGPA-based FFT implementation method.

At present, the existing various fast algorithms for DFT calculation can be roughly divided into two categories: one is to convert DFT into convolution, and use the method of calculating convolution to calculate, which is represented by Winograd algorithm and prime factor algorithm; One is the recursive algorithm, which converts one-dimensional DFT into two-dimensional or multi-dimensional DFT that is easy to calculate, and this process can be repeated. Representative algorithms include Cooley-Tukey algorithm, Rader-Brenner algorithm and split basis algorithm. Compared with the above two types of algorithms, the former has an advantage in the amount of calculation, and the use of multipliers is less than that of the latter, but the control logic is more complicated, and the control unit is relatively troublesome to implement.

Contents of the invention

The purpose of the present invention is to overcome the deficiencies of the prior art, and provide a mixed-radix FFT/IFFT implementation device and method thereof with variable points.

The mixed-radix FFT/IFFT implementation device with variable points includes modules: input data transformation module, storage module A, data selector, butterfly operation module, overflow detection module, storage module B, shift module, output data transformation module and control module, the input data conversion module is connected to the storage module A, data selector, butterfly operation module, overflow detection module, storage module B, and shift module in sequence, the storage module B is connected to the output data conversion module, and the shift module is connected to the data selection module Under the control of the control module, the serial input data is converted and stored in the storage module A, and then the control module controls all the data in the storage module A to complete the first-level butterfly operation, and the result is overflow detection and is also stored in the storage Module B; when all the data in the storage module A have completed the first-level butterfly operation, the control module sends out a sign signal that the storage module A is free and available, indicating that the next calculation data can be input, and at the same time the control module controls the shifting The bit module, the storage module B, the butterfly operation module and the overflow detection module complete all subsequent butterfly operations; when all the butterfly operations are completed, the control module controls the storage module B and the output data transformation module, and converts the storage module B to After shifting and transforming the real and imaginary parts, the final block floating-point calculation result is output after serial reading of the data. When all the data in the storage module B is output, the output data conversion module gives the control module the free and available flag of the storage module B. signal, a new FFT/IFFT operation starts.

The butterfly operation module includes a connected twiddle factor storage module, a multiplier module and an adder module.

The mixed-radix FFT/IFFT implementation method with variable points comprises the following steps:

1) According to whether the operation is FFT or IFFT, under the control of the control module, the serial input data is processed and stored in the storage module A in a block-by-block reverse order;

2) After the processed serial input data are all written into the storage module A, the control module controls the storage module A, the butterfly operation module, and the overflow detection and judgment module, and reads four data from the storage module A to complete a base-4 butterfly Shape operation; after performing overflow detection and judgment on the butterfly operation result data, it is stored in the storage module B according to the original address. When all the data in the storage module A have completed the first-level butterfly operation, the control module sends out a signal, and the The data stream of an FFT or IFFT operation enters the storage module A;

3) Record the points of FFT or IFFT operation as N, and N=2 ^L , L is a positive integer greater than or equal to 3: if L is an even number, the number of butterfly operation stages is L/2; if L is an odd number, Then the number of stages of the butterfly operation is (L+1)/2, under the control of the control module, L is the second stage to the L/2 stage in the case of an even number or the second stage to the ( Each butterfly operation of level L-1)/2 reads four data from storage module B, completes a radix-4 butterfly operation after being shifted by the shift module, and stores the result at the original address after being judged by overflow detection into the storage module B; when L is an odd number, the (L+1)/2-level butterfly operation reads two data from the storage module B each time, and performs the base-2 butterfly operation under the control module, and the result Store in storage module B according to the original address after overflow detection and judgment;

4) After all the butterfly operations are completed, according to this operation as FFT or IFFT, the data in the storage module B is processed accordingly and then serially output to obtain the FFT or IFFT block floating-point operation results of the input data. The result is combined with the final output block floating-point exponent into the actual FFT or IFFT result.

Described according to this calculation is FFT or IFFT, under the control of the control module, the steps of storing the serial input data into the storage module A according to the block flashback mode after processing include:

1) The input data of FFT/IFFT transformation is a complex number, the number of points is N, N=2 ^L , and L is greater than or equal to 3

If the input data requires FFT operation, the input complex data does not need to be processed; if the input data requires IFFT operation, the real part of the input complex data remains unchanged, and the imaginary part is reversed;

2) Storage module A includes four sub-storage modules of the same size, namely A1, A2, A3, and A4. The size of each sub-storage module is 2×b×N/4 bits, and b is the real or imaginary part of the input complex number The bit width bit number of the part, the processed data of N points serially input is x(n), wherein n=0,1,2,...,N-1, x(0)～x( N/4-1), x(N/4)～x(2N/4-1), x(2N/4)～x(3N/4-1) and x(3N/4)～x(N- 1) Store them in A1, A2, A3, and A4 in reverse order;

3) When the number of input data points reaches N, the control module sends an FFT/IFFT operation start signal.

After the processed serial input data are all written into the storage module A, the control module controls the storage module A, the butterfly operation module and the overflow detection and judgment module, and reads four data from the storage module A to complete a base-4 butterfly Shape operation; after performing overflow detection and judgment on the butterfly operation result data, it is stored in the storage module B according to the original address. When all the data in the storage module A have completed the first-level butterfly operation, the control module sends out a signal, and the The steps that the data stream of an FFT or IFFT operation can enter the storage module A include:

1) Read a piece of data from the sub-storage modules A1, A2, A3, and A4 respectively, and complete a radix-4 butterfly operation through three complex multiplications and eight complex additions;

2) perform overflow detection and judgment on the result of each butterfly operation, and write down the overflow bit number of the maximum value in the operation result;

3) The storage module B is also composed of four sub-storage modules, which are respectively sub-storage modules B1, B2, B3, and B4. After each butterfly operation, four data are written into the sub-storage modules B1, B2, B3, and B4. The address is equal to the read address of the sub-storage modules A1, A2, A3, A4;

4) Repeat the above three steps until all the data in the storage module A completes the butterfly operation, at this time the maximum overflow bit number is the final overflow bit number of the butterfly operation result of this level;

5) After all the data in the storage module A complete the first-stage butterfly operation, the control module sends a flag signal to the outside, indicating that the next FFT/IFFT data stream enters the storage module A in series and waits.

The number of points in the FFT or IFFT operation is recorded as N, and N=2 ^L , L is a positive integer greater than or equal to 3: if L is an even number, the number of butterfly operation stages is L/2; if L is an odd number , then the butterfly operation series is (L+1)/2. Under the control of the control module, each butterfly operation from the second stage to the L/2th stage when L is an even number or from the second stage to the (L-1)/2th stage when L is an odd number is from Four data are read in the storage module B, and a base-4 butterfly operation is completed after being shifted by the shift module, and the result is stored in the storage module B according to the original address after overflow detection and judgment; when L is an odd number, 1)/2-level butterfly operation reads two data from storage module B each time, performs radix-2 butterfly operation under the control module, and stores the result in storage module B according to the original address after overflow detection and judgment include:

1) The butterfly operation from the second stage to the L/2 stage when L is an even number or from the second stage to the (L-1)/2 stage when L is an odd number, under the control of the control module, every time Read one piece of data from each of the sub-storage modules B1, B2, B3, and B4, and the data shift module performs shifting according to the overflow detection judgment result after the previous butterfly operation, and the shift result completes a radix-4 butterfly operation , the result is written into the sub-storage modules B1, B2, B3, and B4 according to the original address after overflow detection and judgment;

2) When L is an odd number, the (L+1)/2-th stage butterfly operation is a radix-2 butterfly operation. Under the control of the control module, first read out a piece of data from the sub-storage modules B1 and B3 respectively, After the shift, a radix-2 butterfly operation is completed, and the result is stored in the sub-storage modules B1 and B3 according to the original address after being judged by overflow detection, and so on until all the data in the sub-storage modules B1 and B3 complete the butterfly operation; after that, Combining sub-storage modules B2 and B4 to complete the same operations as sub-storage modules B1 and B3;

3) At this point, we have successfully completed all the butterfly operations of the N-point data FFT/IFFT operations, and the results are stored in the sub-storage modules B1, B2, B3, and B4.

After all the butterfly operations described above are completed, according to this operation being FFT or IFFT, the data in the storage module B is processed and then serially output to obtain the FFT or IFFT block floating-point operation results of the input data, and the The steps of combining the result with the final output block floating-point index into the actual FFT or IFFT result include:

1) Under the control of the control module, serially output the data from the sub-storage modules B1, B2, B3, and B4 in a certain order, and perform the following processing according to whether this operation is FFT or IFFT: if it is FFT, the real part and the imaginary part remain unchanged; if it is IFFT, the real part remains unchanged and the imaginary part is reversed;

2) After the conversion of the real part and the imaginary part is completed, according to the overflow detection judgment result of the last butterfly operation, the serial output data can be output after being shifted accordingly, and the output result is the FFT of the input N-point complex data /IFFT block floating-point calculation result, when all the N-point data is output, a flag signal is given to the control module, indicating that the storage module B is available, and a new FFT/IFFT operation can be performed;

3) The actual FFT/IFFT result is: X(k)=X′(k)*2 ^-exp (k=0, 1,...N-1, N is the number of input data points), where X(k) is the actual FFT/IFFT result, X'(k) is the FFT/IFFT block floating-point operation result, and exp is the block floating-point exponent.

The described actual FFT/IFFT result is: X(k)=X'(k)*2 ^-exp , k=0,1,...,N-1, N is the number of input data points, where X(k ) is the actual FFT/IFFT result, X'(k) is the FFT/IFFT block floating point operation result, and exp is the block floating point index. The steps include:

1) When the operation type is FFT, the initial value of exp is 0; when the operation type is IFFT, the initial value of exp is log ₂ N;

2) After each level of butterfly operation, exp is equal to the value before the start of butterfly operation of this level minus the number of overflow bits of butterfly operation of this level. After all butterfly operations are completed, the obtained exp is the final block float exponent;

3) The actual FFT/IFFT result X(k) can be obtained through the final block floating point result X'(k) and the block floating point exponent exp, X(k)=X'(k)*2 ^-exp ,k =0, 1, ..., N-1, N is the number of input data points.

The present invention is a dual-purpose system of FFT and IFFT, which sends the points to be transformed to the controller, so that the points can be allocated; two pieces of storage RAM are used in the transformation process, one of which is used to store the input data, so that each time When the FFT/IFFT operation completes its first-stage butterfly operation, the RAM can be used to accept the data of the next operation, which saves time when realizing multiple consecutive FFT/IFFT operations; in addition, base-4 and base- The method of combining 2 realizes the FFT and IFFT operation of any number of L powers of 2 (L is a positive integer greater than or equal to 3). In the butterfly operation, the block floating point operation is used, that is, the result of the butterfly operation is performed The overflow detection and judgment processing solves the expansion of the data bit width caused by multiplication and addition in the butterfly operation process, saves storage space, and at the same time performs the in-site storage operation on the result to realize the approximate butterfly operation inter-stage pipeline.

Description of drawings

Fig. 1 is all modules of the present invention and connection block diagram;

Fig. 2 is the circuit block diagram of butterfly computing module among the present invention;

Fig. 3 is the change diagram of the number of bits of the block floating-point mechanism in the present invention;

Fig. 4 is a flow chart of block floating point operation in the present invention.

Detailed ways

As shown in Figure 1, the variable-point mixed-radix FFT/IFFT implementation device includes modules: input data conversion module, storage module A, data selector, butterfly operation module, overflow detection module, storage module B, shift module, The output data transformation module and the control module, the input data transformation module is connected with the storage module A, the data selector, the butterfly operation module, the overflow detection module, the storage module B, and the shift module in sequence, and the storage module B is connected with the output data transformation module, The shift module is connected to the data selector; under the control of the control module, the serial input data is converted and stored in the storage module A, and then the control module controls all the data in the storage module A to complete the first-level butterfly operation, and the overflow detection is completed as a result , and also stored in the storage module B; when all the data in the storage module A have completed the first-level butterfly operation, the control module sends out a sign signal that the storage module A is free and available, indicating that the next calculation data can be input , while the control module controls the shift module, the storage module B, the butterfly operation module and the overflow detection module to complete all subsequent butterfly operations; when all the butterfly operations are completed, the control module controls the storage module B, the output data conversion module , read the data in the storage module B serially and output the final block floating-point operation result after shifting and transforming the real part and the imaginary part. When all the data in the storage module B is output, the output data conversion module gives the control module The storage module B is idle and available flag signal, and a new FFT/IFFT operation starts.

As shown in Figure 2, the butterfly operation module includes a connected twiddle factor storage module, a multiplier module and an adder module.

The mixed-radix FFT/IFFT implementation method with variable points comprises the following steps:

1) According to whether the operation is FFT or IFFT, under the control of the control module, the serial input data is processed and stored in the storage module A in a block-by-block reverse order;

2) After the processed serial input data are all written into the storage module A, the control module controls the storage module A, the butterfly operation module, and the overflow detection and judgment module, and reads four data from the storage module A to complete a base-4 butterfly Shape operation; after performing overflow detection and judgment on the butterfly operation result data, it is stored in the storage module B according to the original address. When all the data in the storage module A have completed the first-level butterfly operation, the control module sends out a signal, and the The data stream of an FFT or IFFT operation enters the storage module A;

3) Record the points of FFT or IFFT operation as N, and N=2 ^L , L is a positive integer greater than or equal to 3: if L is an even number, the number of butterfly operation stages is L/2; if L is an odd number, Then the number of stages of the butterfly operation is (L+1)/2, under the control of the control module, L is the second stage to the L/2 stage in the case of an even number or the second stage to the ( Each butterfly operation of level L-1)/2 reads four data from storage module B, completes a radix-4 butterfly operation after being shifted by the shift module, and stores the result at the original address after being judged by overflow detection into the storage module B; when L is an odd number, the (L+1)/2-level butterfly operation reads two data from the storage module B each time, and performs the base-2 butterfly operation under the control module, and the result Store in storage module B according to the original address after overflow detection and judgment;

4) After all the butterfly operations are completed, according to this operation as FFT or IFFT, the data in the storage module B is processed accordingly and then serially output to obtain the FFT or IFFT block floating-point operation results of the input data. The result is combined with the final output block floating-point exponent into the actual FFT or IFFT result.

The described operation is FFT or IFFT according to this time, under the control of the control module, the steps of storing the serial input data into the storage module A according to the block flashback mode include;

1) The input data of FFT/IFFT transformation is a complex number, the number of points is N, N=2 ^L , L is a positive integer greater than or equal to 3, if the input data requires FFT operation, the input complex data does not need to be processed; if the input If the data requires IFFT operation, the real part of the input complex data remains unchanged, and the imaginary part is reversed;

In the embodiment, we set the value range of L to 5 to 14 according to the actual application requirements, that is, the range of the number of points N is a number that is a positive integer power of 2 between 32 and 16384, and the input N-point complex number The data is:

x(n)=I(n)+jQ(n) n=0, 1, 2,..., N-1(1)

I(n) in formula (1) is the real part of the input data, Q(n) is the imaginary part of the input data,

The expressions of FFT and IFFT operations of N-point input data are respectively:

${\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; FFT</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}}{\overset{\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; )</span>{\mathrm{<span\; class="notranslate">\; e</span>}}^{<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; j</span>}\frac{\mathrm{<span\; class="notranslate">\; 2</span>}\mathrm{<span\; class="notranslate">\; \&pi;</span>}}{\mathrm{<span\; class="notranslate">\; N</span>}}\mathrm{<span\; class="notranslate">\; nk</span>}}$

$<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}}{\overset{\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; I</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; jQ</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ]</span><span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; cos</span>}<span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; 2</span>}\mathrm{<span\; class="notranslate">\; \&pi;</span>}}{\mathrm{<span\; class="notranslate">\; N</span>}}\mathrm{<span\; class="notranslate">\; nk</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; 2</span>}\mathrm{<span\; class="notranslate">\; \&pi;</span>}}{\mathrm{<span\; class="notranslate">\; N</span>}}\mathrm{<span\; class="notranslate">\; nk</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ]</span>$

$=\mathrm{Re}\left\{x_{\mathrm{FFT}}\left(k\right)\right\}+\mathrm{jIm}\left\{x_{\mathrm{FFT}}\left(k\right)\right\}$ k=0, 1, 2, . . . , N-1(2)

In formula (2), $\mathrm{Re}\left\{x_{\mathrm{FFT}}\left(k\right)\right\}=\underset{\mathrm{no}=0}{\overset{N-1}{\mathrm{\&Sigma;}}}[I\left(\mathrm{no}\right)\cos \left(\frac{2\mathrm{\&pi;}}{N}\mathrm{nk}\right)+Q\left(\mathrm{no}\right)\sin \left(\frac{2\mathrm{\&pi;}}{N}\mathrm{nk}\right)]$

$\mathrm{<span\; class="notranslate">\; Im</span>}<span\; class="notranslate">\; \{</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; FFT</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \}</span><span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}}{\overset{\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; Q</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; cos</span>}<span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; 2</span>}\mathrm{<span\; class="notranslate">\; \&pi;</span>}}{\mathrm{<span\; class="notranslate">\; N</span>}}\mathrm{<span\; class="notranslate">\; nk</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; I</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; sin</span>}<span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; 2</span>}\mathrm{<span\; class="notranslate">\; \&pi;</span>}}{\mathrm{<span\; class="notranslate">\; N</span>}}\mathrm{<span\; class="notranslate">\; nk</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ]</span>$

${\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; IFFT</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; N</span>}}\underset{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}}{\overset{\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; )</span>{\mathrm{<span\; class="notranslate">\; e</span>}}^{<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; j</span>}\frac{\mathrm{<span\; class="notranslate">\; 2</span>}\mathrm{<span\; class="notranslate">\; \&pi;</span>}}{\mathrm{<span\; class="notranslate">\; N</span>}}\mathrm{<span\; class="notranslate">\; nk</span>}}$

$<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; N</span>}}\underset{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}}{\overset{\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; I</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; jQ</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ]</span><span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; cos</span>}<span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; 2</span>}\mathrm{<span\; class="notranslate">\; \&pi;</span>}}{\mathrm{<span\; class="notranslate">\; N</span>}}\mathrm{<span\; class="notranslate">\; nk</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; j</span>}\mathrm{<span\; class="notranslate">\; sin</span>}<span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; 2</span>}\mathrm{<span\; class="notranslate">\; \&pi;</span>}}{\mathrm{<span\; class="notranslate">\; N</span>}}\mathrm{<span\; class="notranslate">\; nk</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ]</span>$

$=\mathrm{Re}\left\{x_{\mathrm{IFFT}}\left(k\right)\right\}+\mathrm{jIm}\left\{x_{\mathrm{IFFT}}\left(k\right)\right\}$ k=0, 1, 2, . . . , N-1 (3)

In formula (3), $\mathrm{Re}\left\{x_{\mathrm{IFFT}}\left(k\right)\right\}=\frac{1}{N}\underset{\mathrm{no}=0}{\overset{N-1}{\mathrm{\&Sigma;}}}[I\left(\mathrm{no}\right)\cos \left(\frac{2\mathrm{\&pi;}}{N}\mathrm{nk}\right)+(-Q\left(\mathrm{no}\right))\sin \left(\frac{2\mathrm{\&pi;}}{N}\mathrm{nk}\right)]$

$\mathrm{<span\; class="notranslate">\; Im</span>}<span\; class="notranslate">\; \{</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; IFFT</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \}</span><span\; class="notranslate">\; =</span><span\; class="notranslate">\; -</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; N</span>}}\underset{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}}{\overset{\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}<span\; class="notranslate">\; [</span><span\; class="notranslate">\; (</span><span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; Q</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; cos</span>}<span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; 2</span>}\mathrm{<span\; class="notranslate">\; \&pi;</span>}}{\mathrm{<span\; class="notranslate">\; N</span>}}\mathrm{<span\; class="notranslate">\; nk</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; I</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; sin</span>}<span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; 2</span>}\mathrm{<span\; class="notranslate">\; \&pi;</span>}}{\mathrm{<span\; class="notranslate">\; N</span>}}\mathrm{<span\; class="notranslate">\; nk</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ]</span>$

In the present invention, FFT and IFFT adopt the same twiddle factor value, therefore, we take FFT as the standard, as can be seen from formulas (2) and (3), when completing the IFFT operation, we take the imaginary part of the input complex data as Perform FFT operation after inversion, and output the imaginary part of the final result after inversion, so that IFFT can be realized using the same control method as FFT, which simplifies the control logic of the intermediate butterfly calculation;

2) Storage module A includes four sub-storage modules of the same size, namely A1, A2, A3, and A4. The size of each sub-storage module is 2×b×N/4 bits, and b is the real or imaginary part of the input complex number The bit width bit number of the part, the processed data of N points serially input is x(n), wherein n=0,1,2,...,N-1, x(0)～x( N/4-1), x(N/4)～x(2N/4-1), x(2N/4)～x(3N/4-1) and x(3N/4)～x(N- 1) Store them in A1, A2, A3, and A4 in reverse order;

3) When the number of input data points reaches N, the control module sends an FFT/IFFT operation start signal.

After the processed serial input data are all written into the storage module A, the control module controls the storage module A, the butterfly operation module and the overflow detection and judgment module, and reads four data from the storage module A to complete a base-4 butterfly Shape operation; after performing overflow detection and judgment on the butterfly operation result data, it is stored in the storage module B according to the original address. When all the data in the storage module A have completed the first-level butterfly operation, the control module sends out a signal, and the The steps that the data stream of an FFT or IFFT operation can enter the storage module A include:

1) Read a piece of data from the sub-storage modules A1, A2, A3, and A4 respectively, and complete a radix-4 butterfly operation through three complex multiplications and eight complex additions;

Assuming that the data read from A1, A2, A3, and A4 are A, B, C, and D respectively, the base-4 butterfly operation expression is:

A'＝A+BW ^P +CW ^2P +DW ^3P ＝(A+CW ^2P )+(BW ^P +DW ^3P )(4.1)

B'＝A-jBW ^P -CW ^2P +jDW ^3P ＝(A-CW ^2P )-j(BW ^P -DW ^3P )(4.2)

C'＝A-BW ^P +CW ^2P -DW ^3P ＝(A+CW ^2P )-(BW ^P +DW ^3P )(4.3)

D'＝A+jBW ^P -CW ^2P -jDW ^3P ＝(A-CW ^2P )+j(BW ^P -DW ^3P )(4.4)

In formula (4.1)～(4.4), $W^P=W_N^k=e^{-j\frac{2\mathrm{\&pi;}}{N},}$

From formulas (4.1) to (4.4), it can be seen that the three complex multiplications required to complete a radix-4 butterfly operation are: BW ^P , CW ^2P , DW ^3P , and the eight complex additions are: A+CW ^2P , BW ^P +DW ^3P , A-CW ^2P , BW ^P -DW ^3P , the sum and difference of the former two and the sum and difference of the latter two;

2) perform overflow detection and judgment on the result of each butterfly operation, and write down the overflow bit number of the maximum value in the operation result;

3) The storage module B is also composed of four sub-storage modules, which are respectively sub-storage modules B1, B2, B3, and B4. After each butterfly operation, four data are written into the sub-storage modules B1, B2, B3, and B4. The address is equal to the read address of the sub-storage modules A1, A2, A3, A4;

4) Repeat the above three steps until all the data in the storage module A completes the butterfly operation, at this time the maximum overflow bit number is the final overflow bit number of the butterfly operation result of this level;

5) After all the data in the storage module A complete the first-stage butterfly operation, the control module sends a flag signal to the outside, indicating that the next FFT/IFFT data stream enters the storage module A in series and waits.

In the present invention, two storage modules A and B with the same size are used. Storage module A is only used to store input data, while storage module B is used to store butterfly operation results. The purpose of doing this is to continuously complete multiple FFT Or in the IFFT operation, after the first-level butterfly operation is completed in this operation, the storage module A can be idle to accept the serial input data of the next operation, so that when several stages of butterfly operations are performed after this operation , the input data of the next operation can be serially entered into the storage module A at the same time, after the completion of this operation and the final result is completely output from the storage module B, if the input data of the next operation is ready, the next operation can be performed immediately , which saves the time for serially writing data into memory module A.

The number of points in the FFT or IFFT operation is recorded as N, and N=2 ^L , L is a positive integer greater than or equal to 3: if L is an even number, the number of butterfly operation stages is L/2; if L is an odd number , then the butterfly operation series is (L+1)/2. Under the control of the control module, each butterfly operation from the second stage to the L/2th stage when L is an even number or from the second stage to the (L-1)/2th stage when L is an odd number is from Read four data in the storage module B, complete a radix-4 butterfly operation after being shifted by the shift module, and store the result in the storage module B according to the original address after the overflow detection and judgment; when L is an odd number, 1)/2-level butterfly operation reads two data from storage module B each time, performs radix-2 butterfly operation under the control module, and stores the result in storage module B according to the original address after overflow detection and judgment include:

1) The butterfly operation from the second stage to the L/2 stage when L is an even number or from the second stage to the (L-1)/2 stage when L is an odd number, under the control of the control module, every time Read one piece of data from each of the sub-storage modules B1, B2, B3, and B4, and the data shift module performs shifting according to the overflow detection judgment result after the previous butterfly operation, and the shift result completes a radix-4 butterfly operation , the result is written into the sub-storage modules B1, B2, B3, and B4 according to the original address after overflow detection and judgment;

If L is an even number, then N=2 ^L =4 ^L/2 ; if L is an odd number, then N=2 ^L =4 ^(L-1)/2 ×2. Therefore, when L is an even number, all butterfly operations are radix-4 butterfly operations; when L is an odd number, the butterfly operations from the first stage to the (L-1)/2th stage are radix-4 butterfly operations, The final stage is a radix-2 butterfly operation. Since the first-stage butterfly operation is performed by reading data from the storage module A, the butterfly operation for reading data from the storage module B should start from the second stage.

2) When L is an odd number, the (L+1)/2-th stage butterfly operation is a radix-2 butterfly operation. Under the control of the control module, first read out a piece of data from the sub-storage modules B1 and B3 respectively, After the shift, a base-2 butterfly operation is completed, and the result is stored in the sub-storage modules B1 and B3 according to the original address after being judged by overflow detection, and this cycle is performed until all the data in the sub-storage modules B1 and B3 complete the butterfly operation; after that, the Sub-storage modules B2 and B4 are combined to complete the same operations as sub-storage modules B1 and B3;

3) At this point, we have successfully completed all the butterfly operations of the N-point data FFT/IFFT operations, and the results are stored in the sub-storage modules B1, B2, B3, and B4.

After all the butterfly operations described above are completed, according to this operation being FFT or IFFT, the data in the storage module B is processed and then serially output to obtain the FFT or IFFT block floating-point operation results of the input data, and the The steps of combining the result with the final output block floating-point index into the actual FFT or IFFT result include:

1) Under the control of the control module, serially output the data from the sub-storage modules B1, B2, B3, and B4 in a certain order, and perform the following processing according to whether this operation is FFT or IFFT: if it is FFT, the real part and the imaginary part remain unchanged; if it is IFFT, the real part remains unchanged and the imaginary part is reversed;

Through the above analysis of formulas (2) and (3), it can be obtained that when the IFFT operation is completed, the imaginary part is reversed when the data is input, and the imaginary part is reversed when the final result is output, so that IFFT can be achieved Operation and FFT operation use the same twiddle factor value, which simplifies the control logic.

2) After the conversion of the real part and the imaginary part is completed, according to the overflow detection judgment result of the last butterfly operation, the serial output data can be output after being shifted accordingly, and the output result is the FFT of the input N-point complex data /IFFT block floating-point calculation result, when all the N-point data is output, a flag signal is given to the control module, indicating that the storage module B is available, and a new FFT/IFFT operation can be performed;

3) The actual FFT/IFFT result is: X(k)=X′(k)*2 ^-exp (k=0, 1,...N-1, N is the number of input data points), where X(k) is the actual FFT/IFFT result, X'(k) is the FFT/IFFT block floating-point operation result, and exp is the block floating-point exponent.

The described actual FFT/IFFT result is: X(k)=X'(k)*2 ^-exp , k=0,1,...,N-1, N is the number of input data points, where X(k ) is the actual FFT/IFFT result, X'(k) is the FFT/IFFT block floating point operation result, and exp is the block floating point index. The steps include:

1) When the operation type is FFT, the initial value of exp is 0; when the operation type is IFFT, the initial value of exp is log ₂ N;

It can be seen from formulas (2) and (3) that compared with FFT, IFFT needs to be multiplied by a coefficient in front $1/N=2^{{-\log }_{2}N},$ Therefore, when completing the IFFT operation, the initial value of exp is log ₂ N.

2) After each level of butterfly operation, exp is equal to the value before the start of butterfly operation of this level minus the number of overflow bits of butterfly operation of this level. After all butterfly operations are completed, the obtained exp is the final block float exponent;

As shown in Figure 3, assuming that the real part and imaginary part width of the input data are both m, taking one of the real part or imaginary part as an example, the bit width of the memory is that the data with a bit width of m undergoes a radix-4 operation After the maximum possible bit width m+3, now after the first butterfly operation, the bit width is expanded to m+M ₁ (M ₁ ≤3), for the second butterfly operation, the bit width can still be limited In m+3, we need to shift it to the right by M1 after reading the result of the first-stage butterfly operation before performing the second-stage butterfly operation; and so on, before the third-stage butterfly operation starts, we need to The result of the second-stage butterfly operation is shifted to the right by M ₂ bits, ......, before the start of the k+1-th butterfly operation, the result of the k-th butterfly operation needs to be shifted to the right by M _k bits,  … .; As shown in Figure 4, it is the operation flowchart of the block floating point in the k+1 stage butterfly operation process, including reading data from the memory, right shifting M _k bits, butterfly operation, overflow bit number detection and The result of the butterfly operation is written into the memory;

After the above right-shifting process, the final butterfly result is right-shifted by M ₁ +M ₂ +...+M _k +...bits, therefore, the block floating-point index is:

exp＝exp _ini -(M ₁ +M ₂ +...+M _k +...)(5)

exp _ini is the initial value of exp, the FFT operation is 0, and the IFFT operation is log ₂ N;

3) The actual FFT/IFFT result X(k) can be obtained through the final block floating point result X'(k) and the block floating point exponent exp, X(k)=X'(k)*2 ^-exp ,k =0, 1, ..., N-1, N is the number of input data points.

It can be seen from formula (5) that the relationship expression between the actual FFT/IFFT result X(k) and the final output block floating-point result is:

$x\left(k\right)=x^{\&prime;}\left(k\right)*2^{{-\exp }_{\mathrm{ini}}+(m_1+m_2+...+m_k+...)}=x^{\&prime;}\left(k\right)*2^{-\exp }---\left(6\right)$ .

the

Claims (8)

1. A mixed base FFT/IFFT implementation device with variable points is characterized in that it comprises modules: input data conversion module, storage module A, data selector, butterfly operation module, overflow detection module, storage module B, shift The bit module, the output data conversion module and the control module, the input data conversion module and the storage module A, the data selector, the butterfly operation module, the overflow detection module, the storage module B, and the shift module are connected in sequence, and the storage module B is connected with the output data conversion module The modules are connected, and the shift module is connected with the data selector; under the control of the control module, the serial input data is converted and stored in the storage module A, and then the control module controls all the data in the storage module A to complete the first-level butterfly operation, and the result The overflow detection is completed, and it is also stored in the storage module B; when all the data in the storage module A has completed the first-level butterfly operation, the control module sends out a flag signal that the storage module A is free and available, indicating the next operation Data can be input, and the control module controls the shift module, storage module B, butterfly operation module and overflow detection module to complete all subsequent butterfly operations; when all butterfly operations are completed, the control module controls storage module B, output The data conversion module reads the data in the storage module B serially and outputs the final block floating-point operation result after shifting and transforming the real part and the imaginary part. When all the data in the storage module B is output, the output data conversion module sends to the control The module gives the free and available flag signal of storage module B, and a new FFT/IFFT operation starts. 2. a kind of point number variable mixed-radix FFT/IFFT realization device according to claim 1, is characterized in that, described butterfly operation module comprises the connected twiddle factor storage module, multiplier module and adder module . 3. A method for realizing the variable mixed-radix FFT/IFFT using the variable number of points of the device according to claim 1, characterized in that it comprises the steps: 1) According to whether the operation is FFT or IFFT, under the control of the control module, the serial input data is processed and stored in the storage module A in a block-by-block reverse order; 2) After the processed serial input data are all written into the storage module A, the control module controls the storage module A, the butterfly operation module, and the overflow detection and judgment module, and reads four data from the storage module A to complete a base-4 butterfly Shape operation; after performing overflow detection and judgment on the butterfly operation result data, it is stored in the storage module B according to the original address. When all the data in the storage module A have completed the first-level butterfly operation, the control module sends out a signal, and the The data stream of an FFT or IFFT operation enters the storage module A; 3) Record the points of FFT or IFFT operation as N, and N=2 ^L , L is a positive integer greater than or equal to 3: if L is an even number, the number of butterfly operation stages is L/2; if L is an odd number, Then the number of stages of the butterfly operation is (L+1)/2, under the control of the control module, L is the second stage to the L/2 stage in the case of an even number or the second stage to the ( Each butterfly operation of level L-1)/2 reads four data from storage module B, completes a radix-4 butterfly operation after being shifted by the shift module, and stores the result at the original address after being judged by overflow detection into the storage module B; when L is an odd number, the (L+1)/2-level butterfly operation reads two data from the storage module B each time, and performs the base-2 butterfly operation under the control module, and the result Store in storage module B according to the original address after overflow detection and judgment; 4) After all the butterfly operations are completed, according to this operation as FFT or IFFT, the data in the storage module B is processed accordingly and then serially output to obtain the FFT or IFFT block floating-point operation results of the input data. The result is combined with the final output block floating-point exponent into the actual FFT or IFFT result. 4. a kind of point-number-variable mixed-radix FFT/IFFT realization method according to claim 3 is characterized in that, described operation is FFT or IFFT according to this time, under the control of control module, serial input After the data is processed, the steps of storing the data in the storage module A according to the reverse order of the blocks include: 1) The input data of FFT/IFFT transformation is a complex number, the number of points is N, N=2 ^L , L is a positive integer greater than or equal to 3, if the input data requires FFT operation, the input complex data does not need to be processed; if the input If the data requires IFFT operation, the real part of the input complex data remains unchanged, and the imaginary part is reversed; 2) Storage module A includes four sub-storage modules of the same size, namely A1, A2, A3, and A4. The size of each sub-storage module is 2×b×N/4 bits, and b is the real or imaginary part of the input complex number The bit width bit number of the part, the processed data of N points serially input is x(n), wherein n=0,1,2,...,N-1, x(0)～x( N/4-1), x(N/4)～x(2N/4-1), x(2N/4)～x(3N/4-1) and x(3N/4)～x(N- 1) Store them in A1, A2, A3, and A4 in reverse order; 3) When the number of input data points reaches N, the control module sends an FFT/IFFT operation start signal. 5. a kind of point number variable mixed radix FFT/IFFT realization method according to claim 3 is characterized in that, after the serial input data after described processing is all written into memory module A, control module controls memory module A , the butterfly operation module and the overflow detection and judgment module, read four data from the storage module A to complete a radix-4 butterfly operation; after performing overflow detection and judgment on the butterfly operation result data, store it in the storage module B according to the original address , when all the data in the storage module A has completed the first-level butterfly operation, the control module sends a signal to the outside, and the data flow of the next FFT or IFFT operation can enter the storage module A. The steps include: 1) Read a piece of data from the sub-storage modules A1, A2, A3, and A4 respectively, and complete a radix-4 butterfly operation through three complex multiplications and eight complex additions; 2) perform overflow detection and judgment on the result of each butterfly operation, and write down the overflow bit number of the maximum value in the operation result; 3) The storage module B is also composed of four sub-storage modules, which are respectively sub-storage modules B1, B2, B3, and B4. After each butterfly operation, four data are written into the sub-storage modules B1, B2, B3, and B4. The address is equal to the read address of the sub-storage modules A1, A2, A3, A4; 4) Repeat the above three steps until all the data in the storage module A completes the butterfly operation, at this time the maximum overflow bit number is the final overflow bit number of the butterfly operation result of this level; 5) After all the data in the storage module A complete the first-stage butterfly operation, the control module sends a flag signal to the outside, indicating that the next FFT/IFFT data stream enters the storage module A in series and waits. 6. a kind of point number variable mixed-radix FFT/IFFT realization method according to claim 3 is characterized in that, the described point number of FFT or IFFT operation is denoted as N, and N= ^2L , L is greater than Or a positive integer equal to 3: if L is an even number, the number of butterfly operations is L/2; if L is an odd number, the number of butterfly operations is (L+1)/2. Under the control of the control module, each butterfly operation from the second stage to the L/2th stage when L is an even number or from the second stage to the (L-1)/2th stage when L is an odd number is from Read four data in the storage module B, complete a radix-4 butterfly operation after being shifted by the shift module, and store the result in the storage module B according to the original address after the overflow detection and judgment; when L is an odd number, 1)/2-level butterfly operation reads two data from storage module B each time, performs radix-2 butterfly operation under the control module, and stores the result in storage module B according to the original address after overflow detection and judgment include: 1) The butterfly operation from the second stage to the L/2 stage when L is an even number or from the second stage to the (L-1)/2 stage when L is an odd number, under the control of the control module, every time Read one piece of data from each of the sub-storage modules B1, B2, B3, and B4, and the data shift module performs shifting according to the overflow detection judgment result after the previous butterfly operation, and the shift result completes a radix-4 butterfly operation , the result is written into the sub-storage modules B1, B2, B3, and B4 according to the original address after overflow detection and judgment; 2) When L is an odd number, the (L+1)/2-th stage butterfly operation is a radix-2 butterfly operation. Under the control of the control module, first read out a piece of data from the sub-storage modules B1 and B3 respectively, After the shift, a base-2 butterfly operation is completed, and the result is stored in the sub-storage modules B1 and B3 according to the original address after being judged by overflow detection, and this cycle is performed until all the data in the sub-storage modules B1 and B3 complete the butterfly operation; after that, the Sub-storage modules B2 and B4 are combined to complete the same operations as sub-storage modules B1 and B3; 3) At this point, we have successfully completed all the butterfly operations of the N-point data FFT/IFFT operations, and the results are stored in the sub-storage modules B1, B2, B3, and B4. 7. a kind of point-number-variable mixed-radix FFT/IFFT realization method according to claim 3 is characterized in that, after all the butterfly operations are completed, according to this operation being FFT or IFFT, the stored The data in module B is serially output after corresponding processing, and the FFT or IFFT block floating-point operation result of the input data is obtained. The steps of combining the result with the final output block floating-point index into the actual FFT or IFFT result include: 1) Under the control of the control module, serially output the data from the sub-storage modules B1, B2, B3, and B4 in a certain order, and perform the following processing according to whether this operation is FFT or IFFT: if it is FFT, the real part and the imaginary part remain unchanged; if it is IFFT, the real part remains unchanged and the imaginary part is reversed; 2) After the conversion of the real part and the imaginary part is completed, according to the overflow detection judgment result of the last butterfly operation, the serial output data can be output after being shifted accordingly, and the output result is the FFT of the input N-point complex data /IFFT block floating-point calculation result, when all the N-point data is output, a flag signal is given to the control module, indicating that the storage module B is available, and a new FFT/IFFT operation can be performed; 3) The actual FFT/IFFT result is: X(k)=X′(k)*2 ^-exp (k=0, 1,...N-1, N is the number of input data points), where X(k) is the actual FFT/IFFT result, X'(k) is the FFT/IFFT block floating-point operation result, and exp is the block floating-point exponent. 8. a kind of point number variable mixed-radix FFT/IFFT realization method according to claim 7, is characterized in that, described actual FFT/IFFT result is: X(k)=X'(k)*2 ^-exp , k=0, 1, ..., N-1, N is the number of input data points, where X(k) is the actual FFT/IFFT result, X'(k) is the FFT/IFFT block floating point operation result, The steps for exp to be a block floating-point exponent include: 1) When the operation type is FFT, the initial value of exp is 0; when the operation type is IFFT, the initial value of exp is log ₂ N; 2) After each level of butterfly operation, exp is equal to the value before the start of butterfly operation of this level minus the number of overflow bits of butterfly operation of this level. After all butterfly operations are completed, the obtained exp is the final block float exponent; 3) The actual FFT/IFFT result X(k) can be obtained through the final block floating point result X'(k) and the block floating point exponent exp, X(k)=X'(k)*2 ^-exp ,k =0, 1, ..., N-1, N is the number of input data points.

Images