Chapter3

Combinational Logic Sukree Sinthupinyo Department of Computer Science Thammasat University

Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 1/49

Basic Structure ● Basic Structure ● Well-Formed (WF) circuits ● Well-Formed (WF) circuits: Example ● Well-Formed (WF) circuits: Proof ● Non-WF Circuits Minterms

Basic Structure

Maxterms Decimal Notation Complete Gate Sets Wired Logic Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 2/49

Basic Structure

Basic Structure

■

● Basic Structure ● Well-Formed (WF) circuits ● Well-Formed (WF) circuits: Example ● Well-Formed (WF) circuits: Proof ● Non-WF Circuits

■

Combination means that the output changes instantly in response to input changes; in other words, the circuit has no memory.

Minterms Maxterms Decimal Notation Complete Gate Sets Wired Logic Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 3/49

Well-Formed (WF) circuits

Basic Structure

■

● Basic Structure ● Well-Formed (WF) circuits ● Well-Formed (WF) circuits: Example ● Well-Formed (WF) circuits: Proof ● Non-WF Circuits Minterms Maxterms Decimal Notation Complete Gate Sets Wired Logic Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

Certain rules define well-formed or WF combinational circuits ◆ A single line (wire) or gate with constant or variable (binary) primary input signals is WF. ◆ A circuit formed by the juxtaposition of two disjoint WF circuit C1 and C2 -that is, by placing C1 and C2 side by side-is WF. ◆ Let C1 and C2 be disjoint (disconnected) WF circuits. A circuit obtained by connecting an output line of C1 to an input line of C2 or to a new primary output is WF. ◆ If C is WF, the circuit obtained by connecting two primary inputs of C to form a single primary input is WF.

Logic Elements - p. 4/49

Well-Formed (WF) circuits: Example

Basic Structure ● Basic Structure ● Well-Formed (WF) circuits ● Well-Formed (WF) circuits: Example ● Well-Formed (WF) circuits: Proof ● Non-WF Circuits

a b

z2=ac+bc+abc c

Minterms Maxterms

z1=ac+bc

z3=abc+d d

Decimal Notation Complete Gate Sets Wired Logic Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 5/49

Well-Formed (WF) circuits: Proof

Basic Structure ● Basic Structure

z1

z1

z2

z2

z3

z3

● Well-Formed (WF) circuits ● Well-Formed (WF) circuits: Example ● Well-Formed (WF) circuits: Proof ● Non-WF Circuits Minterms Maxterms Decimal Notation Complete Gate Sets Wired Logic

z1

Programmable Circuits

z2

z3

Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 6/49

Non-WF Circuits

Basic Structure

■

● Basic Structure ● Well-Formed (WF) circuits ● Well-Formed (WF) circuits: Example ● Well-Formed (WF) circuits: Proof ● Non-WF Circuits

■

Minterms Maxterms Decimal Notation

The outputs of two gates shown below (left) are connected or tied together to form a structure that is not WF. The right figure shows an example of feedback circuits. ◆ Suppose that y = 0 with a = 0 and b = 1 as shown. ◆ The AND gate requires z = 0. The NOR gate has 0s on both of its inputs, which implies that y should be 1. ◆ But if y = 1, then z = 1.

Complete Gate Sets Wired Logic

1 y

Programmable Circuits

0

Sukree Sinthupinyo, December 18, 2006

a= 0

z

b=1

Logic Elements - p. 7/49

Basic Structure Minterms ● Minterms ● Minterms:Example of truth table ● Minterms ● Sum-of-Minterms ● Sum-of-Minterms: Example

Minterms

● Sum-of-Minterms: Example ● Sum-of-Minterms: Example (con) ● Sum-of-Minterms: Example (con) ● Sum-of-Minterms: Example ● Expression-Circuit Correspondence ● Sum-of-minterms form of

x1 ⊕ x2 ⊕ x3 Maxterms Decimal Notation Complete Gate Sets Wired Logic Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 8/49

Minterms

Basic Structure

■

Minterms ● Minterms ● Minterms:Example of truth table ● Minterms ● Sum-of-Minterms

■

● Sum-of-Minterms: Example ● Sum-of-Minterms: Example ● Sum-of-Minterms: Example (con) ● Sum-of-Minterms: Example (con) ● Sum-of-Minterms: Example

To identify structures that are canonical or universal (in the sense that every function can be realized using these particular structures) Let mi (x1 , x2 , . . . , xn ) = mi (X) denote the n-variable function whose truth table has 1 in row i and 0 everywhere else, where 0 ≤ i ≤ 2n − 1. The function mi is called the ith minterm function, or simply the ith minterm.

● Expression-Circuit Correspondence ● Sum-of-minterms form of

x1 ⊕ x2 ⊕ x3 Maxterms Decimal Notation Complete Gate Sets Wired Logic Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 9/49

Minterms:Example of truth table

Basic Structure Minterms ● Minterms ● Minterms:Example of truth table ● Minterms ● Sum-of-Minterms ● Sum-of-Minterms: Example ● Sum-of-Minterms: Example ● Sum-of-Minterms: Example (con) ● Sum-of-Minterms: Example (con) ● Sum-of-Minterms: Example ● Expression-Circuit Correspondence ● Sum-of-minterms form of

x1 ⊕ x2 ⊕ x3 Maxterms Decimal Notation

0 1 2 3 4 5 6 7

Inputs x1 x2 0 0 0 0 0 1 0 1 1 0 1 0 1 1 1 1

x3 0 1 0 1 0 1 0 1

m0 1 0 0 0 0 0 0 0

m1 0 1 0 0 0 0 0 0

m2 0 0 1 0 0 0 0 0

Minterms m3 m4 m5 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0

m6 0 0 0 0 0 0 1 0

m7 0 0 0 0 0 0 0 1

Complete Gate Sets Wired Logic Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 10/49

Minterms

● Sum-of-Minterms: Example

If index i has the binary representation (bi,1 bi,2 · · · bi,n )2 then the AND gate that realizes mi has input xj inverted if and only if bit bi,j = 0 For instance, if i = 1210 = 11002 , then m12 (x1 , x2 , x3 , x4 ) is realized by an AND gate with inputs x3 and x4 . Hence:

● Sum-of-Minterms: Example (con) ● Sum-of-Minterms: Example

m12 (x1 , x2 , x3 , x4 ) = x1 x2 x¯3 x¯4

Basic Structure

■

Minterms ● Minterms ● Minterms:Example of truth table ● Minterms ● Sum-of-Minterms

■

● Sum-of-Minterms: Example

(con) ● Sum-of-Minterms: Example ● Expression-Circuit Correspondence ● Sum-of-minterms form of

x1 ⊕ x2 ⊕ x3 Maxterms Decimal Notation Complete Gate Sets Wired Logic Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 11/49

Sum-of-Minterms

Basic Structure

■

Minterms ● Minterms ● Minterms:Example of truth table ● Minterms ● Sum-of-Minterms ● Sum-of-Minterms: Example ● Sum-of-Minterms: Example ● Sum-of-Minterms: Example (con) ● Sum-of-Minterms: Example

Consider a general n-variable function f (X) whose truth table has 1s in rows a, b, . . . , k and 0s everywhere else. It is apparent from the definitions of minterm and the OR function that f (X) can be written in the following sum-of-minterms form f (X) = ma (X) + mb (X) + · · · + mk (X)

(con) ● Sum-of-Minterms: Example ● Expression-Circuit Correspondence ● Sum-of-minterms form of

x1 ⊕ x2 ⊕ x3 Maxterms Decimal Notation Complete Gate Sets Wired Logic Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 12/49

Sum-of-Minterms: Example

Basic Structure

■

Minterms ● Minterms ● Minterms:Example of truth table ● Minterms

It’s better to view this figure again. a b

z2=ac+bc+abc

● Sum-of-Minterms ● Sum-of-Minterms: Example ● Sum-of-Minterms: Example

c

● Sum-of-Minterms: Example (con) ● Sum-of-Minterms: Example (con) ● Sum-of-Minterms: Example

z1=ac+bc

z3=abc+d d

● Expression-Circuit Correspondence ● Sum-of-minterms form of

x1 ⊕ x2 ⊕ x3 Maxterms Decimal Notation Complete Gate Sets Wired Logic Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 13/49

Sum-of-Minterms: Example

Basic Structure Minterms ● Minterms ● Minterms:Example of truth table ● Minterms ● Sum-of-Minterms ● Sum-of-Minterms: Example ● Sum-of-Minterms: Example ● Sum-of-Minterms: Example (con) ● Sum-of-Minterms: Example (con) ● Sum-of-Minterms: Example ● Expression-Circuit Correspondence ● Sum-of-minterms form of

x1 ⊕ x2 ⊕ x3 Maxterms Decimal Notation

a 0 0 0 0 0 0 0 0

Inputs b c 0 0 0 0 0 1 0 1 1 0 1 0 1 1 1 1

d 0 1 0 1 0 1 0 1

Outputs z1 z2 z3 0 1 1 0 1 1 0 0 1 0 0 0 0 0 1 0 0 0 1 1 1 1 1 0

Complete Gate Sets Wired Logic Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 14/49

Sum-of-Minterms: Example (con)

Basic Structure Minterms ● Minterms ● Minterms:Example of truth table ● Minterms ● Sum-of-Minterms ● Sum-of-Minterms: Example ● Sum-of-Minterms: Example ● Sum-of-Minterms: Example (con) ● Sum-of-Minterms: Example (con) ● Sum-of-Minterms: Example ● Expression-Circuit Correspondence ● Sum-of-minterms form of

x1 ⊕ x2 ⊕ x3 Maxterms Decimal Notation

a 1 1 1 1 1 1 1 1

Inputs b c 0 0 0 0 0 1 0 1 1 0 1 0 1 1 1 1

d 0 1 0 1 0 1 0 1

Outputs z1 z2 z3 0 0 1 0 0 0 1 1 1 1 1 0 0 0 1 0 0 0 1 1 1 1 1 0

Complete Gate Sets Wired Logic Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 15/49

Sum-of-Minterms: Example (con)

Basic Structure

■

Minterms ● Minterms ● Minterms:Example of truth table ● Minterms ● Sum-of-Minterms ● Sum-of-Minterms: Example ● Sum-of-Minterms: Example ● Sum-of-Minterms: Example (con) ● Sum-of-Minterms: Example

The sum-of-minterms expressions for the three functions can be written directly from the table:

z1 = a ¯bcd¯ + a ¯bcd + a¯bcd¯ + a¯bcd + abcd¯ + abcd z2 = a ¯¯b¯ cd¯ + a ¯¯b¯ cd + a ¯bcd¯ + a ¯bcd + a¯bcd¯ + a¯bcd + abcd¯ + abcd z3 = a ¯¯b¯ cd¯ + a ¯¯b¯ cd + a ¯¯bcd¯ + a ¯b¯ cd¯ + a ¯bcd¯ + a¯b¯ cd¯ + a¯bcd¯ + ab¯ cd¯ + abcd¯

(con) ● Sum-of-Minterms: Example ● Expression-Circuit Correspondence ● Sum-of-minterms form of

x1 ⊕ x2 ⊕ x3 Maxterms Decimal Notation Complete Gate Sets Wired Logic Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 16/49

Sum-of-Minterms: Example

a

Basic Structure

z1=ac+bc

b z2=ac+bc+abc

Minterms

c

● Minterms ● Minterms:Example of truth

z3=abc+d

table ● Minterms

d

● Sum-of-Minterms ● Sum-of-Minterms: Example ● Sum-of-Minterms: Example ● Sum-of-Minterms: Example (con) ● Sum-of-Minterms: Example (con) ● Sum-of-Minterms: Example

■

■

● Expression-Circuit Correspondence ● Sum-of-minterms form of

However, the function z2 is in the figure is defined as: z2 = ac + bc + a ¯¯b¯ c We can find sum-of-minterms by ANDing the factor (a + a ¯), ¯ so we have: (b + ¯b), (c + c¯), or (d + d), ¯ + (a + a ¯ +a ¯ z2 = a(b + ¯b)c(d + d) ¯)bc(d + d) ¯¯b¯ c(d + d)

x1 ⊕ x2 ⊕ x3 Maxterms Decimal Notation

■

Complete Gate Sets

Finally, we will get: z2 = a ¯¯b¯ cd¯ + a ¯¯b¯ cd + a ¯bcd¯ + a ¯bcd + a¯bcd¯ + a¯bcd + abcd¯ + abcd

Wired Logic Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 17/49

Expression-Circuit Correspondence

Basic Structure

■

Minterms ● Minterms ● Minterms:Example of truth table ● Minterms

■

● Sum-of-Minterms ● Sum-of-Minterms: Example ● Sum-of-Minterms: Example ● Sum-of-Minterms: Example (con) ● Sum-of-Minterms: Example

We can translate the sum-of-minterms expression for z into an equally combinational circuit Nz that realizes z. Each of k minterms of z(x1 , x2 , . . . , xn ) is implemented by an n-input AND gate, and the outputs of all the AND gates are fed to a single k-input OR gate whose output is the desired function.

(con) ● Sum-of-Minterms: Example ● Expression-Circuit Correspondence ● Sum-of-minterms form of

x1 ⊕ x2 ⊕ x3 Maxterms Decimal Notation Complete Gate Sets Wired Logic Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 18/49

Sum-of-minterms form of x1 ⊕ x2 ⊕ x3

Basic Structure

■

Minterms

■

● Minterms ● Minterms:Example of truth table ● Minterms ● Sum-of-Minterms

■

● Sum-of-Minterms: Example ● Sum-of-Minterms: Example ● Sum-of-Minterms: Example (con) ● Sum-of-Minterms: Example

f = 1 for every input combination with an odd number of 1s. Only half of the eight possible input combinations-namely, 001,010,100, and 111-have this property. Hence, zXOR has the four minterms m1 , m2 , m4 , and m7 . x1 m2

(con) ● Sum-of-Minterms: Example ● Expression-Circuit Correspondence ● Sum-of-minterms form of

x2

m1 zXOR

x1 ⊕ x2 ⊕ x3

m4

Maxterms Decimal Notation Complete Gate Sets

x3 m7

Wired Logic Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 19/49

Basic Structure Minterms Maxterms ● Maxterms ● The Product-of-Maxterms Form ● The Product-of-Maxterms Form: Example ● The Product-of-Maxterms Form: Example

Maxterms

Decimal Notation Complete Gate Sets Wired Logic Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 20/49

Maxterms

Basic Structure

■

Minterms Maxterms ● Maxterms ● The Product-of-Maxterms Form ● The Product-of-Maxterms

Mi (x1 , x2 , . . . , xn ) = x˙ 1 + x˙ 2 + · · · + x˙ n

Form: Example ● The Product-of-Maxterms Form: Example Decimal Notation

■

Complete Gate Sets Wired Logic

The ith maxterm function of n variables, denoted Mi , is a Boolean function whose truth table has value 0 in the ith row of the output column and 1 everywhere else. A maxterm can be expressed in the following OR or sum form:

■

Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

where literal x˙ j = xj (¯ xj ) if and only if the jth bit from the left in the binary representation of the number i is 0(1). For example, M3 (x1 , x2 , x3 , x4 ) = x1 + x2 + x ¯3 + x ¯4 and M14 (¯ x1 + x ¯2 + x ¯3 + x4 )

Logic Elements - p. 21/49

The Product-of-Maxterms Form

Basic Structure

■

Minterms Maxterms ● Maxterms ● The Product-of-Maxterms Form ● The Product-of-Maxterms

■

Form: Example ● The Product-of-Maxterms Form: Example Decimal Notation

Every function zi (X) has a unique set of maxterms Mi1 , Mi2 , . . . , Mip that corresponds to the set of 0s appearing in the output column of its truth table. The canonical product-of-maxterms form is then the AND function or logical product of these maxterms zi (X) = Mi1 · Mi2 · · · · · Mip

Complete Gate Sets Wired Logic Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 22/49

The Product-of-Maxterms Form: Example

Basic Structure

■

Minterms Maxterms ● Maxterms ● The Product-of-Maxterms Form ● The Product-of-Maxterms Form: Example ● The Product-of-Maxterms Form: Example Decimal Notation Complete Gate Sets Wired Logic Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

Consider the truth table of three-variable function z = a ¯ + bc a b c z m0 m1 m2 m3 M4 M5 M6 m7 0 0 0 1 1 0 0 0 1 1 1 0 0 1 0 0 1 1 1 0 0 0 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1

Logic Elements - p. 23/49

The Product-of-Maxterms Form: Example

Basic Structure

■

Minterms

We can write Sum-of-Minterms and Product-of-Maxterms as follows:

Maxterms ● Maxterms ● The Product-of-Maxterms Form ● The Product-of-Maxterms Form: Example ● The Product-of-Maxterms Form: Example Decimal Notation

z = M4 M5 M6 = (¯ a + b + c)(¯ a + b + c¯)(¯ a + ¯b + c) z = m0 + m1 + m2 + m3 + m7 =a ¯¯b¯ c+a ¯¯bc + a ¯b¯ c+a ¯bc + abc

Complete Gate Sets Wired Logic Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 24/49

Basic Structure Minterms Maxterms Decimal Notation ● Decimal Notation ● Two-Level Forms

Decimal Notation

● The Sum-of-Products Form ● The Product-of-Sums Form Complete Gate Sets Wired Logic Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 25/49

Decimal Notation

Basic Structure

■

Minterms

■

Only the index (subscript) i of mi or Mi is retained. For example, the previous equation can be written as

Maxterms Decimal Notation

z = Π(4, 5, 6) = Σ(0, 1, 2, 3, 7)

● Decimal Notation ● Two-Level Forms ● The Sum-of-Products Form ● The Product-of-Sums Form Complete Gate Sets Wired Logic Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 26/49

Two-Level Forms

Basic Structure

■

Minterms Maxterms

■

Decimal Notation ● Decimal Notation ● Two-Level Forms ● The Sum-of-Products Form

■

● The Product-of-Sums Form Complete Gate Sets

■ Wired Logic Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

From the figure, we can see that the circuit depth is two. The inverters are omiited. Every function has a two-level realization constructed from AND and OR gates. Except for the few cases that can be realized in one level-namely, the basic gate functions. If an n-variable function z has k minterms, it has 2n − k maxterms.

Logic Elements - p. 27/49

The Sum-of-Products Form

Basic Structure

■

Minterms Maxterms Decimal Notation

A Boolean function has many possible two-level implementations that contain widely varying numbers of gates. z3 (a, b, c, d) =¯ a¯b¯ cd¯ + a ¯¯b¯ cd + a ¯¯bcd¯ + a ¯b¯ cd¯ + a ¯bcd¯ + a¯b¯ cd¯ + a¯bcd¯ + ab¯ cd¯ + abcd¯

● Decimal Notation ● Two-Level Forms ● The Sum-of-Products Form ● The Product-of-Sums Form

z3 (a, b, c, d) =¯ a¯b¯ c + ¯b¯ cd¯ + ¯bcd¯ + b¯ cd¯ + bcd¯ z3 (a, b, c, d) =¯ a¯b¯ c + d¯

Complete Gate Sets Wired Logic Programmable Circuits

■

Sukree Sinthupinyo, December 18, 2006

We refer to all the expressions as sum-of-products (SOP) expressions

Logic Elements - p. 28/49

The Product-of-Sums Form

Basic Structure

■

Minterms

¯ + ¯b + c + d)(a ¯ + ¯b + c¯ + d) ¯ z3 (a, b, c, d) =(a + b + c¯ + d)(a ¯ a + b + c¯ + d)(¯ ¯ a + ¯b + c + d) ¯ (¯ a + b + c + d)(¯

Maxterms Decimal Notation ● Decimal Notation ● Two-Level Forms

¯ (¯ a + ¯b + c¯ + d)

● The Sum-of-Products Form ● The Product-of-Sums Form Complete Gate Sets Wired Logic

Two-level OR-AND circuit for the same function z3

■ ■

That is, z3 = Π(3, 5, 7, 9, 11, 13, 15) The simpler but functionally equivalent expression

Programmable Circuits

¯ ¯b + d)(¯ ¯ a + d) ¯ z3 (a, b, c, d) = (¯ c + d)( ■

Sukree Sinthupinyo, December 18, 2006

We refer to the expressions for z3 as product-of-sums (POS) expressions

Logic Elements - p. 29/49

Basic Structure Minterms Maxterms Decimal Notation Complete Gate Sets ● Complete Gate Sets

Complete Gate Sets

● AND, OR, and NOT Gates ● NAND and NOR Gates ● Two-Level NAND and NOR Circuits ● Two-Level NAND and NOR Circuits ● NAND and NOR Operators ● EXCLUSIVE-OR and -NOR Gates Wired Logic Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 30/49

Complete Gate Sets

Basic Structure

■

Minterms Maxterms

■

Decimal Notation Complete Gate Sets ● Complete Gate Sets

ANDs and ORs may not be the most efficient gate types to use. Most transistor technologies favor NAND or NOR gates because these gates can be manufactured using the fewest transistor switches.

● AND, OR, and NOT Gates ● NAND and NOR Gates ● Two-Level NAND and NOR Circuits ● Two-Level NAND and NOR Circuits ● NAND and NOR Operators ● EXCLUSIVE-OR and -NOR Gates Wired Logic Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 31/49

AND, OR, and NOT Gates

Basic Structure

■

Minterms Maxterms

■

Decimal Notation Complete Gate Sets ● Complete Gate Sets

■

● AND, OR, and NOT Gates ● NAND and NOR Gates ● Two-Level NAND and NOR Circuits ● Two-Level NAND and NOR Circuits ● NAND and NOR Operators ● EXCLUSIVE-OR and -NOR Gates Wired Logic Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

A gate set is functionally complete if it alone can be used to realize any Boolean function. The set of gate types {AND, OR, NOT} is functionally or logically complete. Subsets {AND, NOT} and {OR, NOT} or {AND, OR, NOT} are each complete. ◆ Because AND can be realized by a circuit composed of ORs and NOTs while OR can be realized by a circuit composed of ANDs and NOTs. ¯1 + x ¯2 x1 x2 = x ¯1 x ¯2 x1 + x2 = x

Logic Elements - p. 32/49

NAND and NOR Gates

Basic Structure

■

Minterms

{NAND} and {NOR} are functionally complete.

x

Maxterms Decimal Notation

1

NOT

z

Complete Gate Sets ● Complete Gate Sets ● AND, OR, and NOT Gates ● NAND and NOR Gates ● Two-Level NAND and NOR Circuits ● Two-Level NAND and NOR Circuits ● NAND and NOR Operators

x1 x2 x3

z

AND

z

OR

● EXCLUSIVE-OR and -NOR Gates Wired Logic

x1

Programmable Circuits

x2 x3 Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 33/49

Two-Level NAND and NOR Circuits

Basic Structure

■

Minterms

It’s easy to convert a circuit composed of AND, OR, or NOT gates into all-NAND circuit.

Maxterms

a

Decimal Notation

z

Complete Gate Sets

b c

● Complete Gate Sets ● AND, OR, and NOT Gates ● NAND and NOR Gates ● Two-Level NAND and NOR Circuits ● Two-Level NAND and NOR Circuits ● NAND and NOR Operators ● EXCLUSIVE-OR and -NOR Gates Wired Logic

AND

OR

a

z b c

AND

Programmable Circuits

a z b c

Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 34/49

Two-Level NAND and NOR Circuits

Basic Structure

■

Minterms

We also can transform an OR-AND circuit into an all-NOR equivalent

Maxterms Decimal Notation Complete Gate Sets ● Complete Gate Sets ● AND, OR, and NOT Gates ● NAND and NOR Gates ● Two-Level NAND and NOR Circuits ● Two-Level NAND and NOR Circuits ● NAND and NOR Operators ● EXCLUSIVE-OR and -NOR Gates Wired Logic Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 35/49

NAND and NOR Operators

Basic Structure

■

| for NAND and ↓ for NOR

Minterms

a · b = (a|b)|(a|b)

Maxterms

a + b = (a|a)|(b|b)

Decimal Notation Complete Gate Sets

a ¯ = a|a = a|1

● Complete Gate Sets ● AND, OR, and NOT Gates ● NAND and NOR Gates ● Two-Level NAND and NOR

■

Circuits ● Two-Level NAND and NOR Circuits ● NAND and NOR Operators

| is not associative (a|b)|c = (ab)c = ab + c¯

● EXCLUSIVE-OR and -NOR Gates Wired Logic

■

Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

whereas ¯ + bc a|(b|c) = a(bc) = a

Logic Elements - p. 36/49

EXCLUSIVE-OR and -NOR Gates

Basic Structure

■

If we have one input of a two-input EXCLUSIVE-OR gate is set to 1, the gate becomes and inverter with respect to the other input. z =x⊕1=x ¯

■

EXCLUSIVE-OR and related gate sets are not functionally complete.

Minterms Maxterms Decimal Notation Complete Gate Sets ● Complete Gate Sets ● AND, OR, and NOT Gates ● NAND and NOR Gates ● Two-Level NAND and NOR Circuits ● Two-Level NAND and NOR Circuits ● NAND and NOR Operators ● EXCLUSIVE-OR and -NOR Gates Wired Logic Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 37/49

Basic Structure Minterms Maxterms Decimal Notation Complete Gate Sets

Wired Logic

Wired Logic ● Electrical Interpretation of Z and U ● Electrical Interpretation of Z and U ● Z and U Logic Values ● Z and U Logic Values ● Tri-State Logic ● Tri-State Logic Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 38/49

Electrical Interpretation of Z and U

Basic Structure

■

Minterms Maxterms Decimal Notation Complete Gate Sets

■ ■

Wired Logic ● Electrical Interpretation of Z and U ● Electrical Interpretation of Z and U ● Z and U Logic Values

If both switches are open, no energy from the power supply, the meter in the middle is said to be open-circuited or floating. The output z assumes a neutral or inactive state. This state is indicated by the symbol Z, or generally called the high-impedance state

● Z and U Logic Values ● Tri-State Logic ● Tri-State Logic Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 39/49

Electrical Interpretation of Z and U

Basic Structure

■

Minterms Maxterms Decimal Notation

■ ■

Complete Gate Sets

If both swiches are closed and a short circuit is said to be present. The volmeter reading is now unpredictable. We denote this case by U for unknown or uncertain state.

Wired Logic ● Electrical Interpretation of Z and U ● Electrical Interpretation of Z and U ● Z and U Logic Values ● Z and U Logic Values ● Tri-State Logic ● Tri-State Logic Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 40/49

Z and U Logic Values

Basic Structure

■

Minterms Maxterms

■

Decimal Notation Complete Gate Sets Wired Logic ● Electrical Interpretation of Z and U ● Electrical Interpretation of Z and U ● Z and U Logic Values

The high-impedance state Z may occur on internal lines that happen to be disconnected from any 0 or 1 source. Z and U may occur naturally. ◆ During the brief periods when a signal z is in transition between the 0 and 1 levels. ◆ A signal changing can cause z = U . ◆ z is first disconnected from 0 and the connected to 1. This case can cause z = Z.

● Z and U Logic Values ● Tri-State Logic ● Tri-State Logic Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 41/49

Z and U Logic Values

Basic Structure

■

Minterms Maxterms Decimal Notation

■

Complete Gate Sets Wired Logic ● Electrical Interpretation of Z and U ● Electrical Interpretation of Z and U ● Z and U Logic Values

Some classes of logic circuits such as “tri-state” and “open collector” circuites, the normal output signal levels are taken from the three valued set {0, 1, Z}. In these circuits, interconnecting wires are seen as performing basic AND or OR operations, and so they implement what is often called wired logic.

● Z and U Logic Values ● Tri-State Logic ● Tri-State Logic Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 42/49

Tri-State Logic

Basic Structure Minterms Maxterms

x

z

Enable e

Decimal Notation Complete Gate Sets Wired Logic ● Electrical Interpretation of Z and U ● Electrical Interpretation of Z and U ● Z and U Logic Values ● Z and U Logic Values ● Tri-State Logic ● Tri-State Logic Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

x

z

Disable d Inputs x e 0 0 0 1 1 0 1 1

Output z Z 1 Z 0

Logic Elements - p. 43/49

Tri-State Logic

Basic Structure Minterms Maxterms

x

z

Enable e

Decimal Notation Complete Gate Sets Wired Logic ● Electrical Interpretation of Z and U ● Electrical Interpretation of Z and U ● Z and U Logic Values ● Z and U Logic Values ● Tri-State Logic ● Tri-State Logic Programmable Circuits

Sukree Sinthupinyo, December 18, 2006

x

z

Disable d Inputs x d 0 0 0 1 1 0 1 1

Output z 0 Z 1 Z

Logic Elements - p. 44/49

Basic Structure Minterms Maxterms Decimal Notation Complete Gate Sets

Programmable Circuits

Wired Logic Programmable Circuits ● Programmable Circuits ● Crosspoint Switches ● Programmable Arrays ● Programmable Arrays

Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 45/49

Programmable Circuits

Basic Structure

■

Minterms Maxterms

Programmable logic device or PLD is broadly applied to ICs that have a fixed underlying set of components , but whose interconnections can be tailored.

Decimal Notation Complete Gate Sets Wired Logic Programmable Circuits ● Programmable Circuits ● Crosspoint Switches ● Programmable Arrays ● Programmable Arrays

Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 46/49

Crosspoint Switches

Basic Structure

■

Minterms Maxterms

A programmable connection between two lines A and B in a PLD is logically equivalent to a switch that can be programmed to be closed. B

Decimal Notation

B

Complete Gate Sets Wired Logic

A

A

X

Programmable Circuits ● Programmable Circuits ● Crosspoint Switches

x

● Programmable Arrays ● Programmable Arrays

Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 47/49

Programmable Arrays

Basic Structure Minterms

1

z

Maxterms Decimal Notation Complete Gate Sets

0

Wired Logic

0

0

0

0

0

0

Programmable Circuits ● Programmable Circuits ● Crosspoint Switches

x1

x2

x3

x4

x5

x6

x7

● Programmable Arrays ● Programmable Arrays

X X X X X X X x1 x2 x3 x4 x5 x6 x7 Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 48/49

Programmable Arrays

Basic Structure Minterms

0

z

Maxterms Decimal Notation Complete Gate Sets

1

Wired Logic

1

1

1

1

1

1

Programmable Circuits ● Programmable Circuits ● Crosspoint Switches

x1

x2

x3

x4

x5

x6

x7

● Programmable Arrays ● Programmable Arrays

X X X X X X X x1 x2 x3 x4 x5 x6 x7 Sukree Sinthupinyo, December 18, 2006

Logic Elements - p. 49/49