AP1634 Fast Fourier Transformation Fast Fourier Transformati
|
|
|
Top Searches for this datasheet
additional file AP163402.EXE available
AP1634
Fast Fourier Transformation
Fast Fourier Transformation (FFT) algorithm frequently used various applications, like telecommunication, signal image processing. transforms time domain into frequency domain where spectrum amplitude frequency analyzed.
Westerholz Siemens
Semiconductor Group
03.97, Rel.
Fast Fourier Transformation
Abstract Derivation algorithm Implementation Flow chart 1024-point real valued Flowchart Midloop Register content.
AP1634 ApNote Revision History Actual Revision Rel.01 Previous Revison: none Page Page Subjects changes since last release) actual Rel. prev. Rel.
Semiconductor Group
AP1634 03.97
Fast Fourier Transformation
Abstract
Fast Fourier Transformation (FFT) algorithm frequently used various applications, like telecommunication, signal image processing. transforms time domain into frequency domain where spectrum amplitude frequency analyzed. This application note describes implementation real-valued 1024 point decimation time radix-2 C166 microcontroller family. Assuming that code started internal 16-bit demultiplexed bus, execution time been achieved C165 running internal clock. code comprises bytes. This application note based application note performed (Programmierbare Logik Systeme, Hoyerswerda, Germany).
Derivation algorithm
Starting from continuous time Fourier Transformation, discrete Fourier Transformation derived function sample points (N): WNnk
k=0,1,.,N-1
This formula regarded matrix multiplied input data vector x(n). This simple complexity coefficients matrix will denoted following twiddle factors.
order derive radix-2 algorithm, decompose transformation into partial transformations, containing input data with even indices, other with odd. Exploiting symmetries twiddle factors decomposition achieved that only requires multiplications.
x(2n
x(2n
(N/2)-1
Semiconductor Group
AP1634 03.97
Fast Fourier Transformation
number multiplications further repetitive employing this process partial transformations P(k) Q(k) till they completely decomposed into point DFTs (Discrete Fourier Transformations). 2-point commonly referred butterfly operation. butterfly requires complex multiplications resulting four real valued multiplications computing terms P(k) Q(k). Pn+1 n=stage Qn+1 since e-j(2/N)k cos(u) sin(u) (2/N)k
Re(Pn) Im(Pn)
Re(Pn+1) Im(Pn+1)
Re(Qn) Im(Qn)
Re(Qn+1) Im(Qn+1)
Having only real valued input data x(n), computational effort point reduced point complex FFT. Firstly, even indexed data h(n) indexed data g(n) x(2n separated. index running from N-1. h(n) g(n) have spectra H(k) G(k) respectively. spectrum X(k) decomposed into spectra H(k) G(k) follows:
Fourier Transformation (cos
order above point transformation into point transformation complex input vector y(n) h(n) jg(n) formed with index running from N/2-1. real input values formed even indexed input data h(n). imaginary part formed indexed input data g(n). Then y(n) transformed into frequency domain resulting spectrum consisting superposition spectra H(k) G(k). y(n) h(n) jg(n) Fourier Transformation complex spectra H(k) G(k) have extracted complex spectrum jG(k employing symmetry relations, spectra H(k) G(k) derived from spectrum Y(n) follows: Re{H Re{G(k Im{G( Im{H
These spectra inserted into equation X(n) deliver full spectrum.
Semiconductor Group
AP1634 03.97
Fast Fourier Transformation
order illuminate algorithm, example given below shall demonstrate computational process during 8-point FFT. input data consists complex numbers which also perceived real numbers x(0).x(15).
Input
X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) X(8) X(9) X(10 X(11 X(12 X(13 X(14 X(15
Stage
Stage
Stage
Output
X(0) X(1)
X(8) X(9) X(4) X(5)
X(12 X(13 X(2) X(3)
X(10 X(11 X(6) X(7)
X(14 X(15
Semiconductor Group
AP1634 03.97
Fast Fourier Transformation
Corresponding above butterfly operation, input data connected with each other. nature this operation input data sequentially ordered, while output data bitreversed order. each stage four (=N/2) butterflies computed. twiddle factor stage always stage upper half consists again butterflies from previous stage. second half butterflies computed with twiddle factor third stage twiddle factors previous stage appear again upper half lower half contains factors W83. 8-point-FFT twiddle factors e-j(2/N)k cos(X) sin(X) have following values. Twiddle factor e-j(/4) e-j(/2) e-j(3/4) e-j(5/4) e-j(3/2) e-j(7/4) cos(X) sin(X)
Im(W)
Re(W)
Because symmetry twiddle factor only first four (W80 must computed. These four twiddle factors lead degenerated butterflies. They used precompute butterflies first three stages reduce number multiplications. twiddle factors butterfly computation simplified. have cos(X) sin(X) This results butterfly without multiplications: Pn+1 Qn+1 [Re(Pn) Re(Qn) [Im(Pn) Im(Qn)] [Re(Pn) Re(Qn)] [Im(Pn) Im(Qn)]
Semiconductor Group
AP1634 03.97
Fast Fourier Transformation
cos(X) sin(X) This results butterfly third stage where only multiplications must executed: Pn+1 [Re(Pn) Re(Qn) cos(X) Im(Qn) cos(X)] [Im(Pn) Im(Qn) cos(X) Re(Qn) cos(X)] Qn+1 [Re(Pn) Re(Qn) cos(X) Im(Qn) cos(X)] [Im(Pn) Im(Qn) cos(X) Re(Qn) cos(X)] have cos(X) sin(X) This results butterfly without multiplications used second third stage:
Pn+1 Qn+1
[Re(Pn) Im(Qn)] [Im(Pn) Re(Qn)] [Re(Pn) Im(Qn)] [Im(Pn) Re(Qn)]
-cos(X) sin(X) This results butterfly third stage where only multiplications must executed:
Pn+1 [Re(Pn) Re(Qn) cos(X) Im(Qn) cos(X)] [Im(Pn) Im(Qn) cos(X) Re(Qn) cos(X)] Qn+1 [Re(Pn) Re(Qn) cos(X) Im(Qn) cos(X)] [Im(Pn) Im(Qn) cos(X) Re(Qn) cos(X)] output decimation time shows bitreversed order that ordered calculate final frequency spectrum. Supposing input data been sequential order, indices output data easily computed reversing binary presentation input indices. table below gives example reversal point FFT. Order Input data Order output data bitreversed index binary binary index
Semiconductor Group
AP1634 03.97
Fast Fourier Transformation
Implementation
implementation assume real valued input data. Based this assumption, real valued 1024 point reduced point complex followed unweave phase order compute 1024 point spectrum. point complex consists log2 (512) stages each stage calculates 512/2 butterflies. twiddle factors first three stages same point complex FFT. input data stored table FFT_IN which consists 1024 words. Since perform in-place FFT, input data field will overwritten output data. However, final output will stored separate FFTOUT output field. providing trigonomic functions, table (FFT_DAT) stored encompassing precomputed sinus cosines values. Since cos(x) sin(x+/4) table consists sinus period cosines period. Together they form sinus period. rearrange bitreversed output complex calculate twiddle factor bitreversal table (FFT_BR) also been precomputed. input data trigonometric function table represented fixed-point fraction two's complement. This means that such number represents sign, followed bits representing fraction one. examples: binary 0111 1111 1111 1111 0110 0000 0000 0000 1010 0000 0000 0000 1000 0000 0000 0000 7FFF 6000 A000 8000 32767 24576 -24576 -32768 value 0.75 0.75
2-15
Since addition numbers having same sign might cause overflow, numbers have divided before adding them. This done arithmetic shift right. When multiplying 15-bit-numbers, note that signs both multiplied too, result stored 32-bit wide multiplication register.
Therefore result equal scaled multiplication that means that consists multiplication subsequent arithmetic shift right side effect. Because precision required, only first bits contained register used further calculations. Attached will find program flow chart. first part program consists 512point complex radix-2 which executed nine stages. avoid multiplications
Semiconductor Group
AP1634 03.97
Fast Fourier Transformation
means degenerated butterflies, different Mid- Inloops implemented. idea amount calculation needed using degenerated butterflies stages. This very effective first three stages, time savings decreases rear stages. Regarding complex point FFT, number twiddle factors amounts 512. However, symmetry only first (0.255) used. program source twiddle factors denoted refer angles 90°, 135°. Thus, corresponds W12. Stage 1:Since stage twiddle factors butterflies performed Inloop_0. Stage Stage butterflies with Inloop_0 butterflies with Inloop_1 butterflies with Inloop_0 butterflies with Inloop_1 butterflies with Inloop_2 butterflies with Inloop_3 butterflies with Inloop_0 butterflies with Inloop_1 butterflies with Inloop_2 butterflies with Inloop_3 butterflies with Inloop
Stage
second part program unweaves bitreversed output 512-point extract 1024 point real valued FFT. Optional, final stage algorithm calculates amplitude spectrum. last page will find register during program execution. Assuming that code started internal ROM, input data stored external accessed 16-bit demultiplexed without wait states (Syscon: ROMEN=1, Buscon: MTTC=1, MCTC 1111, BTYP execution time real valued 1024-point achieved C165 running internally. code size amounts bytes without data tables. optional computation amplitude spectrum consumes additional execution time independent from input data. Changing number sample points number stages exp, reducing tables, algorithm tailored various resolutions. table below will find execution times different numbers sample points.
64-Points SAB-C165 MHz) 0,56 SAB-C167CR MHz)
Semiconductor Group
256- Points
1024- Points 10,4
AP1634 03.97
Fast Fourier Transformation
This figures demonstrate that C166 architecture even superior some signal processors. This result founded multiplication execution time 400ns RISC like register file. Using more complex radix-4 algorithm combining butterflies further time saving expected. Keeping input output tables internal additional speed achieved point FFT. only parts spectrum have analyzed, partial performed omitting calculations contributing frequency window. Literature Application Note AP-275 Algorithm MCS-96 Products including Supporting Routines Examples", intel September 1986 MS-C-Program TMS32010 High Performance 16/32-Bit Digital Signal Processor Product Description Texas Instruments 1985 Digital Signal Processing Applications with TMS320 Family Texas Instruments 1988 TMS320C25 Digital Signal Processor Product Description Texas Instruments 1986 S.K. Mitra J.F. Kaiser, Handbook Digital Signal Processing, John Wiley Sons, 1993 Maurice Bellanger, Digital Processing Signals, John Wiley Sons, 1989
Semiconductor Group
AP1634 03.97
Fast Fourier Transformation
Flow chart 1024-point real valued
Start Outloop stages
Midloop_0 Inloop_0: compute butterflies with twiddlefactor
elements processed
Midloop_1 Inloop_1: compute butterflies with twiddlefactor
elements processed
Midloop_2 Inloop_2: compute butterflies with twiddlefactor Midloop_3 Inloop_3: compute butterflies with twiddlefactor
elements processed
Midloop Inloop: computation remaining butterflies
elements processed END_Midloop
stage executed
unweave complex result real valued bitreversal FFT_IN generate butterflies
calculate absolute values last element processed
Absolute value "Absolute"
(calculate absolute values write results FFT_OUT)
Semiconductor Group
AP1634 03.97
Fast Fourier Transformation
Flowchart Midloop
Midloop
Init counter Inloop input pointers index Determination Twiddle-factor
Inloop Read input values
Re(Pm), Im(P Re(Q Im(Q from FFT_IN
Calculate Butterfly
Pm+1 QRcos(X) QIsin(X) QIcos(X) QRsin(X)] Qm+1 QRcos(X) QIsin(X) QIcos(X) QRsin(X)]
Write output values
Re(Pm+1 Im(P Re(Q Im(Q FFT_IN increment index pointers decrement counter in_loop
counter in_loop
increment counter mid_loop
Midloop
counter mid_loop 2040
modify help counters decrement counter out_loop
stage executed
Semiconductor Group
AP1634 03.97
Fast Fourier Transformation
Register content Stage
256.0 128.0 Stage1 1024 2048 N*24 Stage2 1024 0.N* Stage3 0.N* Twid/B cos[k] 64.0 p_FFT Stage4 0.N* Twid/B cos[k] sin[k] 32.0 p_FFT Stage5 0.N* Twid/B cos[k] sin[k] 16.0 p_FFT Stage6 0.N* Twid/B cos[k] sin[k] p_FFT Stage7 0.N* Twid/B cos[k] sin[k] p_FFT Stage8 0.N* Twid/B cos[k] sin[k] p_FFT Stage9 0.N* Twid/B cos[k] sin[k] p_FFT p_FFT_In Inloop Note Outloop counter Midloop
pP_FFT_IN pQ_FFT_IN
p_FFT_I p_FFT
number samples (1024); butterfly; Twid twiddle factor; pointer onto element pointer onto element Stage procedure ,,Absolute":
Stage Input temp sin[k] Input temp Absolute Input (Low) Input (High) Output temp temp temp temp temp Stage10 cos[k] Input Input 0,2,4,6,8,.,10 FFT_OUT Absolute
Semiconductor Group
AP1634 03.97
Other recent searches
WP934ZH - WP934ZH WP934ZH Datasheet
TMS320C6000 - TMS320C6000 TMS320C6000 Datasheet
SN74LV32A - SN74LV32A SN74LV32A Datasheet
SA5775A - SA5775A SA5775A Datasheet
PD-21033 - PD-21033 PD-21033 Datasheet
MIC2211 - MIC2211 MIC2211 Datasheet
GL949 - GL949 GL949 Datasheet
BCM5631 - BCM5631 BCM5631 Datasheet
Privacy Policy | Disclaimer
© 2012 Datasheet Archive
