Submit manuscript...
eISSN: 2574-8092

International Robotics & Automation Journal

Mini Review Volume 4 Issue 4

Fuzzy optimization FFT circuit for image processing

Zehong Cao

EEG & BCI & Computational Intelligence, China

Correspondence: Zehong Cao, EEG & BCI & Computational Intelligence, China

Received: July 30, 2018 | Published: August 9, 2018

Citation: Cao Z. Fuzzy optimization FFT circuit for image processing. Int Rob Auto J. 2018;4(4):274-276. DOI: 10.15406/iratj.2018.04.00136

Download PDF

Abstract

In the FPGA implementation of FFT, a fuzzy approach is presented to reduce the multiplication numbers of twiddle factors and memory space, which speeds up the butterflies’ computation. Also, the design of address mapping can get position of data without calculation. Simultaneously, in combination of using the pipeline structure, the speed of the FFT for FPGA implementation can be increased. Moreover, the modules have been simulated by timing and verified by data to judge the correctness of the design. This design could be applied in signal processing and image processing.

Introduction

FAST Fourier Transform (FFT) is an effective and fast discrete Fourier transform (DFT) algorithm, which is the core of digital signal processing algorithms. FFT is widely used in radar, communications, image processing, signal detection and other fields, most of those fields call for the FFT processor with high speed and high precision real-time processing performance. In order to simplify the calculation and shorten operation time to one or two magnitudes, the ideology of FFT algorithm is sequentially dividing the N point DFT into short sequences of DFT for calculating. The introduction of Verilog Hardware Description Language (HDL) provided a modeling and simulation environment for fast prototyping digital circuits and systems on FPGA. After analyzing the radix-4 FFT algorithm, this project advanced a 64-point FFT processor implementation, which has many advantages.1,2 This paper studies the content as follows: first, describe the FFT algorithm. Then, introduce the principle of FPGA architecture, performance and characteristics, combined with the theory of FFT algorithms to determine the FPGA devices as a FFT algorithm basis. After that, using the design tools QuartusⅡ, Modelsim and hardware description language Verilog to achieve the above algorithm. Moreover, analysis of existing design ideas implementation, and compare the various implementations. I find the design structure of the FFT processor, using pipeline structure, and generating address and twiddle factor quickly. Finally, simulate each module, and debug it.3 For the FFT processor, the analysis method is that generate a random signal as the input signal. First, simulate the data signal using FFT function in Mat lab. Second, put the input signal to the FFT processor, and observed data calculated. Finally, it is compared with Mat lab simulation results. The FFT algorithm is applied in image processing.4,5

The FFT algorithm and system structure

DFT calculation

For the one-dimensional DFT, x(n) is a N numbers sequence, the DFT is defined as follows:

X(k)= n=0 N1 x(n)e j2πnk/N = n=0 N1 x(n) W N kn MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaOaamiwai aacIcacaWGRbGaaiykaiabg2da9maaqahabaGaamiEaiaacIcacaWG UbGaaiykaiaadwgaaKqbGeaacaWGUbGaeyypa0JaaGimaaqaaiaad6 eacqGHsislcaaIXaaajuaGcqGHris5amaaCaaabeqcfasaaiabgkHi TiaadQgacaaIYaGaeqiWdaNaamOBaiaadUgacaGGVaGaamOtaaaaju aGcqGH9aqpdaaeWbqaaiaadIhacaGGOaGaamOBaiaacMcacaWGxbWa a0baaKqbGeaacaWGobaabaGaam4Aaiaad6gaaaaabaGaamOBaiabg2 da9iaaicdaaeaacaWGobGaeyOeI0IaaGymaaqcfaOaeyyeIuoaaaa@5FAA@ 0kN1 MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaOaaGimai abgsMiJkaadUgacqGHKjYOcaWGobGaeyOeI0IaaGymaaaa@3E13@

Where this formula achieves transformation from the time domain to the frequency domain.

Cooley-Tukey algorithm

The Cooley-Tukey algorithm is used to calculate the multi-point DFT.6 For N-Point DFT, the number of complex multiplication is equal toN2. Obviously, if N-point DFT is decomposed into several short sequences DFT, the complex multiplication in DFT will be reduced greatly. For example, dividing the N-Point DFT into two N2⁄2-Point DFT, the number of complex multiplication in DFT will be reduced to N2⁄2. Assume that N= r 1 r 2 MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaOaamOtai abg2da9iaadkhadaWgaaqcfasaaiaaigdaaeqaaKqbakaadkhadaWg aaqcfasaaiaaikdaaeqaaaaa@3CEE@ in two-dimensional Cooley-Tukey fast algorithm,7 calculating the Cooley-Tukey fast algorithm is divided into five steps:

First, the x(n) is rewritten as x( n 1 , n 0 ) MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaOaamiEam aabmaabaGaamOBamaaBaaajuaibaGaaGymaaqcfayabaGaaiilaiaa d6gadaWgaaqcfasaaiaaicdaaKqbagqaaaGaayjkaiaawMcaaaaa@3ECF@ , using the formula:

x( n )=x( r 2 n 1 + n 0 )=x( n 1 , n 0 ),{ n 1 =0,1,2,..., r 1 1 n 0 =0,1,2,..., r 2 1 MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaOaamiEam aabmaabaGaamOBaaGaayjkaiaawMcaaiabg2da9iaadIhadaqadaqa aiaadkhadaWgaaqcfasaaiaaikdaaKqbagqaaiaad6gadaWgaaqcfa saaiaaigdaaKqbagqaaiabgUcaRiaad6gadaWgaaqcfasaaiaaicda aeqaaaqcfaOaayjkaiaawMcaaiabg2da9iaadIhadaqadaqaaiaad6 gadaWgaaqcfasaaiaaigdaaeqaaKqbakaacYcacaWGUbWaaSbaaKqb GeaacaaIWaaajuaGbeaaaiaawIcacaGLPaaacaGGSaWaaiqaaeaafa qabeGabaaabaGaamOBamaaBaaajuaibaGaaGymaaqabaqcfaOaeyyp a0JaaGimaiaacYcacaaIXaGaaiilaiaaikdacaGGSaGaaiOlaiaac6 cacaGGUaGaaiilaiaadkhadaWgaaqcfasaaiaaigdaaeqaaKqbakab gkHiTiaaigdaaeaacaWGUbWaaSbaaKqbGeaacaaIWaaabeaajuaGcq GH9aqpcaaIWaGaaiilaiaaigdacaGGSaGaaGOmaiaacYcacaGGUaGa aiOlaiaac6cacaGGSaGaamOCamaaBaaajuaibaGaaGOmaaqabaqcfa OaeyOeI0IaaGymaaaaaiaawUhaaaaa@6ED6@

Second, dividing r 1 MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaOaamOCam aaBaaajuaibaGaaGymaaqabaaaaa@3885@ -point DFT into r 2 MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaOaamOCam aaBaaajuaibaGaaGOmaaqabaaaaa@3886@ units, it can achieve X 1 ( k 0 , n 0 ) MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaOaamiwam aaBaaajuaibaGaaGymaaqabaqcfa4aaeWaaeaacaWGRbWaaSbaaKqb GeaacaaIWaaabeaajuaGcaGGSaGaamOBamaaBaaajuaibaGaaGimaa qcfayabaaacaGLOaGaayzkaaaaaa@4043@ .

Third, N numbers X 1 ( k 0 , n 0 ) MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaOaamiwam aaBaaajuaibaGaaGymaaqabaqcfa4aaeWaaeaacaWGRbWaaSbaaKqb GeaacaaIWaaabeaajuaGcaGGSaGaamOBamaaBaaajuaibaGaaGimaa qcfayabaaacaGLOaGaayzkaaaaaa@4043@ are multiplied by the corresponding twiddle factor W N k 0 n 0 MathType@MTEF@5@5@+= feaagKart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbmqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaOaam4vam aaDaaajuaibaGaamOtaaqaaiaadUgajuaGdaWgaaqcKvaq=haacaaI WaaajuaibeaacaWGUbqcfa4aaSbaaKazfa0=baGaaGimaaqcfasaba aaaaaa@40FA@ , which compose X 1 ( k 0 , n 0 ) MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaOaamiwam aaBaaajuaibaGaaGymaaqabaqcfa4aaeWaaeaacaWGRbWaaSbaaKqb GeaacaaIWaaabeaajuaGcaGGSaGaamOBamaaBaaajuaibaGaaGimaa qcfayabaaacaGLOaGaayzkaaaaaa@4043@ .

X 1 ( k 0 , n 0 )= n 1 =0 r 1 1 x( n 1 , n 0 ) W r 1 n 1 k 0 ,          k 0 =0,1,, r 1 1 MathType@MTEF@5@5@+= feaagKart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbmqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaOaamiwam aaBaaajuaibaGaaGymaaqabaqcfaOaaiikaiaadUgadaWgaaqcfasa aiaaicdaaKqbagqaaiaacYcacaWGUbWaaSbaaKqbGeaacaaIWaaaju aGbeaacaGGPaGaeyypa0ZaaabCaeaacaWG4bGaaiikaiaad6gadaWg aaqcfasaaiaaigdaaeqaaKqbakaacYcacaWGUbWaaSbaaKqbGeaaca aIWaaajuaGbeaacaGGPaaabaGaamOBamaaBaaajuaibaGaaGymaaqa baqcfaOaeyypa0JaaGimaaqaaiaadkhadaWgaaqcfasaaiaaigdaae qaaKqbakabgkHiTiaaigdaaiabggHiLdGaam4vamaaDaaabaGaamOC amaaBaaajuaibaGaaGymaaqcfayabaaabaGaamOBamaaBaaajuaiba GaaGymaaqcfayabaGaam4AamaaBaaajuaibaGaaGimaaqcfayabaaa aiaacYcacaqGGaGaaeiiaiaabccacaqGGaGaaeiiaiaabccacaqGGa GaaeiiaiaabccacaWGRbWaaSbaaKqbGeaacaaIWaaajuaGbeaacqGH 9aqpcaaIWaGaaiilaiaaigdacaGGSaGaeyyXICTaeyyXICTaeyyXIC TaaiilaiaadkhadaWgaaqcfasaaiaaigdaaKqbagqaaiabgkHiTiaa igdaaaa@7515@

Forth, dividing r 2 MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaOaamOCam aaBaaajuaibaGaaGOmaaqabaaaaa@3886@ -point DFT into r 1 MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaOaamOCam aaBaaajuaibaGaaGymaaqabaaaaa@3885@ units, it can achieve X 2 ( k 0 , k 1 ) MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaOaamiwam aaBaaajuaibaGaaGOmaaqabaqcfa4aaeWaaeaacaWGRbWaaSbaaKqb GeaacaaIWaaabeaajuaGcaGGSaGaai4AamaaBaaajuaibaGaaGymaa qcfayabaaacaGLOaGaayzkaaaaaa@4041@ .

Finally, collate sequence and obtain X 1 ( k 1 , k 0 )=X( k ) MathType@MTEF@5@5@+= feaagKart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbmqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaOaamiwam aaBaaajuaibaGaaGymaaqabaqcfaOaaiikaiaadUgadaWgaaqcfasa aiaaigdaaKqbagqaaiaacYcacaWGRbWaaSbaaKqbGeaacaaIWaaaju aGbeaacaGGPaGaeyypa0JaamiwamaabmaabaGaam4AaaGaayjkaiaa wMcaaaaa@4471@ , where k= r 1 × k 1 + k 0 MathType@MTEF@5@5@+= feaagKart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbmqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaOaam4Aai abg2da9iaadkhadaWgaaqcfasaaiaaigdaaKqbagqaaiabgEna0kaa dUgadaWgaaqcfasaaiaaigdaaeqaaiabgUcaRKqbakaadUgadaWgaa qcfasaaiaaicdaaeqaaaaa@4287@ .

X 1 ( k 1 , k 0 )= X 2 ( k 0 , k 1 ) MathType@MTEF@5@5@+= feaagKart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbmqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaOaamiwam aaBaaajuaibaGaaGymaaqabaqcfaOaaiikaiaadUgadaWgaaqcfasa aiaaigdaaKqbagqaaiaacYcacaWGRbWaaSbaaKqbGeaacaaIWaaaju aGbeaacaGGPaGaeyypa0JaamiwamaaBaaajuaibaGaaGOmaaqcfaya baWaaeWaaeaacaWGRbWaaSbaaKqbGeaacaaIWaaajuaGbeaacaGGSa Gaam4AamaaBaaajuaibaGaaGymaaqabaaajuaGcaGLOaGaayzkaaaa aa@4AD9@

This project is used for a 64-point FFT processor.

N= r 1 × r 2 ×r MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbmqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaOaamOtai abg2da9iaadkhadaWgaaqcfasaaiaaigdaaKqbagqaaiabgEna0kaa dkhadaWgaaqcfasaaiaaikdaaKqbagqaaiabgEna0kaadkhaaaa@42A4@ , that is 64=4×4×4 MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbmqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaOaaGOnai aaisdacqGH9aqpcaaI0aGaey41aqRaaGinaiabgEna0kaaisdaaaa@3F73@ .

x( n )=x( r 1 r 2 n 2 + r 3 n 1 + n 0 )=x( n 2 , n 1 , n 0 ),{ n 2=0,1,2,...., r 1 1 n 1 =0,1,2,...., r 2 1 n 0 =0,1,2,...., r 3 1 MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbmqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaOaaiiEam aabmaabaGaamOBaaGaayjkaiaawMcaaiabg2da9iaadIhadaqadaqa aiaadkhadaWgaaqcfasaaiaaigdaaKqbagqaaiaadkhadaWgaaqcfa saaiaaikdaaeqaaKqbakaad6gadaWgaaqcfasaaiaaikdaaeqaaiab gUcaRKqbakaadkhadaWgaaqcfasaaiaaiodaaeqaaKqbakaad6gada WgaaqcfasaaiaaigdaaeqaaKqbakabgUcaRiaad6gadaWgaaqcfasa aiaaicdaaKqbagqaaaGaayjkaiaawMcaaiabg2da9iaadIhadaqada qaaiaad6gadaWgaaqcfasaaiaaikdaaeqaaKqbakaacYcacaWGUbWa aSbaaKqbGeaacaaIXaaabeaajuaGcaGGSaGaamOBamaaBaaajuaiba GaaGimaaqabaaajuaGcaGLOaGaayzkaaGaaiilaiaaykW7caaMc8Ua aGPaVlaaykW7caaMc8+aaiqaaeaafaqabeWabaaabaGaamOBamaaBa aajuaibaGaaGOmaKqbakabg2da9iaaicdacaGGSaGaaGymaiaacYca caaIYaGaaiilaiaac6cacaGGUaGaaiOlaiaac6cacaGGSaGaamOCam aaBaaajuaibaGaaGymaaqabaqcfaOaeyOeI0IaaGymaaqabaaabaGa amOBamaaBaaajuaibaGaaGymaaqabaqcfaOaeyypa0JaaGimaiaacY cacaaIXaGaaiilaiaaikdacaGGSaGaaiOlaiaac6cacaGGUaGaaiOl aiaacYcacaWGYbWaaSbaaKqbGeaacaaIYaaajuaGbeaacqGHsislca aIXaaabaGaamOBamaaBaaajuaibaGaaGimaaqabaqcfaOaeyypa0Ja aGimaiaacYcacaaIXaGaaiilaiaaikdacaGGSaGaaiOlaiaac6caca GGUaGaaiOlaiaacYcacaWGYbWaaSbaaKqbGeaacaaIZaaabeaajuaG cqGHsislcaaIXaaaaaGaay5Eaaaaaa@9343@

Then,

x( n )=x( 16 n 2 +4 n 1 + n 0 )=x( n 2 , n 1 , n 0 ),{ n 2=0,1,2,3 n 1 =0,1,2,3 n 0 =0,1,2,3 MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbmqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaOaaiiEam aabmaabaGaamOBaaGaayjkaiaawMcaaiabg2da9iaadIhadaqadaqa aiaaigdacaaI2aGaamOBamaaBaaajuaibaGaaGOmaaqabaGaey4kaS scfaOaaGinaiaad6gadaWgaaqcfasaaiaaigdaaeqaaKqbakabgUca Riaad6gadaWgaaqcfasaaiaaicdaaKqbagqaaaGaayjkaiaawMcaai abg2da9iaadIhadaqadaqaaiaad6gadaWgaaqcfasaaiaaikdaaeqa aKqbakaacYcacaWGUbWaaSbaaKqbGeaacaaIXaaabeaajuaGcaGGSa GaamOBamaaBaaajuaibaGaaGimaaqabaaajuaGcaGLOaGaayzkaaGa aiilaiaaykW7caaMc8UaaGPaVlaaykW7caaMc8+aaiqaaeaafaqabe WabaaabaGaamOBamaaBaaajuaibaGaaGOmaKqbakabg2da9iaaicda caGGSaGaaGymaiaacYcacaaIYaGaaiilaiaaiodaaeqaaaqaaiaad6 gadaWgaaqcfasaaiaaigdaaeqaaKqbakabg2da9iaaicdacaGGSaGa aGymaiaacYcacaaIYaGaaiilaiaaiodaaeaacaWGUbWaaSbaaKqbGe aacaaIWaaabeaajuaGcqGH9aqpcaaIWaGaaiilaiaaigdacaGGSaGa aGOmaiaacYcacaaIZaaaaaGaay5Eaaaaaa@78F3@

FFT transformation from x( n 2 , n 1 , n 0 ),n=16 n 2+ 4 n 1 + n 0 MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbmqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaOaamiEam aabmaabaGaamOBamaaBaaajuaibaGaaGOmaaqcfayabaGaaiilaiaa d6gadaWgaaqcfasaaiaaigdaaeqaaKqbakaacYcacaWGUbWaaSbaaK qbGeaacaaIWaaajuaGbeaaaiaawIcacaGLPaaacaGGSaGaaGPaVlaa ykW7caWGUbGaeyypa0JaaGymaiaaiAdacaWGUbWaaSbaaKqbGeaaca aIYaqcfaOaey4kaScabeaacaaI0aGaamOBamaaBaaajuaibaGaaGym aaqabaqcfaOaey4kaSIaamOBamaaBaaajuaibaGaaGimaaqabaaaaa@52DD@  to X( k 0 , k 1 , k 2 ) MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbmqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaOaamiwam aabmaabaGaam4AamaaBaaajuaibaGaaGimaaqabaqcfaOaaiilaiaa dUgadaWgaaqcfasaaiaaigdaaeqaaKqbakaacYcacaWGRbWaaSbaaK qbGeaacaaIYaaabeaaaKqbakaawIcacaGLPaaaaaa@41E5@

k=16 k 2+ 4 k 1 + k 0 MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbmqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaOaam4Aai abg2da9iaaigdacaaI2aGaam4AamaaBaaajuaibaGaaGOmaKqbakab gUcaRaqabaGaaGinaiaadUgadaWgaaqcfasaaiaaigdaaeqaaKqbak abgUcaRiaadUgadaWgaaqcfasaaiaaicdaaeqaaaaa@4384@ .

First stage: x( n 2 , n 1 , n 0 ) MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbmqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaOaamiEam aabmaabaGaamOBamaaBaaajuaibaGaaGOmaaqcfayabaGaaiilaiaa d6gadaWgaaqcfasaaiaaigdaaeqaaKqbakaacYcacaWGUbWaaSbaaK qbGeaacaaIWaaajuaGbeaaaiaawIcacaGLPaaaaaa@420E@ , Radix-4 transform to G( k 0 , n 1 , n 0 ) MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbmqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaOaam4ram aabmaabaGaam4AamaaBaaajuaibaGaaGimaaqcfayabaGaaiilaiaa d6gadaWgaaqcfasaaiaaigdaaeqaaKqbakaacYcacaWGUbWaaSbaaK qbGeaacaaIWaaajuaGbeaaaiaawIcacaGLPaaaaaa@41D8@ , twiddle factor W 64 k 0 ( 4 n 1 + n 0 ) MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbmqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaOaam4vam aaDaaajuaibaGaaGOnaiaaisdaaeaacaWGRbqcfa4aaSbaaKazfa0= baGaaGimaaqcfasabaqcfa4aaeWaaKqbGeaacaaI0aGaamOBaKqbao aaBaaajqwba9FaaiaaigdaaKqbGeqaaiabgUcaRiaad6gajuaGdaWg aaqcKvaq=haacaaIWaaabeaaaKqbGiaawIcacaGLPaaaaaaaaa@49C5@ ;

Second stage: G( k 0 , n 1 , n 0 ) MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbmqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaOaam4ram aabmaabaGaam4AamaaBaaajuaibaGaaGimaaqcfayabaGaaiilaiaa d6gadaWgaaqcfasaaiaaigdaaeqaaKqbakaacYcacaWGUbWaaSbaaK qbGeaacaaIWaaajuaGbeaaaiaawIcacaGLPaaaaaa@41D8@ , Radix-4 transform to H( k 0 , k 1 , n 0 ) MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbmqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaOaamisam aabmaabaGaam4AamaaBaaajuaibaGaaGimaaqcfayabaGaaiilaiaa dUgadaWgaaqcfasaaiaaigdaaKqbagqaaiaacYcacaWGUbWaaSbaaK qbGeaacaaIWaaajuaGbeaaaiaawIcacaGLPaaaaaa@41D6@ , twiddle factor W 64 k 1 n 0 MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbmqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaOaam4vam aaDaaajuaibaGaaGOnaiaaisdaaeaacaWGRbqcfa4aaSbaaKqbGeaa caaIXaaabeaacaWGUbqcfa4aaSbaaKazfa0=baGaaGimaaqabaaaaa aa@3FC6@ ;

Third stage: H( k 0 , k 1 , n 0 ) MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbmqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaOaamisam aabmaabaGaam4AamaaBaaajuaibaGaaGimaaqcfayabaGaaiilaiaa dUgadaWgaaqcfasaaiaaigdaaKqbagqaaiaacYcacaWGUbWaaSbaaK qbGeaacaaIWaaajuaGbeaaaiaawIcacaGLPaaaaaa@41D6@ , Radix-4 transform to X( k 0 , k 1 , k 2 ) MathType@MTEF@5@5@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9 vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x fr=xb9adbmqaaeGaciGaaiaabeqaamaabaabaaGcbaqcfaOaamiwam aabmaabaGaam4AamaaBaaajuaibaGaaGimaaqabaqcfaOaaiilaiaa dUgadaWgaaqcfasaaiaaigdaaeqaaKqbakaacYcacaWGRbWaaSbaaK qbGeaacaaIYaaabeaaaKqbakaawIcacaGLPaaaaaa@41E5@ .

Design system structure

Due to complete a 64-point FFT calculation function for the project, the schemes may be selected from the following table (Table 1).8 I use statistical results to select the most suitable circuit structure. If I select the radix-2 scheme, the BR2MDC is better relatively due to the 100 utilization rates and its hardware control is simple relatively. However, since the BR2MDC increases the number of the buffer units, the hardware area used is increased greatly. On the other hand, if I selected the radix-8 scheme, the hardware utilization rate of R8SDF is less than before, but its hardware control is very complicated.9 Thence, the radix-4 scheme is the best choice, and the entire circuit is divided into three levels. Moreover, the hardware utilization rate of R4SDF is few, and its hardware control is not complicated. Therefore, this project uses the radix-4 single-path structure (R4SDF).

Circuit Structure

Complex Multiplier

Complex Adder

Delay     Units

Control Complexity

R2SDF

5

12

31

Simple

R2MDC

5

12

62

Simple

BR2MDC

5

12

190

Simple

R4SDF

2

24

63

Medium

R4MDC

6

24

60

Simple

R8SDF

1

48

Complex

R8MDC

7

48

 

simple

Table 1 statistical results to select the most suitable circuit structure

Experiment results

Figure 1 shows the RTL viewer result. Then, run the Test beach file, and the functional simulation result is described in Figure 2. Finally, check the FFT processor is correct, and Figure 3 shows this FFT processor is applied for image processing.

Figure 1 RTL viewer.
Figure 2 Functional simulations.
Figure 3 Image processing.

Conclusion

This paper analyses the feature of the radix-4 FFT algorithm, advances a pipeline hardware implementation structure, which can reduce consumption of resource ad achieve easily larger points (such as 256 points, 512 points) FFT expansion. The implemented FFT processor meets the high-speed real-time image processing requirements.

The accuracy of addition and multiplication will loss in each level of 64-point FFT. When the values are quantized to 10-bits, the input and output values are 10-bits. Calculating adder and multiplier at each level need to adjust operating bits. In the 64-point processor, there are six levels addition calculation and two levels multiplication calculation. This loss of precision in the 10-bits operation is not negligible. In the future, a good improving method is that append the adder protecting measurement at each level. For example, increasing 1-bit accuracy, six levels adder will increased 6-bits.

Acknowledgements

None

Conflict of interest

The authors declare no conflict of interest.

References

Creative Commons Attribution License

©2018 Cao. This is an open access article distributed under the terms of the, which permits unrestricted use, distribution, and build upon your work non-commercially.