An Observation on the Bisectional Interconnection Networks

Abstract

We show that the recently proposed bisectional interconnection network (BIN) [3] of 2n nodes for any even n, is isomorphic to the n-dimensional folded hypercube (FHC) [5], an n-dimensional hypercube with additional edges between any two nodes that are of Hamming distance n apart. This observation leads to simplification for the proofs of many interesting properties for the BIN. Inspired by the isomorphism between BIN and FHC, we study the class of topologies where nodes are represented by bit strings and two nodes are adjacent if and only if the bitwise Exclusive-OR of their addresses fall in a set of predefined bit string patterns. A few theorems are given to characterize the topology from the mathematical properties of the binary matrix derived from the definition of edges. Index Terms—Bisectional interconnection network, folded hypercube, hypercube, interconnection network, isomorphism, matrix rank. © 1992 IEEE