. The perfect shuffle is a transformation that can be operated on a discrete set of ordered elements and its properties are deeply studied both for their intrinsic mathematical importance and for their large variety of applications [18,19]. In order to make a perfect shuffle permutation, the set of elements to be permutated has to be composed by pd elements, with p a prime number and d a positive integer number. Since d is finite, it is possible to enumerate these objects and to represent the correspond- ing number with a p-ary string (e.g., binary if p=2). At this point, a perfect shuffle permutation can be defined as the permutation that exchanges the element whose representation is b1, b2, b3, bd with the element b2, b3, b1. In other words, this transformation operates an ordered left-side rotation of the bits in the element p-ary representation. An example of perfect shuffle permutation is given in Figure 7.12. The perfect shuffle permutation allows us to design an iterative construction mechanism that gives rise to the class of Banyan switch fabrics. In general, the base element of a Banyan switch is a pxp crossbar matrix, where p is a prime number that is also assumed as the basis to code inside the switch fabric the addresses of the input and output ports. In this way, a connections request can be repre- sented as two strings of elements in an alphabet of p elements: the addresses of the input and output ports to be connected. This representation, useful both in the dynamic and in the static case, also allows an automatic routing procedure to be devised that involves almost no computation from the local processor. In order to be concrete, we will assume p=2, but the extension to other values of p is trivial. With p=2, the building block of a Banyan network is a 2x2 crossbar switch that gener- ally is assumed to have four states, as shown in Figure 7.4. Naturally, a similar building block is also suitable for multicasting into the switch fabric. 0 (000) 0 (000) 1 (001) 1 (001) 2 (010) 2 (010) 3 (011) 3 (011