KEMBAR78
Circular Shift and Convolution Guide | PDF | Convolution | Sequence
Scribd
Upload
933 views4 pages

Circular Shift and Convolution Guide

The document discusses circular shift and circular convolution of sequences. Circular shift involves shifting a sequence by an integer n0 while keeping it within the original range from 0 to N-1. Circular convolution sums the product of corresponding elements from two length-N sequences as they are shifted against each other from 0 to N-1. An example calculates the 4-point circular convolution of two 4-element sequences and obtains the output sequence {6,7,6,5}. Right and left circular shifts are equivalent up to the length of the sequence.

Uploaded by

Tejhas Kapoor
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
933 views4 pages

Circular Shift and Convolution Guide

The document discusses circular shift and circular convolution of sequences. Circular shift involves shifting a sequence by an integer n0 while keeping it within the original range from 0 to N-1. Circular convolution sums the product of corresponding elements from two length-N sequences as they are shifted against each other from 0 to N-1. An example calculates the 4-point circular convolution of two 4-element sequences and obtains the output sequence {6,7,6,5}. Right and left circular shifts are equivalent up to the length of the sequence.

Uploaded by

Tejhas Kapoor
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

Circular Shift of a sequence

Let us consider length-N sequences defined for 0 ≤ n ≤ N − 1 . Such sequences have sample values
equal to zero for n < 0 and n ≥ N .

For an arbitrary integer n0 , the shifted sequence x1[n] = x[n − n0 ] , may no longer be defined over
the range 0 ≤ n ≤ N − 1 .

This brings the requirement for an other type of shift that will keep the shifted sequence always in
the range 0 ≤ n ≤ N − 1 .

We define a new shift type known as the “circular shift”.

[
x c [ n] = x n − n 0 N
]
where, m N
= m modulo N

for n0 > 0 (right circular shift) the equations below apply:

 x[n − n0 ] n0 ≤ n ≤ N − 1

xc [n] = 
 x[N − n + n] 0 ≤ n ≤ n0
 0

x[n]

(a)

0 1 2 3 4 5

left shift by 5 units

[
x n −1 6
] = x[ n + 5 ] 6

Right shift by 1 unit


(b)

0 1 2 3 4 5
(c)

0 1 2 3 4 5

[
x n−4 6
] = x[ n + 2 ]6

It can be seen from (b) and (c) that right circular shift by n 0 is equivalent to a left circular shift by
(N − n 0 ) .

More over a circular shift n 0 greater than N is equivalent to circular shift by n 0 N

Circular Convolution
Circular convolution between two length N sequences can be carried out as shown by the
expression below:

[ ]
N −1
yC [n] = ∑ g [m]h n − m N
m=0

Since the above operation involves two length-N sequences it is referred to as the N-point
circular convolution and denoted by:

yC [n ] = g [n ] N h[n ]

As in linear convolution circular convolution is commutative.

i.e. g [n ] N h[n ] ≡ h[n ] N g [n ]


Example:
Determine the 4-point circular convolution of the two length-4 sequences g[n] and h[n] given by:

g [n] = {1,2,0,1} and h[n] = {2,2,1,1}

2 2 2

1 0 1 1 1

0 1 2 3 0 1 2 3

From the definition of the circular convolution:

[ ]
3
yc [n] = g[n] 4 h[n] = ∑ g[m]h n − m N
0≤n≤3
m=0
Therefore:

[ ]
3
yc [0] = ∑ g[m]h − m N
0≤n≤3
m=0

The circular time-reversed sequence h − m [ 4


] is as shown below:

2 2 2 2 1 2 2 2 2
1 1 1 1 1 1 1

0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3

n=0 n =1 n=2 n=3


[
h −m 4
] [
h 1− m 4
] [
h 2−m 4
] [
h 3−m 4
]
By performing the product of g[m] with h − m [ 4
] for each value of m in the range 0 ≤ m ≤ 3
And summing the products we get:

yC [0] = g [0]⋅ h[0] + g [1]⋅ h[3] + g [2]⋅ h[2] + g [3]⋅ h[1]


= (1× 2 ) + (2 × 1) + (0 × 1) + (1× 2) = 6
[
yC [1] = ∑ g [m]h 1 − m 4
]
yC [1] = g [0]h[1] + g [1]⋅ h[0] + g [2]⋅ h3 + g [3]⋅ h[2]
= (1× 2 ) + (2 × 2 ) + (0 ×1) + (1× 1) = 7

yC [2] = g [0]h[2] + g [1]⋅ h[1] + g [2]⋅ h[0] + g [3]⋅ h[3]


= (1×1) + (2 × 2) + (0 × 2) + (1×1) = 6

yC [3] = g [0]h[3] + g [1]⋅ h[2] + g [2]⋅ h[1] + g [3]⋅ h[0]


= (1× 1) + (2 × 1) + (0 × 2 ) + (1× 2 ) = 5

Ans: yC [N ] = {6,7,6,5}

You might also like