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