[PDF] Compact C language Fourier analysis on small computers

[PDF] REAL-TIME DSP LABORATORY6: - Colorado State University

In this lab, we will create C code to implement an N-point FFT algorithm, where N is a power of 2 To begin, let's create the C code function FFT func(COMPLEX 

[PDF] FFT-based spectrum analysis using a Digital Signal - CORE

Portable C programs demonstrated optimization of the FFT algorithm performance on complex algorithms requires expert programming at the assembly lan-

[PDF] FFT algorithms in C

24 nov 2012 · the code instead of using a whole library worth of complex black-box algo- rithms In the context of the Fast Fourier Transform (FFT) it is not so 

[PDF] Complex Floating Point Fast Fourier Transform - NXP

adapted for use with AltiVec and how AltiVec increases code performance AltiVec is complex Radix-2 DIF FFT using PowerPC instructions The second Complex Floating Point Fast Fourier Transform, Rev 4 Freescale Semiconductor 9

[PDF] Software Optimization of FFTs and IFFTs Using the SC3850 - NXP

transform, the Radix-4 FFT reduces the number of complex multiplications from N The C code in Example 3 is used to generate the twiddle factors Example 3

[PDF] Fast Fourier Transform Based on XC2000/XE166 Microcontroller

If the input sequence is complex, according to equation (9) and equation (10) Infineon provides the free source code for all FFT implementations introduced in  

[PDF] 18335J (S19) Lecture 39 - Fast Fourier Transform and Fast Fourier

powerful enough to e g derive real-input FFT Optimal cache-oblivious from complex FFT algorithm and even find “new” algorithms Optimized C code (or other 

Compact C language Fourier analysis on small computers

The C language is well suited for the programming of are easily incorporated as parts of a C program whose complex exponential form of the FFT For some  

[PDF] complex fft c++

[PDF] complex fft output

[PDF] complex fft python

[PDF] complex fft to power spectrum

[PDF] complex fft vs real fft

[PDF] complex fir filter

[PDF] complex fourier series coefficients calculator

[PDF] complex fourier transform formula

[PDF] complex number real fft

[PDF] complex numbers input fft

[PDF] complex time domain signal

[PDF] complexity of lu factorization

[PDF] components of graphical user interface

[PDF] composite can be classified based on

[PDF] composite materials can be classified based on

/988, 20(4),423-426

Compact C languageFourieranalysis on

small computers

PHILLIPL. EMERSON

Cleveland State University, Cleveland, Ohio

The C language is well suited for theprogrammingof smallcomputersfor data collection in real-time labora tory research, so it is becoming convenient to code some of the analysis programs also in

C.The pair of C rou

tines presented here is for simple applications of the fast Fourier transform (FFT). These routines are written com pactly for small analyses. They are not optimallyefficient, and they areconstrainedby some limitations that can be transcendedby usingcommerciallyavailable

FFTpro

grams,such as those reviewed by Eddy andBremner (1983).Nevertheless,they have the advantage that they are easilyincorporatedas parts of a C program whose main purpose is something other thanFourieranalysis. Beinginsource-codeform, theseroutinesare easyto adapt for various purposes. Such adaptations require some acquaintance with the C language. Kernighan andRitchie's(1988) book can be consulted for the general principles of Cprogramming, and the software documentationfor a particular implemen tation of C usually covers specific exceptions and inno vations. As analternative,a main callingprogramis in cluded here that can be used in many on-line applications without additionalprogramming. Potential users who have little acquaintance with Fou rier analysis may want to consult Kaplan (1983), who ex plained it in the familiar termsofcorrelationsand vari ancecomponents.Fourieranalysis is fundamentally the same as trend analysis using orthogonal polynomials, ex cept that periodic sine and cosine components are used in place of the polynomial components, such as those that are linear,quadratic,and cubic.Fourieranalysis is often used for analyzing cyclic data, such as EEG, speech, animal sounds, and slower biological rhythms. Meaning ful analysisrequiresexperimentaldesign planning that is peculiar toFourieranalysis and, often, somepreprocess ing of the data before the FFT isperformed(Blackman&Tukey,1958; Glass, Wilson,&Gottman, 1975).

TheAlgorithmandProgramElements.In the stan

dardterminologyfor variations on the fundamental FFT algorithm (Liu, 1975), the method used here is frequency decimationwith postshuftling.

Itwas coded firstinBASIC

(Emerson,1980) and now in C, directly from the signal flow graph of Figure 10 inCochranet al. (1967). The radix is 2, for the simplestcomputationalalgorithm,and thecomputationsare done in place inthe sense that the

transformends up in the same memory arrays in whichTheauthor'smailingaddressis Department of Psychology, Cleveland

StateUniversity,Cleveland,OH44115.

the original data were stored. AnAarray is used for the real components and

Bfor the imaginary. Actually, both

arrayshold realquantities,but those in theBarray are assumed implicitly to have thecoefficient so that each (A,B)pairrepresentsa complex number.1The in dex,i,runs from 0 to n-1, wherenis the number of elements in each of the twoarrays.Because the radix is

2,nmust be an integral power of 2. The main computa

tions of the FFT areperformedby the freqdec( ) routine shown in Listing 1. Before calling freqdec( ) for the first time with a new value ofn,the calling program must cre ate the q[]array,which is aquarter-wavetable of co sines to be used in the

FFTcalculations. The ith element

of q[]iscos(2ri/n),for 0:Si:Sn/4.Theqarray is not modified by calls tofreqdec().The direction of the trans form, forward (time to frequency) or inverse (frequency to time), iscontrolledby theargumentsgn in the call to freqdec()(sgn =1forforward;sgn=-1for inverse). Assume that a time series is to betransformed,and that it is obtained as a sequence of equally spaced measure ments on somequantitativevariable. As soon asnis known, the qarray can be constructed. Then the elements of the time series should be inserted intheir naturalorder into the

Aarray,starting atA

o.

Ifpossible, the length of

the time series should be made an integral power of 2 in theexperimentaldesign.

Ifthat cannot be done, then the

series will not fill the

Aarray,and a data window of the

length ofthe actual time series should be applied, with the trailing empty

Aelements set equal to zero. This data

window should betaperedtoward zero on both ends, as is the Hamming window, which will be used in an exam ple.? All of theBelements should be set equal to zero.

Thefreqdec()

routine should then becalled,and post shuffling should be done using bitrev( ), as will be illus trated. Note that theAand theBarrays will contain the complexexponentialform of theFFT. For some purposes, the coefficients (aj,bj)in thetrigonometricform of the

Fourierseries are needed. This series is

ao+E[ajcos(2rij/n)+bjsin(2rij/n)], where the summation starts atj=1. These coefficients are obtainable from the elements oftheAandBarrays,after postshuffling,as ao=Ao/n,b o =0, and aj =(Aj+An-j)/n, bj=(-Bj+Bn-j)/n, for 0ACalling

Program.The mainprogramof Listing 2

can be used for testpurposesand for some real applica tions.

Itcompiles withpopularCimplementations,such

423Copyright1988 Psychonomic Society, Inc.

424 EMERSON

LISTING1

The

FFrSubroutines

1*fftpak1.c-- thenameofthisfile.*1

1*******TheprimaryFFTcomputations,leaving only thepost-shuffling.****1

voidfreqdec(n,sgn,A,B,q) intn,sgn ; }1*u=cos*1 }1*v=sin*1 v = sgn*q[n/4 -k] v = sgn*q[k -n/4] double A[],B[].en ; (intgap,jump,j,k,i,h,m doublex,y,u,v for(gap=n/2,jump= 1 ; gap ; gap1=2,jump*= 2) for(j=O ; j < jumpij++) for(i= 2*gap*j,m=i+gap,k = 0ii < mii++, k+=jump) ( h = gap + i i x = A[i] -A[h]

Y= B[i] - B[h]

A[i]+=A[h]

B[i]+=B[h]

if(k<=n/4){u= q[k] else{ u =-q[n/2-k]

A[h]= u*x + v*y

B[h]= u*y - v*x

intbitrev(word,n)intword,ni (inttem,tern1 tem1= 1in»=1 ; for(tem=0i n tem1"=1, n»=1) if(n&word)tern1=tern1i return(tern)i n isintegralpowerof 2*1 1* andword< n.*1 1*

Shiftn andtem1*1

1* oppositely.*1 1*

Set tembitif*1

1* wordbit= 1.*1 1*

Resultisin tern.*1

LISTING2

A MainProgramCalling theFFrRoutineswithInputDatafromKeyboardor File, andOutputtoScreenorFile

1*Thefileofroutinesfor theFFT.

1*pi to 15places.

1*Themaximumlength ofseriestransformable.

1*librarymemoryallocator.

1*librarycosinefunction.

1*dofft.cthenameof

#include #include

Ifttpak1.c"

#definePI3.141592653589793 #define

NMAX2048

char*callocO doublecos()i thisfile.*1 *1 *1 *1 *1 *1

1******A workable program.****1

1*A,B,qwillbearrays.*1

1*

Allocationof space for*1

1* the A and Barraays.*1 1*

Abortifnot*1

exit(1)i)1*enoughspace.*1 1*

Forwardor*1

0» sgn =-,1*inverse?*/

main(argc,argv)intargcichar *argv[]i {intI,J,n,sgndouble *A,*B,*q,z

A = (double *) calloc(NMAX,sizeof(double)

B = (double *) calloc(NMAX,sizeof(double)

if((A==NUll) 1I(B==NUll) ) (fputs("Memoryoverflow\n",stderr) sgn = 1 i if((argc> 1)&&(strcmp("_I,argv[1])--

CLANGUAGEFOURIERANALYSIS425

LISTING 2(CooliDued)

if(isatty(fileno(stdin)) ) /*Promptneeded?*/ fputS("type thepairsof AB values; end withCTRL-Z\n",stderr); for(i=O; i =i )break; fore ; i < no;i++) { A[il =

0.;B[il =0.;}

q = (double *)calloc(n/4+1,sizeof(double)) ; if(q==NULL) fputs("Memoryoverflow\n",stderr);exit(1); } for(i=O; i <=n/4 ; i++)q[il=cos(2.*PI*i/n); freqdec(n,sgn,A,B,q); for(i=O ; i < n ; i++) ( j=bitrev(i,n); printf("X20.10leX20.10le\n",A[jl .etrn ; /*Getdata.*/ /* Stop on

EOF.*/

/* But i=NMAXand */ /* no

EOFiserror.*/

/*iisnumberof*/ /* datalines.*/

1*Makenintegral*/

/*powerof 2. */ /*Allocatespace*/ /* but abortif*/ /* notavailable,*/ /* andfillin q.*/ /*DotheFFT.*/ /*Postshuffle*/ /* onoutput.*/ asMicrosoftC,DatalightC, andBorlandTurboC. It performsasingle

FFfandthenexitstotheoperatingsys

tem. It is a minimalFFfprogram,but it isdesignedto be used withreadily availablesupportingfacilitiesthat makeit quiteflexible.Theinput/outputredirectionand pipingcapabilitiesof

MS-DOSare veryhelpful,andthe

data-manipulationprogramsin

Perlmanand Horan's

bility.quotesdbs_dbs20.pdfusesText_26