Convolution Theorem - Functions of A Discrete Variable... Sequences

Functions of A Discrete Variable... Sequences

By similar arguments, it can be shown that the discrete convolution of sequences and is given by:



where DTFT represents the discrete-time Fourier transform.

An important special case is the circular convolution of and defined by where is a periodic summation:

It can then be shown that:

\begin{align} x_N * y\ &=\ \scriptstyle{DTFT}^{-1} \displaystyle \big\\ &=\ \scriptstyle{DFT}^{-1} \displaystyle \big, \end{align}

where DFT represents the discrete Fourier transform.

The proof follows from DTFT#Periodic_data, which indicates that can be written as:

The product with is thereby reduced to a discrete-frequency function:

(also using Sampling the DTFT).

The inverse DTFT is:

\begin{align} (x_N * y)\ &=\ \int_{0}^{1} \frac{1}{N} \sum_{k=-\infty}^{\infty} \scriptstyle{DFT}\displaystyle\{x_N\}\cdot \scriptstyle{DFT}\displaystyle\{y_N\}\cdot \delta\left(f-k/N\right)\cdot e^{i 2 \pi f n} df\\ &=\ \frac{1}{N} \sum_{k=-\infty}^{\infty} \scriptstyle{DFT}\displaystyle\{x_N\}\cdot \scriptstyle{DFT}\displaystyle\{y_N\}\cdot \int_{0}^{1} \delta\left(f-k/N\right)\cdot e^{i 2 \pi f n} df\\ &=\ \frac{1}{N} \sum_{k=0}^{N-1} \scriptstyle{DFT}\displaystyle\{x_N\}\cdot \scriptstyle{DFT}\displaystyle\{y_N\}\cdot e^{i 2 \pi \frac{n}{N} k}\\ &=\ \scriptstyle{DFT}^{-1} \displaystyle \big, \end{align}

QED.

Read more about this topic:  Convolution Theorem

Famous quotes containing the words functions of, functions, discrete and/or variable:

    “The mind is a finer body, and resumes its functions of feeding, digesting, absorbing, excluding, and generating, in a new and ethereal element. Here, in the brain, is all the process of alimentation repeated, in the acquiring, comparing, digesting, and assimilating of experience. Here again is the mystery of generation repeated.”
    —Ralph Waldo Emerson (1803–1882)

    “If photography is allowed to stand in for art in some of its functions it will soon supplant or corrupt it completely thanks to the natural support it will find in the stupidity of the multitude. It must return to its real task, which is to be the servant of the sciences and the arts, but the very humble servant, like printing and shorthand which have neither created nor supplanted literature.”
    —Charles Baudelaire (1821–1867)

    “We have good reason to believe that memories of early childhood do not persist in consciousness because of the absence or fragmentary character of language covering this period. Words serve as fixatives for mental images. . . . Even at the end of the second year of life when word tags exist for a number of objects in the child’s life, these words are discrete and do not yet bind together the parts of an experience or organize them in a way that can produce a coherent memory.”
    —Selma H. Fraiberg (20th century)

    “There is not so variable a thing in nature as a lady’s head-dress.”
    —Joseph Addison (1672–1719)