# Contents of /pubs/books/ucbka/trunk/c_dta0/c_dta0.tex

Tue Aug 13 02:35:39 2019 UTC (2 years, 10 months ago) by dashley
File MIME type: application/x-tex
File size: 21618 byte(s)
Change keyword substitution (migration from cvs to svn).

 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 134 \label{eq:cdta0:spsi0:01} 135 t \bmod T_i = 0 . 136 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 145 \label{eq:cdta0:spsi0:02} 146 (t + z_i) \bmod T_i = 0 . 147 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 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 229 230 \noindent{}Applying the same definition for $P_2$ and $P_3$ yields 231 232 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 237 238 \noindent{}and 239 240 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 245 246 We note that the column vector $\mathbf{z}$ is 247 248 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 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 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 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 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 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 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 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 $HeadURL$ 528 $Revision$ 529 $Date$ 530 $Author$ 531 \end{verbatim} 532 \end{tiny} 533 \noindent\rule[0.25in]{\textwidth}{1pt} 534 \end{figure} 535 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 536 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 537 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 538 % 539 %End of file C_PCO0.TEX