Digital Systems (II)

This deals with reduction of boolean functions. Lets start with,
One Bit Binary Adder:
Input: A,B,Cin(carry)
Output: S,Cout
Truth Table:
(A,B,Cin,S,Cout) (0,0,0,0,0)(0,0,1,1,0)(0,1,0,1,0)(0,1,1,0,1)(1,0,0,1,0)(1,0,1,0,1)(1,1,0,0,1)(1,1,1,1,1)

Sum of Products representation:
S=A'B'Cin+A'BCin'+AB'Cin'+ABCin = (After Reduction) A XOR B XOR C
Cout=ABCin'+AB'Cin+A'BCin+ABCin = (After Reduction) Cin(A+B)+AB

Canonical Form Representation:

• Sum Of Products(Min) Terms
• Min Terms - ANDed product of literals (input combination for which output is true)
• Representation: [(0,0,0)(a'b'c') m0],[(0,0,1)(a'b'c) m1],[(0,1,0)(a'bc') m2] .....
  
• Product of Sum (Max) Terms
• Max Terms - ORed sum of literals (input combination for which output is false)
• Representation: [(o,o,o)(a+b+c)M0],[(o,o,1)(a+b+c')M1],[(o,1,o)(a+b'+c)M2], ...

Thus Expressing the 'S' in Canonical (not same as reduced or minimal form)
SOP: S = SUM(1,2,4,7) = m1+m2+m4+m7
POS: S = PROD(0,3,5,6) = M0.M3.M5.M7 = (A+B+Cin)(A'+B'+Cin)(A'+B+Cin')(A+B'+Cin')

Conversions:

• SOP to POS:
• F(a,b,c) = SUM(1,2,4,7) = PROD(0,3,5,6)
• POS to SUM:
• F(a,b,c) = PROD(1,4,7) = SUM(0,2,3,4,6)
• F SOP to F' POS (switch SUM and PROD)
  
• F(a,b,c) = SUM(1,2,3,4) = PROD(0,5,6,7)
• F'(a,b,c) = PROD(1,2,3,4) = SUM(0,5,6,7)
• F POS to F' SOP (switch SUM and PROD)
  
• F(a,b,c) = PROD(1,2,3,4) = SUM(0,5,6,7)
• F'(a,b,c) = SUM(1,2,3,4) = PROD(0,5,6,7)
• Observe that it is same as previous just switch F and F'

Uniting Theorem: This theorem is the basis of Boolean logic reduction.

• Basis: A(B+B') = A
• Find two element sub-sets of the ON-set where only one variable changes its value - this single varying variable can be eliminated and a single product term used to represent both elements
• Usually visual techniques are used to identify these element sub-sets

Boolean Cubes:
One way to visualize a boolean logic is to assume the logic to be a cube. 'One' input is a line, 'two' input a square, 'three' input a cube ... and n inputs corresponds to a n dimensional cube.
Every corner of the cube is assumed to be a adjacency plane. Each adjacency plane corresponds to a product term. Adjacency planes for which the output is ON is made bold. ON-set adjacencies are combined to form ON Sets and these sets form sub-cubes
Implication of a sub-cube in 3d cube,

• 0-cube i.e a single node represents a product term in three literals
• 1-cube i.e a line of two nodes represents a product term in two literals
• 2-cube i.e a square of four nodes represents a product term in one literals
• 3-cube i.e a cube of eight nodes represents a CONSTANT output
• In general, in a 'n' dimensional cube, a 'm' sub-cube yields a term with n-m literals
  

K (or Karnaugh) Maps:
Representing the logic in rectangular boxes, where each box in the rectangle represents a min term. The boxes are arranged in such way that the neighboring boxes vary in one variable. So the numbering system used for these rectangular boxes is based on Grey Codes.

Certain systems have don't care conditions in which case, they can be used as either '1' or '0' to the advantage to reduce the logic.

Certain systems have lesser number of literals in POS than in SOP form, like
SOP: F(A,B,C,D) = C'D+A'D
POS: F(A,B,C,D) = D(A'+C')