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[FixedPeriod Process Scheduling] 
\section[FixedPeriod Process Scheduling] 
23 
{Load Balancing For FixedPeriod Process Scheduling Using Integer Counting} 
{Load Balancing For FixedPeriod 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 compiletime so as to minimize the 
** analytically determine at compiletime so as to minimize the 
47 
** maximum CPU time used in the worstcase tick. */ 
** maximum CPU time used in the worstcase 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 compiletime algorithm employed. */ 
** are input to any compiletime 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 FixedPeriod Integer Counter Process Scheduling 
\caption{Code Snippet Illustrating FixedPeriod 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 columnwise sum of the rows above it. Note also that 
the columnwise 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!2D}It occurs often in microcontroller work that one needs to rotate 
\index{rotation!2D}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 2dimensional 
the most economical algorithms known for 2dimensional 
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 lowcost microcontrollers are used, we assume that 
Because lowcost 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 counterclockwise rotation by $\delta$ (in radians). 
We denote the desired amount of counterclockwise 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 $ 
$RCSfile: c_dta0.tex,v $ 
528 
$Source: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_dta0/c_dta0.tex,v $ 
$Source: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_dta0/c_dta0.tex,v $ 
529 
$Revision: 1.5 $ 
$Revision: 1.5 $ 
530 
$Author: dtashley $ 
$Author: dtashley $ 
531 
$Date: 2003/03/03 23:50:43 $ 
$Date: 2003/03/03 23:50:43 $ 
532 
\end{verbatim} 
\end{verbatim} 
533 
\end{tiny} 
\end{tiny} 
534 
\noindent\rule[0.25in]{\textwidth}{1pt} 
\noindent\rule[0.25in]{\textwidth}{1pt} 
535 
\end{figure} 
\end{figure} 
536 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
537 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
538 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
539 
% $Log: c_dta0.tex,v $ 
% $Log: c_dta0.tex,v $ 
540 
% Revision 1.5 2003/03/03 23:50:43 dtashley 
% Revision 1.5 2003/03/03 23:50:43 dtashley 
541 
% Substantial edits. Safety checkin. 
% Substantial edits. Safety checkin. 
542 
% 
% 
543 
% Revision 1.4 2003/02/27 05:00:06 dtashley 
% Revision 1.4 2003/02/27 05:00:06 dtashley 
544 
% Substantial work towards rotation algorithm section. 
% Substantial work towards rotation algorithm section. 
545 
% 
% 
546 
% Revision 1.3 2003/01/15 06:23:13 dtashley 
% Revision 1.3 2003/01/15 06:23:13 dtashley 
547 
% Safety checkin, substantial edits. 
% Safety checkin, substantial edits. 
548 
% 
% 
549 
% Revision 1.2 2003/01/14 05:39:59 dtashley 
% Revision 1.2 2003/01/14 05:39:59 dtashley 
550 
% Evening safety checkin after substantial edits. 
% Evening safety checkin after substantial edits. 
551 
% 
% 
552 
% Revision 1.1 2001/08/25 22:51:25 dtashley 
% Revision 1.1 2001/08/25 22:51:25 dtashley 
553 
% Complex reorganization of book. 
% Complex reorganization of book. 
554 
% 
% 
555 
%End of file C_PCO0.TEX 
%End of file C_PCO0.TEX 