FFT program (C language)

Void FFTT (Struct Complex * a, int L)

{

Const Double Pai = 3.141592653589793;

Struct Complex U, W, T, TMP1;

Unsigned n = 1, NV2, NM1, K, Le, LEI, IP

Unsigned i, j, m;

Double TMP;

n << = L;

NV2 = n >> 1;

Nm1 = N-1;

J = 0;

For (i = 0; i

{

IF (i

{

T.RE = a [j] .re;

T.IM = a [j] .im;

a [j] .re = a [i] .re;

a [j] .im = a [i] .im;

a [i] .re = T.RE;

a [i] .im = T.im;

}

K = NV2;

While (K <= j)

{

J- = k;

K >> = 1;

}

J = K;

}

Le = 1;

FOR (m = 1; m )

{

Lei = Le;

Le << = 1;

U.RE = 1.0;

u.im = 0.0;

TMP = PAI / LEI;

W.RE = COS (TMP);

W.IM = -SIN (TMP);

For (j = 0; J

{

For (i = j; i

{

IP = I LEI;

MUL (a [ip], u, & tmp1);

T.re = tmp1.re;

T.IM = TMP1.IM;

SUB (a [i], t, & tmp1);

a [ip] .re = TMP1.RE;

a [ip] .im = TMP1.IM;

Add (a [i], t, & tmp1);

a [i] .re = tmp1.re;

a [i] .im = TMP1.IM;

}

MUL (u, w, & tmp1);

u.re = TMP1.RE;

u.im = TMP1.IM;

}

}

}