Circular convolution

Digital Signal Processing

1. Convolution
Thefamiliarone:
y[
n
℄=
1
X
k=1
x
1
[k℄x
2
[
n
k℄
Leavetherstsignalx
1
[k℄unchanged
Forx
2
[k]:
{Flipthesignal:kb ecomesk,givingx
2
[k℄
{Shifttheipp edsignaltotherightby
n
samples:
kb ecomesk
n
x
2
[k℄!x
2
[(k
n
)]=x
2
[
n
k℄
Carryoutsample-by-samplemultiplicationandsumtheresulting
sequencetogettheoutputattimeindex
n
,i.e.y[
n
℄

2. Whathapp enstop erio disignals?
Supp oseb othsignalsarep erio di
x
1
[n+N℄=x
1
[n℄
x
2
[n+N℄=x
2
[n℄
Thenx
1
[k℄x
2
[n
0
k℄willalsob ep erio di(withp erio dN)
Foreachvalueofn
0
wegetadierentp erio disignal(p erio dicity
isNinallcases)

jy[n℄jwillb eeither0or1

3. CircularConvolution
y[n℄
?
=
N1
X
k=0
~ x
1
[k℄~ x
2
[nk℄
y[n℄isp erio diwithp erio dN
nkcanb ereplacedbyhnki
N
(\nkmo dN")
\Circular"Convolution:~ y[n℄=~ x
1
[n℄~ x
2
[n℄
~ y[n℄
def
=
N1
X
k=0
~ x
1
[k℄~ x
2
[hnki
N
℄n=0;1;:::;N1

4. Examples
0
1
0
1
=
4
06 6
*
0 30 5
4
1
0 8
=
11
3
6
Linear
Circular
*

5. RelationshipBetweenLinearandCircular
Convolution
Ifx
1
[n℄haslengthPandx
2
[n℄haslengthQ,thenx
1
[n℄x
2
[n℄is
P+Q1long(e.g.,6+41=9)
Nmax(P ;Q).Ingeneral
~ x
1
[n℄~ x
2
[n℄6=x
1
[n℄x
2
[n℄n=0;1;:::;N1
Circularconvolutioncanb ethoughtofasrep eatingtheresultof
linearconvolutioneveryNsamplesandaddingtheresults(overone
p erio d)

6. Example(cont'd)
=
0 8
4
0 8 6
1
2
2
1
+
3
4
0
3
6
7
3
13

ButifNP+Q1
~ x
1
[n℄~ x
2
[n℄=x
1
[n℄x
2
[n℄n=0;1;:::;N1

7. LinearConvolutionviaCircularConvolution
IfN9onep erio dofcircularconvolutionwillb eequaltolinear
convolution.
0 8 6
1
*
=
4
0 8
0 84
1

8. ConvolutionUsingtheDFT
Averyecientalgorithm,calledthe
FastFourierTransform(FFT)
,
existsforcomputingtheDFT
Sincex
1
[n℄x
2
[n℄ !X
1
[k℄X
2
[k],itismoreecienttocompute
circularconvolutionusingtheFFTasfollows:
y[n℄=DFT
1
(
X
1
[k℄X
2
[k℄
)