Perfect shifters [multiprocessor interconnection networks]

Pin-efficient single-instruction multiple-data networks, with p≈√(2m) pins per cell that can-in one clock tick-shift data by any amount k in an interval [-m,m] are considered. Perfect barrel shifters, which perform the group of permutations c→c+k(mod n), 0⩽k⩽n-1, using p=q+1 pins per cell, are known to exist for all n=q²+q+1, where q is any prime power. In sharp contrast, it is shown that for any permutation π of order greater than 3m, one-tick perfect shifters for the set of permutations π^[-m,m] ={π^k|-m⩽k⩽m} exist only for the three cases (m=1, p=2), (m=3, p=3), and (m=6, p=4). In particular, only three perfect linear arrays, c→c+k, exist. The proof is based on a relationship between the difference covers and zero-one solutions to certain quadratic equations