\documentclass {IEEEtran}

%% \ifCLASSOPTIONcompsoc
%% % IEEE Computer Society needs nocompress option
%% % requires cite.sty v4.0 or later (November 2003)
%% \usepackage[nocompress]{cite}
%% \else
%% % normal IEEE
%% \usepackage{cite}
%% \fi

\usepackage{amsmath}
\usepackage{tikz}
\usepackage{algorithm2e}

\begin {document}

\title {Notes on FFT Implementation in Processig}

\author {Bill~Liu}

% The paper headers
%% \markboth{Journal of \LaTeX\ Class Files,~Vol.~14, No.~8, August~2015}%
%%          {Shell \MakeLowercase{\textit{et al.}}: Bare Demo of IEEEtran.cls for Computer Society Journals}

         \IEEEtitleabstractindextext{%
           \begin{abstract}
             This serves as a collection of notes and implementation details of FFT within the Processig Rust crate.
           \end{abstract}

           % Note that keywords are not normally used for peerreview papers.
           \begin{IEEEkeywords}
             FFT
         \end{IEEEkeywords}}
         
         % make the title area
         \maketitle

         \IEEEPARstart{T}{his} document briefly outlines the background and proceeds to describe the implementation of FFT algorithm.

         \section{Background}
         The Fast Fourier Transform and its inverse are commonly used for polynomial multiplication, where the signals are transformed into point-value forms to be pointwise multiplied and then converted back to polynomial coefficient form. The polynomial coefficent form and the point wise form are convertable due to unique transformation between the two using Lagrange interpolation. FFT speeds up the conversion by using periodicity and roots of unity ($n^{th}$ root in the below equation) to enable computational saving.

         \begin{equation}
           \omega_n = e^{2 \pi i/n} = e^{2 \pi id/dn} = \omega_{n}
         \end{equation}

         \begin{equation}
           \omega^k_n = e^{2 \pi ik/n} = e^{2 \pi i(k~mod~n) /n}
         \end{equation}

         \begin{equation}
           \omega^{n/2}_n = e^{\pi i} = -1
         \end{equation}

         
         
         %% \begin{algorithm}
         %%   \KwData{this text}
         %%   \KwResult{how to write algorithm with \LaTeX2e }
         %%   initialization\;
         %%   \While{not at end of this document}{
         %%     read current\;
         %%     \eIf{understand}{
         %%       go to next section\;
         %%       current section becomes this one\;
         %%     }{
         %%       go back to the beginning of current section\;
         %%     }
         %%   }
         %%   \caption{How to write algorithms}
         %% \end{algorithm}

         %% \begin{tikzpicture}
         %%   \draw (1,0) -- (0,0) -- (0,1);
         %% \end{tikzpicture}
         
         \section{Implementation}
         The conclusion goes here.

         \appendices
         \section{Proof of the First Zonklar Equation}
         Appendix one text goes here.

         % you can choose not to have a title for an appendix
         % if you want by leaving the argument blank
         \section{}
         Appendix two text goes here.

         %% \begin{thebibliography}{1}

         %% \bibitem{IEEEhowto:kopka}
         %%   H.~Kopka and P.~W. Daly, \emph{A Guide to \LaTeX}, 3rd~ed.\hskip 1em plus
         %%   0.5em minus 0.4em\relax Harlow, England: Addison-Wesley, 1999.

         %% \end{thebibliography}

\end {document}
