Application of distributed arithmetic to digital signal processing
Burrus, C. Sidney
Master of Science
Distributed arithmetic trades memory for logic circuits and speed, it is suitable for some fixed computations like the DFT computation and the filter calculation with fixed coefficients. A prime length N DFT computation can be converted to two length (Nl)/2 real convolutions and distributed arithmetic can be applied to these convolution computations. Since all the computations of a prime factor FFT reside in a few short length DFT computations, we can do all the prime factor FFT computations by distributed arithmetic. When the input to a DFT is read, we can save half of the computations of a prime factor FFT algorithm by computing only half of the output without computing the other half and get the other half by the symmetric relation. Using an input index table and an output index table in a prime factor FFT algorithm, we avoid any index calculations for any dimension transform. The transpose form of filter structures using distributed arithmetic have a different arrangement of memory and accumulators from that of direct structures. In software implementation, the transpose structure has the advantage of less process with the input or output data to get the address to address the table in the memory but with the disadvantage of more accumulations when compared to the direct structure. Altogether, an IIR filter with transpose structure will have a little higher speed than that with direct structure when implemented on a microprocessor. Distributed arithmetic reduces the DFT and filter computations to simple and repeated addressing and accumulating operations which can be done by simple logic. A general, external logic can be designed to do both the DFT and filter calculations with a microprocessor.