An efficient systolic array algorithm for the VLSI implementation of a prime-length DHT

In this paper, we present a new systolic algorithm for an efficient design approach using a bi-port memory-based VLSI implementation of the DHT. Using auxiliary input and output sequences and appropriate permutations it is shown that it is possible to compute a prime-length DHT using two cyclic convolutions having the same form and length that can be computed in parallel leading to improve throughput with a reduced hardware and I/O costs. The two computation structures can be mapped on the same linear systolic array using an appropriate hardware-sharing technique. Adopting a bi-port memory-based systolic architecture we can further reduce the hardware complexity and I/O costs while preserving all the advantages of a cyclic convolution based systolic array implementation such as regularity, modularity and a good topology of the interconnection structure.