VLSI Digital Signal Processing Systems: Design and Implementation

8.7    CONCLUSIONS

This chapter has introduced various short-length fast convolution algorithms, including the Cook-Toom algorithm, the modified Cook-Toom algorithm, the Winograd algorithm, and the modified Winograd algorithm. Based on the fast short-length convolution algorithms, long convolution algorithms can be derived using iterated convolution method. The relationship between the cyclic convolution and the linear convolution and how they can be derived from each other has also been addressed. Fast convolution algorithms form the basis for design of fast parallel FIR filters (see Section 9.2.2.3).