Systematic Design of Systolic Correlators with Application to Parallel Blackman–Tukey Spectral Estimation

Different word-level systolic algorithms exhibiting different properties are derived systematically for the problem of correlation computation by applying certain transformations on the dependence graph which represents the algorithm. The algorithm with properties which best suit the application of Blackman–Tukey spectral estimation is selected and the complete estimator comprising autocorrelation, windowing and DFT computation is implemented systolicly. The overall computation time of the parallel system is 6LT_x+3LT₊ as compared to (3L/2log₂L+2L)T_x+(3Llog₂L)T₊ for the serial system with fast autocorrelation and FFT where L is the number of input data samples and T_x and T₊ are the times needed for one multiplication and one addition respectively. This indicates that the parallel system has a speed advantage over the serial system for L≥16 and this speed advantage increases with L. For a typical 1024-sample segment, the parallel system is almost three times faster. The system is also modified to suit applications where a number of spectrum measurements are required consecutively as is the case with iterative spectral estimators. For the modified system, the system clock period can be made as small as 2T_x+T₊ compared to (3/2)log₂L+2]T_x+(3log₂L)T₊ for the serial system so that the parallel system can operate at a higher rate for any value of L. Received August 14, 2000