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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 275 - (hide annotations) (download) (as text)
Mon Aug 12 00:47:10 2019 UTC (4 years, 7 months ago) by dashley
File MIME type: application/x-tex
File size: 51086 byte(s)
Change keyword substitution (migration from cvs to svn).
1 dashley 140 %$Header$
2    
3     \chapter[\cbalzeroshorttitle{}]{\cbalzerolongtitle{}}
4    
5     \label{cbal0}
6    
7     \section{Introduction, Definition, And History Of Boolean Algebra}
8     %Section tag: INT0
9     \label{cbal0:sint0}
10    
11     \index{Boolean algebra}
12     In this chapter, we review methods of
13     simplifying \index{Boolean function}Boolean functions, and
14     show how such methods can be used to simplify software constructs
15     or to construct software which is more compact (in ROM or RAM)
16     or executes more quicky.
17    
18     Boolean algebra is named after \index{Boole, George}George Boole,
19     a 19th-century British mathematician.
20     A fairly concise biography of George Boole comes from
21     \cite{bibref:w:georgeboolebio01}:
22    
23     \begin{quote}
24     George Boole first attended a school in Lincoln, then a commerical school.
25     His early instruction in mathematics, however, was from his father who
26     also gave George a liking for constructing optical instruments. George's
27     interests turned to languages and he received instruction in Latin from a
28     local bookseller.
29    
30     By the age of 12 George had become so skilled in Latin that it provoked
31     an argument. He translated an ode by the Latin poet Horace which his
32     father was so proud of that he had it published. However the talent was
33     such that a local schoolmaster disputed that any 12 year old could
34     have written with such depth.
35    
36     Boole did not study for an academic degree, but from the age of 16 he was an
37     assistant school teacher. He maintained his interest in languages
38     and intended to enter the Church. From 1835, however, he seems to have
39     changed his mind for he opened his own school and began to study mathematics
40     on his own. He was later to realize that he had almost wasted five years
41     in trying to teach himself the subject instead of having a skilled teacher.
42    
43     At this time Boole studied the works of Laplace and Lagrange, making
44     notes which would later be the basis for his first mathematics paper.
45     However he did receive encouragement from Duncan Gregory who at this
46     time was in Cambridge and the editor of the recently founded
47     \emph{Cambridge Mathematical Journal}.
48    
49     Boole was unable to take Duncan Gregory's advice and study courses at
50     Cambridge as he required the income from his school to look after
51     his parents. However he began publishing in the \emph{Cambridge
52     Mathematical Journal} and his interests were also influenced by Duncan Gregory
53     as he began to study algebra. An application of algebraic methods
54     to the solution of differential equations was published by Boole in the
55     \emph{Transactions of the Royal Society} and for this work he received
56     the Society's Royal Medal. His mathematical work was beginning to bring
57     him fame.
58    
59     Boole was appointed to the chair of mathematics at Queens College,
60     Cork in 1849. He taught there for the rest of his life, gaining a reputation
61     as an outstanding and dedicated teacher.
62    
63     In 1854 he published \emph{An investigation into the Laws of Thought, on
64     Which are founded the Mathematical Theories of Logic and Probabilities}.
65     Boole approached logic in a new way reducing it to a simple algebra,
66     incorporating logic into mathematics. He pointed out the analogy
67     between algebraic symbols and those that represent logical forms.
68     It began the algebra of logic called Boolean algebra which now finds
69     application in computer construction, switching circuits etc.
70    
71     Boole also worked on differential equations, the influential
72     \emph{Treatise on Differential Equations} appeared in 1859, the calculus of finite
73     differences, \emph{Treatise on the Calculus of Finite Differences} (1860),
74     and general methods in probability. He published around 50 papers and
75     was one of the first to investigate the basic properties of numbers, such
76     as the distributive property, that underlie the subject of algebra.
77    
78     Many honours were given to Boole as the genius in his work was recognised.
79     He received honorary degrees from the universities of Dublin
80     and Oxford and was elected a Fellow of the Royal Society (1857).
81     However his career, which was started rather late, came to an unfortunately
82     early end when he died at the age of 49. The circumstances are described
83     by Macfarlane in [17]\footnote{As reproduced from
84     \cite{bibref:w:georgeboolebio01}---this is not a valid reference
85     number in this work.} as follows:
86    
87     \begin{quote}
88     One day in 1864 he walked from his residence to the College,
89     a distance of two miles, in the drenching rain, and lectured in wet
90     clothes. The result was a feverish cold which soon fell upon his
91     lungs and terminated his career \ldots{}
92     \end{quote}
93    
94     What Macfarlane fails to say is that Boole's wife
95     (Mary---niece of Sir George Everest, after whom the mountain is named) believed that a
96     remedy should resemble the cause. She put Boole to bed and threw
97     buckets of water over the bed since his illness had been caused by getting
98     wet.
99    
100     Hirst described Boole as:
101    
102     \begin{quote}
103     \ldots{} evidently an earnest able and at the same time a genial man.
104     \end{quote}
105    
106     His work was praised by \index{DeMorgan, Augustus}De Morgan who said:
107    
108     \begin{quote}
109     Boole's system of logic is but one of many proofs of genius and patience combined.
110     \ldots{} That the symbolic processes of algebra,
111     invented as tools of numerical calculation, should be competent to
112     express every act of thought, and to furnish the grammar and
113     dictionary of an all-containing system of logic, would not have
114     been believed until it was proved. When Hobbes \ldots{} published his
115     ``Computation or Logique'' he had a remote glimpse of some of the points which
116     are placed in the light of day by Mr Boole.
117     \end{quote}
118    
119     Boolean algebra has wide applications in telephone switching and the
120     design of modern computers. Boole's work has to be seen as a
121     fundamental step in today's computer revolution.
122     (Article by: J. J. O'Connor and E. F. Robertson.)
123     \end{quote}
124    
125     In the preface of
126     \cite{bibref:b:whitesittbooleanalgandapps}, Whitesitt explains the
127     significance of Boole's work:
128    
129     \begin{quote}
130     George Boole (1815-1864) introduced in his book \emph{The Laws Of Thought}
131     the first systematic treatment of logic and developed for this purpose
132     the algebraic system now known by his name, Boolean algebra. Few
133     mathematical works of the last 100 years have had a greater impact
134     upon mathematics and philosophy than this famous book. The significance
135     of the work has been well expressed by Augustus De Morgan:
136    
137     \begin{quote}
138     That the symbolic processes of algebra, invented as tools of numerical
139     calculation, should be competent to express every act of thought, and to
140     furnish the grammar and dictionary of an all-containing system of
141     logic, would not have been believed until it was proved in
142     \emph{Laws Of Thought}.
143     \end{quote}
144    
145     In addition to its applications in the field of logic, Boolean algebra
146     has two other important applications. The first of these arises from
147     the fact that Boolean algebra is the natural algebra with which to
148     treat the combination of sets of elements under the operations of
149     intersection and union of sets. With the addition of the idea of
150     ``number of elements'' in a set, Boolean algebra becomes the
151     foundation for the theory of probability. The algebra
152     of sets is also important in many other branches of mathematics.
153    
154     With the publication of two papers approximately 20 years
155     ago,\footnote{Whitesitt's book was first published in 1961,
156     so Whitesitt probably means \emph{20 years ago} with
157     respect to 1961.}
158     \index{Shannon, Claude E.}Claude E. Shannon introduced a new
159     area of application of
160     Boolean algebra when he showed that the basic properties of
161     series and parallel combinations of bistable electrical
162     devices such as relays could be adequately represented
163     by this algebra. Since this time, Boolean algebra has
164     played a significant role in the important and complicated
165     task of designing telephone switching circuits, automatic
166     control devices, and electronic computers. At the present
167     time, more interest is centered in this application than
168     in either of the others.
169     \end{quote}
170    
171     Claude E. Shannon's classic 1937 thesis is described separately
172     in several places. From \cite{{bibref:w:boolealghist01}}:
173    
174     \begin{quote}
175     Shannon, whose 1937 thesis centered on the improvement of the
176     Differential Analyzer, a clunky mechanical gear and shaft addition
177     machine, realized that Boolean algebraic principles governed its operation.
178     He proposed that such a machine could be built with circuits using
179     components that were governed by Boolean principles. Shannon's paper
180     was regarded as genius and his ideas were almost immediately
181     incorporated into the telephone system. Shannon took a position at Bell
182     Labs. Later, of course, Shannon's thesis came to be seen as a focal point
183     in the development of modern computers.
184     \end{quote}
185    
186     In \cite{bibref:w:boolealghist02}, Shannon's thesis is described
187     very favorably:
188    
189     \begin{quote}
190     Around the 1850's, the British mathematician George Boole was
191     busily inventing a new form of mathematics, in which he represented
192     logical expressions in a mathematical form now known as
193     Boolean Algebra.
194    
195     Unfortunately, with the exception of students of philosophy
196     and symbolic logic, Boolean Algebra was destined to remain
197     largely unknown and unused for the better part of a century.
198     It fact it was not until 1938 that Claude E. Shannon published
199     an article based on his master's thesis at MIT. (Shannon's
200     thesis has since been described as: \emph{``Possibly the
201     most important master's thesis of the twentieth century.''})
202    
203     In his paper, which was widely circulated, Shannon showed how
204     Boole's concepts of TRUE and FALSE could be used to represent
205     the functions of switches in electronic circuits. It is difficult
206     to convey just how important this concept was; suffice it to say
207     that Shannon had provided electronics engineers with the mathematical
208     tool they needed to design digital electronic circuits, and these
209     techniques remain the cornerstone of digital electronic
210     design to this day.
211    
212     Apropos of nothing at all, Shannon is also credited with the invention
213     of the rocket-powered Frisbee, and is famous for riding down the
214     corridors of Bell Laboratories on a unicycle while simultaneously
215     juggling four balls.
216     \end{quote}
217    
218     In summary, in 1854 George Boole published his classic work
219     \emph{An investigation into the Laws of Thought, on
220     Which are founded the Mathematical Theories of Logic and Probabilities},
221     which laid the foundation of manipulation of
222     logical ideas using algebraic mechanisms. Boole's ideas
223     were revived in 1937 and 1938 by Claude E. Shannon
224     in his master's thesis and a subsequent article, in which
225     Shannon applied Boole's ideas to the design of electric
226     switching circuits. Shannon's reapplication of Boole's work
227     came to be seen as a focal point in the development of modern
228     computers.
229    
230    
231     \section[Simplification By Algebraic Manipulation]
232     {Simplification Of Boolean Functions By Algebraic Manipulation}
233     %Section Tag: SAM0
234     \label{cbal0:ssam0}
235    
236     We assume that the reader has had previous exposure to
237     \index{Boolean function!simplification of}simplification of
238     Boolean functions. For this reason, this section is a review (it is terse
239     and moves quickly). (For readers without this background, we
240     recommend \cite{bibref:b:manodigitaldesignseconded}.)
241    
242     The most direct way to simplify Boolean functions is
243     \index{Boolean function!algebraic simplification}\emph{algebraic}
244     transformation---to use transformation postulates and
245     theorems to transform algebraic
246     expressions to a more desirable equivalent form.
247    
248    
249     \subsection{Nomenclature And Operators}
250     %Subsection Tag: NOM0
251     \label{cbal0:ssam0:snom0}
252    
253     We define the set of two elements which we will use in
254     two-valued Boolean
255     algebra as `0' and '1' (or alternatively as
256     `FALSE' and `TRUE', respectively).
257     All functions which we will describe subsequently require
258     inputs which are members of this set and will produce outputs
259     which are also members of this set.
260    
261     The \emph{complement} or \emph{negation} operator (or function)
262     maps from 0$\rightarrow$1 and from 1$\rightarrow$0 (see Table
263     \ref{tbl:cbal0:ssam0:snom0:01}).
264     We denote this operator
265     by an apostrophe
266     following the variable to be complemented (example: $x'$).
267     Alternatively, in some circumstances, we may use the
268     tilde ($\sim{}x$), the overbar ($\overline{x}$), or
269     the negation symbol ($\neg{}x$).
270    
271     \begin{table}
272     \caption{Definition Of Logical Complement, Logical And, Logical Or, And Logical
273     Exclusive Or Operators}
274     \label{tbl:cbal0:ssam0:snom0:01}
275     \begin{center}
276     \begin{tabular}{|c|c||c|c|c|c|}
277     \hline
278     $X$ & $Y$ & $X'$ & $XY$ & $X+Y$ & $X \oplus{} Y$ \\
279     \hline
280     \hline
281     0 & 0 & 1 & 0 & 0 & 0 \\
282     \hline
283     0 & 1 & 1 & 0 & 1 & 1 \\
284     \hline
285     1 & 0 & 0 & 0 & 1 & 1 \\
286     \hline
287     1 & 1 & 0 & 1 & 1 & 0 \\
288     \hline
289     \end{tabular}
290     \end{center}
291     \end{table}
292    
293     The \emph{logical AND} (or simply \index{AND}\index{Boolean algebra!AND}\emph{AND})
294     operator (or function)
295     returns TRUE if both of its input arguments are TRUE
296     (see Table
297     \ref{tbl:cbal0:ssam0:snom0:01}).
298     We denote this operator
299     by the \emph{times} symbol (example: $x \times{} y$), by
300     the keyword `AND', or by placing the operands adjacent to
301     each other (examples: $xy$, $x(y)$).
302    
303     The \emph{logical OR}
304     (or simply \index{OR}\index{Boolean algebra!OR}\emph{OR})
305     operator (or function)
306     returns TRUE if either of its input arguments are TRUE
307     (see Table
308     \ref{tbl:cbal0:ssam0:snom0:01}).
309     We denote this operator
310     by the \emph{plus} symbol (example: $x + y$) or by
311     the keyword `OR'.
312    
313     The \emph{logical exclusive-OR}
314     (or simply \index{XOR}\index{Boolean algebra!XOR} \emph{XOR})
315     operator (or function)
316     returns TRUE if either but not both of its input arguments are TRUE
317     (see Table
318     \ref{tbl:cbal0:ssam0:snom0:01}).
319     We denote this operator
320     by the \emph{circled plus} symbol (example: $x \oplus{} y$),
321     by the \emph{caret} character (example: $x$\^{}$y$), or by
322     the keyword `XOR'.
323    
324     The exclusive-OR function is not a
325     function traditionally considered in the canonical forms of Boolean
326     algebra. However, we consider it here because our aims may in
327     some cases be subtly
328     different than the aims of classic two-valued Boolean algebra.
329     The goal of classic Boolean algebra is to minimize the number of
330     terms which appear in a canonical form.
331     However, often our goal here is to rearrange Boolean functions into a form
332     which is optimal for implementation on a computer. Since actual
333     computers usually provide a bitwise exclusive-OR instruction, there
334     are some applications where it may be useful to consider the
335     underlying instruction set of the computer (for example,
336     see \emph{Vertical Counters},
337     Section \ref{cbal0:svct0}).
338    
339     In general, there are $2^{2^N}$ different Boolean functions of $N$
340     input variables, so it isn't practical to name functions involving more
341     than 2 input variables. There are 16 ($=2^{2^2}$) Boolean functions of
342     2 input variables, and these are enumerated in
343     Table \ref{tbl:cbal0:ssam0:snom0:02}.
344    
345     \begin{table}
346     \caption{Sixteen Possible Boolean Functions $f(A,B)$ Of Two Boolean Variables}
347     \label{tbl:cbal0:ssam0:snom0:02}
348     \begin{center}
349     \begin{tabular}{|c||c|c|c|c||l|}
350     \hline
351     \small{Func.} & $\scriptstyle{f(1,1)}$ & $\scriptstyle{f(1,0)}$
352     & $\scriptstyle{f(0,1)}$ & $\scriptstyle{f(0,0)}$
353     & Function Description \\
354     \small{Num.} & & & & & \\
355     \hline
356     \hline
357     0 & 0 & 0 & 0 & 0 & \small{``Zero'' or ``clear'' function. Always} \\
358     & & & & & \small{returns zero regardless of $A$ and $B$ } \\
359     & & & & & \small{input values. } \\
360     \hline
361     1 & 0 & 0 & 0 & 1 & \small{Logical NOR = $(A+B)'$. } \\
362     \hline
363     2 & 0 & 0 & 1 & 0 & \small{Inhibition = $BA'$. So named because } \\
364     & & & & & \small{a TRUE value of $A$ inhibits $B$. Also } \\
365     & & & & & \small{equivalent to $B>A$ or to $A<B$. } \\
366     \hline
367     3 & 0 & 0 & 1 & 1 & \small{NOT A = $A'$. Ignores $B$ and returns } \\
368     & & & & & \small{$A'$. } \\
369     \hline
370     4 & 0 & 1 & 0 & 0 & \small{Inhibition = $AB'$. So named because } \\
371     & & & & & \small{a TRUE value of $B$ inhibits $A$. Also } \\
372     & & & & & \small{equivalent to $A>B$ or to $B<A$. } \\
373     \hline
374     5 & 0 & 1 & 0 & 1 & \small{NOT B = $B'$. Ignores $A$ and returns } \\
375     & & & & & \small{$B'$. } \\
376     \hline
377     6 & 0 & 1 & 1 & 0 & \small{Exclusive-OR (XOR) = $A \oplus B$. Also} \\
378     & & & & & \small{equivalent to $A \neq B$. } \\
379     \hline
380     7 & 0 & 1 & 1 & 1 & \small{Logical NAND = $(AB)'$. } \\
381     \hline
382     8 & 1 & 0 & 0 & 0 & \small{Logical AND = $AB$. } \\
383     \hline
384     9 & 1 & 0 & 0 & 1 & \small{Equivalence: true if $A=B$. Also} \\
385     & & & & & \small{known as exclusive-NOR, i.e. $(A \oplus B)'$.} \\
386     \hline
387     10 & 1 & 0 & 1 & 0 & \small{Copy $B$. Ignores $A$ and returns $B$. } \\
388     \hline
389     11 & 1 & 0 & 1 & 1 & \small{Implication: $B \rightarrow A$ (if $B$ } \\
390     & & & & & \small{then $A$). Also equivalent to $B \geq A$.} \\
391     \hline
392     12 & 1 & 1 & 0 & 0 & \small{Copy $A$. Ignores $B$ and returns $A$. } \\
393     \hline
394     13 & 1 & 1 & 0 & 1 & \small{Implication: $A \rightarrow B$ (if $A$ } \\
395     & & & & & \small{then $B$). Also equivalent to $A \geq B$.} \\
396     \hline
397     14 & 1 & 1 & 1 & 0 & \small{Logical OR = $A+B$. } \\
398     \hline
399     15 & 1 & 1 & 1 & 1 & \small{``One'' or ``set'' function. Always } \\
400     & & & & & \small{returns one regardless of $A$ and $B$ } \\
401     & & & & & \small{input values. } \\
402     \hline
403     \end{tabular}
404     \end{center}
405     \end{table}
406    
407     \emph{Any} Boolean function can be synthesized using AND gates and inverters
408     (i.e. NOT gates), OR gates and inverters, NAND gates alone, or NOR
409     gates alone. However, not all Boolean functions can be synthesized
410     using AND gates alone or OR gates alone.
411    
412    
413     \subsection{Postulates And Theorems}
414     %Subsection Tag: POS0
415     \label{cbal0:ssam0:spos0}
416    
417     Mathematicians tend to be very picky about what exactly a
418     \emph{postulate} is versus what a \emph{theorem} is. We are
419     far less picky. Either one (a postulate or a theorem) is a
420     rule that can be used to transform a Boolean algebraic expression
421     into another expression which is equivalent but for one reason or another
422     more desirable. For our purposes here, postulates and theorems
423     are interchangeable.
424    
425     Table \ref{tbl:cbal0:ssam0:spos0:01}
426     (from \cite{bibref:b:manodigitaldesignseconded})
427     supplies the important postulates and theorems which are useful in
428     algebraically simplifying Boolean functions.
429    
430     In Table \ref{tbl:cbal0:ssam0:spos0:01}, we should explain what
431     is meant by the \emph{Dual Postulate Or Theorem}. To
432     quote \cite{bibref:b:manodigitaldesignseconded}, p. 41:
433    
434     \begin{quote}
435     \ldots This important property of Boolean algebra is called
436     the \index{Boolean algebra!duality principle}\index{duality principle}%
437     \emph{duality principle}.
438     It states that every algebraic expression deducible from the postulates
439     of Boolean algebra remains valid if the operators and identity
440     elements are interchanged. In a two-valued Boolean algebra,
441     the identity elements and the elements of the set $B$ are the
442     same: 1 and 0. The duality principle has many applications.
443     If the \emph{dual} of an algebraic expression is desired, we
444     simply interchange OR and AND operators and replaces 1s by
445     0s and 0s by 1s.
446     \end{quote}
447    
448     \begin{table}
449     \caption{Important Postulates And Theorems Of Two-Valued Boolean Algebra}
450     \label{tbl:cbal0:ssam0:spos0:01}
451     \begin{center}
452     \begin{tabular}{|c||c|c||l|}
453     \hline
454     \small{Postulate} & \small{Postulate} & \small{Dual} & \small{Remarks} \\
455     \small{Or} & \small{Or} & \small{Postulate} & \\
456     \small{Theorem} & \small{Theorem} & \small{Or} & \\
457     \small{Number} & & \small{Theorem} & \\
458     \hline
459     1 & $x + 0 = x$ & $x \cdot 1 = 1$ & \\
460     \hline
461     2 & $x + x' = 1$ & $x \cdot x' = 0$ & \\
462     \hline
463     3 & $x + x = x$ & $x \cdot x = x$ & \\
464     \hline
465     4 & $x + 1 = 1$ & $x \cdot 0 = 0$ & \\
466     \hline
467     5 & $(x')' = x$ & & \small{Involution.} \\
468     \hline
469     6 & $x + y = y + x$ & $x \cdot y = y \cdot x $ & \small{Commutative property.} \\
470     \hline
471     7 & $x + (y + z)$ & $x(yz) = (xy)z$ & \small{Associative property.} \\
472     & $= (x + y) + z$ & & \\
473     \hline
474     8 & $x (y + z)$ & $x + yz$ & \small{Distributive property.} \\
475     & $= xy + xz$ & $= (x+y)(x+z)$ & \\
476     \hline
477     9 & $(x+y)' = x'y'$ & $(xy)' = x' + y'$ & \small{DeMorgan's theorem.} \\
478     \hline
479     10 & $x + xy = x$ & $x(x+y) = x$ & \small{Absorption.} \\
480     \hline
481     \end{tabular}
482     \end{center}
483     \end{table}
484    
485     Note also from Item 8 of
486     Table \ref{tbl:cbal0:ssam0:spos0:01} that in Boolean algebra
487     AND distributes over OR and OR distributes over AND (waiting on
488     newsgroup posters to clarify). This is unlike ``normal'' algebra, where
489     in general,
490    
491     \begin{equation}
492     x + yz \neq (x+y) (x+z).
493     \end{equation}
494    
495     The \index{Boolean algebra!operator precedence}%
496     \index{operator precedence!Boolean algebra}\index{operator precedence}%
497     operator precedence for evaluating Boolean expressions assumed throughout
498     this work is:
499    
500     \begin{quote}
501     \begin{enumerate}
502     \item Parenthesis.
503     \item NOT.
504     \item AND.
505     \item OR.
506     \end{enumerate}
507     \end{quote}
508    
509     \noindent{}Note that this operator precedence very closely mirrors
510     the standard precedence of normal algebraic expressions.
511    
512     \subsection{Canonical And Standard Forms}
513     %Subsection Tag: CAS0
514     \label{cbal0:ssam0:scas0}
515    
516     \cite{bibref:b:manodigitaldesignseconded}, p. 49 provides an concise and
517     excellent definition of \emph{minterms} and \emph{maxterms}. The definition
518     here is taken primarily from that source.
519    
520     A binary variable may appear either in its normal form ($x$, for example)
521     or in its complemented form ($x'$, for example). Now consider two
522     binary variables $x$ and $y$ combined with an AND
523     operation. Since each variable may appear in either form, there are four
524     possible combinations: $x'y'$, $x'y$, $xy'$, and $xy$. These
525     four AND terms are mutually exclusive and mutually exhaustive---that is,
526     no combination of values for
527     $x$ and
528     $y$ that causes one of these AND terms to be TRUE may cause any of the
529     others to be TRUE, and every combination of $x$ and $y$ will cause exactly
530     one of these AND terms to be TRUE. Each of these
531     four AND terms is called a \index{Boolean algebra!minterm}\index{minterm}\emph{minterm}
532     or \index{Boolean algebra!standard product}\index{standard product}\emph{standard product}.
533     In a similar manner, $n$ variables can be combined to form $2^n$ minterms.
534    
535     In a similar fashion, $n$ variables forming an OR term, with each variable
536     being primed or unprimed, provide $2^n$ possible combinations, called
537     \index{Boolean algebra!maxterm}\index{maxterm}\emph{maxterms}, or
538     \index{Boolean algebra!standard sum}\index{standard sum}\emph{standard sums}.
539    
540     \begin{table}
541     \caption{Minterms And Maxterms Of Three Boolean Variables}
542     \label{tbl:cbal0:ssam0:scas0:01}
543     \begin{center}
544     \begin{tabular}{|c|c|c||c|c||c|c|}
545     \hline
546     $x$ & $y$ & $z$ & \small{Minterm} & \small{Minterm} & \small{Maxterm} & \small{Maxterm} \\
547     & & & \small{Term} & \small{Designation} & \small{Term} & \small{Designation} \\
548     \hline
549     0 & 0 & 0 & $x'y'z'$ & $m_0$ & $x+y+z$ & $M_0$ \\
550     \hline
551     0 & 0 & 1 & $x'y'z$ & $m_1$ & $x+y+z'$ & $M_1$ \\
552     \hline
553     0 & 1 & 0 & $x'yz'$ & $m_2$ & $x+y'+z$ & $M_2$ \\
554     \hline
555     0 & 1 & 1 & $x'yz$ & $m_3$ & $x+y'+z'$ & $M_3$ \\
556     \hline
557     1 & 0 & 0 & $xy'z'$ & $m_4$ & $x'+y+z$ & $M_4$ \\
558     \hline
559     0 & 0 & 1 & $x'y'z$ & $m_5$ & $x+y+z'$ & $M_5$ \\
560     \hline
561     1 & 1 & 0 & $xyz'$ & $m_6$ & $x'+y'+z$ & $M_6$ \\
562     \hline
563     1 & 1 & 1 & $xyz$ & $m_7$ & $x'+y'+z'$ & $M_7$ \\
564     \hline
565     \end{tabular}
566     \end{center}
567     \end{table}
568    
569     The two primary canonical forms in Boolean algebra are the
570     \emph{sum of minterms} (or \emph{sum of products}) form and the
571     \emph{product of maxterms} (or \emph{product of sums}) form.
572    
573     The sum of minterms canonical form (which is the most common
574     canonical form) is sometimes written using a shorthand
575     notation involving the Greek letter sigma ($\Sigma$). We describe this
576     shorthand form now. Consider the Boolean function of 3 variables,
577    
578     \begin{equation}
579     \label{eq:cbal0:ssam0:scas0:01}
580     F(A, B, C) = A + B'C.
581     \end{equation}
582    
583     \noindent{}Using the postulates and theorems in Table
584     \ref{tbl:cbal0:ssam0:spos0:01}, it is possible
585     to expand (\ref{eq:cbal0:ssam0:scas0:01}) into
586     a sum of minterms form:
587    
588     \begin{eqnarray}
589     \label{eq:cbal0:ssam0:scas0:02}
590     F(A, B, C) & = & A'B'C + AB'C' + AB'C + ABC' + ABC \\
591     & = & m_1 m_4 m_5 m_6 m_7.\nonumber
592     \end{eqnarray}
593    
594     \noindent{}(\ref{eq:cbal0:ssam0:scas0:02}) is also commonly written
595     in the shorthand form:
596    
597     \begin{equation}
598     \label{eq:cbal0:ssam0:scas0:03}
599     F(A, B, C) = \Sigma{}(1, 4, 5, 6, 7).
600     \end{equation}
601    
602     \noindent{}In the right-hand side of
603     (\ref{eq:cbal0:ssam0:scas0:03}), each integer
604     (1, 4, 5, 6, or 7) corresponds to the integer
605     that would be formed by treating the corresponding
606     minterm in (\ref{eq:cbal0:ssam0:scas0:02}) as
607     a binary number, i.e. $A=2^2$, $B=2^1$, and
608     $C=2^0$. This is the basis of the short hand
609     notation.
610    
611     A second but much less commonly used canonical form
612     is the product of maxterms (or product of sums) form,
613     which uses the Greek letter pi ($\Pi$) for its shorthand
614     form. Without further explanation, we present the
615     product of maxterms form of $\Sigma{}(1,4,5,6,7)$
616     (Eqns. \ref{eq:cbal0:ssam0:scas0:01} through
617     \ref{eq:cbal0:ssam0:scas0:03}) as
618     (\ref{eq:cbal0:ssam0:scas0:04})
619     through (\ref{eq:cbal0:ssam0:scas0:07})
620     (Figure \ref{fig:cbal0:ssam0:scas0:01}).
621    
622     \begin{figure}
623     \begin{eqnarray}
624     \label{eq:cbal0:ssam0:scas0:04}
625     F(A, B, C) & = & \Sigma{}(1, 4, 5, 6, 7) \\
626     \label{eq:cbal0:ssam0:scas0:05}
627     & = & \Pi{}(0, 2, 3) \\
628     \label{eq:cbal0:ssam0:scas0:06}
629     & = & M_0 M_2 M_3 \\
630     \label{eq:cbal0:ssam0:scas0:07}
631     & = & (x+y+z)(x+y'+z)(x+y'+z')
632     \end{eqnarray}
633     \caption{Product Of Maxterms Form Of $\Sigma{}(1,4,5,6,7)$}
634     \label{fig:cbal0:ssam0:scas0:01}
635     \end{figure}
636    
637    
638     Because there are so many excellent digital logic books on the market
639     that contain examples and exercises of algebraic simplification
640     (we recommend \cite{bibref:b:manodigitaldesignseconded}), we don't
641     dwell on algebraic simplification or provide examples. Again, we
642     assume that nearly all of our readers have had a course in digital
643     logic or symbolic logic.
644    
645    
646     \section[Karnaugh Maps]
647     {Simplification Of Boolean Functions Using Karnaugh Maps}
648     %Section tag: SKM0
649     \label{cbal0:skm0}
650    
651     In 1953, M. Karnaugh published the graphical map method of simplifying
652     combinational logic functions (\cite{bibref:p:kmapclassic01}). This
653     method has come to be known as the \emph{Karnaugh map} or \emph{K-map}
654     method of reduction, and is taught to engineers in nearly every
655     digital logic class.
656    
657     Although it is possible, starting from an arbitrary Boolean formula, to simplify
658     the formula through algebraic manipulation, algebraic simplification
659     has the disadvantage that formulas can have many forms and there is not
660     an easily remembered, precise, and repeatable procedure for algebraic simplification.
661     The Karnaugh map method has the advantage that each Boolean function
662     has only one graphical representation, and that the procedure for simplification
663     is simple and easily remembered.
664    
665     In a Karnaugh map, each square corresponds to a possible minterm of the function.
666     The essence of the method is to populate a grid of squares with outputs of
667     the function to be simplified. Each minterm that must exist in the
668     function (i.e. each combination of inputs for which the function
669     must return TRUE) receives a `1' in the corresponding square. Each
670     combination of inputs for which the function must return FALSE
671     receives a `0' in the corresponding square. Each combination of inputs
672     for which the function may return either TRUE or FALSE receives an
673     `X' in the corresponding square.
674    
675     After the Karnaugh map squares are populated with 1's, 0's, and X's
676     corresponding to the required values of the function for each combination
677     of inputs, the 1's are graphically combined into the largest rectangle possible.
678     Each rectangle may include 1's, may include X's where convenient, but
679     may not include 0's.
680     Each of these squares is then translated into a product of uncomplemented and
681     complemented input variables, and these products are summed to
682     produce the simplified algebraic expression for the function. (We don't
683     belabor this process, because we assume that most of our readers
684     understand it very thoroughly.) There are some subtle points
685     to the process, such as combining corners and the ``folding'' of the
686     5- and 6-variable maps, but we don't explain these subtle points here
687     because they are so thoroughly explained in so many books.
688    
689     Figures \ref{fig:cbal0:skm0:00} through \ref{fig:cbal0:skm0:04}
690     supply the canonical forms of two-, three-, four-, five-, and
691     six-variable Karnaugh maps.
692    
693     \begin{figure}
694     \centering
695     \includegraphics[width=1.25in]{c_bal0/kmap02cf.eps}
696     \caption{Canonical Form Of Two-Variable Karnaugh Map}
697     \label{fig:cbal0:skm0:00}
698     \end{figure}
699    
700     \begin{figure}
701     \centering
702     \includegraphics[height=1.25in]{c_bal0/kmap03cf.eps}
703     \caption{Canonical Form Of Three-Variable Karnaugh Map}
704     \label{fig:cbal0:skm0:01}
705     \end{figure}
706    
707     \begin{figure}
708     \centering
709     \includegraphics[height=2.0in]{c_bal0/kmap04cf.eps}
710     \caption{Canonical Form Of Four-Variable Karnaugh Map}
711     \label{fig:cbal0:skm0:02}
712     \end{figure}
713    
714     \begin{figure}
715     \centering
716     \includegraphics[width=4.25in]{c_bal0/kmap05cf.eps}
717     \caption{Canonical Form Of Five-Variable Karnaugh Map}
718     \label{fig:cbal0:skm0:03}
719     \end{figure}
720    
721     \begin{figure}
722     \centering
723     \includegraphics[width=4.5in]{c_bal0/kmap06cf.eps}
724     \caption{Canonical Form Of Six-Variable Karnaugh Map}
725     \label{fig:cbal0:skm0:04}
726     \end{figure}
727    
728     \section[Simplification Using The Scheinman Method]
729     {Simplification Of Boolean Functions Using The Scheinman Method}
730     %Section Tag: SCM0
731     \label{cbal0:sscm0}
732    
733     Two major disadvantages of the Karnaugh map method of simplifying Boolean
734     functions are that:
735    
736     \begin{itemize}
737     \item It is generally not possible to apply the method to functions
738     of more than six variables.
739     \item It is not easy to automate the method (in the form that it is stated)
740     because it is inherently graphical.
741     \end{itemize}
742    
743     In 1962, A. H. Scheinman published a method for the simplification
744     of Boolean functions (\cite{bibref:p:scheinmanclassic01}) which is more amenable
745     to automation than the Karnaugh map method.
746    
747     \section[The Quine-McCluskey Method]
748     {Simplification Of Boolean Functions Using The Quine-McCluskey Method}
749    
750    
751     \section{Multiple Functions Of $N$ Boolean Variables}
752    
753     Need to get back to Dr. Singh to inquire about the multiple Scheinman method.
754    
755     \section{Vertical Counters}
756     %Section Tag: VCT0.
757     \label{cbal0:svct0}
758    
759     \index{vertical counter}As has been hinted at elsewhere
760     in this work, the need to generate
761     firmware which minimizes ROM consumption leads to clever (but perhaps
762     less-than-intuitive) programming techniques. One such technique
763     is the construction of \emph{vertical counters}.
764    
765     A \index{vertical counter}vertical counter
766     is a set of identical combinational mappings or state machines
767     where the inputs, state vector, intermediate results, and outputs of each
768     combinational mapping or state machine are stored as a single bit
769     in the same position
770     in each of multiple bytes or words. When inputs, state vectors,
771     intermediate results, and outputs are stored
772     in this way, the bitwise logical instructions of the machine
773     (AND, OR, NOT, XOR) can be used to process several state machines in
774     parallel. Vertical counters are intimately related to the reduction
775     of Boolean functions because such reduction must be performed in order
776     to design the vertical counter. Debouncing and filtering, where the
777     inputs and outputs naturally tend to be arranged as groups of bits,
778     are the most common application of vertical counters.
779    
780     A very helpful resource on the web is the set of web pages
781     maintained by \index{Dattalo, Scott}Scott Dattalo
782     \cite{bibref:i:scottdattalo} for the
783     PIC microcontroller, including
784     especially \cite{bibref:w:sdattalovc02}. Many of the vertical counter
785     designs which follow come from Mr. Dattalo's pages.
786    
787     We abuse the term \emph{counter} somewhat, and we refer to
788     any bit-wise mapping useful in microcontroller work as
789     a vertical counter. We categorize vertical counters as
790     \index{vertical counter!combinational}\emph{combinational}
791     (not truly a counter---the output is a function of the
792     inputs only), \index{vertical counter!sequential}\emph{sequential}
793     (the next state and output may be functions of both the
794     inputs and the present state---i.e. a proper state machine),
795     \index{vertical counter!cyclic}\emph{cyclic} (the counter
796     goes through a series of states and then repeats), or
797     \index{vertical counter!terminating} (the counter
798     will reach a terminal state).
799    
800     \subsection{2-Bit 4-State Cyclic Vertical Counter}
801     %Subsection Tag: TBF0
802     \label{cbal0:svct0:stbf0}
803     In this discussion of vertical counters, we begin with the simplest
804     designs, as often the simpler designs appear as part of more complex
805     designs.
806    
807     Table \ref{tbl:cbal0:svct0:stbf0:01} supplies the state transition table
808     for a 2-bit 4-state
809     cyclic vertical counter. Note that the counter advances through the
810     bit patterns in the ``proper'' binary integer order.
811    
812     \begin{table}
813     \caption{State Transition Table Of 2-Bit 4-State Cyclic Vertical Counter}
814     \label{tbl:cbal0:svct0:stbf0:01}
815     \begin{center}
816     \begin{tabular}{|c|c|c|c|}
817     \hline
818     $A_k$ & $B_k$ & $A_{k+1}$ & $B_{k+1}$ \\
819     \hline
820     \hline
821     0 & 0 & 0 & 1 \\
822     \hline
823     0 & 1 & 1 & 0 \\
824     \hline
825     1 & 0 & 1 & 1 \\
826     \hline
827     1 & 1 & 0 & 0 \\
828     \hline
829     \end{tabular}
830     \end{center}
831     \end{table}
832    
833     From Table \ref{tbl:cbal0:svct0:stbf0:01} it can be readily verified
834     even without a Karnaugh map that the least significant bit
835     ($B$) is always complemented from one state to the next, so that
836     $B_{k+1} = \neg B_k$. It can also be seen that the most significant
837     bit ($A$) is complemented from one state to the next only if $B$=1,
838     so that $A_{k+1} = A_k \oplus B_k$.
839    
840     The implementation of such a counter in `C' comes immediately, since
841     `C' directly supports bit-wise complementation and exclusive-OR of
842     integers:
843    
844     \begin{verbatim}
845     A = A ^ B;
846     B = ~B;
847     \end{verbatim}
848    
849     Note in the `C' snippet above, the two operations are ordered so as
850     not to interfere with each other. Note that reversing the two steps above
851     would not yield the desired result.
852    
853    
854     \subsection{3-Bit 8-State Cyclic Vertical Counter}
855     %Subsection Tag: TBF4
856     \label{cbal0:svct0:stbf4}
857    
858    
859     \subsection[$N$-Bit $2^N$-State Cyclic Vertical Counter]
860     {\mbox{\boldmath $N$}-Bit \mbox{\boldmath $2^N$}-State Cyclic Vertical Counter}
861     %Subsection Tag: TBF1
862     \label{cbal0:svct0:stbf1}
863    
864     The design of the 2-bit 4-state vertical counter presented in
865     Section \ref{cbal0:svct0:stbf0} (immediately above) and be
866     generalized to an $N$-bit $2^N$-state counter which follows
867     the traditional binary integer counting sequence.
868    
869     Note from Section \ref{cbal0:svct0:stbf0} that the least
870     significant bit of the counter is always complemented
871     in going from one state to the next, and that each more
872     significant bit is complemented only if all less significant
873     bits are 1. If $X_0$ is the least significant bit of the
874     counter and $X_N$ the most significant bit,
875     (\ref{eq:cbal0:svct0:stbf1:01}) through (\ref{eq:cbal0:svct0:stbf1:05})
876     (Figure \ref{eq:cbal0:svct0:stbf1:01})
877     describe how the counter is advanced from one state to the next.
878     Note that this set of equations gives only a \emph{logical} description
879     of how to obtain the next state from the present state---these
880     equations cannot be used as a direct blueprint for implementation because
881     earlier steps would destroy the results needed for later steps.
882    
883     \begin{figure}
884     \begin{eqnarray}
885     \label{eq:cbal0:svct0:stbf1:01}
886     X_0(k+1) & = & \neg X_0(k) \\
887     \label{eq:cbal0:svct0:stbf1:02}
888     X_1(k+1) & = & X_1(k) \oplus X_0(k) \\
889     \label{eq:cbal0:svct0:stbf1:03}
890     X_2(k+1) & = & X_2(k) \oplus (X_1(k) X_0(k)) \\
891     \label{eq:cbal0:svct0:stbf1:04}
892     X_3(k+1) & = & X_3(k) \oplus (X_2(k) X_1(k) X_0(k)) \\
893     & \ldots & \nonumber \\
894     \label{eq:cbal0:svct0:stbf1:05}
895     X_N(k+1) & = & X_N(k) \oplus (X_{N-1}(k) \ldots X_0(k))
896     \end{eqnarray}
897     \caption{State Transition Equations Of $N$-Bit $2^N$-State Cyclic Vertical Counter}
898     \label{fig:cbal0:svct0:stbf1:01}
899     \end{figure}
900    
901     The form of
902     (\ref{eq:cbal0:svct0:stbf1:01}) through (\ref{eq:cbal0:svct0:stbf1:05})
903     suggests a way to economically implement an $N$-bit $2^N$-state
904     cyclic vertical counter in software, using two temporary
905     variables $TEMP_A$ and $TEMP_B$. The general blueprint for
906     implementation is supplied as
907     (\ref{eq:cbal0:svct0:stbf1:06}) through (\ref{eq:cbal0:svct0:stbf1:20})
908     (Figure \ref{eq:cbal0:svct0:stbf1:02}).
909    
910     \begin{figure}
911     \begin{eqnarray}
912     \label{eq:cbal0:svct0:stbf1:06}
913     TEMP_A & = & X_0 \\
914     \label{eq:cbal0:svct0:stbf1:07}
915     X_0 & = & \neg X_0 \\
916     \label{eq:cbal0:svct0:stbf1:08}
917     TEMP_B & = & X_1 TEMP_A \\
918     \label{eq:cbal0:svct0:stbf1:09}
919     X_1 & = & X_1 \oplus TEMP_A \\
920     \label{eq:cbal0:svct0:stbf1:10}
921     TEMP_A & = & TEMP_B \\
922     \label{eq:cbal0:svct0:stbf1:11}
923     TEMP_B & = & X_2 TEMP_B \\
924     \label{eq:cbal0:svct0:stbf1:12}
925     X_2 & = & X_2 \oplus TEMP_A \\
926     \label{eq:cbal0:svct0:stbf1:13}
927     TEMP_A & = & TEMP_B \\
928     \label{eq:cbal0:svct0:stbf1:14}
929     TEMP_B & = & X_3 TEMP_B \\
930     \label{eq:cbal0:svct0:stbf1:15}
931     X_3 & = & X_3 \oplus TEMP_A \\
932     & \ldots & \nonumber \\
933     \label{eq:cbal0:svct0:stbf1:16}
934     X_{N-2} & = & X_{N-2} \oplus TEMP_A \\
935     \label{eq:cbal0:svct0:stbf1:17}
936     TEMP_A & = & TEMP_B \\
937     \label{eq:cbal0:svct0:stbf1:18}
938     TEMP_B & = & X_{N-1} TEMP_B \\
939     \label{eq:cbal0:svct0:stbf1:19}
940     X_{N-1} & = & X_{N-1} \oplus TEMP_A \\
941     \label{eq:cbal0:svct0:stbf1:20}
942     X_N & = & X_N \oplus X_N TEMP_B
943     \end{eqnarray}
944     \caption{Implementation Blueprint Of $N$-Bit $2^N$-State Cyclic Vertical Counter}
945     \label{fig:cbal0:svct0:stbf1:02}
946     \end{figure}
947    
948     Figure \ref{fig:cbal0:svct0:stbf1:01}
949     supplies a concrete example of a C-language
950     implementation of a 5-bit 32-state cyclic vertical counter.
951     Note that the counter will follow the traditional
952     binary integer counting sequence. Note also that
953     the blueprint provided by Eqns.
954     (\ref{eq:cbal0:svct0:stbf1:06}) through (\ref{eq:cbal0:svct0:stbf1:20})
955     and Figure \ref{fig:cbal0:svct0:stbf1:01} can
956     be extended to a counter of any size.
957    
958     \begin{figure}
959     \begin{verbatim}
960     /**************************************************************/
961     /* Assume: */
962     /* x4 : Byte containing most significant bits of the */
963     /* a group of 8 bits. */
964     /* x3, */
965     /* x2, */
966     /* x1 : Bytes containing the intermediate bits. */
967     /* x0 : Byte containing the least significant bits. */
968     /* temp_a, */
969     /* temp_b : Temporary variables, used to accumulate the */
970     /* result of AND'ing old counter bit values. */
971     /**************************************************************/
972    
973     temp_a = x0;
974     x0 = ~x0;
975     temp_b = x1 & temp_a;
976     x1 = x1 ^ temp_a;
977     temp_a = temp_b;
978     temp_b = x2 & temp_b;
979     x2 = x2 ^ temp_a;
980     temp_a = temp_b;
981     temp_b = x3 & temp_b;
982     x3 = x3 ^ temp_a;
983     x4 = x4 ^ temp_b;
984    
985     /* End of code. */
986     \end{verbatim}
987     \caption{C-Language Implementation Of 5-Bit 32-State Cyclic Vertical Counter}
988     \label{fig:cbal0:svct0:stbf1:01b}
989     \end{figure}
990    
991    
992     \subsection{3-Bit 5-State Cyclic Vertical Counter}
993     %Subsection Tag: TBF5
994     \label{cbal0:svct0:stbf5}
995    
996    
997     \subsection{3-Bit 6-State Cyclic Vertical Counter}
998     %Subsection Tag: TBF6
999     \label{cbal0:svct0:stbf6}
1000    
1001    
1002     \subsection{3-Bit 7-State Cyclic Vertical Counter}
1003     %Subsection Tag: TBF7
1004     \label{cbal0:svct0:stbf7}
1005    
1006    
1007     \subsection{2-Bit 4-State Terminating Vertical Counter}
1008     %Subsection Tag: TBF8
1009     \label{cbal0:svct0:stbf8}
1010    
1011    
1012     \subsection{3-Bit 5-State Terminating Vertical Counter}
1013     %Subsection Tag: TBF9
1014     \label{cbal0:svct0:stbf9}
1015    
1016    
1017     \subsection{3-Bit 6-State Terminating Vertical Counter}
1018     %Subsection Tag: TBG0
1019     \label{cbal0:svct0:stbg0}
1020    
1021    
1022     \subsection{3-Bit 7-State Terminating Vertical Counter}
1023     %Subsection Tag: TBG1
1024     \label{cbal0:svct0:stbg1}
1025    
1026    
1027     \subsection{2/3 Debouncing Vertical Counter}
1028     %Subsection Tag: TTD0.
1029     \label{cbal0:svct0:sttd0}
1030    
1031     \index{debouncing}\index{debouncing!2/3}\emph{2/3 debouncing}
1032     is debouncing where at least two of the most recent
1033     three samples must be at the same value (either 0 or 1) to cause the output
1034     to be that same value.
1035    
1036     Note that \emph{2/3 debouncing} as we describe it here represents a
1037     purely combinational mapping from the 3 most recent samples to
1038     the debounced output. When 3 samples are available, 0 of the
1039     samples or 1 of the samples with value 1 map to a debounced
1040     output value of 0; while 2 of the samples or 3 of the samples
1041     with value 1 map to a debounced output value of 1.
1042    
1043     If $A$ is the most recent sample, $B$ is the next-most-recent sample, and
1044     $C$ is the oldest sample, Fig. \ref{fig:cbal0:svct0:sttd0:01}
1045     supplies the Karnaugh map for 2/3
1046     debouncing.
1047    
1048     \begin{figure}
1049     \centering
1050     \includegraphics[height=1.25in]{c_bal0/kmap23db.eps}
1051     \caption{Karnaugh Map Of 2/3 Debouncing}
1052     \label{fig:cbal0:svct0:sttd0:01}
1053     \end{figure}
1054    
1055     It can be seen from the figure that the expression for the output is
1056    
1057     \begin{equation}
1058     \label{eq:cbal0:svct0:sttd0:01}
1059     AB + AC + BC = A (B+C) + BC .
1060     \end{equation}
1061    
1062     Intuitively, (\ref{eq:cbal0:svct0:sttd0:01}) makes sense---the output
1063     will be 1 if any two of the most recent samples are 1
1064     ($AB + AC + BC$). Similarly, the output will be 0 if any two of
1065     the most recent samples are 0.
1066    
1067     Figure \ref{fig:cbal0:svct0:sttd0:02} supplies the C-language
1068     code to implement 2/3 debouncing as a vertical mapping.
1069     A C-compiler will typically implement this code very directly
1070     using the bitwise logical instructions of the machine.
1071    
1072     \begin{figure}
1073     \begin{verbatim}
1074     /**************************************************************/
1075     /* Assume: */
1076     /* A : Most recent sample (i.e. at t(0)), arranged as */
1077     /* a group of 8 bits. */
1078     /* B : Next most recent sample t(-1). */
1079     /* C : Oldest sample t(-2). */
1080     /* output : Debounced collection of 8 bits presented to */
1081     /* software internals. */
1082     /**************************************************************/
1083    
1084     output = (A & (B | C)) | (B & C);
1085    
1086     /* End of code. */
1087     \end{verbatim}
1088     \caption{C-Language Implementation Of 2/3 Debouncing}
1089     \label{fig:cbal0:svct0:sttd0:02}
1090     \end{figure}
1091    
1092     \subsection{3/3 Debouncing Vertical Counter}
1093     %Subsection Tag: TTD1.
1094     \label{cbal0:svct0:sttd1}
1095    
1096     \index{debouncing}\index{debouncing!3/3}\emph{3/3 debouncing}
1097     is debouncing where all three of the most recent
1098     three samples must be at a value (either 0 or 1) to cause the
1099     debounced output to transition to that same value.
1100    
1101     Note that 3/3 debouncing as we present it is a sequential (rather than
1102     a purely combinational) mapping from the 3 most recent samples to the
1103     debounced output. In addition to the 3 inputs, the behavior of the
1104     mapping depends on a single bit of state which is held. (In the
1105     implementation presented in this section, the state and the debounced
1106     output are the same bit.) For example, if 2 of the 3 most recent
1107     input samples are 1, the debounced output value may be either 0
1108     or 1. The transition of the debounced output value from
1109     0 to 1 or from 1 to 0 can only occur if all 3 most recent samples
1110     are 1 or are 0, respectively.
1111    
1112     If $A$ is the most recent sample, $B$ is the next-most-recent sample,
1113     $C$ is the oldest sample, and $O$ is the output (assumed maintained
1114     as a RAM location) Fig. \ref{fig:cbal0:svct0:sttd1:01}
1115     supplies the Karnaugh map for 3/3
1116     debouncing.
1117    
1118     \begin{figure}
1119     \centering
1120     \includegraphics[height=2.0in]{c_bal0/kmap33db.eps}
1121     \caption{Karnaugh Map Of 3/3 Debouncing}
1122     \label{fig:cbal0:svct0:sttd1:01}
1123     \end{figure}
1124    
1125     It can be seen from the figure that the expression for the output is
1126    
1127     \begin{equation}
1128     \label{eq:cbal0:svct0:sttd1:01}
1129     ABC + AO + BO + CO = ABC + O(A + B + C).
1130     \end{equation}
1131    
1132     Intuitively, (\ref{eq:cbal0:svct0:sttd1:01}) makes sense---the output
1133     will be unconditionally 1 if all three of the most recent samples are 1
1134     ($ABC$). The output will also be 1 if the previous output was 1
1135     and at least one of the most recent samples are 1 [$O(A+B+C)$]---at least
1136     one true recent sample blocks the output from transition to 0.
1137    
1138     Figure \ref{fig:cbal0:svct0:sttd1:02} supplies the C-language
1139     code to implement 3/3 debouncing as a vertical mapping.
1140     A C-compiler will typically implement this code very directly
1141     using the bitwise logical instructions of the machine.
1142    
1143     \begin{figure}
1144     \begin{verbatim}
1145     /**************************************************************/
1146     /* Assume: */
1147     /* A : Most recent sample (i.e. at t(0)), arranged as */
1148     /* a group of 8 bits. */
1149     /* B : Next most recent sample t(-1). */
1150     /* C : Oldest sample t(-2). */
1151     /* output : Debounced collection of 8 bits presented to */
1152     /* software internals. Note that this is both */
1153     /* an input (to the combinational mapping) and */
1154     /* the new result. */
1155     /**************************************************************/
1156    
1157     output = (A & B & C) | (output & (A | B | C));
1158    
1159     /* End of code. */
1160     \end{verbatim}
1161     \caption{C-Language Implementation Of 3/3 Debouncing}
1162     \label{fig:cbal0:svct0:sttd1:02}
1163     \end{figure}
1164    
1165     \subsection{N/N Debouncing Vertical Counter}
1166     %Subsection Tag: NNC0.
1167     \label{cbal0:svct0:snnc0}
1168    
1169     \index{debouncing}\index{debouncing!N/N}It is clear from
1170     the design of the 3/3 debouncing
1171     vertical counter (Section \ref{cbal0:svct0:sttd1}, immediately
1172     above) that the design of the 3/3 debouncing vertical counter
1173     can be generalized to cover any number of recent samples.
1174     We call such a debouncing vertical counter an N/N debouncing
1175     vertical counter. In order for the output of such a counter to
1176     turn 1, all $N$ most recent samples must be 1. Similarly, in order
1177     for such a counter to turn 0, all $N$ most recent samples must be 0.
1178    
1179     We rely on a logical argument to design such a N/N debouncing
1180     vertical counter, rather than on Karnaugh maps. If $I_1 \ldots I_N$
1181     are the $N$ most recent input samples and $O$ is the most recent
1182     output (assumed stored in RAM), it is clear from the form of
1183     (\ref{eq:cbal0:svct0:sttd1:01}) that the formula for the new output
1184     as a function of the inputs $I_1 \ldots I_N$ and the
1185     most recent output $O_{k-1}$ must be:
1186    
1187     \begin{equation}
1188     \label{eq:cbal0:svct0:snnc0:01}
1189     O_k = I_1 I_2 \ldots I_N + (O_{k-1} (I_1 + I_2 + \ldots + I_N)) .
1190     \end{equation}
1191    
1192     The form of (\ref{eq:cbal0:svct0:snnc0:01}) is intuitively
1193     plausible. If the previous output $O_{k-1}$ is 0, the only
1194     circumstance under which the next output $O_k$ will become 1
1195     is if all $N$ inputs $I_1, I_2, \ldots , I_N$ are 1.
1196     Similarly, if the previous output $O_{k-1}$ is 1, the only
1197     circumstance under which $O_k$ will become 0
1198     is if all $N$ inputs $I_1, I_2, \ldots , I_N$ are 0. This
1199     is the desired behavior.
1200    
1201     For an N/N counter when a large number of previous samples
1202     are required to be at the same value (say, $N=10$, for example),
1203     it may seem that the efficiency of the N/N vertical counter
1204     design presented here will break down. However, it must be
1205     remembered that the vertical counter approach manipulates
1206     a large number (usually 8 or 16) inputs at a time. It can be
1207     shown easily that an N/N debouncing vertical counter requires
1208     $2N$ operations to determine the next output. Thus, for a
1209     10/10 debouncing vertical counter, the necessary software
1210     may execute in as little as 20 machine instructions. It would
1211     be difficult to find another method which will perform 10/10
1212     debouncing for 8 or 16 inputs in only 20 machine instructions, thus
1213     we maintain that the N/N debouncing vertical counter
1214     approach presented is quite efficient even for larger
1215     $N$.
1216    
1217    
1218     \section{Authors And Acknowledgements}
1219     %Section tag: ACK0
1220     This chapter was primarily written by David T. Ashley
1221     \cite{bibref:i:daveashley}.
1222    
1223     We are very grateful to \index{Dattalo, Scott}Scott Dattalo
1224     \cite{bibref:i:scottdattalo},
1225     whose web pages about vertical counters provided much of the
1226     material for the Section \ref{cbal0:svct0}.
1227     Special thanks to \index{Virgil}Virgil \cite{bibref:i:virgil},
1228     \index{Dresner, Norm}Norm Dresner \cite{bibref:i:normdresner},
1229     and \index{Kaskelma, Heikki}Heikki Kaskelma \cite{bibref:i:heikkikaskelma}
1230     for mathematical assistance provided via the
1231     \index{sci.math newsgroup@\texttt{sci.math} newsgroup}%
1232     \texttt{sci.math} \cite{bibref:n:scimathnewsgroup} newsgroup.
1233    
1234    
1235     \section{Exercises}
1236    
1237    
1238     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1239    
1240     \noindent\begin{figure}[!b]
1241     \noindent\rule[-0.25in]{\textwidth}{1pt}
1242     \begin{tiny}
1243     \begin{verbatim}
1244 dashley 275 $HeadURL$
1245     $Revision$
1246     $Date$
1247     $Author$
1248 dashley 140 \end{verbatim}
1249     \end{tiny}
1250     \noindent\rule[0.25in]{\textwidth}{1pt}
1251     \end{figure}
1252    
1253 dashley 275 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1254 dashley 140 %
1255     %End of file C_BAL0.TEX

Properties

Name Value
svn:eol-style native
svn:keywords Author Date Id Revision URL Header

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25