Chapter 10 Communication Networks288
Bn
Bn
BnC 1
2 n
2 n
2 nC^1
À
À
new inputs new outputs
Figure 10.3 BnC 1 , the Bene ̆s Net switches with 2 nC^1 inputs and outputs.both inputs and outputs at each stage. Now we recursively defineBnto be the
switches and connections (without the terminals) of the Benes net with ̆ NWWD 2 n
input and output switches.
The base case,B 1 , with 2 input switches and 2 output switches is exactly the
same asF 1 in Figure 10.1.
In the constructor step, we constructBnC 1 out of twoBnnets connected to a
new set of 2 nC^1 input switchesand alsoa new set of 2 nC^1 output switches. This is
illustrated in Figure 10.3.
Namely, theith and 2 nCith new input switches are each connected to the same
two switches, namely, to theith input switches of each of twoBncomponents for
iD1;:::;2n, exactly as in the Butterfly net. In addition, theith and 2 nCith new
outputswitches are connected to the same two switches, namely, to theith output
switches of each of twoBncomponents.
NowBnC 1 is laid out in columns of height 2 nC^1 by adding two more columns
of switches to the columns inBn. So theBnC 1 switches are arrayed in2.nC1/
columns. The total number of switches is the number of columns times the height
of the columns, namely,2.nC1/2nC^1.
All paths inBnC 1 from an input switch to an output are the same length, namely,
2.nC1/ 1 , and the diameter of the Bene ̆s net with 2 nC^1 inputs is this length plus
two because of the two edges connecting to the terminals.
So Benes has doubled the number of switches and the diameter, of course, but ̆