Computation of Convolutions by Polynomial Transforms Having Dimensions 2/t/
Original Publication Date: 1978-Feb-01
Included in the Prior Art Database: 2005-Feb-20
Polynomial transforms defined modulo (z/q/+1), with q = 2/t/ can be used to compute two-dimensional transforms defined modulo z/q/ + 1 in both dimensions. We consider the two polynomial sequences: (Image Omitted) This generalized convolution can be computed with q polynomial multiplications modulo (Z/q/+1), as shown in the figure. The a(n,m) and x(s,r) terms are ordered in ORD 1 and ORD 2, respectively, to provide polynomials P(m)(z) and Q(r)(z), which are in turn multiplied by z/m/ and z/r/ in MULT 1 and MULT 2, respectively. Polynomial transforms of q terms and modulo (z/q/+l) are performed in PT1 and PT2 (polynomial transformers) on the MULT 1 and MULT 2 outputs to generate A(k)(z) and X(k)(z). Polynomials A(k)(z) and X(k)(z) are then multiplied together in PM (polynomial multiplier) to provide A(k)(z) .