Rumination # 4: Quine Mcluskey Method

Greetings grasshoppers. As we all gear up for spring break, I would like to raise awareness about a key issue in our society today, the Quine Mcluskey method for reducing Boolean functions.


• Advantages over K-maps
– Can be computerized
– Can handle functions of more than six variables

• Overview of the method
– Given the minterms of a function
– Find all prime implicants (steps 1 and 2)

• Partition minterms into groups according to the number of 1’s

• Exhaustively search for prime implicants
– Find a minimum prime implicant cover (steps 3 and 4)

• Construct a prime implicant chart

• Select the minimum number of prime implicant


f(A,B,C,D) = m(2,4,6,8,9,10,12,13,15)

http://moodle.ucs.louisiana.edu/file.php/12393/chapter_3SP12.pdf

The Resulting Minimal Realization of f

f(A,B,C,D) = PI1 + PI3 + PI4 + PI7

      = 1-0- + -010 + 01-0 + 11-1

      = AC' + B' CD' + A' BD' + ABD

Covering Procedure

Step 1 -- Identify any minterms covered by only one PI.  

Select these PIs for the cover.

Step 2 -- Remove rows covered by the PIs identified in step 1.  

Remove minterms covered by the removed rows.

Step 3 -- If a cyclic chart results from step 2, go to step 5.  

Otherwise, apply the reduction procedure of steps 1 and 2.

Step 4 -- If a cyclic chart results from step 3, go to step 5.  

Otherwise return to step 1.

Step 5 -- Apply the cyclic chart procedure.  Repeat step 5 

until a void chart or noncyclic chart chart is produced.  In 

the latter case, return to step 1

Using the Q-M Procedure with Incompletely 

Specified Functions

1.  Use minterms and don’t cares when generating 

prime implicants

2.  Use only minterms when finding a minimal cover

Minimizing Circuits with Multiple Outputs

1. To each minterm we must affix a flag to identify

the function in which it appears.

2. Two terms or minterms can be combined only if

they both possess one or more common flags and

the term that results from the combination carries

only flags that are common to both minterms.

3. Each term in the minimizing table cab be checked

off only if all the flags that the term possesses

appear in the term resulting from the combination

So there you have it. Simple as pie. Think about that while staking out the Easter bunny.

All images courtesy of http://moodle.ucs.louisiana.edu/file.php/12393/chapter_3SP12.pdf

Rumination # 3 Karnaugh Maps

Hello my fellow seekers of the Boolean light. Tonight's post will be about one of two main methods of simplifying functions, the Karnaugh map. Simplifying a function has the advantage of minimizing costs and the number of gates neccesary for realization of a circuit, these methods will also probably figure predominantly in your tests that might be coming up soon, so without further avail, here they are:

-Karnaugh Map:

http://www.google.com/imgres?hl=en&sa=X&biw=1680&bih=925&tbm=isch&prmd=imvnsab&tbnid=gBrasygvvTvOvM:&imgrefurl=http://www.ee.surrey.ac.uk/Projects/Labview/minimisation/nak.html&docid=Fix7J9LtJAWa4M&imgurl=http://ww 

An n-variable K-map has 2^n cells with each cell corresponding to a
row of an n-variable truth table. They are labeled with the corresponding truth-table row. K-map cells are arranged such that adjacent cells correspond to truth rows that differ in only one bit position (logical adjacency).  Switching functions are mapped (or plotted) by placing the function’s
value (0,1,d) in each cell of the map.


-Simplifying using a K-map:

http://www.tech-faq.com/karnaugh-map.html 

K-map cells that are physically adjacent are also logically adjacent.  Also, cells on an edge of a K-map are logically adjacent to cells on the opposite edge of the map. If two logically adjacent cells both contain logical 1s, the two cells can be combined to eliminate the variable that has value 1 in one cell’s label and value 0 in the other. This is equivalent to the algebraic operation, aP + a'P =P where P is a product term not containing a or a'

-Simplification Guidelines for using K-maps:


 •Each cell of an n-variable K-map has n logically adjacent cells. Cells may be combined in groups of 2,4,8,…,2^k
• A group of cells can be combined only if all cells in the
group have the same value for some set of variables.
• Always combine as many cells in a group as possible.
This will result in the fewest number of literals in the term
that represents the group.
• Make as few groupings as possible to cover all minterms.
This will result in the fewest product terms.
• Always begin with the “loneliest” cells.


-General Terminology
• An implicant is a product term that can cover minterms of a
function.
• A prime implicant is a product term that is not covered by
another implicant of the function.
• An essential prime implicant is a prime implicant that covers
at least one minterm that is not covered by any other prime
implicant.
• A set of implicants is said to be a cover of a function if each
minterm of the function is covered by at least one implicant
in the set.
• A minimal cover is a cover that contains the smallest number
of prime implicants and the smallest number of literals


-Sample simplification.

http://moodle.ucs.louisiana.edu/file.php/12393/chapter_3SP12.pdf 

5  Minterms: {A'B' C, A' BC', A' BC, ABC', ABC}
5  Groups of two minterms:  {A'B, AB, A' C, BC', BC}
1  Group of four minterms:  {B}
Prime implicants:  {A'C, B}
Cover = {A' C, B}
MSOP (Minimum Sum Of Products)  = A' C B


As you can see, this is very simple to do, and with a few problems of practice, you will have no trouble simplifying functions using this method. Tune in next week for the Quine Mckluskey Method of simplification!!

Rumination #2: The Postulates and Theorems

Hello Readers.
I will begin the journey to Boolean enlightenment with the fundamental postulates of Boolean algebra.
For all the following, the variables (a,b,c...) will have two possible values of either 1 (true) or 0 (false) represented as such : a = 1 , a' = 0.

• Basic Postulates:
• Postulate 1 (Definition): A Boolean algebra is a closed algebraic system
containing a set K of two or more elements and the two operators . and +.
• Postulate 2 (Existence of 1 and 0 element):
(a) a + 0 = a (identity for +), (b) a .1 = a (identity for .)
• Postulate 3 (Commutativity):
(a) a + b = b + a, (b) a .b = b .a
• Postulate 4 (Associativity):
(a) a + (b + c) = (a + b) + c (b) a. (b.c) = (a.b) .c
• Postulate 5 (Distributivity):
(a) a + (b.c) = (a + b) .(a + c) (b) a. (b + c) = a.b + a.c
• Postulate 6 (Existence of Complement):
(a) a + a' = 1       (b) a.a' = 0
Usually the '.' sign is ommited.



FUNDAMENTAL THEOREMS OF BOOLEAN ALGEBRA:

• Theorem 1 (Idempotency): (a) a + a = a                (b) aa =  a
• Theorem 2 (Null Element):  (a) a + 1 = 1               (b) a0 = 0
• Theorem 3 (Involution): a'' = a
• Theorem 4 (Absorption):    (a) a + ab = a                       (b)  a (a + b) = a    
• Theorem 5:                        (a) a + a'b = a+b                   (b) a (a' + b) = ab 
• Theorem 6:                        (a) ab + ab' = a                     (b) (a + b)(a + b') = a
• Theorem 7:                        (a) ab + ab'c = ab + ac          (b) (a + b)(a + b' + c)= (a + b)(a + c)
• Theorem 8 (Demorgan's Theorem):                                                                                                                                                                                                            (a)(a + b)' = a'b'                (b) (ab)' = a' + b'   
• Theorem 9(Consensus):     (a) ab + a'c + bc = ab + a'c   (b) (a + b)(a' + c)(b + c)= (a + b)(a + c)

This is all pretty basic logic (1+0 = 1 and 1.0 = 0), applicable to general algebraic thinking.  If  1 is substituted for all the normal letters and 0 for all the 'complemented' letters (a' , b' , c'), you will find that these theorems are in fact very simple. They are powerful tools for simplifying very seemingly complex functions and circuits and any aspiring EECE student would be wise to memorize these.

Boolean introduction.

Hello, my name is Shadi Khansa. I am an Electrical engineering student and this is my Blog!! Chances are you may be wondering what on earth my blogs title is referring to, or chances are you know and despise what I'm referring to, but were googling for homework solutions to one of your computer engineering classes and found this by accident. Either way, I'll explain. Boolean algebra(or logic) is a logical calculus of truth values developed by English philosopher and mathematician George Boole in the 1840s. It is the algebra of two values, usually taken to be 0 and 1, but F and T, false and True, x and y, or any domain of two values could be used. Since practically every modern computer operates by using the Binary numeral system, which represents all data using two symbols (0 and 1), Boolean algebra is the basis of modern digital computer logic and George Boole is regarded as a founder in the field of computer science. 

The reason this is all so interesting to me, is that I am taking a Computer Engineering class in which I will be using George Boole's brain child extensively, so I will be documenting and explaining what I learn in this blog, in the hopes that somebody will find it useful. To kick things off,  I have included a diagram of various representations of Boolean operations, to be demystified in my next post. And the journey begins....

Rumination # 1

Food & Wine magazine reported that in Japan, squid is the most popular topping for Domino’s pizza.

In binary, that says:

01000110 01101111 01101111 01100100 00100000 00100110 00100000 01010111 01101001 01101110 01100101 00100000 01101101 01100001 01100111 01100001 01111010 01101001 01101110 01100101 00100000 01110010 01100101 01110000 01101111 01110010 01110100 01100101 01100100 00100000 01110100 01101000 01100001 01110100 00100000 01101001 01101110 00100000 01001010 01100001 01110000 01100001 01101110 00101100 00100000 01110011 01110001 01110101 01101001 01100100 00100000 01101001 01110011 00100000 01110100 01101000 01100101 00100000 01101101 01101111 01110011 01110100 00100000 01110000 01101111 01110000 01110101 01101100 01100001 01110010 00100000 01110100 01101111 01110000 01110000 01101001 01101110 01100111 00100000 01100110 01101111 01110010 00100000 01000100 01101111 01101101 01101001 01101110 01101111 00011001 01110011 00100000 01110000 01101001 01111010 01111010 01100001 00101110