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:

    “In today’s world parents find themselves at the mercy of a society which imposes pressures and priorities that allow neither time nor place for meaningful activities and relations between children and adults, which downgrade the role of parents and the functions of parenthood, and which prevent the parent from doing things he wants to do as a guide, friend, and companion to his children.”
    —Urie Bronfenbrenner (b. 1917)

    “The English masses are lovable: they are kind, decent, tolerant, practical and not stupid. The tragedy is that there are too many of them, and that they are aimless, having outgrown the servile functions for which they were encouraged to multiply. One day these huge crowds will have to seize power because there will be nothing else for them to do, and yet they neither demand power nor are ready to make use of it; they will learn only to be bored in a new way.”
    —Cyril Connolly (1903–1974)

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