Parent Directory | Revision Log

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

*Mon Jul 3 01:59:16 2017 UTC*
(6 years, 7 months 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 | %$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 |