Configurable Hardware Solutions for Computing Autocorrelation Coefficients: a Case Study to be presented at FPGA2005

There are many computationally intensive problems in the area of digital design and logic synthesis. Some of these have no “good ” solution; that is, simply by their definition they have exponential run-times. In order to overcome this, we examine the possibility of a configurable hardware solu-tion to speed up one such problem. The computation of the problem is carried out on a Field Programmable Gate Array (FPGA), where the problem is encoded in such a way that within certain parameters, the design of the solution need not be changed for working with a variety of benchmark circuits. This saves considerably on compilation and config-uration times. The use of configurable hardware, however, still allows for configuration in situations where the param-eters change significantly enough to require an altered ap-proach. We examine two implementations of the problem, which in this case consists of computing the autocorrelation coefficients for a Boolean function