Notes on FFT Implementation in Processig

Bill Liu

T HIS document briefly outlines the background and proceeds to describe the implementation of FFT algorithm.

I. Background

The Fast Fourier Transform and its inverse are commonly used for transforming signals into point-value forms to be pointwise multiplied and then converted back to polynomial coefficient form. FFT is used on periodicity and roots of unity (n^{th} root in the below equation) to enable computational saving.

ω_{n} = e^{2πi/n} = e^{2πid/dn} = ω_{n}  (1)

ω_{n}^{k} = e^{2πik/n} = e^{2πi(k mod n)/n}  (2)

ω_{n}^{n/2} = e^{πi} = −1  (3)

II. Implementation

The conclusion goes here.

Appendix A

Proof of the First Zonklar Equation Appendix one text goes here.

Appendix B

Appendix two text goes here.