Abstract: The proposed decomposition algorithm follows the divide-and-conquer approach. Specifically, operands of discrete convolution operation are decomposed into smaller units, computed separately, and then combined for the final result. The decomposition of the operands is based on integer modular arithmetic from Number Theory. Operands are treated as ordered set, and integer modular arithmetic is used to partition these sets into congruent subsets. It is basically a Decimation by p operation, where p is the common factor of the operands' sizes. Since the proposed decomposition algorithm is an isomorphism, the decomposed convolution operation is equivalent to the original one. Processing speed is increased by implementing these decomposed convolution operations in parallel. The proposed algorithm is similar to the well- known Block convolution except that it is more suitable for parallel implementation. Because the decomposed operations are highly regular and independent, it is also suitable for VLSI implementation.!12
展开▼