8.1. FOURIER TRANSFORMS 119
wI = cos(arg);
wR = sin(arg);
sumXr[i] += data->real[j] * wR + data->imaginary[j] * wI;
sumXi[i] += data->imaginary[j] * wR - data->real[j] * wI;
}
}
for(i=0; i<N; i++) {
out->real[i] = sumXr[i];
out->imaginary[i] = sumXi[i];
}
}
is code takes an input structure containing arrays for the real and imaginary components
of a signal segment along with the number of samples contained in the signal segment. e
DFT is then computed and the input signal is overwritten by the DFT. Notice that this code
is computationally inefficient, as it calculates each twiddle factor ( wR and wI ) using a math
library at every iteration. It is also important to note that the frequency-domain resolution of the
DFT may be increased by increasing the size of the transform and zero-padding the input signal.
Zero-padding allows representing the signal spectrum with a greater number of frequency bins.
In the above code, the size of the transform matches the size of the array provided by the input
structure. For example, if the input array is allowed to store four times the length of the original
signal with the remaining three-quarters being zero-padded, the resulting transform will contain
four times the frequency resolution of the original transform.
8.1.2 FAST FOURIER TRANSFORM
e computational complexity (number of additions and multiplications) of DFT is reduced
to .N=2/ log
2
N complex multiplications and N log
2
N complex additions by using FFT algo-
rithms. In these algorithms, N is normally considered to be a power of two. To improve the
computational efficiency, the FFT computation utilizes the symmetry properties in the DFT
transformation. A typical FFT C code appears below (note that there are many FFT versions,
here the FFT implementation in [1] is stated):
void FFT(Complex* data) {
int i, j, k, L, m, n, o, p, q, r;
float tempReal, tempImaginary, cos, sin, xt, yt, arg;
k = data->N;
j = 0;
m = k/2;
120 8. FREQUENCY DOMAIN TRANSFORMS
float cosine[k];
float sine[k];
for (i=0; i<k/2; i++) {
arg = -2*M_PI*i/k;
cosine[i] = cos(arg);
sine[i] = sin(arg);
}
//bit reversal
for(i=1;i<(k-1);i++) {
L=m;
while(j>=L) {
j = j-L;
L = L/2;
}
j = j+L;
if(i<j) {
tempReal = data->real[i];
tempImaginary = data->imaginary[i];
data->real[i] = data->real[j];
data->imaginary[i] = data->imaginary[j];
data->real[j] = tempReal;
data->imaginary[j] = tempImaginary;
}
}
L = 0;
m = 1;
n = k/2;
//computation
for(i=k; i>1; i=(i>>1)) {
L = m;
m = 2*m;
o = 0;
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.