1 |
dashley |
140 |
%$Header$ |
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 |
dashley |
278 |
$HeadURL$ |
188 |
|
|
$Revision$ |
189 |
|
|
$Date$ |
190 |
|
|
$Author$ |
191 |
dashley |
140 |
\end{verbatim} |
192 |
|
|
\end{tiny} |
193 |
|
|
\noindent\rule[0.25in]{\textwidth}{1pt} |
194 |
|
|
\end{figure} |
195 |
|
|
|
196 |
dashley |
278 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
197 |
dashley |
140 |
% |
198 |
|
|
%End of file C_QUA0.TEX |