Decomposing BPC Permutations into Semi-Permutations for Crosstalk Avoidance in Multistage Optical Interconnection Networks

摘要

This paper introduces a simple O(N) algorithm that decomposes BPC (bit-permute-complement) permutations into semi-permutations for avoiding crosstalk when realizing them in N × N optical multistage interconnection networks (OMINs). Crosstalk means that two optical signals, sharing an optical switch, undergo a kind of undesired coupling. A semi-permutation is a partial permutation which meets the requirement for each switch in an input and output stages of the network to be used with only one optical signal at a time. It provides avoiding crosstalk in the first and the last stages of a network and creates the potential for crosstalk-free realization of a semi-permutation, and finally the whole permutation in question. The algorithm is based on employment the periodicity of appearing 1 's and 0's in columns of transition matrices for BPC permutations.