Free Books

The DFT and its Inverse Restated

Let $ x(n), n=0,1,2,\ldots,N-1$, denote an $ N$-sample complex sequence, i.e., $ x\in{\bf C}^N$. Then the spectrum of $ x$ is defined by the Discrete Fourier Transform (DFT):

$\displaystyle \zbox {X(k) \isdef \sum_{n=0}^{N-1}x(n) e^{-j 2\pi nk/N},\quad k=0,1,2,\ldots,N-1}

The inverse DFT (IDFT) is defined by

$\displaystyle \zbox {x(n) = \frac{1}{N}\sum_{k=0}^{N-1}X(k) e^{j 2\pi nk/N},\quad n=0,1,2,\ldots,N-1.}

In this chapter, we will omit mention of an explicit sampling interval $ T=1/f_s$, as this is most typical in the digital signal processing literature. It is often said that the sampling frequency is $ f_s=1$. In this case, a radian frequency $ \omega_k \isdef 2\pi k/N$ is in units of ``radians per sample.'' Elsewhere in this book, $ \omega_k$ usually means ``radians per second.'' (Of course, there's no difference when the sampling rate is really $ 1$.) Another term we use in connection with the $ f_s=1$ convention is normalized frequency: All normalized radian frequencies lie in the range $ [-\pi,\pi)$, and all normalized frequencies in Hz lie in the range $ [-0.5,0.5)$.7.1 Note that physical units of seconds and Hertz can be reintroduced by the substitution

$\displaystyle e^{j 2\pi nk/N} = e^{j 2\pi k (f_s/N) nT} \isdef e^{j \omega_k t_n}.

Notation and Terminology

If $ X$ is the DFT of $ x$, we say that $ x$ and $ X$ form a transform pair and write

$\displaystyle \zbox {x\;\longleftrightarrow\;X}$   $\displaystyle \mbox{(\lq\lq $x$\ corresponds to $X$'')}$$\displaystyle . \protect$

Another notation we'll use is

\hbox{\sc DFT}(x)&\isdef & X,\quad\mbox{and} \\
\hbox{\sc DFT}_k(x)&\isdef & X(k).

If we need to indicate the length of the DFT explicitly, we will write $ \hbox{\sc DFT}_N(x) = X$ and $ \hbox{\sc DFT}_{N,k}(x) = X(k)$. As we've already seen, time-domain signals are consistently denoted using lowercase symbols such as ``$ x(n)$,'' while frequency-domain signals (spectra), are denoted in uppercase (`` $ X(\omega_k)$'').

Modulo Indexing, Periodic Extension

The DFT sinusoids $ s_k(n) \isdef e^{j\omega_k n}$ are all periodic having periods which divide $ N$. That is, $ s_k(n+mN)=s_k(n)$ for any integer $ m$. Since a length $ N$ signal $ x$ 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 $ x(n)$ beyond the range $ [0,N-1]$ is periodic extension, i.e., $ x(n+mN)\isdef
x(n)$ for every integer $ m$.

Moreover, the DFT also repeats naturally every $ N$ 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 $ n$ and $ k$.) 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 $ N$ samples:

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

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

for every integer $ m$.

As a result of this convention, all indexing of signals and spectra7.2 can be interpreted modulo $ N$, and we may write $ x(n\left(\mbox{mod}\;N\right))$ to emphasize this. Formally, `` $ n\left(\mbox{mod}\;N\right)$'' is defined as $ n-mN$ with $ m$ chosen to give $ n-mN$ in the range $ [0,N-1]$.

As an example, when indexing a spectrum $ X$, we have that $ X(N)=X(0)$ 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 $ NT$ seconds ($ N$ 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 $ x(n)$ consists of $ N$ 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 [72].

Next Section:
Signal Operators
Previous Section:
DFT Problems