Subversion Repositories dblclockfft

\documentclass{gqtekspec}
\project{Double Clocked FFT}
\title{Specification}
\author{Dan Gisselquist, Ph.D.}
\email{dgisselq\at opencores.org}
\revision{Rev.~0.2}
\begin{document}
\pagestyle{gqtekspecplain}
\titlepage
\begin{license}
Copyright (C) \theyear\today, Gisselquist Technology, LLC
 
This project is free software (firmware): you can redistribute it and/or
modify it under the terms of  the GNU General Public License as published
by the Free Software Foundation, either version 3 of the License, or (at
your option) any later version.
 
This program is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTIBILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.
 
You should have received a copy of the GNU General Public License along
with this program.  If not, see \hbox{<http://www.gnu.org/licenses/>} for a copy.
\end{license}
\begin{revisionhistory}
0.2 & 6/2/2015 & Gisselquist & Superficial formatting changes\\\hline
0.1 & 3/3/2015 & Gisselquist & First Draft \\\hline
\end{revisionhistory}
% Revision History
% Table of Contents, named Contents
\tableofcontents
\listoffigures
\listoftables
\begin{preface}
This FFT comes from my attempts to design and implement a signal processing
algorithm inside a generic FPGA, but only on a limited budget.  As such,
I don't yet have the FPGA board I wish to place this algorithm onto, neither
do I have any expensive modeling or simulation capabilities.  I'm using
Verilator for my modeling and simulation needs.  This makes
using a vendor supplied IP core, such as an FFT, difficult if not impossible
to use.
 
My problem was made worse when I learned that the published maximum clock
speed for a device wasn't necessarily the maximum clock speed that I could
achieve.  My design needed to process the incoming signal at 500~MHz to be
commercially viable.  500~MHz is not necessarily a clock speed
that can be easily achieved.  250~MHz, on the other hand, is much more within
the realm of possibility.  Achieving a 500~MHz performance with a 250~MHz
clock, however, requires an FFT that accepts two samples per clock.
 
This, then, was and is the genesis of this project.
\end{preface}
 
\chapter{Introduction}
\pagenumbering{arabic}
\setcounter{page}{1}
 
The Double Clocked FFT project contains all of the software necessary to
create the IP to generate an arbitrary sized FFT that will clock two samples
in at each clock cycle, and after some pipeline delay it will clock two
samples out at every clock cycle.
 
The FFT generated by this approach is very configurable.  By simple adjustment
of a command line parameter, the FFT may be made to be a forward FFT or an
inverse FFT.  The number of bits processed, kept, and maintained by this
FFT are also configurable.  Even the number of bits used for the twiddle
factors, or whether or not to bit reverse the outputs, are all configurable
parts to this FFT core.
 
These features make the Double Clocked FFT very different and unique among the
other cores available on opencores.com.
 
For those who wish to get started right away, please download the package,
change into the {\tt sw} directory and run {\tt make}.  There is no need to
run a configure script, {\tt fftgen} is completely portable C++.  Then, once
built, go ahead and run {\tt fftgen} without any arguments.  This will cause
{\tt fftgen} to print a usage statement to the screen.  Review the usage
statement, and run {\tt fftgen} a second time with the arguments you need.
 
 
\chapter{Generation}
 
Creating a double clocked FFT core is as simple as running the program
{\tt fftgen}.  The program will then create a series of Verilog files, as
well as {\tt .hex} files suitable for use with a \textdollar readmemh, and
place them into an {\tt ./fft-core/} directory that {\tt fftgen} will create.
Creating the core you want takes a touch of configuring.
Therefore, the following lists the arguments that can be given to 
{\tt fftgen} to adjust the core that it builds:
\begin{itemize}
\item[\hbox{-f size}]
	This specifies the size of the FFT core that {\tt fftgen} will build.
	The size must be a power of two.  The transform is given, within a
	scale factor, to,
	\begin{eqnarray*}
	X\left[k\right] &=& \sum_{n=0}^{N-1} x\left[n\right]
		e^{-j2\pi \frac{k}{N}n}
	\end{eqnarray*}
 
\item[\hbox{-1}]
	This specifies that the FFT will be an inverse FFT.  Specifically,
	it will calculate,
	\begin{eqnarray*}
	x\left[n\right] &=& \sum_{k=0}^{N-1} X\left[k\right] e^{j2\pi \frac{k}{N}n}
	\end{eqnarray*}
\item[\hbox{-0}]
	This specifies building a forward FFT.  However, since this is the
	default, this option never necessary.
\item[\hbox{-s}]
	This causes the core to skip the final bit reversal stage.  The 
	outputs of the FFT will then come out in bit reversed order.
 
	This option is useful in those cases where someone wishes to 
	multiply the coefficients coming out of an FFT by some product,
	and then to inverse FFT the results.  If the coefficients are also
	applied in bit--reversed order, then both the FFT and IFFT may
	skip their bit reversals.
 
	Be aware, however, doing this requires the bit reversed forward
	transform be followed by a bitreversed decimation in time approach
	to the inverse transform.  This software does not (yet) provide that
	capability.  As such, the utility just isn't there yet.
\item[\hbox{-S}]
	Include the final bit reversal stage.  As this is also the default,
	specifying the option should not be necessary.
\item[\hbox{-d DIR}]
	Specifies the DIRectory to place the produced Verilog files.  By
	default, this will be in the `./fft-core/' directory, but it can
	be moved to any other directory as necessary.
\item[\hbox{-n bits}] Sets the number of input bits per sample.  Given this
	setting, each of the two samples clocked in at every clock cycle
	will have this many bits for their real portion, and again this many
	bits for their imaginary portion.  Thus, the data input to the
	FFT will be four times this many bits per clock.
\item[\hbox{-m bits}] This sets the maximum bit width of the output.
	By default, the FFT will gain bits as they accumulate within
	the FFT.  Bits are accumulated at roughly one bit for every two stages.
	However, if this value is set, bits are only accumulated up to this
	maximum width.  After this width, further accumulations are truncated.
\item[\hbox{-c bits}] The number of bits in each twiddle coefficient is given
	by the number of bits input to that stage plus this extra number of
	bits per coefficient.  By increasing the number of bits per coefficient
	above that of the input samples, truncation error is kept to the
	original error found within the original samples.
\item[\hbox{-x bits}] Internally accumulated roundoff error can be a difficult
	problem to solve.  By using this option, you guarantee that the FFT
	runs with an additional {\tt bits} bits, and only truncates down to
	the necessary width at the end in order to minimize rounding
	errors along the way.
\item[\hbox{-p nmpy}] This sets the number of hardware multiplies that the FFT
	will consume.  By default, the FFT does not use any hardware multiplies.
	However, this can be expensive on the rest of the logic used by the
	device.  You can avoid this problem by allowing the FFT to use
	hardware multiplies using this option.  By default, the multiplies will
	be used in the latter stages, so that they will be applied where
	the bit width is the greatest.
\end{itemize}
 
\chapter{Architecture}
 
As a component of another system the structure of this system is a simple
black box such as the one shown in Fig.~\ref{fig:black-box}. 
\begin{figure}\begin{center}
\begin{pspicture}(-2.1in,0)(2.1in,2in)
% \rput(0,0){\psframe(-2.1in,0)(2.1in,2in)}
\rput(0,0){\rput(0,0){\psframe[linewidth=2\pslinewidth](-0.75in,0)(0.75in,2in)}
	\rput(0,1in){(I)FFT Core}
	\rput[r](-1.6in,1.8in){\tt i\_clk}
		\rput(-1.5in,1.8in){\psline{->}(0,0)(0.7in,0)}
	\rput[r](-1.6in,1.5in){\tt i\_rst}
		\rput(-1.5in,1.5in){\psline{->}(0,0)(0.7in,0)}
	\rput[r](-1.6in,1.2in){\tt i\_ce}
		\rput(-1.5in,1.2in){\psline{->}(0,0)(0.7in,0)}
	\rput[r](-1.6in,0.6in){\tt i\_left}
		\rput(-1.5in,0.6in){\psline{->}(0,0)(0.7in,0)}
		\rput(-1.15in,0.6in){\psline(-0.05in,-0.05in)(0.05in,0.05in)}
		\rput[br](-1.2in,0.6in){\scalebox{0.75}{$2N_i$}}
	\rput[r](-1.6in,0.3in){\tt i\_right}
		\rput(-1.5in,0.3in){\psline{->}(0,0)(0.7in,0)}
		\rput(-1.15in,0.3in){\psline(-0.05in,-0.05in)(0.05in,0.05in)}
		\rput[br](-1.2in,0.3in){\scalebox{0.75}{$2N_i$}}
	%
	\rput[l](1.6in,1.2in){\tt o\_sync}
		\rput(0.8in,1.2in){\psline{->}(0,0)(0.7in,0)}
	\rput[l](1.6in,0.6in){\tt o\_left}
		\rput(0.8in,0.6in){\psline{->}(0,0)(0.7in,0)}
		\rput(1.15in,0.6in){\psline(-0.05in,-0.05in)(0.05in,0.05in)}
		\rput[br](1.1in,0.6in){\scalebox{0.75}{$2N_o$}}
	\rput[l](1.6in,0.3in){\tt o\_right}
		\rput(0.8in,0.3in){\psline{->}(0,0)(0.7in,0)}
		\rput(1.15in,0.3in){\psline(-0.05in,-0.05in)(0.05in,0.05in)}
		\rput[br](1.1in,0.3in){\scalebox{0.75}{$2N_o$}}
	}
\end{pspicture}
\caption{(I)FFT Black Box Diagram}\label{fig:black-box}
\end{center}\end{figure}
The interface
is simple: strobe the reset line, and every clock thereafter set the clock
enable line when data is valid on the left and right input ports.  Likewise
for the outputs, when the {\tt o\_sync} line goes high the first data sample
is available.  Ever after that, one data sample will be available every clock
cycle that the {\tt i\_ce} line is high.
 
Internal to the FFT, things are a touch more complex.  Fig.~\ref{fig:white-box}
\begin{figure}\begin{center}
\begin{pspicture}(1.3in,-0.5in)(4.7in,5in)
	% \rput(0,0){\psframe(0,-0.5in)(\textwidth,5.25in)}
	\rput(0,0){\psframe[linewidth=2\pslinewidth](1.3in,-0.25in)(4.7in,5in)}
	\rput(0,5in){%
		\rput[r](1.95in,0.125in){\tiny\tt i\_left}
		\rput[l](4.05in,0.125in){\tiny\tt i\_right}
		\rput(2.0in,0){\psline{->}(0,0.25in)(0,0.0in)}
		\rput(4.0in,0){\psline{->}(0,0.25in)(0,0.0in)}
	}
	\rput(2in,0){%
		\rput(0,4.25in){\psframe(-0.5in,0)(0.5in,0.5in)%
			\rput[r](-0.05in,0.675in){\tiny Left}
			\rput(0.0in,0){\psline{->}(0,0.75in)(0,0.5in)}
			\rput(0,0.25in){Evens, $N$}
			\rput[r](-0.35in,-0.125in){\tiny Sync}
			\rput[l](0.35in,-0.125in){\tiny Data}
			\rput(-0.3in,0){\psline{->}(0,0)(0,-0.25in)}
			\rput(0.3in,0){\psline{->}(0,0)(0,-0.25in)}}
		\rput(0,3.5in){\psframe(-0.5in,0)(0.5in,0.5in)%
			\rput(0,0.25in){Evens, $N/2$}
			\rput[r](-0.35in,-0.125in){\tiny Sync}
			\rput[l](0.35in,-0.125in){\tiny Data}
			\rput(-0.3in,0){\psline{->}(0,0)(0,-0.25in)}
			\rput( 0.3in,0){\psline{->}(0,0)(0,-0.25in)}}
		% \rput(0,3in){\psframe(-0.5in,0)(0.5in,0.5in)%
			% \rput(0,0.25in){Evens, $N$}}
		\rput(0,2.25in){\psframe(-0.5in,0)(0.5in,0.5in)%
			\rput(0,0.25in){Evens, $8$}
			\rput[r](-0.35in,-0.125in){\tiny Sync}
			\rput[l](0.35in,-0.125in){\tiny Data}
			\rput[r](-0.35in,0.675in){\tiny Sync}
			\rput[l](0.35in,0.675in){\tiny Data}
			\rput(-0.3in,0.9in){$\vdots$}
			\rput( 0.3in,0.9in){$\vdots$}
			\rput(-0.3in,0.75in){\psline{->}(0,0)(0,-0.25in)}
			\rput( 0.3in,0.75in){\psline{->}(0,0)(0,-0.25in)}
			\rput(-0.3in,0){\psline{->}(0,0)(0,-0.25in)}
			\rput(0.3in,0){\psline{->}(0,0)(0,-0.25in)}}
		\rput(0,1.5in){\psframe(-0.5in,0)(0.5in,0.5in)%
			\rput(0,0.25in){Qtrstage (Even)}
			\rput[r](-0.35in,-0.125in){\tiny Sync}
			\rput[lb](0.6in,-0.10in){\tiny Data}
			\rput(-0.3in,0){\psline{->}(0,0)(0,-0.5in)(0.8in,-0.5in)}
			\rput(0.3in,0){\psline{->}(0,0)(0,-0.125in)(0.4in,-0.125in)(0.4in,-0.25in)}}
		% \rput(0,0.75in){\psframe(-0.5in,0)(0.5in,0.5in)%
			% \rput(0,0.25in){dblstage}}
		% \rput(0,0in){\psframe(-0.5in,0)(0.5in,0.5in)%
			% \rput(0,0.25in){Bit Reversal}}
	}
	\rput(4in,0){%
		\rput(0,4.25in){\psframe(-0.5in,0)(0.5in,0.5in)%
			\rput[l](0.05in,0.675in){\tiny Right}
			\rput(0.0in,0){\psline{->}(0,0.75in)(0,0.5in)}
			\rput(0,0.25in){Odds, $N$}
			\rput[l](0.35in,-0.125in){\tiny Sync}
			\rput[r](-0.35in,-0.125in){\tiny Data}
			\rput(-0.3in,0){\psline{->}(0,0)(0,-0.25in)}
			\rput(0.3in,0){\psline{->}(0,0)(0,-0.25in)}}
		\rput(0,3.5in){\psframe(-0.5in,0)(0.5in,0.5in)%
			\rput(0,0.25in){Odds, $N/2$}
			\rput[l](0.35in,-0.125in){\tiny Sync}
			\rput[r](-0.35in,-0.125in){\tiny Data}
			\rput(-0.3in,0){\psline{->}(0,0)(0,-0.25in)}
			\rput(0.3in,0){\psline{->}(0,0)(0,-0.25in)}}
		% \rput(0,3in){\psframe(-0.5in,0)(0.5in,0.5in)%
			% \rput(0,0.25in){Evens, $N$}}
		\rput(0,2.25in){\psframe(-0.5in,0)(0.5in,0.5in)%
			\rput(0,0.25in){Odds, $8$}
			\rput[l](0.35in,0.675in){\tiny Sync}
			\rput[r](-0.35in,0.675in){\tiny Data}
			\rput(-0.3in,0.9in){$\vdots$}
			\rput( 0.3in,0.9in){$\vdots$}
			\rput[l](0.35in,-0.125in){\tiny Sync}
			\rput[r](-0.35in,-0.125in){\tiny Data}
			\rput(-0.3in,0.75in){\psline{->}(0,0)(0,-0.25in)}
			\rput(0.3in,0.75in){\psline{->}(0,0)(0,-0.25in)}
			\rput(-0.3in,0){\psline{->}(0,0)(0,-0.25in)}
			\rput(0.3in,0){\psline{->}(0,0)(0,-0.25in)}}
		\rput(0,1.5in){\psframe(-0.5in,0)(0.5in,0.5in)%
			\rput(0,0.25in){Qtrstage (Odd)}
			\rput[rb](-0.6in,-0.10in){\tiny Data}
			\rput(0.3in,0){\psline{->}(0,0)(0,-0.25in)}
				\rput[t](0.3in,-0.3in){\tiny NC}
			\rput(-0.3in,0){\psline{->}(0,0)(0,-0.125in)(-0.4in,-0.125in)(-0.4in,-0.25in)}
			}
	}
	\rput(3in,0.75in){\psframe(-0.5in,0)(0.5in,0.5in)%
		\rput(0,0.25in){Double Stage}
			\rput[r](-0.35in,-0.125in){\tiny Sync}
			\rput[l](0.35in,-0.125in){\tiny Right}
			\rput[r](0.15in,-0.125in){\tiny Left}
		\rput(-0.3in,0){\psline{->}(0,0)(0,-0.25in)}
		\rput(0.2in,0){\psline{->}(0,0)(0,-0.25in)}
		\rput(0.3in,0){\psline{->}(0,0)(0,-0.25in)}}
	\rput(3in,0in){\psframe(-0.5in,0)(0.5in,0.5in)%
		\rput(0,0.25in){Bit Reversal}
			\rput[r](-0.35in,-0.125in){\tiny Sync}
			\rput[l](0.35in,-0.125in){\tiny Right}
			\rput[r](0.15in,-0.125in){\tiny Left}
		\rput(-0.3in,0){\psline{->}(0,0)(0,-0.25in)}
		\rput(0.2in,0){\psline{->}(0,0)(0,-0.25in)}
		\rput(0.3in,0){\psline{->}(0,0)(0,-0.25in)}}
	\rput(3in,-0.25in){\rput[r](-0.35in,-0.125in){\tiny\tt o\_sync}
			\rput[l](0.35in,-0.125in){\tiny\tt o\_right}
			\rput[r](0.15in,-0.125in){\tiny\tt o\_left}
		\rput(-0.3in,0){\psline{->}(0,0)(0,-0.25in)}
		\rput(0.2in,0){\psline{->}(0,0)(0,-0.25in)}
		\rput(0.3in,0){\psline{->}(0,0)(0,-0.25in)}}
\end{pspicture}
\caption{Internal FFT Structure}\label{fig:white-box}
\end{center}\end{figure}
attempts to show some of this structure.  As you can see from the figure, the
FFT itself is composed of a series of stages.  These stages are split from the
beginning into an even stage and an odd stage.  Further, they are numbered
according to the size of the FFT they represent.  Therefore the first stage
is numbered $N$ and represents the first stage of an $N$ point FFT.  The
second stage is labeled $N/2$, then $N/$, and so on down to $N=8$.  The
four sample stage and the two sample stages are different, however.  These
two stages, representing three blocks on Fig.~\ref{fig:white-box}, can be
accomplished without any multiplies.  Therefore they have been accomplished
separately.  Likewise all of the stages, save the double stage at the bottom,
operate on one data sample per clock.  Only the last stage, prior to the
bit reversal stage, takes two data samples per clock as input, and outputs two 
data samples per clock.  Finally, the bit reversal stage acts as the last
piece of the structure.
 
Internal to each of the FFT stages is a butterfly and a complex multiply,
as shown in Fig.~\ref{fig:fftstage}. 
\begin{figure}\begin{center}
\begin{pspicture}(-0.25in,-1.8in)(3.25in,4.25in)
	% \rput(0,0){\psframe(0in,-2in)(3in,4.25in)}
	\rput(0,0){\psframe[linewidth=2\pslinewidth](-0.25in,-1.55in)(3.25in,4.0in)}
	\rput[r](1.625in,4.125in){\tt i\_data}
	\rput(1.675in,3.75in){\psline{->}(0,0.5in)(0,0in)%
			\psline{->}(0,0)(-0.2in,-0.25in)%
			\psarc{->}{0.15in}{200}{340}}
	\rput(0,2.75in){\rput(0,0){\psframe(0,0)(1.3in,0.25in)}
			\rput(0,0){\psframe(0.1in,0)(0.2in,0.25in)}
			\rput(0,0){\psframe(0.3in,0)(0.4in,0.25in)}
			\rput(0,0){\psframe(0.5in,0)(0.6in,0.25in)}
			\rput(0,0){\psframe(0.7in,0)(0.8in,0.25in)}
			\rput(0,0){\psframe(0.9in,0)(1.0in,0.25in)}
			\rput(0,0){\psframe(1.1in,0)(1.2in,0.25in)}
			\rput(0,0){\psline{-}(0.7in,-0.05in)(1.1in,-0.25in)}
			\rput(0,0){\psline{<-}(0.7in,0.3in)(1.5in,0.5in)(1.5in,0.75in)}}
	\rput(1.85in,2.75in){\psline(0,0.75in)(0,-0.25in)}
	\rput(0.6in,0.25in){\rput(0,0){\psframe[linewidth=2\pslinewidth](0,0)(2in,2.0in)}
		\rput(0.50in,2in){\psline{->}(0,0.25in)(0,0in)}
		\rput(1.25in,2in){\psline{->}(0,0.25in)(0,0in)}
		\rput(1.75in,2in){\psline{->}(0,0.25in)(0,0in)}
		\rput(0.5in,0){%
			\rput(0in,0){\psline{->}(0,2.0in)(0,1.1in)}
			\rput(0in,0){\psline{->}(0,1.75in)(0.65in,1.1in)}
			\rput(-0.1in,1.1in){$+$}
			\rput(0in,1.0in){$\bigoplus$}
			\rput(0in,0){\psline{->}(0,0.9in)(0,0.75in)}
			\rput(0in,0.5in){\psframe(-0.45in,-0.25in)(0.45in,0.25in)}
			\rput(0in,0.5in){\parbox{0.8in}{Delay, and\\shift by $C-2$}}
			\rput(0in,0){\psline{->}(0,0.25in)(0,0.0in)}}
		\rput(1.25in,0){%
			\rput(0in,0){\psline{->}(0,2.0in)(0,1.1in)}
			\rput(0in,0){\psline{->}(0,1.75in)(-0.65in,1.1in)}
			\rput(0.1in,1.1in){$-$}
			\rput(0in,1in){$\bigoplus$}
			\rput(0in,0){\psline{->}(0,0.9in)(0,0.6in)}
			\rput(0in,0.5in){$\bigotimes$}
			\rput(0in,0){\psline{->}(0,0.4in)(0,0.0in)}}
		\rput(1.75in,0){%
			\rput(0,0){\psline{->}(0,2.0in)(0,0.5in)(-0.4in,0.5in)}}
		\rput(0.50in,-0.25in){\psline{->}(0,0.25in)(0,-1.05in)}
		\rput(1.25in,-0.25in){\psline{-}(0,0.25in)(0,0in)}}
	\rput*[l](2.0in,0.5in){DIF Butterfly}
	\rput*[lb](1.95in,2.5in){Coefficient memory}
	% \rput(0,0){\psframe(1.3in,-0.25in)(4.7in,5in)}
	\rput(1.7in,-0.5in){\rput(0,0){\psframe(0,0)(1.3in,0.25in)}
			\rput(0,0){\psframe(0.1in,0)(0.2in,0.25in)}
			\rput(0,0){\psframe(0.3in,0)(0.4in,0.25in)}
			\rput(0,0){\psframe(0.5in,0)(0.6in,0.25in)}
			\rput(0,0){\psframe(0.7in,0)(0.8in,0.25in)}
			\rput(0,0){\psframe(0.9in,0)(1.0in,0.25in)}
			\rput(0,0){\psframe(1.1in,0)(1.2in,0.25in)}
			\rput(0,0){\psline{<-}(0.7in,0.30in)(0.15in,0.5in)}
			\rput(0,0){\psline{->}(0.7in,-0.05in)(-0.2in,-0.3in)(-0.2in,-0.55in)}}
	\rput(1.3in,-1.3in){\psline{->}(-0.2in,0.25in)(0,0)}
	\rput(1.3in,-1.3in){\psarcn{->}{0.15in}{150}{30}}
	\rput(1.3in,-1.3in){\psline{->}(0,0)(0,-0.5in)}
	\rput[l](1.35in,-1.675in){\tt o\_data}
\end{pspicture}
\caption{A Single FFT Stage, with Butterfly}\label{fig:fftstage}
\end{center}\end{figure}
These FFT stages are really no different than any other decimation in 
frequency FFT, save only that the coefficients are alternated between the
two stages.  That is, the even stages get all the even coefficients, and
the odd stages get all of the odd coefficients.
Internally, each stage spends the first $N/4$ clocks storing its inputs
into memory, and then the next $N/4$ clocks pairing a stored input with
a single external input, so that both values become inputs to the butterfly.
Likewise, the butterfly coefficient is read from a small ROM table.
 
One trick to making the FFT stage work successfully is synchronization.  Since
the shift and add multiplies create a delay of (roughly) one clock cycle per
bit of input, there is a significant pipeline delay from the input to the
output of the butterfly routine.  To match this delay, the FFT stage places a 
synchronization pulse into the butterfly.  When this synchronization pulse
comes out of the butterfly, the values of the butterfly then match the
first sample out of the stage.  The next synchronization problem comes from
the fact that the butterflies operate on two samples at a time, whereas the
FFT stage operates on a single sample at a time.  This means that half the
time the butterfly output will be invalid.  To keep things aligned, and to 
avoid the invalid data half, a counter is started by the synchronization pulse
coming out of the butterfly in order to keep track.  Using this counter and
once the butterfly produces the first sync pulse, the next $N/4$ clock cycles
will produce valid butterfly outputs.  For these clock cycles, the left or
first output is sent immediately to the next FFT stage, whereas the right
or second output is saved into memory.  Once these cycles are complete, the
butterfly outputs will be invalid for the next $N/4$ clock cycles.  During
these invalid clock cycles, the FFT stage outputs data that had been stored
in memory.  In this fashion, data is always valid coming out of each FFT
stage once the initial synchronization pulse goes high.
 
The complex multiply itself, formed internal to the butterfly routine, is
formed from three very simple shift and add multiplies, whose output is
then transformed into a single complex output, although there is a command
line option to use hardware multiplies instead.  To avoid overflow, the
complex coefficients, $z_n$, for these multiplies are given by,
\begin{eqnarray}
z_n &=& c_n + js_n,\mbox{ where} \\
c_n &=& \left\lfloor 2^{C-2}\cos\left(2\pi \frac{n}{N}\right)+\frac{1}{2}\right\rfloor,\\
s_n &=& \left\lfloor 2^{C-2}\sin\left(2\pi \frac{n}{N}\right)+\frac{1}{2}\right\rfloor\mbox{, and}
\end{eqnarray}
$C$ is the number of bits allocated to the coefficient.
 
For those wishing to understand this operation further and in more depth, I
would commend them to the literature on how a decimation in frequency FFT is
constructed.
 
\chapter{Operation}
 
The core is actually really easy to use:
\begin{enumerate}
	\item Provide a system clock to the core every clock cycle.
	\item Set the {\tt i\_rst} line high for at least one clock cycle
		before you intend to use the core.
	\item From the time of reset until the first sample pair is available
		on the IO ports, {\tt i\_rst} may be kept low, but the clock
		enable line {\tt i\_ce} must also be kept low.
	\item On the clock containing the first sample pair, {\tt i\_left}
		and {\tt i\_right}, set {\tt i\_ce} high.
	\item Ever after, any time a valid pair of samples is available to
		the input of the FFT, place the first sample of the pair
		on the {\tt i\_left} line, the second on the {\tt i\_right}
		line, and set {\tt i\_ce} high.
	\item At the first valid output, the FFT core will set {\tt o\_sync}
		line high in addition to the output values {\tt o\_left}
		(the first of two), and {\tt o\_right} (the second of the two).
	\item Ever after, whenever {\tt i\_ce} is high, the FFT core will clock
		two samples in and two samples out.  On any valid first
		pair of samples coming out of the transform,
		{\tt o\_sync} will be high.  Otherwise {\tt o\_sync} will
		remain low.
\end{enumerate}
 
There are no special modes or states associated with this core.  If you wish
it to stop or pause, just turn off {\tt i\_ce}.  If you wish to flush the
core, just send zeros into the core.
 
\chapter{Registers}
 
Once built, the FFT routine has no capability for runtime configuration
or reconfiguration.  Therefore, this implementation maintains no user
configurable or readable registers.
 
This is a great advantage in many ways, simply because it greatly simplifies
the interface over other cores that are available out there.
 
\chapter{Clocks}
 
The FFT routines built by this core use one clock only.  The speed of this
clock will depend upon the speed your hardware is capable of.  If your data
rate is slower than your clock speed, just hold off on the {\tt i\_ce}
line as necessary so that every clock with the {\tt i\_ce} line high is a 
valid sample.
 
\chapter{IO Ports}
 
The FFT core presents a small set of IO ports to its external interface.
These ports are listed in Table.~\ref{tbl:ioports}.
\begin{table}[htbp]
\begin{center}
\begin{portlist}
i\_clk & 1 & Input & The global clock driving the FFT. \\\hline
i\_rst & 1 & Input & An active high synchronous reset.\\\hline
i\_ce & 1 & Input & Clock Enable.  Set this high to clock data in and
		out.\\\hline
i\_left & $2N_i$ & Input & The first of two input complex input samples.  Bits
		[$\left(2N_i-1\right)$:$N_i$] of this value are the real
		portion, whereas bits [$\left(N_i-1\right)$:0] represent the
		imaginary portion.  Both portions are in signed twos complement
		integer format.  The number of bits, $N_i$, is configurable.
		\\\hline
i\_right & $2N_i$ & Input & The second of two input complex input samples.
		The format is the same as {\tt i\_left} above.\\\hline
o\_left & $2N_o$ & Output & The first of two input complex output samples.
		The format is the same, save only that $N_o$ bits are
		used for each twos complement portion instead of $N_i$.\\\hline
o\_right & $2N_o$ & Output & The second of two input complex output samples.
		The format is the same as for {\tt o\_left} above.\\\hline
o\_sync & 1 & Output & Signals the first output sample pair of any transform,
		zero otherwise.
		\\\hline
\end{portlist}
\caption{List of IO ports}\label{tbl:ioports}
\end{center}\end{table}
% Appendices
% Index
\end{document}