URL
https://opencores.org/ocsvn/yac/yac/trunk
Subversion Repositories yac
[/] [yac/] [trunk/] [doc/] [documentation.tex] - Rev 2
Compare with Previous | Blame | View Log
\documentclass[a4paper, 12pt, notitlepage]{report}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{fullpage}
\usepackage[pagewise]{lineno}
\usepackage{hyperref}
\usepackage{longtable}
\usepackage{ltxtable}
\usepackage[usenames,dvipsnames]{color}
\usepackage{colortbl}
\usepackage{tabularx, booktabs}
\usepackage{multirow}
\usepackage{dirtree}
\definecolor{tableheadcolor}{gray}{0.8}
\definecolor{darkblue}{rgb}{0,0,.5}
\definecolor{gray}{gray}{0.95}
\definecolor{lightgray}{gray}{0.95}
\newcommand{\file}[1]{\textbf{#1}}
\newcommand{\state}[1]{{\tt\textbf{#1}}}
\newcommand{\signal}[1]{{\textbf{\tt#1}}}
\title{YAC - Yet Another CORDIC Core}
\author{Christian Haettich [feddischson@opencores.org]}
\date{\today}
\begin{document}
%%%%%%%%%% PRELIMINARY MATERIAL %%%%%%%%%%
\maketitle
\begin{center}
IP core and C-model documentation
\end{center}
\thispagestyle{empty}
\tableofcontents
\chapter{Organization and Introduction}
\section{History}
\begin{table}[htbp]
\center
\begin{tabular}{@{}llll@{}}
\rowcolor{tableheadcolor}\textbf{Version}& \textbf{Date} & \textbf{Description} & \textbf{Author} \\
\multirow{1}{*}{0.01} & 4th March 2014 & Initial document & Christian Haettich\\\midrule
\bottomrule
\end{tabular}
\caption{History}
\label{tab:frqband}
\end{table}
\section{Folder and Files}
\dirtree{%
.1 /.
.2 c\_octave.
.3 cordic\_iterative.c\DTcomment{C-code for bit accurate model}.
.3 cordic\_iterative\_code.m\DTcomment{Script to auto-generate VHDL and C-code}.
.3 cordic\_iterative\_test.m\DTcomment{YAC performance analysis script}.
.2 doc.\DTcomment{Contains files to create this documentation}.
.2 licenses.
.3 lgpl-3.0.txt\DTcomment{LGPL license}.
.2 README.txt\DTcomment{A short read-me file}.
.2 rtl.
.3 vhdl.
.4 cordic\_iterative\_int.vhd\DTcomment{Top-level VHDL file}.
.4 cordic\_iterative\_pkg.vhd\DTcomment{VHDL package file}.
.4 cordic\_iterative\_tb.vhd\DTcomment{VHDL testbench}.
}
\section{License}
Copyright (c) 2014, Christian Haettich, All rights reserved. \newline\newline
YAC is free software; 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.0 of the License, or (at your option) any later version. \newline\newline
YAC is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details. \newline\newline
You should have received a copy of the GNU Lesser General Public
License along with this library. If not, download it from
http://www.gnu.org/licenses/lgpl
\section{The CORDIC algorithm}
The CORDIC algorithm is used to do trigonometric, hyperbolic, multiplication
and division calculations in a hardware-efficient way. This means, that
only bit-shift, addition and subtraction operations in combination
with a lookup-table is required.\newline
Good introductions are available in \cite{survey}\cite{vlsi}\cite{dawid}.
A description on wikibook.org \cite{wikibook} is also useful.
For this reason, no more introduction is given here and the following chapters assume, that
the reader is familiar with the CORDIC algorithm.
\chapter{IP-Core Description}
The two files \file{cordic\_iterative\_int.vhd} and \file{cordic\_iterative\_pkg.vhd}
implements an iterative CORDIC algorithm in fixed-point format.
Iterative means, that the IP-core is started with a set of input data and after
a specific amount of clock cycles, the result is available. No parallel data
can be processed. The
following six modes are supported:
\begin{itemize}
\item trigonometric rotation
\item trigonometric vectoring
\item linear rotation
\item linear vectoring
\item hyperbolic rotation
\item hyperbolic vectoring
\end{itemize}
\section{Port Description}
\begin{table}[htbp]
\center
\begin{tabular}{@{}lllll@{}}
\rowcolor{tableheadcolor}\textbf{Name}& \textbf{Type} & \textbf{Direction} & \textbf{Size} & \textbf{Description} \\
\multirow{1}{*}{clk} & std\_logic & input & 1 & clock \\\midrule
\multirow{1}{*}{rst} & std\_logic & input & 1 & synchronous reset \\\midrule
\multirow{1}{*}{en} & std\_logic & input & 1 & clock-enable \\\midrule
\multirow{1}{*}{start} & std\_logic & input & 1 & start trigger \\\midrule
\multirow{1}{*}{done} & std\_logic & output & 1 & done indicator \\\midrule
\multirow{1}{*}{mode} & std\_logic\_vector & input & 4 & mode configuration \\\midrule
\multirow{1}{*}{x\_i} & std\_logic\_vector & input & XY\_WIDTH & X input vector \\\midrule
\multirow{1}{*}{y\_i} & std\_logic\_vector & input & XY\_WIDTH & Y input vector \\\midrule
\multirow{1}{*}{a\_i} & std\_logic\_vector & input & A\_WIDTH + 2 & angular input vector \\\midrule
\multirow{1}{*}{x\_o} & std\_logic\_vector & input & XY\_WIDTH + GUARD\_BITS & X output vector \\\midrule
\multirow{1}{*}{y\_o} & std\_logic\_vector & input & XY\_WIDTH + GUARD\_BITS & Y output vector \\\midrule
\multirow{1}{*}{a\_o} & std\_logic\_vector & input & A\_WIDTH + 2 & angular output vector \\\midrule
\bottomrule
\end{tabular}
\caption{Port description}
\label{tab:ports}
\end{table}
\begin{figure}[p]
\centering
\includegraphics{figs/block_symbol.pdf}
\caption{YAC block symbol}
\label{fig:ports}
\end{figure}
Table \ref{tab:ports} and Figure \ref{fig:ports} gives an overview
of the YAC ports.
The three input ports start, done and mode and are used to interact
with an external state machine or with a software driver.
After setting \signal{start} to high, the YAC starts processing.
If all necessary rotations are done, the \signal{done} output is set to
high for one clock cycle.
When starting the YAC, all other inputs must contain valid data.
The mode input is used to select the CORDIC mode.
Table \ref{fig:ports} shows all input and output ports and Figure
\ref{fig:ports} shows a CORDIC block symbol: $x_i, y_i, a_i, x_o, y_o, a_o$
are data ports whereas start, done and mode are configuration signals.
\section{Parameter Description}
\begin{table}[htbp]
\center
\begin{tabular}{@{}lllll@{}}
\rowcolor{tableheadcolor}\textbf{Name}& \textbf{type} & \textbf{size} & \textbf{Description} \\
\multirow{1}{*}{XY\_WIDTH} & natural & defines the size of x and y input and output vectors \\\midrule
\multirow{1}{*}{A\_WIDTH} & natural & defines the size of the angular input and output vectors \\\midrule
\multirow{1}{*}{GUARD\_BITS} & natural & defines the number of guard bits \\\midrule
\multirow{1}{*}{RM\_GAIN} & natural & defines the precision of the CORDIC gain removal \\\midrule
\bottomrule
\end{tabular}
\caption{Parameter description}
\label{tab:params}
\end{table}
Table \ref{tab:params} shows the four parameter, which can be used to parameterize
the YAC.
\section{Mode description}
With the mode-input, it is possible to select between circular, linear and hyperbolic
operation as well as between rotation and vectoring operations:
\begin{itemize}
\item mode(1:0) = "00" selects circular operation
\item mode(1:0) = "01" selects linear operation
\item mode(1:0) = "10" selects hyperbolic operation
\item mode(1:0) = "11" is reserved
\item mode(3) = '0' selects rotation
\item mode(3) = '1' selects vectoring
\end{itemize}
The package cordic\_iterative\_int.vhd contains the following defines to
setup the mode:
\begin{itemize}
\item VAL\_MODE\_CIRC = "00"
\item VAL\_MODE\_LIN = "01"
\item VAL\_MODE\_HYP = "10"
\item I\_FLAG\_VEC\_ROT = 3 (bit index)
\end{itemize}
For example if a hyperbolic rotation mode is required, the mode input is "0010",
and for the linear vector operation, the mode input is "1001".
Please note, that bit number 2 is reserved for future implementations.\newline
Table \ref{tab:modes} defines the behaviour of the YAC
for different mode configurations.
\begin{table}[htbp]
\center
\begin{tabular}{@{}ll@{}}
\rowcolor{tableheadcolor}\textbf{Setup}& \textbf{Description} \\
\multirow{2}{*}{mode =( FLAG\_VEC\_ROT = 1, VAL\_MODE\_CIR ) } & $a_o = \textrm{atan2}( y_i, x_i ) \cdot \beta, $\\
& $x_o = \sqrt{ x_i^2+y_i^2 } $ \\\midrule
\multirow{2}{*}{mode =( FLAG\_VEC\_ROT = 0, VAL\_MODE\_CIR ) } & $x_o = \cos( a_i / \beta ) \cdot \alpha $\\
& $y_o = \sin( a_i / \beta ) \cdot \alpha $\\\midrule
\multirow{1}{*}{mode =( FLAG\_VEC\_ROT = 1, VAL\_MODE\_LIN ) } & $a_o = z + y/x $\\\midrule
\multirow{1}{*}{mode =( FLAG\_VEC\_ROT = 0, VAL\_MODE\_LIN ) } & $a_o = y + x\cdot z $ $ $\\\midrule
\multirow{2}{*}{mode =( FLAG\_VEC\_ROT = 1, VAL\_MODE\_HYP ) } & $a_o = \textrm{tanh}( y_i / x_i ) \cdot \beta, $\\
& $x_o = \sqrt{ x_i^2-y_i^2 } $\\\midrule
\multirow{2}{*}{mode =( FLAG\_VEC\_ROT = 0, VAL\_MODE\_HYP ) } & $x_o = \cosh( a_i / \beta ) \cdot \alpha$\\
& $y_o = \sinh( a_i / \beta ) \cdot \alpha$\\
\bottomrule
\end{tabular}
\caption{Mode description (see equation \ref{eqn:alpha} and \ref{eqn:beta} for $\alpha$ and $\beta$)}
\label{tab:modes}
\end{table}
\section{Data Range and Limitations}
Both, the $x_i$ and $y_i$ inputs are defined with a size of $XY\_WIDTH$ and therefore,
the maximum positive value in the two's complement format is
\begin{eqnarray}
\alpha & = & 2^{XY\_WIDTH-1}-1
\label{eqn:alpha}
\end{eqnarray}
The angle input $a_i$ is defined with a size of $A\_WIDTH+2$.
The value $\beta$ is defined with
\begin{eqnarray}
\beta & = & 2^{A\_WIDTH-1} -1
\label{eqn:beta}
\end{eqnarray}
\subsection{Circular Vectoring Mode}
The valid input range for $x_i$ and $y_i$ is $-\alpha ... +\alpha$.
The angular input $a_i$ is ignored.
\subsection{Circular Rotation Mode}
The valid input range for $x_i$ and $y_i$ is $-\alpha ... +\alpha$.
For the angular input $a_i$, values between $-\beta\pi$ and $+\beta\pi$ are valid.
For calculating a complex rotation of a complex vector, all three inputs
are required. For calculating $\sin$ and $\cos$, $x_i$ is set to $\alpha$
and $y_i$ to 0, the angle input $a_i$ gets the angle.
\subsection{Linear Vectoring Mode}
The linear vectoring mode is used to calculate $y_i / x_i$. The limitation
of this operation is the following:
\begin{eqnarray}
\frac{y_i}{x_i} \le 2
\end{eqnarray}
The valid input values for $x_i$ and $y_i$ are $-\alpha ... +\alpha$.
\subsection{Linear Rotation Mode}
The two inputs $x_i$ and $y_i$ have a valid data range between $-\alpha$ and $+\alpha$.
\subsection{Hyperbolic Vectoring Mode}
The data-range for $x_i$ and $y_i$ is $-0.79 \cdot \alpha$ to $0.79 \cdot \alpha$.
\subsection{Hyperbolic Rotation Mode}
The data-range for $a_i$ is $-\beta ... \beta$. Typically, $x_i$ is set to
$\alpha$ and $y_i$ to 0.
\section{Internal Operation}
\begin{figure}[p]
\centering
\includegraphics[width=200pt]{figs/state_diagram.pdf}
\caption{State diagram}
\label{fig:states}
\end{figure}
Five states are used do to the CORDIC algorithm. The five states are visualized in a
state diagram in Figure \ref{fig:states}.
After reset, the YAC goes into the \state{ST\_IDLE} state. Only in this state, the
start signal is accepted. After starting the YAC, the state switches from
the \state{ST\_IDLE} state to the \state{ST\_INIT} state. The init state does some initial
rotations/flipping.
After initialization, the main rotation starts with the \state{ST\_ROTATION} state
(there are a few cases, where no further rotations are required, see next sections).
Every rotation step is done within two clock cycles: in the first cycle,
the angular value is loaded from the lookup-table and shifted. In addition,
the x and y values are shifted. In the second
clock cycle, the results are added according to the CORDIC algorithm.
After all required iterations are done, the state switches to
the \state{RM\_GAIN} state, where the CORDIC gain is removed (depending on
the mode). The last state \state{ST\_DONE} is only used to set the done flag to
'1' for one clock cycle. After this, the YAC returns to the \state{ST\_IDLE} state.
\subsection{Initialization}
During the initialization state ST\_INIT, pre-rotations are done, depending on
the selected mode.
\subsubsection{Circular Vectoring Mode}
Because we support atan2 and not atan, we do the following pre-rotations.
Some specific input values don't need a further processing, for
example $atan( 0, 0 )$.\newline\newline
\begin{tabular}{@{}lp{380pt}@{}}
\rowcolor{tableheadcolor}\textbf{Input} &\textbf{ Description } \\
$x_i = 0, y_i = 0$ & Fixed result: $x_o = 0, a_o = 0$,
to support cartesian to polar coordinate transformations,
further processing is skipped \\ \midrule
$x_i = 0, y_i > 0 $ & Fixed result: $x_o = y_i, a_o = \pi/2$,
further processing is skipped \\ \midrule
$x_i = 0, y_i < 0 $ & Fixed result: $x_o = -y_i, a_o = -\pi/2$,
further processing is skipped \\ \midrule
$x_i < 0, y_i < 0 $ & Pre-rotation from the third to the first quadrant,
the angular register is initialized with $-\pi$ and
the sign of the $x$ and $y$ register is flipped. \\ \midrule
$x_i < 0, y_i \ge 0 $ & Pre-rotation from the second to the fourth quadrant,
the angular register is initialized with $\pi$ and
the sign of the $x$ and $y$ register is flipped. \\ \midrule
$x_i = + \alpha, y_i = + \alpha $ & Fixed result: $x_o = \sqrt{2} \cdot \alpha, a_o = \frac{\pi}{4} \cdot \beta$ ,
further processing is skipped \\ \midrule
$x_i = + \alpha, y_i = - \alpha $ & Fixed result: $x_o = \sqrt{2} \cdot \alpha, a_o = - \frac{\pi}{4} \cdot \beta$,
further processing is skipped \\ \midrule
$x_i = - \alpha, y_i = + \alpha $ & Fixed result: $x_o = \sqrt{2} \cdot \alpha, a_o = \frac{3 \pi}{4} \cdot \beta$,
further processing is skipped \\ \midrule
$x_i = - \alpha, y_i = - \alpha $ & Fixed result: $x_o = \sqrt{2} \cdot \alpha, a_o = - \frac{3 \pi }{4} \cdot \beta$ ,
further processing is skipped \\
\bottomrule
\end{tabular}
\subsubsection{Circular Rotation Mode}
The following pre-rotations are done:\newline\newline
\begin{tabular}{@{}lp{380pt}@{}}
\rowcolor{tableheadcolor}\textbf{Input} &\textbf{ Description } \\
$a_i < - \frac{\pi}{2}$ & Pre-rotation from the third to the first quadrant,
the sign of the $x$ and $y$ register is flipped,
the angular register is initialized with $\pi$ \\ \midrule
$a_i > \frac{\pi}{2}$ & Pre-rotation from the second to the fourth quadrant,
the sign of the $x$ and $y$ register is flipped,
the angular register is initialized with $-\pi$ \\
\bottomrule
\end{tabular}
\subsubsection{Linear Vectoring Mode}
The following pre-rotations are done:\newline\newline
\begin{tabular}{@{}lp{380pt}@{}}
\rowcolor{tableheadcolor}\textbf{Input} &\textbf{ Description } \\
$x_i < 0$ & Pre-rotation from the left half to the right half, thus
the sign of the $x$ and $y$ register is flipped \\
\bottomrule
\end{tabular}
\subsection{Rotation}
\subsubsection{Hyperbolic Repetitions}
The following iteration steps are repeated for convergence of the hyperbolic mode:
\begin{eqnarray}
4, 13, 40, 121, ..., 3i+1
\end{eqnarray}
\section{Testbench}
A VHDL testbench (cordic\_iterative\_tb.vhd) is available which reads from an input file
data. This data is fed into the YAC. In addition, the input file must
provide the output data, which is expected from the YAC processing.
The following format is used in the testbench input-file:
\begin{verbatim}
x_i y_i a_i x_o y_o a_o mode
1234 1234 1234 1234 1234 1234 111 \
2345 2345 2345 2345 2345 2345 222 | 7 columns:
3456 3456 3456 3456 3456 3456 333 | 3 input, 3 output and one mode
... ... |
... |
...
\end{verbatim}
The data must be in the two's complement with a base of 10.
After processing all lines, the testbench prints some info, how much
tests failed.\newline
For generating the test-patterns, the C-model with octave is used. By running
the script \file{cordic\_iterative\_test.m}, an entry
in the testbech data file is done for every cordic calculation.
\chapter{Using the C-Model with Octave or Matlab}
For using the C-model, open octave or Matlab and compile the C-Model
with \newline
\textit{mex cordic\_iterative.c}
Afterwards, the C-model can be used in Octave/Matlab with the function call\newline
{\tt [ x\_o, y\_o, a\_o, it ] = cordic\_iterative( x\_i, y\_i, a\_i, mode, XY\_WIDTH, ANGLE\_WIDTH,
GUARD\_BITS, RM\_GAIN )}.\newline
The input and output arguments reflect almost the ports and parameters of the
VHDL toplevel implementation, except that there is no done, start clk and rst port
in the C-model. In addition, the last argument provides the number of iterations,
which are done.\newline \newline
The input arguments x\_i, y\_i, and a\_i can be 1xN vectors with N elements.
In this case, this three input arguments must have the same size. All
output arguments will also have the same size 1xN.
\section{Guard-Bits -- Input and output sizes}
It is possible to define MSB guard bits.
The need of MSB guard bits have several reasons. On the one hand,
they are required to handle the data growth of the cordic gain within the rotation state.
(which is compensated later). A nother reason is the data growth caused by the choise of
input data. For example
\begin{eqnarray}
\sqrt{ \alpha^2 + \alpha^2 } = \sqrt{2} \alpha
\end{eqnarray}
and therefore, a growth by the factor $\sqrt{2}$ happens, if an absolute calculation
of the two maximum input values is processed.\newline
\newline
Another point is the input and output size of the angular values ($a_i$ and $a_o$)
Because within this YAC, $\beta$ represents the angle 1, the input and output with
of $a_i$ and $a_o$ is A\_WIDTH+2, which allows to process angle values within
$-\pi ... \pi$
\subsection{Input data width versus iterations}
The number of iterations depends on the width of the input data.
Input data with $X$ bit require $X+1$ rotations \cite{dawid}.
This requires, that the number of iterations are adapted. One solution might
be to detect the size of the input data and use this information for the CORDIC processing.
In YAC, a different sheme was chosen: the rotations are done until
\begin{itemize}
\item the angular register is 0 or doesn't change (in case of the rotation mode)
\item the y register is 0 or doesn't change (in case of the vecotring mode).
\end{itemize}
This results in a dynamic iterations adaption, depending the the input data width.
\chapter{Performance}
The performance is evaluated through the matlab script \file{cordic\_iterative\_test.m}.
\chapter{Open issues and future work}
\section{Next steps}
\begin{itemize}
\item Add YAC to a FPGA based System-on-Chip to prove
FPGA feasibility
\item Performance optimization
\item circuit optimizations
\item numerical optimizations
\end{itemize}
\section{Future plans}
\begin{itemize}
\item Hyperbolic range extension
\item Floating point CORDIC
\end{itemize}
%%%%%%%%%% BIBLIOGRAPHY %%%%%%%%%%
\begin{thebibliography}{9}
\bibitem{survey}
Andraka, Ray; \textit{A survey of CORDIC algorithms for FPGA based computers}
\bibitem{vlsi}
Hu, Yu Hen; \textit{CORDIC-Based VLSI Architectures for Digital Signal Processing}
\bibitem{wikibook}
CORDIC on wikibook: \url{http://en.wikibooks.org/wiki/Digital_Circuits/CORDIC}
\bibitem{dawid}
David, Herbert; Meyr, Heinricht; \textit{CORDIC Algorithms and Architectures}
\url{http://www.eecs.berkeley.edu/newton/Classes/EE290sp99/lectures/ee290aSp996_1/cordic_chap24.pdf}
\end{thebibliography}
\end{document}
%
%
% Opencores Description
%
% For this project GIT is preferred as revision control and therefore, the files under development are located on https://github.com/feddischson/yac.
% Nevertheless, stable intermediate steps are place here on SVN.
%
%
%
%
%
%