Novel approach for implementing convolutions with small tables

摘要

The author presents an algorithm, the one over eight squared algorithm, which can be useful in computing tasks with convolutional complexity, such as convolutions, correlations and complex multiplications. The algorithm reduces the address space requirement and hardware investment for table lookup implementations of such tasks from 2/sup 2n/ to 2/sup n/, where n is the width of the operands. Owing to considerable reduction in the required table size, convolutions and correlations with table lookups can be cost-effectively extended to wider operands.