 # Contents of /pubs/books/ucbka/trunk/c_qua0/c_qua0.tex

Initial commit after migrating from CVS.

 1 %$Header: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_qua0/c_qua0.tex,v 1.3 2001/06/29 23:40:53 dtashley Exp$ 2 3 \chapter{\cquazerolongtitle{}} 4 5 \label{cqua0} 6 7 \section{Introduction} 8 %Section tag INT 9 10 A microcontroller can inherently manipulate only integers: usually 8-bit 11 integers, 16-bit integers, or 32-bit integers. Typically, the less 12 expensive a microcontroller is, the smaller the maximum data sizes that 13 it can accomodate; the least expensive devices can easily manipulate 14 only integers no larger than 8 bits. 15 16 This chapter deals with the error analysis of \emph{quantization}. By 17 \emph{quantization}, we mean three [distinct] mechanisms of error introduction 18 in microcontroller software. 19 20 \begin{itemize} 21 \item \textbf{Input Quantization:} the unavoidable conversion from 22 $\vworkrealset$ to $\vworkintset$ performed by interface hardware. 23 For example, interface hardware may convert a voltage which is 24 conceptually continuous to an integer (which can assume only discrete 25 values), or may convert a time period which is conceptually 26 continuous to an integer. 27 \item \textbf{Arithmetic Quantization:} microcontroller arithmetic algorithms 28 must often discard precision in order to restrict intermediate results of 29 calculations to data sizes which the microcontroller can economically 30 manipulate. This type of quantization error is most often injected 31 by discarding the remainder of an integer quotient. 32 \item \textbf{Output Quantization:} microcontroller output hardware can 33 produce continuous outputs (such as voltages or pulse widths) 34 only in discrete steps. Often, this lack of ability to control 35 outputs precisely introduces additional uncertainty into the 36 system which must be analyzed. 37 \end{itemize} 38 39 Note that the error-injection mechanism that we call \emph{quantization} 40 (in some sense, the creation of a discrete-\emph{data} system) 41 is not related to and is orthogonal to the notion of a 42 discrete-\emph{time} (or sampled) system. 43 44 45 \section{Modeling Of Quantization} 46 %Section tag: MOQ 47 48 For the analytical treatment of quantization, the \emph{floor($\cdot{}$)} 49 function, denoted $\lfloor \cdot \rfloor$, is used, often preceded by a 50 scaling factor. For example, in the case of an A/D converter which 51 converts a voltage $\in [0, 5]$ volts into an integer 52 $\in [0,255]_{\vworkintsetnonneg{}}$, we may model the function which 53 maps from voltage to A/D count as 54 55 \begin{equation} 56 \label{eq:cqua0:smoq:001} 57 f(x) = \left\lfloor {\frac{255 x }{5}} \right\rfloor . 58 \end{equation} 59 60 Inherent in (\ref{eq:cqua0:smoq:001}) 61 is the assumption that quantization will 62 choose an integer by rounding \emph{down}. Other 63 assumptions are possible 64 (\ref{eq:cqua0:smoq:002}, \ref{eq:cqua0:smoq:003}). 65 66 \begin{equation} 67 \label{eq:cqua0:smoq:002} 68 f(x) = \left\lceil {\frac{255 x }{5}} \right\rceil 69 \end{equation} 70 71 \begin{equation} 72 \label{eq:cqua0:smoq:003} 73 f(x) = \left\lfloor {\frac{255 x }{5} + \frac{1}{2}} \right\rfloor 74 \end{equation} 75 76 At first glance, it may seem intuitively likely 77 that (\ref{eq:cqua0:smoq:003}) leads 78 to smaller error terms than (\ref{eq:cqua0:stqn:001}) 79 or (\ref{eq:cqua0:smoq:002})---that rounding to the 80 nearest integer is a better strategy than rounding 81 down or rounding up. In this case, intuition may be misleading. 82 (\ref{eq:cqua0:smoq:003}) more precisely \emph{centers the 83 expected value} of the error than (\ref{eq:cqua0:smoq:001}) 84 or (\ref{eq:cqua0:smoq:002}), but the \emph{span} of the 85 error---the largest error minus the smallest error---remains 86 one. In a practical system, the \emph{span} of the error 87 is the dominant effect. In practice, 88 (\ref{eq:cqua0:smoq:001}), (\ref{eq:cqua0:smoq:002}), 89 and (\ref{eq:cqua0:smoq:003}) lead to near-identical 90 error terms. For algebraic convenience, 91 (\ref{eq:cqua0:smoq:001}) is used preferentially. 92 93 Error terms are denoted by the Greek 94 letter \emph{epsilon} ($\varepsilon$) and 95 are viewed as the perturbation to the 96 ideal'' to yield the actual''; so that a negative error 97 term leads to a result less than than it 98 should'' be, and a positive 99 error term leads to a result greater than 100 it should'' be. If the \emph{floor($\cdot{}$)} 101 is used to model quantization, the relationship 102 in (\ref{eq:cqua0:smoq:004}) holds. 103 104 \begin{equation} 105 \label{eq:cqua0:smoq:004} 106 \lfloor x \rfloor = x - \varepsilon{}; \; \varepsilon \in [0,1) 107 \end{equation} 108 109 110 \section{Error Analysis Of Addition Of Quantized Inputs} 111 %Section tag: eaqi 112 113 If we add two quantized values $\lfloor a \rfloor$ and 114 $\lfloor b \rfloor$, both $a$ and $b$ contain quantization 115 error, and a question of interest is how much 116 error the sum $\lfloor a \rfloor + \lfloor b \rfloor$ may 117 contain; that is, how different it may be from $a+b$.\footnote{For 118 addition and subtraction, this question is nearly trivial; but for 119 multiplication and division the relationships are more complex; and for 120 an arbitrary network of addition, subtraction, multiplication, and 121 division we are not sure how to answer this question easily. 122 Please see \ldots{}.} 123 We seek an inequality which bounds 124 125 \begin{equation} 126 \label{eq:cqua0:eaqi:001} 127 \varepsilon{} = \left( {\lfloor a \rfloor + \lfloor b \rfloor} \right) 128 - \left( {a + b} \right) . 129 \end{equation} 130 131 Noting that quantization introduces an error $\varepsilon \in [0,1)$ 132 (Eq. \ref{eq:cqua0:stqn:004}) leads to 133 (\ref{eq:cqua0:eaqi:002}) and (\ref{eq:cqua0:eaqi:003}), which are equivalent statements. 134 135 \begin{equation} 136 \label{eq:cqua0:eaqi:002} 137 a + b - 2 < \lfloor a \rfloor + \lfloor b \rfloor \leq a + b 138 \end{equation} 139 140 \begin{equation} 141 \label{eq:cqua0:eaqi:003} 142 \varepsilon \in (-2,0] 143 \end{equation} 144 145 Extending (\ref{eq:cqua0:eaqi:002}) and (\ref{eq:cqua0:eaqi:003}) 146 to an arbitrary number $N \in \vworkintsetpos{}$ of quantized inputs leads to 147 (\ref{eq:cqua0:eaqi:004}) and (\ref{eq:cqua0:eaqi:005}), 148 which are equivalent statements. 149 150 \begin{equation} 151 \label{eq:cqua0:eaqi:004} 152 \sum_{i=1}^{N} x_i - N < \sum_{i=1}^{N} \lfloor x_i \rfloor \leq \sum_{i=1}^{N} x_i 153 \end{equation} 154 155 \begin{equation} 156 \label{eq:cqua0:eaqi:005} 157 \varepsilon \in (-N,0] 158 \end{equation} 159 160 \section{Error Analysis Of Subtraction Of Quantized Inputs} 161 162 \section{Error Analysis Of Multiplication Of Quantized Inputs} 163 164 \section{Error Analysis Of Division Of Quantized Inputs} 165 166 \begin{equation} 167 \frac{p-1}{q} 168 < 169 \frac{\lfloor p \rfloor}{\lfloor q \rfloor} 170 < 171 \frac{p}{q-1}; \; p,q > 1 172 \end{equation} 173 174 \section{Error Analysis Of Arbitrary Algebraic Functions} 175 176 \section{Error Analysis Of Rational Sweeps} 177 178 \section{Exercises} 179 180 181 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 182 183 \noindent\begin{figure}[!b] 184 \noindent\rule[-0.25in]{\textwidth}{1pt} 185 \begin{tiny} 186 \begin{verbatim} 187 $RCSfile: c_qua0.tex,v$ 188 $Source: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_qua0/c_qua0.tex,v$ 189 $Revision: 1.3$ 190 $Author: dtashley$ 191 $Date: 2001/06/29 23:40:53$ 192 \end{verbatim} 193 \end{tiny} 194 \noindent\rule[0.25in]{\textwidth}{1pt} 195 \end{figure} 196 197 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 198 % $Log: c_qua0.tex,v$ 199 % Revision 1.3 2001/06/29 23:40:53 dtashley 200 % Spelling mistake corrected. 201 % 202 % Revision 1.2 2001/06/29 23:39:56 dtashley 203 % Conversion from binary to CVS archives. 204 % 205 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 206 % $History: c_qua0.tex$ 207 % 208 % ***************** Version 3 ***************** 209 % User: Dashley1 Date: 12/22/00 Time: 12:56a 210 % Updated in $/uC Software Multi-Volume Book (A)/Chapter, QUA0, Quantization 211 % Tcl automated method of build refined. 212 % 213 % ***************** Version 2 ***************** 214 % User: David T. Ashley Date: 7/11/00 Time: 8:30p 215 % Updated in$/uC Software Multi-Volume Book (A)/Chapter, QUA0, Quantization 216 % Separation and enhancement of quantization chapter. 217 % 218 % ***************** Version 1 ***************** 219 % User: David T. Ashley Date: 7/11/00 Time: 6:07p 220 % Created in \$/uC Software Multi-Volume Book (A)/Chapter, QUA0, Quantization 221 % Initial check-in. 222 % 223 %End of file C_QUA0.TEX