Introduction:
A physical process can be described in 2 ways:
1. using time domain. In this case we will have a quantity as a function of time. h(t)
2. using frequency domain. In this case the amplitude H is given as a function of frequency. H(f). f can take any value and H(f) is usually a complex number.
h(t) and H(f) are both representations of the same function. To go back and forth between these 2 representations, one uses the Fourier transform equations.
if t is measured in seconds, then the frequency is in cycles per second (hertz). we can also have the Fourier transformations on angular frequency.
The total power in a signal is the same whether we compute it in the time domain or in the frequency domain.
Sometimes we want to know how much power is contained in the frequency interval between f and f+df in which case we usually consider f to be from 0 to infinity. Based on that we define PSD (one sided power spectral density) and the total power is the integral of PSD from 0 to infinity.
something of interest is the PSD per unit time. This is computed by taking a long but finite stretch of h(t) and finding a function that is equal to h(t) in this stretch and 0 anywhere else, then computing the PSD of this function and dividing it by the length of the stretch.
Fourier Transform of Discretely Sampled Data:
for any sampling interval t, there is a frequency f called the Nyquist critical frequency given by f = 1/2t.
This comes from the fact that a critical sampling of a sine wave is two sample points per cycle; one to sample the positive peak and one to sample the negative peak.
The Nyquist critical frequency is important for 2 reasons:
1. Sampling Theorem:
- (Definition) Band-Limiting is the limiting of a signal's Fourier transform or PSD to zero above a certain finite frequency.
This says that if a signal is known to be bandwidth limited to the Nyquist critical frequency we can get the entire information content of the signal by sampling it at a rate equal to twice the maximum frequency(which I guess is the critical frequency).
2. Aliasing:
This happens when the signal is not bandwidth limited to less than the Nyquist critical frequency.
we also define the discrete Fourier transform to find the Fourier transform of a discrete sample of h(t).
The complexity seems to be O(N^2) in the first look because of a vector matrix multiplication that requires multiplying N^2 complex numbers. But it can also be done in O(N log N) operations using fast Fourier transform.
Fast Fourier Transform (FFT):
The idea is we can compute the discrete Fourier transform of length N, by summing two discrete Fourier transforms of length N/2, one formed from the even-numbered points of the original N and one from the odd-numbered points.
Next, each of those two discrete Fourier transforms can be written as the sum of two other half length discrete Fourier transform and that is how the better complexity is obtained.
The easiest case is for N to be a power of two. If the length of our data is not a power of two, we should pad it with 0s.
FFT uses bit reversal which is reversing the order of the bits so 001 will turn to 100. so given the original vector of data fj, we will rearrange it in bit-reversed order and the adjacent numbers in the resulting vector are the exact order in which we need to access them inorder to compute the Fourier transforms. To note is that the first half of the vector would be the even-numbered points of the original N and the second half would be the odd numbered points.
Thus the FFT algorithms has two sections. The first section sorts the data in bit-reversed order. The second section has an outer loop that is executed logN times calculating the transforms of different lengths.
since we had N points sampled originally, the whole algorithm now takes O(N log N) time.
The above algorithm is known as Cooley-Tukey algorithm.
FFT in Two or More Dimensions:
suppose we have a two dimensional function h(k1, k2). The 2-dimensional discrete Fourier transform H(n1, n2) is defined (very similar to one dimensional) as
The above function can be generalized to L dimensions in a similar way.
