Transcript EE208 Chapter 1 - Digital Systems and Binary Numbers

1
EE 208 – Logic Design
Chapter 1
Digital Systems and Binary
Numbers
Sohaib Majzoub
2
Digital Electronics …. Everywhere
3
Objective
LEARN BASICS BEHIND COMPUTER SYSTEMS
• Hardware architecture and organization
• Digital logic design
– Switching and logic gate design
• Computer architecture building blocks
–
–
–
–
Adders/subtractors/counters
Shift/rotate registers
Multiplexers/demultiplexers and encoders/decoders
Controllers and sequencers
4
Generic Computer System
5
Hierarchy in a System
6
NAND Gate Example
7
Analog and Digital Signal
X(t)
Sampled
Quantized
t
Analog signal
Analog signals vary
continuously over a specified
range with infinite values.
7
Digital
Digital signals can assume
only finite values.
8
Binary Logic Levels
9
Number Systems
• Number Systems?
• What are the different forms to represent the number
systems?
–
–
–
–
Decimal
Hexadecimal representation
Binary representation
Arithmetic Operations
Decimal Number System
• Radix or base is equal to 10, e.g. N = 1256.932
N = 1x103+2x102+5x101+6x100+9x10-1+3x10-2+2x10-3
10
11
Polynomial Representation of Numbers
an is the most significant digit or MSD and
a-m is the least significant digit or LSD
• Radix or base can be any integer, most known systems are
- r = 2 (binary)
- r = 3 (Ternary)
- r = 4 (Quaternary)
- r = 8 (Octal)
- r = 16 (Hexadecimal)
Commonly Used Number Systems
Name
Radix
Decimal Binary Octal Hexadecimal
10
2
8
16
Possible 0 to 9
digit
values
0 and 1 0 to 7 0 to 9
A to F
12
Number Systems
13
Conversion to Decimal
14
• Binary to Decimal: N = (11010.1101)2
• N = 1x24 +1x23 +0x22 +1x21 +0x20 +1x2-1 +1x2-2 +0x2-3
+1x2-4 = 26.8125
Conversion to Decimal
15
• Octal: N = (4 5 2 6 . 2 3)8
N = 4x83 +5x82 +2x81 +6x80 +2x8-1 +3x8-2 = 2390 + 19/64
• Hexadecimal: N = (A 1 F .1 C)16
N = Ax162 +1x161 +Fx160 +1x16-1 +Cx16-2 =2592+28/256
Conversion from Decimal
• Radix Divide Technique: Divide the given integer
successively by the target radix, noting the reminder in
each step, until the quotient is zero. Collect the from each
step starting from last to first.
• Convert (245)10 = (?)2
16
Conversion from Decimal
• Convert: (245)10 = (?)8
• Convert: (245)10 = (?)16
17
Conversion from Decimal
• Radix Multiply Technique: Successively multiply the
given fraction by the required base, noting the integer
portion of the product at each step. Collect the integer
digits starting from first to last.
• Convert: (0.345)10 = (?)2
18
Conversion from Decimal
• Covert: (242.45)10= (?)2
19
20
Conversion Between Systems
• From Binary to:
– Octal: arrange bits in groups of 3 and substitute
(10111011001)2 = (010 111 011 001)2 = (2731)8
– Hex: arrange bits in groups of 4 and substitute (10111011001)2
= (0101 1101 1001)2 = (5D9)16 = (5D9)H
Each single hex digit (4 bits) is called a nibble
– Decimal: use general positional summation method
(10111011001)2 = 1x210 + 0x29 + 1x28 + 1x27 +
1x26 + 0x25 + 1x24 + 1x23 + 0x22 + 0x21 + 1x20 = (1497)10
21
Conversion Between Systems
• From Octal to:
– Binary: Substitute each Oct digit with 3 binary bits
(1234)8 = (001 010 011 100)2
– Hex: Convert to binary, then to Hex
(1234)8 = (001 010 011 100)2
= (0010 1001 1100)2 = (29C)16
– Decimal: use general positional summation method
(1234)8 = 1x83 + 2x82 + 3x81 + 4x80
= 1x512 + 2x64 + 3x8 + 4x1 = (668)10
Conversion Between Systems
• From Hex to:
– Binary: Substitute each Hex digit with 4 binary bits
(C0DE)16 = (1100 0000 1101 1110)2
– Octal: Convert to binary, then to Hex
(C0DE)16 = (1100 0000 1101 1110)2
= (001 100 000 011 011 110)2 = (140336)8
– Decimal: use general positional summation method
(C0DE)16 = 12x163 + 0x162 + 13x161 + 14x160
= 12x4096 + 0x256 + 13x16 + 14x1 = (49374)10
22
Arithmetic
23
• Arithmetic rules in all Number Systems are the same (-, +,
*, / ), just remember the base
• Binary Arithmetic:
Binary Addition
Binary Arithmetic
• Binary Subtraction:
• Binary Multiplication:
24
Binary Arithmetic
• Binary Division
25
Representation of Negative Numbers
• Why do we need a negative representation?
• Computers do not understand the negative sign.
• Example: (178)10 is equivalent to (10110010)2
• Sign-Magnitude system: bn-1bn-2 …… b1b0
Sign N-1 magnitude bits
bit
• Example:
-178
- 10110010 is equivalent to 1 10110010
+178
+10110010 is equivalent to 0 10110010
• If the computer has 9 bits to represent numbers use the
MSB for the sign
26
The Complement Number System
• A complement is a negative representation of a positive
number (and vice versa)
• The complement of a number (N)r defined by:
• Twos Complement when r = 2 (Binary System)
• Examples:
- The twos complement of (01010)2 is
25 – (01010) = 100000 – 01010 = 10110
• Complement numbers simplify subtractions
– Subtraction is converted to addition
– Simplifies hardware implementation
27
Twos Complement
• A shortcut to find the Twos complement:
• Similar to regular binary addition
• Ignore carry out of MSB
28
Ones Complement
• Another method to represent negative numbers, same as
Two complement but do not add one.
• Example: the ones complement of (01010)2 is 10101.
29
Negative Representation in Computers
30
Subtractions with Twos Complement
• Twos complement to represent negative numbers or
subtractions.
• Example: A – B means A + (-B), i.e. calculate the Twos
complement of B, and then add both.
• Consider A =5, B =4, then A + B is
• Consider A – B, or A + (-B), then
31
Subtractions with Twos Complement
• B – A or B + (-A) then:
32
Subtraction with Ones Complement
• A=5, and B = 4, then A + (– B) is equal to:
• Consider B + (– A):
33
34
Overflow
• What is overflow?
– Result of arithmetic exceeds the range
• i.e. No enough bits to represent number
Example: using 4 bit two’s complement binary:
6 + 5 = 11

0110 + 0101 = 1011 = -5 WRONG!
The result 11 cannot be represented with 4 bits using two’s complement
notation
When Will Overflow Occur?
• In unsigned arithmetic:
– Adding two positive numbers, if we have a carry out from the
MSB, then overflow occurred (overflow = MSB carry out)
– Example: using 4 bit unsigned binary:
9 + 10 = 19
 1001 + 1010 = 1 0011 = 3
Overflow!
• In signed two’s complement arithmetic:
– Adding a positive and a negative number: overflow can never
happen. Why? The result is always between the two numbers 
can be represented with same number of bits
– Adding two positive or two negative numbers, overflow can
happen.
How to detect?
If sign of result is different than sign of two numbers being
added  Overflow
Remember: Carry out from MSB is always ignored!
35
36
Overflow Examples
• Add the following 8-bit two’s complement numbers. Find
if there is an overflow or not.
10010110
01110100
------------
11011010
10010010
------------
01101110
01011101
------------
Binary Coded Decimal
• Computers operate on binary numbers, but when
communicate with humans, they use decimal.
• Conversion from binary to decimal and decimal to binary
is necessary.
• The digits 0 to 9 are coded into binary bits (this is not
decimal  binary conversion, it is digit coding)
• In the BCD code, each decimal digit is represented by 4
bits. The BCD code is the 8,4,2,1 code.
• BCD is a weighted code (8, 4, 2, and 1 are weights)
• This code is the simplest, most intuitive binary code for
decimal digits and uses the same powers of 2 as a binary
number, but only encodes the first ten values from 0 to 9.
37
38
BCD Code
• Binary Coded Decimal (BCD)
– Decimal number 86 is
represented in BCD with 8 bits
as 1000 0110, with each group of
4 bits is an input to a seven
segment display.
– A decimal number in BCD is
the same as its equivalent binary
number only when the number is
between 0 and 9.
– The binary combinations 1010
through 1111 are not used.
39
• Example:
BCD Code
– Consider decimal number 185 and its corresponding value in
BCD and binary:
• BCD addition (hint: Add +6 if the sum >9)
40
BCD Code
• Example:
– Consider the addition of 184 + 576 = 760 in BCD:
41
Gray Code
– Advantage: only one bit is
changed between any two
successive codes
42
ASCII Code
• American Standard Code for Information Interchange (ASCII)
42
43
ASCII Properties
– Digits 0 to 9 span Hexadecimal values 3016 to 3916
– Upper case A-Z span 4116 to 5A16
– Lower case a-z span 6116 to 7A16
– Lower to upper case translation (and vice versa)
occurs by flipping bit 6.
44
Other Codes
45
Error Detection
• Error-Detecting Code
– To detect errors in data communication and processing, an
eighth bit is sometimes added to the ASCII character to indicate
its parity.
– A parity bit is an extra bit included with a message to make the
total number of 1's either even or odd.
• Example: characters with even and odd parity
Warning: Conversion or Coding?
• Do NOT mix up conversion of a decimal number to a
binary number with coding a decimal number with a
BINARY CODE.
• 1310 = 11012 (This is conversion)
• 13  0001|0011 (This is coding)
46
47
UNICODE
• UNICODE extends ASCII to 65,536 universal
characters codes
– For encoding characters in world languages
– Available in many modern applications
– 2 byte (16-bit) code words
Chapter 1