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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 140 - (hide 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)
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

Properties

Name Value
svn:eol-style native
svn:keywords Header

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25