Next: Four Forms of Fourier Up: Fourier_Analysis Previous: Continuous Fourier Transform

# Discrete Fourier Transform

In practice, the expression of the signal is not available, so the signal has to be digitized (truncated and sampled) and then analyzed numerically by a digital computer.

• Truncation

As computer can only process finite amount of data, a signal of infinite duration must be truncated, i.e., it is assumed to be periodic with a finite period . (We cannot assume the signal is 0 outside the time range T, as that would still be an infinite signal. Repeated signals carry no information while zero signals still do.) The Fourier transform of this periodic signal now becomes Fourier series expansion (Eq. 3.38):

with coefficient ( in Eq. 3.39, which is changed to in Problem 5.54):

The spectrum of this periodic signal becomes discrete

where is the interval between two consecutive frequency components. In particular, when , , the discrete spectrum becomes continuous.

• Heisenberg's Uncertainty Principle

Sometimes it is desirable to study the frequency characteristics of a signal over a short duration . However, the time window and the frequency resolution (the gap between two consecutive frequency components available) are inversely related, i.e., it is impossible to increase both the temporal resolution (small ) and frequency resolution (small ). When one of the resolutions is improved, the other must suffer. This relationship is similar to Heisenberg's Uncertainty Principle in quantum physics which states that it is impossible to exactly measure both the position and the momentum of a particle at the same time. The more precisely one of the quantities is determined, the less precisely the other is known. To better address this issue of time and frequency resolution, Wavelet transform can be used.

• Sampling

As computer can only process discrete values, the continuous signal must be sampled:

where is the mth sample, is the interval between two consecutive samples and , and is the sampling rate. The number of samples in each period is assumed to be . As the signal is now discrete (as well as periodic), its spectrum becomes periodic (as well as discrete) with period . Note that the number of coefficients in frequency domain is also :

This relation indicates that the representation of a signal in either time or frequency domain has the same number of independent variables, or same degrees of freedom. Moreover, the Parseval's theorem further indicates that the representations in both domains contain the same amount of energy.

The nth Fourier coefficient is:

and the mth signal sample can be expressed as (Eq. 5.19):

As , the above can be rewritten as (Eqs. P5.53-2, P5.54-2):

This is the discrete Fourier transform (DFT), with both the time signal and its spectrum discrete and finite, and the only form of Fourier transform that can be implemented by a digital computer.

Alternatively, the truncation and sampling of the discretization process can be carried out in a different order, sampling first followed by truncation.

• Sampling

The signal becomes discrete after sampling with rate :

and its spectrum become periodic (of period ):

and the mth signal sample can be written as:

In particular, if we assume , and replace by , the above become the same as Eqs. 5.8 and 5.9:

Note on alternative notations:
• The periodic spectrum of a discrete signal in Eqs. 5.8 and 5.9 is changed to to better illustrate the duality of Fourier transform in both time and frequency domains.
• The above notations of Fourier transform of discrete signals take the sampling rate and period into consideration, while Eqs. 5.8 and 5.9 as a special case () do not. That is why they are modified to include sampling rate/period in section 7.4.

• Truncation:

The sampled signal is then truncated by a time window and becomes periodic with time samples in a period . The spectrum become discrete (with gap ) as well as periodic (with period ). There are also coefficients in a period :

where is the nth coefficient:

and the mth signal sample can be written as:

This is the same discrete Fourier transform as obtained above.

Next: Four Forms of Fourier Up: Fourier_Analysis Previous: Continuous Fourier Transform
Ruye Wang 2003-11-17