Arithmetic

Combinational Circuits

© Luis Entrena, Celia López,

Mario García, Enrique San Millán
Universidad Carlos III de Madrid

1
 Contents
1.  Addition and Subtraction Circuits
Ø  Adders with serial propagation of carry (ripple-carry)
•  Half Adder. Full Adder. n bits adder with serial carry
Ø  Adders with carry look ahead
Ø  Adder/Subtractor in 2-s Complement
2.  Circuits for Multiplication
Ø  Basic Multiplier Circuit
3.  Arithmetic Logic Units (ALUs)
Ø  Concept of ALU

© Luis Entrena, Celia López, Mario García, Enrique San Millán. Universidad Carlos III de Madrid, 2008 2
 Adders and Subtractors circuits

A(n)
S(n)
B(n) ADD

Carry_Out
Carry_In

A(n)
R(n)
B(n) SUB

Borrow_Out
Borrow_In

© Luis Entrena, Celia López, Mario García, Enrique San Millán. Universidad Carlos III de Madrid, 2008 3
 Adder with serial propagation of
Carry.
Decimal and binary Addition
1 1 Ø  Operands: n bits
86d à 1010110b Ø  Result: n+1 bits
25d à 0011001b
111d à 11011111b
Bn An Bn-1 An-1 B1 A1 B0 A0

bit bit bit bit

…
Cn n Cn-1 n-1 C1 1 C0 0

Sn Sn-1 S1 S0

© Luis Entrena, Celia López, Mario García, Enrique San Millán. Universidad Carlos III de Madrid, 2008 4
 Adder with serial propagation of carry.
Half Adder
A B S Carry
0 0 0 0
0 1 1 0
A Carry 1 0 1 0
Half-Adder 1 1 0 1
B (SS) S
A
Carry
B

© Luis Entrena, Celia López, Mario García, Enrique San Millán. Universidad Carlos III de Madrid, 2008 5
 Adder with serial propagation of carry.
Full Adder
A B C_in S C_out
A 0 0 0 0 0
C_out 0 0 1 1 0
B Full-Adder 0 1 0 1 0
0 1 1 0 1
(SC) S 1 0 0 1 0
C_in 1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

A
SS C_out
B

SS
C_in S

© Luis Entrena, Celia López, Mario García, Enrique San Millán. Universidad Carlos III de Madrid, 2008 6
 Adder with serial propagation of carry.
Full Adder
A B C_in S C_out
A 0 0 0 0 0
C_out 0 0 1 1 0
B Full-Adder 0 1 0 1 0
0 1 1 0 1
(SC) S 1 0 0 1 0
C_in 1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

S
0 1 0 1

1 0 1 0 Cout
0 0 1 0

0 1 1 1

© Luis Entrena, Celia López, Mario García, Enrique San Millán. Universidad Carlos III de Madrid, 2008 7
 Adder with serial propagation of carry.
Full Adder
A B C_in S C_out
A 0 0 0 0 0
C_out 0 0 1 1 0
B Full-Adder 0 1 0 1 0
0 1 1 0 1
(SC) S 1 0 0 1 0
C_in 1 0 1 0 1
1 1 0 0 1
BCin 1 1 1 1 1

ACin Carry

AB
A
B S
C_in
© Luis Entrena, Celia López, Mario García, Enrique San Millán. Universidad Carlos III de Madrid, 2008 8
 Adder with serial propagation of carry.
N-bits adder
B(0) A(0)

SS
bit 0
B(1) A(1) C_in(1)

C_out(0) S(0)
SC
bit 1
B(2) A(2) C_in(2)

C_out(1) S(1)
SC
B(3) A(3) C_in(3)
bit 2

C_out(2) S(2)
SC
bit 3 L Delay = f(#bits)

C_out(3) S(3)

© Luis Entrena, Celia López, Mario García, Enrique San Millán. Universidad Carlos III de Madrid, 2008 9
 Adder with serial propagation of carry.
N-bits adder

B(3) A(3) B(2) A(2) B(1) A(1) B(0) A(0)

C_out C_in

S(3) S(2) S(1) S(0)

© Luis Entrena, Celia López, Mario García, Enrique San Millán. Universidad Carlos III de Madrid, 2008 10
 Adder with carry look ahead.

C_out
B3 A3 B2 A2 B1 A1 B0 A0
SC S3

SC S2

SC S1

Carry
SC S0
look-ahead

© Luis Entrena, Celia López, Mario García, Enrique San Millán. Universidad Carlos III de Madrid, 2008 11
 Adder with carry look ahead.
B(3) A(3) B(2) A(2) B(1) A(1) B(0) A(0)

Carry logic C_in

C_out

Addition
logic S(3) S(2) S(1) S(0)

© Luis Entrena, Celia López, Mario García, Enrique San Millán. Universidad Carlos III de Madrid, 2008 12
 Adder/Subtractor with 2s
complement.
2-s complement

•  Positive numbers 01010 +10d

•  Negative numbers
10110 -10d

+ 2s C(A)
1

© Luis Entrena, Celia López, Mario García, Enrique San Millán. Universidad Carlos III de Madrid, 2008 13
 Adder/Subtractor with 2s
complement.

A – B = A + (-B)

B 1 + Res

2sC 0

Add/Sub

© Luis Entrena, Celia López, Mario García, Enrique San Millán. Universidad Carlos III de Madrid, 2008 14
 Adder/Subtractor with 2s
complement.
AS
B(0)
C_in
B(1) B
S(0)
Adder S(1)
A(0)
B(2)
A(1)
4 bits S(2)
S S(3)
A(2) A
B(3) A(3) C_out

B(4)
C_in
B(5) B Overflow OV
Adder S(4) detector
A 4 bits
B(6) A(4) S(5)
A(5) S S(6)
A(6) S(7)
B(7) A(7) C_out

© Luis Entrena, Celia López, Mario García, Enrique San Millán. Universidad Carlos III de Madrid, 2008 15
 Adder/Subtractor with 2s
complement. Exercise
A(7)
B (7)
Overflow OV
S(7) detector

© Luis Entrena, Celia López, Mario García, Enrique San Millán. Universidad Carlos III de Madrid, 2008 16
 Multiplier.

Decimal and binary multiplier

A
Multiplier S 86d à 1010110b
B
15d à 0001111b
1290d à 10100001010b
Decimal
86d
Ø  Operands: n bits
15d Ø  Result: 2*n bits
30 5x6
40 5x8 shifted left 1 position.
6 6x1 shifted left 1 position.
8 8x1 shifted left 2 positions.
1290
© Luis Entrena, Celia López, Mario García, Enrique San Millán. Universidad Carlos III de Madrid, 2008 17
 Multiplier.

Binary

A * B = A * (bn-1*2n-1+ bn-2*2n-2+…+ b1*21+ b0*20

¡¡ 1s o 0s !!

The binary multiplication of two numbers A (m bits) y B (n bits) consists in an

adding of as many elements as bits in B (n). Every element i is number A
shifted left i-times when the corresponding weight of B is ‘1’.
In other case the element is ‘0’.

© Luis Entrena, Celia López, Mario García, Enrique San Millán. Universidad Carlos III de Madrid, 2008 18
 Multiplier.

A * B = A * (4*B(2)+2*B(1)+1*B(0))

*1 1
A
0

*2
B(0)
+ Res
SHL(1) 1

*4
B(1) +
SHL(1) 1

0 B(2)

© Luis Entrena, Celia López, Mario García, Enrique San Millán. Universidad Carlos III de Madrid, 2008 19
 Multiplier.

A * 7 = A * (4+2+1)

*1
A

SHL(1)
*2 + Res

*4
+
SHL(1)

© Luis Entrena, Celia López, Mario García, Enrique San Millán. Universidad Carlos III de Madrid, 2008 20
 Multiplier.

A * 5 = A * (4+0+1)

*1
A

SHL(1)
*2 + Res

*4
+
SHL(1)

© Luis Entrena, Celia López, Mario García, Enrique San Millán. Universidad Carlos III de Madrid, 2008 21
 Multiplier.

B4 B3 B2 B1
A4 A3 A2 A1
A1B4 A1B3 A1B2 A1B1
A2B4 A2B3 A2B2 A2B1
A3B4 A3B3 A2B2 A3B1
A4B4 A4B3 A4B2 A4B1
P8 P7 P6 P5 P4 P3 P2 P1

© Luis Entrena, Celia López, Mario García, Enrique San Millán. Universidad Carlos III de Madrid, 2008 22
 Multiplier.

© Luis Entrena, Celia López, Mario García, Enrique San Millán. Universidad Carlos III de Madrid, 2008 23
 Arithmetic-Logic Unit

CarryIn

Res
Overflow
A>B
A<B
A=B
CarryOut
B

Sel_Op

© Luis Entrena, Celia López, Mario García, Enrique San Millán. Universidad Carlos III de Madrid, 2008 24
 Arithmetic-Logic Unit.
Combinational
Block for execution of arithmetic-logic operations:
Ø  Adding
A+B Logic operations (bit to bit)
Ø  Substraction Ø  AND
A-B Ø  OR
Ø  2-s Complement Ø  XOR
-B Ø  XNOR
Ø  NOT
Ø  Comparison
A>B
A<B SUBSTRACTION
A=B
Ø  Shift Left A A A A A A 7 A 6A 5 4 3 2 1 0

SHL(A) ß
Ø  Shift Right
SHR (A) à A A A A A A 7 A 6A 5 4 3 2 1 0

© Luis Entrena, Celia López, Mario García, Enrique San Millán. Universidad Carlos III de Madrid, 2008 25
 References
l  “Circuitos y Sistemas Digitales”. J. E. García
Sánchez, D. G. Tomás, M. Martínez Iniesta. Ed.
Tebar-Flores
l  Electrónica Digital , L. Cuesta, E. Gil, F. Remiro,
McGraw-Hill
l  Fundamentos de Sistemas Digitales , T.L Floyd,
Prentice-Hall

© Luis Entrena, Celia López, Mario García, Enrique San Millán. Universidad Carlos III de Madrid, 2008 26