A pipelined tree machine architecture for computing a multidimensional convolution
Kuang Liu · IEEE Transactions on Circuits and Systems · 1982
In this paper, a technique is proposed to decompose a two-dimensional (2-D) cyclic convolution of twod_{1} \times d_{2}arrays, whered_{2} = 2^{m}withm > 1, into many identical and independent 2-D cyclic convolutions of smaller size. Using this technique and the fact that fast polynomial transform (FFT) exists whend_{1}=2^{m-r+1}for1 \leq r \leq m, a pipelined tree machine architecture composed of modular FPT, FFT, and Chinese Remainder Theorem (CRT) computational units is then developed to efficiently compute a 2-D cyclic convolution. Finally, the extension of this tree machine architecture to efficiently compute a multidimensional cyclic convolution is discussed in this paper.