O'Reilly logo

VLSI Digital Signal Processing Systems: Design and Implementation by Keshab K. Parhi

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ci = Rmi[c], for i = 0, 1, · · · , k, where mi are moduli and are relatively prime, then

image

where M = image mi, Mi = M/mi and Ni is the solution of

image

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

Theorem 8.3.2 CRT for Polynomials

Given c(i)(p) = Rm(i)(p)[c(p)], for i = 0, 1, · · · , k, where m(i)(p) are relatively prime, then

image

where image and N(i)(p) is the solution of

provided that the degree of c

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required