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

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

Parent Directory | Revision Log | View Patch Patch

-revision 4 by dashley,
Thu Oct  6 03:15:02 2016 UTC
+revision 140 by dashley,
Mon Jul  3 01:59:16 2017 UTC
 Line 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$
  \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 \; 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 \;
 \; 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 \;
 \; 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
 :
  \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 & 1 & 0 & 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 & 1 \\
 & 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 \; 2 \; 0 \; \ldots \; ] \\
  \label{eq:ex:cdta0:spsi0:01:06}
  \overline{\rho_2}(1)  & = & [ \; 0 \; 0 \; 7 \; 0 \; 0 \; 0 \; 7 \; 0 \; 0 \; 0 \;
 \; 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 \;
 \; 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 &  2 &  0 &  0 &  0 &  0 &  0 &  2 &  0 &  0 \\
 &  0 &  7 &  0 &  0 &  0 &  7 &  0 &  0 &  0 &  7 &  0 \\
 &  0 &  5 &  0 &  0 &  5 &  0 &  0 &  5 &  0 &  0 &  5 \\
 &  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

 Legend:



Removed from v.4
 


changed lines


 
Added in v.140
 Legend:



Removed from v.4
 


changed lines


 
Added in v.140
-Removed from v.4
+Added in v.140

dashley@gmail.com	ViewVC Help
Powered by ViewVC 1.1.25