OurBigBook.comSite Source code

Even--odd fast Fourier transform recursion

For

ω_{m} = e^{- 2 πi / m}

and length-

m /2

transforms

E_{k}, O_{k}

of the even and odd samples,

Y_{k} = E_{k} + ω_{m}^{k} O_{k}, Y_{k + m /2} = E_{k} - ω_{m}^{k} O_{k} .

 Ancestors (7)