Parent Directory | Revision Log

Revision **6** -
(**hide annotations**)
(**download**)
(**as text**)

*Fri Oct 7 01:36:46 2016 UTC*
(7 years, 9 months ago)
by *dashley*

File MIME type: application/x-tex

File size: 8303 byte(s)

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 |