--- pubs/books/ucbka/trunk/c_dta0/c_dta0.tex	2016/10/06 03:15:02	4
+++ pubs/books/ucbka/trunk/c_dta0/c_dta0.tex	2017/07/03 01:59:16	140
@@ -1,555 +1,555 @@
-%$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 $
-
-\chapter[\cdtazeroshorttitle{}]{\cdtazerolongtitle{}}
-
-\label{cdta0}
-
-\beginchapterquote{``Under construction!''}
-                     {Under construction!}
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\section{Introduction}
-%Section tag: INT0
-\label{cdta0:sint0}
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\section[Fixed-Period Process Scheduling]
-        {Load Balancing For Fixed-Period Process Scheduling Using Integer Counting}
-%Section tag: PSI0
-\label{cdta0:spsi0}
-
-\index{process scheduling!using integer counting}It happens in a variety of 
-contexts in small microcontroller work
-that one schedules processes (which may be implemented as subroutines
-or functions) with a fixed period
-using integer counting.  Such scheduling tends to take the form of
-the code snippet in  
-Figure \ref{fig:cdta0:spsi0:01}.  Typically a ``master'' scheduling function
-is called at a periodic rate, and the scheduled functions are called
-once every $T_i$ invocations of the master scheduling function ($T_i$ is
-defined later).  Note in the figure that every scheduled function
-is called with perfect periodicity, but that the invocation sequence
-can be staggered.  Note also in the figure that the comments assume
-that the scheduling function is called every 10ms (which is typical in
-microcontroller work). 
-
-\begin{figure}
-\begin{small}
-\begin{verbatim}
-/* The following "stagger" values are what we are attempting to
-** analytically determine at compile-time so as to minimize the
-** maximum CPU time used in the worst-case tick. */ 
-#define P1_STAGGER   (0)
-#define P2_STAGGER   (0)
-#define P3_STAGGER   (0)
-
-/* The periods are fixed and not subject to change.  The periods
-** are input to any compile-time algorithm employed. */
-#define P1_PERIOD    (2)   /* Every   20ms.            */
-#define P2_PERIOD    (5)   /* Every  100ms.            */
-#define P3_PERIOD  (100)   /* Every 1000ms = 1 second. */
-
-/* These are the integer counters.  Their initial load values, which
-** determine the staggering, are the parameters we seek to
-** determine. */
-static unsigned char p1_ctr = P1_STAGGER;
-static unsigned char p2_ctr = P2_STAGGER;
-static unsigned char p3_ctr = P3_STAGGER;
-
-/* This is the master scheduling function called every 10ms.  It 
-** calls the periodic functions.  Note that this is an integer
-** counting problem. */
-void master_scheduling_function(void)
-   {
-   p1_ctr++;
-   if (p1_ctr >= P1_PERIOD)
-      {
-      Process_1();  /* Call the process.   */
-      p1_ctr = 0;   /* Reset the counter.  */
-      }
-   p2_ctr++;
-   if (p2_ctr >= P2_PERIOD)
-      {
-      Process_2();  /* Call the process.   */
-      p2_ctr = 0;   /* Reset the counter.  */
-      }
-   p3_ctr++;
-   if (p3_ctr >= P3_PERIOD)
-      {
-      Process_3();  /* Call the process.   */
-      p3_ctr = 0;   /* Reset the counter.  */
-      }
-   }
-\end{verbatim}
-\end{small}
-\caption{Code Snippet Illustrating Fixed-Period Integer Counter Process Scheduling
-        (3 Processes)}
-\label{fig:cdta0:spsi0:01}
-\end{figure}
-
-
-It is easy to see from Figure \ref{fig:cdta0:spsi0:01} that it may happen
-on a single invocation of the master scheduling function that several or all of 
-the processes are scheduled.  If the scheduling of the
-processes is not staggered, this will happen for the first time
-on the invocation (or ``tick'')
-corresponding to the least common multiple of all of the periods.  In
-the case of Figure \ref{fig:cdta0:spsi0:01}, $LCM(2,5,100) = 100$, and so
-on the hundredth invocation of the master scheduling function, all three processes will
-run.  It may be undesirable to run all three processes on the same invocation of
-the master scheduling function, because this may require a large amount of CPU time.
-The general question to which we seek an answer is:  \emph{How should the
-stagger values be chosen so as to minimize the maximum amount of CPU
-time taken on any invocation of the master scheduling function?}
-
-We denote the set of $N$ processes that we must schedule
-by $\{ P_1, P_2, \ldots , P_N \}$.  
-Process $P_i$ has period $T_i$ (measured in invocations 
-or ``ticks'' of
-the master scheduling function, or ``ticks'').  Note that
-$T_i$ is dimensionless.  
-
-Each process $P_i$ also has cost
-$\tau_i$ 
-(the cost is usually the execution
-time of the function, but could in principle represent any property of
-interest).  Note that there is no required relationship between 
-$\{ T_i \}$ and $\{ \tau_i \}$, as we are not determining schedulability.
-Thus $\{ \tau_i \}$ may be specified in any time unit, or it may not
-represent time at all.
-
-We agree that each invocation of the master scheduling function
-is one ``tick'' in discrete time, and that the first invocation
-of the master scheduling function is denoted $t_1$ or $t=1$.
-With no staggering ($z_i = 0$) each process $P_i$ will run
-whenever
-
-\begin{equation}
-\label{eq:cdta0:spsi0:01}
-t \bmod T_i = 0 .
-\end{equation}
-
-We may modify the invocation sequence of a process $P_i$ by 
-varying a stagger value, which we denote $z_i$.  The stagger value
-specifies by how many ticks we will advance the invocation of
-$P_i$.  When considering stagger values, each process $P_i$ will
-run whenever
-
-\begin{equation}
-\label{eq:cdta0:spsi0:02}
-(t + z_i) \bmod T_i = 0 .
-\end{equation}
-
-At each tick, each process $P_i$ is either scheduled to run or not scheduled
-to run.  We define an infinite row vector, called the \emph{uncosted invocation
-sequence} (or simply the \emph{invocation sequence}) 
-and denoted $\rho_i(z_i)$, which contains a `1' in each column corresponding
-to a tick when the process $P_i$ run or `0' if it does not run.  For example,
-if $T_1 = 3$, 
-
-\begin{eqnarray}
-\nonumber
-\rho_1 = \rho_1(0) & = & [ \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; \ldots \; ] \\
-\label{eq:cdta0:spsi0:03}
-\rho_1(1) & = & [ \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; \ldots \; ] \\
-\nonumber
-\rho_1(2) & = & [ \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; \ldots \; ] \\
-\nonumber
-\rho_1(3) & = & [ \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; \ldots \; ]
-\end{eqnarray}
-
-\noindent{}We define but avoid using stagger values $z_i \geq T_i$, but as
-(\ref{eq:cdta0:spsi0:03}) shows, when it is necessary we define these so that
-$\rho_i(z_i) = \rho_i(z_i \bmod T_i)$.  Also as shown in (\ref{eq:cdta0:spsi0:03}),
-we use that notation
-that $\rho_i = \rho_i(0)$. 
-
-We define the \emph{costed invocation sequence}, denoted 
-$\overline{\rho_i}(z_i)$, as the infinite row
-vector similar to (\ref{eq:cdta0:spsi0:03}) but where
-the cost $\tau_i$ is used in place of `1' when a process $P_i$ runs.
-For example, if $T_1=3$ and $\tau_i = 5$,
-
-\begin{eqnarray}
-\nonumber
-\overline{\rho_1} = 
-\overline{\rho_1}(0) & = & [ \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; \ldots \; ] \\
-\label{eq:cdta0:spsi0:04}
-\overline{\rho_1}(1) & = & [ \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; \ldots \; ] \\
-\nonumber
-\overline{\rho_1}(2) & = & [ \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; \ldots \; ] \\
-\nonumber
-\overline{\rho_1}(3) & = & [ \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; \ldots \; ]
-\end{eqnarray}
-
-We define the \emph{cost calculation matrix} as the matrix formed by vertically
-concatenating, in order, the first $LCM(T_1, \ldots , T_N)$ 
-columns of either the uncosted invocation sequence
-$\rho_i(z_i)$ or the costed invocation sequence $\overline{\rho_i}(z_i)$
-of every process in the system; and then appending to this as a row vector
-the sums of 
-each column.  We choose only the first $LCM(T_1, \ldots , T_N)$ columns
-because the contents of these columns repeat in subsequent columns forever.
-We denote the cost calculation matrix as $\xi(\mathbf{z})$ (in the case
-of the uncosted invocation sequences) or as $\overline{\xi}(\mathbf{z})$
-(in the case of the costed invocation sequences); where $\mathbf{z}$ is the
-column vector consisting of all of the staggers $z_i$.  Finally, we define the 
-\emph{cost}, denoted $\xi$, as the maximum element from the last row of the 
-cost calculation matrix (it is $\xi$ that we seek to minimize by choosing
-$\mathbf{z}$).  These definitions are illustrated in the following example.
-
-\begin{vworkexamplestatement}
-\label{ex:cdta0:spsi0:01}
-For the system of 3 processes ($P_1$, $P_2$, and $P_3$) with 
-$T_1=6$, $T_2=4$, $T_3=3$, $\tau_1=2$, $\tau_2=7$, $\tau_3=5$,
-$z_1 = 2$, $z_2 = 1$, and $z_3 = 0$,
-form the uncosted and costed invocation sequences, the cost
-calculation matrices, and the costs.
-\end{vworkexamplestatement}
-\begin{vworkexampleparsection}{Solution}
-We first handle the uncosted case in full, followed by the costed
-case in full.
-
-\textbf{(Uncosted Case):}
-With $T_1=6$ and $z_1=2$, the first invocation of $P_1$ will occur
-when $(t + 2) \bmod 6 = 0$ (see Eq. \ref{eq:cdta0:spsi0:02}), at $t=4$,
-and then repeat with periodicity 6.  Thus
-
-\begin{equation}
-\label{eq:ex:cdta0:spsi0:01:01}
-\rho_1(2)  =  [ \; 0 \; 0 \; 0 \; 1 \; 0 \; 0 \; 0 \; 0 \; 0 \; 1 \; 
- 0 \; 0 \; 0 \; 0 \; 0 \; 1 \; 0 \; \ldots \; ] .
-\end{equation}
-
-\noindent{}Applying the same definition for $P_2$ and $P_3$ yields
-
-\begin{equation}
-\label{eq:ex:cdta0:spsi0:01:02}
-\rho_2(1)  =  [ \; 0 \; 0 \; 1 \; 0 \; 0 \; 0 \; 1 \; 0 \; 0 \; 0 \; 
- 1 \; 0 \; 0 \; 0 \; 1 \; 0 \; 0 \; \ldots \; ] 
-\end{equation}
-
-\noindent{}and
-
-\begin{equation}
-\label{eq:ex:cdta0:spsi0:01:03}
-\rho_3(0) = \rho_3 =  [ \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 
- 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; \ldots \; ] .
-\end{equation}
-
-We note that the column vector $\mathbf{z}$ is
-
-\begin{equation}
-\label{eq:ex:cdta0:spsi0:01:04}
-\mathbf{z}
-=
-\left[\begin{array}{c}z_1\\z_2\\z_3\end{array}\right]
-=
-\left[\begin{array}{c}2\\1\\0\end{array}\right] .
-\end{equation}
-
-$LCM(T_1, T_2, T_3) = LCM(6, 4, 3) = 12$, and so the cost calculation matrix
-can be constructed with only 12 columns, since the columns repeat with periodicity
-12:
-
-\begin{equation}
-\label{eq:ex:cdta0:spsi0:01:05}
-\xi(\mathbf{z})
-= 
-\xi\left(\left[\begin{array}{c}2\\1\\0\end{array}\right]\right)
-=
-\left[
-\begin{array}{rrrrrrrrrrrr}
-0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\
-0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\
-0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\
-0 & 0 & 2 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 1
-\end{array}
-\right]
-.
-\end{equation}
-
-Note in (\ref{eq:ex:cdta0:spsi0:01:05}) that the last row is
-the column-wise sum of the rows above it.  Note also that
-the last row gives, on a per tick basis, the number of processes
-that run.
-
-The cost $\xi$ is the maximum of the last row of (\ref{eq:ex:cdta0:spsi0:01:05}),
-and by inspection $\xi = 2$.
-
-\textbf{(Costed Case):}
-The costed invocation sequences are simply 
-(\ref{eq:ex:cdta0:spsi0:01:01}), (\ref{eq:ex:cdta0:spsi0:01:02}), and
-(\ref{eq:ex:cdta0:spsi0:01:02}) with 1's replaced by the cost appropriate
-to the process being considered;  $\tau_1$, $\tau_2$, or $\tau_3$:
-
-\begin{eqnarray}
-\nonumber
-\overline{\rho_1}(2)  & = &  [ \; 0 \; 0 \; 0 \; 2 \; 0 \; 0 \; 0 \; 0 \; 0 \; 2 \; 
- 0 \; 0 \; 0 \; 0 \; 0 \; 2 \; 0 \; \ldots \; ] \\
-\label{eq:ex:cdta0:spsi0:01:06}
-\overline{\rho_2}(1)  & = & [ \; 0 \; 0 \; 7 \; 0 \; 0 \; 0 \; 7 \; 0 \; 0 \; 0 \; 
- 7 \; 0 \; 0 \; 0 \; 7 \; 0 \; 0 \; \ldots \; ]  \\
-\nonumber
-\overline{\rho_3}(0) = \overline{\rho_3} & = &  [ \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 
- 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; \ldots \; ] 
-\end{eqnarray}
-
-The cost calculation matrix in the costed case is formed by vertically concatenating the
-first 12 columns of the rows of (\ref{eq:ex:cdta0:spsi0:01:06}), with the 
-final row containing columnwise sums:
-
-\begin{equation}
-\label{eq:ex:cdta0:spsi0:01:07}
-\overline{\xi}(\mathbf{z})
-= 
-\overline{\xi}\left(\left[\begin{array}{c}2\\1\\0\end{array}\right]\right)
-=
-\left[
-\begin{array}{rrrrrrrrrrrr}
- 0 &  0 &  0 &  2 &  0 &  0 &  0 &  0 &  0 &  2 &  0 &  0 \\
- 0 &  0 &  7 &  0 &  0 &  0 &  7 &  0 &  0 &  0 &  7 &  0 \\
- 0 &  0 &  5 &  0 &  0 &  5 &  0 &  0 &  5 &  0 &  0 &  5 \\
- 0 &  0 & 12 &  2 &  0 &  5 &  7 &  0 &  5 &  2 &  7 &  5
-\end{array}
-\right]
-.
-\end{equation}
-
-The cost $\overline{\xi}$ is the maximum of the last row of (\ref{eq:ex:cdta0:spsi0:01:07}),
-and by inspection $\overline{\xi} = 12$.
-\end{vworkexampleparsection}
-\vworkexamplefooter{}
-
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\section{Sine And Cosine}
-%Section tag: sco0
-\label{cdta0:ssco0}
-
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\section{Rotational Transformations In 2 Dimensions}
-%Section tag: RTR2
-\label{cdta0:srtr2}
-
-\index{rotation!2-D}It occurs often in microcontroller work that one needs to rotate
-coordinates in 2 dimensions (Figure \ref{fig:cdta0:srtr2:01}).  In this section,
-the most economical algorithms known for 2-dimensional
-rotation are discussed.  We assume that the
-point $\mathbf{p}$ to be rotated is specified in rectangular coordinates
-$\mathbf{p} = (p_x, p_y)$ rather than polar coordinates 
-$\mathbf{p} = (r, \theta)$; since if $\mathbf{p}$ is specified in polar coordinates
-rotation involves only addition to $\theta$ modulo $2\pi$.  We denote the point to be
-rotated $\mathbf{p} = (p_x, p_y) = \left[\begin{array}{c}p_x\\p_y\end{array}\right]$ 
-and the result of the rotation 
-$\mathbf{q} = (q_x, q_y) = \left[\begin{array}{c}q_x\\q_y\end{array}\right]$.
-We denote the length of the vector represented by $\mathbf{p}$ or $\mathbf{q}$
-by $r$, and note that 
-$r = |\mathbf{p}| = \sqrt{p_x^2 + p_y^2} = |\mathbf{q}| = \sqrt{q_x^2 + q_y^2}$.
-Because low-cost microcontrollers are used, we assume that
-$p_x, p_y, q_x, q_y \in \vworkintset$.
-We denote the desired amount of counter-clockwise rotation by $\delta$ (in radians).
-
-\begin{figure}
-\begin{huge}
-\begin{center}
-Reserved
-\end{center}
-\end{huge}
-\caption{Rotation In 2 Dimensions}
-\label{fig:cdta0:srtr2:01}
-\end{figure}
-
-A particularly na\"{\i}ve algorithm to use in microcontroller work is to 
-convert $\mathbf{p} = (p_x, p_y)$ to polar coordinates
-$\mathbf{p} = (r, \theta)$, rotate to obtain 
-$\mathbf{q} = (r, (\theta + \delta) \bmod 2\pi)$, and then convert back to 
-rectangular coordinates $\mathbf{q} = (q_x, q_y)$.  
-This algorithm is na\"{\i}ve because trigonometric and
-inverse trigonometric functions are required, which are not economical to implement 
-on microcontrollers.  We seek if possible algorithms which operate exclusively in
-rectangular coordinates and which require little or no evaluation of
-trigonometric and inverse trigonometric functions.
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\subsection{Matrix Rotation In 2 Dimensions}
-%Section tag: MRT0
-\label{cdta0:srtr2:smrt2}
-
-Assume we wish to rotate the vector
-
-\begin{equation}
-\label{eq:cdta0:srtr2:smrt2:01}
-\mathbf{p} 
-= (p_x, p_y) 
-= \left[\begin{array}{c}p_x\\p_y\end{array}\right]
-= (r \cos \theta, r \sin \theta) 
-= \left[\begin{array}{c}r \cos \theta\\r \sin \theta\end{array}\right]
-\end{equation}
-
-\noindent{}by an angle of $\delta$ to give the vector
-
-\begin{eqnarray}
-\label{eq:cdta0:srtr2:smrt2:02}
-\mathbf{q} & = & (q_x, q_y) = \left[\begin{array}{c}q_x\\q_y\end{array}\right] \\
-\nonumber & = & (r \cos (\theta + \delta), r \sin (\theta + \delta)) 
-= \left[\begin{array}{c}r \cos (\theta + \delta)\\r \sin (\theta+\delta)\end{array}\right].
-\end{eqnarray}
-
-\noindent{}Recall from standard trigonometry identities that for sines and cosines of 
-sums of angles that
-
-\begin{eqnarray}
-\label{eq:cdta0:srtr2:smrt2:03}
-\left[\begin{array}{c}r \cos (\theta + \delta)\\r \sin (\theta+\delta)\end{array}\right]
-& = &
-\left[\begin{array}{c}r \cos \theta \cos \delta - r \sin \theta \sin \delta \\
-                      r \sin \theta \cos \delta + r \cos \theta \sin \delta \end{array}\right] \\
-\label{eq:cdta0:srtr2:smrt2:04}
-& = & 
-\left[\begin{array}{c}p_x \cos \delta - p_y \sin \delta \\
-                      p_x \sin \delta + p_y \cos \delta \end{array}\right] \\
-\label{eq:cdta0:srtr2:smrt2:05}
-& = & 
-\left[\begin{array}{c}q_x\\q_y\end{array}\right]
-=
-\left[\begin{array}{cc}\cos \delta & - \sin \delta \\
-                       \sin \delta & \;\;\;\cos \delta \end{array}\right]
-\left[\begin{array}{c}p_x\\p_y\end{array}\right] .
-\end{eqnarray}
-
-\noindent{}Note that (\ref{eq:cdta0:srtr2:smrt2:05})
-reduces the rotation problem to four multiplications and two additions
-(the matrix multiplication), provided that some approximation of the sine
-and cosine functions is available (see Section \ref{cdta0:ssco0}).  
-
-To apply (\ref{eq:cdta0:srtr2:smrt2:05}), the embedded software
-may or may not need to approximate the sine and cosine functions.
-For some applications, if the angle of rotation is fixed, 
-$\sin \delta$ and
-$\cos \delta$ may be calculated at compile time and tabulated in 
-ROM rather than $\delta$ (so that the embedded software does not need
-to approximate these functions).  For other applications,
-sine and cosine must be approximated (see Section \ref{cdta0:ssco0}).
-
-The 2 $\times$ 2 matrix in (\ref{eq:cdta0:srtr2:smrt2:05})
-is called the \index{rotation matrix}\emph{rotation matrix}.  There are
-other functionally equivalent ways to derive this result, including complex
-arithmetic (i.e. phasor analysis) and graphical geometric arguments.
-
-As pointed out in Section \ref{cdta0:ssco0}, the best way to approximate
-sine and cosine in low cost microcontrollers is usually by tabulation of the 
-values of $\sin \delta$ for $\delta \in [0, \pi/2]$.  Using the 
-techniques presented in Section \ref{cdta0:ssco0} for approximation of
-sine and cosine and using (\ref{eq:cdta0:srtr2:smrt2:05}), rotation can usually
-be carried out using around 20 machine instructions.
-
-If a vector is rotated repeatedly using (\ref{eq:cdta0:srtr2:smrt2:05}), cumulative
-truncation and rounding errors may eventually yield a vector 
-$\mathbf{q}$ with a significantly different
-magnitude $|\mathbf{q}| = \sqrt{q_x^2 + q_y^2}$ than the starting vector.
-It should be possible to develop an algorithm similar in spirit to the 
-Bresenham circle algorithm (see Section \ref{cdta0:srtr2:sbrt2}) to
-adjust the magnitude of a vector to correct for cumulative 
-errors while leaving its direction as nearly unchanged
-as possible (see Exercise \ref{exe:cdta0:sexe0:01}).
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\subsection{Bresenham Rotation In 2 Dimensions}
-%Section tag: BRT0
-\label{cdta0:srtr2:sbrt2}
-
-Depending on the application \ldots{}
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\section{Rotational Transformations In 3 Dimensions}
-%Section tag: RTR3
-\label{cdta0:srtr3}
-
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\section{Acknowledgements}
-%Section tag: ACK0
-\label{cdta0:sack0}
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\section{Exercises}
-%Section tag: sexe0
-\label{cdta0:sexe0}
-
-\begin{vworkexercisestatement}
-\label{exe:cdta0:sexe0:01}
-Develop an algorithm similar in spirit to the Bresenham circle
-algorithm to adjust a vector $\mathbf{q} = (q_x, q_y)$ with 
-cumulative magnitude errors due to repeated rotations to 
-a vector $\mathbf{z} = (z_x, z_y)$ which points as nearly as
-possible in the same direction as $\mathbf{q}$ but with 
-a desired magnitude $r$.
-\end{vworkexercisestatement}
-\vworkexercisefooter{}
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\vfill
-\noindent\begin{figure}[!b]
-\noindent\rule[-0.25in]{\textwidth}{1pt}
-\begin{tiny}
-\begin{verbatim}
-$RCSfile: c_dta0.tex,v $
-$Source: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_dta0/c_dta0.tex,v $
-$Revision: 1.5 $
-$Author: dtashley $
-$Date: 2003/03/03 23:50:43 $
-\end{verbatim}
-\end{tiny}
-\noindent\rule[0.25in]{\textwidth}{1pt}
-\end{figure}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-% $Log: c_dta0.tex,v $
-% 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
+%$Header$
+
+\chapter[\cdtazeroshorttitle{}]{\cdtazerolongtitle{}}
+
+\label{cdta0}
+
+\beginchapterquote{``Under construction!''}
+                     {Under construction!}
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\section{Introduction}
+%Section tag: INT0
+\label{cdta0:sint0}
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\section[Fixed-Period Process Scheduling]
+        {Load Balancing For Fixed-Period Process Scheduling Using Integer Counting}
+%Section tag: PSI0
+\label{cdta0:spsi0}
+
+\index{process scheduling!using integer counting}It happens in a variety of 
+contexts in small microcontroller work
+that one schedules processes (which may be implemented as subroutines
+or functions) with a fixed period
+using integer counting.  Such scheduling tends to take the form of
+the code snippet in  
+Figure \ref{fig:cdta0:spsi0:01}.  Typically a ``master'' scheduling function
+is called at a periodic rate, and the scheduled functions are called
+once every $T_i$ invocations of the master scheduling function ($T_i$ is
+defined later).  Note in the figure that every scheduled function
+is called with perfect periodicity, but that the invocation sequence
+can be staggered.  Note also in the figure that the comments assume
+that the scheduling function is called every 10ms (which is typical in
+microcontroller work). 
+
+\begin{figure}
+\begin{small}
+\begin{verbatim}
+/* The following "stagger" values are what we are attempting to
+** analytically determine at compile-time so as to minimize the
+** maximum CPU time used in the worst-case tick. */ 
+#define P1_STAGGER   (0)
+#define P2_STAGGER   (0)
+#define P3_STAGGER   (0)
+
+/* The periods are fixed and not subject to change.  The periods
+** are input to any compile-time algorithm employed. */
+#define P1_PERIOD    (2)   /* Every   20ms.            */
+#define P2_PERIOD    (5)   /* Every  100ms.            */
+#define P3_PERIOD  (100)   /* Every 1000ms = 1 second. */
+
+/* These are the integer counters.  Their initial load values, which
+** determine the staggering, are the parameters we seek to
+** determine. */
+static unsigned char p1_ctr = P1_STAGGER;
+static unsigned char p2_ctr = P2_STAGGER;
+static unsigned char p3_ctr = P3_STAGGER;
+
+/* This is the master scheduling function called every 10ms.  It 
+** calls the periodic functions.  Note that this is an integer
+** counting problem. */
+void master_scheduling_function(void)
+   {
+   p1_ctr++;
+   if (p1_ctr >= P1_PERIOD)
+      {
+      Process_1();  /* Call the process.   */
+      p1_ctr = 0;   /* Reset the counter.  */
+      }
+   p2_ctr++;
+   if (p2_ctr >= P2_PERIOD)
+      {
+      Process_2();  /* Call the process.   */
+      p2_ctr = 0;   /* Reset the counter.  */
+      }
+   p3_ctr++;
+   if (p3_ctr >= P3_PERIOD)
+      {
+      Process_3();  /* Call the process.   */
+      p3_ctr = 0;   /* Reset the counter.  */
+      }
+   }
+\end{verbatim}
+\end{small}
+\caption{Code Snippet Illustrating Fixed-Period Integer Counter Process Scheduling
+        (3 Processes)}
+\label{fig:cdta0:spsi0:01}
+\end{figure}
+
+
+It is easy to see from Figure \ref{fig:cdta0:spsi0:01} that it may happen
+on a single invocation of the master scheduling function that several or all of 
+the processes are scheduled.  If the scheduling of the
+processes is not staggered, this will happen for the first time
+on the invocation (or ``tick'')
+corresponding to the least common multiple of all of the periods.  In
+the case of Figure \ref{fig:cdta0:spsi0:01}, $LCM(2,5,100) = 100$, and so
+on the hundredth invocation of the master scheduling function, all three processes will
+run.  It may be undesirable to run all three processes on the same invocation of
+the master scheduling function, because this may require a large amount of CPU time.
+The general question to which we seek an answer is:  \emph{How should the
+stagger values be chosen so as to minimize the maximum amount of CPU
+time taken on any invocation of the master scheduling function?}
+
+We denote the set of $N$ processes that we must schedule
+by $\{ P_1, P_2, \ldots , P_N \}$.  
+Process $P_i$ has period $T_i$ (measured in invocations 
+or ``ticks'' of
+the master scheduling function, or ``ticks'').  Note that
+$T_i$ is dimensionless.  
+
+Each process $P_i$ also has cost
+$\tau_i$ 
+(the cost is usually the execution
+time of the function, but could in principle represent any property of
+interest).  Note that there is no required relationship between 
+$\{ T_i \}$ and $\{ \tau_i \}$, as we are not determining schedulability.
+Thus $\{ \tau_i \}$ may be specified in any time unit, or it may not
+represent time at all.
+
+We agree that each invocation of the master scheduling function
+is one ``tick'' in discrete time, and that the first invocation
+of the master scheduling function is denoted $t_1$ or $t=1$.
+With no staggering ($z_i = 0$) each process $P_i$ will run
+whenever
+
+\begin{equation}
+\label{eq:cdta0:spsi0:01}
+t \bmod T_i = 0 .
+\end{equation}
+
+We may modify the invocation sequence of a process $P_i$ by 
+varying a stagger value, which we denote $z_i$.  The stagger value
+specifies by how many ticks we will advance the invocation of
+$P_i$.  When considering stagger values, each process $P_i$ will
+run whenever
+
+\begin{equation}
+\label{eq:cdta0:spsi0:02}
+(t + z_i) \bmod T_i = 0 .
+\end{equation}
+
+At each tick, each process $P_i$ is either scheduled to run or not scheduled
+to run.  We define an infinite row vector, called the \emph{uncosted invocation
+sequence} (or simply the \emph{invocation sequence}) 
+and denoted $\rho_i(z_i)$, which contains a `1' in each column corresponding
+to a tick when the process $P_i$ run or `0' if it does not run.  For example,
+if $T_1 = 3$, 
+
+\begin{eqnarray}
+\nonumber
+\rho_1 = \rho_1(0) & = & [ \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; \ldots \; ] \\
+\label{eq:cdta0:spsi0:03}
+\rho_1(1) & = & [ \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; \ldots \; ] \\
+\nonumber
+\rho_1(2) & = & [ \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; \ldots \; ] \\
+\nonumber
+\rho_1(3) & = & [ \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; \ldots \; ]
+\end{eqnarray}
+
+\noindent{}We define but avoid using stagger values $z_i \geq T_i$, but as
+(\ref{eq:cdta0:spsi0:03}) shows, when it is necessary we define these so that
+$\rho_i(z_i) = \rho_i(z_i \bmod T_i)$.  Also as shown in (\ref{eq:cdta0:spsi0:03}),
+we use that notation
+that $\rho_i = \rho_i(0)$. 
+
+We define the \emph{costed invocation sequence}, denoted 
+$\overline{\rho_i}(z_i)$, as the infinite row
+vector similar to (\ref{eq:cdta0:spsi0:03}) but where
+the cost $\tau_i$ is used in place of `1' when a process $P_i$ runs.
+For example, if $T_1=3$ and $\tau_i = 5$,
+
+\begin{eqnarray}
+\nonumber
+\overline{\rho_1} = 
+\overline{\rho_1}(0) & = & [ \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; \ldots \; ] \\
+\label{eq:cdta0:spsi0:04}
+\overline{\rho_1}(1) & = & [ \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; \ldots \; ] \\
+\nonumber
+\overline{\rho_1}(2) & = & [ \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; \ldots \; ] \\
+\nonumber
+\overline{\rho_1}(3) & = & [ \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; \ldots \; ]
+\end{eqnarray}
+
+We define the \emph{cost calculation matrix} as the matrix formed by vertically
+concatenating, in order, the first $LCM(T_1, \ldots , T_N)$ 
+columns of either the uncosted invocation sequence
+$\rho_i(z_i)$ or the costed invocation sequence $\overline{\rho_i}(z_i)$
+of every process in the system; and then appending to this as a row vector
+the sums of 
+each column.  We choose only the first $LCM(T_1, \ldots , T_N)$ columns
+because the contents of these columns repeat in subsequent columns forever.
+We denote the cost calculation matrix as $\xi(\mathbf{z})$ (in the case
+of the uncosted invocation sequences) or as $\overline{\xi}(\mathbf{z})$
+(in the case of the costed invocation sequences); where $\mathbf{z}$ is the
+column vector consisting of all of the staggers $z_i$.  Finally, we define the 
+\emph{cost}, denoted $\xi$, as the maximum element from the last row of the 
+cost calculation matrix (it is $\xi$ that we seek to minimize by choosing
+$\mathbf{z}$).  These definitions are illustrated in the following example.
+
+\begin{vworkexamplestatement}
+\label{ex:cdta0:spsi0:01}
+For the system of 3 processes ($P_1$, $P_2$, and $P_3$) with 
+$T_1=6$, $T_2=4$, $T_3=3$, $\tau_1=2$, $\tau_2=7$, $\tau_3=5$,
+$z_1 = 2$, $z_2 = 1$, and $z_3 = 0$,
+form the uncosted and costed invocation sequences, the cost
+calculation matrices, and the costs.
+\end{vworkexamplestatement}
+\begin{vworkexampleparsection}{Solution}
+We first handle the uncosted case in full, followed by the costed
+case in full.
+
+\textbf{(Uncosted Case):}
+With $T_1=6$ and $z_1=2$, the first invocation of $P_1$ will occur
+when $(t + 2) \bmod 6 = 0$ (see Eq. \ref{eq:cdta0:spsi0:02}), at $t=4$,
+and then repeat with periodicity 6.  Thus
+
+\begin{equation}
+\label{eq:ex:cdta0:spsi0:01:01}
+\rho_1(2)  =  [ \; 0 \; 0 \; 0 \; 1 \; 0 \; 0 \; 0 \; 0 \; 0 \; 1 \; 
+ 0 \; 0 \; 0 \; 0 \; 0 \; 1 \; 0 \; \ldots \; ] .
+\end{equation}
+
+\noindent{}Applying the same definition for $P_2$ and $P_3$ yields
+
+\begin{equation}
+\label{eq:ex:cdta0:spsi0:01:02}
+\rho_2(1)  =  [ \; 0 \; 0 \; 1 \; 0 \; 0 \; 0 \; 1 \; 0 \; 0 \; 0 \; 
+ 1 \; 0 \; 0 \; 0 \; 1 \; 0 \; 0 \; \ldots \; ] 
+\end{equation}
+
+\noindent{}and
+
+\begin{equation}
+\label{eq:ex:cdta0:spsi0:01:03}
+\rho_3(0) = \rho_3 =  [ \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 
+ 0 \; 1 \; 0 \; 0 \; 1 \; 0 \; 0 \; \ldots \; ] .
+\end{equation}
+
+We note that the column vector $\mathbf{z}$ is
+
+\begin{equation}
+\label{eq:ex:cdta0:spsi0:01:04}
+\mathbf{z}
+=
+\left[\begin{array}{c}z_1\\z_2\\z_3\end{array}\right]
+=
+\left[\begin{array}{c}2\\1\\0\end{array}\right] .
+\end{equation}
+
+$LCM(T_1, T_2, T_3) = LCM(6, 4, 3) = 12$, and so the cost calculation matrix
+can be constructed with only 12 columns, since the columns repeat with periodicity
+12:
+
+\begin{equation}
+\label{eq:ex:cdta0:spsi0:01:05}
+\xi(\mathbf{z})
+= 
+\xi\left(\left[\begin{array}{c}2\\1\\0\end{array}\right]\right)
+=
+\left[
+\begin{array}{rrrrrrrrrrrr}
+0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\
+0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\
+0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\
+0 & 0 & 2 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 1
+\end{array}
+\right]
+.
+\end{equation}
+
+Note in (\ref{eq:ex:cdta0:spsi0:01:05}) that the last row is
+the column-wise sum of the rows above it.  Note also that
+the last row gives, on a per tick basis, the number of processes
+that run.
+
+The cost $\xi$ is the maximum of the last row of (\ref{eq:ex:cdta0:spsi0:01:05}),
+and by inspection $\xi = 2$.
+
+\textbf{(Costed Case):}
+The costed invocation sequences are simply 
+(\ref{eq:ex:cdta0:spsi0:01:01}), (\ref{eq:ex:cdta0:spsi0:01:02}), and
+(\ref{eq:ex:cdta0:spsi0:01:02}) with 1's replaced by the cost appropriate
+to the process being considered;  $\tau_1$, $\tau_2$, or $\tau_3$:
+
+\begin{eqnarray}
+\nonumber
+\overline{\rho_1}(2)  & = &  [ \; 0 \; 0 \; 0 \; 2 \; 0 \; 0 \; 0 \; 0 \; 0 \; 2 \; 
+ 0 \; 0 \; 0 \; 0 \; 0 \; 2 \; 0 \; \ldots \; ] \\
+\label{eq:ex:cdta0:spsi0:01:06}
+\overline{\rho_2}(1)  & = & [ \; 0 \; 0 \; 7 \; 0 \; 0 \; 0 \; 7 \; 0 \; 0 \; 0 \; 
+ 7 \; 0 \; 0 \; 0 \; 7 \; 0 \; 0 \; \ldots \; ]  \\
+\nonumber
+\overline{\rho_3}(0) = \overline{\rho_3} & = &  [ \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 
+ 0 \; 5 \; 0 \; 0 \; 5 \; 0 \; 0 \; \ldots \; ] 
+\end{eqnarray}
+
+The cost calculation matrix in the costed case is formed by vertically concatenating the
+first 12 columns of the rows of (\ref{eq:ex:cdta0:spsi0:01:06}), with the 
+final row containing columnwise sums:
+
+\begin{equation}
+\label{eq:ex:cdta0:spsi0:01:07}
+\overline{\xi}(\mathbf{z})
+= 
+\overline{\xi}\left(\left[\begin{array}{c}2\\1\\0\end{array}\right]\right)
+=
+\left[
+\begin{array}{rrrrrrrrrrrr}
+ 0 &  0 &  0 &  2 &  0 &  0 &  0 &  0 &  0 &  2 &  0 &  0 \\
+ 0 &  0 &  7 &  0 &  0 &  0 &  7 &  0 &  0 &  0 &  7 &  0 \\
+ 0 &  0 &  5 &  0 &  0 &  5 &  0 &  0 &  5 &  0 &  0 &  5 \\
+ 0 &  0 & 12 &  2 &  0 &  5 &  7 &  0 &  5 &  2 &  7 &  5
+\end{array}
+\right]
+.
+\end{equation}
+
+The cost $\overline{\xi}$ is the maximum of the last row of (\ref{eq:ex:cdta0:spsi0:01:07}),
+and by inspection $\overline{\xi} = 12$.
+\end{vworkexampleparsection}
+\vworkexamplefooter{}
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\section{Sine And Cosine}
+%Section tag: sco0
+\label{cdta0:ssco0}
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\section{Rotational Transformations In 2 Dimensions}
+%Section tag: RTR2
+\label{cdta0:srtr2}
+
+\index{rotation!2-D}It occurs often in microcontroller work that one needs to rotate
+coordinates in 2 dimensions (Figure \ref{fig:cdta0:srtr2:01}).  In this section,
+the most economical algorithms known for 2-dimensional
+rotation are discussed.  We assume that the
+point $\mathbf{p}$ to be rotated is specified in rectangular coordinates
+$\mathbf{p} = (p_x, p_y)$ rather than polar coordinates 
+$\mathbf{p} = (r, \theta)$; since if $\mathbf{p}$ is specified in polar coordinates
+rotation involves only addition to $\theta$ modulo $2\pi$.  We denote the point to be
+rotated $\mathbf{p} = (p_x, p_y) = \left[\begin{array}{c}p_x\\p_y\end{array}\right]$ 
+and the result of the rotation 
+$\mathbf{q} = (q_x, q_y) = \left[\begin{array}{c}q_x\\q_y\end{array}\right]$.
+We denote the length of the vector represented by $\mathbf{p}$ or $\mathbf{q}$
+by $r$, and note that 
+$r = |\mathbf{p}| = \sqrt{p_x^2 + p_y^2} = |\mathbf{q}| = \sqrt{q_x^2 + q_y^2}$.
+Because low-cost microcontrollers are used, we assume that
+$p_x, p_y, q_x, q_y \in \vworkintset$.
+We denote the desired amount of counter-clockwise rotation by $\delta$ (in radians).
+
+\begin{figure}
+\begin{huge}
+\begin{center}
+Reserved
+\end{center}
+\end{huge}
+\caption{Rotation In 2 Dimensions}
+\label{fig:cdta0:srtr2:01}
+\end{figure}
+
+A particularly na\"{\i}ve algorithm to use in microcontroller work is to 
+convert $\mathbf{p} = (p_x, p_y)$ to polar coordinates
+$\mathbf{p} = (r, \theta)$, rotate to obtain 
+$\mathbf{q} = (r, (\theta + \delta) \bmod 2\pi)$, and then convert back to 
+rectangular coordinates $\mathbf{q} = (q_x, q_y)$.  
+This algorithm is na\"{\i}ve because trigonometric and
+inverse trigonometric functions are required, which are not economical to implement 
+on microcontrollers.  We seek if possible algorithms which operate exclusively in
+rectangular coordinates and which require little or no evaluation of
+trigonometric and inverse trigonometric functions.
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\subsection{Matrix Rotation In 2 Dimensions}
+%Section tag: MRT0
+\label{cdta0:srtr2:smrt2}
+
+Assume we wish to rotate the vector
+
+\begin{equation}
+\label{eq:cdta0:srtr2:smrt2:01}
+\mathbf{p} 
+= (p_x, p_y) 
+= \left[\begin{array}{c}p_x\\p_y\end{array}\right]
+= (r \cos \theta, r \sin \theta) 
+= \left[\begin{array}{c}r \cos \theta\\r \sin \theta\end{array}\right]
+\end{equation}
+
+\noindent{}by an angle of $\delta$ to give the vector
+
+\begin{eqnarray}
+\label{eq:cdta0:srtr2:smrt2:02}
+\mathbf{q} & = & (q_x, q_y) = \left[\begin{array}{c}q_x\\q_y\end{array}\right] \\
+\nonumber & = & (r \cos (\theta + \delta), r \sin (\theta + \delta)) 
+= \left[\begin{array}{c}r \cos (\theta + \delta)\\r \sin (\theta+\delta)\end{array}\right].
+\end{eqnarray}
+
+\noindent{}Recall from standard trigonometry identities that for sines and cosines of 
+sums of angles that
+
+\begin{eqnarray}
+\label{eq:cdta0:srtr2:smrt2:03}
+\left[\begin{array}{c}r \cos (\theta + \delta)\\r \sin (\theta+\delta)\end{array}\right]
+& = &
+\left[\begin{array}{c}r \cos \theta \cos \delta - r \sin \theta \sin \delta \\
+                      r \sin \theta \cos \delta + r \cos \theta \sin \delta \end{array}\right] \\
+\label{eq:cdta0:srtr2:smrt2:04}
+& = & 
+\left[\begin{array}{c}p_x \cos \delta - p_y \sin \delta \\
+                      p_x \sin \delta + p_y \cos \delta \end{array}\right] \\
+\label{eq:cdta0:srtr2:smrt2:05}
+& = & 
+\left[\begin{array}{c}q_x\\q_y\end{array}\right]
+=
+\left[\begin{array}{cc}\cos \delta & - \sin \delta \\
+                       \sin \delta & \;\;\;\cos \delta \end{array}\right]
+\left[\begin{array}{c}p_x\\p_y\end{array}\right] .
+\end{eqnarray}
+
+\noindent{}Note that (\ref{eq:cdta0:srtr2:smrt2:05})
+reduces the rotation problem to four multiplications and two additions
+(the matrix multiplication), provided that some approximation of the sine
+and cosine functions is available (see Section \ref{cdta0:ssco0}).  
+
+To apply (\ref{eq:cdta0:srtr2:smrt2:05}), the embedded software
+may or may not need to approximate the sine and cosine functions.
+For some applications, if the angle of rotation is fixed, 
+$\sin \delta$ and
+$\cos \delta$ may be calculated at compile time and tabulated in 
+ROM rather than $\delta$ (so that the embedded software does not need
+to approximate these functions).  For other applications,
+sine and cosine must be approximated (see Section \ref{cdta0:ssco0}).
+
+The 2 $\times$ 2 matrix in (\ref{eq:cdta0:srtr2:smrt2:05})
+is called the \index{rotation matrix}\emph{rotation matrix}.  There are
+other functionally equivalent ways to derive this result, including complex
+arithmetic (i.e. phasor analysis) and graphical geometric arguments.
+
+As pointed out in Section \ref{cdta0:ssco0}, the best way to approximate
+sine and cosine in low cost microcontrollers is usually by tabulation of the 
+values of $\sin \delta$ for $\delta \in [0, \pi/2]$.  Using the 
+techniques presented in Section \ref{cdta0:ssco0} for approximation of
+sine and cosine and using (\ref{eq:cdta0:srtr2:smrt2:05}), rotation can usually
+be carried out using around 20 machine instructions.
+
+If a vector is rotated repeatedly using (\ref{eq:cdta0:srtr2:smrt2:05}), cumulative
+truncation and rounding errors may eventually yield a vector 
+$\mathbf{q}$ with a significantly different
+magnitude $|\mathbf{q}| = \sqrt{q_x^2 + q_y^2}$ than the starting vector.
+It should be possible to develop an algorithm similar in spirit to the 
+Bresenham circle algorithm (see Section \ref{cdta0:srtr2:sbrt2}) to
+adjust the magnitude of a vector to correct for cumulative 
+errors while leaving its direction as nearly unchanged
+as possible (see Exercise \ref{exe:cdta0:sexe0:01}).
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\subsection{Bresenham Rotation In 2 Dimensions}
+%Section tag: BRT0
+\label{cdta0:srtr2:sbrt2}
+
+Depending on the application \ldots{}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\section{Rotational Transformations In 3 Dimensions}
+%Section tag: RTR3
+\label{cdta0:srtr3}
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\section{Acknowledgements}
+%Section tag: ACK0
+\label{cdta0:sack0}
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\section{Exercises}
+%Section tag: sexe0
+\label{cdta0:sexe0}
+
+\begin{vworkexercisestatement}
+\label{exe:cdta0:sexe0:01}
+Develop an algorithm similar in spirit to the Bresenham circle
+algorithm to adjust a vector $\mathbf{q} = (q_x, q_y)$ with 
+cumulative magnitude errors due to repeated rotations to 
+a vector $\mathbf{z} = (z_x, z_y)$ which points as nearly as
+possible in the same direction as $\mathbf{q}$ but with 
+a desired magnitude $r$.
+\end{vworkexercisestatement}
+\vworkexercisefooter{}
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\vfill
+\noindent\begin{figure}[!b]
+\noindent\rule[-0.25in]{\textwidth}{1pt}
+\begin{tiny}
+\begin{verbatim}
+$RCSfile: c_dta0.tex,v $
+$Source: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_dta0/c_dta0.tex,v $
+$Revision: 1.5 $
+$Author: dtashley $
+$Date: 2003/03/03 23:50:43 $
+\end{verbatim}
+\end{tiny}
+\noindent\rule[0.25in]{\textwidth}{1pt}
+\end{figure}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% $Log: c_dta0.tex,v $
+% 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