Cyclic convolution is also known as circular convolution. Let *h* = {*h*_{0}, *h*_{1},· · ·, *h*_{n−1}} be the filter coefficients and *x* = {*x*_{0},*x*_{1},· · ·,*x*_{n−1}} be the data sequence. The cyclic convolution can be expressed as

and the output samples are given by

where ((*i*–*k*)) denotes (*i*–*k*) *mod n.* The cyclic convolution can be computed as a linear convolution reduced by modulo *p*^{n} – 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*) = *p*^{n} – 1, which is much simpler.

**Example 8.5.1** *Construct a* 4 × 4 *cyclic convolution algorithm using CRT with m*(*p*) = *p*^{4} – 1 = (*p* – 1)(*p* + 1)(*p*^{2} + 1).

**Solution**

*Let h*(*p*) = *h*_{0} + *h*_{1}*p* + *h*_{2}*p*^{2} + *h*_{3}*p*^{3} *and x*(*p*) = *x*_{0} + *x*_{1}*p* + *x*_{2}*p*^{2} + *x*_{3}*p*^{3}. *Let m*^{(0)}(*p*) = *p* – 1, *m*^{(1)}(*p*) = *p* + 1, *m*^{(2)}(*p*) = *p*^{2} + 1. *Let* . *Use the relationship (8.37) to construct the following table:*

*Compute residues*

*and*

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

Start Free Trial

No credit card required