数字逻辑chapter4_b

Canonical Sum Representation Minterm number: An n-variable minterm can be represented by an n-bit integer--the minterm number. We use the name minterm i to denote the minterm corresponding to row i of the truth table. For n-variables i is in the set {0,1, …, 2n-1}

The canonical sum of a logic function is a sum of the minterms corresponding to the truth table rows for which the function produces a 1 output. A short-hand representation of the minterm list uses the S notation and minterm numbers to indicate the sum of minterms of the function. F = S X,Y,Z (0, 3, 4, 6, 7) This representation is usually realized using 2-level AND-OR logic circuits with inverters at AND gates inputs as needed.

Canonical Sum Example The function represented by the truth table:Row X Y Z 0 0 0 0 1 0 0 1 2 0 1 0 3 0 1 1 4 1 0 0 5 1 0 1 6 1 1 0 7 1 1 1 F 1 0 0 1 1 0 1 1

has the canonical sum representation:Short hand F = S X,Y,Z (0, 3, 4, 6, 7) = X Y Z + X Y Z + X Y Z + X Y Z + X Y Z Algebraic canonical sum of minterms

4.2 Combinational-Circuit Analysis Combinational logic circuits:Types of Logic Circuits

– Outputs depend only on its current inputs. – A combinational circuit may contain an arbitrary number of logic gates and inverters but no feedback loops. A feedback loop is a connection from the output of one gate to propagate back into the input of that same gate – The function of a combinational circuit represented by a logic diagram is formally described using logic expressions and truth tables.

Sequential logic circuits:– Outputs depend not only on the current inputs but also on the past sequences of inputs. – Sequential logic circuits contain combinational logic in addition to memory elements formed with feedback loops. – The behavior of sequential circuits is formally described with state transition tables and diagrams.

Sequential Circuits The general structure of a sequential Circuit:Combinational logic + Memory ElementsCombinational outputs

Memory outputs

Combinational logic

Memory elements

External inputs

Memory element: a device that can remember value indefinitely, or change value on command from its inputs. Examples: flip-flops

Combinational Circuit Analysis Start with a logic diagram of the circuit. Proceed to a formal description of the function of the circuit using truth tables or logic expressions.

Analysing Logic Circuits When a logic circuit is provided, we can analyse the circuit to obtain the logic expression. Example: What is the Boolean expression of F4?A' B' C A'B' A'B'+C (A'B'+C)' F4

F4 = (A'B'+C)'

Analysing Logic Circuit Example: What is Boolean expression of F5?

x y z F5

F5 =

XY+YZ

Combinational Circuit Analysis ExampleGiven this logic circuit we can : Create truth table by applying all input combinations: From truth table find Canonical Sum Representations Find corresponding logic express

ion from circuit Manipulate logic expression to other forms using theorems.X 00001111 Y00110011 00001111

Truth TableRow 0 1 2 3 4 5 6 7 X 0 0 0 0 1 1 1 1 Y 0 0 1 1 0 0 1 1 Z 0 1 0 1 0 1 0 1 F 0 1 1 0 0 1 0 1

X+Y 11001111

11001100

Y Z01010101

(X+Y ) · Z01000101

From truth table: Canonical Sum F = S X,Y,Z (1, 2, 5,7)

Z 01010101 X

01100101 11110000

F

Y 00110011

Z 10101010corresponding logic expression:

X · Y · Z F = ((X + Y ) ·Z) + (X · Y · Z )

00100000

Combinational Circuit Analysis Example(continued) The previous circuit logic expression F can be transformed into sum of products by multiplying out and written as :

F = X · Z + Y · Z + X ·Y· Z Realized using a 2-level AND-OR circuit:

Combinational Circuit Analysis Example(continued) Similarly, we can “add out” the original expression to obtain a product of sums :

Realized using a 2-level OR-AND circuit:

4.3 Combinational Circuit Synthesis May start with an informal (possibly verbal) description of the function performed. A formal description of the circuit function in terms of a truth table or logic expression. The logic expression is manipulated using Boolean (or switching) algebra and optimized to minimize the number of gates needed, or to use specific type of gates. A logic diagram is generated based on the resulting logic expression.

4.3.1 Circuit Description and DesignsCombinational Circuit Synthesis Example(1) An example of a combinational circuit description: “4-bit prime-number detector” “Given a 4-bit input combination N=N3N2N1N0, this function produces a 1 output for N = 1, 2, 3, 5, 7, 11, 13, and 0 otherwise.” The logic function can be designed directly from the canonical sum expression : F = S N3N2N1N0 (1,2,3,5,7,11,13) = N3 N2 N1 N0+ N3 N2 N1N0 + N3 N2 N1N0 +N3 N2N1 N +N3 N2N1N0+ N3N2 N1N0+ N3N2N1 N0

Combinational Circuit Synthesis Example(1)(continued)

A Verbal Synthesis Example(2)An Alarm Circuit A verbal logic description:– The ALARM output is 1 if the panic input is 1, or if the ENABLE input is 1, the EXITING input is 0, and the house is not secure. – The house is secure if the WINDOW, DOOR, GARAGE inputs are all 1

This can be put in logic expressions as follows:ALARM = PANIC + ENABLE · EXITING · SECURE SECURE = WINDOW· DOOR· GARAGE ALARM = PANIC + ENABLE · EXITING · (WINDOW · DOOR · GARAGE)

A Verbal Synthesis Example(2)(continued)In sum of products form as (by using DeMorgan T13 and multiplying out) :ALARM = PANIC + ENABLE· EXITING · WINDOW + ENABLE · EXITING · DOOR + ENABLE· EXITING · GARAGE

4.3.2 Circuit Manipulations NAND and NOR gates are faster than ANDs and Ors in most technologies. We need ways to translate a “natural” logic expression into other forms - AND-OR =>NAND-NAND - OR-AND => NOR-NOR

NAND-NAND Logic Circuits for Sum of Products A sum

of products logic expression can be realized by NAND gates by replacing all AND gates and the OR gate in the usual realization with NAND gates as follows: F = A + B + C + D ...where A, B, C, …. are product terms of the input variables e.g. A= x· z y· F = (A ) +(B ) +(C ) +(D ) + …. from T4 = (A ·B ·C ·D … ) (from DeMorgan s theorem T13)

This is a 2-level NAND-NAND representation.

Alternate Sum of Products Realizations(Applying DeMorgan s theorem T13 Graphically)

AND-OR

NAND-NANDNAND SymbolsNormal Symbol

Alternate NAND Symbol

X(X · Y) YAccording to DeMorgan s theorem T13:

X Y(X · Y) = X + Y

X + Y

NAND-NAND Sum of Products Example The sum of products expression F = X · Z + Y · Z + X ·Y· Z = ((X · Z) ) + ((Y · Z) ) + ((X ·Y· Z ) ) double negate T4 = [(X · Z) · (Y · Z) · (X ·Y·Z ) ] DeMorgan s theorem T13 Can be realized using the 2-level NAND-NAND circuit:X

(X · Z)

Y

Y

F = [(X · Z) · (Y · Z) · (X ·Y· Z ) ]

(Y · Z)

X (X · Y · Z )

Z

Z

4.3.3 Combinational Circuit Minimization Canonical sum and product logic expressions do not provide a circuit realization with the minimum number of gates. Minimization methods reduce the cost of two level AND-OR, NAND-NAND, OR-AND, NOR-NOR circuits in three ways: 1 By minimizing the number of first level gates 2 By minimizing the number of inputs on each first-level gate. 3 Minimizing the inputs on the second level gate

Most minimization methods are based on the combining theorems T10, T10 :X·Y +X·Y = X (X+Y) ·(X+ Y ) =X

Example

“4-bit prime-number detector”

has three fewer gates and one of the remaining gates has two fewer inputs How to get the simplest diagram?