/[dtapublic]/pubs/books/ucbka/trunk/c_qua0/c_qua0.tex
ViewVC logotype

Annotation of /pubs/books/ucbka/trunk/c_qua0/c_qua0.tex

Parent Directory Parent Directory | Revision Log Revision Log


Revision 6 - (hide annotations) (download) (as text)
Fri Oct 7 01:36:46 2016 UTC (6 years, 3 months ago) by dashley
File MIME type: application/x-tex
File size: 8303 byte(s)
Initial commit after migrating from CVS.
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

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25