+For the first item, we produced a matlab version of each algorithm,
+running in double precision. The profile was generated for about
+34,000 different quadruplets of periods ($\in \lbrack 3.1,6.1]$, step
+= 0.1), phases ($\in \lbrack -3.1,3.1]$, steps = 0.062) and slope
+($\in \lbrack -2,2]$, step = 0.4). Obviously, the discretization of
+$[-\pi ,\pi ]$ introduces an error in the phase estimation. It is at
+most equal to $\frac{\pi}{nb_s}$. From some experiments on a $17\times
+4$ array, authors of \cite{AFMCSEM11} noticed a average ratio of 50
+between phase variation in radians and lever end position in
+nanometers. Assuming such a ratio and $nb_s = 1024$, the maximum lever
+deflection error would be 0.15nm which is smaller than 0.3nm, the best
+precision achieved with the setup used in \cite{AFMCSEM11}.
+
+Moreover, pixels have been paired and the paired intensities have been
+perturbed by addition of a random number uniformly picked in
+$[-N,N]$. Notice that we have observed that perturbing each pixel
+independently yields too weak profile distortion. We report
+percentages of errors between the reference and the computed phases
+out of $2\pi ,$%
+\begin{equation*}
+err=100\times \frac{|\theta _{ref}-\theta _{comp}|}{2\pi }.
+\end{equation*}%
+Table \ref{tab:algo_prec} gives the maximum and the average errors for both
+algorithms and for increasing values of $N$ the noise parameter.
+
+\begin{table}[ht]
+\begin{center}
+\begin{tabular}{|c|c|c|c|c|}
+\hline
+& \multicolumn{2}{c|}{SPL} & \multicolumn{2}{c|}{LSQ} \\ \cline{2-5}
+noise (N)& max. err. & aver. err. & max. err. & aver. err. \\ \hline
+0 & 2.46 & 0.58 & 0.49 & 0.1 \\ \hline
+2.5 & 2.75 & 0.62 & 1.16 & 0.22 \\ \hline
+5 & 3.77 & 0.72 & 2.47 & 0.41 \\ \hline
+7.5 & 4.72 & 0.86 & 3.33 & 0.62 \\ \hline
+10 & 5.62 & 1.03 & 4.29 & 0.81 \\ \hline
+15 & 7.96 & 1.38 & 6.35 & 1.21 \\ \hline
+30 & 17.06 & 2.6 & 13.94 & 2.45 \\ \hline
+\end{tabular}%
+\end{center}
+\caption{Error (in \%) for cosines profiles, with noise.}
+\label{tab:algo_prec}
+\end{table}
+
+The results show that the two algorithms yield close results, with a slight
+advantage for LSQ. Furthermore, both behave very well against noise.
+Assuming an average ratio of 50 (see above), an error of 1 percent on
+the phase corresponds to an error of 0.5nm on the lever deflection, which is
+very close to the best precision.
+
+It is very hard to predict which level of noise will be present in
+real experiments and how it will distort the profiles. Authors of
+\cite{AFMCSEM11} gave us the authorization to exploit some of their
+results on a $17\times 4$ array. It allowed us to compare experimental
+profiles to simulated ones. We can see on figure \ref{fig:noise20} the
+profile with $N=10$ that leads to the biggest error. It is a bit
+distorted, with pikes and straight/rounded portions. In fact, it is
+very close to some of the worst experimental profiles. Figure
+\ref{fig:noise60} shows a sample of worst profile for $N=30$. It is
+completely distorted, largely beyond any experimental ones. Obviously,
+these comparisons are a bit subjectives and experimental profiles
+could also be completly distorted on other experiments. Nevertheless,
+they give an idea about the possible error.
+
+\begin{figure}[ht]
+\begin{center}
+\includegraphics[width=\columnwidth]{intens-noise20}
+\end{center}
+\caption{Sample of worst profile for N=10}
+\label{fig:noise20}
+\end{figure}
+
+\begin{figure}[ht]
+\begin{center}
+\includegraphics[width=\columnwidth]{intens-noise60}
+\end{center}
+\caption{Sample of worst profile for N=30}
+\label{fig:noise60}
+\end{figure}
+
+The second criterion is relatively easy to estimate for LSQ and harder for
+SPL because of the use of the arctangent function. In both cases, the number
+of operation is proportional to $M$ the numbers of pixels. For LSQ, it also
+depends on $nb_{s}$ and for SPL on $L=k\times M$ the number of interpolated
+points. We assume that $M=20$, $nb_{s}=1024$ and $k=4$, that all possible
+parts are already in lookup tables and that a limited set of operations (+,
+-, *, /, $<$, $>$) is taken into account. Translating both algorithms in C
+code, we obtain about 430 operations for LSQ and 1,550 (plus a few tenth for
+$atan$) for SPL. This result is largely in favor of LSQ. Nevertheless,
+considering the total number of operations is not fully relevant for FPGA
+implementation which time and space consumption depends not only on the type
+of operations but also of their ordering. The final evaluation is thus very
+much driven by the third criterion.
+
+The Spartan 6 used in our architecture has a hard constraint since it
+has no built-in floating point units. Obviously, it is possible to use
+some existing "black-boxes" for double precision operations. But they
+require a lot of clock cycles to complete. It is much simpler to
+exclusively use integers, with a quantization of all double precision
+values. It should be chosen in a manner that does not alterate result
+precision. Furthermore, it should not lead to a design with a huge
+latency because of operations that could not complete during a single
+or few clock cycles. Divisions fall into that category and, moreover,
+they need a varying number of clock cycles to complete. Even
+multiplications can be a problem since a DSP48 takes inputs of 18 bits
+maximum. So, for larger multiplications, several DSP must be combined
+which increases the overall latency.
+
+In the present algorithms, the hardest constraint does not come from the
+FPGA characteristics but from the algorithms. Their VHDL implementation can
+be efficient only if they can be fully (or near) pipelined. We observe that
+only a small part of SPL can be pipelined, indeed, the computation of spline
+coefficients implies to solve a linear tridiagonal system which matrix and
+right-hand side are computed from incoming pixels intensity but after, the
+back-solve starts with the latest values, which breaks the pipeline.
+Moreover, SPL relies on interpolating far more points than profile size.
+Thus, the end of SPL works on a larger amount of data than at the beginning,
+which also breaks the pipeline.
+
+LSQ has not this problem since all parts, except the dichotomic search, work
+on the same amount of data, i.e. the profile size. Furthermore, LSQ requires
+less operations than SPL, implying a smaller output latency. In total, LSQ
+turns out to be the best candidate for phase computation on any architecture
+including FPGA.
+
+\section{VHDL implementation and experimental tests}
+
+\label{Experimental tests}
+
+\subsection{VHDL implementation}
+
+From the LSQ algorithm, we have written a C program that uses only
+integer values. We used a very simple quantization which consists in
+multiplying each double precision value by a factor power of two and
+by keeping the integer part. For an accurate evaluation of the
+division in the computation of $a$ the slope coefficient, we also
+scaled the pixel intensities by another power of two. The main problem
+was to determin these factors. Most of the time, they are chosen to
+minimize the error induced by the quantization. But in our case, we
+also have some hardware constraints, for example the size and depth of
+RAMs or the input size of DSPs. Thus, having a maximum of values that
+fit in these sizes is a very important criterion to choose the scaling
+factors.
+
+Consequently, we have determined the maximum value of each variable as
+a function of the scale factors and the profile size involved in the
+algorithm. It gave us the the maximum number of bits necessary to code
+them. We have chosen the scale factors so that any variable (except
+the covariance) fits in 18 bits, which is the maximum input size of
+DSPs. In this way, all multiplications, except one, could be done with
+a single DSP, in a single clock cycle. Moreover, assuming that $nb_s =
+1024$, all LUTs could fit in the 18Kbits RAMs. Finally, we compared
+the double and integer versions of LSQ and found a nearly perfect
+agreement between their results.
+
+As mentionned above, some operations like divisions must be
+avoided. But when the denominator is fixed, a division can be replaced
+by its multiplication/shift counterpart. This is always the case in
+LSQ. For example, assuming that $M$ is fixed, $x_{var}$ is known and
+fixed. Thus, $\frac{xy_{covar}}{x_{var}}$ can be replaced by
+
+\[ (xy_{covar}\times \left \lfloor\frac{2^n}{x_{var}} \right \rfloor) \gg n\]
+
+where $n$ depends on the desired precision (in our case $n=24$).
+
+Obviously, multiplications and divisions by a power of two can be
+replaced by left or right bit shifts. Finally, the code only contains
+shifts, additions, subtractions and multiplications of signed integers, which
+are perfectly adapted to FGPAs.
+
+
+We built two versions of VHDL codes, namely one directly by hand
+coding and the other with Matlab using the Simulink HDL coder feature~\cite%
+{HDLCoder}. Although the approaches are completely different we obtained
+quite comparable VHDL codes. Each approach has advantages and drawbacks.
+Roughly speaking, hand coding provides beautiful and much better structured
+code while Simulind HDL coder produces allows for fast code production. In
+terms of throughput and latency, simulations show that the two approaches
+yield close results with a slight advantage for hand coding.
+
+\subsection{Simulation}
+
+Before experimental tests on the FPGA board, we simulated our two VHDL
+codes with GHDL and GTKWave (two free tools with linux). We built a
+testbench based on experimental profiles and compared the results to
+values given by the SPL algorithm. Both versions lead to correct
+results. Our first codes were highly optimized, indeed the pipeline
+could compute a new phase each 33 cycles and its latency was equal to
+95 cycles. Since the Spartan6 is clocked at 100MHz, estimating the
+deflection of 100 cantilevers would take about $%
+(95+200\times 33).10=66.95\mu $s, i.e. nearly 15,000 estimations by
+second.
+
+\subsection{Bitstream creation}
+
+In order to test our code on the SP Vision board, the design was
+extended with a component that keeps profiles in RAM, flushes them in
+the phase computation component and stores its output in another
+RAM. We also added a wishbone, a component that can "drive" signals to
+communicate between i.MX and other components. It is mainly used to
+start to flush profiles and to retrieve the computed phases in
+RAM. Unfortunately, the first designs could not be placed and routed
+with ISE on the Spartan6 with a 100MHz clock. The main problems were
+encountered with series of arthmetic operations and more especially
+with RAM outputs used in DSPs. So, we needed to decompose some parts
+of the pipeline, which added few clock cycles. Finally, we obtained a
+bitstream that has been successfully tested on the board.
+
+Its latency is of 112 cycles and computes a new phase every 40
+cycles. For 100 cantilevers, it takes $(112+200\times 40).10=81.12\mu
+$s to compute their deflection. It corresponds to about 12300 images
+per second, which is largely beyond the camera capacities and the
+possibility to extract a new profile from an image every 40
+cycles. Nevertheless, it also largely fits our design goals.
