Circular Shifts 2.5 2002/08/02 2005/06/24 19:40:16.395 GMT-5 Justin Romberg jrom@rice.edu Roy Ha rha@rice.edu Justin Romberg jrom@rice.edu Richard G. Baraniuk richb@rice.edu circular shift circular shifts DFT discrete time fourier fourier transform The module looks at circular shifting and how it is can be used as a tool to represent the shifting of a periodic sequence. The many properties of the DFT become really straightforward (very similar to the Fourier Series) once we have once concept down: Circular Shifts.

Circular shifts We can picture periodic sequences as having discrete points on a circle as the domain

Shifting by m, f n m , corresponds to rotating the cylinder m notches ACW (counter clockwise). For m -2 , we get a shift equal to that in the following illustration:

for m -2

To cyclic shift we follow these steps: 1) Write f n on a cylinder, ACW

N 8

2) To cyclic shift by m, spin cylinder m spots ACW → f n f (( n + m )) N

m -3

If f n 0 1 2 3 4 5 6 7 , then f (( n - 3 )) N 3 4 5 6 7 0 1 2 It's called circular shifting, since we're moving around the circle. The usual shifting is called "linear shifting" (shifting along a line).

Notes on circular shifting f (( n + N )) N f n Spinning N spots is the same as spinning all the way around, or not spinning at all. f (( n + N )) N f (( n - ( N - m ) )) N Shifting ACW m is equivalent to shifting CW N m

f (( - n )) N The above expression, simply writes the values of f n clockwise.

f n f (( - n )) N

Circular shifts and the DFT Circular Shifts and DFT If f n ↔ DFT F k then f (( n - m )) N ↔ DFT 2 N k m F k (i.e. circular shift in time domain = phase shift in DFT) f n 1 N k 0 N 1 F k 2 N k n so phase shifting the DFT f n 1 N k 0 N 1 F k 2 N k n 2 N k n 1 N k 0 N 1 F k 2 N k n m f (( n - m )) N