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

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

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 139 by dashley, Fri Oct 7 01:36:46 2016 UTC revision 140 by dashley, Mon Jul 3 01:59:16 2017 UTC
# Line 1  Line 1 
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

Legend:
Removed from v.139  
changed lines
  Added in v.140

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25