The DFT - Synthesis Lectures on Signal Processing - page 120

where N is the total sampled sequence length, Fs is the sample rate or frequency, UniqueBins is the total
number of unique DFT bins (applies to a real signal only), T is the total sampling duration in seconds,
and A is1if N is even and 1/2 if N is odd.

Example 3.18. A real signal is sampled for three seconds at a sampling rate of 8000 Hz. Compute the
bin width, total number of samples, and the total number of unique bins the DFT will yield.

The Nyquist limit is 8000/2 = 4000 Hz, and from Eq. (3.13), Binwidth = 0.333 Hz, total samples
N (from Eq. (3.14)) = (3)(8,000) = 24,000, and UniqueBins , from Eq. (3.15), = 24,000/2+1=12,001.

Example 3.19. A total of 100 samples are obtained of a real signal, sampled at a constant rate for three
seconds. What is the bin width, Nyquist limit, and number of unique bins?

The bin width is 0.333 Hz and the number of unique bins is 51. Since the sampling frequency is
100/3 = 33.33 Hz, the Nyquist rate is 33.33/2 = 16.66 Hz; the anti-aliasing filter should cutoff at this
frequency.

Example 3.20. A real signal is sampled for three seconds at a rate of 100 Hz. Give the bin width, the
highest nonaliased frequency, the number of unique bins, and whether the following frequencies in the
signal would be on-bin or off-bin in the DFT: 2.0 Hz, 4.5 Hz, 6.666 Hz.

A total of 300 samples result. The bin width is 0.333 Hz, and the bin frequencies are therefore 0,
0.333 Hz, 0.666 Hz, 1 Hz, 1.333 Hz, etc. The (nonaliased) highest frequency based on the sampling rate
and proper anti-aliasing, is 50 Hz; the number of unique bins is 300/2+1=151. The frequencies 2.0 Hz
and 6.666 Hz would lie squarely on-bin (in fact, on bins 6 and 20, respectively), while 4.5 Hz is off-bin.

3.14 THE FF T

There are many specialized algorithms for efficiently computing the DFT. The direct implementation
of a DFT of length N requires roughly N 2 computations. The Cooley-Tukey radix-2 FFT is perhaps
the most well-known of such algorithms, and requires only Nlog 2 (N) operations, which makes possible
real-time computation of larger DFTs.

Example 3.21. Assume that a certain computer takes one second to compute the DFT of a length-2ˆ18
sequence using an FFT algorithm. Compute how long (approximately) it would take to compute the
same DFT using the direct DFT implementation.

We evaluate the ratio

N 2 /(N log 2 (N))

=

N/ log 2 (N)

as 2 18 / 18 = 14,564 seconds or about 4.05 hours.