Computer Organization & Architecture: Combination Circuit

1.0 Combinational Circuits

A logic block contains no memory and computes the output of a pure function present on input.

This type of logic circuit is a combinational logic circuit because it use the variable logical operation to combined it.

1.1 Boolean Function

A Boolean algebra is the combinations of variables and operators. Boolean function is a function which takes Boolean variables (0 or 1) as input and generates a Boolean output value.

There have two ways to represent a Boolean Function:

1. Truth table

2. Boolean Expression

1.Truth Table

- Provides a listing for every possible combination of inputs and its corresponding outputs.

- It also can have different number of inputs and outputs.

2.Boolean Expression

All Boolean equation can be represent in:

· Sum-of-product (SOP)

Ø A logical sum (OR) of several product terms.

Ø Combination of input value that produce 1s is convert into equivalent variables, ANDed together then ORed with other combination variables with the same output.

Ø SOP is easier to derive from truth table.

· Product-of-sums (POS)

Ø A logical product (AND) of several sum terms.

Ø Input combinations that produce 0 in sum terms ( ORed variables ) are ANDed together.

Ø Convert input values that produce 0s into equivalent variables, ORed that variables, then ANDed with other ORed forms.

Ø If more than 1s produce, it will use it in output function.

· Truth tables are able help in circuit for analysis and design. Every function is computed by a circuit can be specified for a truth table. This specifies of function a unique.

· Truth tables can be very complicated

Ø When n inputs, a truth table will have 2ⁿ rows.

Ø Cannot be manipulated to become a cost – effective logic circuit especially to the complicated circuits.

Ø Just for simple Boolean expressions.

· A specify of Boolean function can express the logical relationship between the binary variables. Example :

· The binary variable and logical operator is a sequence of Boolean expression.

· Binary variables only have two possible values,0 or 1.

· Logic operator is a represent a logic gate:

Ø Ā or A’ is NOT A

Ø A.B is A AND B

Ø A+B is A OR B

Ø A ⊕ B is A XOR B

Ø (A+B)’ is A NOR B

Ø (A.B)’ is A NAND B

· The way to draw a logic circuit from Bollean expression.

Ø Wiring or interconnections:

Ø We can draw the logic circuit from the output to the input based on the Boolean expression.

Ø Example:

· We also can analysis the expression based on the circuit.

· From the input of circuit to derive the Boolean expression for each nodes.Derive the expression level by level until reach the output of circuit.

Ø Example :

1.2 Simplification Of Boolean Equation

To simplify the Boolean Equation, there are two ways to solve it.

v Laws of Boolean algebra – rules to simplify Boolean equation.

v Karnaugh maps - A grid-like of representation of a truth table.

1.2.1 Laws Of Boolean Algebra

These are the basic laws of Boolean Algebra to help for simplified the logic equations.

Law	AND form	OR form
Identity Law	A.1=A	A+0=A
Zero and One Lwa	A.0=0	A+1=1
Inverse Law	A.Ā=0	A+Ā=1
Idempotent 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)
Absorption Law	A(A+B)=A	( A+A.B=A ) / (A+A'B=A+B)
De Morgan's Law	(A̅.B̅) =A̅+B̅	(A̅+B̅) =A̅.B̅
Double Complement Law	X̿ =	X

Table : Basic Laws Of Boolean Algebra

1.2.2 Karnaugh Map

- The Karnuagh Map,K-Map is given us a simple and most straight –forward method to simplified the Boolean equation. It is limitation to be ineffective for more than 4 inputs.

- K-Map also have a same concept of grid-like representation of a truth table. The row and columns for K-map is corresponding to the outcome values of the function input.

- Minterm is a set for all variables are include in the product, just either is complement or not complement.

- There have 2ⁿ distinct minterms for n variables.

Ø If there have total 2 input variable, then it will have 4 minterms

Ø If there have total 3 input variable, then it will have 8 minterms.

-If two variable (AB) join together in the K-Map, we should labelling the column in AB, A’B, AB’, A’B’as a sequence.All input values should arranged, therefore easy to make sure each of minterm differs only for one variable only.

- When we don’t know when to add extra AB or don’t have a good algebraic manipulation skills, algebraic simplification is very hard for us.However K-Maps able to help us to ovewrcome which term to add or which Boolean Law to use.From the K-Maps, we need to group 1’s.

- Specific of grouping 1’s in Karnaugh Map :

Ø Each group just contain only 1s.

Ø Only adjacent cells can be group and diagonal is no allow to group it.

Ø Number power of 2 mean 2, 4, 8, or 16 must be in the group.

Ø Size of group is no limit as long as obey the rules.

Ø All 1s must to belong in one group.

Ø Overlap and wrap around is able to happen.

Ø Fewest number of group is more encourage.

-Simplification by K-Map is grouping in a rectangle block of neighbours.

- There are two ways for grouping:

· Sum of Porduct (SOP):

Group in value of 1