Multiple radix fast Fourier transformation based on number theoretic transforms

DOI10.1016/0016-0032(91)90003-LMaRDI QIDQ757003zbMATH OpenOpenAlexFDO

Authors Brooks Lawrence, Robert J. Polge, Adhami, Reza R.

Publication date 1991

Published in Journal of the Franklin Institute (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0016-0032(91)90003-l

zbMATH Keywords

Chinese remainder theoremcyclic convolutionDiscrete Fourier transformmultiple radix fast Fourier transformationnumber theoretic transformsresidue arithmetic

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Numerical methods for discrete and fast Fourier transforms (65T50)

Review text

Discrete Fourier transform on a prime number of samples is computed by means of the multiple radix fast Fourier transformation based on number theoretic transforms. This proposal is efficient in the transformation of samples \(P=2^{k1}3^{k2}5^{k3}\) with arbitrary integers ki \((i=1,2,3)\).

Recommendations

• Fast Fourier transformation based on number theoretic transforms
• Fast Multipliers for Number Theoretic Transforms
• A polymorphic radix-n framework for fast Fourier transforms
• Very fast computation of the radix-2 discrete Fourier transform
• scientific article; zbMATH DE number 3932301
• The structure of vector radix fast Fourier transforms
• Calculation of radix-2 discrete multiresolution Fourier transform
• Split-radix generalized fast Fourier transform
• Integer fast Fourier transform
• scientific article; zbMATH DE number 3942981

Cites work

• Efficient Fast Fourier Transform Programs for Arbitary Factors with One Step Loop Unscrambling
• Fast Fourier transformation based on number theoretic transforms

Cited in

(9)

• Fast Fourier transformation based on number theoretic transforms
• Extendible look-up table of twiddle factors and radix-8 based fast Fourier transform
• Faster arithmetic for number-theoretic transforms
• Multiplierless implementation of rotators and FFTs
• scientific article; zbMATH DE number 4209552 (Why is no real title available?)
• scientific article; zbMATH DE number 3926792 (Why is no real title available?)
• scientific article; zbMATH DE number 3932301 (Why is no real title available?)
• Fast Radix 2, 3, 4, and 5 Kernels for Fast Fourier Transformations on Computers with Overlapping Multiply--Add Instructions
• New Recursive Fast Radix-2 Algorithm for the Modulated Complex Lapped Transform

This page was built for publication: Multiple radix fast Fourier transformation based on number theoretic transforms

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