Formal Construction of Joel's Permutation Networks and Their Setting Algorithms

Shoji SAKURAZAWA  Yoshihide IGARASHI  

Publication
IEICE TRANSACTIONS (1976-1990)   Vol.E64   No.4   pp.235-242
Publication Date: 1981/04/25
Online ISSN: 
DOI: 
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Automata and Languages
Keyword: 


Full Text: PDF>>
Buy this Article




Summary: 
Formal descriptions for constructing a Joel's permutation network are discussed. We show that a setting algorithm of the network can be described in terms of bipartite graphs. We then study a fast parallel algorithm for setting the network. We show that it can be implemented by a parallel computer with N processors in O((log2 N)2) time, where N is the size of permutations produced on the network.