Use FFT IP Core to implement FFT algorithm

Combining engineering practice, this paper introduces a method of using FFT IP Core to realize FFT. The design can perform 256-point FFT operation on two real number sequences at the same time, and perform modulo square operation on the conversion result, and has the ability to continuously process data. The design is realized by low-cost FPGA, which has the characteristics of low cost, high performance, strong flexibility and fast speed, and the design is proved to be correct and feasible through engineering applications.

Due to the advent of FFT (Fast Fourier Transform), it has promoted the maturity of the subject of digital signal processing, and it can be applied to any field that Fourier Transform theory can involve. Traditional FFT implementation methods are nothing more than software (software programming) and hardware (dedicated chip ASIC). The emergence of FPGA gives people another choice in FFT implementation. FPGA at the same time has the advantages of software programming flexibility and ASIC circuit speed, etc., suitable for high-speed digital signal processing. Most FPGA vendors provide a configurable logic core (Core) to implement various algorithm functions, including FFT IP Core (Intellectual Property Core). Using these resources allows designers to spend more time and energy on improving and increasing system functions, which will undoubtedly greatly reduce design risks and shorten development cycles.

This design uses Altera's FFT IP Core to realize the FFT function, which can realize the FFT conversion of two 256-point real data at the same time, and perform the modulo square operation on the conversion result. The design has the ability to continuously process the data. The FPGA chip used is the Cyclone series chip of Altera, which has the lowest cost ever. The FFT core is Altera MegaCore FFT-V2.0.0. The whole design has low cost and good performance, and has been successfully applied to radar products.

2 Algorithm principle and FFT Core introduction

The algorithms used in the design include the FFT algorithm and the CORDIC algorithm that simultaneously calculate two real functions.

2.1 FFT algorithm for calculating two real functions at the same time

The definition of DFT is:

In formula (1), it is assumed that the time function x(n) is a complex function. But in many practical applications of FFT, the time function is often a real function. The algorithm described below can effectively reduce the computational workload of the real-number sequence FFT, thereby increasing the computational speed. The method can be summarized into the following steps:

① Functions h(n) and g(n) are two real functions, n=0, 1,., N-1;

② Taking one of them as the real part and the other as the imaginary part, the complex function z(n) is formed as:

z(n)=h(n)+jg(n), n=0, 1,., N-1;

③Calculate the N-point DFT of z(n) to get:

In the formula, Zr(k) and Zi(k) are the real and imaginary parts of Z(k), respectively;

④Analyze H(k) and G(k) from z(k):

In the formula, H(k) and G(k) are the DFT of h(n) and g(n) respectively.

2.2 CORDIC algorithm principle

The CORDIC (The Coordinate Rotational Digital Computer) algorithm is a cyclic iterative algorithm. Its basic idea is to use a series of constant deflection of the angle related to the operating base to approximate the required rotation angle. Broadly speaking, it is a method of numerical calculation and approximation. Since these fixed angles are related to the calculation base, the only operations are shift and addition and subtraction. Functions that can be calculated with this algorithm include multiplication, division, square root, sine, cosine tangent, vector rotation (ie, complex multiplication), and exponential operations. The basic principles of CORDIC are as follows.

Vector x+jy, rotation angle θ to vector x'+jy', the assumed direction is represented by δ, the angle of rotation is θi, and θi satisfies the relationship: tanθi=2i. It can be seen from the derivation of literature [3]:

Assuming x[0]=b,y[0]=a,z[0]=0, then:

Where

For operations with a certain word length, it is a constant. For example, when the word length is 16 bits, K=1.6667. δi represents the direction of each rotation. When y[i]≥0, its value is 1; when y[i]≤0, its value is -1.

2.3 Introduction to FFT Core

FFT-V2.0.0 is a new FFT intellectual property core released by Altera in February 2004. It is a high-performance, highly parameterized Fast Fourier Transform (FFT) processor that supports Cyclone,

StraTIx II, Stratix GX, Stratix series FPGA devices. The FFT Core function is to perform high-performance forward complex FFT or inverse FFT (IFFT), using radix 2/4 frequency domain decimation (DIF) FFT algorithm, and its conversion length is 2m, where 6≤m≤14. Internally, FFT uses a block floating-point structure to obtain the maximum benefit between the maximum signal-to-noise ratio (SNR) and the minimum resource requirement. FFT Core receives as input a sequence of complex numbers with length N in two's complement format and sequential input, and outputs a sequence of complex numbers in the conversion domain. At the same time, an accumulated block index is output, which represents the quantization factor of the block floating point. The conversion direction of the FFT Core is specified in advance by an input port for each data conversion block.

FFT Core can be set with two different engine structures: Quad-output FFT engine and Single-output FFT engine. For the minimum conversion time required

For applications, the four-output engine structure is the best choice; for applications that require as few resources as possible, the single-output engine structure is more appropriate. In order to increase the throughput of the entire FFT Core, a multi-parallel engine structure can be used.

FFT Core supports three I/O data stream structures: continuous (streaming), buffered burst (Buffered Burst), and burst (Burst). The continuous I/O data stream structure allows processing continuous input data and output continuous complex data streams without interrupting the input and output data; the buffered burst I/O data stream structure requires less storage resources than the continuous structure, but , This is to reduce the average throughput

Volume is the price; the operation of the burst data stream structure is basically the same as the buffer burst mode, but the burst mode requires less storage resources, which also comes at the cost of reducing throughput.

3 hardware design

The overall schematic diagram of the design is shown in Figure 1. The input and output buffers store the preprocessed data and FFT conversion results respectively; the FFT operator is responsible for the FFT operation; the controller provides read and write addresses for the input and output buffers, and controls the timing of the FFT operation and the read and write operations of the buffer; The processing unit separates two channels of real number input spectrum data from a single channel of complex number input spectrum data; the modulus arithmetic unit implements the CORDIC algorithm and obtains the square root of the conversion result. The designed input is a two-way real number sequence, one as the real part and the other as the imaginary part, consisting of continuous 256-point data segments; the output is a discontinuous 256-point data segment, and the first 128 points of each data segment are the first The last 128 points are the second channel of spectrum data. According to the result that the FFT spectrum is symmetric about the center point, only the first half of the spectrum data is intercepted and no information is lost.

The working sequence of the whole system is:

①Data is input to the input buffer at a rate of 5MHz;

②The FFT arithmetic unit fetches data from the input buffer at a rate of 40MHz for operation;

③At the end of the FFT operation, store the conversion result in the output buffer;

④ The output buffer data is sent to the post-processing unit for conversion at a rate of 20MHz;

⑤The data is sent to the modulo calculator for CORDIC calculation and output;

⑥ When ③ is over, the FFT arithmetic unit returns to the initial state and waits for the next set of data to be processed, so that the calculation can be carried out over and over again. The entire design is strictly controlled by the controller.

The input and output buffers are implemented by RAM inside the FPGA, which are relatively simple. The following highlights. FFT arithmetic unit, controller, post-processing unit and modulo arithmetic unit.

3.1 FFT calculator

The FFT arithmetic unit is realized by FFT Core, and its engine structure is dual single-output, and the I/O data stream adopts burst mode. FFT Core adopts AtlanTIc Interface protocol, input

The interface is regarded as the main receiver, and the output interface is regarded as the main transmitter. The specific interface definition is shown in Table 1.

Specific workflow: After the system is reset, the data source sets master_sink_dav to indicate that there is sampled data waiting for input; in response, FFT Core sets master_sink_ena to indicate that the input data can be received; the data source loads the first complex data, and at the same time master_sink_sop Set to indicate the beginning of the input data block; the next clock, master_sink_sop is cleared, and the input data is added in natural order. When the input data reaches 256 points, the system naturally starts FFT operation. The FFT conversion direction of a single data block can be changed by setting/clearing the inv_i signal. The inv_i signal must be strictly synchronized with the master_sink_sop signal. When the FFT conversion is over, the sub-receiver has set the master_source_dav signal, indicating that the sub-receiver can receive the FFT conversion result; at the same time, the master_source_ena signal is set, and FFTCore outputs the operation result in natural order; in the output process,

The master_source_sop and master_source_eop signals are set to indicate the start and end of the output data block. For a detailed description, see reference [4].

3.2 Controller and post-processing unit

The controller can be roughly divided into three parts: input buffer control (c_i), FFT operation control (c_f), output buffer control (c_o). c_i provides read/write address and corresponding read/write for input buffer

Control signal; c_f provides the control signal for the FFT arithmetic unit to strictly control the working sequence of the FFT Core; c_o provides the read/write address and read/write control signal for the output buffer. The controller can be easily realized through the state machine mode of VHDL language programming.

The post-processing unit is actually the hardware implementation of equations (2) and (3), and the specific principle is shown in Figure 2.

The marks "mux", "+", "-", and "1/2" in the figure represent selectors, adders, subtractors and dividers, respectively, dr, di, dnr, and dni are related to equations (1) and ( 2) Zr(k),

Zi(k), Zr(N-k), Zi(N-k) correspond. When sel is equal to 0, extract the spectrum data G(k) of the first real sequence to realize the function of formula (1); when sel is equal to 1, extract the spectrum data of the second real sequence to realize the function of formula (2).

3.3 Modulo operator

Since the project only requires the square root and does not involve the calculation of the angle, the angle calculation part of CORDIC is not given, but this will not affect the calculation of the amplitude. The entire CORDIC adopts a full assembly line structure, and the design has a total of 16 pipeline units, and the structure of each assembly line unit is similar. 

This result is not the final result, and one level of amplitude correction should be added to remove the influence of distortion factors.

4 Conclusion

The designed input and output operating frequencies are relatively low, so it is easy to meet. The key is the performance index of the FFT Core. According to engineering needs, the input data rate is 5MHz, the FFT Core works at 40MHz, and the output conversion result uses a 20MHz clock. Under these conditions, hardware tests are performed on the design. The results prove that the design has correct functions, stable work, and superior performance. In addition, the software timing simulation shows that the maximum operating frequency of the FFT Core can reach 117.52MHz. By increasing the operating clock, faster computing power can also be obtained.

The design uses Altera's FFT Core, and successfully implements two continuous 256-point real-number sequence FFT algorithms in FPGA. The design cost is low and the performance is good, and it has been successfully applied to radar products. Because of the strong plasticity of FFT Core, the design can be easily adapted to different products by changing the parameter settings.