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

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

Parent Directory | Revision Log | View Patch Patch

-revision 3 by dashley,
Wed Oct  5 03:27:36 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_bal0/c_bal0.tex,v 1.10 2003/11/03 02:14:24 dtashley Exp $
+ %$Header$
  \chapter[\cbalzeroshorttitle{}]{\cbalzerolongtitle{}}
  \label{cbal0}
  \section{Introduction, Definition, And History Of Boolean Algebra}
  %Section tag:  INT0
  \label{cbal0:sint0}
  \index{Boolean algebra}
  In this chapter, we review methods of
  simplifying \index{Boolean function}Boolean functions, and
  show how such methods can be used to simplify software constructs
  or to construct software which is more compact (in ROM or RAM)
  or executes more quicky.
  Boolean algebra is named after \index{Boole, George}George Boole,
  a 19th-century British mathematician.
  A fairly concise biography of George Boole comes from
  \cite{bibref:w:georgeboolebio01}:
  \begin{quote}
  George Boole first attended a school in Lincoln, then a commerical school.
  His early instruction in mathematics, however, was from his father who
  also gave George a liking for constructing optical instruments.  George's
  interests turned to languages and he received instruction in Latin from a
  local bookseller.
  By the age of 12 George had become so skilled in Latin that it provoked
  an argument.  He translated an ode by the Latin poet Horace which his
  father was so proud of that he had it published.  However the talent was
  such that a local schoolmaster disputed that any 12 year old could
  have written with such depth.
  Boole did not study for an academic degree, but from the age of 16 he was an
  assistant school teacher.  He maintained his interest in languages
  and intended to enter the Church.  From 1835, however, he seems to have
  changed his mind for he opened his own school and began to study mathematics
  on his own.  He was later to realize that he had almost wasted five years
  in trying to teach himself the subject instead of having a skilled teacher.
  At this time Boole studied the works of Laplace and Lagrange, making
  notes which would later be the basis for his first mathematics paper.
  However he did receive encouragement from Duncan Gregory who at this
  time was in Cambridge and the editor of the recently founded
  \emph{Cambridge Mathematical Journal}.
  Boole was unable to take Duncan Gregory's advice and study courses at
  Cambridge as he required the income from his school to look after
  his parents.  However he began publishing in the \emph{Cambridge
  Mathematical Journal} and his interests were also influenced by Duncan Gregory
  as he began to study algebra. An application of algebraic methods
  to the solution of differential equations was published by Boole in the
  \emph{Transactions of the Royal Society} and for this work he received
  the Society's Royal Medal.  His mathematical work was beginning to bring
  him fame.
  Boole was appointed to the chair of mathematics at Queens College,
  Cork in 1849. He taught there for the rest of his life, gaining a reputation
  as an outstanding and dedicated teacher.
  In 1854 he published \emph{An investigation into the Laws of Thought, on
  Which are founded the Mathematical Theories of Logic and Probabilities}.
  Boole approached logic in a new way reducing it to a simple algebra,
  incorporating logic into mathematics.  He pointed out the analogy
  between algebraic symbols and those that represent logical forms.
  It began the algebra of logic called Boolean algebra which now finds
  application in computer construction, switching circuits etc.
  Boole also worked on differential equations, the influential
  \emph{Treatise on Differential Equations} appeared in 1859, the calculus of finite
  differences, \emph{Treatise on the Calculus of Finite Differences} (1860),
  and general methods in probability. He published around 50 papers and
  was one of the first to investigate the basic properties of numbers, such
  as the distributive property, that underlie the subject of algebra.
  Many honours were given to Boole as the genius in his work was recognised.
  He received honorary degrees from the universities of Dublin
  and Oxford and was elected a Fellow of the Royal Society (1857).
  However his career, which was started rather late, came to an unfortunately
  early end when he died at the age of 49.  The circumstances are described
  by Macfarlane in [17]\footnote{As reproduced from
  \cite{bibref:w:georgeboolebio01}---this is not a valid reference
  number in this work.} as follows:
  \begin{quote}
  One day in 1864 he walked from his residence to the College,
  a distance of two miles, in the drenching rain, and lectured in wet
  clothes.  The result was a feverish cold which soon fell upon his
  lungs and terminated his career \ldots{}
  \end{quote}
  What Macfarlane fails to say is that Boole's wife
  (Mary---niece of Sir George Everest, after whom the mountain is named) believed that a
  remedy should resemble the cause. She put Boole to bed and threw
  buckets of water over the bed since his illness had been caused by getting
  wet.
  Hirst described Boole as:
  \begin{quote}
  \ldots{} evidently an earnest able and at the same time a genial man.
  \end{quote}
  His work was praised by \index{DeMorgan, Augustus}De Morgan who said:
  \begin{quote}
  Boole's system of logic is but one of many proofs of genius and patience combined.
  \ldots{} That the symbolic processes of algebra,
  invented as tools of numerical calculation, should be competent to
  express every act of thought, and to furnish the grammar and
  dictionary of an all-containing system of logic, would not have
  been believed until it was proved. When Hobbes \ldots{} published his
  ``Computation or Logique'' he had a remote glimpse of some of the points which
  are placed in the light of day by Mr Boole.
  \end{quote}
  Boolean algebra has wide applications in telephone switching and the
  design of modern computers. Boole's work has to be seen as a
  fundamental step in today's computer revolution.
  (Article by: J. J. O'Connor and E. F. Robertson.)
  \end{quote}
  In the preface of
  \cite{bibref:b:whitesittbooleanalgandapps}, Whitesitt explains the
  significance of Boole's work:
  \begin{quote}
  George Boole (1815-1864) introduced in his book \emph{The Laws Of Thought}
  the first systematic treatment of logic and developed for this purpose
  the algebraic system now known by his name, Boolean algebra.  Few
  mathematical works of the last 100 years have had a greater impact
  upon mathematics and philosophy than this famous book.  The significance
  of the work has been well expressed by Augustus De Morgan:
  \begin{quote}
  That the symbolic processes of algebra, invented as tools of numerical
  calculation, should be competent to express every act of thought, and to
  furnish the grammar and dictionary of an all-containing system of
  logic, would not have been believed until it was proved in
  \emph{Laws Of Thought}.
  \end{quote}
  In addition to its applications in the field of logic, Boolean algebra
  has two other important applications.  The first of these arises from
  the fact that Boolean algebra is the natural algebra with which to
  treat the combination of sets of elements under the operations of
  intersection and union of sets.  With the addition of the idea of
  ``number of elements'' in a set, Boolean algebra becomes the
  foundation for the theory of probability.  The algebra
  of sets is also important in many other branches of mathematics.
  With the publication of two papers approximately 20 years
  ago,\footnote{Whitesitt's book was first published in 1961,
  so Whitesitt probably means \emph{20 years ago} with
  respect to 1961.}
  \index{Shannon, Claude E.}Claude E. Shannon introduced a new
  area of application of
  Boolean algebra when he showed that the basic properties of
  series and parallel combinations of bistable electrical
  devices such as relays could be adequately represented
  by this algebra.  Since this time, Boolean algebra has
  played a significant role in the important and complicated
  task of designing telephone switching circuits, automatic
  control devices, and electronic computers.  At the present
  time, more interest is centered in this application than
  in either of the others.
  \end{quote}
  Claude E. Shannon's classic 1937 thesis is described separately
  in several places.  From \cite{{bibref:w:boolealghist01}}:
  \begin{quote}
  Shannon, whose 1937 thesis centered on the improvement of the
  Differential Analyzer, a clunky mechanical gear and shaft addition
  machine, realized that Boolean algebraic principles governed its operation.
  He proposed that such a machine could be built with circuits using
  components that were governed by Boolean principles.  Shannon's paper
  was regarded as genius and his ideas were almost immediately
  incorporated into the telephone system.  Shannon took a position at Bell
  Labs.  Later, of course, Shannon's thesis came to be seen as a focal point
  in the development of modern computers.
  \end{quote}
  In \cite{bibref:w:boolealghist02}, Shannon's thesis is described
  very favorably:
  \begin{quote}
  Around the 1850's, the British mathematician George Boole was
  busily inventing a new form of mathematics, in which he represented
  logical expressions in a mathematical form now known as
  Boolean Algebra.
  Unfortunately, with the exception of students of philosophy
  and symbolic logic, Boolean Algebra was destined to remain
  largely unknown and unused for the better part of a century.
  It fact it was not until 1938 that Claude E. Shannon published
  an article based on his master's thesis at MIT.  (Shannon's
  thesis has since been described as: \emph{``Possibly the
  most important master's thesis of the twentieth century.''})
  In his paper, which was widely circulated, Shannon showed how
  Boole's concepts of TRUE and FALSE could be used to represent
  the functions of switches in electronic circuits.  It is difficult
  to convey just how important this concept was; suffice it to say
  that Shannon had provided electronics engineers with the mathematical
  tool they needed to design digital electronic circuits, and these
  techniques remain the cornerstone of digital electronic
  design to this day.
  Apropos of nothing at all, Shannon is also credited with the invention
  of the rocket-powered Frisbee, and is famous for riding down the
  corridors of Bell Laboratories on a unicycle while simultaneously
  juggling four balls.
  \end{quote}
  In summary, in 1854 George Boole published his classic work
  \emph{An investigation into the Laws of Thought, on
  Which are founded the Mathematical Theories of Logic and Probabilities},
  which laid the foundation of manipulation of
  logical ideas using algebraic mechanisms.  Boole's ideas
  were revived in 1937 and 1938 by Claude E. Shannon
  in his master's thesis and a subsequent article, in which
  Shannon applied Boole's ideas to the design of electric
  switching circuits.  Shannon's reapplication of Boole's work
  came to be seen as a focal point in the development of modern
  computers.
  \section[Simplification By Algebraic Manipulation]
          {Simplification Of Boolean Functions By Algebraic Manipulation}
  %Section Tag: SAM0
  \label{cbal0:ssam0}
  We assume that the reader has had previous exposure to
  \index{Boolean function!simplification of}simplification of
  Boolean functions.  For this reason, this section is a review (it is terse
  and moves quickly).  (For readers without this background, we
  recommend \cite{bibref:b:manodigitaldesignseconded}.)
  The most direct way to simplify Boolean functions is
  \index{Boolean function!algebraic simplification}\emph{algebraic}
  transformation---to use transformation postulates and
  theorems to transform algebraic
  expressions to a more desirable equivalent form.
  \subsection{Nomenclature And Operators}
  %Subsection Tag:  NOM0
  \label{cbal0:ssam0:snom0}
  We define the set of two elements which we will use in
  two-valued Boolean
  algebra as `0' and '1' (or alternatively as
  `FALSE' and `TRUE', respectively).
  All functions which we will describe subsequently require
  inputs which are members of this set and will produce outputs
  which are also members of this set.
  The \emph{complement} or \emph{negation} operator (or function)
  maps from 0$\rightarrow$1 and from 1$\rightarrow$0 (see Table
  \ref{tbl:cbal0:ssam0:snom0:01}).
  We denote this operator
  by an apostrophe
  following the variable to be complemented (example: $x'$).
  Alternatively, in some circumstances, we may use the
  tilde ($\sim{}x$), the overbar ($\overline{x}$), or
  the negation symbol ($\neg{}x$).
  \begin{table}
  \caption{Definition Of Logical Complement, Logical And, Logical Or, And Logical
           Exclusive Or Operators}
  \label{tbl:cbal0:ssam0:snom0:01}
  \begin{center}
  \begin{tabular}{|c|c||c|c|c|c|}
  \hline
  $X$ & $Y$  & $X'$ & $XY$ & $X+Y$ & $X \oplus{} Y$ \\
  \hline
  \hline
 & 0 & 1 & 0 & 0 & 0 \\
  \hline
 & 1 & 1 & 0 & 1 & 1 \\
  \hline
 & 0 & 0 & 0 & 1 & 1 \\
  \hline
 & 1 & 0 & 1 & 1 & 0 \\
  \hline
  \end{tabular}
  \end{center}
  \end{table}
  The \emph{logical AND} (or simply \index{AND}\index{Boolean algebra!AND}\emph{AND})
  operator (or function)
  returns TRUE if both of its input arguments are TRUE
  (see Table
  \ref{tbl:cbal0:ssam0:snom0:01}).
  We denote this operator
  by the \emph{times} symbol (example: $x \times{} y$), by
  the keyword `AND', or by placing the operands adjacent to
  each other (examples: $xy$, $x(y)$).
  The \emph{logical OR}
  (or simply \index{OR}\index{Boolean algebra!OR}\emph{OR})
  operator (or function)
  returns TRUE if either of its input arguments are TRUE
  (see Table
  \ref{tbl:cbal0:ssam0:snom0:01}).
  We denote this operator
  by the \emph{plus} symbol (example: $x + y$)  or by
  the keyword `OR'.
  The \emph{logical exclusive-OR}
  (or simply \index{XOR}\index{Boolean algebra!XOR} \emph{XOR})
  operator (or function)
  returns TRUE if either but not both of its input arguments are TRUE
  (see Table
  \ref{tbl:cbal0:ssam0:snom0:01}).
  We denote this operator
  by the \emph{circled plus} symbol (example: $x \oplus{} y$),
  by the \emph{caret} character (example: $x$\^{}$y$),  or by
  the keyword `XOR'.
  The exclusive-OR function is not a
  function traditionally considered in the canonical forms of Boolean
  algebra.  However, we consider it here because our aims may in
  some cases be subtly
  different than the aims of classic two-valued Boolean algebra.
  The goal of classic Boolean algebra is to minimize the number of
  terms which appear in a canonical form.
  However, often our goal here is to rearrange Boolean functions into a form
  which is optimal for implementation on a computer.  Since actual
  computers usually provide a bitwise exclusive-OR instruction, there
  are some applications where it may be useful to consider the
  underlying instruction set of the computer (for example,
  see \emph{Vertical Counters},
  Section \ref{cbal0:svct0}).
  In general, there are $2^{2^N}$ different Boolean functions of $N$
  input variables, so it isn't practical to name functions involving more
  than 2 input variables.  There are 16 ($=2^{2^2}$) Boolean functions of
 input variables, and these are enumerated in
  Table \ref{tbl:cbal0:ssam0:snom0:02}.
  \begin{table}
  \caption{Sixteen Possible Boolean Functions $f(A,B)$ Of Two Boolean Variables}
  \label{tbl:cbal0:ssam0:snom0:02}
  \begin{center}
  \begin{tabular}{|c||c|c|c|c||l|}
  \hline
  \small{Func.} & $\scriptstyle{f(1,1)}$ & $\scriptstyle{f(1,0)}$
                & $\scriptstyle{f(0,1)}$ & $\scriptstyle{f(0,0)}$
                            & Function Description \\
  \small{Num.}  &          &          &          &          &                 \\
  \hline
  \hline
 & 0 & 0 & 0 & 0 & \small{``Zero'' or  ``clear'' function.  Always}       \\
     &   &   &   &   & \small{returns zero regardless of $A$ and $B$  }       \\
     &   &   &   &   & \small{input values.                           }       \\
  \hline
 & 0 & 0 & 0 & 1 & \small{Logical NOR = $(A+B)'$.                 }       \\
  \hline
 & 0 & 0 & 1 & 0 & \small{Inhibition = $BA'$.  So named because   }       \\
     &   &   &   &   & \small{a TRUE value of $A$ inhibits $B$.  Also }       \\
     &   &   &   &   & \small{equivalent to $B>A$ or to $A<B$.        }       \\
  \hline
 & 0 & 0 & 1 & 1 & \small{NOT A = $A'$.  Ignores $B$ and returns  }       \\
     &   &   &   &   & \small{$A'$.                                   }       \\
  \hline
 & 0 & 1 & 0 & 0 & \small{Inhibition = $AB'$.  So named because   }       \\
     &   &   &   &   & \small{a TRUE value of $B$ inhibits $A$.  Also }       \\
     &   &   &   &   & \small{equivalent to $A>B$ or to $B<A$.        }       \\
  \hline
 & 0 & 1 & 0 & 1 & \small{NOT B = $B'$.  Ignores $A$ and returns  }       \\
     &   &   &   &   & \small{$B'$.                                   }       \\
  \hline
 & 0 & 1 & 1 & 0 & \small{Exclusive-OR (XOR) = $A \oplus B$.  Also}       \\
     &   &   &   &   & \small{equivalent to $A \neq B$.               }       \\
  \hline
 & 0 & 1 & 1 & 1 & \small{Logical NAND = $(AB)'$.                 }       \\
  \hline
 & 1 & 0 & 0 & 0 & \small{Logical AND = $AB$.                     }       \\
  \hline
 & 1 & 0 & 0 & 1 & \small{Equivalence:  true if $A=B$.  Also}       \\
     &   &   &   &   & \small{known as exclusive-NOR, i.e. $(A \oplus B)'$.}       \\
  \hline
 & 1 & 0 & 1 & 0 & \small{Copy $B$.  Ignores $A$ and returns $B$. }       \\
  \hline
 & 1 & 0 & 1 & 1 & \small{Implication:  $B \rightarrow A$ (if $B$ }       \\
     &   &   &   &   & \small{then $A$).  Also equivalent to $B \geq A$.}     \\
  \hline
 & 1 & 1 & 0 & 0 & \small{Copy $A$.  Ignores $B$ and returns $A$. }       \\
  \hline
 & 1 & 1 & 0 & 1 & \small{Implication:  $A \rightarrow B$ (if $A$ }       \\
     &   &   &   &   & \small{then $B$).  Also equivalent to $A \geq B$.}     \\
  \hline
 & 1 & 1 & 1 & 0 & \small{Logical OR = $A+B$.                     }       \\
  \hline
 & 1 & 1 & 1 & 1 & \small{``One'' or ``set'' function.  Always    }       \\
     &   &   &   &   & \small{returns one regardless of $A$ and $B$   }       \\
     &   &   &   &   & \small{input values.                           }       \\
  \hline
  \end{tabular}
  \end{center}
  \end{table}
  \emph{Any} Boolean function can be synthesized using AND gates and inverters
  (i.e. NOT gates), OR gates and inverters, NAND gates alone, or NOR
  gates alone.  However, not all Boolean functions can be synthesized
  using AND gates alone or OR gates alone.
  \subsection{Postulates And Theorems}
  %Subsection Tag:  POS0
  \label{cbal0:ssam0:spos0}
  Mathematicians tend to be very picky about what exactly a
  \emph{postulate} is versus what a \emph{theorem} is.  We are
  far less picky.  Either one (a postulate or a theorem) is a
  rule that can be used to transform a Boolean algebraic expression
  into another expression which is equivalent but for one reason or another
  more desirable.  For our purposes here, postulates and theorems
  are interchangeable.
  Table \ref{tbl:cbal0:ssam0:spos0:01}
  (from \cite{bibref:b:manodigitaldesignseconded})
  supplies the important postulates and theorems which are useful in
  algebraically simplifying Boolean functions.
  In Table \ref{tbl:cbal0:ssam0:spos0:01}, we should explain what
  is meant by the \emph{Dual Postulate Or Theorem}.  To
  quote \cite{bibref:b:manodigitaldesignseconded}, p. 41:
  \begin{quote}
  \ldots This important property of Boolean algebra is called
  the \index{Boolean algebra!duality principle}\index{duality principle}%
  \emph{duality principle}.
  It states that every algebraic expression deducible from the postulates
  of Boolean algebra remains valid if the operators and identity
  elements are interchanged.  In a two-valued Boolean algebra,
  the identity elements and the elements of the set $B$ are the
  same:  1 and 0.  The duality principle has many applications.
  If the \emph{dual} of an algebraic expression is desired, we
  simply interchange OR and AND operators and replaces 1s by
 s and 0s by 1s.
  \end{quote}
  \begin{table}
  \caption{Important Postulates And Theorems Of Two-Valued Boolean Algebra}
  \label{tbl:cbal0:ssam0:spos0:01}
  \begin{center}
  \begin{tabular}{|c||c|c||l|}
  \hline
  \small{Postulate} &  \small{Postulate}   & \small{Dual}        & \small{Remarks}   \\
  \small{Or}        &  \small{Or}          & \small{Postulate}   &                   \\
  \small{Theorem}   &  \small{Theorem}     & \small{Or}          &                   \\
  \small{Number}    &                      & \small{Theorem}     &                   \\
  \hline
           &  $x + 0 = x$         & $x \cdot 1 = 1$     &                   \\
  \hline
           &  $x + x' = 1$        & $x \cdot x' = 0$    &                   \\
  \hline
           &  $x + x = x$         & $x \cdot x = x$     &                   \\
  \hline
           &  $x + 1 = 1$         & $x \cdot 0 = 0$     &                   \\
  \hline
           &  $(x')' = x$         &                     & \small{Involution.} \\
  \hline
           &  $x + y = y + x$     & $x \cdot y = y \cdot x $ & \small{Commutative property.} \\
  \hline
           &  $x + (y + z)$       & $x(yz) = (xy)z$  & \small{Associative property.} \\
                    &  $= (x + y) + z$     &                     &                            \\
  \hline
           &  $x (y + z)$         & $x + yz$          & \small{Distributive property.} \\
                    &  $= xy + xz$                    & $= (x+y)(x+z)$      &                                \\
  \hline
           &  $(x+y)' = x'y'$      & $(xy)' = x' + y'$  & \small{DeMorgan's theorem.} \\
  \hline
           &  $x + xy = x$         & $x(x+y) = x$       & \small{Absorption.} \\
  \hline
  \end{tabular}
  \end{center}
  \end{table}
  Note also from Item 8 of
  Table \ref{tbl:cbal0:ssam0:spos0:01} that in Boolean algebra
  AND distributes over OR and OR distributes over AND (waiting on
  newsgroup posters to clarify).  This is unlike ``normal'' algebra, where
  in general,
  \begin{equation}
  x + yz \neq (x+y) (x+z).
  \end{equation}
  The \index{Boolean algebra!operator precedence}%
  \index{operator precedence!Boolean algebra}\index{operator precedence}%
  operator precedence for evaluating Boolean expressions assumed throughout
  this work is:
  \begin{quote}
  \begin{enumerate}
  \item Parenthesis.
  \item NOT.
  \item AND.
  \item OR.
  \end{enumerate}
  \end{quote}
  \noindent{}Note that this operator precedence very closely mirrors
  the standard precedence of normal algebraic expressions.
  \subsection{Canonical And Standard Forms}
  %Subsection Tag:  CAS0
  \label{cbal0:ssam0:scas0}
  \cite{bibref:b:manodigitaldesignseconded}, p. 49 provides an concise and
  excellent definition of \emph{minterms} and \emph{maxterms}.  The definition
  here is taken primarily from that source.
  A binary variable may appear either in its normal form ($x$, for example)
  or in its complemented form ($x'$, for example).  Now consider two
  binary variables $x$ and $y$ combined with an AND
  operation.  Since each variable may appear in either form, there are four
  possible combinations:  $x'y'$, $x'y$, $xy'$, and $xy$.  These
  four AND terms are mutually exclusive and mutually exhaustive---that is,
  no combination of values for
  $x$ and
  $y$ that causes one of these AND terms to be TRUE may cause any of the
  others to be TRUE, and every combination of $x$ and $y$ will cause exactly
  one of these AND terms to be TRUE.  Each of these
  four AND terms is called a \index{Boolean algebra!minterm}\index{minterm}\emph{minterm}
  or \index{Boolean algebra!standard product}\index{standard product}\emph{standard product}.
  In a similar manner, $n$ variables can be combined to form $2^n$ minterms.
  In a similar fashion, $n$ variables forming an OR term, with each variable
  being primed or unprimed, provide $2^n$ possible combinations, called
  \index{Boolean algebra!maxterm}\index{maxterm}\emph{maxterms}, or
  \index{Boolean algebra!standard sum}\index{standard sum}\emph{standard sums}.
  \begin{table}
  \caption{Minterms And Maxterms Of Three Boolean Variables}
  \label{tbl:cbal0:ssam0:scas0:01}
  \begin{center}
  \begin{tabular}{|c|c|c||c|c||c|c|}
  \hline
   $x$ & $y$ & $z$ & \small{Minterm} &  \small{Minterm}     & \small{Maxterm} & \small{Maxterm}     \\
       &     &     & \small{Term}    &  \small{Designation} & \small{Term}    & \small{Designation} \\
  \hline
  &  0  &  0  & $x'y'z'$        &  $m_0$               & $x+y+z$         & $M_0$               \\
  \hline
  &  0  &  1  & $x'y'z$         &  $m_1$               & $x+y+z'$        & $M_1$               \\
  \hline
  &  1  &  0  & $x'yz'$         &  $m_2$               & $x+y'+z$        & $M_2$               \\
  \hline
  &  1  &  1  & $x'yz$          &  $m_3$               & $x+y'+z'$       & $M_3$               \\
  \hline
  &  0  &  0  & $xy'z'$         &  $m_4$               & $x'+y+z$        & $M_4$               \\
  \hline
  &  0  &  1  & $x'y'z$         &  $m_5$               & $x+y+z'$        & $M_5$               \\
  \hline
  &  1  &  0  & $xyz'$          &  $m_6$               & $x'+y'+z$       & $M_6$               \\
  \hline
  &  1  &  1  & $xyz$           &  $m_7$               & $x'+y'+z'$      & $M_7$               \\
  \hline
  \end{tabular}
  \end{center}
  \end{table}
  The two primary canonical forms in Boolean algebra are the
  \emph{sum of minterms} (or \emph{sum of products}) form and the
  \emph{product of maxterms} (or \emph{product of sums}) form.
  The sum of minterms canonical form (which is the most common
  canonical form) is sometimes written using a shorthand
  notation involving the Greek letter sigma ($\Sigma$).  We describe this
  shorthand form now.  Consider the Boolean function of 3 variables,
  \begin{equation}
  \label{eq:cbal0:ssam0:scas0:01}
  F(A, B, C) = A + B'C.
  \end{equation}
  \noindent{}Using the postulates and theorems in Table
  \ref{tbl:cbal0:ssam0:spos0:01}, it is possible
  to expand (\ref{eq:cbal0:ssam0:scas0:01}) into
  a sum of minterms form:
  \begin{eqnarray}
  \label{eq:cbal0:ssam0:scas0:02}
  F(A, B, C) & = & A'B'C + AB'C' + AB'C + ABC' + ABC \\
             & = & m_1 m_4 m_5 m_6 m_7.\nonumber
  \end{eqnarray}
  \noindent{}(\ref{eq:cbal0:ssam0:scas0:02}) is also commonly written
  in the shorthand form:
  \begin{equation}
  \label{eq:cbal0:ssam0:scas0:03}
  F(A, B, C) = \Sigma{}(1, 4, 5, 6, 7).
  \end{equation}
  \noindent{}In the right-hand side of
  (\ref{eq:cbal0:ssam0:scas0:03}), each integer
  (1, 4, 5, 6, or 7) corresponds to the integer
  that would be formed by treating the corresponding
  minterm in (\ref{eq:cbal0:ssam0:scas0:02}) as
  a binary number, i.e. $A=2^2$, $B=2^1$, and
  $C=2^0$.  This is the basis of the short hand
  notation.
  A second but much less commonly used canonical form
  is the product of maxterms (or product of sums) form,
  which uses the Greek letter pi ($\Pi$) for its shorthand
  form.  Without further explanation, we present the
  product of maxterms form of $\Sigma{}(1,4,5,6,7)$
  (Eqns. \ref{eq:cbal0:ssam0:scas0:01} through
  \ref{eq:cbal0:ssam0:scas0:03}) as
  (\ref{eq:cbal0:ssam0:scas0:04})
  through (\ref{eq:cbal0:ssam0:scas0:07})
  (Figure \ref{fig:cbal0:ssam0:scas0:01}).
  \begin{figure}
  \begin{eqnarray}
  \label{eq:cbal0:ssam0:scas0:04}
  F(A, B, C) & = & \Sigma{}(1, 4, 5, 6, 7) \\
  \label{eq:cbal0:ssam0:scas0:05}
             & = & \Pi{}(0, 2, 3)          \\
  \label{eq:cbal0:ssam0:scas0:06}
                     & = & M_0 M_2 M_3             \\
  \label{eq:cbal0:ssam0:scas0:07}
                     & = & (x+y+z)(x+y'+z)(x+y'+z')
  \end{eqnarray}
  \caption{Product Of Maxterms Form Of $\Sigma{}(1,4,5,6,7)$}
  \label{fig:cbal0:ssam0:scas0:01}
  \end{figure}
  Because there are so many excellent digital logic books on the market
  that contain examples and exercises of algebraic simplification
  (we recommend \cite{bibref:b:manodigitaldesignseconded}), we don't
  dwell on algebraic simplification or provide examples.  Again, we
  assume that nearly all of our readers have had a course in digital
  logic or symbolic logic.
  \section[Karnaugh Maps]
          {Simplification Of Boolean Functions Using Karnaugh Maps}
  %Section tag:  SKM0
  \label{cbal0:skm0}
  In 1953, M. Karnaugh published the graphical map method of simplifying
  combinational logic functions (\cite{bibref:p:kmapclassic01}).  This
  method has come to be known as the \emph{Karnaugh map} or \emph{K-map}
  method of reduction, and is taught to engineers in nearly every
  digital logic class.
  Although it is possible, starting from an arbitrary Boolean formula, to simplify
  the formula through algebraic manipulation, algebraic simplification
  has the disadvantage that formulas can have many forms and there is not
  an easily remembered, precise, and repeatable procedure for algebraic simplification.
  The Karnaugh map method has the advantage that each Boolean function
  has only one graphical representation, and that the procedure for simplification
  is simple and easily remembered.
  In a Karnaugh map, each square corresponds to a possible minterm of the function.
  The essence of the method is to populate a grid of squares with outputs of
  the function to be simplified.  Each minterm that must exist in the
  function (i.e. each combination of inputs for which the function
  must return TRUE) receives a `1' in the corresponding square.  Each
  combination of inputs for which the function must return FALSE
  receives a `0' in the corresponding square.  Each combination of inputs
  for which the function may return either TRUE or FALSE receives an
  `X' in the corresponding square.
  After the Karnaugh map squares are populated with 1's, 0's, and X's
  corresponding to the required values of the function for each combination
  of inputs, the 1's are graphically combined into the largest rectangle possible.
  Each rectangle may include 1's, may include X's where convenient, but
  may not include 0's.
  Each of these squares is then translated into a product of uncomplemented and
  complemented input variables, and these products are summed to
  produce the simplified algebraic expression for the function.  (We don't
  belabor this process, because we assume that most of our readers
  understand it very thoroughly.)  There are some subtle points
  to the process, such as combining corners and the ``folding'' of the
 - and 6-variable maps, but we don't explain these subtle points here
  because they are so thoroughly explained in so many books.
  Figures \ref{fig:cbal0:skm0:00} through \ref{fig:cbal0:skm0:04}
  supply the canonical forms of two-, three-, four-, five-, and
  six-variable Karnaugh maps.
  \begin{figure}
  \centering
  \includegraphics[width=1.25in]{c_bal0/kmap02cf.eps}
  \caption{Canonical Form Of Two-Variable Karnaugh Map}
  \label{fig:cbal0:skm0:00}
  \end{figure}
  \begin{figure}
  \centering
  \includegraphics[height=1.25in]{c_bal0/kmap03cf.eps}
  \caption{Canonical Form Of Three-Variable Karnaugh Map}
  \label{fig:cbal0:skm0:01}
  \end{figure}
  \begin{figure}
  \centering
  \includegraphics[height=2.0in]{c_bal0/kmap04cf.eps}
  \caption{Canonical Form Of Four-Variable Karnaugh Map}
  \label{fig:cbal0:skm0:02}
  \end{figure}
  \begin{figure}
  \centering
  \includegraphics[width=4.25in]{c_bal0/kmap05cf.eps}
  \caption{Canonical Form Of Five-Variable Karnaugh Map}
  \label{fig:cbal0:skm0:03}
  \end{figure}
  \begin{figure}
  \centering
  \includegraphics[width=4.5in]{c_bal0/kmap06cf.eps}
  \caption{Canonical Form Of Six-Variable Karnaugh Map}
  \label{fig:cbal0:skm0:04}
  \end{figure}
  \section[Simplification Using The Scheinman Method]
          {Simplification Of Boolean Functions Using The Scheinman Method}
  %Section Tag: SCM0
  \label{cbal0:sscm0}
  Two major disadvantages of the Karnaugh map method of simplifying Boolean
  functions are that:
  \begin{itemize}
  \item It is generally not possible to apply the method to functions
        of more than six variables.
  \item It is not easy to automate the method (in the form that it is stated)
        because it is inherently graphical.
  \end{itemize}
  In 1962, A. H. Scheinman published a method for the simplification
  of Boolean functions (\cite{bibref:p:scheinmanclassic01}) which is more amenable
  to automation than the Karnaugh map method.
  \section[The Quine-McCluskey Method]
          {Simplification Of Boolean Functions Using The Quine-McCluskey Method}
  \section{Multiple Functions Of $N$ Boolean Variables}
  Need to get back to Dr. Singh to inquire about the multiple Scheinman method.
  \section{Vertical Counters}
  %Section Tag: VCT0.
  \label{cbal0:svct0}
  \index{vertical counter}As has been hinted at elsewhere
  in this work, the need to generate
  firmware which minimizes ROM consumption leads to clever (but perhaps
  less-than-intuitive) programming techniques.  One such technique
  is the construction of \emph{vertical counters}.
  A \index{vertical counter}vertical counter
  is a set of identical combinational mappings or state machines
  where the inputs, state vector, intermediate results, and outputs of each
  combinational mapping or state machine are stored as a single bit
  in the same position
  in each of multiple bytes or words.  When inputs, state vectors,
  intermediate results, and outputs are stored
  in this way, the bitwise logical instructions of the machine
  (AND, OR, NOT, XOR) can be used to process several state machines in
  parallel.  Vertical counters are intimately related to the reduction
  of Boolean functions because such reduction must be performed in order
  to design the vertical counter.  Debouncing and filtering, where the
  inputs and outputs naturally tend to be arranged as groups of bits,
  are the most common application of vertical counters.
  A very helpful resource on the web is the set of web pages
  maintained by \index{Dattalo, Scott}Scott Dattalo
  \cite{bibref:i:scottdattalo} for the
  PIC microcontroller, including
  especially \cite{bibref:w:sdattalovc02}.  Many of the vertical counter
  designs which follow come from Mr. Dattalo's pages.
  We abuse the term \emph{counter} somewhat, and we refer to
  any bit-wise mapping useful in microcontroller work as
  a vertical counter.  We categorize vertical counters as
  \index{vertical counter!combinational}\emph{combinational}
  (not truly a counter---the output is a function of the
  inputs only), \index{vertical counter!sequential}\emph{sequential}
  (the next state and output may be functions of both the
  inputs and the present state---i.e. a proper state machine),
  \index{vertical counter!cyclic}\emph{cyclic} (the counter
  goes through a series of states and then repeats), or
  \index{vertical counter!terminating} (the counter
  will reach a terminal state).
  \subsection{2-Bit 4-State Cyclic Vertical Counter}
  %Subsection Tag: TBF0
  \label{cbal0:svct0:stbf0}
  In this discussion of vertical counters, we begin with the simplest
  designs, as often the simpler designs appear as part of more complex
  designs.
  Table \ref{tbl:cbal0:svct0:stbf0:01} supplies the state transition table
  for a 2-bit 4-state
  cyclic vertical counter.  Note that the counter advances through the
  bit patterns in the ``proper'' binary integer order.
  \begin{table}
  \caption{State Transition Table Of 2-Bit 4-State Cyclic Vertical Counter}
  \label{tbl:cbal0:svct0:stbf0:01}
  \begin{center}
  \begin{tabular}{|c|c|c|c|}
  \hline
   $A_k$     & $B_k$     & $A_{k+1}$ & $B_{k+1}$ \\
  \hline
  \hline
         & 0         & 0         & 1         \\
  \hline
         & 1         & 1         & 0         \\
  \hline
         & 0         & 1         & 1         \\
  \hline
         & 1         & 0         & 0         \\
  \hline
  \end{tabular}
  \end{center}
  \end{table}
  From Table \ref{tbl:cbal0:svct0:stbf0:01} it can be readily verified
  even without a Karnaugh map that the least significant bit
  ($B$) is always complemented from one state to the next, so that
  $B_{k+1} = \neg B_k$.  It can also be seen that the most significant
  bit ($A$) is complemented from one state to the next only if $B$=1,
  so that $A_{k+1} = A_k \oplus B_k$.
  The implementation of such a counter in `C' comes immediately, since
  `C' directly supports bit-wise complementation and exclusive-OR of
  integers:
  \begin{verbatim}
           A = A ^ B;
           B = ~B;
  \end{verbatim}
  Note in the `C' snippet above, the two operations are ordered so as
  not to interfere with each other.  Note that reversing the two steps above
  would not yield the desired result.
  \subsection{3-Bit 8-State Cyclic Vertical Counter}
  %Subsection Tag: TBF4
  \label{cbal0:svct0:stbf4}
  \subsection[$N$-Bit $2^N$-State Cyclic Vertical Counter]
             {\mbox{\boldmath $N$}-Bit \mbox{\boldmath $2^N$}-State Cyclic Vertical Counter}
  %Subsection Tag: TBF1
  \label{cbal0:svct0:stbf1}
  The design of the 2-bit 4-state vertical counter presented in
  Section \ref{cbal0:svct0:stbf0} (immediately above) and be
  generalized to an $N$-bit $2^N$-state counter which follows
  the traditional binary integer counting sequence.
  Note from Section \ref{cbal0:svct0:stbf0} that the least
  significant bit of the counter is always complemented
  in going from one state to the next, and that each more
  significant bit is complemented only if all less significant
  bits are 1.  If $X_0$ is the least significant bit of the
  counter and $X_N$ the most significant bit,
  (\ref{eq:cbal0:svct0:stbf1:01}) through (\ref{eq:cbal0:svct0:stbf1:05})
  (Figure \ref{eq:cbal0:svct0:stbf1:01})
  describe how the counter is advanced from one state to the next.
  Note that this set of equations gives only a \emph{logical} description
  of how to obtain the next state from the present state---these
  equations cannot be used as a direct blueprint for implementation because
  earlier steps would destroy the results needed for later steps.
  \begin{figure}
  \begin{eqnarray}
  \label{eq:cbal0:svct0:stbf1:01}
    X_0(k+1) & = & \neg X_0(k)                             \\
  \label{eq:cbal0:svct0:stbf1:02}
    X_1(k+1) & = & X_1(k) \oplus X_0(k)                    \\
  \label{eq:cbal0:svct0:stbf1:03}
    X_2(k+1) & = & X_2(k) \oplus (X_1(k) X_0(k))           \\
  \label{eq:cbal0:svct0:stbf1:04}
    X_3(k+1) & = & X_3(k) \oplus (X_2(k) X_1(k) X_0(k))    \\
             & \ldots & \nonumber                          \\
  \label{eq:cbal0:svct0:stbf1:05}
    X_N(k+1) & = & X_N(k) \oplus (X_{N-1}(k) \ldots X_0(k))
  \end{eqnarray}
  \caption{State Transition Equations Of $N$-Bit $2^N$-State Cyclic Vertical Counter}
  \label{fig:cbal0:svct0:stbf1:01}
  \end{figure}
  The form of
  (\ref{eq:cbal0:svct0:stbf1:01}) through (\ref{eq:cbal0:svct0:stbf1:05})
  suggests a way to economically implement an $N$-bit $2^N$-state
  cyclic vertical counter in software, using two temporary
  variables $TEMP_A$ and $TEMP_B$.  The general blueprint for
  implementation is supplied as
  (\ref{eq:cbal0:svct0:stbf1:06}) through (\ref{eq:cbal0:svct0:stbf1:20})
  (Figure \ref{eq:cbal0:svct0:stbf1:02}).
  \begin{figure}
  \begin{eqnarray}
  \label{eq:cbal0:svct0:stbf1:06}
    TEMP_A   & = & X_0                                     \\
  \label{eq:cbal0:svct0:stbf1:07}
    X_0      & = & \neg X_0                                \\
  \label{eq:cbal0:svct0:stbf1:08}
    TEMP_B   & = & X_1 TEMP_A                              \\
  \label{eq:cbal0:svct0:stbf1:09}
    X_1      & = & X_1 \oplus TEMP_A                       \\
  \label{eq:cbal0:svct0:stbf1:10}
    TEMP_A   & = & TEMP_B                                  \\
  \label{eq:cbal0:svct0:stbf1:11}
    TEMP_B   & = & X_2 TEMP_B                              \\
  \label{eq:cbal0:svct0:stbf1:12}
    X_2      & = & X_2 \oplus TEMP_A                       \\
  \label{eq:cbal0:svct0:stbf1:13}
    TEMP_A   & = & TEMP_B                                  \\
  \label{eq:cbal0:svct0:stbf1:14}
    TEMP_B   & = & X_3 TEMP_B                              \\
  \label{eq:cbal0:svct0:stbf1:15}
    X_3      & = & X_3 \oplus TEMP_A                       \\
             & \ldots & \nonumber                          \\
  \label{eq:cbal0:svct0:stbf1:16}
    X_{N-2}  & = & X_{N-2} \oplus TEMP_A                   \\
  \label{eq:cbal0:svct0:stbf1:17}
    TEMP_A   & = & TEMP_B                                  \\
  \label{eq:cbal0:svct0:stbf1:18}
    TEMP_B   & = & X_{N-1} TEMP_B                          \\
  \label{eq:cbal0:svct0:stbf1:19}
    X_{N-1}  & = & X_{N-1} \oplus TEMP_A                   \\
  \label{eq:cbal0:svct0:stbf1:20}
    X_N      & = & X_N \oplus X_N TEMP_B
  \end{eqnarray}
  \caption{Implementation Blueprint Of $N$-Bit $2^N$-State Cyclic Vertical Counter}
  \label{fig:cbal0:svct0:stbf1:02}
  \end{figure}
  Figure \ref{fig:cbal0:svct0:stbf1:01}
  supplies a concrete example of a C-language
  implementation of a 5-bit 32-state cyclic vertical counter.
  Note that the counter will follow the traditional
  binary integer counting sequence.  Note also that
  the blueprint provided by Eqns.
  (\ref{eq:cbal0:svct0:stbf1:06}) through (\ref{eq:cbal0:svct0:stbf1:20})
  and Figure \ref{fig:cbal0:svct0:stbf1:01} can
  be extended to a counter of any size.
  \begin{figure}
  \begin{verbatim}
  /**************************************************************/
  /* Assume:                                                    */
  /*    x4     : Byte containing most significant bits of the   */
  /*             a group of 8 bits.                             */
  /*    x3,                                                     */
  /*    x2,                                                     */
  /*    x1     : Bytes containing the intermediate bits.        */
  /*    x0     : Byte containing the least significant bits.    */
  /*    temp_a,                                                 */
  /*    temp_b : Temporary variables, used to accumulate the    */
  /*             result of AND'ing old counter bit values.      */
  /**************************************************************/
  temp_a =  x0;
  x0     = ~x0;
  temp_b =  x1 & temp_a;
  x1     =  x1 ^ temp_a;
  temp_a =  temp_b;
  temp_b =  x2 & temp_b;
  x2     =  x2 ^ temp_a;
  temp_a =  temp_b;
  temp_b =  x3 & temp_b;
  x3     =  x3 ^ temp_a;
  x4     =  x4 ^ temp_b;
  /* End of code. */
  \end{verbatim}
  \caption{C-Language Implementation Of 5-Bit 32-State Cyclic Vertical Counter}
  \label{fig:cbal0:svct0:stbf1:01b}
  \end{figure}
  \subsection{3-Bit 5-State Cyclic Vertical Counter}
  %Subsection Tag: TBF5
  \label{cbal0:svct0:stbf5}
  \subsection{3-Bit 6-State Cyclic Vertical Counter}
  %Subsection Tag: TBF6
  \label{cbal0:svct0:stbf6}
  \subsection{3-Bit 7-State Cyclic Vertical Counter}
  %Subsection Tag: TBF7
  \label{cbal0:svct0:stbf7}
  \subsection{2-Bit 4-State Terminating Vertical Counter}
  %Subsection Tag: TBF8
  \label{cbal0:svct0:stbf8}
  \subsection{3-Bit 5-State Terminating Vertical Counter}
  %Subsection Tag: TBF9
  \label{cbal0:svct0:stbf9}
  \subsection{3-Bit 6-State Terminating Vertical Counter}
  %Subsection Tag: TBG0
  \label{cbal0:svct0:stbg0}
  \subsection{3-Bit 7-State Terminating Vertical Counter}
  %Subsection Tag: TBG1
  \label{cbal0:svct0:stbg1}
  \subsection{2/3 Debouncing Vertical Counter}
  %Subsection Tag: TTD0.
  \label{cbal0:svct0:sttd0}
  \index{debouncing}\index{debouncing!2/3}\emph{2/3 debouncing}
  is debouncing where at least two of the most recent
  three samples must be at the same value (either 0 or 1) to cause the output
  to be that same value.
  Note that \emph{2/3 debouncing} as we describe it here represents a
  purely combinational mapping from the 3 most recent samples to
  the debounced output.  When 3 samples are available, 0 of the
  samples or 1 of the samples with value 1 map to a debounced
  output value of 0; while 2 of the samples or 3 of the samples
  with value 1 map to a debounced output value of 1.
  If $A$ is the most recent sample, $B$ is the next-most-recent sample, and
  $C$ is the oldest sample, Fig. \ref{fig:cbal0:svct0:sttd0:01}
  supplies the Karnaugh map for 2/3
  debouncing.
  \begin{figure}
  \centering
  \includegraphics[height=1.25in]{c_bal0/kmap23db.eps}
  \caption{Karnaugh Map Of 2/3 Debouncing}
  \label{fig:cbal0:svct0:sttd0:01}
  \end{figure}
  It can be seen from the figure that the expression for the output is
  \begin{equation}
  \label{eq:cbal0:svct0:sttd0:01}
  AB + AC + BC = A (B+C) + BC .
  \end{equation}
  Intuitively, (\ref{eq:cbal0:svct0:sttd0:01}) makes sense---the output
  will be 1 if any two of the most recent samples are 1
  ($AB + AC + BC$).  Similarly, the output will be 0 if any two of
  the most recent samples are 0.
  Figure \ref{fig:cbal0:svct0:sttd0:02} supplies the C-language
  code to implement 2/3 debouncing as a vertical mapping.
  A C-compiler will typically implement this code very directly
  using the bitwise logical instructions of the machine.
  \begin{figure}
  \begin{verbatim}
  /**************************************************************/
  /* Assume:                                                    */
  /*    A      : Most recent sample (i.e. at t(0)), arranged as */
  /*             a group of 8 bits.                             */
  /*    B      : Next most recent sample t(-1).                 */
  /*    C      : Oldest sample t(-2).                           */
  /*    output : Debounced collection of 8 bits presented to    */
  /*             software internals.                            */
  /**************************************************************/
  output = (A & (B | C)) | (B & C);
  /* End of code. */
  \end{verbatim}
  \caption{C-Language Implementation Of 2/3 Debouncing}
  \label{fig:cbal0:svct0:sttd0:02}
  \end{figure}
  \subsection{3/3 Debouncing Vertical Counter}
  %Subsection Tag: TTD1.
  \label{cbal0:svct0:sttd1}
  \index{debouncing}\index{debouncing!3/3}\emph{3/3 debouncing}
  is debouncing where all three of the most recent
  three samples must be at a value (either 0 or 1) to cause the
  debounced output to transition to that same value.
  Note that 3/3 debouncing as we present it is a sequential (rather than
  a purely combinational) mapping from the 3 most recent samples to the
  debounced output.  In addition to the 3 inputs, the behavior of the
  mapping depends on a single bit of state which is held.  (In the
  implementation presented in this section, the state and the debounced
  output are the same bit.)  For example, if 2 of the 3 most recent
  input samples are 1, the debounced output value may be either 0
  or 1.  The transition of the debounced output value from
 to 1 or from 1 to 0 can only occur if all 3 most recent samples
  are 1 or are 0, respectively.
  If $A$ is the most recent sample, $B$ is the next-most-recent sample,
  $C$ is the oldest sample, and $O$ is the output (assumed maintained
  as a RAM location) Fig. \ref{fig:cbal0:svct0:sttd1:01}
  supplies the Karnaugh map for 3/3
  debouncing.
  \begin{figure}
  \centering
  \includegraphics[height=2.0in]{c_bal0/kmap33db.eps}
  \caption{Karnaugh Map Of 3/3 Debouncing}
  \label{fig:cbal0:svct0:sttd1:01}
  \end{figure}
  It can be seen from the figure that the expression for the output is
  \begin{equation}
  \label{eq:cbal0:svct0:sttd1:01}
  ABC + AO + BO + CO = ABC + O(A + B + C).
  \end{equation}
  Intuitively, (\ref{eq:cbal0:svct0:sttd1:01}) makes sense---the output
  will be unconditionally 1 if all three of the most recent samples are 1
  ($ABC$).  The output will also be 1 if the previous output was 1
  and at least one of the most recent samples are 1 [$O(A+B+C)$]---at least
  one true recent sample blocks the output from transition to 0.
  Figure \ref{fig:cbal0:svct0:sttd1:02} supplies the C-language
  code to implement 3/3 debouncing as a vertical mapping.
  A C-compiler will typically implement this code very directly
  using the bitwise logical instructions of the machine.
  \begin{figure}
  \begin{verbatim}
  /**************************************************************/
  /* Assume:                                                    */
  /*    A      : Most recent sample (i.e. at t(0)), arranged as */
  /*             a group of 8 bits.                             */
  /*    B      : Next most recent sample t(-1).                 */
  /*    C      : Oldest sample t(-2).                           */
  /*    output : Debounced collection of 8 bits presented to    */
  /*             software internals.  Note that this is both    */
  /*             an input (to the combinational mapping) and    */
  /*             the new result.                                */
  /**************************************************************/
  output = (A & B & C) | (output & (A | B | C));
  /* End of code. */
  \end{verbatim}
  \caption{C-Language Implementation Of 3/3 Debouncing}
  \label{fig:cbal0:svct0:sttd1:02}
  \end{figure}
  \subsection{N/N Debouncing Vertical Counter}
  %Subsection Tag: NNC0.
  \label{cbal0:svct0:snnc0}
  \index{debouncing}\index{debouncing!N/N}It is clear from
  the design of the 3/3 debouncing
  vertical counter (Section \ref{cbal0:svct0:sttd1}, immediately
  above) that the design of the 3/3 debouncing vertical counter
  can be generalized to cover any number of recent samples.
  We call such a debouncing vertical counter an N/N debouncing
  vertical counter.  In order for the output of such a counter to
  turn 1, all $N$ most recent samples must be 1.  Similarly, in order
  for such a counter to turn 0, all $N$ most recent samples must be 0.
  We rely on a logical argument to design such a N/N debouncing
  vertical counter, rather than on Karnaugh maps.  If $I_1 \ldots I_N$
  are the $N$ most recent input samples and $O$ is the most recent
  output (assumed stored in RAM), it is clear from the form of
  (\ref{eq:cbal0:svct0:sttd1:01}) that the formula for the new output
  as a function of the inputs $I_1 \ldots I_N$ and the
  most recent output $O_{k-1}$ must be:
  \begin{equation}
  \label{eq:cbal0:svct0:snnc0:01}
  O_k = I_1 I_2 \ldots I_N + (O_{k-1} (I_1 + I_2 + \ldots + I_N)) .
  \end{equation}
  The form of (\ref{eq:cbal0:svct0:snnc0:01}) is intuitively
  plausible.  If the previous output $O_{k-1}$ is 0, the only
  circumstance under which the next output $O_k$ will become 1
  is if all $N$ inputs $I_1, I_2, \ldots , I_N$ are 1.
  Similarly, if the previous output $O_{k-1}$ is 1, the only
  circumstance under which $O_k$ will become 0
  is if all $N$ inputs $I_1, I_2, \ldots , I_N$ are 0.  This
  is the desired behavior.
  For an N/N counter when a large number of previous samples
  are required to be at the same value (say, $N=10$, for example),
  it may seem that the efficiency of the N/N vertical counter
  design presented here will break down.  However, it must be
  remembered that the vertical counter approach manipulates
  a large number (usually 8 or 16) inputs at a time.  It can be
  shown easily that an N/N debouncing vertical counter requires
  $2N$ operations to determine the next output.  Thus, for a
 /10 debouncing vertical counter, the necessary software
  may execute in as little as 20 machine instructions.  It would
  be difficult to find another method which will perform 10/10
  debouncing for 8 or 16 inputs in only 20 machine instructions, thus
  we maintain that the N/N debouncing vertical counter
  approach presented is quite efficient even for larger
  $N$.
  \section{Authors And Acknowledgements}
  %Section tag:  ACK0
  This chapter was primarily written by David T. Ashley
  \cite{bibref:i:daveashley}.
  We are very grateful to \index{Dattalo, Scott}Scott Dattalo
  \cite{bibref:i:scottdattalo},
  whose web pages about vertical counters provided much of the
  material for the Section \ref{cbal0:svct0}.
  Special thanks to \index{Virgil}Virgil \cite{bibref:i:virgil},
  \index{Dresner, Norm}Norm Dresner \cite{bibref:i:normdresner},
  and \index{Kaskelma, Heikki}Heikki Kaskelma \cite{bibref:i:heikkikaskelma}
  for mathematical assistance provided via the
  \index{sci.math newsgroup@\texttt{sci.math} newsgroup}%
  \texttt{sci.math} \cite{bibref:n:scimathnewsgroup} newsgroup.
  \section{Exercises}
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \noindent\begin{figure}[!b]
  \noindent\rule[-0.25in]{\textwidth}{1pt}
  \begin{tiny}
  \begin{verbatim}
  $RCSfile: c_bal0.tex,v $
  $Source: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_bal0/c_bal0.tex,v $
  $Revision: 1.10 $
  $Author: dtashley $
  $Date: 2003/11/03 02:14:24 $
  \end{verbatim}
  \end{tiny}
  \noindent\rule[0.25in]{\textwidth}{1pt}
  \end{figure}
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  % $Log: c_bal0.tex,v $
  % Revision 1.10  2003/11/03 02:14:24  dtashley
  % All duplicate labels as flagged by LaTeX removed.  Additional files added
  % to Microsoft Visual Studio edit context.
  %
  % Revision 1.9  2001/07/11 18:42:04  dtashley
  % Safety check-in.  Beginning work now on using GNU GMP in the tool set
  % and must cease work on book temporarily.
  %
  % Revision 1.8  2001/07/09 22:44:36  dtashley
  % All figures changed to use the Courier font.  Full checkin of this
  % subdirectory after this change.  Reason for font change was font
  % substitution warning messages both during print from 4AllTeX and from Acrobat
  % Distiller.
  %
  % Revision 1.7  2001/07/09 02:22:55  dtashley
  % Edits.  Safety check-in after changes and addition of figures.
  %
  % Revision 1.6  2001/07/07 03:19:52  dtashley
  % Test commit to be sure the CVS add worked correctly in adding files.
  %
  % Revision 1.5  2001/07/06 23:46:53  dtashley
  % Edits.  Addition of K-map diagrams to Boolean function chapter.
  %
  % Revision 1.4  2001/07/01 21:10:59  dtashley
  % Safety check-in after major re-org.
  %
  % Revision 1.3  2001/06/30 23:32:07  dtashley
  % End-of-month safety check-in.
  %
  % Revision 1.2  2001/06/30 16:32:10  dtashley
  % Moved out of binary mode for use of CVS.
  %
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  % $History: c_bal0.tex $
  %
  % *****************  Version 3  *****************
  % User: Dashley1     Date: 12/22/00   Time: 12:53a
  % Updated in $/uC Software Multi-Volume Book (A)/Chapter, BAL0, Bolean Algebra
  % Tcl build is up and running.  Result is near-perfect.
  %
  % *****************  Version 2  *****************
  % User: David T. Ashley Date: 7/09/00    Time: 11:15p
  % Updated in $/uC Software Multi-Volume Book (A)/Chapter, BAL0, Bolean Algebra
  % Addition of new chapters, enhancements to preface.
  %
  % *****************  Version 1  *****************
  % User: David T. Ashley Date: 7/09/00    Time: 9:28p
  % Created in $/uC Software Multi-Volume Book (A)/Chapter, BAL0, Bolean Algebra
  % Initial check-in.
  %End of file C_BAL0.TEX

 Legend:



Removed from v.3
 


changed lines


 
Added in v.140
 Legend:



Removed from v.3
 


changed lines


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

dashley@gmail.com	ViewVC Help
Powered by ViewVC 1.1.25