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

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

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 4 by dashley, Thu Oct 6 03:15:02 2016 UTC revision 277 by dashley, Tue Aug 13 02:35:39 2019 UTC
# Line 1  Line 1 
1  %$Header: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_dta0/c_dta0.tex,v 1.5 2003/03/03 23:50:43 dtashley Exp $  %$Header$
2    
3  \chapter[\cdtazeroshorttitle{}]{\cdtazerolongtitle{}}  \chapter[\cdtazeroshorttitle{}]{\cdtazerolongtitle{}}
4    
5  \label{cdta0}  \label{cdta0}
6    
7  \beginchapterquote{``Under construction!''}  \beginchapterquote{``Under construction!''}
8                       {Under construction!}                       {Under construction!}
9    
10    
11  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
12  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
13  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
14  \section{Introduction}  \section{Introduction}
15  %Section tag: INT0  %Section tag: INT0
16  \label{cdta0:sint0}  \label{cdta0:sint0}
17    
18    
19  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
20  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
21  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
22  \section[Fixed-Period Process Scheduling]  \section[Fixed-Period Process Scheduling]
23          {Load Balancing For Fixed-Period Process Scheduling Using Integer Counting}          {Load Balancing For Fixed-Period Process Scheduling Using Integer Counting}
24  %Section tag: PSI0  %Section tag: PSI0
25  \label{cdta0:spsi0}  \label{cdta0:spsi0}
26    
27  \index{process scheduling!using integer counting}It happens in a variety of  \index{process scheduling!using integer counting}It happens in a variety of
28  contexts in small microcontroller work  contexts in small microcontroller work
29  that one schedules processes (which may be implemented as subroutines  that one schedules processes (which may be implemented as subroutines
30  or functions) with a fixed period  or functions) with a fixed period
31  using integer counting.  Such scheduling tends to take the form of  using integer counting.  Such scheduling tends to take the form of
32  the code snippet in    the code snippet in  
33  Figure \ref{fig:cdta0:spsi0:01}.  Typically a ``master'' scheduling function  Figure \ref{fig:cdta0:spsi0:01}.  Typically a ``master'' scheduling function
34  is called at a periodic rate, and the scheduled functions are called  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  once every $T_i$ invocations of the master scheduling function ($T_i$ is
36  defined later).  Note in the figure that every scheduled function  defined later).  Note in the figure that every scheduled function
37  is called with perfect periodicity, but that the invocation sequence  is called with perfect periodicity, but that the invocation sequence
38  can be staggered.  Note also in the figure that the comments assume  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  that the scheduling function is called every 10ms (which is typical in
40  microcontroller work).  microcontroller work).
41    
42  \begin{figure}  \begin{figure}
43  \begin{small}  \begin{small}
44  \begin{verbatim}  \begin{verbatim}
45  /* The following "stagger" values are what we are attempting to  /* The following "stagger" values are what we are attempting to
46  ** analytically determine at compile-time so as to minimize the  ** analytically determine at compile-time so as to minimize the
47  ** maximum CPU time used in the worst-case tick. */  ** maximum CPU time used in the worst-case tick. */
48  #define P1_STAGGER   (0)  #define P1_STAGGER   (0)
49  #define P2_STAGGER   (0)  #define P2_STAGGER   (0)
50  #define P3_STAGGER   (0)  #define P3_STAGGER   (0)
51    
52  /* The periods are fixed and not subject to change.  The periods  /* The periods are fixed and not subject to change.  The periods
53  ** are input to any compile-time algorithm employed. */  ** are input to any compile-time algorithm employed. */
54  #define P1_PERIOD    (2)   /* Every   20ms.            */  #define P1_PERIOD    (2)   /* Every   20ms.            */
55  #define P2_PERIOD    (5)   /* Every  100ms.            */  #define P2_PERIOD    (5)   /* Every  100ms.            */
56  #define P3_PERIOD  (100)   /* Every 1000ms = 1 second. */  #define P3_PERIOD  (100)   /* Every 1000ms = 1 second. */
57    
58  /* These are the integer counters.  Their initial load values, which  /* These are the integer counters.  Their initial load values, which
59  ** determine the staggering, are the parameters we seek to  ** determine the staggering, are the parameters we seek to
60  ** determine. */  ** determine. */
61  static unsigned char p1_ctr = P1_STAGGER;  static unsigned char p1_ctr = P1_STAGGER;
62  static unsigned char p2_ctr = P2_STAGGER;  static unsigned char p2_ctr = P2_STAGGER;
63  static unsigned char p3_ctr = P3_STAGGER;  static unsigned char p3_ctr = P3_STAGGER;
64    
65  /* This is the master scheduling function called every 10ms.  It  /* This is the master scheduling function called every 10ms.  It
66  ** calls the periodic functions.  Note that this is an integer  ** calls the periodic functions.  Note that this is an integer
67  ** counting problem. */  ** counting problem. */
68  void master_scheduling_function(void)  void master_scheduling_function(void)
69     {     {
70     p1_ctr++;     p1_ctr++;
71     if (p1_ctr >= P1_PERIOD)     if (p1_ctr >= P1_PERIOD)
72        {        {
73        Process_1();  /* Call the process.   */        Process_1();  /* Call the process.   */
74        p1_ctr = 0;   /* Reset the counter.  */        p1_ctr = 0;   /* Reset the counter.  */
75        }        }
76     p2_ctr++;     p2_ctr++;
77     if (p2_ctr >= P2_PERIOD)     if (p2_ctr >= P2_PERIOD)
78        {        {
79        Process_2();  /* Call the process.   */        Process_2();  /* Call the process.   */
80        p2_ctr = 0;   /* Reset the counter.  */        p2_ctr = 0;   /* Reset the counter.  */
81        }        }
82     p3_ctr++;     p3_ctr++;
83     if (p3_ctr >= P3_PERIOD)     if (p3_ctr >= P3_PERIOD)
84        {        {
85        Process_3();  /* Call the process.   */        Process_3();  /* Call the process.   */
86        p3_ctr = 0;   /* Reset the counter.  */        p3_ctr = 0;   /* Reset the counter.  */
87        }        }
88     }     }
89  \end{verbatim}  \end{verbatim}
90  \end{small}  \end{small}
91  \caption{Code Snippet Illustrating Fixed-Period Integer Counter Process Scheduling  \caption{Code Snippet Illustrating Fixed-Period Integer Counter Process Scheduling
92          (3 Processes)}          (3 Processes)}
93  \label{fig:cdta0:spsi0:01}  \label{fig:cdta0:spsi0:01}
94  \end{figure}  \end{figure}
95    
96    
97  It is easy to see from Figure \ref{fig:cdta0:spsi0:01} that it may happen  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  on a single invocation of the master scheduling function that several or all of
99  the processes are scheduled.  If the scheduling of the  the processes are scheduled.  If the scheduling of the
100  processes is not staggered, this will happen for the first time  processes is not staggered, this will happen for the first time
101  on the invocation (or ``tick'')  on the invocation (or ``tick'')
102  corresponding to the least common multiple of all of the periods.  In  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  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  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  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.  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  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  stagger values be chosen so as to minimize the maximum amount of CPU
109  time taken on any invocation of the master scheduling function?}  time taken on any invocation of the master scheduling function?}
110    
111  We denote the set of $N$ processes that we must schedule  We denote the set of $N$ processes that we must schedule
112  by $\{ P_1, P_2, \ldots , P_N \}$.    by $\{ P_1, P_2, \ldots , P_N \}$.  
113  Process $P_i$ has period $T_i$ (measured in invocations  Process $P_i$ has period $T_i$ (measured in invocations
114  or ``ticks'' of  or ``ticks'' of
115  the master scheduling function, or ``ticks'').  Note that  the master scheduling function, or ``ticks'').  Note that
116  $T_i$ is dimensionless.    $T_i$ is dimensionless.  
117    
118  Each process $P_i$ also has cost  Each process $P_i$ also has cost
119  $\tau_i$  $\tau_i$
120  (the cost is usually the execution  (the cost is usually the execution
121  time of the function, but could in principle represent any property of  time of the function, but could in principle represent any property of
122  interest).  Note that there is no required relationship between  interest).  Note that there is no required relationship between
123  $\{ T_i \}$ and $\{ \tau_i \}$, as we are not determining schedulability.  $\{ 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  Thus $\{ \tau_i \}$ may be specified in any time unit, or it may not
125  represent time at all.  represent time at all.
126    
127  We agree that each invocation of the master scheduling function  We agree that each invocation of the master scheduling function
128  is one ``tick'' in discrete time, and that the first invocation  is one ``tick'' in discrete time, and that the first invocation
129  of the master scheduling function is denoted $t_1$ or $t=1$.  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  With no staggering ($z_i = 0$) each process $P_i$ will run
131  whenever  whenever
132    
133  \begin{equation}  \begin{equation}
134  \label{eq:cdta0:spsi0:01}  \label{eq:cdta0:spsi0:01}
135  t \bmod T_i = 0 .  t \bmod T_i = 0 .
136  \end{equation}  \end{equation}
137    
138  We may modify the invocation sequence of a process $P_i$ by  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  varying a stagger value, which we denote $z_i$.  The stagger value
140  specifies by how many ticks we will advance the invocation of  specifies by how many ticks we will advance the invocation of
141  $P_i$.  When considering stagger values, each process $P_i$ will  $P_i$.  When considering stagger values, each process $P_i$ will
142  run whenever  run whenever
143    
144  \begin{equation}  \begin{equation}
145  \label{eq:cdta0:spsi0:02}  \label{eq:cdta0:spsi0:02}
146  (t + z_i) \bmod T_i = 0 .  (t + z_i) \bmod T_i = 0 .
147  \end{equation}  \end{equation}
148    
149  At each tick, each process $P_i$ is either scheduled to run or not scheduled  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  to run.  We define an infinite row vector, called the \emph{uncosted invocation
151  sequence} (or simply the \emph{invocation sequence})  sequence} (or simply the \emph{invocation sequence})
152  and denoted $\rho_i(z_i)$, which contains a `1' in each column corresponding  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,  to a tick when the process $P_i$ run or `0' if it does not run.  For example,
154  if $T_1 = 3$,  if $T_1 = 3$,
155    
156  \begin{eqnarray}  \begin{eqnarray}
157  \nonumber  \nonumber
158  \rho_1 = \rho_1(0) & = & [ \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; \ldots \; ] \\  \rho_1 = \rho_1(0) & = & [ \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; \ldots \; ] \\
159  \label{eq:cdta0:spsi0:03}  \label{eq:cdta0:spsi0:03}
160  \rho_1(1) & = & [ \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; \ldots \; ] \\  \rho_1(1) & = & [ \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; \ldots \; ] \\
161  \nonumber  \nonumber
162  \rho_1(2) & = & [ \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; \ldots \; ] \\  \rho_1(2) & = & [ \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; \ldots \; ] \\
163  \nonumber  \nonumber
164  \rho_1(3) & = & [ \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; \ldots \; ]  \rho_1(3) & = & [ \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; \ldots \; ]
165  \end{eqnarray}  \end{eqnarray}
166    
167  \noindent{}We define but avoid using stagger values $z_i \geq T_i$, but as  \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  (\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}),  $\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  we use that notation
171  that $\rho_i = \rho_i(0)$.  that $\rho_i = \rho_i(0)$.
172    
173  We define the \emph{costed invocation sequence}, denoted  We define the \emph{costed invocation sequence}, denoted
174  $\overline{\rho_i}(z_i)$, as the infinite row  $\overline{\rho_i}(z_i)$, as the infinite row
175  vector similar to (\ref{eq:cdta0:spsi0:03}) but where  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.  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$,  For example, if $T_1=3$ and $\tau_i = 5$,
178    
179  \begin{eqnarray}  \begin{eqnarray}
180  \nonumber  \nonumber
181  \overline{\rho_1} =  \overline{\rho_1} =
182  \overline{\rho_1}(0) & = & [ \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; \ldots \; ] \\  \overline{\rho_1}(0) & = & [ \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; \ldots \; ] \\
183  \label{eq:cdta0:spsi0:04}  \label{eq:cdta0:spsi0:04}
184  \overline{\rho_1}(1) & = & [ \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; \ldots \; ] \\  \overline{\rho_1}(1) & = & [ \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; \ldots \; ] \\
185  \nonumber  \nonumber
186  \overline{\rho_1}(2) & = & [ \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; \ldots \; ] \\  \overline{\rho_1}(2) & = & [ \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; \ldots \; ] \\
187  \nonumber  \nonumber
188  \overline{\rho_1}(3) & = & [ \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; \ldots \; ]  \overline{\rho_1}(3) & = & [ \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; \ldots \; ]
189  \end{eqnarray}  \end{eqnarray}
190    
191  We define the \emph{cost calculation matrix} as the matrix formed by vertically  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)$  concatenating, in order, the first $LCM(T_1, \ldots , T_N)$
193  columns of either the uncosted invocation sequence  columns of either the uncosted invocation sequence
194  $\rho_i(z_i)$ or the costed invocation sequence $\overline{\rho_i}(z_i)$  $\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  of every process in the system; and then appending to this as a row vector
196  the sums of  the sums of
197  each column.  We choose only the first $LCM(T_1, \ldots , T_N)$ columns  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.  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  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})$  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  (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  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  \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  cost calculation matrix (it is $\xi$ that we seek to minimize by choosing
205  $\mathbf{z}$).  These definitions are illustrated in the following example.  $\mathbf{z}$).  These definitions are illustrated in the following example.
206    
207  \begin{vworkexamplestatement}  \begin{vworkexamplestatement}
208  \label{ex:cdta0:spsi0:01}  \label{ex:cdta0:spsi0:01}
209  For the system of 3 processes ($P_1$, $P_2$, and $P_3$) with  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$,  $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$,  $z_1 = 2$, $z_2 = 1$, and $z_3 = 0$,
212  form the uncosted and costed invocation sequences, the cost  form the uncosted and costed invocation sequences, the cost
213  calculation matrices, and the costs.  calculation matrices, and the costs.
214  \end{vworkexamplestatement}  \end{vworkexamplestatement}
215  \begin{vworkexampleparsection}{Solution}  \begin{vworkexampleparsection}{Solution}
216  We first handle the uncosted case in full, followed by the costed  We first handle the uncosted case in full, followed by the costed
217  case in full.  case in full.
218    
219  \textbf{(Uncosted Case):}  \textbf{(Uncosted Case):}
220  With $T_1=6$ and $z_1=2$, the first invocation of $P_1$ will occur  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$,  when $(t + 2) \bmod 6 = 0$ (see Eq. \ref{eq:cdta0:spsi0:02}), at $t=4$,
222  and then repeat with periodicity 6.  Thus  and then repeat with periodicity 6.  Thus
223    
224  \begin{equation}  \begin{equation}
225  \label{eq:ex:cdta0:spsi0:01:01}  \label{eq:ex:cdta0:spsi0:01:01}
226  \rho_1(2)  =  [ \; 0 \; 0 \; 0 \; 1 \; 0 \; 0 \; 0 \; 0 \; 0 \; 1 \;  \rho_1(2)  =  [ \; 0 \; 0 \; 0 \; 1 \; 0 \; 0 \; 0 \; 0 \; 0 \; 1 \;
227   0 \; 0 \; 0 \; 0 \; 0 \; 1 \; 0 \; \ldots \; ] .   0 \; 0 \; 0 \; 0 \; 0 \; 1 \; 0 \; \ldots \; ] .
228  \end{equation}  \end{equation}
229    
230  \noindent{}Applying the same definition for $P_2$ and $P_3$ yields  \noindent{}Applying the same definition for $P_2$ and $P_3$ yields
231    
232  \begin{equation}  \begin{equation}
233  \label{eq:ex:cdta0:spsi0:01:02}  \label{eq:ex:cdta0:spsi0:01:02}
234  \rho_2(1)  =  [ \; 0 \; 0 \; 1 \; 0 \; 0 \; 0 \; 1 \; 0 \; 0 \; 0 \;  \rho_2(1)  =  [ \; 0 \; 0 \; 1 \; 0 \; 0 \; 0 \; 1 \; 0 \; 0 \; 0 \;
235   1 \; 0 \; 0 \; 0 \; 1 \; 0 \; 0 \; \ldots \; ]   1 \; 0 \; 0 \; 0 \; 1 \; 0 \; 0 \; \ldots \; ]
236  \end{equation}  \end{equation}
237    
238  \noindent{}and  \noindent{}and
239    
240  \begin{equation}  \begin{equation}
241  \label{eq:ex:cdta0:spsi0:01:03}  \label{eq:ex:cdta0:spsi0:01:03}
242  \rho_3(0) = \rho_3 =  [ \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \;  \rho_3(0) = \rho_3 =  [ \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \;
243   0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; \ldots \; ] .   0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; \ldots \; ] .
244  \end{equation}  \end{equation}
245    
246  We note that the column vector $\mathbf{z}$ is  We note that the column vector $\mathbf{z}$ is
247    
248  \begin{equation}  \begin{equation}
249  \label{eq:ex:cdta0:spsi0:01:04}  \label{eq:ex:cdta0:spsi0:01:04}
250  \mathbf{z}  \mathbf{z}
251  =  =
252  \left[\begin{array}{c}z_1\\z_2\\z_3\end{array}\right]  \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] .  \left[\begin{array}{c}2\\1\\0\end{array}\right] .
255  \end{equation}  \end{equation}
256    
257  $LCM(T_1, T_2, T_3) = LCM(6, 4, 3) = 12$, and so the cost calculation matrix  $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  can be constructed with only 12 columns, since the columns repeat with periodicity
259  12:  12:
260    
261  \begin{equation}  \begin{equation}
262  \label{eq:ex:cdta0:spsi0:01:05}  \label{eq:ex:cdta0:spsi0:01:05}
263  \xi(\mathbf{z})  \xi(\mathbf{z})
264  =  =
265  \xi\left(\left[\begin{array}{c}2\\1\\0\end{array}\right]\right)  \xi\left(\left[\begin{array}{c}2\\1\\0\end{array}\right]\right)
266  =  =
267  \left[  \left[
268  \begin{array}{rrrrrrrrrrrr}  \begin{array}{rrrrrrrrrrrr}
269  0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\  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 \\  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 \\  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  0 & 0 & 2 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 1
273  \end{array}  \end{array}
274  \right]  \right]
275  .  .
276  \end{equation}  \end{equation}
277    
278  Note in (\ref{eq:ex:cdta0:spsi0:01:05}) that the last row is  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  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  the last row gives, on a per tick basis, the number of processes
281  that run.  that run.
282    
283  The cost $\xi$ is the maximum of the last row of (\ref{eq:ex:cdta0:spsi0:01:05}),  The cost $\xi$ is the maximum of the last row of (\ref{eq:ex:cdta0:spsi0:01:05}),
284  and by inspection $\xi = 2$.  and by inspection $\xi = 2$.
285    
286  \textbf{(Costed Case):}  \textbf{(Costed Case):}
287  The costed invocation sequences are simply  The costed invocation sequences are simply
288  (\ref{eq:ex:cdta0:spsi0:01:01}), (\ref{eq:ex:cdta0:spsi0:01:02}), and  (\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  (\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$:  to the process being considered;  $\tau_1$, $\tau_2$, or $\tau_3$:
291    
292  \begin{eqnarray}  \begin{eqnarray}
293  \nonumber  \nonumber
294  \overline{\rho_1}(2)  & = &  [ \; 0 \; 0 \; 0 \; 2 \; 0 \; 0 \; 0 \; 0 \; 0 \; 2 \;  \overline{\rho_1}(2)  & = &  [ \; 0 \; 0 \; 0 \; 2 \; 0 \; 0 \; 0 \; 0 \; 0 \; 2 \;
295   0 \; 0 \; 0 \; 0 \; 0 \; 2 \; 0 \; \ldots \; ] \\   0 \; 0 \; 0 \; 0 \; 0 \; 2 \; 0 \; \ldots \; ] \\
296  \label{eq:ex:cdta0:spsi0:01:06}  \label{eq:ex:cdta0:spsi0:01:06}
297  \overline{\rho_2}(1)  & = & [ \; 0 \; 0 \; 7 \; 0 \; 0 \; 0 \; 7 \; 0 \; 0 \; 0 \;  \overline{\rho_2}(1)  & = & [ \; 0 \; 0 \; 7 \; 0 \; 0 \; 0 \; 7 \; 0 \; 0 \; 0 \;
298   7 \; 0 \; 0 \; 0 \; 7 \; 0 \; 0 \; \ldots \; ]  \\   7 \; 0 \; 0 \; 0 \; 7 \; 0 \; 0 \; \ldots \; ]  \\
299  \nonumber  \nonumber
300  \overline{\rho_3}(0) = \overline{\rho_3} & = &  [ \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \;  \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 \; ]   0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; \ldots \; ]
302  \end{eqnarray}  \end{eqnarray}
303    
304  The cost calculation matrix in the costed case is formed by vertically concatenating the  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  first 12 columns of the rows of (\ref{eq:ex:cdta0:spsi0:01:06}), with the
306  final row containing columnwise sums:  final row containing columnwise sums:
307    
308  \begin{equation}  \begin{equation}
309  \label{eq:ex:cdta0:spsi0:01:07}  \label{eq:ex:cdta0:spsi0:01:07}
310  \overline{\xi}(\mathbf{z})  \overline{\xi}(\mathbf{z})
311  =  =
312  \overline{\xi}\left(\left[\begin{array}{c}2\\1\\0\end{array}\right]\right)  \overline{\xi}\left(\left[\begin{array}{c}2\\1\\0\end{array}\right]\right)
313  =  =
314  \left[  \left[
315  \begin{array}{rrrrrrrrrrrr}  \begin{array}{rrrrrrrrrrrr}
316   0 &  0 &  0 &  2 &  0 &  0 &  0 &  0 &  0 &  2 &  0 &  0 \\   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 \\   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 \\   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   0 &  0 & 12 &  2 &  0 &  5 &  7 &  0 &  5 &  2 &  7 &  5
320  \end{array}  \end{array}
321  \right]  \right]
322  .  .
323  \end{equation}  \end{equation}
324    
325  The cost $\overline{\xi}$ is the maximum of the last row of (\ref{eq:ex:cdta0:spsi0:01:07}),  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$.  and by inspection $\overline{\xi} = 12$.
327  \end{vworkexampleparsection}  \end{vworkexampleparsection}
328  \vworkexamplefooter{}  \vworkexamplefooter{}
329    
330    
331    
332  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
333  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
334  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
335  \section{Sine And Cosine}  \section{Sine And Cosine}
336  %Section tag: sco0  %Section tag: sco0
337  \label{cdta0:ssco0}  \label{cdta0:ssco0}
338    
339    
340    
341  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
342  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
343  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
344  \section{Rotational Transformations In 2 Dimensions}  \section{Rotational Transformations In 2 Dimensions}
345  %Section tag: RTR2  %Section tag: RTR2
346  \label{cdta0:srtr2}  \label{cdta0:srtr2}
347    
348  \index{rotation!2-D}It occurs often in microcontroller work that one needs to rotate  \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,  coordinates in 2 dimensions (Figure \ref{fig:cdta0:srtr2:01}).  In this section,
350  the most economical algorithms known for 2-dimensional  the most economical algorithms known for 2-dimensional
351  rotation are discussed.  We assume that the  rotation are discussed.  We assume that the
352  point $\mathbf{p}$ to be rotated is specified in rectangular coordinates  point $\mathbf{p}$ to be rotated is specified in rectangular coordinates
353  $\mathbf{p} = (p_x, p_y)$ rather than polar coordinates  $\mathbf{p} = (p_x, p_y)$ rather than polar coordinates
354  $\mathbf{p} = (r, \theta)$; since if $\mathbf{p}$ is specified in polar coordinates  $\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  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]$  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  and the result of the rotation
358  $\mathbf{q} = (q_x, q_y) = \left[\begin{array}{c}q_x\\q_y\end{array}\right]$.  $\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}$  We denote the length of the vector represented by $\mathbf{p}$ or $\mathbf{q}$
360  by $r$, and note that  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}$.  $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  Because low-cost microcontrollers are used, we assume that
363  $p_x, p_y, q_x, q_y \in \vworkintset$.  $p_x, p_y, q_x, q_y \in \vworkintset$.
364  We denote the desired amount of counter-clockwise rotation by $\delta$ (in radians).  We denote the desired amount of counter-clockwise rotation by $\delta$ (in radians).
365    
366  \begin{figure}  \begin{figure}
367  \begin{huge}  \begin{huge}
368  \begin{center}  \begin{center}
369  Reserved  Reserved
370  \end{center}  \end{center}
371  \end{huge}  \end{huge}
372  \caption{Rotation In 2 Dimensions}  \caption{Rotation In 2 Dimensions}
373  \label{fig:cdta0:srtr2:01}  \label{fig:cdta0:srtr2:01}
374  \end{figure}  \end{figure}
375    
376  A particularly na\"{\i}ve algorithm to use in microcontroller work is to  A particularly na\"{\i}ve algorithm to use in microcontroller work is to
377  convert $\mathbf{p} = (p_x, p_y)$ to polar coordinates  convert $\mathbf{p} = (p_x, p_y)$ to polar coordinates
378  $\mathbf{p} = (r, \theta)$, rotate to obtain  $\mathbf{p} = (r, \theta)$, rotate to obtain
379  $\mathbf{q} = (r, (\theta + \delta) \bmod 2\pi)$, and then convert back to  $\mathbf{q} = (r, (\theta + \delta) \bmod 2\pi)$, and then convert back to
380  rectangular coordinates $\mathbf{q} = (q_x, q_y)$.    rectangular coordinates $\mathbf{q} = (q_x, q_y)$.  
381  This algorithm is na\"{\i}ve because trigonometric and  This algorithm is na\"{\i}ve because trigonometric and
382  inverse trigonometric functions are required, which are not economical to implement  inverse trigonometric functions are required, which are not economical to implement
383  on microcontrollers.  We seek if possible algorithms which operate exclusively in  on microcontrollers.  We seek if possible algorithms which operate exclusively in
384  rectangular coordinates and which require little or no evaluation of  rectangular coordinates and which require little or no evaluation of
385  trigonometric and inverse trigonometric functions.  trigonometric and inverse trigonometric functions.
386    
387    
388  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
389  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
390  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
391  \subsection{Matrix Rotation In 2 Dimensions}  \subsection{Matrix Rotation In 2 Dimensions}
392  %Section tag: MRT0  %Section tag: MRT0
393  \label{cdta0:srtr2:smrt2}  \label{cdta0:srtr2:smrt2}
394    
395  Assume we wish to rotate the vector  Assume we wish to rotate the vector
396    
397  \begin{equation}  \begin{equation}
398  \label{eq:cdta0:srtr2:smrt2:01}  \label{eq:cdta0:srtr2:smrt2:01}
399  \mathbf{p}  \mathbf{p}
400  = (p_x, p_y)  = (p_x, p_y)
401  = \left[\begin{array}{c}p_x\\p_y\end{array}\right]  = \left[\begin{array}{c}p_x\\p_y\end{array}\right]
402  = (r \cos \theta, r \sin \theta)  = (r \cos \theta, r \sin \theta)
403  = \left[\begin{array}{c}r \cos \theta\\r \sin \theta\end{array}\right]  = \left[\begin{array}{c}r \cos \theta\\r \sin \theta\end{array}\right]
404  \end{equation}  \end{equation}
405    
406  \noindent{}by an angle of $\delta$ to give the vector  \noindent{}by an angle of $\delta$ to give the vector
407    
408  \begin{eqnarray}  \begin{eqnarray}
409  \label{eq:cdta0:srtr2:smrt2:02}  \label{eq:cdta0:srtr2:smrt2:02}
410  \mathbf{q} & = & (q_x, q_y) = \left[\begin{array}{c}q_x\\q_y\end{array}\right] \\  \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))  \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].  = \left[\begin{array}{c}r \cos (\theta + \delta)\\r \sin (\theta+\delta)\end{array}\right].
413  \end{eqnarray}  \end{eqnarray}
414    
415  \noindent{}Recall from standard trigonometry identities that for sines and cosines of  \noindent{}Recall from standard trigonometry identities that for sines and cosines of
416  sums of angles that  sums of angles that
417    
418  \begin{eqnarray}  \begin{eqnarray}
419  \label{eq:cdta0:srtr2:smrt2:03}  \label{eq:cdta0:srtr2:smrt2:03}
420  \left[\begin{array}{c}r \cos (\theta + \delta)\\r \sin (\theta+\delta)\end{array}\right]  \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 \\  \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] \\                        r \sin \theta \cos \delta + r \cos \theta \sin \delta \end{array}\right] \\
424  \label{eq:cdta0:srtr2:smrt2:04}  \label{eq:cdta0:srtr2:smrt2:04}
425  & = &  & = &
426  \left[\begin{array}{c}p_x \cos \delta - p_y \sin \delta \\  \left[\begin{array}{c}p_x \cos \delta - p_y \sin \delta \\
427                        p_x \sin \delta + p_y \cos \delta \end{array}\right] \\                        p_x \sin \delta + p_y \cos \delta \end{array}\right] \\
428  \label{eq:cdta0:srtr2:smrt2:05}  \label{eq:cdta0:srtr2:smrt2:05}
429  & = &  & = &
430  \left[\begin{array}{c}q_x\\q_y\end{array}\right]  \left[\begin{array}{c}q_x\\q_y\end{array}\right]
431  =  =
432  \left[\begin{array}{cc}\cos \delta & - \sin \delta \\  \left[\begin{array}{cc}\cos \delta & - \sin \delta \\
433                         \sin \delta & \;\;\;\cos \delta \end{array}\right]                         \sin \delta & \;\;\;\cos \delta \end{array}\right]
434  \left[\begin{array}{c}p_x\\p_y\end{array}\right] .  \left[\begin{array}{c}p_x\\p_y\end{array}\right] .
435  \end{eqnarray}  \end{eqnarray}
436    
437  \noindent{}Note that (\ref{eq:cdta0:srtr2:smrt2:05})  \noindent{}Note that (\ref{eq:cdta0:srtr2:smrt2:05})
438  reduces the rotation problem to four multiplications and two additions  reduces the rotation problem to four multiplications and two additions
439  (the matrix multiplication), provided that some approximation of the sine  (the matrix multiplication), provided that some approximation of the sine
440  and cosine functions is available (see Section \ref{cdta0:ssco0}).    and cosine functions is available (see Section \ref{cdta0:ssco0}).  
441    
442  To apply (\ref{eq:cdta0:srtr2:smrt2:05}), the embedded software  To apply (\ref{eq:cdta0:srtr2:smrt2:05}), the embedded software
443  may or may not need to approximate the sine and cosine functions.  may or may not need to approximate the sine and cosine functions.
444  For some applications, if the angle of rotation is fixed,  For some applications, if the angle of rotation is fixed,
445  $\sin \delta$ and  $\sin \delta$ and
446  $\cos \delta$ may be calculated at compile time and tabulated in  $\cos \delta$ may be calculated at compile time and tabulated in
447  ROM rather than $\delta$ (so that the embedded software does not need  ROM rather than $\delta$ (so that the embedded software does not need
448  to approximate these functions).  For other applications,  to approximate these functions).  For other applications,
449  sine and cosine must be approximated (see Section \ref{cdta0:ssco0}).  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})  The 2 $\times$ 2 matrix in (\ref{eq:cdta0:srtr2:smrt2:05})
452  is called the \index{rotation matrix}\emph{rotation matrix}.  There are  is called the \index{rotation matrix}\emph{rotation matrix}.  There are
453  other functionally equivalent ways to derive this result, including complex  other functionally equivalent ways to derive this result, including complex
454  arithmetic (i.e. phasor analysis) and graphical geometric arguments.  arithmetic (i.e. phasor analysis) and graphical geometric arguments.
455    
456  As pointed out in Section \ref{cdta0:ssco0}, the best way to approximate  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  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  values of $\sin \delta$ for $\delta \in [0, \pi/2]$.  Using the
459  techniques presented in Section \ref{cdta0:ssco0} for approximation of  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  sine and cosine and using (\ref{eq:cdta0:srtr2:smrt2:05}), rotation can usually
461  be carried out using around 20 machine instructions.  be carried out using around 20 machine instructions.
462    
463  If a vector is rotated repeatedly using (\ref{eq:cdta0:srtr2:smrt2:05}), cumulative  If a vector is rotated repeatedly using (\ref{eq:cdta0:srtr2:smrt2:05}), cumulative
464  truncation and rounding errors may eventually yield a vector  truncation and rounding errors may eventually yield a vector
465  $\mathbf{q}$ with a significantly different  $\mathbf{q}$ with a significantly different
466  magnitude $|\mathbf{q}| = \sqrt{q_x^2 + q_y^2}$ than the starting vector.  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  It should be possible to develop an algorithm similar in spirit to the
468  Bresenham circle algorithm (see Section \ref{cdta0:srtr2:sbrt2}) to  Bresenham circle algorithm (see Section \ref{cdta0:srtr2:sbrt2}) to
469  adjust the magnitude of a vector to correct for cumulative  adjust the magnitude of a vector to correct for cumulative
470  errors while leaving its direction as nearly unchanged  errors while leaving its direction as nearly unchanged
471  as possible (see Exercise \ref{exe:cdta0:sexe0:01}).  as possible (see Exercise \ref{exe:cdta0:sexe0:01}).
472    
473    
474  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
475  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
476  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
477  \subsection{Bresenham Rotation In 2 Dimensions}  \subsection{Bresenham Rotation In 2 Dimensions}
478  %Section tag: BRT0  %Section tag: BRT0
479  \label{cdta0:srtr2:sbrt2}  \label{cdta0:srtr2:sbrt2}
480    
481  Depending on the application \ldots{}  Depending on the application \ldots{}
482    
483  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
484  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
485  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
486  \section{Rotational Transformations In 3 Dimensions}  \section{Rotational Transformations In 3 Dimensions}
487  %Section tag: RTR3  %Section tag: RTR3
488  \label{cdta0:srtr3}  \label{cdta0:srtr3}
489    
490    
491    
492  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
493  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
494  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
495  \section{Acknowledgements}  \section{Acknowledgements}
496  %Section tag: ACK0  %Section tag: ACK0
497  \label{cdta0:sack0}  \label{cdta0:sack0}
498    
499    
500  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
501  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
502  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
503  \section{Exercises}  \section{Exercises}
504  %Section tag: sexe0  %Section tag: sexe0
505  \label{cdta0:sexe0}  \label{cdta0:sexe0}
506    
507  \begin{vworkexercisestatement}  \begin{vworkexercisestatement}
508  \label{exe:cdta0:sexe0:01}  \label{exe:cdta0:sexe0:01}
509  Develop an algorithm similar in spirit to the Bresenham circle  Develop an algorithm similar in spirit to the Bresenham circle
510  algorithm to adjust a vector $\mathbf{q} = (q_x, q_y)$ with  algorithm to adjust a vector $\mathbf{q} = (q_x, q_y)$ with
511  cumulative magnitude errors due to repeated rotations to  cumulative magnitude errors due to repeated rotations to
512  a vector $\mathbf{z} = (z_x, z_y)$ which points as nearly as  a vector $\mathbf{z} = (z_x, z_y)$ which points as nearly as
513  possible in the same direction as $\mathbf{q}$ but with  possible in the same direction as $\mathbf{q}$ but with
514  a desired magnitude $r$.  a desired magnitude $r$.
515  \end{vworkexercisestatement}  \end{vworkexercisestatement}
516  \vworkexercisefooter{}  \vworkexercisefooter{}
517    
518    
519  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
520  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
521  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
522  \vfill  \vfill
523  \noindent\begin{figure}[!b]  \noindent\begin{figure}[!b]
524  \noindent\rule[-0.25in]{\textwidth}{1pt}  \noindent\rule[-0.25in]{\textwidth}{1pt}
525  \begin{tiny}  \begin{tiny}
526  \begin{verbatim}  \begin{verbatim}
527  $RCSfile: c_dta0.tex,v $  $HeadURL$
528  $Source: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_dta0/c_dta0.tex,v $  $Revision$
529  $Revision: 1.5 $  $Date$
530  $Author: dtashley $  $Author$
531  $Date: 2003/03/03 23:50:43 $  \end{verbatim}
532  \end{verbatim}  \end{tiny}
533  \end{tiny}  \noindent\rule[0.25in]{\textwidth}{1pt}
534  \noindent\rule[0.25in]{\textwidth}{1pt}  \end{figure}
535  \end{figure}  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
536  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
537  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
538  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %
539  % $Log: c_dta0.tex,v $  %End of file C_PCO0.TEX
 % Revision 1.5  2003/03/03 23:50:43  dtashley  
 % Substantial edits.  Safety checkin.  
 %  
 % Revision 1.4  2003/02/27 05:00:06  dtashley  
 % Substantial work towards rotation algorithm section.  
 %  
 % Revision 1.3  2003/01/15 06:23:13  dtashley  
 % Safety checkin, substantial edits.  
 %  
 % Revision 1.2  2003/01/14 05:39:59  dtashley  
 % Evening safety checkin after substantial edits.  
 %  
 % Revision 1.1  2001/08/25 22:51:25  dtashley  
 % Complex re-organization of book.  
 %  
 %End of file C_PCO0.TEX  

Legend:
Removed from v.4  
changed lines
  Added in v.277

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25