UCCD1133
Introduction to Computer Organisation and Architecture
Chapter 3
Basic Concept of Logic
Disclaimer
• This slide may contain copyrighted material of which has not been specifically authorized by the copyright owner. The use of copyrighted materials are solely for educational purpose. If you wish to use this copyrighted material for other purposes, you must first obtain permission from the original copyright owner.
2
Chapter 3-5
Combinational Circuits Building Blocks
3
Outcome
1. Describe the commonly used computational circuits building blocks:
• Decoder
• Multiplexer • Adder
2. Defineanddetectoverflow
4
Combinational Circuit
❑ Example of non-arithmetic building blocks:
Decoder
Encoder and priority encoder Demultiplexer
Multiplexer
❑ Example of arithmetic building blocks:
Adder
Subtractor
ALU (Arithmetic and Logic) Multiplier
Diviser
Comparator
Shifter
❑ What is standard circuits? Pre-designed circuits with at least
correct functionalities
– They speed up design work (modelling based on schematic, verification and implementation)
– Collected as part of library
5
Decoder
❑ A decoder:
Converts one type of code, x[n-1:0], into another type, y[2n-1:0]. The enable inputs, en – to enable/ disable the outputs.
n-to-2n decoder
x[0] y[0] x[1] y[1]
x[n-1] en[0]
y[2n – 1]
decoder3to8
y[0] y[1] y[2] y[3] y[4] y[5] y[6] y[7]
decoder2to4
y[0] y[1] y[2]
en y[3]
a[0] a[1]
a[0] a[1] a[2]
en
LSB
. .
. . .
.
Also known as n-to-2n decoder – e.g. 3-to-8 decoder. – Has n inputs and 2n outputs.
Only one output (1-out-of-2n) can be asserted
– To indicate/ identify the code that has been placed at input.
❑ Other types of decoder: display decoder
Inputs in code
form MS B.
Outputs in another code form
Enable Inputs
❑ A binary decoder
Most basic type of decoder
6
Example: 2-to-4 Binary Decoder
❑ Block diagram
First, determine the interfaces : 2 inputs and 4 outputs, plus one enable input.
decoder2to4
y[0] y[1] y[2]
en y[3]
a[0] a[1]
2
4
decoder2to4
a[1:0] y[3:0] en
❑ Functional behaviour
The functional behaviour (the in-out relationship) for
binary decoder:
– only an output (1-out-of-2n) can be asserted when a code is applied to the inputs.
❑ Logic function
❑ From the truth table: y[0] = en (a[1]’a[0]’) y[1] = en (a[1]’a[0]) y[2] = en (a[1] a[0]’) y[3] = en (a[1] a[0])
❑ Implementation using basic logic gates
Inputs
Outputs
en a[1] a[0]
y[3] y[2] y[1] y[0]
0dd 100 101 110 111
0000 0001 0010 0100 1000
a[0] a[1]
en
y[0] y[1] y[2] y[3]
7
Decoder Application 1: Minterm Generation
❑ Notice the outputs of binary decoder represent all possible minterms. Can be used as a minterm generator.
❑ Example
Implement the following functions.
f(A,B,C) = m1 + m4 +m7: use a decoder (with active-high outputs) with an OR gate. f(A,B,C) = (m1’ m4’ m7’)’: use a decoder (with active-low outputs) with a NAND gate. f(A,B,C) = m2’ m3’ m5’: use a decoder (with active-low outputs) with an AND gate.
❑ Solution
aaa bbb cfcfc
(a) (b)
f
y[0] a y[1] b y[2] c y[3] y[4]
y[5] y[6] y[7]
y[0] a y[1] b y[2] c y[3] y[4] y[5] y[6] y[7]
y[0] a y[1] b y[2] c y[3] y[4]
y[5] y[6] y[7]
(c)
8
Decoder Application 2: Device Enable/Control
❑ Example 1
A 4-to-16 binary decoder to selectively enable one out of 7 I/O devices.
9 outputs are not used.
Only one device is allowed to be active at any time.
9
Display Decoder
❑ A display decoder converts a code into a suitable format to drive a numeric display (LCD, 7-segment display, dot matrix display, etc)
❑ Example
7-segment display decoders (BCD-to-
7 segment decoders)
Available in the market as standard components 7447 and 74X49.
Inputs
Outputs
wxyz
a
b
c
d
e
f
g
0000 0001 0010 0011
1 0 1 1
1 1 1 1
1 1 0 1
1 0 1 1
1 0 1 0
1 0 0 0
0 0 1 1
0100 0101 0110 0111
0 1 1 1
1 0 0 1
1 1 1 1
0 1 1 0
0 0 1 0
1 1 1 1
1 1 1 0
1000 1001
1 1
1 1
1 1
1 1
1 0
1 1
1 1
1010 1011 1100 1101 1110 1111
d d d d d d
d d d d d d
d d d d d d
d d d d d d
d d d d d d
d d d d d d
d d d d d d
w x y z
10
Multiplexer (Data Selector)
2n sources
of data inputs
Select
❑ A multiplexer (mux) is a circuit that has: • 2n data inputs
b b
mux 2n-to-1 d0[b-1:0]
d1[b-1:0] y[b-1:0]
d(2n-1)[b-1:0]
sel[s-1:0] en
• s data selectors (control inputs) • An output
. .
b
Data output
❑ It is used as a digital switch
. b s
• Connects data from one of 2n sources to the output, based on the select signals, sel[s-1:0].
❑ Like many other circuits, the mux can have additional enable input signal, en
Enable
Block diagram of 2n-to-1 mux
• The s-bit must meet the condition s≥n
• •
To enable or disable the operation of the mux
Set the output to z
d[0] 0 d[1] 1 d[2] 2 d[3] 3
sel[1:0]
out
d[0]
d[1]
d[2]
d[3] d[4]
d[5] d[6] d[7]
0 1 2 3 4 5 6 7
out
Graphical symbol of 4-to-1 mux and 8-to-1 mux
sel[2:0]
11
Example: 4-to-1 Multiplexer
❑ Block diagram
A basic 4-to-1 multiplexer has the following signals.
The output signal y.
The input signals, d[3:0].
Since the multiplexer has 4 data inputs, it required 2 bits data-select (4 = 22).
mux4to1
d[0] d[1] d[2] d[3]
s[1] s[0]
y
❑ Functional behaviour ❑ Logic function
The logic function of the multiplexer:
y = s[1]’s[0]’d[0] + s[1]’s[0] d[1] + s[1]s[0]’d[2] + s[1]s[0]d[3]
s[1] s[0]
y
00 01 10 11
d[0] d[1] d[2] d[3]
12
Application: Minterm Generation
❑ Select inputs -> generates minterms, while data lines are used to enable the minterms
❑ Example 1
Use a 8-to-1 multiplexer to realize f(J,K,L) = m(0, 2, 3, 5).
❑ Solution
List the truth table for the function.
Then map the content of the truth table to the mux.
‘1’
VCC
JK L
f
000 001 010 011 100 101 110 111
1 0 1 1 0 1 0 0
d[0] d[1] d[2] d[3] d[4]
Y d[5]
d[6] d[7]
G ABC
f
‘0’
JKL 13
Application: Minterm Generation
❑ Example 2
(a) Implement f(a,b,c) = ab + b’c using 4-to-1 mux if a and b are used as the select signal of the mux.
(b) Implement the above function using one 2-to-1 mux and some basic gates if a is used as the select signal of the mux.
❑ Solution Part (a)
Derive the reduced inputs (Mux inputs)
abc
f
Mux inputs
000 001
0 1
d[0] = c
010 011
0 0
d[1] = 0
100 101
0 1
d[2] = c
110 111
1 1
d[3] = 1
Express the logic function in canonical form. c
0 f
1
ab
If not specified, other variables can
be used as the select input
f =ab+b’c
= ab(c’ + c) + b’c(a’ + a) c
The final result:
d[0] d[1] d[2] d[3]
y s[1] s[0]
= abc’ + abc + a’b’c + ab’c Construct its truth table.
14
Application: Minterm Generation
❑ Solution Part (b)
From(a), we know that
f =abc’+abc+a’b’c+ab’c
Construct its truth table and derive the mux inputs.
The final result:
b’.c b+c
f
d[0]
y
d[1] s
a
abc
f
Mux inputs
000 001 010 011
0 1 0 0
d[0] = b’.c
100 101 110 111
0 1 1 1
d[1] = b + c
If not specified, other variables can be used as the select input
15
Application of Mux/Demux: Data Routing/Transmission*
❑ Data must be switched from multiple sources to a destination. ❑ Example
Design a 16-line to 16-line mux/demux system.
The purpose of the system is to reduce the number of wires used for transmission
mux16to1
E[0] E[1] E[2] E[3] E[4] E[5] E[6] E[7] E[8] E[9] E[10] E[11] E[12] E[13] E[14] E[15]
DCBA
Y
demux1to16
E[0] E[1] E[2] E[3] E[4] E[5] E[6] E[7] E[8] E[9]
E[10] E[11] E[12] E[13] E[14] E[15]
D0
DCBA
x[0] x[1] x[2] x[3] x[4] x[5] x[6] x[7] x[8] x[9]
x[10] x[11] x[12] x[13] x[14] x[15]
16 lines
C[3] C[2] C[1] C[0]
x[0] x[1] x[2] x[3] x[4]
Single data x[5] channel x[6]
x[7] x[8] x[9] x[10] x[11] x[12] x[13] x[14] x[15]
16 reduced to 5 lines
16
Adder
❑ Addition is one of the most common operation in digital systems. ❑ Adder is an arithmetic circuit that adds two n-bit binary numbers. ❑ Can be implemented in combinational or sequential logic.
❑ Terminology for addition operation:
111102 + 011002 = 010102
Augend
Sum
The carry bit 1 is called the carry output, Cout of the third column and the carry in, Cin to the fourth column of addition.
Addend
11110 Augend 1 1 1 0 0 0 Carries
+01100 Addend 01010 Sum
17
Half-Adder
❑ A half-adder is a logic circuit that performs a single bit addition. It adds two bits, x and y, and produces two outputs, a sum bit and a carry out bit.
❑ There is no carry-in input carry-in is treated as 0.
❑ Block diagram:
❑ Truth table:
add_half
cout y half_sum
x
xy
cout half_sum
00 01 10 11
00 01 01 10
18
Full-Adder
❑ The main difference between a full adder and half-adder is that a full adder accepts the carry in cin.
❑ Block diagram:
add_full
x
y cin
cout sum
❑ Truth table:
cin x y
cout sum
000 001 010 011
00 01 01 10
100 101 110 111
01 10 10 11
19
n-bit Adder: Carry-Ripple Adder (cra)
❑ n-bit carry-ripple adder adds 2 n-bit binary numbers (signed and unsigned) Result is (n+1)-bit: n-bit sum and a carry-out.
Each bit position requires a full-adder
❑ Principle in constructing an n-bit carry-ripple adder Cascading n full-adders (FA) through a chain of carry signals.
FA(i).cout => FA(i+1).cin
where i = 0, 1, …. n-1
a[n-1] b[n-1] c[n-1]
……
m sum[n-1]
a[1] b[1]
Connect to top- level carry-in pin
a[0] b[0] cin
c[0]
m
xy
FA(n-1)
cout su
cout
sum[1
sum[0
c[2]
c[1] ]]
x ycin
FA1
cout sum
x y cin
FA0
cout su
cin
20
Subtracter Constructed from Adder
❑ Subtraction can be carried out using the adder circuit Based on the 2’s complement arithmetic
1
A[n-1:0] n
B[n-1:0] n n
borrow
n diff[n-1:0]
D2 = A2 – B2 = A2 + [B]2
=A2 +(B2)’+1
addn
cout a[n-1:0] sum[n-1:0]
cin b[n-1:0]
(a)
(b)
❑ However, the circuit can only perform one function i.e. subtraction. Cannot perform addition.
❑ To perform both add and subtract functions, combine the adder and subtracter circuits into one.
subn
A[n-1:0] borrow B[n-1:0] diff[n-1:0]
21
Subtraction/Addition Implementation Based on 2’s Complement Arithmetic
❑ Construction of binary adder used to perform both addition and subtraction.
operand_a[3:0] operand_b[3:0]
To channel the correct data for subtract or add operation.
We can also use XOR gates in place of the muxes.
w[3:0] v[3:0] mux S
y[3:0]
select
carry_out
sum[3:0]
a[3:0]
s[3:0]
b[3:0]
c4
add4
c0
Signals
Addition Operation
Subtraction Operation
select
select = 0
Mux output, y[3:0] = w[3:0] = operand_b[3:0]
select = 1
Mux output, y[3:0] = v[3:0] = operand_b[3:0]’
c0
c0 = select = 0
c0 = select = 1
sum[3:0]
sum[3:0] = a[3:0] + b[3:0] + c0
= operand_a[3:0] + y[3:0] + 0
= operand_a[3:0] + w[3:0]
= operand_a[3:0] + operand_b[3:0]
sum[3:0] = a[3:0] + b[3:0] + c0
= operand_a[3:0] + y[3:0] + 1
= operand_a[3:0] + v[3:0] + 1
= operand_a[3:0] + operand_b[3:0]’ + 1
22
Overflow
❑ Two’s complement numbers (2cns) uses complement arithmetic. E.g. (A – B) can be performed by computing A + (-B) = A + B2c
– Only need a binary adder and complementing circuits to handle both add and subtract.
Easy hardware implementation.
❑ One problem of digital systems is that it have limited bits for data representation (limited range of signed values).
The decimal range for an n-bit digital system using 2cns is (-2n-1) N (2n-1 – 1). E.g. an 8-bit digital system can only operate on values between -128 to 127.
❑ If the result is out of the range, signed overflow occurs. – The out-of-range result cannot be used.
– Shoulddesigndigitalsystemthatgeneratesawarningsignal – Sothatinvalidnumbersarenotmistakenforcorrectresults.
23
Overflow: Signed and Unsigned Numbers
❑ The computation for signed and unsigned overflows are not the same. ❑ Example
Compute (– 9 – 5).
-9-5 =(-9)+(-5)
= [01001] + [00101]
= 101112c + 110112c
Signed addition: input and output numbers treated as signed
(- 9) + (- 5)
Unsigned addition: input and output numbers treated as unsigned
2 3 + 2 7 5 0
1 0 1 1 12c + 1 1 0 1 12c 1 1 0 0 1 02c
– 1 4
❑ For unsigned arithmetic, carry out indicates an overflow.
Carry out
❑ For signed numbers, the carry out from the sign-bit is not sufficient to determine the overflow.
It is meant for extending the adder circuit to higher order bits.
However, overflow can be detected by observing the carry into the sign-bit position and the carry out of the sign-bit position. If these two carries are not equal, an overflow has occurred.
24
Overflow: 2’s Complement Arithmetic for Signed Numbers
❑ The following 3 case studies are useful for detecting and analysing overflow. ❑ Assume B and C are positive in a 5-bit system (range represented: -16 to 15).
❑ Case study 1: A = B + C Compute 12 + 7.
❑
Case study 2: A = – B – C
0 1 1 0 02c + 0 0 1 1 12c 1 0 0 1 12c
1 2 7 + 1 9
Compute (–12 – 5). – 12 – 5 = (-12) + (-5)
= [01100] + [00101] = 101002c + 110112c
1 0 1 0 02c + 1 1 0 1 12c 1 0 1 1 1 12c
+
Result shows an incorrect sign bit (indicates overflow)
Addition of two positive numbers produce a negative result
[10011]2c = -011012 = -13
-13 is incorrectly interpreted due to overflow Sum requires > 5 bits to represent it
Carry discarded
(-1 2) + (- 5)
– 1 7
Result shows an incorrect sign bit (indicates overflow)
Addition of two negative numbers produce a positive result
Incorrectly interpreted as 15 due to overflow
Overflow rule for addition:
If two 2’s complement numbers with the same sign are added, then overflow occurs if: – adding two positive numbers give a NEGATIVE result.
– adding two negative numbers give a POSITIVE result.
25
Overflow: 2’s Complement Arithmetic for Signed Numbers
❑ Case study 3: A = B – C
The magnitude of (B – C) will always be less than either of the two numbers. Overflow can never occur
Compute 12 – 5. 12-5 =12+(-5)
= 01100 + [00101] = 011002c + 110112c
0 1 1 0 02c + 1 1 0 1 1 2c 1 0 0 1 1 1 2c
Carry discarded
1 2 + (- 5) + 7
The carry generated can be discarded It’s not a valid carry
– B > C shouldn’t generate a carry
26