The DFT and its Inverse Restated
Let , denote an -sample complex sequence, i.e., . Then the spectrum of is defined by the Discrete Fourier Transform (DFT):
Notation and Terminology
If is the DFT of , we say that and form a transform pair and write
If we need to indicate the length of the DFT explicitly, we will write and . As we've already seen, time-domain signals are consistently denoted using lowercase symbols such as ``,'' while frequency-domain signals (spectra), are denoted in uppercase (`` '').
Modulo Indexing, Periodic Extension
The DFT sinusoids are all periodic having periods which divide . That is, for any integer . Since a length signal can be expressed as a linear combination of the DFT sinusoids in the time domain,
Moreover, the DFT also repeats naturally every samples, since
Definition (Periodic Extension): For any signal , we define
As a result of this convention, all indexing of signals and spectra7.2 can be interpreted modulo , and we may write to emphasize this. Formally, `` '' is defined as with chosen to give in the range .
As an example, when indexing a spectrum , we have that which can be interpreted physically as saying that the sampling rate is the same frequency as dc for discrete time signals. Periodic extension in the time domain implies that the signal input to the DFT is mathematically treated as being samples of one period of a periodic signal, with the period being exactly seconds ( samples). The corresponding assumption in the frequency domain is that the spectrum is exactly zero between frequency samples . It is also possible to adopt the point of view that the time-domain signal consists of samples preceded and followed by zeros. In that case, the spectrum would be nonzero between spectral samples , and the spectrum between samples would be reconstructed by means of bandlimited interpolation .