Hardware index to permutation converter
Butler, Jon T.
MetadataShow full item record
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).
19th Reconfigurable Architectures Workshop, May 21-22, 2012, Shanghai, China.
RightsThis publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
Showing items related by title, author, creator and subject.
Chung, Jong Ho (Monterey, California: Naval Postgraduate School, 2013-09);In this thesis, we study a type of affine equivalence for the monomial rotation-symmetric (MRS) Boolean func-tions and two new construction techniques for cryptographic Boolean functions based on the affine equivalence of ...
Stănică, Pantelimon; Mandal, Bimal; Gangopadhyay, Sugata; Pasalic, Enes (2015-06-14);Two (so-called C;D) classes of permutation-based bent Boolean functions were introduced by Carlet two decades ago, but without specifying some explicit construction methods for their construction (apart from the subclass ...
Canright, David; Chung, Jong H.; Stănică, Pantelimon (Elsevier, 2015);The goal of this paper is two-fold. We first focus on the problem of deciding whether two monomial rotation symmetric (MRS) Boolean functions are affine equivalent via a permutation. Using a correspondence between such ...