Transcript 15.11.2016 (7) - Erwin Sitompul

Digital Systems
Lecture 7
Dr.-Ing. Erwin Sitompul
President University
http://zitompul.wordpress.com
2 0 1 6
President University
Erwin Sitompul
Digital Systems 7/1
Digital Systems
Section 8
Multiplexers
President University
Erwin Sitompul
Digital Systems 7/2
Lecture
Digital Systems
Multiplexer (Mux)
 A multiplexer (mux) is a digital circuit building block which is used
to select and transmit one of its 2n inputs to its one output, based
on n select bit.
 A multiplexer allows for conditional data transfer.
 A 4-input mux needs 2 select bit to indicate which input to route
through. An 8-input mux needs 3 select bits, and so on.
● A railway switch
President University
Erwin Sitompul
Digital Systems 7/3
Lecture
Digital Systems
Multiplexer (Mux)
 Four data are possible to be displayed: Air temperature (T),
average km/l (A), instantaneous km/l (I), and kilometer
remaining (M), each 8-bit wide.
 We can chose which to display by using two inputs X and Y.
 In this case, an 8-bit 4-to-1 multiplexer is used.
President University
Erwin Sitompul
Digital Systems 7/4
Lecture
Digital Systems
2-to-1 Multiplexer
 A multiplexer with one select bit is shown below, or 2-to-1
multiplexer.
 If S = 0, then Y = I0, if S = 1, then Y = I1.
● Circuit of 2-to-1 multiplexer
President University
Erwin Sitompul
● Symbol
Digital Systems 7/5
Lecture
Digital Systems
2-to-1 Multiplexer
● Truth table
S I0 I1
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
F(S,I0,I1)
0
0
1
1
0
1
0
1
● Compact truth table
S
0
1
F(S,I0,I1)
I0
I1
?
● Determine the Boolean
expression for Y as a
function of I0, I1, and S.
A● Y = S’I
President University
Erwin Sitompul
0
+ SI1
Digital Systems 7/6
Lecture
Digital Systems
4-to-1 Multiplexers
 A 4-to-1 multiplexer is shown below.
?
President University
● Determine the Boolean
expression for Y as a
function of Di and Si.
Erwin Sitompul
Digital Systems 7/7
Lecture
Digital Systems
4-to-1 Multiplexers
 A 4-to-1 multiplexer can also be made by using two 2-to-1
multiplexers, as shown below:
S0
S1
I0
0
I1
1
0
F
1
I2
0
I3
1
President University
Erwin Sitompul
Digital Systems 7/8
Lecture
Digital Systems
Quadruple 2-to-1 Multiplexer
 A quadruple 2-to-1 multiplexer is shown below.
President University
Erwin Sitompul
Digital Systems 7/9
Lecture
Digital Systems
Design Exercise: Multiplexer
Design a multiplexer with 8 inputs (A1, A2, B1, B2, C1, C2, D1, D2),
with 2 outputs and 4 possibilities of transmission: (A1, A2), (B1, B2),
(C1, C2), and (D1, D2).
Give the logic expression and the logic circuit of the multiplexer.
A2
B2
C2
D2
A1
O2
O1
B1
C1
D1
President University
Erwin Sitompul
Digital Systems 7/10
Lecture
Digital Systems
Exercise: Crossbar Switch
Find out the truth table of the following
circuit? What can the function of this circuit?
X1
0
Y1
1
S
X2
S X1 X2
Y1
Y2
0 X1 X2
X1
X2
(Straight)
1 X1 X2
X2
X1
(Crossed)
0
Y2
1
S
This crossbar switch circuit is capable
to connect any input to any output.
Here X1 and X2 can be set to pass
through Y1 or Y2.
President University
Erwin Sitompul
X1
Y1
X2
Y2
Digital Systems 7/11
Digital Systems
Section 9
Binary Adders
President University
Erwin Sitompul
Digital Systems 7/12
Lecture
Digital Systems
Binary Adders
 Addition of binary data is very fundamental in digital systems. The
hardware implementation needs to be determined.
 The inputs are: single bit values, carry in
 The outputs are: sum, carry out.
 After creating a single-bit adder, we can chain multiple adders
together.
 Overflow must also be considered. Overflow is the situation where
the result of addition exceeds the magnitude which can be
represented with the allocated number of bits.
President University
Erwin Sitompul
Digital Systems 7/13
Lecture
Digital Systems
Half Adder
 A half adder adds two binary numbers.
 The inputs: A0, B0 (single bit inputs).
 The outputs: S0 (single bit sum) and C1
(carry out).
A0
B0
C1 S0
0
0
0 0
0
1
0 1
● Truth Table of
Half Adder
A 0 B0 S0 C1
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1
President University
A0
Half
adder
B0
1
0
0 1
S0
C1
1
1
1 0
● Circuit of Half
Adder
A0
B0
Erwin Sitompul
S0
C1
Digital Systems 7/14
Lecture
Digital Systems
Multiple Bit Addition
 Consider the addition of 2 binary numbers, A and B.
A3
A2
A1
A0
B3
B2
B1
B0
A 0
1
0
1
B 0
1
1
1
 Addition of each bit position Ai and Bi creates a sum Si and a carry
Ci+1.
Ci 1
Ci
Ai
Bi
Si
President University
C
1
1
1
A 0 1 0 1
B 0 1 1 1
1 1 0 0
Erwin Sitompul
Digital Systems 7/15
Lecture
Digital Systems
Full Adder
 A full adder adds two binary numbers but also include a carry in.
 The inputs: Ai, Bi, Ci (single bit inputs).
 The outputs: Si (single bit sum) and Ci+1 (carry out).
● Truth Table of
Half Adder
Ai
0
0
0
0
1
1
1
1
Bi
0
0
1
1
0
0
1
1
Ci
0
1
0
1
0
1
0
1
President University
Si
0
1
1
0
1
0
0
1
● K-Map for Si
00
01
11
10
0
0
1
0
1
1
1
0
1
0
Ci
Ci 1
0
0
0
1
0
1
1
1
AiBi
● K-Map for Ci+1
Erwin Sitompul
AiBi
00
01
11
10
0
0
0
1
0
1
0
1
1
1
Ci
Digital Systems 7/16
Lecture
Digital Systems
Full Adder
 Let us now simplify Boolean function for S by using Boolean
algebra.
Si = Ai’Bi’Ci + Ai’BiCi’ + AiBi’Ci’ + AiBiCi
Si = Ci·(Ai’Bi’ + AiBi) + Ci’·(Ai’Bi + AiBi’)
Si = Ci·(Ai  Bi )’ + Ci’·(Ai  Bi )
Si = Ci  (Ai  Bi )
Hint:
A  B = A·B’ + A’·B
(A·B)’ = A’ + B’
(A+B)’ = A’ · B’
President University
Erwin Sitompul
AiBi
00
01
11
10
0
0
1
0
1
1
1
0
1
0
Ci
Digital Systems 7/17
Lecture
Digital Systems
Full Adder
 Let us now simplify Boolean function for Ci+1 by using Boolean
algebra.
Ci+1 = AiBi + AiCi +BiCi
(previous result)
Ci+1 = AiBi + CiAi’Bi +CiAiBi’ (as shown by K-map below)
Ci+1 = AiBi + Ci ·(Ai’Bi + AiBi’)
Ci+1 = AiBi + Ci ·(Ai  Bi)
Hint:
A  B = A·B’ + A’·B
(A·B)’ = A’ + B’
(A+B)’ = A’ · B’
President University
Erwin Sitompul
AiBi
00
01
11
10
0
0
0
1
0
1
0
1
1
1
Ci
Digital Systems 7/18
Lecture
Digital Systems
Full Adder
 The logic circuit of the full adder can be shown as:
Ci
Half adder
Ai
Si
Bi
Half adder
Ci+1
Si = Ci  (Ai  Bi )
Ci+1 = AiBi + Ci ·(Ai  Bi)
 A full adder can be made from 2 half adders and an OR Gate.
 Such structure repetition simplifies circuit design.
President University
Erwin Sitompul
Digital Systems 7/19
Lecture
Digital Systems
Full Adder
Ci
Ai
Bi
Half
adder
Si
Half
adder
Ci+1
=
Ci
Ai
Bi
Full
adder
Si
Ci+1
 This single bit full adder will be the building block of large adders.
President University
Erwin Sitompul
Digital Systems 7/20
Lecture
Digital Systems
n × Full Adder = n-bit Ripple Carry Adder
Bi
Ai
Ci+1
Full
adder
Ci
C
1
1
1
0
A 0 1 0 1
B 0 1 1 1
1 1 0 0
Si
A3
C4
B3
Full
adder
MSB position
S4
A2
C3
B2
Full
adder
S3
A1
C2
B1
A0
C1
Full
adder
B0
Full
adder
C0
LSB position
S2
S1
● 4-bit ripple-carry adder
President University
Erwin Sitompul
Digital Systems 7/21
Digital Systems
Section 10
Signed Numbers
President University
Erwin Sitompul
Digital Systems 7/22
Lecture
Digital Systems
How to Represent Signed Numbers
 For decimal numbers, it is common to use the sign + and –, as for
+25, –16, +433, –2775.
 For computers, where operations are done using binary digits, it is
desirable to represent signed numbers also in bits.
 There are 3 representations of signed binary numbers:
1. Signed magnitude
2. 1’s complement
3. 2’s complement
 In each case, the left-most bit indicates the sign: 0 means
positive, 1 means negative.
President University
Erwin Sitompul
Digital Systems 7/23
Lecture
Digital Systems
How to Represent Signed Numbers
bn–1
b1
b0
Magnitude
MSB
● Unsigned number
bn–1 bn–2
Sign
0 denotes +
1 denotes –
b1
b0
Magnitude
MSB
● Signed number
President University
Erwin Sitompul
Digital Systems 7/24
Lecture
Digital Systems
Signed Numbers
0000
1111
1110
1101
1100
–1
0
0001
0010
+1
–2
–3
+2
+3
–4
0101
+6
–7 –8 +7
1001
0100
+5
–6
1010
0011
+4
–5
1011
● 4-bit signed binary
number comparison
1000
0110
0111
● Number circle for 4-bit
2’s complement numbers
President University
Erwin Sitompul
Digital Systems 7/25
Lecture
Digital Systems
Signed Numbers
●4-bit signed binary number comparison
President University
Erwin Sitompul
Digital Systems 7/26
Lecture
Digital Systems
Signed Magnitude Representation
 As mentioned before, in signed magnitude, the left-most bit is
used to indicate the sign. 0 means positive, 1 means negative.
000011002 = 1210
Sign bit
Magnitude
100011002 = –1210
Sign bit
Magnitude
 By using signed magnitude, n bits can be used to represent
integers N in the range of: 2n–1 – 1 ≤ N ≤ 2n–1 – 1
 For example, the range of an unsigned 4-bit binary number is from
0 to 15.
 The range of a signed 4-bit binary number is –7 to + 7 (or 11112
to 01112)
 For signed magnitude, there are two representations for zero. For
example, with n = 4, 0000 and 1000.
President University
Erwin Sitompul
Digital Systems 7/27
Lecture
Digital Systems
1’s Complement Representation
 The 1’s complement of a binary number involves inverting all bits.
1s become 0s, and 0s become 1s.
 As example,
 1’s complement of 00110011 is 11001100
 1’s complement of 10101010 is 01010101.
 Thus, for an n-bit number N, the 1’s complement is 2n – 1 – N.
 To find the negative of a number, take the 1’s complement of that
number.
 For 1’s complement, there are two representations for zero. For
example, with n = 4, 0000 and 1111.
000011002 = 1210
Sign bit
President University
Magnitude
111100112 = –1210
Sign bit
Erwin Sitompul
Magnitude
Digital Systems 7/28
Lecture
Digital Systems
1’s Complement Addition / Subtraction
 As Example 1, suppose we wish to add 1210 + 110.
 1210 = 11002 = 011002 in 1’s complement
110 = 00012 = 000012 in 1’s complement
 Step 1: Add the binary numbers
 Step 2: Add the carry to lowest-order bit
011002
000012
0
011012
0
011012 = 1310
President University
Erwin Sitompul
Digital Systems 7/29
Lecture
Digital Systems
1’s Complement Addition / Subtraction
 As Example 2, suppose we wish to substract 1210 – 110.
 1210 = 11002 = 011002 in 1’s complement
–110 = –00012 = 111102 in 1’s complement
 Step 1: Add the binary numbers
 Step 2: Add the carry to lowest-order bit
011002
111102
1
010102
1
010112 = 1110
President University
Erwin Sitompul
Digital Systems 7/30
Lecture
Digital Systems
1’s Complement Addition / Subtraction
 As Example 3, suppose we wish to substract –510 – 410.
 –510 = –01012 = 110102 in 1’s complement
–410 = –01002 = 110112 in 1’s complement
 Step 1: Add the binary numbers
 Step 2: Add the carry to lowest-order bit
110102
110112
1
101012
1
101102 = –10012
= –910
President University
Erwin Sitompul
Digital Systems 7/31
Lecture
Digital Systems
1’s Complement Addition / Subtraction
 As Example 4, suppose we wish to substract –510 + 410.
 –510 = –01012 = 110102 in 1’s complement
–410 = –01002 = 001002 in 1’s complement
 Step 1: Add the binary numbers
 Step 2: Add the carry to lowest-order bit
110102
001002
0
111102
0
111102 = –00012
= –110
President University
Erwin Sitompul
Digital Systems 7/32
Lecture
Digital Systems
2’s Complement Representation
 The 2’s complement of a binary number involves inverting all bits
and adding 1.
 As example,
 2’s complement of 00110011 is 11001101
 2’s complement of 10101010 is 01010110.
 Thus, for an n-bit number N, the 2’s complement is 2n – 1 – N + 1 =
2n – N.
 To find the negative of a number, take the 2’s complement of that
number.
 For 2’s complement more negative numbers than positive.
000011002 = 1210
Sign bit
President University
Magnitude
111101002 = –1210
Sign bit
Erwin Sitompul
Magnitude
Digital Systems 7/33
Lecture
Digital Systems
2’s Complement Addition / Subtraction
 As Example 5, suppose we wish to add –510 + 910.
 –510 = –01012 = 110112 in 2’s complement
–910 = –10012 = 010112 in 2’s complement
 Step 1: Add the binary numbers
 Step 2: Discard the carry
110112
010012
1
President University
001002 = 410
Erwin Sitompul
Digital Systems 7/34
Lecture
Digital Systems
2’s Complement Addition / Subtraction
 As Example 6, suppose we wish to add –510 – 910.
 –510 = –01012 = 110112 in 2’s complement
–910 = –10012 = 101112 in 2’s complement
 Step 1: Add the binary numbers
 Step 2: Discard the carry
110112
101112
1
100102 = –11102
= –1410
President University
Erwin Sitompul
Digital Systems 7/35
Lecture
Digital Systems
2’s Complement Addition / Subtraction
 As Example 7, suppose we wish to substract 1310 – 510.
 1310 = –11012 = 011012 in 2’s complement
–510 = –01012 = 110112 in 2’s complement
 Step 1: Add the binary numbers
 Step 2: Discard the carry
011012
110112
1
President University
010002 = 810
Erwin Sitompul
Digital Systems 7/36
Lecture
Digital Systems
2’s Complement Addition / Subtraction
 As Example 8, suppose we wish to substract 510 – 1210.

510 = –01012 = 001012 in 2’s complement
–1210 = –11002 = 101002 in 2’s complement
 Step 1: Add the binary numbers
 Step 2: Discard the carry
001012
101002
0
110012 = –01112
= –710
President University
Erwin Sitompul
Digital Systems 7/37
Lecture
Digital Systems
Adder-Subtractor Circuit
 The following circuit is called an adder-subtractor. This circuit is
capable of adding and subtracting binary numbers.
 When D = 0, the circuit performs addition, S = A + B.
 When D = 1, the circuit performs subtraction, S = A – B. The XOR
Gates invert the value of B to its 2’s complement (C0 = 1).
D
President University
Erwin Sitompul
Digital Systems 7/38
Lecture
Digital Systems
Comparing the Signed Numbers
1.Signed magnitude:
 Negating is very easy  Just change the sign bit
 Adding or subtracting is difficult  If the signs are the same, add the
magnitudes and keep the sign. If the signs are different, subtract the
smaller operand from the larger operand. The sign of the result is the
same as the sign of the larger operand.
 Rather complex circuit is required.
2.1’s complement:
 Negating is easy  Invert the number but keep the sign bit.
 Adding and subtracting is much easier  Include the sign bits, add
directly. If there is carry, add it to the sum
 Simple but must differentiate cases where carry is 0 or 1.
3.2’s complement:
 Negating is not easy  Invert the number, keep the sign, add 1.
 Adding and subtracting is easy  Include the sign bits, add directly.
Ignore the carry, directly get the result.
 Simple circuit
President University
Erwin Sitompul
Digital Systems 7/39
Lecture
Digital Systems
Overflow in Binary Addition and Subtraction
 When two numbers of the same sign are added, the answer may
not fit the number of bits provided.
 In this case, the answer exceeds the magnitude which can be
represented with the allotted number of bits. This is called
overflow.
 In 2’s complement, overflow occurs when a transition is made from
2n–1 –1 to –2n–1 when adding or from –2n–1 to 2n–1 –1.
1111
1110
1101
1100
0000
–1 0
0001
0010
+1
–2
–3
+2
+3
–4
+4
–5
1011
–6
1010
1001
President University
0011
0100
+5
–7 –8 +7
1000
+6
0101
0110
0111
Erwin Sitompul
Digital Systems 7/40
Lecture
Digital Systems
Overflow in 4-bit 2 Complement Number
00
0010
0011
0101
2
3
5
01
0011
0110
1001
3
6
–7
Overflow
President University
11
1110
1101
1011
10
1101
1010
0111
00
0010
1100
1110
11
1110
0100
0010
–2
–3
–5
–3
–6
7
2
–4
–2
–2
4
2
Overflow
Erwin Sitompul
Digital Systems 7/41
Lecture
Digital Systems
Homework 7
1.Create a full adder by using NOR Gates only.
2.Convert 1 0111 01102 to decimal from
i. signed magnitude
ii. 1’s complement
iii. 2’s complement
3.Calculate the following equations using signed magnitude:
–810 – 1010 =
2310 – 1710 =
4.Calculate each of the following equations using 1’s and 2’s
complement:
–310 – 1010 =
2210 – 3010 =
 Deadline: Tuesday, 15 November 2016.
President University
Erwin Sitompul
Digital Systems 7/42