Characterizing the Bit Permutation Networks Obtainedfrom the Line Digraphs of Bit Permutation NetworksFrank K. HwangDepartment of Applied Mathematics, National Chiao Tung University, Hsinchu 30050, Taiwan, Republic of ChinaChih-Hung YenDepartment of Applied Mathematics, National Chiao Tung University, Hsinchu 30050, Taiwan, Republic of ChinaA bit permutation network is an sss-stage interconnectionnetwork composed ofdddnnn−1ddd ××× ddd crossbar switches ineach stage. This class of networks includes most of themultistage interconnection networks. Recently, Changet al. [Networks 33 (1999), 261–267] showed that ansss-stageddd-nary bit permutation network NNN with dddninputs(outputs) can be characterized by an (sss −−− 1)-vector (kkk1,...,kkksss−1), where kkkt∈∈∈ {1, ..., nnn −−− 1}. In this paper, wegive a simple (but not trivial) formula to determine thecharacteristic vector of a new networkGGG(NNN)+, which is,approximately, the line digraph ofNNN. We use this for-mula to obtain relations between some well-studied bitpermutation networks.© 2001 John Wiley & Sons, Inc.Keywords: multistage interconnection network; switchingnetwork; bit permutation network; photonic switching1. INTRODUCTIONChang et al. [1] proposed the notion of a bitpermutation network which is an s-stage interconnec-tion network composed of dn−1d × d crossbar switchesin each stage, where a crossbar switch, or just a crossbar,can connect any one-to-one mapping from inputs to out-puts. This class of networks includes the Beneˇs network,the Omega network, the banyan network, the baselinenetwork, and their extra-stage versions, namely, mostof the multistage interconnection networks. Suppose thatthe dn−1crossbars in a stage are each labeled by a distinctReceived January 200l; accepted April 2001Correspondence to: C.-H. Yenc 2001 John Wiley & Sons, Inc.d-nary (n−1)-vector. They showed that an s-stage d-narybit permutation network N with dninputs (outputs) canbe characterized by a (s − 1)-vector (k1,...,ks−1), wherekt= j ∈{1,...,n − 1} means that N is topologicallyequivalent to a network whose linking pattern betweenstage t and t+1 consists of dn−2disjoint complete bipar-tite graphs where each such graph connects all crossbarsin stage t and t+1 having the same d-nary (n−1)-vectorsexcept bit j. Fig 1 shows a bit permutation network withcharacteristic vector (3, 1, 2) and is topologically equiv-alent to the network in Fig 2.The line digraph G(N) of a multistage crossbar net-work N is obtained by taking the links of N as nodes inG(N), and an arc from node p to node q in G(N) existsif link p is adjacent to and precedes link q in N. Notethat nodes of the same stage in G(N) are ordered bythe starting points of their corresponding links in N (seeFig 3). Let G(N)+be obtained from G(N) by adding d in-lets (outlets) to each input (output) node. By interpretingnodes as crossbars, then G(N)+can also be viewed as amultistage crossbar network (see Fig 4). It is well knownthat being crosstalk-free (each crossbar carries at mostone path) is an essential property for photonic switching,which uses optical fiber instead of electric wire as thetransmission media. Lea [3] observed that if two pathsare link-disjoint in N then their corresponding paths arenode-disjoint in G(N). Furthermore, Hwang and Lin [2]gave formulas relating the nonblocking properties of Nto the crosstalk-free nonblocking properties of G(N)+.Therefore, it is of interest to know that if N is a bitpermutation network, what kind of network is G(N)+.In this paper, we will prove that if N is an s -staged-nary bit permutation network with dninputs (outputs)NETWORKS, Vol. 38(1), 1–5 2001FIG. 1. A bit permutation network N2(4; u, v, f1,f2,f3).then G(N)+is an (s+1)-stage d-nary bit permutation net-work with dn+1inputs (outputs). Furthermore, we givea simple (but not trivial) formula to determine the char-acteristic vector of G(N)+from that of N. Finally, weuse this formula to obtain relations between some well-studied bit permutation networks.2. BIT PERMUTATION NETWORKSConsider a multistage interconnection network withdninputs (outputs) and s stages of dn−1crossbars of sized × d. Let the ithcrossbar in a stage be labeled by i inthe d-nary (n − 1)-vector. Define a bit-j group as the setof crossbars in a stage identical in their labels except thejthbit. Such a group will also be labeled by a d-nary(n − 1)-bit vector which is identical to any member inthe group except that bit j is replaced by the symbolx0, which stands for the set {0, 1,...,d− 1}. Chang etFIG. 2. A bit permutation network N2(4; I3,I1,I2).al. [1] called an s-stage d-nary interconnection networka bit permutation network if the links from stage t tot + 1 are always from a bit-utgroup Z to a bit-vtgroupZ0, where Z0is a permutation of Z, for t =1,...,s− 1.Those values utand vt,1≤ t ≤ s− 1, can be representedby two functions u and v from set {1,...,s− 1} to set{1,...,n−1}. For our purpose, we will restate their mainresults in a slightly different way (and provide proofs forjustification).Assume that N is an s-stage d-nary bit permuta-tion network with dninputs (outputs). Let ft, t =1,...,s− 1, denote the group linking function betweenstage t and t +1 ofN. Then, N can be represented byNd(n; u, v, f1,...,fs−1). Note that ftis a permutation of{1,...,n− 1} and (ft)−1(ut)=vt.The network in Figure 1 shows a bit permutation net-work with 16 inputs (outputs), in which crossbar i isrepresented by its binary 3-bit vector (x1,x2,x3). Ignor-ing the inputs and outputs, then the network in Figure1 can be viewed as a digraph whose nodes are those 32crossbars labeled by (x1(t),x2(t),x3(t)) (t is often omitted)and links are directed from left to right, where 1 ≤ t ≤ 4and x1,x2,x3∈{0, 1}. The links are from a bit-3 group(x1,x2,x0) in stage 1 to a bit-1 group (x0,x1,x2) in stage 2,from a bit-2 group (x1,x0,x3) in stage 2 to a bit-3 group(x1,x3,x0) in stage 3, and from a bit-2 group (x1,x0,x3)in stage 3 to a bit-2 group (x1,x0,x3) in stage 4, wherex0∈{0, 1}. Thus,u1=3,v1=1,f1(1)=3,f1(2)=1,f1(3)=2,u2=2,v2=3,f2(1)=1,f2(2)=3,f2(3)=2,u3=2,v3=2,f3(1)=1,f3(2)=2,f3(3)=3.In this paper, we shall use the cycle notation for per-mutations, that is, the cycle (i1,i2,...,in) represents thepermutation f with f(i1)=i2,f(i2)=i3,...,f(in−1)=in,f(in)=i1, and the cycle (j) represents f with f(j)=j.Then, f1can be represented by (1, 3, 2); f2, by (1)(2, 3);and f3, by