1 |
dashley |
6 |
%$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
|