Karnaugh Map

The Karnaugh Map

What is Karnaugh Map?

Karnaugh Map is a pictorial method of grouping together expressions with common factors and therefore eliminating unwanted variables. The Karnaugh Map can also be described as a special arrangement of a truth table.                                                                                                              -Lecture Note Chapter 5-

Untuk senang cerita, Karnaugh Map atau nama famousnya K-Map, adalah sama konsepnya dengan Truth Table. Yang membezakan kedua-duanya adalah bentuk mereka (Truth Table menggunakan jadual, K-Map menggunakan rajah).

Please note that groups may be horizontal or vertical, not diagonal.

Sekarang, mari cuba tengok contoh.

Katakan:

Solution:

The answer is:

x = BD + B'C

Key-Note of K-Map:

       ·         The groups can only contain 1.

       ·         No diagonals selections and zero(s) (0) allowed.

       ·         Must have at least two (2) number of one (1) in cells in each group.

       ·         A group must be power of two. Ex: 2, 4, 8, 16.

       ·         Overlapping and Wrap around allowed.

       ·         Fewest numbers of groups possible.

Sumber: Lecture Note Chapter 5 dan Lab Companion

Boolean Equation Forms

BOOLEAN EQUATION FORMS

      ·         Can be represented in two forms:

                                 i.     Sum-of-Products (SOP)

Ø  Combination of input values that produces one (1)

Ø  Easier to derive from truth table

A	B	C	X	Product term
0	0	0	0
0	0	1	1	A’B’C
0	1	0	0
0	1	1	0
1	0	0	1	AB’C’
1	0	1	0
1	1	0	0
1	1	1	1	ABC

SOP Expression:

X = A’B’C + AB’C’ + ABC

                               ii.     Product-of-Sums (POS)

Ø  Input combinations that produces zero (0) in sum terms

Ø  Usually use if more one (1) produce in output function

A	B	C	X	Product term
0	0	0	0	A+B+C
0	0	1	0	A+B+C’
0	1	0	0	A+B’+C
0	1	1	1
1	0	0	1
1	0	1	0	A’+B+C’
1	1	0	1
1	1	1	1

POS Expression:

                X = (A+B+C)(A+B+C’)(A+B’+C)(A’+B+C’)

(Note that the method is reversible. We can find SOP/POS expression from truth table or build the truth table from the expression.)

      ·         Two ways to simplify Boolean equation:

1.       Laws of Boolean Algebra

	AND Form	OR Form	Notes
Identity Law	A•1 = A	A+0 = A
Zero and One Law	A•0 = 0	A+1 = 1
Inverse Law	A•Ā = 0	A+Ā = 1
Idempotent Law	A•A = A	A+A = A
Communication Law	A•B = B•A	A+B = B+A
Association Law	A•(B•C) = (A•B)•C	A+(B+C) = (A+B)+C
Distribution Law	A+(B•C)=(A+B)•(A+C)	A•(B+C) = (A•B)+(A•C)	Reverse Derivation (A+B)•(A+C)=AA+AC+AB+BC→AA=A                        =A+AC+AB+BC                        =A+AB+BC                        =A(1+B)+BC                        =A•1+BC                        =A+BC
Absorption Law	A(A+B) = A	A+A•B = A A+A’B = A+B	A(A+B)=A(1+B)           →1+B=1               =A(1)              →A•1=A               =A A(A+B)=AA+AB           →A•A=A               =A+AB            →A(1+B)=A(1)               =A A+A’B=(A+AB)A’B       →A=A•A             =(AA+AB)+A’B             =AA+AB+A’B             =(A+A’)(A+B)             =1•(A+B)           →A+A’=1             =(A+B)
DeMorgan’s Law	(A•B)’ = A’+B’	(A+B)’ = A’•B’	If you break the line, change the sign.
Double Complement Law	X” = X

2.       Karnaugh Map

Binary Number Operation

Ridzuan -

DIGITAL LOGIC - COMBINATION CIRCUIT(2'S COMPLEMENT NUMBER OPERATION )

2'S COMPLEMENT NUMBER OPERATION 

Definition of one’s complement

• The ones' complement of a binary number is defined as the value obtained by inverting all the bits in the binary representation of the number (swapping 0's for 1's and vice-versa).

• In this form, a negative number is the 1’s complement of the corresponding positive number.

• The 1’s complement of a binary number is found by changing all 1s to 0s and all 0s to 1s as shown below:

+28₁₀ = 00011100₂

-28₁₀ = 11100011₂ (1’s complement of +25)

Definition of two’s complement

• Two's complement is a mathematical operation on binary numbers, as well as a representation of signed binary numbers based on this operation. The two's complement of an N-bit number is defined as the complement with respect to 2^N, in other words the result of subtracting the number from 2^N

•  The 2’s complement of a binary number can be obtained by adding 1 to one’s complement:

2’s complement = (1’s complement) + 1

Example:

• The negative (-) decimal number conversion is done in next steps .Lets we convert -118.

1. Separate the sign and magnitude number of -1 .If the sign bits is 1, its represent      as  negative sign in the 2s complement conversion.

2. Convert the decimal number to its 7-bits binary equivalent.

Decimal	8-bits binary number			Note
	sign	Magnitude
118	0	1110110	Convert to 7-bits binary
		0001001	1stcomplement	Each 0 is changed to 1 and each 1 to 0.
		0001010	2nd

Another Example:

Express the decimal number -55 as an 8-bit in the sign-magnitude, 1’s complement, and 2’s complement forms.

SOLUTION:

8-bit number for + 55₁₀ = 00110111₂

Sign-magnitude form for -55₁₀ = 10110111₂

•  Change the sign bit to a 1 and leave the magnitude bits as they are 1’s complement form for -55₁₀ = 11001000₂

• Take the 1’s complement of +55 by changing all 1’s to 0s and 0s to 1s

2’s complement form for -55_{10 =}

          11001000    1's complement

+                       1                        

           11001001    2's complement

2’s Complement Operations

• Two Positive Numbers

    1410                              000011102

+  2510          -------->     +    000110012

    3910                               001001112  

Positive Number and Smaller Negative Number

    

                2910  

           -    1510

SOLUTION:

1. Find the binary numbers for 2910
            2910        =     000111012

2. Find the binary form for -1510 using 2's complement
            -1510      =     111100012
3. Add the binary numbers

                                             000111012
                                       +   111 100012
                                            1000011102
                                                          |           
                                    |
                                    |
                            Discard carry over

Positive Number and Larger Negative Number

               1210

        -      2510

 

Tasks:

1. Find the binary form for 12₁₀

2. Find the binary form for −25₁₀ using 2’s complement

3. Add the binary numbers

Solution:

1 :+122   -------->  000011002

2 : 

             +2510    ------>   000110012

             -2510     ------>  111001102

                                  +             1  

                                    111001112

3 :

           1210                              000011002

     +( -2510)         -------->   +  111001102

                                                                            111100112= -1310

Check the answer using  2's complement

       111100112     -------->        000011002

                                               +               1  

                                                  000011012 = +1310