URL
https://opencores.org/ocsvn/dblclockfft/dblclockfft/trunk
Subversion Repositories dblclockfft
[/] [dblclockfft/] [trunk/] [doc/] [src/] [spec.tex] - Rev 42
Compare with Previous | Blame | View Log
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% Filename: doc/src/spec.tex
%%
%% Project: A General Purpose Pipelined FFT Implementation
%%
%% Purpose: This file contains the LaTeX instructions necessary to build
%% the doc/spec.pdf file. It's not nearly as interesting as the
%% doc/spec.pdf file itself, so I would recommend you read that file
%% before looking for items within here.
%%
%% Creator: Dan Gisselquist, Ph.D.
%% Gisselquist Technology, LLC
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% Copyright (C) 2018, Gisselquist Technology, LLC
%%
%% This file is part of the general purpose pipelined FFT project.
%%
%% The pipelined FFT project is free software (firmware): you can redistribute
%% it and/or modify it under the terms of the GNU Lesser General Public License
%% as published by the Free Software Foundation, either version 3 of the
%% License, or (at your option) any later version.
%%
%% The pipelined FFT project 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 Lesser
%% General Public License for more details.
%%
%% You should have received a copy of the GNU Lesser General Public License
%% along with this program. (It's in the $(ROOT)/doc directory. Run make
%% with no target there if the PDF file isn't present.) If not, see
%% <http://www.gnu.org/licenses/> for a copy.
%%
%% License: LGPL, v3, as defined and found on www.gnu.org,
%% http://www.gnu.org/licenses/lgpl.html
%%
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%%
\documentclass{gqtekspec}
\project{Pipelined FFT}
\title{Specification}
\author{Dan Gisselquist, Ph.D.}
\email{dgisselq (at) opencores.org}
\revision{Rev.~0.3}
\begin{document}
\pagestyle{gqtekspecplain}
\titlepage
\begin{license}
Copyright (C) \theyear\today, Gisselquist Technology, LLC
This file is part of the general purpose pipelined FFT project.
The pipelined FFT project is free software (firmware): you can redistribute
it and/or modify it under the terms of the GNU Lesser General Public License
as published by the Free Software Foundation, either version 3 of the
License, or (at your option) any later version.
The pipelined FFT project 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 Lesser
General Public License for more details.
You should have received a copy of the GNU Lesser General Public License along
with this project. If not, see \texttt{http://www.gnu.org/licenses/} for a
copy.
\end{license}
\begin{revisionhistory}
0.3 & 6/2/2015 & Gisselquist & General purpose pipelined FFT generator\\\hline
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 came about originally from my attempts to design and implement a
GPS decorrelation
algorithm inside a generic FPGA, but only on a limited budget. As such,
it was built before I had the board that could use it. Because I was trying
to hit a very high processing rate, the FFT core was originally built to handle
two samples at a time. Hence the original name, the ``Double clocked FFT
core''.
One of the difficulties of doing all of your development using Verilator as
a simulator, is that you can only simulate components that you have the
Verilog source for. My desire to use Verilator kept me from using any of
the vendor supplied FFTs out there.
This, then, was and is the genesis of this project.
Since this genesis, I've used this core as part of several other designs and
maintaied it. Eventually it has morphed into the general purpose FFT core
generator that it is today.
\end{preface}
\chapter{Introduction}
\pagenumbering{arabic}
\setcounter{page}{1}
The General Purpose Pipelined FFT generator project contains all of the
software necessary to create an arbitrary sized FFT HDL core that will
accept up to two samples per clock cycle, and after some pipeline delay
it will output FFT results at the same rate they are input.
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. Finally, the FFT can be configured to process two
samples per clock, one sample per clock, one sample every other clock, or even
one sample every third clock (or less).
These features make this general purpose pipelined FFT generator 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++. (While I
do my development on Ubuntu, I am told by others that the core builds on
Microsoft systems as well.) 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 an 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 output directory, {\tt ./fft-core/} by default, 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.
Given an input $x\left[n\right]$, the FFT will calculate,
\begin{eqnarray*}
X\left[k\right] &=& \sum_{n=0}^{N-1} x\left[n\right]
e^{-j2\pi \frac{k}{N}n}
\end{eqnarray*}
to within a scale factor.
\item[\hbox{-i}]
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*}
If no {\tt -i} option is given, the core will by default generate a
forward FFT.
\item[\hbox{-2}]
Builds an FFT that can ingest and output two samples per clock.
This option requires six multiplies for all but the last two butterfly
stages. The last two butterfly stages are accomplished using shifts
and adds only, so they require no multiplies.
\item[\hbox{-k 1}]
Builds an FFT that can ingest and output one sample per clock.
This option is incompatible with {\tt -2}.
This option requires three multiplies for all but the last two
butterfly stages.
\item[\hbox{-k 2}]
Builds an FFT that can ingest and output one sample every other clock.
This option is incompatible with {\tt -2}, and will override {\tt -k 1}.
You are responsible for making sure that {\tt i\_ce} will never be
true for two clocks in a row.
Unlike {\tt -k 1}, this option only requires two multiplies for all
but the last two butterfly stages.
\item[\hbox{-k 3}]
Builds an FFT that can ingest and output one sample every third clock.
This option is incompatible with {\tt -2}, and will override any
other {\tt -k} option.
For this to work, you will need to guarantee that {\tt i\_ce} will
never be true more than one time in any three clock periods.
Unlike {\tt -k 1} and {\tt -k 2}, this option only requires one
multiply for all but the last two butterfly stages.
\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, this capability is really just a placeholder for
a future capability.
\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}] Specifies the number of extra bits to be given to each
twiddle factor. The size of the twiddle factors is nominally the size
of the input data. By specifying {\tt -c <bits>}, you can extend
this default value to avoid any loss in precision.
\item[\hbox{-x bits}] Maintains {\tt bits} extra bits during the computation
to deal with roundoff error. Hence, after the first stage, there will
be this many excess bits within the FFT pipeline.
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-one}
\begin{figure}\begin{center}
\begin{pspicture}(-2.2in,0.3in)(2.2in,2in)
% \rput(0,0){\psframe(-2.2in,0.3in)(2.2in,2in)}
\rput(0,0){\rput(0,0){\psframe[linewidth=2\pslinewidth](-0.75in,0.3in)(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\_sample}
\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[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\_result}
\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$}}
}
\end{pspicture}
\caption{(I)FFT Black Box Diagram}\label{fig:black-box-one}
\end{center}\end{figure}
for the two traditional one sample per clock FFT implementation, or
Fig.~\ref{fig:black-box-dbl}
\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{Two sample per clock (I)FFT Black Box Diagram}\label{fig:black-box-dbl}
\end{center}\end{figure}
for the two samples per clock FFT.
The interface
is simple: strobe the reset line, and every clock thereafter set the clock
enable line when data is valid on the input port. 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-dbl}
\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-dbl}
\end{center}\end{figure}
attempts to show some of this structure for the two-sample per clock FFT.
As you can see from the figure, the
FFT itself is composed of a series of stages. For the two-sample per clock
FFT, 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/4$, 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\_sample}
\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 radix-2 FFT implementation, save only that for the two-sample per
clock FFT the coefficients are alternated between the two inputs
shown in Fig.~\ref{fig:white-box-dbl}. That is, the even stages would get all
the even coefficients, and the odd stages get all of the odd coefficients.
For the more general purpose FFT, there's only the one pipeline, so every
sample goes through every butterfly.
Internally, each stage spends the first $N/2$ clocks storing its inputs
into memory, and then the next $N/2$ clocks pairing a stored input with
a single (fresh) 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
two bits 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/2$ 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/2$ 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, {\tt i\_sample}, or the
first sample pair, {\tt i\_left} and {\tt i\_right} for the
two sample-per-clock FFT, set {\tt i\_ce} high.
If you have elected an FFT that multiplexes its multiplies,
and so can only handle one sample every two or three clocks,
then you'll need to guarantee {\tt i\_ce} remains low for
one or two clocks respectively before raising it again.
\item Ever after, any time a valid sample is placed in {\tt i\_sample}
and {\tt i\_ce} raised high, a sample will enter into the
FFT for processing. For the two sample-per-clock FFT, the
input will be into {\tt i\_left} (for the first input)
and {\tt i\_right} (for the next one).
\item At the first valid output, the FFT core will set {\tt o\_sync}
line high in addition to placing the output value into
{\tt o\_result}. For the two-sample per clock FFT, the outputs
will be placed into {\tt o\_left}
(the first of two), and {\tt o\_right} (the second of the two)
respectively.
\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\_sample & $2N_i$ & Input & The complex input sample. 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\_left & $2N_i$ & Input & When the core is configured for two-samples per
clock,
this is the first of the two data inputs presented to the core
on any given clock. It has the same format as {\tt i\_sample}
above.
\\\hline
i\_right & $2N_i$ & Input & The second of two input complex input samples,
used when the core is configured for two-samples per clock.
The format is the same as {\tt i\_sample} above.\\\hline
o\_sync & 1 & Output & Signals the first output sample of any transform.
It will be zero from the time of the reset until the first
output sample. Ever afterwards, it will be true any time
bin zero of the FFT is on the output.\\\hline
o\_result & $2N_o$ & Output & The complex output sample. The format is the
same, save only that $N_o$ bits are used for each twos
complement portion instead of $N_i$. Hence bits
[$\left(2N_o-1\right)$:$N_o$] of this value are the real
portion, whereas bits [$\left(N_o-1\right)$:0] represent the
imaginary portion.
\\\hline
o\_left & $2N_o$ & Output & When in the two-sample per clock configuration,
this is the first of two complex output samples.\\\hline
o\_right & $2N_o$ & Output & When in the two-sample per clcok configuration,
this is the second of two complex output samples. \\\hline
\\\hline
\end{portlist}
\caption{List of IO ports}\label{tbl:ioports}
\end{center}\end{table}
% Appendices
% Index
\end{document}