22 Oct 2012

Chapter 3 :Digital Logic


POST BY : NURUL ILHAM KAMALIAH BT AHMAD         B031210353


3.2: COMBINATIONAL CIRCUITS
v  Alogic block contains no memory and computes the output given the current inputs.
v  Can be defined in three ways :
1.       Truth table
2.       Graphical symbols
3.       Boolean equations
 BOOLEAN EQUATION FORMS
v  A boolean  algebra is the combinations of variables and operators.
v  All Boolean expression can be represented in two forms:
Ø  Sum-of-products(SOP) =  Combination of input values that produce 1s is convert into
equivalentvariables,ANDed together then ORed with other
combination variable with the same output.

Example :
  •         The truth table :

F = A’B’+ ABC’D
A
B
C
D
F
0
0
0
0
1
0
0
0
1
1
0
0
1
0
1
0
0
1
1
1
0
1
0
0
0
0
1
0
1
0
0
1
1
0
0
0
1
1
1
0
1
0
0
0
0
1
0
0
1
0
1
0
1
0
0
1
0
1
1
0
1
1
0
0
0
1
1
0
1
1
1
1
1
0
0
1
1
1
1
0

          SOP expression :
          F = (A’B’C’D’) + (A’B’C’D) + (A’B’CD) + (ABC’D)


Ø 
Product-of-sum(POS) = Input combinations that produce 0s in sum terms
                                          (ORed variables) are ANDed together.
                                           Convert input values that produce 0s into equivalent variables
                                          ORed the variables,thenANDed with other ORed forms
                                          Usually use if more 1s produce in output function
EXAMPLE :
F = (A+B+C)(A+B+C’)(A+B+C’)(A’+B+C’)

A
B
C
F
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
1
1
0
0
1
1
0
1
0
1
1
0
1
1
1
1
1











POS expression :
F = (A+B+C)(A+B+C’)(A+B+C’)(A’+B+C’)



 SIMPLIFICATION OF BOOLEAN EQUATION

  •    Two ways to simplify Boolean equation,

1.       Law Of Boolean Algebra – rules to simplify expression
2.       Karnaugh Map – A grid-like representation of a truth table

 LAW OF BOOLEAN ALGEBRA

Table 3-2: Basic Laws of Boolean Algebra

AND Form
OR Form
Identity Law
A·1 = A
A + 0 = A
Zero and One Law
 A·0 = 0
A+1 = 1
Inverse Law
A·A’ = 0
A+A’ = 1
Indempotent Law
A·A = A
A+A = A
Commutative Law
A·B = B·A
A+B = B+A
Associative Law
A·(B·C) = (A·B)·C
A+(B+C) = (A+B)+C
Distributive Law
A+(B·C) = (A+B)·(A+C)
A·(B+C) = (A·B)+(A·C)
Absorbtion Law
A(A+B) = A
A+A·B = A
A+A’B = A+B
DorMorgan’s Law
(A·B)’ = A’+B’
(A+B)’ = A’·B’
Double Complement Law
                                         =
                                         X = X


 De Morgan’s Law

NOTE:
If you break the line,you change the sign.
                           (A·B)’ = A’+ B’
                            (A+B)’ = A’·B’


POST BY : NUR SYAZWAN BT ABDUL MALEK                 B031210119


3.3 Karnaugh Map (K-Map)

- K-Map provides a simple method on minimizing Boolean expressions.
- However, it will be ineffective for more than four inputs.


For n inputs, there are 2n cells needed to build the K-Map 


 Example

A
B
Minterm
0
0
A’B’
0
1
A’B
1
0
AB’
1
1
AB


A
B
A’
A
B’


B







  K-Map for two variables(A and B)




A
B
C
Minterm
0
0
0
A’B’C’
0
0
1
A’B’C
0
1
0
A’BC’
0
1
1
A’BC
1
0
0
AB’C’
1
0
1
AB’C
1
1
0
ABC’
1
1
1
ABC

BC
A
B’C’
B’C
BC
BC’
A’




A









K-Map for three variables(A,B and C)




A
B
C
D
Minterm
0
0
0
0
A’B’C’D’
0
0
0
1
A’B’C’D
0
0
1
0
A’B’CD’
0
0
1
1
A’B’CD
0
1
0
0
A’BC’D’
0
1
0
1
A’BC’D
0
1
1
0
A’BCD’
0
1
1
1
A’BCD
1
0
0
0
AB’C’D’
1
0
0
1
AB’C’D
1
0
1
0
AB’CD’
1
0
1
1
AB’CD
1
1
0
0
ABC’D’
1
1
0
1
ABC’D
1
1
1
0
ABCD’
1
1
1
1
ABCD

CD
AB
C’D’
C’D
CD
CD’
A’B’




A’B




AB




AB’











K-Map for four variables (A,B,C, and D)


A product term that includes all of the variables once, either complemented or not complemented is called a minterm.
For example,
-          If there are two inputs or variables, there are four minterms(A’B’,A’B,)
-          If there are inputs or variables,there are 8 mintermA’B’C’ , A’B’C , A’BC’ , A’BC , AB’C’ , AB’C , ABC’ and ABC.

Example

F = A+B
  •   The truth table:


A
B
A+B
A’B’
0
0
0
A’B
0
1
1
AB’
1
0
1
AB
1
1
1

  •              Karnaugh Map:


A
B
A’
A
B’
0
1
B
1
1

  •   Boolean Law:

F = A’B + AB’ + AB
  =A’B + AB + AB’ + AB                     AB + AB = AB
  =B (A’+ A) + A(B’ + B)
  =B + A
  =A + B

GROUPING 1’s IN KARNAUGH MAP
1-    The groups can ONLY contain 1s
2-     Only 1s adjacent cells can be grouped ; diagonal grouping is not allowed.
3-       The number of 1s in a group must be a power of 2,means a group can contain 2,4,8, or 16 of  1s.
4-      The groups must be  as large as possible while still following all rules.
5-      All 1s must belong to a group, even if it is a group of one
6-    Overlapping  groups are allowed.
7-     Wrap around is allowed.
8-    Use the fewest number  of groups possible.