System and method for designing architecture for specified permutation and datapath circuits for permutation

Abstract

Computer-implemented systems and methods that provide an efficient technique for performing a large class of permutations on data vectors of length 2, n>1, implemented with streaming width 2(where 1≦k≦n−1). The technique applies to any permutation Q on 2datawords that can be specified as a linear transform, i.e., as an n×n bit matrix (a matrix containing only 1s and 0s) P on the bit level. The relationship between Q and P is as follows: If Q maps (dataword) i to (dataword) j, then the bit representation of j is the bit-matrix-vector product of P with the bit representation of i. Given such a permutation specified by the matrix P and given the streaming width (k), an architectural framework (or datapath) is calculated to implement the permutation.