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.5    CYCLIC CONVOLUTION

Cyclic convolution is also known as circular convolution. Let h = {h0, h1,· · ·, hn−1} be the filter coefficients and x = {x0,x1,· · ·,xn−1} be the data sequence. The cyclic convolution can be expressed as

image

and the output samples are given by

image

where ((ik)) denotes (ik) mod n. The cyclic convolution can be computed as a linear convolution reduced by modulo pn – 1. (Notice that there are 2n – 1 different output samples for this linear convolution). Alternatively, the cyclic convolution can be computed using CRT with m(p) = pn – 1, which is much simpler.

Example 8.5.1 Construct a 4 × 4 cyclic convolution algorithm using CRT with m(p) = p4 – 1 = (p – 1)(p + 1)(p2 + 1).

Solution

Let h(p) = h0 + h1p + h2p2 + h3p3 and x(p) = x0 + x1p + x2p2 + x3p3. Let m(0)(p) = p – 1, m(1)(p) = p + 1, m(2)(p) = p2 + 1. Let image. Use the relationship (8.37) to construct the following table:

image

Compute residues

image

and

Notice that it takes 1 multiplication to compute and 1 to compute The computation ...

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