trunk/c_qua0/c_qua0.tex

%$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 $

\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

\begin{equation}
\label{eq:cqua0:smoq:001}
f(x) = \left\lfloor {\frac{255 x }{5}} \right\rfloor .
\end{equation}

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}).

\begin{equation}
\label{eq:cqua0:smoq:002}
f(x) = \left\lceil {\frac{255 x }{5}} \right\rceil
\end{equation}

\begin{equation}
\label{eq:cqua0:smoq:003}
f(x) = \left\lfloor {\frac{255 x }{5} + \frac{1}{2}} \right\rfloor
\end{equation}

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.

\begin{equation}
\label{eq:cqua0:smoq:004}
\lfloor x \rfloor = x - \varepsilon{}; \; \varepsilon \in [0,1)
\end{equation}


\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

\begin{equation}
\label{eq:cqua0:eaqi:001}
\varepsilon{} = \left( {\lfloor a \rfloor + \lfloor b \rfloor} \right)
                      - \left( {a + b} \right)  .
\end{equation}

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.

\begin{equation}
\label{eq:cqua0:eaqi:002}
a + b - 2 < \lfloor a \rfloor + \lfloor b \rfloor \leq a + b
\end{equation}

\begin{equation}
\label{eq:cqua0:eaqi:003}
\varepsilon \in (-2,0]
\end{equation}

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.

\begin{equation}
\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
\end{equation}

\begin{equation}
\label{eq:cqua0:eaqi:005}
\varepsilon \in (-N,0]
\end{equation}

\section{Error Analysis Of Subtraction Of Quantized Inputs}

\section{Error Analysis Of Multiplication Of Quantized Inputs}

\section{Error Analysis Of Division Of Quantized Inputs}

\begin{equation}
\frac{p-1}{q}
<
\frac{\lfloor p \rfloor}{\lfloor q \rfloor}
<
\frac{p}{q-1}; \; p,q > 1
\end{equation}

\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}
$RCSfile: c_qua0.tex,v $
$Source: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_qua0/c_qua0.tex,v $
$Revision: 1.3 $
$Author: dtashley $
$Date: 2001/06/29 23:40:53 $
\end{verbatim}
\end{tiny}
\noindent\rule[0.25in]{\textwidth}{1pt}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% $Log: c_qua0.tex,v $
% Revision 1.3  2001/06/29 23:40:53  dtashley
% Spelling mistake corrected.
%
% Revision 1.2  2001/06/29 23:39:56  dtashley
% Conversion from binary to CVS archives.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% $History: c_qua0.tex $
% 
% *****************  Version 3  *****************
% User: Dashley1     Date: 12/22/00   Time: 12:56a
% Updated in $/uC Software Multi-Volume Book (A)/Chapter, QUA0, Quantization
% Tcl automated method of build refined.
% 
% *****************  Version 2  *****************
% User: David T. Ashley Date: 7/11/00    Time: 8:30p
% Updated in $/uC Software Multi-Volume Book (A)/Chapter, QUA0, Quantization
% Separation and enhancement of quantization chapter.
%
% *****************  Version 1  *****************
% User: David T. Ashley Date: 7/11/00    Time: 6:07p
% Created in $/uC Software Multi-Volume Book (A)/Chapter, QUA0, Quantization
% Initial check-in.
%
%End of file C_QUA0.TEX
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