PowerPoint Presentation
REVISION
Bernhard Kainz
b.kainz@imperial.ac.uk
mailto:b.kainz@imperial.ac.uk
Boolean Algebra – Truth Tables
• All possible outcomes of the operators can be written as
truth tables
Boolean Algebra – Rules
• Note: A and B can be any Boolean Expression
Negation:
(A’)’ = A
A • A’ = 0
A + A’ = 1
Associative:
(A • B) • C = A • (B • C)
(A + B) + C = A + (B + C)
Commutative:
A • B = B • A
A + B = B + A
Distributive:
A • (B + C) = A • B + A • C
A + (B • C) = (A + B) • (A + C)
Note the precedence
Boolean Algebra – Rules
Single variables (Idempotent law):
A • A = A
A + A = A
Simplification rules with 1 and 0:
A • 0 = 0
A • 1 = A
A + 0 = A
A + 1 = 1
Boolean Algebra – de Morgan’s Rule
(A + B)’ = A’ • B’
(A • B)’ = A’ + B’
as before, A and B can be any Boolean expression
Can generalise to n Boolean variables:
(A + B + C + D + …)’ = A’ • B’ • C’ • D’ • …
(A • B • C • D • … • X)’ = A ‘ + B’ + C’ + D’ + … + X’
Half Adder
• Recall
• Truth Table
0 0 1 1
+ 0 1 0 1
00 01 01 10
A B A + B Sum Carry
0 0 0 0 0
0 1 1 1 0
1 0 1 1 0
1 1 2 0 1
Full Adder
S = A⊕ B⊕ Cin
Cout = (A • B) + Cin • (A ⊕ B))
Full Adder
• Conceptually
1-Bit Full
Adder
A B
Cout Cin
S
Latches
• SR-Latch: Truth table
S R Q Q’
0 0 Latch
0 1 0 1
1 0 1 0
1 1 Undefined
Memory
• Useful variation on the SR latch circuit is the Data latch,
or D latch
• Constructed by using the inverted S input as the R input
signal
• Allows for a single input No race condition as input is inverted
Memory
• Memories hold binary values
• Data (e.g. Integers, Reals, Characters)
• CPU Instructions (i.e. Computer Programs)
• Memory Addresses (“Pointers” to data or instructions)
• Contents remain unchanged unless overwritten with a
new binary value
• Some of them lose the content when power is turned off (volatile
memory)
Computer Architecture
Input/Output Controllers
RAM RAM
Main Memory
Arithmetic & Logic Unit (ALU)
Registers
Control
Unit
CPU
Hard Disk
DVD Drive
Memory Stick
Mouse,
Keyboard
Monitor, Printer,
Scanner
Ethernet
Modem
Wifi
Bluetooth
GSM/GPRS
Speakers,
Microphone,
Camera, Game
Devices
Summary
Registers
RAM
Hard Disk
expensive cheapCOST
small largeCAPACITY
high lowVOLATILITY
slower
SPEED
faster
difficult
FLEXIBILITY
USABILITY
easier
Cache
Byte Addressing (Big Endian)
Main Memory
1
3
5
7
9
11
13
15
Byte Address
0
2
4
6
8
10
12
14
Byte Address
0110 1101 1010 1101
0000 0000 0000 0011
0000 0000 0000 0000
1111 1111 1111 1111
0000 0000 0000 0000
1001 1010 1010 0010
0000 0000 0000 0000
1111 1111 1111 1110
Byte Addressing (Little Endian)
Main Memory
0
2
4
6
8
10
12
14
Byte Address
1
3
5
7
9
11
13
15
Byte Address
0110 1101 1010 1101
0000 0000 0000 0011
0000 0000 0000 0000
1111 1111 1111 1111
0000 0000 0000 0000
1001 1010 1010 0010
0000 0000 0000 0000
1111 1111 1111 1110
1GB (256M x 32-bit) Memory
256M
rows
32 bits
1GB (256M x 32-bit) Memory
• Four 256MB memory modules
• Each module has four 64M x 8-bit RAM Chips
8
Module 0
256MB
Module 1
256MB
Module 2
256MB
Module 3
256MB
64M
8 8 8
64M
64M
64M
Memory Interleaving
• Example:
• Memory = 4M words, each word = 32-bits
• Built with 4 x 1M x 32-bit memory modules
• For 4M words we need 22 bits for an address
• 22 bits = 2 bits (to select Modules) + 20 bits (to select row within
Module)
Row within Module
220
Low-Order Interleave
High-Order Interleave
Module
Row within Module
2 20
Module
MSI Chips – Multiplexer
• A multiple-input, single-output switch
• Also called MUX for short ☺
• sel selects which of I0 or I1 is mapped to the output
• For example, sel = 0 selects I0 and sel = 1 selects I1
• Example is called a 2-to-1 MUX
• With n selects/control lines, we can have 2n input lines
MSI Chips – Decoder
• Only one output is 1 – the
one selected by the n-bit
binary input number – the
rest are zero
• Useful in transmitting line
selection with fewer wires
(e.g. selecting a memory
chip)
MSI Chips – Decoder
• Truth Table
A B C D7 D6 D5 D4 D3 D2 D1 D0
0 0 0 0 0 0 0 0 0 0 1
0 0 1 0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0 1 0 0
0 1 1 0 0 0 0 1 0 0 0
1 0 0 0 0 0 1 0 0 0 0
1 0 1 0 0 1 0 0 0 0 0
1 1 0 0 1 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0 0 0
MSI Chips – Calculations – Comparator
• The comparator returns 1
if the two n-bit inputs A and
B are equal, 0 otherwise
MSI Chips – Calculations – Bit-shifter
• Faster calculations for powers of 2
• Shift left and right (multiply and divide)
• c = 0 shift left
• c = 1 shift right
The Arithmetic Logic Unit (ALU)
• The ALU is able to perform
multiple functions
• Depending on the input to
the decoder (F0,F1) one of
four functions is selected –
A and B, A or B, not B,
arithmetic A+B
Data representation
Bit Pattern 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
Unsigned 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Sign &
Magnitude
+0 +1 +2 +3 +4 +5 +6 +7 −0 −1 −2 −3 −4 −5 −6 −7
1s
Complement
+0 +1 +2 +3 +4 +5 +6 +7 -7 -6 -5 -4 -3 -2 -1 -0
2s
Complement
+0 +1 +2 +3 +4 +5 +6 +7 -8 -7 -6 -5 -4 -3 -2 -1
Excess-8 -8 -7 -6 -5 -4 -3 -2 1 0 1 2 3 4 5 6 7
BCD 0 1 2 3 4 5 6 7 8 9 – – – – – –
ASCII Character Set
Bit positions 654
Bit positions
3210
000 001 010 011 100 101 110 111
NUL DLE SP 0 @ P ‘ p 0000
SOH DC1 ! 1 A Q a q 0001
STX DC2 “ 2 B R b r 0010
ETX DC3 # 3 C S c s 0011
EOT DC4 $ 4 D T d t 0100
ENQ NAK % 5 E U e u 0101
ACK SYN & 6 F V f v 0110
BEL ETB ‘ 7 G W g w 0111
BS CAN ( 8 H X h x 1000
HT EM ) 9 I Y i y 1001
LF SUB * : J Z j z 1010
VT ESC + ; K [ k { 1011
FF FS , < L \ l | 1100 CR GS - = M ] m } 1101 SO RS . > N ^ n ~ 1110
SI US / ? O _ o DEL 1111
Strings are represented as sequence of characters. E.g. Fred is encoded as follows:
English F r e d
ASCII (Binary) 0100 0110 0111 0010 0110 0101 0110 0100
ASCII (Hex) 46 72 65 64
Two’s Complement – BNA Summary
• Addition
• Add the values, discarding any carry-out bit
• Subtraction
• Negate the subtrahend and add, discarding any carry-out bit
• Overflow
• Adding two positive numbers produces a negative result
• Adding two negative numbers produces a positive result
• Adding operands of unlike signs never produces an overflow
• Note – discarding the carry out of the most significant bit during
Two’s Complement addition is a normal occurrence, and does not
by itself indicate overflow
Floating point zones of expressibility
• Example: assume numbers are formed with a signed 3-
digit coefficient and a signed 2-digit exponent
• Zones of expressibility:
Normalised forms (base 10)
Number Normalised form
23.2 × 104 2.32 × 105
−4.01 × 10−3 −4.01 × 10−3
343 000 × 100 3.43 × 105
0.000 000 098 9 × 100 9.89 × 10−8
Binary fraction to decimal fraction
• What is the binary value 0.01101 in decimal?
•
1
4
+
1
8
+
1
32
=
13
32
= 0.40625
•
8+4+1
25
=
13
32
• What about 0.000 110 011?
• Answer:
32+16+2+1
29
=
51
512
= 0.099 609 375
𝟐−𝟏 𝟐−𝟐 𝟐−𝟑 𝟐−𝟒 𝟐−𝟓
. 0 1 1 0 1
𝟑𝟐 𝟏𝟔 𝟖 𝟒 𝟐 𝟏
. 0 1 1 0 1
Floating point multiplication
𝑁1 × 𝑁2 = 𝑀1 × 10
𝐸1 × 𝑀2 × 10
𝐸2
= 𝑀1 ×𝑀2 × 10
𝐸1 × 10𝐸2
= 𝑀1 ×𝑀2 × 10
𝐸1+𝐸2
• That is, we multiply the coefficients and add the
exponents
• Example:
2.6 × 106 × 5.4 × 10−3 = 2.6 × 5.4 × 103
= 14.04 × 103
• We must also normalise the result, so final answer is
1.404 × 104
Floating point addition
• A floating point addition such as 4.5 × 103 + 6.7 × 102 is not a
simple coefficient addition, unless the exponents are the same.
Otherwise, we need to align them first
𝑁1 +𝑁2 = 𝑀1 × 10
𝐸1 + 𝑀2 × 10
𝐸2
= 𝑀1 +𝑀2 × 10
𝐸2−𝐸1 × 10𝐸1
• To align, choose the number with the smaller exponent and
shift its coefficient the corresponding number of digits to the
right
4.5 × 103 + 6.7 × 102 = 4.5 × 103 + 0.67 × 103
= 5.17 × 103 = 5.2 × 103
(rounded)
IEEE Single precision format (32-bit)
• Coefficient is called the significand in the IEEE standard
• Value represented is ±𝟏. 𝑭 × 𝟐𝑬−𝟏𝟐𝟕
• The normal bit (the 1.) is omitted from the significand
field a hidden bit
• Single precision yields 24 bits (approx. 7 decimal digits
of precision)
• Normalised ranges in decimal are approximately:
−𝟏𝟎𝟑𝟖 to −𝟏𝟎−𝟑𝟖, 0, 𝟏𝟎𝟑𝟖 to 𝟏𝟎−𝟑𝟖
Sign
S
1 bit
Exponent
E
8 bits
Significand
F
23 bits
Special values
• IEEE formats can encode five kinds of values: zero,
normalised numbers, denormalised numbers, infinity
and not-a-number (NaNs)
• Single precision representations:
IEEE value Sign
field
Exponent Significand True
exponent
Value
±0 0 or 1 0 0 (all zeros) ±0.0 x 20
± denormalised no. 0 or 1 0 Any non-zero bit
pattern
−126 ±0. F x 2
_126
±normalised no. 0 or 1 1…254 Any bit pattern −126…127 ±1. F x 2E
_127
±∞ 0 or 1 255 0 (all zeros) ±1.0 x 2128
Not-a-number 0 or 1 255 Any non-zero bit
pattern
±1. F x 2128