Modulo Indexing, Periodic Extension

The DFT sinusoids $s_k(n) \isdef e^{j\omega_k n}$ 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,

$\displaystyle x(n) = \frac{1}{N}\sum_k X(k) s_k(n),$

it follows that the ``automatic'' definition of

beyond the range

is periodic extension, i.e., $x(n+mN)\isdef x(n)$ for every integer

Moreover, the DFT also repeats naturally every samples, since

$\displaystyle X(k+mN) \isdef \left<x,s_{k+mN}\right> = \left<x,s_k\right> = X(k)$

because $s_{k+mN}(n) = e^{j2\pi n(k+mN)/N} = e^{j2\pi nk/N}e^{j2\pi n m} = s_k(n)$ . (The DFT sinusoids behave identically as functions of

and

.) Accordingly, for purposes of DFT studies, we may define all signals in ${\bf C}^N$ as being single periods from an infinitely long periodic signal with period

samples:

Definition (Periodic Extension): For any signal $x\in{\bf C}^N$ , we define

$\displaystyle x(n+mN)\isdef x(n)$

for every integer

As a result of this convention, all indexing of signals and spectra ^7.2 can be interpreted modulo , and we may write $x(n\left(\mbox{mod}\;N\right))$ to emphasize this. Formally, `` $n\left(\mbox{mod}\;N\right)$ '' 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 $\omega_k$ . 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 $\omega_k$ , and the spectrum between samples would be reconstructed by means of bandlimited interpolation [69].

Order a Hardcopy of Mathematics of the DFT

Previous: Notation and Terminology
Next: Signal Operators

written by Julius Orion Smith III
Julius Smith's background is in electrical engineering (BS Rice 1975, PhD Stanford 1983). He is presently Professor of Music and Associate Professor (by courtesy) of Electrical Engineering at Stanford's Center for Computer Research in Music and Acoustics (CCRMA), teaching courses and pursuing research related to signal processing applied to music and audio systems. See http://ccrma.stanford.edu/~jos/ for details.

Sign in

Search Online Books

Free Online Books

Chapters

Mathematics of the DFT
    Fourier Theorems for the DFT
       The DFT and its Inverse Restated
          Modulo Indexing, Periodic Extension