The general time-space-time switching problem in telecommunications requires the use of multichannel time slot interchangers. We propose two multichannel time slot sorters which sort N/sup 2/ time-division multiplexed (TDM) optical inputs, arranged as N frames with N time slots per frame using O(Nlog/sup 2/N) optical switch elements. The TDM optical inputs are sorted in place without expanding the space-time fabric into a space-division switch. The hardware components used are 2/spl times/2 optical switches (LiNbO/sub 3/ directional couplers) and optical delay lines connected in a feedforward fashion. Two space-time variants of the spatial odd-even merge algorithm are used to design the sorters. By maintaining the number of shift-exchange operations invariant at each stage, the proposed sorters use fewer switches than previously proposed sorters using switches with feedback line delays. The use of local control at each 2/spl times/2 switch makes the proposed sorters more practical for high-speed optical inputs than Benes-based time slot permuters with global control and high latency, which affects interframe distance. Both time slot sorters support pipelining of input frames and sorted outputs are available at each time slot after an initial frame delay. The proposed sorters find practical application in the time-domain equivalents of space-division, nonblocking, self-routing packet switches using the sort-banyan architecture, such as the Starlite switch, Sunshine switch, etc.

We consider time slot interchangers (TSIs) which are built from 2/spl times/2 exchange switches and delays and which are useful for time division multiplexed (TDM) systems in telecommunications and pipelined systems such as time multiplexed optical multiprocessors. We formulate a general method for constructing TSIs based on multistage interconnection networks in the space domain via space-to-time mapping. Two types of TSIs, time slot permuters and time slot sorters, are considered. We review the time slot permuter based on the Benes network, and obtain the /spl Lambdaspl tilde/ time slot permuter based on the bit-controlled, self-routing /spl Lambda/ permutation network. The time slot sorter, S/sub N/, is obtained from the Batcher spatial sorting network. The generalized Lambda time slot permuter /spl Lambdasub Nsup q/ is obtained, in an algorithmic approach, by combining the idea of the /spl Lambdaspl tilde/ time slot permuter and Q-way bitonic decomposition (Q=2/sup q/). The numbers of switches, control complexities, and frame delays of these architectures are compared, and the problem of crosstalk in optical implementation is discussed. It is shown that control complexity can be traded against the number of switches.>

The authors formulated a general method for constructing time slot permuters from spatial permutation networks. Using the method, they constructed a new time slot permuter, the Lambda time-slot permuter. The Lambda time slot permuter is obtained from the bit-controlled, self-routing permutation network, the Lambda network. While the Lambda time slot permuter requires more hardware than the time slot permuter based on the Benes network described by S.V. Ramanan et al. (1990), its control is very simple. In the Lambda time slot permuter, a single bit from the destination tag in the first of a pair of time slots entering an exchange element is used as the control bit so that the switch setting can be done before the second time slot arrives; thus, it is possible that the switch setting does not incur any delay. The Lambda time slot permuter is suitable for a class of applications where on-the-fly control of the time slot permuter is important, and is especially efficient for a pipelined operation.>

Formulas for the number of the augmented-data-manipulator (ADM)-passable permutations were given previously as cross-recurrence relations for the cardinalities of three specific subsets of such permutations. More concise, transparent recurrence formulas are derived utilizing a novel and conceptually simple model of the ADM. As a byproduct, a global control algorithm for the inverse ADM (IADM) is obtained that can set paths for all the IADM-passable permutations. This algorithm can be adapted for the ADM. Also included are two local control algorithms for the IADM/ADM: the signed bit difference tag control and the destination tag control.>