%$Header$ \chapter{\cquazerolongtitle{}} \label{cqua0} \section{Introduction} %Section tag INT A microcontroller can inherently manipulate only integers: usually 8-bit integers, 16-bit integers, or 32-bit integers. Typically, the less expensive a microcontroller is, the smaller the maximum data sizes that it can accomodate; the least expensive devices can easily manipulate only integers no larger than 8 bits. This chapter deals with the error analysis of \emph{quantization}. By \emph{quantization}, we mean three [distinct] mechanisms of error introduction in microcontroller software. \begin{itemize} \item \textbf{Input Quantization:} the unavoidable conversion from $\vworkrealset$ to $\vworkintset$ performed by interface hardware. For example, interface hardware may convert a voltage which is conceptually continuous to an integer (which can assume only discrete values), or may convert a time period which is conceptually continuous to an integer. \item \textbf{Arithmetic Quantization:} microcontroller arithmetic algorithms must often discard precision in order to restrict intermediate results of calculations to data sizes which the microcontroller can economically manipulate. This type of quantization error is most often injected by discarding the remainder of an integer quotient. \item \textbf{Output Quantization:} microcontroller output hardware can produce continuous outputs (such as voltages or pulse widths) only in discrete steps. Often, this lack of ability to control outputs precisely introduces additional uncertainty into the system which must be analyzed. \end{itemize} Note that the error-injection mechanism that we call \emph{quantization} (in some sense, the creation of a discrete-\emph{data} system) is not related to and is orthogonal to the notion of a discrete-\emph{time} (or sampled) system. \section{Modeling Of Quantization} %Section tag: MOQ For the analytical treatment of quantization, the \emph{floor($\cdot{}$)} function, denoted $\lfloor \cdot \rfloor$, is used, often preceded by a scaling factor. For example, in the case of an A/D converter which converts a voltage $\in [0, 5]$ volts into an integer $\in [0,255]_{\vworkintsetnonneg{}}$, we may model the function which maps from voltage to A/D count as $$\label{eq:cqua0:smoq:001} f(x) = \left\lfloor {\frac{255 x }{5}} \right\rfloor .$$ Inherent in (\ref{eq:cqua0:smoq:001}) is the assumption that quantization will choose an integer by rounding \emph{down}. Other assumptions are possible (\ref{eq:cqua0:smoq:002}, \ref{eq:cqua0:smoq:003}). $$\label{eq:cqua0:smoq:002} f(x) = \left\lceil {\frac{255 x }{5}} \right\rceil$$ $$\label{eq:cqua0:smoq:003} f(x) = \left\lfloor {\frac{255 x }{5} + \frac{1}{2}} \right\rfloor$$ At first glance, it may seem intuitively likely that (\ref{eq:cqua0:smoq:003}) leads to smaller error terms than (\ref{eq:cqua0:stqn:001}) or (\ref{eq:cqua0:smoq:002})---that rounding to the nearest integer is a better strategy than rounding down or rounding up. In this case, intuition may be misleading. (\ref{eq:cqua0:smoq:003}) more precisely \emph{centers the expected value} of the error than (\ref{eq:cqua0:smoq:001}) or (\ref{eq:cqua0:smoq:002}), but the \emph{span} of the error---the largest error minus the smallest error---remains one. In a practical system, the \emph{span} of the error is the dominant effect. In practice, (\ref{eq:cqua0:smoq:001}), (\ref{eq:cqua0:smoq:002}), and (\ref{eq:cqua0:smoq:003}) lead to near-identical error terms. For algebraic convenience, (\ref{eq:cqua0:smoq:001}) is used preferentially. Error terms are denoted by the Greek letter \emph{epsilon} ($\varepsilon$) and are viewed as the perturbation to the ideal'' to yield the actual''; so that a negative error term leads to a result less than than it should'' be, and a positive error term leads to a result greater than it should'' be. If the \emph{floor($\cdot{}$)} is used to model quantization, the relationship in (\ref{eq:cqua0:smoq:004}) holds. $$\label{eq:cqua0:smoq:004} \lfloor x \rfloor = x - \varepsilon{}; \; \varepsilon \in [0,1)$$ \section{Error Analysis Of Addition Of Quantized Inputs} %Section tag: eaqi If we add two quantized values $\lfloor a \rfloor$ and $\lfloor b \rfloor$, both $a$ and $b$ contain quantization error, and a question of interest is how much error the sum $\lfloor a \rfloor + \lfloor b \rfloor$ may contain; that is, how different it may be from $a+b$.\footnote{For addition and subtraction, this question is nearly trivial; but for multiplication and division the relationships are more complex; and for an arbitrary network of addition, subtraction, multiplication, and division we are not sure how to answer this question easily. Please see \ldots{}.} We seek an inequality which bounds $$\label{eq:cqua0:eaqi:001} \varepsilon{} = \left( {\lfloor a \rfloor + \lfloor b \rfloor} \right) - \left( {a + b} \right) .$$ Noting that quantization introduces an error $\varepsilon \in [0,1)$ (Eq. \ref{eq:cqua0:stqn:004}) leads to (\ref{eq:cqua0:eaqi:002}) and (\ref{eq:cqua0:eaqi:003}), which are equivalent statements. $$\label{eq:cqua0:eaqi:002} a + b - 2 < \lfloor a \rfloor + \lfloor b \rfloor \leq a + b$$ $$\label{eq:cqua0:eaqi:003} \varepsilon \in (-2,0]$$ Extending (\ref{eq:cqua0:eaqi:002}) and (\ref{eq:cqua0:eaqi:003}) to an arbitrary number $N \in \vworkintsetpos{}$ of quantized inputs leads to (\ref{eq:cqua0:eaqi:004}) and (\ref{eq:cqua0:eaqi:005}), which are equivalent statements. $$\label{eq:cqua0:eaqi:004} \sum_{i=1}^{N} x_i - N < \sum_{i=1}^{N} \lfloor x_i \rfloor \leq \sum_{i=1}^{N} x_i$$ $$\label{eq:cqua0:eaqi:005} \varepsilon \in (-N,0]$$ \section{Error Analysis Of Subtraction Of Quantized Inputs} \section{Error Analysis Of Multiplication Of Quantized Inputs} \section{Error Analysis Of Division Of Quantized Inputs} $$\frac{p-1}{q} < \frac{\lfloor p \rfloor}{\lfloor q \rfloor} < \frac{p}{q-1}; \; p,q > 1$$ \section{Error Analysis Of Arbitrary Algebraic Functions} \section{Error Analysis Of Rational Sweeps} \section{Exercises} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \noindent\begin{figure}[!b] \noindent\rule[-0.25in]{\textwidth}{1pt} \begin{tiny} \begin{verbatim} $HeadURL$ $Revision$ $Date$ $Author$ \end{verbatim} \end{tiny} \noindent\rule[0.25in]{\textwidth}{1pt} \end{figure} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % %End of file C_QUA0.TEX