VLSI Digital Signal Processing Systems: Design and Implementation

8.3    WINOGRAD ALGORITHM

The Winograd short convolution algorithm is based on the CRT over an integer ring, which can be stated as:

“It is possible to uniquely determine a nonnegative integer given only its remainders with respect to the given moduli, provided that the moduli are relatively prime and the integer is known to be smaller than the product of the moduli.”

In a polynomial ring over any field, there again exists a CRT. Both the CRT over an integer ring and the CRT over a polynomial ring are summarized below.

Theorem 8.3.1 CRT for Integers

Given c_i = R_mi[c], for i = 0, 1, · · · , k, where m_i are moduli and are relatively prime, then

where M = m_i, M_i = M/mi and N_i is the solution of

provided that 0 ≤ c < M. The notation R_mi[c] represents the remainder when c is divided by m_i.

Theorem 8.3.2 CRT for Polynomials

Given c⁽ⁱ⁾(p) = R_{m⁽ⁱ⁾(p)}[c(p)], for i = 0, 1, · · · , k, where m⁽ⁱ⁾(p) are relatively prime, then

where and N⁽ⁱ⁾(p) is the solution of

provided that the degree of c