We know the following pairs:
\begin{align*}
x(n) &\ftp X(\omega) \\
y(n) &\ftp Y(\omega)
\end{align*}

What is the transform of $x(n)y(n)$? It may seem that multiplication in the time domain corresponds to convolution in the frequency domain, but there are issues with the $2\pi$ periodicity of the frequency response. So we do not use ordinary convolution.

\begin{align*}
\mbox{let } q(n) = x(n)y(n) \\
Q(\omega) &= \sum \limits_{n\in\Z}x(n)y(n)e^{-i\omega n} \\
Q(\omega) &= \sum \limits_{n\in\Z}\lr{\frac{1}{2\pi}\int_{\langle 2\pi\rangle}X(\lambda)e^{i\lambda n}d\lambda}y(n)e^{-i\omega n} \\
Q(\omega) &= \frac{1}{2\pi}\int_{\langle 2\pi\rangle} X(\lambda) \lr{\sum \limits_{n\in\Z}y(n)e^{i\lambda n}e^{-i\omega n}}d\lambda \\
Q(\omega) &= \frac{1}{2\pi}\int_{\langle 2\pi\rangle} X(\lambda) \lr{\sum \limits_{n\in\Z}y(n) e^{-i(\omega-\lambda) n}} d\lambda \\
Q(\omega) &= \frac{1}{2\pi}\int_{\langle 2\pi\rangle} X(\lambda) Y(\omega - \lambda) d\lambda \\
\end{align*}

Thus, the fourier transform pair is:

\begin{nicebox}
$$
x(n)y(n) \ftp \frac{1}{2\pi}\int_{\langle 2\pi\rangle} X(\lambda) Y(\omega - \lambda) d\lambda 
$$
\end{nicebox}

So we can define this result as \emph{circular convolution}:

\begin{nicebox}
$$
(X \circconv Y)(\omega) = \int_{\langle 2\pi\rangle} X(\lambda) Y(\omega - \lambda) d\lambda 
$$
\end{nicebox}

Do not confuse this with regular convolution: 
\begin{nicebox}
$$
(X * Y)(\omega) = \int_{\R} X(\lambda) Y(\omega - \lambda) d\lambda 
$$
\end{nicebox}

We use ordinary convolution with non-periodic functions and circular convolution with periodic functions. How can we solve a circular convolution?

\begin{enumerate}
\item Keep on function as it is.
\item Restrict the other function to one period
\item Perform a normal convolution
\item Divide by $2\pi$ (if necessary as in above example)
\end{enumerate}

\begin{example}

1) Consider the two following $2\pi$-periodic frequency responses:

% \img{images/boxes/circularconv/a/boxes.ps}
% \img{images/boxes/circularconv/b/boxes.ps}


How would we perform a circular convolution? Limit $Y(\lambda)$ to one period and then perform a single convolution.

% \img{images/boxes/circularconv/b/oneperiod/boxes.ps}

\end{example}

\begin{example}

2) Lets look at an example of DT amplitude modulation. This system takes in $x(n)$ and multiplies it by $y(t)$:

% \img{images/modulators/dtampmod/am.ps}

\begin{center}
\begin{pspicture}(-3,-3)(3,3)

% in from x
\rput(-3.2,0){$x(n)$}
\psline[linewidth=1.25 pt, arrowscale=1.1]{->}(-2.7,0)(-0.25,0)
% out to y
\rput(4.25,0){$q(n)=x(n)y(n)$}
\psline[linewidth=1.25 pt, arrowscale=1.1]{->}(0.25,0)(2.7,0)
% up arrow
\rput(0,-2){$y(n)=e^{i\omega_0 n}$}
\psline[linewidth=1.25 pt, arrowscale=1.1]{->}(0,-1.65)(0,-0.25)

% multiplier
\pscircle(0,0){0.25}
\psline(-0.175,0.175)(0.175,-0.175)
\psline(0.175,0.175)(-0.175,-0.175)

% box
\pspolygon(-1.5,-2.65)(-1.5,1)(1.5,1)(1.5,-2.65)

\end{pspicture}
\end{center}

$y(n) = e^{i\omega_0 n}$, and $x(n)$ is defined by its frequency response, $X(\lambda)$, which is shown below:

% \img{images/boxes/circularconv/a/simple/boxes.ps}

$Y(\lambda)$ can be shown to be an infinite impulse train, such that when limited for our circular convolution method, we have a single dirac delta:

% \img{images/pulsetrains/diracs/freq/yomega.ps}
% \img{images/pulsetrains/diracs/freq/limited.ps}

Now we perform regular convolution. Any time we convolve a signal with a single dirac at a particular frequency, we simple shift the signal such that it is centered at that frequency:

% \img{images/boxes/circularconv/a/convolved/boxes.ps}

This is equal to $\frac{1}{2\pi}\int_{\langle 2\pi\rangle}x(\lambda)Y(\omega - \lambda)d\lambda = \lr{X \circconv Y }\lr{\omega}$.

\end{example}

Circular Convolution