Abstract

Calculation of a function's autocorrelation coefficients is usually done either by brute force application of the defining equation, or by using a fast method to calculate the interim spectral coefficients and applying a transform to these coefficients. Both of these methods require time exponential in the number of inputs to calculate each coefficient. We present in this paper various methods for more efficient calculation of a function's first order autocorrelation coefficients. The first method is based on a disjoint cube list, and requires on the order of p² time for each coefficient, where p is the number of cubes in the disjoint list. The other methods are based on ROBDD representations of the function(s). Advantages and disadvantages of each method is discussed, and possibilities for other techniques are introduced.