## 1. Introduction

The prevalent subject of Fourier analysis encompasses a vast spectrum of mathematics where parts may appear quite different at first glance. In Fourier analysis, the term Fourier transform often refers to the process that decomposes a given function into the harmonics domain. This process results in another function that describes what frequencies are in the original function. Meanwhile, the transformation is often given a more specific name depending upon the domain and other properties of the function being transformed.

## 2. Fourier transform fundamental

Fourier transform was introduced with the main concepts of discrete Fourier transform (DFT) [1] in the heart of most DSP processor. The DFT is a Fourier representation of a finite‐length sequence which is the most important fundamental operation in digital signal processing and communication system [2, 3]. However, the computation complexity of the direct evaluation of an *N*‐point DFT involves a long phase computational time and large power consumption [4]. As a result of these problems, it is important to develop a fast algorithm. There are numerous viewpoints that can be taken toward the derivation and interpretation of the DFT representation of a finite‐duration sequence. The sequence of *N* by a periodic sequence can be represented by a periodic sequence with period *N*, one period of which is identical to the finite‐duration sequence. The sampled sequence signal in frequency is defined as

The DFT *X*(*ω*) is a function of continuous‐frequency variable *ω*, and the summation in Eq. (1) extends toward positive and negative infinitively. Therefore, the DFT is a theoretical Fourier transform of a digital signal. However, it cannot be implemented for real applications. It is the sample of the signal in time domain at a particular time and can be expressed as:

The frequency analysis of a finite‐length sequence is equal to the sample of continuous frequency variable *ω* at *N* equally spaced frequencies *ωk* = 2*πk*/*N* for *k* = 0, 1, 2, …, *N* - 1 on the unit circle. These frequency samples are expressed as:

where the twiddle factors are defined as:

The DFT is based on the assumption that the signal is periodic. Therefore,

*X*(

*k*) for

*k*= 0, 1, …,

*N*- 1 can uniquely represent a periodic sequence

*x*(

*n*) of period

*N*. The inverse DFT is the reversed process of the DFT. It converts the frequency spectrum

*X*(

*k*) back to the time domain signal

*x*(

*n*) [5]:

Direct computation of an ** N**-point DFT according to Equation Eq. (5) requires

**(**

*N***-**

*N***1**) complex additions and

**(**

*N***-**

*N***1**) complex multiplications. The complexity for computing an N-point DFT is therefore

**(**

*O***). High computation complexity in DFT algorithm and need for having efficient Fourier processor leads for introduction of a fast Fourier transform (FFT) processor.**

*N*2### 2.1. Fast Fourier transform (FFT) algorithm

In 1965 Cooley and Tukey [6] developed the use of FFT in order to save time and avoid unnecessary complex calculations. FFT algorithm computes an *N*‐point forward DFT or inverse DFT (IDFT) where *N* is 2^{} power of *M*. FFT algorithm divides *N*‐point data into two *N*/2‐point series and performs the DFT on series individually results in the order of *N*^{2} operations in an *N*‐point DFT. The process of dividing can be continued until a 2‐point DFT is reached. FFT algorithm computes an *N*‐point forward DFT or inverse DFT (IDFT) where *N* is 2 power of *m*. The FFT is a family of algorithms that efficiently implements the DFT. **Table 1** shows the comparison between the calculation of direct DFT and FFT when a different number of

To calculate FFT algorithm, there are two well‐known methods identified as DIT‐FFT and DIF‐FFT calculations [7–9]. In general, FFT processor has many types in terms of Fourier calculation. Taking into account different types of FFT algorithms are:

Different Radixes, such as Radix II, Radix IV, etc., and mixed‐radix algorithms.

DIT and DIF.

Real and complex algorithm.

Here, further detail is provided for DIT and DIF processor.

#### 2.1.1. DIT Radix II butterfly FFT processor

The FFT structure divides input series into odd and even sequences. The number of stream in FFT is *N* = 2^{m}when *m* is a positive integer:

Based on the DFT definition and combination of the FFT concept, *X*(*k*) can be written as:

Since

where **Figure 1** shows the twiddle factor for 8‐point Fourier transform. The twiddle factor *N*. The twiddle factors are periodic and for 8‐point FFT twiddle factor 0 and 8 are equal.

By assuming

Butterfly calculation is the fundamental concept of the FFT algorithm and 8‐point butterfly structure is shown in **Figure 2**.

Radix II butterfly FFT is decomposed into *N* complex additions are required. Therefore, the total computational requirement is **Figure 3**.

#### 2.1.2. DIF Radix II butterfly FFT processor

DIF‐FFT calculation is similar to the DIT‐FFT algorithm. As far as FFT calculation is involved, the time domain sequence is divided into two subsequences with expressed as:

Given that

Later, Eq. (11) is expanded into two parts including even

(12) |

Similarly, 8‐point DIF FFT structure is shown in **Figure 4** with detail complex calculation in three stages. The output sequence **Figure 4**, the complex multiplication is performed before the complex addition or subtraction in the DIT‐FFT processor. In contrast, the complex subtraction is performed before the complex multiplication in the DIF‐FFT. The process of decomposition is continued until the last stage is reduced to the 2‐point DFT. Since the frequency samples in the DIF‐FFT are bit‐reversed, it is required to apply bit‐reversal algorithm to the frequency samples. Likewise, the DIF‐FFT algorithm also uses in‐place computation.

Unlike the DIF structure, input data in DIT‐FFT is in bit‐reverse format while the output is sorted. On the other hand, both the DIT and DIF can go from normal to shuffled data or vice versa. In order to apply Radix II FFT structures, DIT and DIF algorithms require the same number of operations and bit‐reversal to compute the FFT calculation. The overall performance of the FFT processor is dependent on the application, hardware implementation, and convenience. If the design is focused on high speed structure, the processor has to take the most efficient approach and algorithm to perform the FFT calculation accordingly. In this chapter DIT‐FFT architecture is considered for floating‐point implementation.

### 2.2. Floating point FFT algorithm

Measured frequency by FFT will be subjected to quantization noise error with respect to the real frequency. This is caused by the fact that the FFT only computes the spectrum at discrete frequencies. This error is said to affect the accuracy. In addition, spectral leakage effect becomes very significant when small amplitude harmonics are close to large amplitude ones since they become hidden by the energy distribution of the larger harmonics. Furthermore, the fixed internal arithmetic calculation generates white noise in frequency domain. To reduce the generated noise effect and enhance signal strength, floating‐point technique is designed and implemented. The floating‐point technique allows numbers to be represented with a large dynamic range. Therefore, floating‐point arithmetic enables the reduction of overflow problems that occur in fixed‐point arithmetic. Although it is at the expense of throughput and chip area size, the new architecture is designed and investigated to avoid undesired effects in floating‐point FFT algorithm. Floating‐point arithmetic provides higher precision and a much larger dynamic range under IEEE 754 standard [10]. Therefore, floating‐point operations support more accurate DSP operations. **Table 2** compares the efficiency between fixed‐point and the floating‐point FFT processor.

In floating‐point format, the data are translated based on power and mantissa in the decimal system. This notation can be expanded into the binary system. Representing the data in power and mantissa system gives the data the capability of storing a much greater range of numbers than if the binary points were fixed. Floating point refers to the “truth” of the Radix point, which refers to the decimal point or in computers it is known as the binary point that has the capability to float. This entails the event to occur anywhere that is relative to the significant digit of the number. Thus, a floating‐point representation, with its position indicated separately in the internal representation, is a computer's recognition of a scientific concept. Although the benefit of floating‐point representation over fixed‐point (and integer) representation is much wider in range of values, but the floating‐point format needs more storage. Hence, the implementation of high performance system requires applying efficient and fast floating‐point processor, which is competitive with the fixed‐point processor. Various types of floating‐point representation have been used in computers in the past. However, in the last decade, the IEEE 754 standard [10] has defined the representation. According to the IEEE 754 standard [10], the single precision is chosen to represent the floating‐point data. The IEEE standard specifies a way in which the three values described can be represented in a 32‐bit or a 64‐bit binary number, referred to single and double precision, respectively [11, 12]. In this project, single precision is selected to function. For the 32‐bit numbers, the first bit (MSB) specifies the sign, followed by 8 bits for the exponent, and the remaining 23 bits are used for the mantissa. This arrangement is illustrated in **Figure 5**. The sign bit is set to zero if the number is positive, and the bit is set to 1 if the number is negative. The mantissa bits are set to the fractional part of the mantissa in the original number in bits 22 to 0.

Floating‐point algorithm finds huge demand in industry. To conclude this section, **Table 3** summarizes the FFT algorithm application in fixed‐point and floating‐point architectures.

### 2.3. Pipeline/parallel FFT algorithm

In 2009, Xilinx Logic core [13] introduced the FFT processor using the Radix structure on a chip. The introduced FFT processors were designed to offer a trade‐off between core sizes and transform time. These architectures are classified below:

FFT Processor with Radix II pipelined serial I/O architecture

FFT Processor with Radix IV, parallel I/O (burst) architecture

FFT Processor with Radix II, parallel I/O (burst) architecture

FFT Processor Radix II lite, parallel I/O (burst) architecture

The pipeline serial I/O allows to continue data processing, whereas the burst parallel I/O loads and processes data separately by using the iterative approach. It is smaller in size than the parallel but has a longer transform time. In the case of Radix II algorithm, it uses the same iterative approach as Radix IV with the difference of smaller butterfly size that differentiates it. Yet, the transformation time is longer. Finally, for the last category, based on Radix II architecture, this variant uses a time multiplexed approach to the butterfly for an even smaller core, at the expense of longer transformation time. **Figure 6** shows the throughput versus resource among the four architectures.

#### 2.3.1. FFT processor with Radix II pipelined, serial I/O

In this design, *n*‐stage of Radix II butterfly is connected as a serial structure. Each unit of Radix II butterfly has its own RAM memory to upload and download data. The input data are stored in the RAM while the processor simultaneously performs transform calculations on the current frame of data and loads input data for the next frame of data and unloads the result of the previous frame of data. Input data are presented in sorted order. The unloaded output data can either be in bit‐reversed order or in sorted order. When sorted output data are selected, an additional memory resource is utilized. **Figure 7** illustrates the architecture of the pipeline serial I/O with individual memory bank, which connects in a serial structure.

#### 2.3.2. FFT processor with Radix IV, burst I/O

Radix IV structure accepts 4 input data simultaneously whereas Radix II takes only 2 input data at the time to perform FFT calculation. Radix IV input data uploaded into the FFT processor, cannot be uploaded while the calculation is underway. When the FFT is started, the data are loaded. After a full frame has been loaded, the core computes the transformation. The result can be downloaded after the full process is over. The data loading and unloading processes can be overlapped if the data are unloaded in digit‐reversed order. **Figure 8** shows the Radix IV structure when 4 input data are loaded for FFT calculation.

#### 2.3.3. FFT processor with Radix II, burst I/O

FFT processor with burst I/O architecture utilizes Radix II butterfly calculation to execute the arithmetic structure. In spite of Radix IV with burst I/O processor, which the input data cannot be loaded and unloaded simultaneously, the Radix II processor accepts the input data during the FFT processor and data can be used concurrently when the output samples are in bit‐reversed order. The twiddle factors are stored in the ROM blocks while the output and input data are stored in a separate or mixed RAM blocks. **Figure 9** shows the Radix II structure when 2 input data are loaded for FFT calculation.

#### 2.3.4. FFT processor with Radix II lite, burst I/O

FFT processor with Radix II lite architecture uses one shared RAM, hence reducing resources at the expense of an additional delay per butterfly calculation. The multiplier in this structure multiplies the real part of complex number in one clock cycle and the imaginary in the next. In this architecture, the data can be simultaneously loaded and unloaded if the output samples are in bit‐reversed order. In this architecture, sine and cosine twiddle factor coefficient will be saved in the ROM and the output data will be saved in a single RAM. Although this proposed architecture saves the resources, the throughput is significantly limited by the FFT structure due to the sequence calculations. **Figure 10** shows the Radix II lite structure when 2 input data are loaded for FFT calculations.

## 3. Advanced high‐tech fast Fourier transform algorithm

In Section 2, FFT fundamental was discussed and elaborated. Furthermore, different FFT architectures were provided with the detail on IO configuration. Here, advance FFT processor with the focus on 1024 floating‐point parallel architecture for high performance application is provided.

### 3.1. Stage realization of 1024‐point parallel pipeline FFT structure

High‐tech FFT principle is based on Radix II algorithm in floating‐point format to conduct 1024 point FFT structure. **Figure 11** illustrates the main block diagram of the 1024‐point Radix II floating‐point parallel pipeline (FPP) FFT processor in detail.

As shown in **Figure 11**, there are six major subprocessor units in the high‐tech 1024 point Radix II FPP‐FFT algorithm. These units are shared memory, bit reverse, butterfly arithmetic, smart controller, ROM, and finally address generator unit. The floating‐point input data act as a variable streaming configuration into the processor. The variable streaming configuration allows continuous streaming of input data and produces continuous stream of output data. **Figure 12** shows the internal schematic of the pipeline butterfly algorithm with the parallel architecture at a glance.

To enhance the speed of calculation in Radix II butterfly algorithm, the pipeline registers are located after each addition, subtraction, and multiplication subprocessors. Hence, the pipeline butterfly algorithm keeps the final result in the register to be transferred into the RAM by the next clock cycle. Additionally, the parallel architecture splits the data in real and imaginary format and increases the speed of FFT calculation by 50%. As a result of the design algorithm, Radix II FPP‐FFT processor calculates 1024 point floating‐point FFT exactly after

Radix II butterfly unit is responsible for calculating the complex butterfly equations as

#### 3.1.1. Floating point adder/subtraction

Butterfly processor efficiency greatly depends on its arithmetic units, and high‐speed floating‐point adder is the bottle neck of butterfly calculation. Based on IEEE‐754 standard [10] for floating‐point arithmetic, 32‐bit data register is considered to allocate mantissa, exponent, and sign bit in a portion of 23, 8, and 1 bits, respectively. The advantages of floating‐point adder are that the bias power is applied to complete the calculation and avoid using unsigned value. Additionally, the floating‐point adder unit performs the addition and subtraction using substantially the same hardware as used for the floating‐point operations. This functionality minimizes the core area by minimizing the number of elements. Furthermore, each block of floating‐point adder/subtraction operates the arithmetic calculation within only one clock cycle that results high‐throughput and low latency for the entire FFT processor. **Figure 13** shows the novel structure of the floating‐point adder when it is divided into four separate blocks while detail algorithm is presented in **Figure 14**.

The purpose of having separate blocks is to share the total critical path delay into three equal blocks. These blocks calculate the arithmetic function within one clock cycle. However, the propagation delay can be associated with continuous assignment to increase the overall critical path delay and for the slowing down of the throughput. Based on combinational design, the output of each stage depends on its input value at the time. The unique structure of floating‐point adder enables feeding of the output result in the pipeline registers after every clock cycles. Hence, the sequential structure is applied for the overall pipelined add/subtraction algorithm to combine the stages. The processing flow of the floating‐point addition/subtraction operation consists of comparison, alignment, addition/subtraction, and normalization stages.

The comparison stage compares two input exponents. This unit compares two exponents and provides the result for the next stage. The comparison is made by two subtraction units and the result is revealed by *compare_sign* bit.

According to the results of the comparison stage, the alignment stage shifts the mantissa and transfers it to the adder/subtraction stage. The number of shifting will be selected by the comparison stage output. Consequently, each stage of the floating‐point adder algorithm is executed within one clock cycle. Floating‐point adder/subtraction unit satisfies high speed and efficiency of arithmetic unit in cost of die area size. The floating‐point arithmetic unit is designed to calculate entire numbers regardless of the number sign. As shown in **Figure 15**, there is a logic gate involved with the stages, which cause higher delay propagation through the circuit.

Floating‐point numbers are generally stored in registers as normalized numbers. This means that the most significant bit of the mantissa has a nonzero value. Employing this method allows the most accurate value of a number to be stored in a register. For this purpose, the normalized stage is required. This unit is located after the add/sub stage. The output signal representing the add/sub block leads to zero digits of an unnormalized result of the calculation operation. The normalized block ignores the digital value of zero from the MSB of the mantissa and shifts the mantissa to imply value of one in digital as MSB in mantissa.

#### 3.1.2. Floating‐point multiplier

In a floating‐point multiplier, numbers are represented in single‐precision normalized mantissa and 8‐bit exponent format defined by the IEEE 754 standard. This structure has developed the architecture for partial‐product reduction for the IEEE standard floating‐point multiplication, leading to a structured high‐speed floating‐point multiplier. The shortening of the data path is desirable because they require shorter wires and therefore support faster operation. The former approach uses a reduction scheme based on combination unit and connects it as parallel architecture. Implementing floating‐point multiplier is simpler than floating‐point adder since it does not require alignment stage. The processing flow of the floating‐point multiplication operation consists of multiple stage and normalized stage. **Figure 16** shows the overall block diagram of the floating‐point multiplier while the flowchart of the functionality of the multiplier is shown in **Figure 17**.

In a floating‐point multiplier, the bias power format is applied to avoid having negative exponent in the data format. Additionally, the multiplier is designed as pipelined structure to enhance speed calculation, with the intention of the initial result appearing after the latency period where the result can then be obtained after every clock cycle. The multiplier offers low latency and high throughput and is IEEE 754 compliant. This design allows a trade‐off between the clock frequency and the overall latency by adding the pipeline stage.

#### 3.1.3. Smart controller structure

Smart controller unit significantly affects the efficiency of the 1024 Radix II FPP‐FFT processor. As such, small die area can be achieved by designing high performance controller for the FFT processor. In this architecture, FFT controller is designed with the pipeline capability. The global controller unit provides the signal control to the different parts of the FFT processor. Additionally, several paths are switched between the data input and data output in architecture design and the data path is controlled. To calculate the 1024 point Radix II FFT processor, it is necessary to have **Figure 18** shows the smart controller state machine, which controls the flow of the 1024 floating‐point Radix II FFT processor.

There are several control signals in smart controller to clarify the presence of correct output after finishing the current cycle of FFT calculation. The control signals transfer information through the RAM, ROM, butterfly preprocessor, and address generator. The designed controller operates according to the provided state machine (**Figure 18**) and makes the high performance FFT calculation feasible for implementation. The controller unit is structured into the subblocks such as in sequential and combination units. Sequential unit is responsible for updating the state of the processor, while the combinational unit performs the states individually. The state machine waits for processor core to complete the entire FFT calculations and then records data points into the memory. Reset state is received every time the reset input is asserted then holds the entire calculation. The processor gets activated after the reset input signal is removed.

#### 3.1.4. Memory and address generator

Address generator has a significant task in Radix II FFT processor, since it delivers the address of the input/output data for each computational stage in an appropriate way. Address generator architecture consists of ROM address generator, Read address generator, and Write address generator. ROM address generator produces the reading address for the ROM module. The reading address represents the address of the twiddle factor, which must be taken to feed the butterfly structure. This address generator is designed to select the specific twiddle factor for the butterfly calculations. Meanwhile, the Write address generator is designed to save the result of the butterfly calculation in the proper location in the complex RAM. The proposed smart address generator is designed to provide the correct result for the next stage of the butterfly in 1024‐point Radix II FFT calculations. The architecture of the Read address generator is similar to the Write address generator. The butterfly will save the data result after reading from the certain address and input it to the butterfly, in the previous address line. The reading RAM select control signal ensures the correct location of data in the complex RAM. On the other hand, memory modules are used for the storing input and output results with 1024 complex long words of 32‐bit registers. The implemented architecture for the memory is shown in **Figure 19**. The capacity of the memory is 1024‐point data for real and imaginary data. In high‐tech implementation, shared RAM architecture is designed and implemented in a single‐chip FFT processor. The high‐tech design makes the Radix II FFT architecture entirely independent of the type of FPGA board since it has on board memory system. Furthermore, each complex RAM has the capability of saving real and imaginary input data separately. The module is programed with a dual‐in‐line header to provide the appropriate location for storing input and output result in each stage consequently. It is composed of two delay memories and multiplexer, which allows straight through or crossed input‐output connection as required in the pipeline algorithm. Memory unit similarly contains the controller trig. The controller, which is connected directly to the memory modules, takes the responsibility of transferring data through the memory and arithmetic blocks ensuring that no data conflict occurs within the complete process of the FFT calculations. This is another advantage of high‐tech smart memory modules, by which data can be read and written in the memory simultaneously without sending bubble data in the FFT processor.

### 3.2. Advantages of 1024‐point parallel pipeline FFT structure

Design algorithm of the 1024 point Radix II FPP‐FFT processor was based on the smart subblocks where the result was optimized accordingly. The designed processor takes the advantages of (i) shared memory to store the input and output data and makes the system as single chip. Hence, it reduces hardware complexity. Furthermore, (ii) the entire individual arithmetic unit is designed to operate within one clock cycle to increase the maximum clock frequency. Additionally, (iii) the butterfly structure is in parallel and pipelined architecture to minimize delay caused by the FFT calculations, and finally, (iv) the strong controller with collaboration of address generator unit ignores the need of using *N* numbers of butterfly unit, since Radix II calculation is carried out within one butterfly unit that results reduction of power consumption, area, and avoid system complexity. The high performance processor is implemented with optimizing the architecture to enable the system in maintaining a reasonable clock rate and with low latency of

## 4. 1024 point FPP‐FFT implementation

Section 4 details the implementation of introduced 1024‐point floating‐point parallel pipeline Radix II FFT algorithm. Hardware implementation of the algorithm as system on chip (SOC) is presented here.

### 4.1. Hardware implementation

In order to verify the functionality of the 1024‐point FPP‐FFT processor, the VHDL code for the overall processor is developed. Register transfer level (RTL) behavior description of the processor is generated for downloading into FPGA prototyping. The procedure is continued by attaching the library cell and constraint file for ASIC implementation. High performance FFT is transferred into the gate level synthesis to complete postsimulation stage. The design moves forward to the back‐end implementation by 0.18 µm Silterra technology and 0.35 Mimos technology library. Generated netlist with constraint file is transferred to complete floor planning and place and route stage. The implementation process is summarized in **Figure 20**.

The high‐tech 1024‐point FPP‐FFT specification generated by Xilinx ISE synthesis report is provided in **Table 4**.

As stated in **Table 4**, high‐tech FFT processor operates with the maximum clock frequency of 227.7 MHz and the total latency of 5131 clock cycles (**Figure 21**) to prove the computation complexity derived from (*N*/2log2*N*) + 11 when *N* = 1024.

Place and route (PAR) process was completed and the processor routed successfully on silicon chip (**Figure 22**).

Later, the 1024‐point FPP‐FFT processor was optimized in Silterra 0.18 µm and Mimos 0.35 µm technology for power consumption and die size measurement in maximum clock frequency. **Table 5** shows the optimization result of FFT processor implementation in Silterra 0.18 µm and Mimos 0.35 µm technology library.

FPP‐FFT specification | Silterra 0.18 µm technology | Mimos 0.35 µm technology |
---|---|---|

Active core area (mm^{2}) | 2.32 × 2.32 | 4.256 × 4.256 |

Power consumption (mW) | 640 | 1198 |

To conclude, after FPGA implementation and ASIC optimization and with considering available software and hardware resources, the high‐tech 1024‐point Radix II FPP‐FFT processor was implemented and tested in FPGA prototyping under Xilinx ISE software and CAD tools in synopsis. **Figure 23** shows relevant FPGA board, and **Table 6** summarizes the design property.

## 5. Summary and conclusion

In this chapter, high‐tech 1024‐point Radix II FFT processor was implemented. The design was launched with introducing 32‐bit data single precision floating‐point parallel pipeline architecture. Then, it was followed by implementing the subcomponents such as Radix II butterfly and smart controller. The implementation result of high‐tech 1024‐point Radix II FPP FFT processor was provided accordingly. Designing high speed floating‐point arithmetic unit such as adder/subtraction (278 MHz), multiplier (322 MHz), implementing smart controller to save area and increase system efficiency, design processor as single chip by implementing complex dual memory, and providing pipeline and parallel architecture lead to present a high‐tech 1024‐point Radix II FPP FFT processor. In addition, the processor was synthesized using the Xilinx ISE platform. From synthesis report, it was found that the FPP FFT processor shows the maximum clock frequency of 227 MHz. The latency for calculating 1024‐point FFT is 22 µs. After FPGA implementation, the proposed processor was optimized in ASIC under Silterra 0.18 µm and Mimos 0.35 µm technology libraries. The estimation power consumption was reported 640 mW in Silterra and 1.198 W in Mimos technology library with sample rate of 25 ms/s. The procedure was followed by defining the constraints and the netlist (gate level) to produce the ASIC layout. The design compiler result shows the die size of ^{2} in Silterra 0.18 µm technology and ^{2} in Mimos 0.35 µm technology. From the given specification, it was found that the high‐tech 1024‐point Radix II FPP FFT processor is suitable for high performance DSP application.