An Algorithm for Computing the Correlation Functions of Walsh Functions

An algorithm for computing the correlations of Walsh functions is presented. Given indices j and p between 0 and 2n - 1, the algorithm computes the correlation between the jth and kth Walsh-Paley function at time differences t = i2-n, i =0,1,..., 2n - 1. These values specify the correlation completely as it varies linearly between these points. A Fortran program is shown. The time required to compute a complete 2n point correlation is approximately the same as that of a 2n point fast Walsh transform.