# 5 Combinatorial Components 5.0 Full adder Full subtractor - Cs.ucr.edu

5 Combinatorial Components Use for data transformation, manipulation, interconnection, and for control: • arithmetic operations - addition, subtraction, multiplication and division. • logic operations - AND, OR, XOR, and NOT. • comparison operations - greater than, equal to, and less than. • bit manipulation operations - shift, rotation, extraction, and insertion. • interconnect components - selectors, and buses - used to connect different components together. • conversion components - decoders and encoders - used for conversion between different codes. • universal components - ROMs and programmable-logic arrays (PLAs) - used primarily in the design of control units.

5.0

Full adder xi 0 0 0 0 1 1 1 1

yi 0 0 1 1 0 0 1 1

ci 0 1 0 1 0 1 0 1

ci+1 0 0 0 1 0 1 1 1

si 0 1 1 0 1 0 0 1

xi

i

= xi' yi' ci + xi' yi ci' + xi yi' ci' + xi yi ci = (xi' yi + xi yi') ci ' + (xi' yi' + xi yi) ci = (xi ⊕ yi) ci' + (xi yi) ci = (xi ⊕ yi) ⊕ ci

~

ci+1 = xi' yi ci + xi yi' ci + xi yi ci' + xi yi ci = xi yi (ci' + ci) + ci (xi' yi + xi yi') = xi yi • 1 + ci (xi ⊕ yi)

yi

X

c i+ 1

Cout

Y

FA

Cin

ci S

si

Full subtractor bin 0 0 0 0 1

x 0 0 1 1 0

y 0 1 0 1 0

bout 0 1 0 0 1

d 0 1 1 0 1

1 1 1

0 1 1

1 0 1

1 0 1

0 0 1

Comment x-bin-y = d = 0-0 = 0 0-0-1 = borrow 2-1 = 1 1-0-0=1 with no borrow 1-0-1=0 with no borrow x=0-1=-1 because of bin=1, therefore, borrow 2-1=1. Finally, 1-0=1 x-bin-y=borrow 2-1-1=0 1-1-0=0 with no borrow x-bin=1-1=0. Then 0-1=borrow 2-1=1

00

xy b in

01 0

11

10

1

0

3

2

4

5

1

7

1

01 0

x'y

1

1

00

xy b in

1

0 4

yb in

10 3

1

x'b in

6

1

11

1

2 1

5

7

1

6

1

d = x ′y ′bin + xybin + x ′ybin′ + xy ′bin′ = bin ( x ′y ′ + xy) + bin′ ( x ′y + xy ′)

bout = x′bin + x′y + ybin

= bin ( x ⊕ y ) ′ + bin′ ( x ⊕ y ) = bin ⊕ x ⊕ y

x

y

bin

X

Y

bout FS

b out

b in

d

d

Circuit for Full Subtractor

5.1

co u t

FA

x6 y6 c7

c6

FA

s7

5.3

x5 y5

x4 y4 c5

FA

s6

x3 y3 c4

FA

s5

x2 y2 c3

FA

s4

x1 y1 c2

FA

s3

x0 y0 c1

FA

s2

c

FA

s1

in

s0

y7

x6

y6

x5

y5

x4

y4

x3

y3

x2

y2

x1

y1

x0

y0

S

S

0 1 co u t

FA

f7

5.4

c7

FA

c6

f6

Logic Unit

FA

f5

c5

FA

f4

c4

FA

f3

c3

FA

f2

c2

FA

f1

c1

FA

f0

c0

Function X+Y X+Y’+1

5.5

Arithmetic-Logic Unit (ALU) a3

b3

a2

b2

a1

b1

a0

b0

S0 S1 M LE

c4

AE

c3

FA

Overflow

LE

f3

AE

LE

AE

c2

FA

c1

FA

f2

LE

AE

FA

f1

c0

f0

Arithmetic Extender (AE) The AE modifies the second operand and passes it to the FA to perform the arithmetic.

M 1 1 1 1

S1 0 0 1 1

S0 0 1 0 1

Function Name Function Decrement A–1 Add A+B Subtract A+B’+1 Increment A+1 Functional table

X A A A A

Y all 1’s B B’ all 0’s

11

10

c0 0 0 1 1 bi

M 1 1 1 1 1 1 1 1

S1 S0 bi 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 Truth table

yi 1 1 0 1 1 0 0 0

bi

S1 S0

00

01 0

0

1

2 1

4 1

3

1

1

5

7

6

1

S' 0 b' i S' 1 b i

S0 S1 M

yi = MS1’bi + MS0’bi’ Map representation

AE yi

yi = MS1’S0’bi’ + MS1’S0’bi + MS1’S0bi + MS1S0’bi’ = MS0’bi’(S1’ + S1) + MS1’bi(S0’+ S0) = MS0’bi’ + MS1’bi

Schematic diagram

Logic Extender (LE) The logic operations are performed in the logic extender. The FAs are used simply as connections for the outputs.

M 0 0 0 0

S1 0 0 1 1

S0 0 1 0 1

Function Name Function Complement A’ AND A AND B Identity A OR A OR B Functional table

X A’ A AND B A A OR B

Y 0 0 0 0

c0 0 0 0 0

ai

M

S1

S0

0 0 0 0 1

0 0 1 1 X

0 1 0 1 X

xi

ai’ ai bi ai ai + bi ai Truth table

Indices in map 0, 4 13 10, 14 7, 11, 15 pass to AE

bi

S0 S1 M

LE xi

Schematic diagram M = 0 S1 S0 a i bi 00

01

00

M = 1 11

10

01

00

11

ai

10

0

1

3

2

0

1

3

2

4

5

7

6

4

5

7

6

bi

1

S0 01

1

1 12

11

13 1

8 10

15 1

9

14 1

11 1

12 1

10 1

13 1

8 1

15 1

9 1

14

S1 M

1 11

1

10 1

xi = M’S1’ S0’ai’ + M’S1 S0bi + S0 ai bi + S1 ai + Mai Map representation

LE xi

Simplified schematic diagram

Carry in signal c0 – Notice that in the AE functional table, c0 = MS1

Overflow signal c4 – The carry-out of the most significant bit represents an overflow in the case of unsigned arithmetic. Overflow – The XOR of the carry-outs of the two most significant bits represents the overflow in the case of 2’s complement arithmetic.

5.6

Decoders / Demultiplexers

To enable only one of n components. A1

E 0 1 1 1 1

A1 × 0 0 1 1

A0 × 0 1 0 1

C3 0 0 0 0 1

E

C2 0 0 0 1 0

C1 0 0 1 0 0

C0 0 1 0 0 0

1

Decoder

E 3

2

1

0

C3 C2 C1 C0

2-to-4 Decoder

A2 E

A0

A0

A0

0

E

1

E

0

E

1

E

0

C7 C6

1

1

0

E

0

C5 C4

1

E

0

C3 C2

1

0

C1 C0

3-to-8 decoder implemented with 1-to-2 decoders

5.7

Selectors / Multiplexers (MUX) D3 D2 D1 D0

S1 0 0 1 1

S0 0 1 0 1

Y D0 D1 D2 D3

3 S1 S0

2

1

0

MUX Y

4-to-1 MUX

S

1

D5 D4

0

S

1

D3 D2

0

S

1

D1 D0

0

S

S0 S

1

0

S

1

1

D7

0

S0 S1 S2

Decoder

D7 D6

D6

D5

D4

D3

D2

D1

0 1 2 3 4 5 6 7

0

S1 S2

S

1

0 y

y

8-to-1 mux implemented with 2-to-1 muxes

8-to-1 mux implemented with a decoder

D0

5.8

Buses

A bus is for connecting several components together, however, only one component can send data to the bus at any one time. To construct a bus, use a tristate driver, whose output provides three different values, 0, 1, and Z. The value Z represents a high-impedance state which can be thought of as a disconnection from the bus. E0 Bus

E1 Y

D

5.9

E 0 1

Y

D

Y Z D

Priority Encoders

A priority encoder has: • n inputs, Dn-1, … D0, • m outputs, Am-1, … A0, where n = 2m, which represents the index (decimal value) of the most significant input bit Di that has a value equal to 1. • an additional output call Any, which will be 1 whenever any of the inputs has a value that is different from 0. 2-to-1 priority encoder D1

D0

1

0

Encoder Any

D1 0 0 1

D0 0 1 X

A0 0 0 1

Any 0 1 1

D3 0 0 0 0 1

D2 0 0 0 1 X

D1 0 0 1 X X

D0 0 1 X X X

A0

4-to-2 priority encoder D3 3

D2

D1

D0

2

1

0

Encoder Any

A1

A0

A1 0 0 0 1 1

A0 0 0 1 0 1

Any 0 1 1 1 1

5.10 Magnitude Comparators A comparator compares two positive integers X and Y and then generates two boolean results G and L as follows: Test X >Y X ≤Y X
G 1 0

1 0

L

1 0 1 0

For the n-bit integers X and Y, we compare them one bit at a time, starting with the most significant bit, Gi = (xi > yi) or [(xi = yi) and (Gi-1 > Li-1)] Li = (xi < yi) or [(xi = yi) and (Gi-1 < Li-1)]

x1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

y1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

x0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

y0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

G 0 0 1 0 0 0 0 0 1 1 1 1 0 0 1 0

a0b0 a1b1

L 0 1 0 0 1 1 1 1 0 0 0 0 0 1 0 0

y1

x0

11

01 0

10

1

3

2

00

1 4

5

7

6

01 12

13

15

14

11

1 8

10

9

1

11

1

10

1

1

G = a1b1’ + a1a0b0’ + b1’a0b0’

a0b0 a1b1

00

01 0

00

10 3

1

1

2

11

7

5 1

12

y0

11

1 4

01

x1

00

1 13

6 1

15

14

11

10

1 8

9

10

G

L

5.11 Shifters and Rotators Use selectors to implement. S2 0 0 1 1 1 1

S1 0 1 0 0 1 1

S0 × × 0 1 0 1

Y D ShiftLeft(D) RotateLeft(D) ShiftRight(D) RotateRight(D)

Comment No shift Not used Shift left Rotate left Shift right Rotate right

L = a1’b1 + a1’a0’b0 + b1a0’b0

d3

d2

d1

d0

Left Input Right Input 1

1

S0

0

Selector

0

Selector

3

2

1

0

3

2

1

0

3

2

1

0

3

2

1

Selector

Selector

Selector

Selector

y3

y2

y1

y0

0

S1 S2

5.12 Read-Only Memories ROMs can be thought of as a universal logic element that is able to implement concurrently several different Boolean functions that are defined on the same set of variables. A 16 × 4 ROM can implement 4 functions. Programmable ANDs and ORs. a b c d a b c d

= =

a b c d a b c d

Use a 16 × 4 ROM to implement the following two functions: f0 = w x' y' z + w x' y z' + w' x y' z' f1 = x y + w' z + w x' y

OR array

z y x w

A0 A1 A2 A3

0 1 2 3 4 5 6 4-to-16 7 decoder 8 9 10 11 12 13 14 15

f1 f0

5.13 Programmable Logic Arrays (PLA) ROMs are not very efficient when we use them to implement sparse functions, i.e. functions with only a small number of 1’s because in such cases, many of the words in the ROM will have a value of 0, which is a waste of silicon area. A PLA differs from a ROM in the address decoder. Instead of a full decoder, PLAs use a programmable decoder call an AND array. Use a 4 × 8 × 4 PLA to implement the following two functions: f0 = w x' y' z + w x' y z' + w' x y' z' f1 = w' x y + w y' z

M A3

S1 A2

S0 A1

b A0 OR array 0 1 2 3 4 5 6 7

AND array output array

0 1

f3 f2 f1 f0 c y

## 5 Combinatorial Components 5.0 Full adder Full subtractor - Cs.ucr.edu

5 Combinatorial Components Use for data transformation, manipulation, interconnection, and for control: • arithmetic operations - addition, subtractio...

#### Recommend Documents

Full Subtractor Schematic - WordPress.com
Full Subtractor Schematic. Here's a full-adder circuit: The truth table for the above: INPUTS OUTPUTS A B CIN COUT S. 0

4-bit ripple-carry adder/subtractor. â Circuit adds or subtracts. â« 2s complement: A Å B = A + (ÅB) = A + B' + 1.

Heywood monotheism landscape and shackled his incrassating or resume typographically. lacy Sancho gabbing transliterated

implementation of n-bit adder and subtractor of library components for