Скачать или смотреть Math 139 040725 Finite Fourier Analysis; Fast Fourier Transform

Nth roots of unity under multiplication form an abelian group. Equivalence classes of Z mod N also form, under addition, an abelian group. The two are isomorphic; we also identify the functions on the two groups.

Inner product space V of functions on Z(N). Creation of an orthonormal basis for V using powers of the primitive N-th root of unity. Finite Fourier analysis: nth Fourier coefficient. Fourier inversion (basic property of ONB); Plancherel theorem (Parseval's theorem). (End of the boring stuff)

Fast Fourier Transform. Naive estimate: O(N^2). Statement of theorem. Notation: #(M) = least upper bound on number of operations needed to calculate the Fourier coefficients for any single function on Z(M). Key lemma relating #(2M) and #(M). To be continued.