64-point FFT Instruction Implementation and Evaluation on a Microcode Programmable Processor

Abstract: Fast Fourier Transform is an efficient algorithm for computing the Discrete Fourier Transform (DFT) and one of the most important algorithms used in many digital signal processing applications over decades. This thesis presents an efficient implementation method of a 32-bit complex number 64-point FFT instruction on a micro-programmable processor. The implementation uses a radix-4 decimation in frequency (DIF) FFT structure. To reduce the total hardware budget, instead of floating-point computation, a block floating-point algorithm is applied to prevent the data overflow and make the most of the floating-point dynamic range, resulting in a highly efficient implementation with acceptable accuracy and SNR. The FFT instruction is divided into several sub-instructions that can be executed separately or chained together. The implementation for the instruction is realized in microcode, and the implementation method will be discussed in detail, including flowcharts and logical structures. This thesis is in cooperation with Imsys, some of the parameters such as 64-point FFT and data format are the requirements from Imsys. In order to realize an acceptable performance, several alternative implementation methods regarding twiddle factor formats and multiplication methods are investigated and discussed. The FFT instruction output has been verified on an Imsys Embla device with its embedded software test framework against an Excel model provided by Imsys. Several test functions are created to perform the functional verification for each sub-instruction and the entire FFT-IFFT chain. These test functions will be introduced and presented with their flowcharts. The evaluation mainly focuses on the performance of different implementation methods towards two aspects: the total execution time and the output accuracy and SNR. The measurement for the execution time is done by configuring a timer system built in the Imsys Embla device. The calculation for the output accuracy and SNR is according to given formulas. The best implementation method is chosen by comparing the SNR and execution cycle. Besides, the evaluation results are also compared with the excel model. During the instruction development process, the method of further possible improvement in the precision of the FFT instruction output has been discovered and is discussed in the future work chapter.