# An FPGA-Based Four-Channel 128k-Point FFT Processor Suitable for Spaceborne SAR
## 2 Fast Fourier Transform (FFT) Operation Analysis and Principle Introduction
### Operation Proportion Analysis of FFT in the Standard Chirp-Scaling (CS) Algorithm  
In order to use synthetic aperture radar to accurately image targets, a variety of mature SAR imaging algorithms have been proposed. The chirp-scaling (CS) imaging algorithm proposed by [PERSON] et al. (2019) in 1992, is often used as the core of an integrated algorithm, as well as the basis of other SAR imaging algorithms ([PERSON] et al., 2019). Therefore, it is important to study the proportion of the FFT operation in the standard CS imaging algorithm. The flowchart of the standard CS algorithm is shown in Figure 1.  
In the algorithm flow, other operations, except FFT and inverse FFT (IFFT), are implemented by complex multiplication, so the number of real number additions and multiplications in the algorithm execution process can be used to measure the computational complexity of the entire algorithm and the complexity of hardware implementation. It is well known that data processed by a SAR system is a two-dimensional discrete signal. We assume that Na represents the number of sampling points of the original echo data in the azimuth direction, and Nr represents the number of sampling points of the echo data in the distance direction. Then, according to the processing flow of the CS algorithm, we can disassemble the CS algorithm into basic calculations, as shown in Figure 2.  
Furthermore, we can calculate the real number of addition and multiplication computations required by FFT/IFFT and the whole algorithm. The comparison results of  
Figure 1: The flowchart of the standard chirp-scaling (CS) algorithm. Figure 2: The flowchart of the standard CS algorithm. When designing processors of the same length under the same FFT structure, if different algorithms are used to implement them, the theoretical consumption values of  
Figure 4: Implementation structure diagram of the radix-\(2^{3}\) algorithm. hardware resources for each algorithm are different. Single-path delay feedback (SDF) circuit structure to implement a pipelined FFT structure has the advantages of less memory requirement and high data throughput. The SDF structure is introduced in detail in the following sections. Table 4 lists the occupancy of the multiplier, memory unit, and butterfly unit by applying common radix-2, radix-4, and radix-23 algorithms, mentioned in this paper, when using the SDF structure to implement N-point FFT. The statistics of the multiplier occupancy in Table 4 refers to the number of multipliers that, theoretically, are required in the realization of non-constant factor multiplication. The statistics of the memory unit occupancy refers to the data depth that the memory Block RAM (BRAM) needs to provide during the implementation process, so this value does not represent the data width. The occupation of the butterfly unit refers to the number of basic units that need to be placed in the processor. R2 represents the radix-2 butterfly unit, and R4 represents the radix-4 butterfly unit. Figure 5 shows the structure diagram of the radix-4 algorithm. It can be seen from Table 4 that the most significant feature of the radix-23 algorithm is to save the use of multiplier resources. The three algorithms occupy the same memory resources, which is the result of the use of the SDF structure. The radix-23 and radix-2 algorithms are consistent in the occupancy of the butterfly unit; due to the complex implementation structure of the radix-4 butterfly unit, even if the occupancy is half of the radix-2 unit, it still takes up the most hardware resources. Specifically, the implementation of a single radix-4 unit requires 24 adders, while the realization of a single radix-2 unit requires only four adders. We can see from Figure 5 that the radix-4 structure includes four 4-input 1-output complex adders, and each 4-input 1-output complex adder needs six adders to implement. When we assume that N is 128k, the radix-23 algorithm can save 68.6% and 37.3% of the multiplier resources as compared with the radix-2 and radix-4 algorithms, respectively.