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:

    “Those things which now most engage the attention of men, as politics and the daily routine, are, it is true, vital functions of human society, but should be unconsciously performed, like the corresponding functions of the physical body.”
    —Henry David Thoreau (1817–1862)

    “When Western people train the mind, the focus is generally on the left hemisphere of the cortex, which is the portion of the brain that is concerned with words and numbers. We enhance the logical, bounded, linear functions of the mind. In the East, exercises of this sort are for the purpose of getting in tune with the unconscious—to get rid of boundaries, not to create them.”
    —Edward T. Hall (b. 1914)

    “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)