On first inspection the following discussion on shuffle-exchange permutations may appear to be simply a notational convenience, but it is important to understand how a sequence of shuffle and exchange permutations can together form a useful network. The key to understanding multi-stage permutation networks is to consider the effect each successive permutation has on the label of an object in passage through the network. Assume that S is the label of an object entering the network, and D is the label of the destination of that object. We associate a temporary label L with the object, and this is initially set to S. If we can modify L by a sequence of permutations so that it becomes equal to D then the object will arrive at its destination.
Since the E1 permutation provides us with the choice of inverting the least significant bit of the input label or leaving it intact, it is possible to use the E1 permutation to make the least significant bit in L equal to the least significant bit in D. This is the basic step in converting from L to D, and the choice of ε1 or I permutation determines the switch-node setting in the general exchange box of Figure 1. The next step is to expose the next bit in L to the E1 permutation, and this is done most simply by shifting L by one bit. This is directly equivalent to a perfect-shuffle permutation on all labels L in the range 0 to N, as shown for N=8 in Figure 2. After n=log2N applications of the shuffle and exchange permutations all bits in L will have been changed, and L will be equal to D. As a direct consequence of this, the object located at label L will have been routed to the output port identified by D, and the network will have performed its function.
A number of important multi-stage shuffle-exchange networks have been devised. The banyan, omega and indirect binary n-cube networks are discussed in the next section, Shuffle Exchange Network Examples