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)

    “One can describe a landscape in many different words and sentences, but one would not normally cut up a picture of a landscape and rearrange it in different patterns in order to describe it in different ways. Because a photograph is not composed of discrete units strung out in a linear row of meaningful pieces, we do not understand it by looking at one element after another in a set sequence. The photograph is understood in one act of seeing; it is perceived in a gestalt.”
    —Joshua Meyrowitz, U.S. educator, media critic. “The Blurring of Public and Private Behaviors,” No Sense of Place: The Impact of Electronic Media on Social Behavior, Oxford University Press (1985)

    “Walked forth to ease my pain
    Along the shore of silver streaming Thames,
    Whose rutty bank, the which his river hems,
    Was painted all with variable flowers,”
    —Edmund Spenser (1552?–1599)