Xref: utzoo sci.crypt:3821 sci.electronics:15645
Path: utzoo!attcan!uunet!know!zaphod.mps.ohio-state.edu!unix.cis.pitt.edu!dsinc!netnews.upenn.edu!dsl.cis.upenn.edu!touch
From: touch@dsl.cis.upenn.edu (Joe Touch)
Newsgroups: sci.crypt,sci.electronics
Subject: Re: programmable bit permutation circuit
Summary: use a Batcher-banyan organization
Message-ID: <32904@netnews.upenn.edu>
Date: 15 Nov 90 00:30:51 GMT
References: <HUGHES.90Nov14134247@locusts.Berkeley.EDU>
Sender: news@netnews.upenn.edu
Reply-To: touch@dsl.cis.upenn.edu (Joe Touch)
Distribution: sci
Organization: University of Pennsylvania
Lines: 12

In article <HUGHES.90Nov14134247@locusts.Berkeley.EDU> hughes@locusts.Berkeley.EDU (Eric Hughes) writes:
>I am looking for a circuit which can arbitrarily permute a fix number
>of bits (e.g. 64).

>any such circuit which uses O(n log n) gates?

Use a Batcher-banyan organization.  It has (n/2)log(n) elements,
and can realize any permutation.  

See references on Multistage Interconnection Networks.

Joe