Subversion Repositories dblclockfft

/spec.pdf Cannot display: file marked as a binary type. svn:mime-type = application/octet-stream

/spec.pdf

spec.pdf Property changes : Added: svn:mime-type ## -0,0 +1 ## +application/octet-stream \ No newline at end of property Index: src/GT.eps =================================================================== --- src/GT.eps (nonexistent) +++ src/GT.eps (revision 10) @@ -0,0 +1,94 @@ +%!PS-Adobe-3.0 EPSF-3.0 +%%BoundingBox: 0 0 504 288 +%%Creator: Gisselquist Technology LLC +%%Title: Gisselquist Technology Logo +%%CreationDate: 11 Mar 2014 +%%EndComments +%%BeginProlog +/black { 0 setgray } def +/white { 1 setgray } def +/height { 288 } def +/lw { height 8 div } def +%%EndProlog +% %%Page: 1 + +false { % A bounding box + 0 setlinewidth + newpath + 0 0 moveto + 0 height lineto + 1.625 height mul lw add 0 rlineto + 0 height neg rlineto + closepath stroke +} if + +true { % The "G" + newpath + height 2 div 1.25 mul height moveto + height 2 div height 4 div sub height lineto + 0 height 3 4 div mul lineto + 0 height 4 div lineto + height 4 div 0 lineto + height 3 4 div mul 0 lineto + height height 4 div lineto + height height 2 div lineto + % + height lw sub height 2 div lineto + height lw sub height 4 div lw 2 div add lineto + height 3 4 div mul lw 2 div sub lw lineto + height 4 div lw 2 div add lw lineto + lw height 4 div lw 2 div add lineto + lw height 3 4 div mul lw 2 div sub lineto + height 4 div lw 2 div add height lw sub lineto + height 2 div 1.25 mul height lw sub lineto + closepath fill + newpath + height 2 div height 2 div moveto + height 2 div 0 rlineto + 0 height 2 div neg rlineto + lw neg 0 rlineto + 0 height 2 div lw sub rlineto + height 2 div height 2 div lw sub lineto + closepath fill +} if + +height 2 div 1.25 mul lw add 0 translate +false { + newpath + 0 height moveto + height 0 rlineto + 0 lw neg rlineto + height lw sub 2 div neg 0 rlineto + 0 height lw sub neg rlineto + lw neg 0 rlineto + 0 height lw sub rlineto + height lw sub 2 div neg 0 rlineto + 0 lw rlineto + closepath fill +} if + +true { % The "T" of "GT". + newpath + 0 height moveto + height lw add 2 div 0 rlineto + 0 height neg rlineto + lw neg 0 rlineto + 0 height lw sub rlineto + height lw sub 2 div neg 0 rlineto + closepath fill + + % The right half of the top of the "T" + newpath + % (height + lw)/2 + lw + height lw add 2 div lw add height moveto + % height - (above) = height - height/2 - 3/2 lw = height/2-3/2lw + height 3 lw mul sub 2 div 0 rlineto + 0 lw neg rlineto + height 3 lw mul sub 2 div neg 0 rlineto + closepath fill +} if + + +grestore +showpage +%%EOF Index: src/gqtekspec.cls =================================================================== --- src/gqtekspec.cls (nonexistent) +++ src/gqtekspec.cls (revision 10) @@ -0,0 +1,280 @@ +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%/ +% +% Copyright (C) 2015, Gisselquist Technology, LLC +% +% This template is free software: 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 template 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 for a copy. +% +% License: GPL, v3, as defined and found on www.gnu.org, +% http://www.gnu.org/licenses/gpl.html +% +% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% \NeedsTeXFormat{LaTeX2e}[1995/12/01] +\ProvidesClass{gqtekspec}[2015/02/15 v0.1 -- Gisselquist Technology Specification] +\typeout{by Dan Gisselquist} +\LoadClassWithOptions{report} +\usepackage{datetime} +\usepackage{graphicx} +\usepackage[dvips]{pstricks} +\newdateformat{headerdate}{\THEYEAR/\twodigit{\THEMONTH}/\twodigit{\THEDAY}} +\setlength{\hoffset}{0.25in} +\setlength{\voffset}{-0.5in} +\setlength{\marginparwidth}{0in} +\setlength{\marginparsep}{0in} +\setlength{\textwidth}{6in} +\setlength{\oddsidemargin}{0in} + +% ************************************** +% * APPENDIX * +% ************************************** +% +\newcommand\appfl@g{\appendixname} %used to test \@chapapp +% +% \renewcommand\appendix{\par\clearpage + % \setcounter{chapter}{0}% + % \setcounter{section}{0}% + % \renewcommand\@chapapp{\appendixname}% + % \renewcommand\thechapter{\Alph{chapter}} + % \if@nosectnum\else + % \renewcommand\thesection{\Alph{chapter}.\arabic{section}} + % \fi +% } + + +% FIGURE +% redefine the @caption command to put a period after the figure or +% table number in the lof and lot tables +\long\def\@caption#1[#2]#3{\par\addcontentsline{\csname + ext@#1\endcsname}{#1}{\protect\numberline{\csname + the#1\endcsname.}{\ignorespaces #2}}\begingroup + \@parboxrestore + \normalsize + \@makecaption{\csname fnum@#1\endcsname}{\ignorespaces #3}\par + \endgroup} + +% **************************************** +% * TABLE OF CONTENTS, ETC. * +% **************************************** + +\renewcommand\contentsname{Contents} +\renewcommand\listfigurename{Figures} +\renewcommand\listtablename{Tables} + +\newif\if@toc \@tocfalse +\renewcommand\tableofcontents{% + \begingroup% temporarily set if@toc so that \@schapter will not + % put Table of Contents in the table of contents. + \@toctrue + \chapter*{\contentsname} + \endgroup + \thispagestyle{gqtekspecplain} + + \baselineskip=10pt plus .5pt minus .5pt + + {\raggedleft Page \par\vskip-\parskip} + \@starttoc{toc}% + \baselineskip=\normalbaselineskip + } + +\def\l@appendix{\pagebreak[3] + \vskip 1.0em plus 1pt % space above appendix line + \@dottedtocline{0}{0em}{8em}} + +\def\l@chapter{\pagebreak[3] + \vskip 1.0em plus 1pt % space above appendix line + \@dottedtocline{0}{0em}{4em}} + +% \if@nosectnum\else + % \renewcommand\l@section{\@dottedtocline{1}{5.5em}{2.4em}} + % \renewcommand\l@subsection{\@dottedtocline{2}{8.5em}{3.2em}} + % \renewcommand\l@subsubsection{\@dottedtocline{3}{11em}{4.1em}} + % \renewcommand\l@paragraph{\@dottedtocline{4}{13.5em}{5em}} + % \renewcommand\l@subparagraph{\@dottedtocline{5}{16em}{6em}} +% \fi + +% LIST OF FIGURES +% +\def\listoffigures{% + \begingroup + \chapter*{\listfigurename}% + \endgroup + \thispagestyle{gqtekspecplain}% + + \baselineskip=10pt plus .5pt minus .5pt% + + {\hbox to \hsize{Figure\hfil Page} \par\vskip-\parskip}% + + \rule[2mm]{\textwidth}{0.5mm}\par + + \@starttoc{lof}% + \baselineskip=\normalbaselineskip}% + +\def\l@figure{\@dottedtocline{1}{1em}{4.0em}} + +% LIST OF TABLES +% +\def\listoftables{% + \begingroup + \chapter*{\listtablename}% + \endgroup + \thispagestyle{gqtekspecplain}% + \baselineskip=10pt plus .5pt minus .5pt% + {\hbox to \hsize{Table\hfil Page} \par\vskip-\parskip}% + + % Added line underneath headings, 20 Jun 01, Capt Todd Hale. + \rule[2mm]{\textwidth}{0.5mm}\par + + \@starttoc{lot}% + \baselineskip=\normalbaselineskip}% + +\let\l@table\l@figure + +% **************************************** +% * PAGE STYLES * +% **************************************** +% +\def\ps@gqtekspectoc{% + \let\@mkboth\@gobbletwo + \def \@oddhead{} + \def \@oddfoot{\rm + \hfil\raisebox{-9pt}{\thepage}\hfil\thispagestyle{gqtekspectocn}} + \let \@evenhead\@oddhead \let \@evenfoot\@oddfoot} +\def\ps@gqtekspectocn{\let\@mkboth\@gobbletwo + \def \@oddhead{\rm \hfil\raisebox{10pt}{Page}} + \def \@oddfoot{\rm + \hfil\raisebox{-9pt}{\thepage}\hfil\thispagestyle{gqtekspectocn}} + \let \@evenhead\@oddhead \let \@evenfoot\@oddfoot} + +\def\ps@gqtekspeclof{\let\@mkboth\@gobbletwo + \def \@oddhead{} + \def \@oddfoot{\rm + \hfil\raisebox{-9pt}{\thepage}\hfil\thispagestyle{gqtekspeclofn}} + \let \@evenhead\@oddhead \let \@evenfoot\@oddfoot} +\def\ps@gqtekspeclofn{\let\@mkboth\@gobbletwo + \def \@oddhead{\rm + \parbox{\textwidth}{\raisebox{0pt}{Figure}\hfil\raisebox{0pt}{Page} % + \raisebox{20pt}{\rule[10pt]{\textwidth}{0.5mm}} }} + + \def \@oddfoot{\rm + \hfil\raisebox{-9pt}{\thepage}\hfil\thispagestyle{gqtekspeclofn}} + \let \@evenhead\@oddhead \let \@evenfoot\@oddfoot} + +\def\ps@gqtekspeclot{\let\@mkboth\@gobbletwo + \def \@oddhead{} + \def \@oddfoot{\rm + \hfil\raisebox{-9pt}{\thepage}\hfil\thispagestyle{gqtekspeclotn}} + \let \@evenhead\@oddhead \let \@evenfoot\@oddfoot} +\def\ps@gqtekspeclotn{\let\@mkboth\@gobbletwo + \def \@oddhead{\rm + \parbox{\textwidth}{\raisebox{0pt}{Table}\hfil\raisebox{0pt}{Page} % + \raisebox{20pt}{\rule[10pt]{\textwidth}{0.5mm}} }} + + \def \@oddfoot{\rm + \hfil\raisebox{-9pt}{\thepage}\hfil\thispagestyle{gqtekspeclotn}} + \let \@evenhead\@oddhead \let \@evenfoot\@oddfoot} + +\def\ps@gqtekspecplain{\let\@mkboth\@gobbletwo + \def \@oddhead{\rput(0,-2pt){\psline(0,0)(\textwidth,0)}\rm \hbox to 1in{\includegraphics[height=0.8\headheight]{GT.eps} Gisselquist Technology, LLC}\hfil\hbox{\r@vision}\hfil\hbox to 1in{\hfil\headerdate\@date}} + \def \@oddfoot{\rput(0,9pt){\psline(0,0)(\textwidth,0)}\rm \hbox to 1in{www.opencores.com\hfil} \hfil\hbox{\r@vision}\hfil\thepage} + \let \@evenhead\@oddhead \let \@evenfoot\@oddfoot} + +% \def\author#1{\def\auth@r{#1}} +% \def\title#1{\def\ti@tle{#1}} + +\def\logo{\begin{pspicture}(0,0)(5.67in,0.75in) + \rput[lb](0.05in,0.10in){\includegraphics[height=0.75in]{GT.eps}} + \rput[lb](1.15in,0.05in){\scalebox{1.8}{\parbox{2.0in}{Gisselquist\\Technology, LLC}}} + \end{pspicture}} +% TITLEPAGE +% +\def\titlepage{\setcounter{page}{1} + \typeout{^^JTitle Page.} + \thispagestyle{empty} + \leftline{\rput(0,0){\psline(0,0)(\textwidth,0)}\hfill} + \vskip 2\baselineskip + \logo\hfil % Original is 3.91 in x 1.26 in, let's match V thus + \vspace*{5pt}\vfil + \begin{minipage}{\textwidth}\raggedleft + \ifproject{\scalebox{1.2}{\Huge\bfseries\MakeUppercase\@project}} \\\fi + \vspace*{15pt} + \scalebox{1.2}{\Huge\bfseries\MakeUppercase\@title} \\ + \vskip 8\baselineskip + \large \@author \\ + \ifemail{\large \@email}\\\fi + \vskip 4\baselineskip + \large \usdate\@date \\ + \end{minipage} + % \baselineskip 22.5pt\large\rm\MakeUppercase\ti@tle + \vspace*{30pt} + \vfil + \newpage\baselineskip=\normalbaselineskip} + +\newenvironment{license}{\clearpage\typeout{^^JLicense Page.}\ \vfill\noindent}% + {\vfill\newpage} +% **************************************** +% * CHAPTER DEFINITIONS * +% **************************************** +% +\renewcommand\chapter{\if@openright\cleardoublepage\else\clearpage\fi + \thispagestyle{gqtekspecplain}% + \global\@topnum\z@ + \@afterindentfalse + \secdef\@chapter\@schapter} +\renewcommand\@makechapterhead[1]{% + \hbox to \textwidth{\hfil\scalebox{1.8}{\Huge\bfseries \thechapter.}}\vskip 10\p@ + \hbox to \textwidth{\rput(0,0){\psline[linewidth=0.04in](0,0)(\textwidth,0)}}\vskip \p@ + \hbox to \textwidth{\rput(0,0){\psline[linewidth=0.04in](0,0)(\textwidth,0)}}\vskip 10\p@ + \hbox to \textwidth{\hfill\scalebox{1.8}{\Huge\bfseries #1}}% + \par\nobreak\vskip 40\p@} +\renewcommand\@makeschapterhead[1]{% + \hbox to \textwidth{\hfill\scalebox{1.8}{\Huge\bfseries #1}}% + \par\nobreak\vskip 40\p@} +% **************************************** +% * INITIALIZATION * +% **************************************** +% +% Default initializations + +\ps@gqtekspecplain % 'gqtekspecplain' page style with lowered page nos. +\onecolumn % Single-column. +\pagenumbering{roman} % the first chapter will change pagenumbering + % to arabic +\setcounter{page}{1} % in case a titlepage is not requested + % otherwise titlepage sets page to 1 since the + % flyleaf is not counted as a page +\widowpenalty 10000 % completely discourage widow lines +\clubpenalty 10000 % completely discourage club (orphan) lines +\raggedbottom % don't force alignment of bottom of pages + +\date{\today} +\newif\ifproject\projectfalse +\def\project#1{\projecttrue\gdef\@project{#1}} +\def\@project{} +\newif\ifemail\emailfalse +\def\email#1{\emailtrue\gdef\@email{#1}} +\def\@email{} +\def\revision#1{\gdef\r@vision{#1}} +\def\r@vision{} +\def\at{\makeatletter @\makeatother} +\newdateformat{theyear}{\THEYEAR} +\newenvironment{revisionhistory}{\clearpage\typeout{^^JRevision History.}% + \hbox to \textwidth{\hfil\scalebox{1.8}{\large\bfseries Revision History}}\vskip 10\p@% + \begin{tabular}{|p{0.5in}|p{1in}|p{1in}|p{3.5in}|}\hline + Rev. & Date & Author & Description\\\hline\hline} + {\end{tabular}\clearpage} +\newenvironment{portlist}{\begin{tabular}{|p{0.75in}|p{0.5in}|p{0.75in}|p{3.5in}|}\hline + Port & Width & Direction & Description \\\hline\hline}% + {\end{tabular}} +\newenvironment{preface}{\chapter*{Preface}}{\par\bigskip\bigskip\leftline{\hfill\@author}} +\endinput Index: src/spec.tex =================================================================== --- src/spec.tex (nonexistent) +++ src/spec.tex (revision 10) @@ -0,0 +1,498 @@ +\documentclass{gqtekspec} +\project{Double Clocked FFT} +\title{Specification} +\author{Dan Gisselquist, Ph.D.} +\email{dgisselq\at opencores.org} +\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{} for a copy. +\end{license} +\begin{revisionhistory} +0.0 & 3/2/2015 & Gisselquist & Incomplete 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. +\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. +\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(-1in,0.9in){\tt i\_nnonce}-1in,1.8in){\psline{->}(0,0)(1in,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(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}(0in,0in)(\textwidth,5in) + \rput(0,0){\psframe(0in,0in)(\textwidth,5in)} + \rput(1.675in,3.75in){\psline{->}(0,0.5in)(0,0in)} + \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(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,0in)} + \rput(1.25in,-0.25in){\psline{->}(0,0.25in)(0,0in)} + } + % \rput(0,0){\psframe(1.3in,-0.25in)(4.7in,5in)} + \iffalse + \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)}} + \fi +\end{pspicture} +\caption{A Single FFT Stage, with Butterfly (Figure is still a work in progress)}\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 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. 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 valiid 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 + [$2N_i-1$:$2N_i$] of this value are the real portion, + whereas bits [$2N_i-1$: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} + + Index: gpl-3.0.pdf =================================================================== Cannot display: file marked as a binary type. svn:mime-type = application/octet-stream Index: gpl-3.0.pdf =================================================================== --- gpl-3.0.pdf (nonexistent) +++ gpl-3.0.pdf (revision 10)

gpl-3.0.pdf Property changes : Added: svn:mime-type ## -0,0 +1 ## +application/octet-stream \ No newline at end of property Index: Makefile =================================================================== --- Makefile (revision 3) +++ Makefile (revision 10) @@ -1,4 +1,4 @@ -all: gpl-3.0.pdf +all: gpl-3.0.pdf spec.pdf DSRC := src gpl-3.0.pdf: $(DSRC)/gpl-3.0.tex @@ -8,3 +8,11 @@ ps2pdf -dAutoRotatePages=/All gpl-3.0.ps gpl-3.0.pdf rm gpl-3.0.dvi gpl-3.0.log gpl-3.0.aux gpl-3.0.ps +spec.pdf: $(DSRC)/spec.tex $(DSRC)/gqtekspec.cls + cd $(DSRC)/; latex spec.tex + cd $(DSRC)/; latex spec.tex + dvips -q -z -t letter -P pdf -o spec.ps $(DSRC)/spec.dvi + ps2pdf -dAutoRotatePages=/All spec.ps spec.pdf + rm $(DSRC)/spec.dvi $(DSRC)/spec.log + rm $(DSRC)/spec.aux spec.ps $(DSRC)/spec.toc +