Topologies of combined (2 log N-1)-stage interconnection networks
Qing Hu, Xiaojun Shen, Jingyu Yang · IEEE Transactions on Computers · 1997
A combined (2 log N-1)-stage interconnection network (denoted by /spl Delta//spl oplus//spl Delta/') is constructed by concatenating two Omega-equivalent networks (/spl Delta/ and /spl Delta/') with the rightmost stage of /spl Delta/ and the leftmost stage of /spl Delta/' overlapped. Benes network and the (2 log N-1)-stage shuffle-exchange network are two examples of such networks. Although these two networks have received intensive studies, the research on the topology of entire class of /spl Delta//spl oplus//spl Delta/' networks is very limited so far. In this paper, we study the topological structure of /spl Delta//spl oplus//spl Delta/' networks and propose an algorithm for determining topological equivalence between two given /spl Delta//spl oplus//spl Delta/' networks. We also present a simplified /spl Omega/-equivalence checking algorithm as a supporting result.