Deriving an FFT Algorithm via Group Representation Theory
A self-contained lecture on the Discrete Fourier Transform and its relation to the time and frequency representations of a signal. By describing time-shift and frequency-shift operators with a structure known as the Heisenberg group, explicit steps can be given for producing an FFT algorithm. Pseudocode and programmable examples will be …