GraphicEqFFT - A Graphic Equaliser using 2 Analog inputs and an …

Users » User_4574 » Code » GraphicEqFFT

Næþ'n Lasseter / Mbed 2 deprecated GraphicEqFFT

A Graphic Equaliser using 2 Analog inputs and an Fast Fourier Transform

fft.cpp@0:b771a5301e43, 2010-03-18 (annotated)

Committer:: User_4574
Date:: Thu Mar 18 15:15:33 2010 +0000
Revision:: 0:b771a5301e43

Who changed what in which revision?

User	Revision	Line number	New contents of line
User_4574	0:b771a5301e43	1	/*
User_4574	0:b771a5301e43	2	* This is not my code and I do not take credit for it.
User_4574	0:b771a5301e43	3	* http://www.mit.edu/~emin/source_code/fft/index.html
User_4574	0:b771a5301e43	4	*/
User_4574	0:b771a5301e43	5
User_4574	0:b771a5301e43	6	#define SIN_2PI_16 0.38268343236508978
User_4574	0:b771a5301e43	7	#define SIN_4PI_16 0.707106781186547460
User_4574	0:b771a5301e43	8	#define SIN_6PI_16 0.923879532511286740
User_4574	0:b771a5301e43	9	#define C_P_S_2PI_16 1.30656296487637660
User_4574	0:b771a5301e43	10	#define C_M_S_2PI_16 0.54119610014619690
User_4574	0:b771a5301e43	11	#define C_P_S_6PI_16 1.3065629648763766
User_4574	0:b771a5301e43	12	#define C_M_S_6PI_16 -0.54119610014619690
User_4574	0:b771a5301e43	13
User_4574	0:b771a5301e43	14	/* INPUT: float input[16], float output[16] */
User_4574	0:b771a5301e43	15	/* OUTPUT: none */
User_4574	0:b771a5301e43	16	/* EFFECTS: Places the 16 point fft of input in output in a strange */
User_4574	0:b771a5301e43	17	/* order using 10 real multiplies and 79 real adds. */
User_4574	0:b771a5301e43	18	/* Re{F[0]}= out0 */
User_4574	0:b771a5301e43	19	/* Im{F[0]}= 0 */
User_4574	0:b771a5301e43	20	/* Re{F[1]}= out8 */
User_4574	0:b771a5301e43	21	/* Im{F[1]}= out12 */
User_4574	0:b771a5301e43	22	/* Re{F[2]}= out4 */
User_4574	0:b771a5301e43	23	/* Im{F[2]}= -out6 */
User_4574	0:b771a5301e43	24	/* Re{F[3]}= out11 */
User_4574	0:b771a5301e43	25	/* Im{F[3]}= -out15 */
User_4574	0:b771a5301e43	26	/* Re{F[4]}= out2 */
User_4574	0:b771a5301e43	27	/* Im{F[4]}= -out3 */
User_4574	0:b771a5301e43	28	/* Re{F[5]}= out10 */
User_4574	0:b771a5301e43	29	/* Im{F[5]}= out14 */
User_4574	0:b771a5301e43	30	/* Re{F[6]}= out5 */
User_4574	0:b771a5301e43	31	/* Im{F[6]}= -out7 */
User_4574	0:b771a5301e43	32	/* Re{F[7]}= out9 */
User_4574	0:b771a5301e43	33	/* Im{F[7]}= -out13 */
User_4574	0:b771a5301e43	34	/* Re{F[8]}= out1 */
User_4574	0:b771a5301e43	35	/* Im{F[8]}=0 */
User_4574	0:b771a5301e43	36	/* F[9] through F[15] can be found by using the formula */
User_4574	0:b771a5301e43	37	/* Re{F[n]}=Re{F[(16-n)mod16]} and Im{F[n]}= -Im{F[(16-n)mod16]} */
User_4574	0:b771a5301e43	38
User_4574	0:b771a5301e43	39	/* Note using temporary variables to store intermediate computations */
User_4574	0:b771a5301e43	40	/* in the butterflies might speed things up. When the current version */
User_4574	0:b771a5301e43	41	/* needs to compute a=a+b, and b=a-b, I do a=a+b followed by b=a-b-b. */
User_4574	0:b771a5301e43	42	/* So practically everything is done in place, but the number of adds */
User_4574	0:b771a5301e43	43	/* can be reduced by doinc c=a+b followed by b=a-b. */
User_4574	0:b771a5301e43	44
User_4574	0:b771a5301e43	45	/* The algorithm behind this program is to find F[2k] and F[4k+1] */
User_4574	0:b771a5301e43	46	/* seperately. To find F[2k] we take the 8 point Real FFT of x[n]+x[n+8] */
User_4574	0:b771a5301e43	47	/* for n from 0 to 7. To find F[4k+1] we take the 4 point Complex FFT of */
User_4574	0:b771a5301e43	48	/* exp(-2pijn/16){x[n] - x[n+8] + j(x[n+12]-x[n+4])} for n from 0 to 3.*/
User_4574	0:b771a5301e43	49
User_4574	0:b771a5301e43	50	void fft(float input[16],float output[16] ) {
User_4574	0:b771a5301e43	51	float temp, out0, out1, out2, out3, out4, out5, out6, out7, out8;
User_4574	0:b771a5301e43	52	float out9,out10,out11,out12,out13,out14,out15;
User_4574	0:b771a5301e43	53
User_4574	0:b771a5301e43	54	out0=input[0]+input[8]; /* output[0 through 7] is the data that we */
User_4574	0:b771a5301e43	55	out1=input[1]+input[9]; /* take the 8 point real FFT of. */
User_4574	0:b771a5301e43	56	out2=input[2]+input[10];
User_4574	0:b771a5301e43	57	out3=input[3]+input[11];
User_4574	0:b771a5301e43	58	out4=input[4]+input[12];
User_4574	0:b771a5301e43	59	out5=input[5]+input[13];
User_4574	0:b771a5301e43	60	out6=input[6]+input[14];
User_4574	0:b771a5301e43	61	out7=input[7]+input[15];
User_4574	0:b771a5301e43	62
User_4574	0:b771a5301e43	63
User_4574	0:b771a5301e43	64
User_4574	0:b771a5301e43	65	out8=input[0]-input[8]; /* inputs 8,9,10,11 are */
User_4574	0:b771a5301e43	66	out9=input[1]-input[9]; /* the Real part of the */
User_4574	0:b771a5301e43	67	out10=input[2]-input[10]; /* 4 point Complex FFT inputs.*/
User_4574	0:b771a5301e43	68	out11=input[3]-input[11];
User_4574	0:b771a5301e43	69	out12=input[12]-input[4]; /* outputs 12,13,14,15 are */
User_4574	0:b771a5301e43	70	out13=input[13]-input[5]; /* the Imaginary pars of */
User_4574	0:b771a5301e43	71	out14=input[14]-input[6]; /* the 4 point Complex FFT inputs.*/
User_4574	0:b771a5301e43	72	out15=input[15]-input[7];
User_4574	0:b771a5301e43	73
User_4574	0:b771a5301e43	74	/First we do the "twiddle factor" multiplies for the 4 point CFFT /
User_4574	0:b771a5301e43	75	/Note that we use the following handy trick for doing a complex /
User_4574	0:b771a5301e43	76	/multiply: (e+jf)=(a+jb)(c+jd) */
User_4574	0:b771a5301e43	77	/* e=(a-b)d + a(c-d) and f=(a-b)d + b(c+d) */
User_4574	0:b771a5301e43	78
User_4574	0:b771a5301e43	79	/* C_M_S_2PI/16=cos(2pi/16)-sin(2pi/16) when replaced by macroexpansion */
User_4574	0:b771a5301e43	80	/* C_P_S_2PI/16=cos(2pi/16)+sin(2pi/16) when replaced by macroexpansion */
User_4574	0:b771a5301e43	81	/* (SIN_2PI_16)=sin(2pi/16) when replaced by macroexpansion */
User_4574	0:b771a5301e43	82	temp=(out13-out9)*(SIN_2PI_16);
User_4574	0:b771a5301e43	83	out9=out9*(C_P_S_2PI_16)+temp;
User_4574	0:b771a5301e43	84	out13=out13*(C_M_S_2PI_16)+temp;
User_4574	0:b771a5301e43	85
User_4574	0:b771a5301e43	86	out14*=(SIN_4PI_16);
User_4574	0:b771a5301e43	87	out10*=(SIN_4PI_16);
User_4574	0:b771a5301e43	88	out14=out14-out10;
User_4574	0:b771a5301e43	89	out10=out14+out10+out10;
User_4574	0:b771a5301e43	90
User_4574	0:b771a5301e43	91	temp=(out15-out11)*(SIN_6PI_16);
User_4574	0:b771a5301e43	92	out11=out11*(C_P_S_6PI_16)+temp;
User_4574	0:b771a5301e43	93	out15=out15*(C_M_S_6PI_16)+temp;
User_4574	0:b771a5301e43	94
User_4574	0:b771a5301e43	95	/* The following are the first set of two point butterfiles */
User_4574	0:b771a5301e43	96	/* for the 4 point CFFT */
User_4574	0:b771a5301e43	97
User_4574	0:b771a5301e43	98	out8+=out10;
User_4574	0:b771a5301e43	99	out10=out8-out10-out10;
User_4574	0:b771a5301e43	100
User_4574	0:b771a5301e43	101	out12+=out14;
User_4574	0:b771a5301e43	102	out14=out12-out14-out14;
User_4574	0:b771a5301e43	103
User_4574	0:b771a5301e43	104	out9+=out11;
User_4574	0:b771a5301e43	105	out11=out9-out11-out11;
User_4574	0:b771a5301e43	106
User_4574	0:b771a5301e43	107	out13+=out15;
User_4574	0:b771a5301e43	108	out15=out13-out15-out15;
User_4574	0:b771a5301e43	109
User_4574	0:b771a5301e43	110	/The followin are the final set of two point butterflies /
User_4574	0:b771a5301e43	111	output[1]=out8+out9;
User_4574	0:b771a5301e43	112	output[7]=out8-out9;
User_4574	0:b771a5301e43	113
User_4574	0:b771a5301e43	114	output[9]=out12+out13;
User_4574	0:b771a5301e43	115	output[15]=out13-out12;
User_4574	0:b771a5301e43	116
User_4574	0:b771a5301e43	117	output[5]=out10+out15; /* implicit multiplies by */
User_4574	0:b771a5301e43	118	output[13]=out14-out11; /* a twiddle factor of -j */
User_4574	0:b771a5301e43	119	output[3]=out10-out15; /* implicit multiplies by */
User_4574	0:b771a5301e43	120	output[11]=-out14-out11; /* a twiddle factor of -j */
User_4574	0:b771a5301e43	121
User_4574	0:b771a5301e43	122
User_4574	0:b771a5301e43	123	/* What follows is the 8-point FFT of points output[0-7] */
User_4574	0:b771a5301e43	124	/* This 8-point FFT is basically a Decimation in Frequency FFT */
User_4574	0:b771a5301e43	125	/* where we take advantage of the fact that the initial data is real*/
User_4574	0:b771a5301e43	126
User_4574	0:b771a5301e43	127	/* First set of 2-point butterflies */
User_4574	0:b771a5301e43	128
User_4574	0:b771a5301e43	129	out0=out0+out4;
User_4574	0:b771a5301e43	130	out4=out0-out4-out4;
User_4574	0:b771a5301e43	131	out1=out1+out5;
User_4574	0:b771a5301e43	132	out5=out1-out5-out5;
User_4574	0:b771a5301e43	133	out2+=out6;
User_4574	0:b771a5301e43	134	out6=out2-out6-out6;
User_4574	0:b771a5301e43	135	out3+=out7;
User_4574	0:b771a5301e43	136	out7=out3-out7-out7;
User_4574	0:b771a5301e43	137
User_4574	0:b771a5301e43	138	/* Computations to find X[0], X[4], X[6] */
User_4574	0:b771a5301e43	139
User_4574	0:b771a5301e43	140	output[0]=out0+out2;
User_4574	0:b771a5301e43	141	output[4]=out0-out2;
User_4574	0:b771a5301e43	142	out1+=out3;
User_4574	0:b771a5301e43	143	output[12]=out3+out3-out1;
User_4574	0:b771a5301e43	144
User_4574	0:b771a5301e43	145	output[0]+=out1; /* Real Part of X[0] */
User_4574	0:b771a5301e43	146	output[8]=output[0]-out1-out1; /Real Part of X[4] /
User_4574	0:b771a5301e43	147	/* out2 = Real Part of X[6] */
User_4574	0:b771a5301e43	148	/* out3 = Imag Part of X[6] */
User_4574	0:b771a5301e43	149
User_4574	0:b771a5301e43	150	/* Computations to find X[5], X[7] */
User_4574	0:b771a5301e43	151
User_4574	0:b771a5301e43	152	out5*=SIN_4PI_16;
User_4574	0:b771a5301e43	153	out7*=SIN_4PI_16;
User_4574	0:b771a5301e43	154	out5=out5-out7;
User_4574	0:b771a5301e43	155	out7=out5+out7+out7;
User_4574	0:b771a5301e43	156
User_4574	0:b771a5301e43	157	output[14]=out6-out7; /* Imag Part of X[5] */
User_4574	0:b771a5301e43	158	output[2]=out5+out4; /* Real Part of X[7] */
User_4574	0:b771a5301e43	159	output[6]=out4-out5; /Real Part of X[5] /
User_4574	0:b771a5301e43	160	output[10]=-out7-out6; /* Imag Part of X[7] */
User_4574	0:b771a5301e43	161	}

Repository toolbox

Export to desktop IDE

Build repository

Repository details

Type:	Program
Mbed OS support:	Mbed 2 deprecated
Created:	18 Mar 2010
Imports:	85
Forks:	0
Commits:	1
Dependents:	0
Dependencies:	1
Followers:	5

fft.cpp@0:b771a5301e43, 2010-03-18 (annotated)

Who changed what in which revision?

Repository toolbox

Repository details

Important Information for this Arm website

Access Warning