Elementary Number Theory and Rader's FFT | Zendy

Shlomo Engelberg | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Elementary Number Theory and Rader's FFT

Author(s) -

Shlomo Engelberg

Publication year - 2017

Publication title -

siam review

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 4.683

H-Index - 120

eISSN - 1095-7200

pISSN - 0036-1445

DOI - 10.1137/15m1044990

Subject(s) - fast fourier transform , split radix fft algorithm , prime factor fft algorithm , arithmetic , mathematics , rader's fft algorithm , discrete fourier transform (general) , number theory , multiplicative function , cooley–tukey fft algorithm , algorithm , discrete mathematics , combinatorics , fourier transform , fourier analysis , mathematical analysis , fractional fourier transform

This note provides a self-contained introduction to Rader's fast Fourier transform (FFT). We start by explaining the need for an additional type of FFT. The properties of the multiplicative group of the integers modulo a prime number are then developed and their relevance to the calculation of the discrete Fourier transform is explained. Rader's FFT is then derived, Rader's zero-padding technique is described, and the performance of the unpadded and the zero-padded approaches is examined.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research