Hardware index to permutation converter

Abstract

We demonstrate a circuit that generates a permutation in response to an index. Since there are n! n-element permutations, the index ranges from 0 to n! à ¢ 1. Such a circuit is needed in the hardware implementation of unique-permutation hash functions to specify how parallel machines interact through a shared memory. Such a circuit is also needed in cryptographic applications. The circuit is based on the factorial number system. Here, each non-negative integer is uniquely represented as snà ¢ 1(nà ¢ 1)! +snà ¢ 2(nà ¢ 2)! +...+s11!, where 1 à ¢ à ¤ si à ¢ à ¤ i. That is, the permutation is produced by generating the digits si in the factorial number system representation of the index. The circuit is combinational and is easily pipelined to produce one permutation per clock period. We give experimental results that show the efà ¯à ¬ ciency of our designs. For example. we show that the rate of production of permutations on the SRC-6 reconà ¯à ¬ gurable computer is 1,820 times faster than a program on a conventional microprocessor in the case of 10-element permutations. We also show an efà ¯à ¬ cient reconà ¯à ¬ gurable computer implementation that produces random permutations using the Knuth shufà ¯à ¬ e algorithm. This is useful in Monte Carlo simulations. For both circuits, the complexity is O(n2), and the delay is O(n).