Skip to content Skip to navigation

Connexions

You are here: Home » Content » Circular Shift Operator

Navigation

Content Actions
  • Download module PDF
  • Add to ...
    Add the module to:
    • My Favorites
    • A lens
    • An external social bookmarking service
    • My Favorites (What is 'My Favorites'?)
      'My Favorites' is a special kind of lens which you can use to bookmark modules and collections directly in Connexions. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need a Connexions account to use 'My Favorites'.
    • A lens (What is a lens?)

      Definition of a lens

      Lenses

      A lens is a custom view of Connexions content. You can think of it as a fancy kind of list that will let you see Connexions through the eyes of organizations and people you trust.

      What is in a lens?

      Lens makers point to Connexions materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

      Who can create a lens?

      Any individual Connexions member, a community, or a respected organization.

    • External bookmarks
  • E-mail the author

Recently Viewed

This feature requires Javascript to be enabled.

Circular Shift Operator

Module by: Richard Baraniuk

Summary: Introduction to the circular shift operator.

The concept of a time shift or delay is crucial to DSP.

Example 1

yn=xn-2 y n x n 2 , which means "delay xx by 2 time units" (Figure 1).

Figure 1: N=8 N 8 .
Figure 1 (delay.png)
There are now 2 issues:
  • What to put in the first two positions in the graph of yy (Figure 1)?
  • What to do with values that slide off the end of yy (Figure 1)?
A solution: stuff the values that slide off the end into the beginning (Figure 2).
Figure 2
Figure 2 (circ.png)

Notes

1.

This is equivalent to putting xx on a wheel/circle with N N ticks and spinning it 2 ticks. x=11110000T x 1 1 1 1 0 0 0 0 (Figure 3).

Figure 3: N=8 N 8 .
Figure 3 (wheel1.png)
To delay xx by 2 units, spin the wheel 2 ticks counter-clockwise and read off yy. y=00111100T y 0 0 1 1 1 1 0 0 (Figure 4).
Figure 4
Figure 4 (wheel2.png)
So, we call yy a circular shift of xx.

2.

This is also equivalent to viewing xx as one period of an infinite-length periodic vector xp x p . x=123 x 1 2 3 xp=…123123123123… x p … 1 2 3 1 2 3 1 2 3 1 2 3 … We can then shift xp x p 2 units and read off y y …231231231231… … 2 3 1 2 3 1 2 3 1 2 3 1 … y=231 y 2 3 1 i.e.: we can view a ℂN N signal as one period of a periodic signal.

3.

Finally we can write y y in terms of x x using modulo arithmetic.

yn=xn-2modN y n x n 2 N (1)
for 0≤n≤N-1 0 n N 1 .

Aside:

rmodN=r+pN r N r p N where pp is an integer chosen such that 0≤r+pN≤N-1 0 r p N N 1 . e.g.: 10mod8=10+-1×8=2 10 8 10 -1 8 2 -15mod6=-15+3×6=3 -15 6 -15 3 6 3

General Circular Shift

yn=xn-mmodN y n x n m N (2)
for 0≤n≤N-1 0 n N 1 .

Example 2

Shift x x by -3 units, i.e. m=-3 m -3 (Figure 5).

Figure 5: N=8 N 8 .
Figure 5 (gcs.png)

Circular Shift Matrix

y= C m x y C m x (3)
with yn=xn-mmodN y n x n m N for 0≤n≤N-1 0 n N 1 .

Example 3

m=2 m 2 .

y= C 2 x y C 2 x (4)
00111100=0…………0100…………00110………………010……………0010…………00010………000010……0000010011110000 0 0 1 1 1 1 0 0 0 … … … … 0 1 0 0 … … … … 0 0 1 1 0 … … … … … … 0 1 0 … … … … … 0 0 1 0 … … … … 0 0 0 1 0 … … … 0 0 0 0 1 0 … … 0 0 0 0 0 1 0 0 1 1 1 1 0 0 0 0

Notes

  1. C m C m is a "permutation" matrix.
  2. Columns of C m C m are shifted δ δ basis.
Indeed...
C m =δ [ m ] mod N δ [ m + 1 ] mod N …δ [ m + N - 1 ] mod N C m δ [ m ] mod N δ [ m + 1 ] mod N … δ [ m + N - 1 ] mod N (5)

Example 4

C 3 C 3 for N=5 N 5 . Apply to x=12345T x 1 2 3 4 5 (Figure 6).

Figure 6
Figure 6 (x.png)

Aside on Circular Shifts

C m x C m x circularly shifts the column vector xx down mm units.

Example 5

C 1 123=001100010123=312 C 1 1 2 3 0 0 1 1 0 0 0 1 0 1 2 3 3 1 2 (6)

xT C m T x C m circularly shifts the row vector xT x right mm units.

Example 6

123 C 1 T=123010001100=312 1 2 3 C 1 1 2 3 0 1 0 0 0 1 1 0 0 3 1 2 (7)

Comments, questions, feedback, criticisms?

Send feedback