Parent Directory | Revision Log

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

*Mon Jul 3 01:59:16 2017 UTC*
(7 years, 1 month ago)
by *dashley*

File MIME type: application/x-tex

File size: 22240 byte(s)

File MIME type: application/x-tex

File size: 22240 byte(s)

Change SVN properties for EOL and keyword expansion.

1 | dashley | 140 | %$Header$ |

2 | |||

3 | \chapter[\cdtazeroshorttitle{}]{\cdtazerolongtitle{}} | ||

4 | |||

5 | \label{cdta0} | ||

6 | |||

7 | \beginchapterquote{``Under construction!''} | ||

8 | {Under construction!} | ||

9 | |||

10 | |||

11 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

12 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

13 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

14 | \section{Introduction} | ||

15 | %Section tag: INT0 | ||

16 | \label{cdta0:sint0} | ||

17 | |||

18 | |||

19 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

20 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

21 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

22 | \section[Fixed-Period Process Scheduling] | ||

23 | {Load Balancing For Fixed-Period Process Scheduling Using Integer Counting} | ||

24 | %Section tag: PSI0 | ||

25 | \label{cdta0:spsi0} | ||

26 | |||

27 | \index{process scheduling!using integer counting}It happens in a variety of | ||

28 | contexts in small microcontroller work | ||

29 | that one schedules processes (which may be implemented as subroutines | ||

30 | or functions) with a fixed period | ||

31 | using integer counting. Such scheduling tends to take the form of | ||

32 | the code snippet in | ||

33 | Figure \ref{fig:cdta0:spsi0:01}. Typically a ``master'' scheduling function | ||

34 | is called at a periodic rate, and the scheduled functions are called | ||

35 | once every $T_i$ invocations of the master scheduling function ($T_i$ is | ||

36 | defined later). Note in the figure that every scheduled function | ||

37 | is called with perfect periodicity, but that the invocation sequence | ||

38 | can be staggered. Note also in the figure that the comments assume | ||

39 | that the scheduling function is called every 10ms (which is typical in | ||

40 | microcontroller work). | ||

41 | |||

42 | \begin{figure} | ||

43 | \begin{small} | ||

44 | \begin{verbatim} | ||

45 | /* The following "stagger" values are what we are attempting to | ||

46 | ** analytically determine at compile-time so as to minimize the | ||

47 | ** maximum CPU time used in the worst-case tick. */ | ||

48 | #define P1_STAGGER (0) | ||

49 | #define P2_STAGGER (0) | ||

50 | #define P3_STAGGER (0) | ||

51 | |||

52 | /* The periods are fixed and not subject to change. The periods | ||

53 | ** are input to any compile-time algorithm employed. */ | ||

54 | #define P1_PERIOD (2) /* Every 20ms. */ | ||

55 | #define P2_PERIOD (5) /* Every 100ms. */ | ||

56 | #define P3_PERIOD (100) /* Every 1000ms = 1 second. */ | ||

57 | |||

58 | /* These are the integer counters. Their initial load values, which | ||

59 | ** determine the staggering, are the parameters we seek to | ||

60 | ** determine. */ | ||

61 | static unsigned char p1_ctr = P1_STAGGER; | ||

62 | static unsigned char p2_ctr = P2_STAGGER; | ||

63 | static unsigned char p3_ctr = P3_STAGGER; | ||

64 | |||

65 | /* This is the master scheduling function called every 10ms. It | ||

66 | ** calls the periodic functions. Note that this is an integer | ||

67 | ** counting problem. */ | ||

68 | void master_scheduling_function(void) | ||

69 | { | ||

70 | p1_ctr++; | ||

71 | if (p1_ctr >= P1_PERIOD) | ||

72 | { | ||

73 | Process_1(); /* Call the process. */ | ||

74 | p1_ctr = 0; /* Reset the counter. */ | ||

75 | } | ||

76 | p2_ctr++; | ||

77 | if (p2_ctr >= P2_PERIOD) | ||

78 | { | ||

79 | Process_2(); /* Call the process. */ | ||

80 | p2_ctr = 0; /* Reset the counter. */ | ||

81 | } | ||

82 | p3_ctr++; | ||

83 | if (p3_ctr >= P3_PERIOD) | ||

84 | { | ||

85 | Process_3(); /* Call the process. */ | ||

86 | p3_ctr = 0; /* Reset the counter. */ | ||

87 | } | ||

88 | } | ||

89 | \end{verbatim} | ||

90 | \end{small} | ||

91 | \caption{Code Snippet Illustrating Fixed-Period Integer Counter Process Scheduling | ||

92 | (3 Processes)} | ||

93 | \label{fig:cdta0:spsi0:01} | ||

94 | \end{figure} | ||

95 | |||

96 | |||

97 | It is easy to see from Figure \ref{fig:cdta0:spsi0:01} that it may happen | ||

98 | on a single invocation of the master scheduling function that several or all of | ||

99 | the processes are scheduled. If the scheduling of the | ||

100 | processes is not staggered, this will happen for the first time | ||

101 | on the invocation (or ``tick'') | ||

102 | corresponding to the least common multiple of all of the periods. In | ||

103 | the case of Figure \ref{fig:cdta0:spsi0:01}, $LCM(2,5,100) = 100$, and so | ||

104 | on the hundredth invocation of the master scheduling function, all three processes will | ||

105 | run. It may be undesirable to run all three processes on the same invocation of | ||

106 | the master scheduling function, because this may require a large amount of CPU time. | ||

107 | The general question to which we seek an answer is: \emph{How should the | ||

108 | stagger values be chosen so as to minimize the maximum amount of CPU | ||

109 | time taken on any invocation of the master scheduling function?} | ||

110 | |||

111 | We denote the set of $N$ processes that we must schedule | ||

112 | by $\{ P_1, P_2, \ldots , P_N \}$. | ||

113 | Process $P_i$ has period $T_i$ (measured in invocations | ||

114 | or ``ticks'' of | ||

115 | the master scheduling function, or ``ticks''). Note that | ||

116 | $T_i$ is dimensionless. | ||

117 | |||

118 | Each process $P_i$ also has cost | ||

119 | $\tau_i$ | ||

120 | (the cost is usually the execution | ||

121 | time of the function, but could in principle represent any property of | ||

122 | interest). Note that there is no required relationship between | ||

123 | $\{ T_i \}$ and $\{ \tau_i \}$, as we are not determining schedulability. | ||

124 | Thus $\{ \tau_i \}$ may be specified in any time unit, or it may not | ||

125 | represent time at all. | ||

126 | |||

127 | We agree that each invocation of the master scheduling function | ||

128 | is one ``tick'' in discrete time, and that the first invocation | ||

129 | of the master scheduling function is denoted $t_1$ or $t=1$. | ||

130 | With no staggering ($z_i = 0$) each process $P_i$ will run | ||

131 | whenever | ||

132 | |||

133 | \begin{equation} | ||

134 | \label{eq:cdta0:spsi0:01} | ||

135 | t \bmod T_i = 0 . | ||

136 | \end{equation} | ||

137 | |||

138 | We may modify the invocation sequence of a process $P_i$ by | ||

139 | varying a stagger value, which we denote $z_i$. The stagger value | ||

140 | specifies by how many ticks we will advance the invocation of | ||

141 | $P_i$. When considering stagger values, each process $P_i$ will | ||

142 | run whenever | ||

143 | |||

144 | \begin{equation} | ||

145 | \label{eq:cdta0:spsi0:02} | ||

146 | (t + z_i) \bmod T_i = 0 . | ||

147 | \end{equation} | ||

148 | |||

149 | At each tick, each process $P_i$ is either scheduled to run or not scheduled | ||

150 | to run. We define an infinite row vector, called the \emph{uncosted invocation | ||

151 | sequence} (or simply the \emph{invocation sequence}) | ||

152 | and denoted $\rho_i(z_i)$, which contains a `1' in each column corresponding | ||

153 | to a tick when the process $P_i$ run or `0' if it does not run. For example, | ||

154 | if $T_1 = 3$, | ||

155 | |||

156 | \begin{eqnarray} | ||

157 | \nonumber | ||

158 | \rho_1 = \rho_1(0) & = & [ \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; \ldots \; ] \\ | ||

159 | \label{eq:cdta0:spsi0:03} | ||

160 | \rho_1(1) & = & [ \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; \ldots \; ] \\ | ||

161 | \nonumber | ||

162 | \rho_1(2) & = & [ \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; \ldots \; ] \\ | ||

163 | \nonumber | ||

164 | \rho_1(3) & = & [ \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; \ldots \; ] | ||

165 | \end{eqnarray} | ||

166 | |||

167 | \noindent{}We define but avoid using stagger values $z_i \geq T_i$, but as | ||

168 | (\ref{eq:cdta0:spsi0:03}) shows, when it is necessary we define these so that | ||

169 | $\rho_i(z_i) = \rho_i(z_i \bmod T_i)$. Also as shown in (\ref{eq:cdta0:spsi0:03}), | ||

170 | we use that notation | ||

171 | that $\rho_i = \rho_i(0)$. | ||

172 | |||

173 | We define the \emph{costed invocation sequence}, denoted | ||

174 | $\overline{\rho_i}(z_i)$, as the infinite row | ||

175 | vector similar to (\ref{eq:cdta0:spsi0:03}) but where | ||

176 | the cost $\tau_i$ is used in place of `1' when a process $P_i$ runs. | ||

177 | For example, if $T_1=3$ and $\tau_i = 5$, | ||

178 | |||

179 | \begin{eqnarray} | ||

180 | \nonumber | ||

181 | \overline{\rho_1} = | ||

182 | \overline{\rho_1}(0) & = & [ \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; \ldots \; ] \\ | ||

183 | \label{eq:cdta0:spsi0:04} | ||

184 | \overline{\rho_1}(1) & = & [ \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; \ldots \; ] \\ | ||

185 | \nonumber | ||

186 | \overline{\rho_1}(2) & = & [ \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; \ldots \; ] \\ | ||

187 | \nonumber | ||

188 | \overline{\rho_1}(3) & = & [ \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; \ldots \; ] | ||

189 | \end{eqnarray} | ||

190 | |||

191 | We define the \emph{cost calculation matrix} as the matrix formed by vertically | ||

192 | concatenating, in order, the first $LCM(T_1, \ldots , T_N)$ | ||

193 | columns of either the uncosted invocation sequence | ||

194 | $\rho_i(z_i)$ or the costed invocation sequence $\overline{\rho_i}(z_i)$ | ||

195 | of every process in the system; and then appending to this as a row vector | ||

196 | the sums of | ||

197 | each column. We choose only the first $LCM(T_1, \ldots , T_N)$ columns | ||

198 | because the contents of these columns repeat in subsequent columns forever. | ||

199 | We denote the cost calculation matrix as $\xi(\mathbf{z})$ (in the case | ||

200 | of the uncosted invocation sequences) or as $\overline{\xi}(\mathbf{z})$ | ||

201 | (in the case of the costed invocation sequences); where $\mathbf{z}$ is the | ||

202 | column vector consisting of all of the staggers $z_i$. Finally, we define the | ||

203 | \emph{cost}, denoted $\xi$, as the maximum element from the last row of the | ||

204 | cost calculation matrix (it is $\xi$ that we seek to minimize by choosing | ||

205 | $\mathbf{z}$). These definitions are illustrated in the following example. | ||

206 | |||

207 | \begin{vworkexamplestatement} | ||

208 | \label{ex:cdta0:spsi0:01} | ||

209 | For the system of 3 processes ($P_1$, $P_2$, and $P_3$) with | ||

210 | $T_1=6$, $T_2=4$, $T_3=3$, $\tau_1=2$, $\tau_2=7$, $\tau_3=5$, | ||

211 | $z_1 = 2$, $z_2 = 1$, and $z_3 = 0$, | ||

212 | form the uncosted and costed invocation sequences, the cost | ||

213 | calculation matrices, and the costs. | ||

214 | \end{vworkexamplestatement} | ||

215 | \begin{vworkexampleparsection}{Solution} | ||

216 | We first handle the uncosted case in full, followed by the costed | ||

217 | case in full. | ||

218 | |||

219 | \textbf{(Uncosted Case):} | ||

220 | With $T_1=6$ and $z_1=2$, the first invocation of $P_1$ will occur | ||

221 | when $(t + 2) \bmod 6 = 0$ (see Eq. \ref{eq:cdta0:spsi0:02}), at $t=4$, | ||

222 | and then repeat with periodicity 6. Thus | ||

223 | |||

224 | \begin{equation} | ||

225 | \label{eq:ex:cdta0:spsi0:01:01} | ||

226 | \rho_1(2) = [ \; 0 \; 0 \; 0 \; 1 \; 0 \; 0 \; 0 \; 0 \; 0 \; 1 \; | ||

227 | 0 \; 0 \; 0 \; 0 \; 0 \; 1 \; 0 \; \ldots \; ] . | ||

228 | \end{equation} | ||

229 | |||

230 | \noindent{}Applying the same definition for $P_2$ and $P_3$ yields | ||

231 | |||

232 | \begin{equation} | ||

233 | \label{eq:ex:cdta0:spsi0:01:02} | ||

234 | \rho_2(1) = [ \; 0 \; 0 \; 1 \; 0 \; 0 \; 0 \; 1 \; 0 \; 0 \; 0 \; | ||

235 | 1 \; 0 \; 0 \; 0 \; 1 \; 0 \; 0 \; \ldots \; ] | ||

236 | \end{equation} | ||

237 | |||

238 | \noindent{}and | ||

239 | |||

240 | \begin{equation} | ||

241 | \label{eq:ex:cdta0:spsi0:01:03} | ||

242 | \rho_3(0) = \rho_3 = [ \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; | ||

243 | 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; \ldots \; ] . | ||

244 | \end{equation} | ||

245 | |||

246 | We note that the column vector $\mathbf{z}$ is | ||

247 | |||

248 | \begin{equation} | ||

249 | \label{eq:ex:cdta0:spsi0:01:04} | ||

250 | \mathbf{z} | ||

251 | = | ||

252 | \left[\begin{array}{c}z_1\\z_2\\z_3\end{array}\right] | ||

253 | = | ||

254 | \left[\begin{array}{c}2\\1\\0\end{array}\right] . | ||

255 | \end{equation} | ||

256 | |||

257 | $LCM(T_1, T_2, T_3) = LCM(6, 4, 3) = 12$, and so the cost calculation matrix | ||

258 | can be constructed with only 12 columns, since the columns repeat with periodicity | ||

259 | 12: | ||

260 | |||

261 | \begin{equation} | ||

262 | \label{eq:ex:cdta0:spsi0:01:05} | ||

263 | \xi(\mathbf{z}) | ||

264 | = | ||

265 | \xi\left(\left[\begin{array}{c}2\\1\\0\end{array}\right]\right) | ||

266 | = | ||

267 | \left[ | ||

268 | \begin{array}{rrrrrrrrrrrr} | ||

269 | 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ | ||

270 | 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ | ||

271 | 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ | ||

272 | 0 & 0 & 2 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 1 | ||

273 | \end{array} | ||

274 | \right] | ||

275 | . | ||

276 | \end{equation} | ||

277 | |||

278 | Note in (\ref{eq:ex:cdta0:spsi0:01:05}) that the last row is | ||

279 | the column-wise sum of the rows above it. Note also that | ||

280 | the last row gives, on a per tick basis, the number of processes | ||

281 | that run. | ||

282 | |||

283 | The cost $\xi$ is the maximum of the last row of (\ref{eq:ex:cdta0:spsi0:01:05}), | ||

284 | and by inspection $\xi = 2$. | ||

285 | |||

286 | \textbf{(Costed Case):} | ||

287 | The costed invocation sequences are simply | ||

288 | (\ref{eq:ex:cdta0:spsi0:01:01}), (\ref{eq:ex:cdta0:spsi0:01:02}), and | ||

289 | (\ref{eq:ex:cdta0:spsi0:01:02}) with 1's replaced by the cost appropriate | ||

290 | to the process being considered; $\tau_1$, $\tau_2$, or $\tau_3$: | ||

291 | |||

292 | \begin{eqnarray} | ||

293 | \nonumber | ||

294 | \overline{\rho_1}(2) & = & [ \; 0 \; 0 \; 0 \; 2 \; 0 \; 0 \; 0 \; 0 \; 0 \; 2 \; | ||

295 | 0 \; 0 \; 0 \; 0 \; 0 \; 2 \; 0 \; \ldots \; ] \\ | ||

296 | \label{eq:ex:cdta0:spsi0:01:06} | ||

297 | \overline{\rho_2}(1) & = & [ \; 0 \; 0 \; 7 \; 0 \; 0 \; 0 \; 7 \; 0 \; 0 \; 0 \; | ||

298 | 7 \; 0 \; 0 \; 0 \; 7 \; 0 \; 0 \; \ldots \; ] \\ | ||

299 | \nonumber | ||

300 | \overline{\rho_3}(0) = \overline{\rho_3} & = & [ \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; | ||

301 | 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; \ldots \; ] | ||

302 | \end{eqnarray} | ||

303 | |||

304 | The cost calculation matrix in the costed case is formed by vertically concatenating the | ||

305 | first 12 columns of the rows of (\ref{eq:ex:cdta0:spsi0:01:06}), with the | ||

306 | final row containing columnwise sums: | ||

307 | |||

308 | \begin{equation} | ||

309 | \label{eq:ex:cdta0:spsi0:01:07} | ||

310 | \overline{\xi}(\mathbf{z}) | ||

311 | = | ||

312 | \overline{\xi}\left(\left[\begin{array}{c}2\\1\\0\end{array}\right]\right) | ||

313 | = | ||

314 | \left[ | ||

315 | \begin{array}{rrrrrrrrrrrr} | ||

316 | 0 & 0 & 0 & 2 & 0 & 0 & 0 & 0 & 0 & 2 & 0 & 0 \\ | ||

317 | 0 & 0 & 7 & 0 & 0 & 0 & 7 & 0 & 0 & 0 & 7 & 0 \\ | ||

318 | 0 & 0 & 5 & 0 & 0 & 5 & 0 & 0 & 5 & 0 & 0 & 5 \\ | ||

319 | 0 & 0 & 12 & 2 & 0 & 5 & 7 & 0 & 5 & 2 & 7 & 5 | ||

320 | \end{array} | ||

321 | \right] | ||

322 | . | ||

323 | \end{equation} | ||

324 | |||

325 | The cost $\overline{\xi}$ is the maximum of the last row of (\ref{eq:ex:cdta0:spsi0:01:07}), | ||

326 | and by inspection $\overline{\xi} = 12$. | ||

327 | \end{vworkexampleparsection} | ||

328 | \vworkexamplefooter{} | ||

329 | |||

330 | |||

331 | |||

332 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

333 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

334 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

335 | \section{Sine And Cosine} | ||

336 | %Section tag: sco0 | ||

337 | \label{cdta0:ssco0} | ||

338 | |||

339 | |||

340 | |||

341 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

342 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

343 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

344 | \section{Rotational Transformations In 2 Dimensions} | ||

345 | %Section tag: RTR2 | ||

346 | \label{cdta0:srtr2} | ||

347 | |||

348 | \index{rotation!2-D}It occurs often in microcontroller work that one needs to rotate | ||

349 | coordinates in 2 dimensions (Figure \ref{fig:cdta0:srtr2:01}). In this section, | ||

350 | the most economical algorithms known for 2-dimensional | ||

351 | rotation are discussed. We assume that the | ||

352 | point $\mathbf{p}$ to be rotated is specified in rectangular coordinates | ||

353 | $\mathbf{p} = (p_x, p_y)$ rather than polar coordinates | ||

354 | $\mathbf{p} = (r, \theta)$; since if $\mathbf{p}$ is specified in polar coordinates | ||

355 | rotation involves only addition to $\theta$ modulo $2\pi$. We denote the point to be | ||

356 | rotated $\mathbf{p} = (p_x, p_y) = \left[\begin{array}{c}p_x\\p_y\end{array}\right]$ | ||

357 | and the result of the rotation | ||

358 | $\mathbf{q} = (q_x, q_y) = \left[\begin{array}{c}q_x\\q_y\end{array}\right]$. | ||

359 | We denote the length of the vector represented by $\mathbf{p}$ or $\mathbf{q}$ | ||

360 | by $r$, and note that | ||

361 | $r = |\mathbf{p}| = \sqrt{p_x^2 + p_y^2} = |\mathbf{q}| = \sqrt{q_x^2 + q_y^2}$. | ||

362 | Because low-cost microcontrollers are used, we assume that | ||

363 | $p_x, p_y, q_x, q_y \in \vworkintset$. | ||

364 | We denote the desired amount of counter-clockwise rotation by $\delta$ (in radians). | ||

365 | |||

366 | \begin{figure} | ||

367 | \begin{huge} | ||

368 | \begin{center} | ||

369 | Reserved | ||

370 | \end{center} | ||

371 | \end{huge} | ||

372 | \caption{Rotation In 2 Dimensions} | ||

373 | \label{fig:cdta0:srtr2:01} | ||

374 | \end{figure} | ||

375 | |||

376 | A particularly na\"{\i}ve algorithm to use in microcontroller work is to | ||

377 | convert $\mathbf{p} = (p_x, p_y)$ to polar coordinates | ||

378 | $\mathbf{p} = (r, \theta)$, rotate to obtain | ||

379 | $\mathbf{q} = (r, (\theta + \delta) \bmod 2\pi)$, and then convert back to | ||

380 | rectangular coordinates $\mathbf{q} = (q_x, q_y)$. | ||

381 | This algorithm is na\"{\i}ve because trigonometric and | ||

382 | inverse trigonometric functions are required, which are not economical to implement | ||

383 | on microcontrollers. We seek if possible algorithms which operate exclusively in | ||

384 | rectangular coordinates and which require little or no evaluation of | ||

385 | trigonometric and inverse trigonometric functions. | ||

386 | |||

387 | |||

388 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

389 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

390 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

391 | \subsection{Matrix Rotation In 2 Dimensions} | ||

392 | %Section tag: MRT0 | ||

393 | \label{cdta0:srtr2:smrt2} | ||

394 | |||

395 | Assume we wish to rotate the vector | ||

396 | |||

397 | \begin{equation} | ||

398 | \label{eq:cdta0:srtr2:smrt2:01} | ||

399 | \mathbf{p} | ||

400 | = (p_x, p_y) | ||

401 | = \left[\begin{array}{c}p_x\\p_y\end{array}\right] | ||

402 | = (r \cos \theta, r \sin \theta) | ||

403 | = \left[\begin{array}{c}r \cos \theta\\r \sin \theta\end{array}\right] | ||

404 | \end{equation} | ||

405 | |||

406 | \noindent{}by an angle of $\delta$ to give the vector | ||

407 | |||

408 | \begin{eqnarray} | ||

409 | \label{eq:cdta0:srtr2:smrt2:02} | ||

410 | \mathbf{q} & = & (q_x, q_y) = \left[\begin{array}{c}q_x\\q_y\end{array}\right] \\ | ||

411 | \nonumber & = & (r \cos (\theta + \delta), r \sin (\theta + \delta)) | ||

412 | = \left[\begin{array}{c}r \cos (\theta + \delta)\\r \sin (\theta+\delta)\end{array}\right]. | ||

413 | \end{eqnarray} | ||

414 | |||

415 | \noindent{}Recall from standard trigonometry identities that for sines and cosines of | ||

416 | sums of angles that | ||

417 | |||

418 | \begin{eqnarray} | ||

419 | \label{eq:cdta0:srtr2:smrt2:03} | ||

420 | \left[\begin{array}{c}r \cos (\theta + \delta)\\r \sin (\theta+\delta)\end{array}\right] | ||

421 | & = & | ||

422 | \left[\begin{array}{c}r \cos \theta \cos \delta - r \sin \theta \sin \delta \\ | ||

423 | r \sin \theta \cos \delta + r \cos \theta \sin \delta \end{array}\right] \\ | ||

424 | \label{eq:cdta0:srtr2:smrt2:04} | ||

425 | & = & | ||

426 | \left[\begin{array}{c}p_x \cos \delta - p_y \sin \delta \\ | ||

427 | p_x \sin \delta + p_y \cos \delta \end{array}\right] \\ | ||

428 | \label{eq:cdta0:srtr2:smrt2:05} | ||

429 | & = & | ||

430 | \left[\begin{array}{c}q_x\\q_y\end{array}\right] | ||

431 | = | ||

432 | \left[\begin{array}{cc}\cos \delta & - \sin \delta \\ | ||

433 | \sin \delta & \;\;\;\cos \delta \end{array}\right] | ||

434 | \left[\begin{array}{c}p_x\\p_y\end{array}\right] . | ||

435 | \end{eqnarray} | ||

436 | |||

437 | \noindent{}Note that (\ref{eq:cdta0:srtr2:smrt2:05}) | ||

438 | reduces the rotation problem to four multiplications and two additions | ||

439 | (the matrix multiplication), provided that some approximation of the sine | ||

440 | and cosine functions is available (see Section \ref{cdta0:ssco0}). | ||

441 | |||

442 | To apply (\ref{eq:cdta0:srtr2:smrt2:05}), the embedded software | ||

443 | may or may not need to approximate the sine and cosine functions. | ||

444 | For some applications, if the angle of rotation is fixed, | ||

445 | $\sin \delta$ and | ||

446 | $\cos \delta$ may be calculated at compile time and tabulated in | ||

447 | ROM rather than $\delta$ (so that the embedded software does not need | ||

448 | to approximate these functions). For other applications, | ||

449 | sine and cosine must be approximated (see Section \ref{cdta0:ssco0}). | ||

450 | |||

451 | The 2 $\times$ 2 matrix in (\ref{eq:cdta0:srtr2:smrt2:05}) | ||

452 | is called the \index{rotation matrix}\emph{rotation matrix}. There are | ||

453 | other functionally equivalent ways to derive this result, including complex | ||

454 | arithmetic (i.e. phasor analysis) and graphical geometric arguments. | ||

455 | |||

456 | As pointed out in Section \ref{cdta0:ssco0}, the best way to approximate | ||

457 | sine and cosine in low cost microcontrollers is usually by tabulation of the | ||

458 | values of $\sin \delta$ for $\delta \in [0, \pi/2]$. Using the | ||

459 | techniques presented in Section \ref{cdta0:ssco0} for approximation of | ||

460 | sine and cosine and using (\ref{eq:cdta0:srtr2:smrt2:05}), rotation can usually | ||

461 | be carried out using around 20 machine instructions. | ||

462 | |||

463 | If a vector is rotated repeatedly using (\ref{eq:cdta0:srtr2:smrt2:05}), cumulative | ||

464 | truncation and rounding errors may eventually yield a vector | ||

465 | $\mathbf{q}$ with a significantly different | ||

466 | magnitude $|\mathbf{q}| = \sqrt{q_x^2 + q_y^2}$ than the starting vector. | ||

467 | It should be possible to develop an algorithm similar in spirit to the | ||

468 | Bresenham circle algorithm (see Section \ref{cdta0:srtr2:sbrt2}) to | ||

469 | adjust the magnitude of a vector to correct for cumulative | ||

470 | errors while leaving its direction as nearly unchanged | ||

471 | as possible (see Exercise \ref{exe:cdta0:sexe0:01}). | ||

472 | |||

473 | |||

474 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

475 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

476 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

477 | \subsection{Bresenham Rotation In 2 Dimensions} | ||

478 | %Section tag: BRT0 | ||

479 | \label{cdta0:srtr2:sbrt2} | ||

480 | |||

481 | Depending on the application \ldots{} | ||

482 | |||

483 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

484 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

485 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

486 | \section{Rotational Transformations In 3 Dimensions} | ||

487 | %Section tag: RTR3 | ||

488 | \label{cdta0:srtr3} | ||

489 | |||

490 | |||

491 | |||

492 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

493 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

494 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

495 | \section{Acknowledgements} | ||

496 | %Section tag: ACK0 | ||

497 | \label{cdta0:sack0} | ||

498 | |||

499 | |||

500 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

501 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

502 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

503 | \section{Exercises} | ||

504 | %Section tag: sexe0 | ||

505 | \label{cdta0:sexe0} | ||

506 | |||

507 | \begin{vworkexercisestatement} | ||

508 | \label{exe:cdta0:sexe0:01} | ||

509 | Develop an algorithm similar in spirit to the Bresenham circle | ||

510 | algorithm to adjust a vector $\mathbf{q} = (q_x, q_y)$ with | ||

511 | cumulative magnitude errors due to repeated rotations to | ||

512 | a vector $\mathbf{z} = (z_x, z_y)$ which points as nearly as | ||

513 | possible in the same direction as $\mathbf{q}$ but with | ||

514 | a desired magnitude $r$. | ||

515 | \end{vworkexercisestatement} | ||

516 | \vworkexercisefooter{} | ||

517 | |||

518 | |||

519 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

520 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

521 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

522 | \vfill | ||

523 | \noindent\begin{figure}[!b] | ||

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

525 | \begin{tiny} | ||

526 | \begin{verbatim} | ||

527 | $RCSfile: c_dta0.tex,v $ | ||

528 | $Source: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_dta0/c_dta0.tex,v $ | ||

529 | $Revision: 1.5 $ | ||

530 | $Author: dtashley $ | ||

531 | $Date: 2003/03/03 23:50:43 $ | ||

532 | \end{verbatim} | ||

533 | \end{tiny} | ||

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

535 | \end{figure} | ||

536 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

537 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

538 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

539 | % $Log: c_dta0.tex,v $ | ||

540 | % Revision 1.5 2003/03/03 23:50:43 dtashley | ||

541 | % Substantial edits. Safety checkin. | ||

542 | % | ||

543 | % Revision 1.4 2003/02/27 05:00:06 dtashley | ||

544 | % Substantial work towards rotation algorithm section. | ||

545 | % | ||

546 | % Revision 1.3 2003/01/15 06:23:13 dtashley | ||

547 | % Safety checkin, substantial edits. | ||

548 | % | ||

549 | % Revision 1.2 2003/01/14 05:39:59 dtashley | ||

550 | % Evening safety checkin after substantial edits. | ||

551 | % | ||

552 | % Revision 1.1 2001/08/25 22:51:25 dtashley | ||

553 | % Complex re-organization of book. | ||

554 | % | ||

555 | %End of file C_PCO0.TEX |

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

svn:eol-style |
native |

svn:keywords |
Header |

dashley@gmail.com | ViewVC Help |

Powered by ViewVC 1.1.25 |