Perfect Shuffle Permutations

A perfect-shuffle permutation of port labels can be used to map from a set of source labels S to a set of destination labels D. The ordered set of input labels is divided into two subsets of equal size which are then interleaved. This can be represented by the bipartite graph of figure 1, from which it can be observed that this permutation can be produced by a simple manipulation of the binary representation of the source label.

If a port label is expressed as an ordered set of binary digits, x, such that

x= {an, an-1, .. a2, a1} = an.2n-1 + an-1.2n-2 + .. + a1

then it is a relatively simple matter to define formally the perfect-shuffle permutation. Observing the source and destination port labels for N=4,

S = {0,0}, {0,1}, {1,0}, {1,1}
D = {0,0}, {1,0}, {0,1}, {1,1}

it can be seen that a perfect-shuffle permutation consists of a simple circular rotation of the port label bits one place to the left. Thus, the perfect shuffle permutation σ(x) is defined to be

σ(x) = {an-1, an-2, .. a1, an}

It is also possible to rotate just a part of the binary representation of x, and this gives rise to the super-shuffle and sub-shuffle permutations. The kth super-shuffle, denoted σk, involves a rotation of the most significant k bits in x, thus

σk(an, an-1, .. a2, a1) = {an-1, .. an-1+1, an, an-k, .. a1}

The kth sub-shuffle, σk, involves a rotation of the least significant k bits in x, thus

σk(an, an-1, .. a2, a1) = {an, .. ak+1, ak-1, .. a1, ak}

The main reason why the perfect shuffle alone is not sufficient to implement a full interconnection structure can be seen by observing the figure, which depicts the perfect shuffle permutation in terms of all possible inter-nodal links.

When the perfect shuffle permutation is repeatedly applied to x, effectively recirculating data through the network several times, there are a number of unconnected groups of network ports. This is a consequence of the number of 1's and 0's in the binary representation of x remaining unaffected by the perfect-shuffle permutation.