The discrete Fourier transform (DFT) and the fast Fourier transform (FFT) are possibly the two most important transforms you will ever see. All modern telecommunications relies on the FFT, as does data compression, satellite imaging, medical imaging, and a host of other application areas. Basically, any application that uses digital data will almost certainly use a DFT or FFT (or the closely related discrete cosine transform)

somewhere.

The DFT and FFT are based on sums of terms of the form e −2πin N , where n is an integer. These are called Nth roots of 1.

a. If z = e −2πin N , then calculate z N for N = 1 and N = 2.
Does it make any difference what n is? What do you think z N will be when N = 20? How about N = 200? Why?

b. If N = 2 what are the Nth roots of 1? Plot them in the complex plane. (Hint: think of the cases n = 0 and n = 1.
Does any other value of n give a different root?)

c. Repeat the above question for N = 3, N = 4 and N = 5.
You should be seeing a pattern.

d. As n varies, how many different Nth roots of 1 do you get?
(Remember that n has to be an integer.)

e. How would you sketch the Nth roots of 1 in the complex plane if N = 20? N = 50?