This page is optimized for mobile devices, if you would prefer the desktop version just click here

5.3 Discrete fourier transform properties

Recall, for discrete-time finite length signals, the definition of the DFT and the inverse DFT, both in its normalized form: $(DFT)~~X[k]= \sum_{n=0}^{N-1} x[n]\, \frac{e^{-j \frac{2\pi}{N}kn}}{\sqrt N} \\[2mm](Inverse DFT)~~x[n] = \sum_{k=0}^{N-1} X[k]\, \frac{e^{j \frac{2\pi}{N}kn}}{\sqrt N}$ and in its much more commonly used un-normalized form:$(DFT)~~X[k] = \sum_{n=0}^{N-1} x[n]\, e^{-j \frac{2\pi}{N}kn} \\[2mm] (Inverse DFT)~~x[n]= \frac{1}{N}\sum_{k=0}^{N-1} X[k] \, e^{j \frac{2\pi}{N}kn}$A signal $x[n]$ and its DFT $X[k]$ (recall there is a one-to-one correspondence) are referred to as a DFT PAIR. The DFT has a variety of properties, which we will now consider.

The dft and its inverse are periodic

The DFT is defined for finite-length (length $N$) signals; so, for $x[n]$, $n$ runs from $0$ to $N-1$, as does $k$. But let is us see what happens when we consider a value of $k$ outside this range in the DFT formula, say $X[k+lN]$, where $l$ is some nonzero integer: $\begin{align*}X[k+l N]&=~ \sum_{n=0}^{N-1} x[n]\,e^{-j \frac{2\pi}{N}(k+l N)n}\\&=\sum_{n=0}^{N-1} x[n]\, e^{-j \frac{2\pi}{N}kn} e^{-j \frac{2\pi}{N}l N n}\\&=\sum_{n=0}^{N-1} x[n]\, e^{-j \frac{2\pi}{N}kn}\cdot 1\\&=\sum_{n=0}^{N-1} x[n]\, e^{-j \frac{2\pi}{N}kn}\\&= X[k] \end{align*}$As $X[k+lN]=X[k]$, the DFT is periodic:

CAPTION.

By the same token, the inverse DFT is also periodic: $\begin{align*}x[n+l N]&=~ \frac{1}{N}\sum_{k=0}^{N-1} X[k]\,e^{j \frac{2\pi}{N}k(n+lN)}\\&=\sum_{k=0}^{N-1} X[k]\, e^{j \frac{2\pi}{N}kn} e^{j \frac{2\pi}{N}klN}\\&=\sum_{k=0}^{N-1} X[k]\, e^{j \frac{2\pi}{N}kn}\cdot 1\\&=\sum_{k=0}^{N-1} X[k]\, e^{j \frac{2\pi}{N}kn}\\&= x[n] \end{align*}$Again this is to be expected because the complex harmonic sinusoids of the inverse DFT sum are periodic. This also further illustrates the fact that any finite-length signals can be understood as a single period of a periodic signal.

Dft frequency ranges

A complex harmonic sinuoids $e^{j(\frac{2\pi}{N}k)n}$ has, by definition, a frequency of $\frac{2\pi}{N}k$, which may label as $\omega_k$. In the DFT of a signal of length $N$, the variable $k$ rangers from $0$ to $N-1$, which corresponds to frequencies from $0$ to (just about) $2\pi$:

For an $N=16$ length signal, one way to express the range of frequencies is for $k$ to run from $0$ to $N-1$, which corresponds to frequencies between $0$ and $2\pi$.

However, as we saw above, since the DFT is periodic, $0$ to $N-1$ is not the only range of $k$ we may use to express the DFT. Since $X[k]=X[k-N]$, we may let $k$ run from $-\frac{N}{2}$ to $\frac{N}{2}-1$ (for even $N$, that is; for odd $N$ it would be $-\frac{N-1}{2}$ to $\frac{N-1}{2}$):

For an $N=16$ length signal, another way to express the range of frequencies is for $k$ to run from $-\frac{N}{2}$ to $\frac{N}{2}-1$, which corresponds to frequencies between $-\pi$ and $\pi$.

Shifts in time and frequency

Let $x[n]$ and $X[k]$ be a DFT pair (i.e., $X[k]$ is the DFT of $x[n]$). A circular shift in time on $x[n]$ will produce a phase shift on $X[k]$: $x[(n-m)_N]~\stackrel{\textrm{DFT}}{\longleftrightarrow}~ e^{-j\frac{2\pi}{N}km} X[k]$To prove this relationship, we first note that for the circular shift $(n-m)_N$, there is some integer $l$ such that $(n-m)_N=n-m+lN$. We will use that fact for a change of variables in our proof: $\begin{align*}\textrm{DFT}\{x[(n-m)_N]\}&=\sum_{n=0}^{N-1} x[(n-m)_N]\, e^{-j \frac{2\pi}{N}kn}\\&\textrm{Let }r=(n-m)_N=n-m+lN\\&=\sum_{r=0}^{N-1} x[r]\,e^{-j \frac{2\pi}{N}k (r+m-lN)}\\&=\sum_{r=0}^{N-1} x[r]\,e^{-j \frac{2\pi}{N}kr}e^{-j \frac{2\pi}{N}m}e^{-j \frac{2\pi}{N}lN}\\&=e^{-j \frac{2\pi}{N}m}\sum_{r=0}^{N-1} x[r]\,e^{-j \frac{2\pi}{N}kr}\cdot 1\\&=e^{-j\frac{2\pi}{N}km} X[k]\end{align*}$ As you might expect from the symmetrical similarities between the DFT and inverse DFT, a comparable relationship exists in the other direction as well. A circular shift in the frequency domain of a signal results in the modulation of the signal in the time domain:$e^{j\frac{2\pi}{N}l n} \, x[n] ~\stackrel{\textrm{DFT}}{\longleftrightarrow}~ X[(k-l)_N]$ The proof of this property follows the same approach as that of the first.

<< Chapter < Page Page > Chapter >>

Read also:

OpenStax, Discrete-time signals and systems. OpenStax CNX. Oct 07, 2015 Download for free at https://legacy.cnx.org/content/col11868/1.2

Google Play and the Google Play logo are trademarks of Google Inc.