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:

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

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