Chapter5

Useful Circuits Sukree Sinthupinyo Department of Computer Science Thammasat University

Sukree Sinthupinyo, January 15, 2007

Combinational Design - p. 1/17

Data Transfer Logic ● Data Transfer Logic ● Shared Data Paths ● Multiplexer and Demultiplexer ● Multiplexer Design ● Multiplexer Design (cont.) ● n-Way Multiplexers ● Demultiplexer Design ● Tri-State Buses

Data Transfer Logic

● Decoders Adders and Subtracters

Sukree Sinthupinyo, January 15, 2007

Combinational Design - p. 2/17

Data Transfer Logic

Data Transfer Logic

■

● Data Transfer Logic ● Shared Data Paths ● Multiplexer and Demultiplexer ● Multiplexer Design ● Multiplexer Design (cont.) ● n-Way Multiplexers ● Demultiplexer Design ● Tri-State Buses ● Decoders Adders and Subtracters

Sukree Sinthupinyo, January 15, 2007

■

Shared Data Paths Data transfer paths are frequently shared to reduce hardware cost. A Particular destination can take signals from only one source at a time. The source-to-destination data transfer paths must be shared to some degree.

Combinational Design - p. 3/17

Shared Data Paths

Data Transfer Logic

■

● Data Transfer Logic ● Shared Data Paths ● Multiplexer and Demultiplexer ● Multiplexer Design ● Multiplexer Design (cont.) ● n-Way Multiplexers ● Demultiplexer Design ● Tri-State Buses ● Decoders

■

The left most image show the simplest case in which a single source must broadcast its data to a set of m ≥ 1 destinations simultaneously. The multiplexer and demultiplexer are shown in the middle and the right most images. D1

Adders and Subtracters

D2 S1 S2 S Sn

D1 D2 . . .

Multiplexer

D

S

Multiplexer . . .

Dn

Dm Source Address A

Sukree Sinthupinyo, January 15, 2007

Destnation Address A

Combinational Design - p. 4/17

Multiplexer and Demultiplexer

Data Transfer Logic

■

● Data Transfer Logic ● Shared Data Paths ● Multiplexer and Demultiplexer ● Multiplexer Design

■

● Multiplexer Design (cont.) ● n-Way Multiplexers ● Demultiplexer Design ● Tri-State Buses ● Decoders

■ Adders and Subtracters

■

Sukree Sinthupinyo, January 15, 2007

In order to connect serveral sources to a single destination, we use a logic circuit called a multiplexer or data selector A multiplxer M , often called a mux for short, allows one and only one of n sources to be logically connected to a common destination D at any time. The source Si used at any particular time is determined by signals placed on M ’s address or select inputs A. Demultiplexer serves to connect a common source S to a single selected destination Di . Again, a set of address lines specify which destination is to be selected at any time.

Combinational Design - p. 5/17

Multiplexer Design

Data Transfer Logic

■

● Data Transfer Logic ● Shared Data Paths ● Multiplexer and Demultiplexer ● Multiplexer Design ● Multiplexer Design (cont.) ● n-Way Multiplexers ● Demultiplexer Design

■ ■

Simple multiplexer M that is required to connect one of two 1-bit source x0 and x1 to a common destination z. Only one address bit a is needed. The desired circuit has three input lines and one output line.

● Tri-State Buses ● Decoders Adders and Subtracters

Sukree Sinthupinyo, January 15, 2007

Combinational Design - p. 6/17

Multiplexer Design (cont.)

Data Transfer Logic ● Data Transfer Logic ● Shared Data Paths ● Multiplexer and Demultiplexer ● Multiplexer Design

■

z=a ¯x0 + ax1

x0

● Multiplexer Design (cont.) ● n-Way Multiplexers

z

● Demultiplexer Design ● Tri-State Buses ● Decoders Adders and Subtracters

x1

a

Sukree Sinthupinyo, January 15, 2007

Combinational Design - p. 7/17

n-Way Multiplexers

Data Transfer Logic

■

● Data Transfer Logic ● Shared Data Paths ● Multiplexer and Demultiplexer ● Multiplexer Design

For example, we could extend the preceding multiplexer example to accommodate four sources instead of two by changing the expression from the previous slide to:

● Multiplexer Design (cont.) ● n-Way Multiplexers

z=a ¯1 a ¯0 x0 + a ¯1 a0 x1 + a1 a ¯0 x2 + a1 a0 x3

● Demultiplexer Design ● Tri-State Buses ● Decoders

■

Adders and Subtracters

We can define the minimal SOP equation as X a˙ k−1 a˙ k−2 . . . a˙ 1 a˙ 0 z= i

■

Sukree Sinthupinyo, January 15, 2007

Moreover, we can design n-Way, w-Bit Multiplexers by using the same method.

Combinational Design - p. 8/17

Demultiplexer Design

Data Transfer Logic

■

● Data Transfer Logic ● Shared Data Paths ● Multiplexer and Demultiplexer ● Multiplexer Design ● Multiplexer Design (cont.)

■

zi = a˙ k−1 a˙ k−2 . . . a˙ 1 a˙ 0 x For example, we can design 4-way, 1-bit demultiplexer as below.

● n-Way Multiplexers

z0

● Demultiplexer Design ● Tri-State Buses ● Decoders

z1

Adders and Subtracters

x z2 z3

a1

Sukree Sinthupinyo, January 15, 2007

a0

Combinational Design - p. 9/17

Tri-State Buses

Data Transfer Logic ● Data Transfer Logic ● Shared Data Paths ● Multiplexer and Demultiplexer

■

A tri-state bus is used to link a large number of logic devices E1 , E2 , . . . , En .

● Multiplexer Design ● Multiplexer Design (cont.) ● n-Way Multiplexers ● Demultiplexer Design ● Tri-State Buses ● Decoders Adders and Subtracters

x1

Sukree Sinthupinyo, January 15, 2007

z1 e1=0 xi

zi ei =1 xj

zj ej =0 xn

zn en=0

Combinational Design - p. 10/17

Decoders

Data Transfer Logic

■

● Data Transfer Logic ● Shared Data Paths ● Multiplexer and Demultiplexer ● Multiplexer Design ● Multiplexer Design (cont.) ● n-Way Multiplexers ● Demultiplexer Design

■ ■

● Tri-State Buses ● Decoders Adders and Subtracters

■

If we swap the positions of the data input x and address inputs A of an m-way, 1 bit demultiplexer so that the latter become the circuit’s main inputs. We will obtain a very useful logic circuit D, called a one-out-of-m decoder. The input x now assumes a control function and is termed as enable line. z0 a1 z1 a0 z2 z3

Sukree Sinthupinyo, January 15, 2007

Combinational Design - p. 11/17

Data Transfer Logic Adders and Subtracters ● A Full Adder ● Ripple-Carry Adders ● Fast Adders ● Carry Lookahead ● Carry Lookahead (cont.)

Sukree Sinthupinyo, January 15, 2007

Adders and Subtracters

Combinational Design - p. 12/17

A Full Adder

Data Transfer Logic

■

Adders and Subtracters

■

● A Full Adder ● Ripple-Carry Adders ● Fast Adders ● Carry Lookahead ● Carry Lookahead (cont.)

■

ci si = xi + yi + ci−1 where ci is an output carry bit, si is an output sum bit, xi and yi are input operand bits, ci−1 is an input carry bit. Full-adder equations si = xi ⊕ yi ⊕ ci−1 ci = xi yi + xi ci−1 + yi ci−1

Sukree Sinthupinyo, January 15, 2007

Combinational Design - p. 13/17

Ripple-Carry Adders

Data Transfer Logic Adders and Subtracters ● A Full Adder ● Ripple-Carry Adders ● Fast Adders

■

Each full-adder stage Ai receives a carry signal ci−1 from the full adder Ai−1 and supplies a carry signal ci to full adder Ai+1 .

● Carry Lookahead ● Carry Lookahead (cont.)

Sukree Sinthupinyo, January 15, 2007

Combinational Design - p. 14/17

Fast Adders

Data Transfer Logic

■

For n = 1, cout is given by

Adders and Subtracters

c0 = x0 y0 + x0 cin + y0 cin

● A Full Adder ● Ripple-Carry Adders ● Fast Adders ● Carry Lookahead ● Carry Lookahead (cont.)

■

For n = 2, the output carry function becomes c1 = x1 y1 + x1 c0 + y1 c0 c1 = x1 y1 + x1 (x0 y0 + x0 cin + y0 cin ) + y1 (x0 y0 + x0 cin + y0 cin ) c1 = x1 y1 + x1 x0 y0 + x1 x0 cin + x1 y0 cin + y1 x0 y0 + y1 x0 cin + y1 y0 cin

Sukree Sinthupinyo, January 15, 2007

Combinational Design - p. 15/17

Carry Lookahead

Data Transfer Logic

■

Adders and Subtracters ● A Full Adder ● Ripple-Carry Adders ● Fast Adders ● Carry Lookahead

■

● Carry Lookahead (cont.)

Define two new functions. ◆ generate function gi = xi yi ◆ propagate function pi = xi + y + i From si = xi ⊕ yi ⊕ ci−1 ci = xi yi + xi ci−1 + yi ci−1

■

can be rewritten in the form si = gi ⊕ pi ⊕ ci−1 ci = gi + pi ci−1

Sukree Sinthupinyo, January 15, 2007

Combinational Design - p. 16/17

Carry Lookahead (cont.)

Data Transfer Logic Adders and Subtracters ● A Full Adder

c0 = g0 + p0 cin

● Ripple-Carry Adders ● Fast Adders ● Carry Lookahead ● Carry Lookahead (cont.)

c1 = g1 + p1 c0 = g1 + p1 (g0 + p0 cin ) = g1 + p1 g0 + p1 p0 cin c2 = g2 + p2 c1 = g2 + p2 (g1 + p1 g0 + p1 p0 cin ) = g2 + p2 g1 + p2 p1 g0 + p2 p1 p0 cin

Sukree Sinthupinyo, January 15, 2007

Combinational Design - p. 17/17