Improved fast polynomial transform algorithm for cyclic convolutions

DOI10.1007/BF01213957MaRDI QIDQ1902509zbMATH OpenFDO

Authors Albert Ming Loh, W. C. Siu

Publication date 9 September 1996

Published in Circuits, Systems, and Signal Processing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01213957

zbMATH Keywords

algorithm complexitycyclic convolutionfast polynomial transform

Mathematics Subject Classification ID

Probabilistic methods, stochastic differential equations (65C99) Numerical methods for discrete and fast Fourier transforms (65T50) Analysis of algorithms and problem complexity (68Q25) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Review text

The authors present an improved version of the fast polynomial transform which eliminates totally the pre-transform and post-transform computations for the realization of the cyclic convolution. This new formulation has the advantage of regular structure and requires just one type of complex root of unity. The computation time is 20\% reduced.

Recommendations

• An improved FPT algorithm for computing two-dimensional cyclic convolutions
• An efficient algorithm for cyclic convolution based on fast-polynomial and fast-W transforms
• A novel modularized fast polynomial transform algorithm for two- dimensional convolutions
• scientific article; zbMATH DE number 5026599
• scientific article; zbMATH DE number 123830

Cites work

• An improved FPT algorithm for computing two-dimensional cyclic convolutions
• Fast polynomial transform algorithms for digital convolution
• scientific article; zbMATH DE number 3928865 (Why is no real title available?)
• scientific article; zbMATH DE number 3967542 (Why is no real title available?)
• scientific article; zbMATH DE number 3523640 (Why is no real title available?)
• scientific article; zbMATH DE number 3392542 (Why is no real title available?)

Cited in

(4)

• Fast polynominal transforms for two-dimensional convolution
• An improved FPT algorithm for computing two-dimensional cyclic convolutions
• Using quadratic residue arithmetic for computing skew cyclic convolutions
• scientific article; zbMATH DE number 123830 (Why is no real title available?)

This page was built for publication: Improved fast polynomial transform algorithm for cyclic convolutions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1902509)