The Looping Algorithm Extended to Base 2<sup>t</sup>Rearrangeable Switching Networks

Abstract

Clos Rearrangeable Switching Networks (RSN's) are examined with regard to properties of imprimitivity. It is shown that a certain version of RSN's built by 2 × 2 matrices in all stages except in the center stage have properties that imply a routing procedure for base 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">t</sup> RSN's ( <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">t</tex> is any positive integer) based on the looping procedure. The routing procedure gives, in turn, control data applicable to base 2, base 4, ..., base 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">t</sup> RSN's. Necessary computing time increases only linearly with the number of inputs if the maximum degree of parallelism is utilized. The obtained results can be applied to networks with an arbitrary base <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</tex> by omitting unnecessary parts of a suitable base 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">t</sup> network.