Parent Directory | Revision Log

Revision **278** -
(**show annotations**)
(**download**)
(**as text**)

*Wed Aug 14 23:10:36 2019 UTC*
(4 years, 6 months ago)
by *dashley*

File MIME type: application/x-tex

File size: 6852 byte(s)

File MIME type: application/x-tex

File size: 6852 byte(s)

Change keyword substitution (migration from cvs to svn).

1 | %$Header$ |

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

188 | $Revision$ |

189 | $Date$ |

190 | $Author$ |

191 | \end{verbatim} |

192 | \end{tiny} |

193 | \noindent\rule[0.25in]{\textwidth}{1pt} |

194 | \end{figure} |

195 | |

196 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |

197 | % |

198 | %End of file C_QUA0.TEX |

Name | Value |
---|---|

svn:eol-style |
native |

svn:keywords |
Author Date Id Revision URL Header |

dashley@gmail.com | ViewVC Help |

Powered by ViewVC 1.1.25 |