Search by:
Parallel Computation Algorithm of Convolution
Full text (PDF)
UDC: 510.52
Publication Language: Russian
Stuc. intelekt. 2012; 17(3):79-95
Abstract: It is given the optimization of computation algorithm for convolution of length N=2ⁿ based on Fast Walsh transform (FWT). The optimization includes the use of the quality of pre-computational adjustment of multi-digit value of length M by multi-digit value of length M/2 to get the sum of FWTs both multi-digit values based on computation of one FWT multi-digit value of length M . The total number of FWTs is reduced more than twofold. That reduces the number of single precision additions and subtractions on sequential computation. It is shown that it is possible to compute algorithm in parallel. There are examples of computation algorithm of convolutions of length 4 и 8. Complexity of sequential and parallel computations is shown.
Keywords: multidigit arithmetic, cyclic convolution, multidigit multiplication.
References:
View full text (PDF)