/[dtapublic]/pubs/books/ucbka/trunk/c_dta0/c_dta0.tex
ViewVC logotype

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 277 - (show annotations) (download) (as text)
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).
Add quotation.
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 $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

Properties

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