Characterizing the bit permutation networks obtained from the line digraphs of bit permutation networks
Frank K. Hwang, Chih‐Hung Yen · Networks · 2001
Abstract A bit permutation network is an s‐stage interconnection network composed of dn−1 d × d crossbar switches in each stage. This class of networks includes most of the multistage interconnection networks. Recently, Chang et al. [Networks 33 (1999), 261–267] showed that an s‐stage d‐nary bit permutation network N with dn inputs (outputs) can be characterized by an (s − 1)‐vector (k1, …, ks−1), where kt ∈ {1, …, n − 1}. In this paper, we give a simple (but not trivial) formula to determine the characteristic vector of a new network G(N)+, which is, approximately, the line digraph of N. We use this formula to obtain relations between some well‐studied bit permutation networks. © 2001 John Wiley & Sons, Inc.