## Fourier Transform: Discrete, Periodic Time Sequence

If a discrete time sequence is periodic, its Fourier transform will be discrete and periodic in frequency. This transform is known as the Discrete Fourier Series, or DFS.

A discrete, periodic signal where the period is N samples has the following Fourier transform:  Here xN [n] and XN [k] indicate the DFS of an N point periodic discrete series has a period of N samples.

## The Discrete Fourier Transform: DFT

Although the DFS is only valid for a periodic discrete time series, we can consider the N point time series to represent one period of a periodic series. The resulting DFS is also periodic, but it is important to notice the DFS can be viewed as representing one period of a sampled version of the Fourier transform of a non-periodic discrete time sequence.  This is the Discrete Fourier Transform or DFT.

Again, a discrete, non-periodic series actually has a continuous Fourier Transform (the Discrete Time Fourier Transform or DTFT), but we can use one period of the DFS to produce the DFT, a sampled version of the continuous transform. Because the DFT operates on discrete sequences and produces a discrete sequence as a result, the DFT can be used to process signals on a digital computer.  If a continuous signal is sampled at twice its highest frequency or higher, then the DFT of the sampled signal is a sampled version of the Fourier transform of the original continuous signal. Further, all of the information in the continuous signal is present in the sampled signal. This is the power of the DFT. In principle, we can take a continuous signal, sample it, process the samples on a computer and then convert the processed samples back into a continuous signal. The result will be identical to processing the continuous signal with an equivalent analog system. In many cases, the computer processed results cannot be achieved in the analog domain at all.

If the length of the time sequence is a power of two (e.g. 128, 512, 1024, etc.), the DFT can be calculated much faster by means of a Fast Fourier Transform or FFT. The FFT is just a faster implementation of the DFT. DADiSP can calculate both the DFT and FFT. Because DADiSP uses the mixed radix implementation of the FFT, DADiSP can also perform FFT's of signal lengths that are not a power of two.