Optimum Circuits for Bit-Dimension Permutations

In this paper, we present a systematic approach to design hardware circuits for bit-dimension permutations. The proposed approach is based on decomposing any bit-dimension permutation into elementary bit-exchanges. Such decomposition is proven to achieve the theoretical minimum number of delays required for the permutation. This offers optimum solutions for multiple well-known problems in the literature that make use of bit-dimension permutations. This includes the design of permutation circuits for the fast Fourier transform, bit reversal, matrix transposition, stride permutations, and Viterbi decoders.Funding Agencies|Swedish ELLIIT Program; FPU Fellowship of the Spanish Ministry of Education [AP2005-0544]; Spanish National Research and Development Program [TEC2014-53815-R]; Madrid Regional Government [S2013/ICE3000]