Transcript Digital Systems

Chapter 1: Binary Systems
Topics in this Chapter:
•
•
•
•
•
•
•
•
Digital Systems
Numbering Systems
Number Base Conversions
Complements
Arithmetic Operations
Binary Coded Decimal (BCD)
Binary Storage and Registers
Binary Logic
A.Abhari
CPS213
1
Digital Systems
• Discrete quantities: weekly salaries, income
taxes, letters or alphabet, digits
• Digital systems: digital telephones, digital
cameras, digital computers and etc.
•Digital systems have the ability to manipulate
discrete quantities.
• Some digital systems can operate with
extreme reliability by using error-correcting
code. For example: DVD
A.Abhari
CPS213
2
Numbering Systems
• Decimal numbering systems:
A decimal digit can have the values of 0,1,2,3,4,5,6,7,8
and 9. The number of combination of 2 decimal digits is
102 . In general for any numbering system the number
of combination of n digits can be determined by:
Bn
where B is the base of numbering system and n is the
number of digits to be combined.
• For example for two decimal digits the largest number is
99 so the two decimal digits end at 99. Using the formula
of Bn the total number of combinations for two decimal
digits would be 102 = 100
A.Abhari
CPS213
3
Numbering Systems
• A decimal number such as 7,392.42 is equal to:
7 * 103 + 3 * 102 + 9 * 101 + 2 * 100 + 4 * 10-1 + 2
* 10-2
• In general for any numbering system
an an-1 an-2…… a1 a0. a-1 a-2……. a-m
the equal decimal number is:
an* rn + an-1* rn-1 + ….a1* r + a0 + a-1* r-1+… am* rm
where aj is the coefficient
and
the number expressed in a base-r system
A.Abhari
CPS213
4
Octal Numbering System
• The Octal numbering system is a base-eight
numbering system with eight digits of
0,1,2,3,4,5,6,7
Decimal
Octal
-------------------0
0
1
1
7
7
8
10
9
11
A.Abhari
CPS213
5
Octal Numbering System
• For example to count in octal the digits combine
after reaching a count of 7
1,..7,10,11,12,…,15,16,17,20,21,…,75,76,77,100
for two octal digits the largest number is 77 so
the two octal digits end after at 77. Using the
formula of Bn the total number of combinations
for two octal digits would be 82 = 64
• To find the decimal number equal to an octal
number:
(127.4)8= 1* 82 +2 * 81 + 7 * 80 + 4 * 8-1 = (87.5)10
A.Abhari
CPS213
6
The Hexadecimal Numbering System
• It is a base-sixteen numbering system. That is there are
16 digits in this system:
Hexadecimal
Decimal
---------------------------0
0
1
1
2
2
……..
……
9
9
A
10
B
11
C
12
D
13
E
14
F
15
A.Abhari
CPS213
7
The Hexadecimal Numbering System
• For example to count in hexadecimal
…F,10,11,12,…19,1A,1B,1C,1D,1E,1F,20,
21,….99,9A,…,9F,A0,A1…..,FE,FF,100
for two hexadecimal digits the largest number is FF so
the two hexadecimal digits end after at FF. Using the
formula of Bn the total number of combinations for two
hexadecimal digits would be 162 = 256.
• To find the decimal number equal to a hexadecimal
number:
(B65F)16= 11 * 163 + 6 * 162 + 5 * 161 + 5 * 160 = (46,687)10
A.Abhari
CPS213
8
The Binary Numbering System
Only two digits required {1,0}
20
Base 10
Equivalent
0
0
1
1
1
0
2
1
1
3
21
A.Abhari
CPS213
9
The Binary Numbering System
• For four binary digits the largest number is 1111
so the four binary digits end at 1111. Using the
formula of Bn the total number of combinations
for four binary digits would be 24 = 16.
• To find the decimal number equal to a binary
number:
(110101)2 = 32 + 16 + 4 + 1 = (53)10
(0.1101)2 =(1*.5 +1*.25 +0*.125 +1*.0625 )10
=(0.8125) 10
A.Abhari
CPS213
10
Adding Binary Numbers
Same rule as decimal
Example:
+
0
1
1 1 1
0
0
1
+ 1 1 1
1
1
10
1 1 1 0
carry
A.Abhari
CPS213
11
Multiplication of Binary numbers
Multiplication Table
*
0
0
0
Example:
1 1 1
1
0
*
1 1 1
1 1 1
1
0
1
1 1 1
1 1 1
1 1 0 0 0 1
A.Abhari
CPS213
12
Number Base Conversions
• For converting decimal number to binary number
REPETETIVE DIVISION is used as follows:
The following algorithm generates the binary digits.
Q = decimal number
While Q is not equal to 0 do the
following
Binary digit = Q mod 2
Q = Q / 2
(quotient)
End While
A.Abhari
CPS213
13
Conversion Example
Convert (58)10 to (?)2
58 mod 2 = 0
29 mod 2 = 1
14 mod 2 = 0
7 mod 2 = 1
3 mod 2 = 1
1 mod 2 = 1
A.Abhari
29
14
7
3
1
1
Ans: (111010)2
CPS213
14
Conversion Example
• To convert a fraction, it multiples by 2 to give an
integer and a fraction and only the fraction
again multiplies by 2. This process continues
until the faction becomes zero or until the
number of digits have sufficient accuracy:
(0.6875) 10 = ( ? ) 2
0.6875 * 2 = 1 + 0.3750
0.3750 * 2 = 0 + 0.7500
0.7500 *2 = 1 + 0.5000
0.5000 * 2 = 1 + 0.0000
== result is (0.1011)2
A.Abhari
CPS213
15
Hex to Binary
Converting from Hex to Binary is easy:
Every hex digit becomes 4 binary digits
(1AF5) 16
=(0001 1010 1111 0101) 2
=(1101011110101)2
(306.D)16
= ( 0011 0000 0110. 1101 )2
A.Abhari
CPS213
16
Binary to Hex
Just as simple, reverse to process
(111001010101011101) 2
=(0011 1001 0101 0101 1101) 2
=(3955D) 16
A.Abhari
CPS213
17
Octal to Binary
Converting from Octal to Binary is trivial:
Every octal digit becomes 3 binary digits
(175 ) 8
=(001 111 101) 2
=(1111101) 2
A.Abhari
CPS213
18
Binary to Octal
Just as simple, reverse to process
(11001010101011101) 2
=(011 001 010 101 011 101) 2
=(312535) 8
• Using the hex and octal equivalent instead
of binary numbers are more convenient
and less prone to errors.
A.Abhari
CPS213
19
Complements
• One of the use of complements is the
simplifying subtraction operation. We want
to be able to perform subtraction through
the addition operation.
There are two types of complements for
each base-r system:
• r’s complement ( radix complement )
• (r-1)’s complement ( diminished radix
complement)
A.Abhari
CPS213
20
(r-1)’s Complements
• (r-1)’s complement for a number N with n digits
in base-r numbering system is defined as:
(rn -1 ) – N
• For example for decimal numbers since r is 10,
(r-1)’s complement of a number N is:
( 10n – 1) – N
• For example: 9’s complement of 12389 is
(105 -1 ) - 12389 = 99999 -12389= 87610
Or 9’s complement of 2389 is
(104 -1) – 2389 = 9999 -2389 = 7610
A.Abhari
CPS213
21
(r-1)’s Complements
1’s complement of a number N, is defined as
(2n – 1 ) – N
For example for 1011001 it is equal to :
( 27 – 1 ) – 1011001 = 0 100110
Therefore, 1’s complement of binary
numbers is formed by changing 1’s to 0’s
and 0’s to 1’s
For example 1’s complement of 0001111 is
1110000
A.Abhari
CPS213
22
(r’s complement)
• (r’s) complement for number N in base r with n digits
is defined as rn – N
also it is clear r’s complement= ( r-1)’s complement +1
Therefore we can use (r-1)’s complements of the previous
examples to calculate their r’s complement :
10’s complement of 2389= 7610 + 1 = 7611
2’s complement 101100= 010011
1’s complement
+
1
-------------010100
• 2’s complement of 101100 by using rn – N definition
generates same result:
2n – N = 1000000
- 0101100
---------------------0010100
A.Abhari
CPS213
23
Subtraction with complements
(Unsigned Numbers)
For doing the subtraction on two n digits
unsigned numbers M and N the in base r
the following algorithm can be used:
1- Add M to r’s complement of N
2- If M>=N subtract rn form the result
3- if M<N place a negative sign “-” in front
of r’s complement of the result
A.Abhari
CPS213
24
Subtraction with complements
(Unsigned Numbers)
• For example 3250 -72532
M = 03250
10’s complement of N = + 27468
-----------30718
Since N is > M the result is
- (10’s complement 30718) =-69282
A.Abhari
CPS213
25
Subtraction with complements (Unsigned Numbers)
• For Binary numbers the algorithm is same. See the examples in the
book
• Subtraction also can be done by (r-1)’s complement. In that case if
M>=N, after discarding the end carry one should be added to result:
For example for X =1010100 -Y= 1000011:
2’s compl.
1’s compl.
X = 1010100
1010100
+ Y = 0111101
+ 0111100
------------------------------10010001
10010000
- 10000000 - 10000000
+
1
-------------------- ---------------0010001
0010001
• The problem is how we can simplify the subtraction for signed numbers?
For example how about 2- (-1)?
• For doing that first we should represent a signed number and then
devise an algorithm for the arithmetic operations of the signed numbers.
See the next slides…
A.Abhari
CPS213
26
Signed Binary Numbers
• Positive integer numbers can be represented by unsigned
numbers. However we need a notation for negative
numbers:
• A negative binary number assumed to be signed or
unsigned. For example 01001 can be considered
unsigned binary = 9 or
signed binary = +9
Or 11001 can be considered
unsigned binary = 25 or
signed binary = -9
• If the representation of the signed numbers uses 0 for “+”
and 1 for “-” , this system is called Signed-magnitude
convention
A.Abhari
CPS213
27
Signed Binary Numbers
• Another system to represent negative numbers is
signed complement system
For example
+9 is 00001001 in two systems
but -9 is
10001001 in signed-magnitude
11110110 in signed-1’s-complement
(complementing all bits include sign bit or
subtracting from 2n -1)
11110111 in signed-2’s-complement
( 2’complement of all bits or subtracting from 2n )
A.Abhari
CPS213
28
Signed Binary Numbers
• Representation method only matters when
we are talking about negative numbers
• All negative numbers have 1 in leftmost bit
• The signed magnitude is mostly used in
ordinary arithmetic
• The 1’s complement is mostly used in
logical operations
• The 2’s complement is mostly used in
computer arithmetic
A.Abhari
CPS213
29
Decimal
signed-2’s
complement
-------------------+7
0111
+2
0010
+1
0001
+0
0000
-0
---1
1111
-2
1110
-7
1001
-8
1000
A.Abhari
signed-1’s
signed
complement magnitude
----------------------0111
0111
0010
0010
0001
0001
0000
0000
1111
1000
1110
1001
1101
1010
1000
1111
-----------CPS213
30
Arithmetic Addition (Signed Numbers)
• The addition of binary numbers in signed-magnitude
system follows the same rules as ordinary arithmetic.
(sign of larger number)
• For adding the numbers in 2’s complement form the result
can be obtained by adding the two numbers including their
sign bits. The carry of the sign bits is discarded and
negative results are automatically in 2’s complement form.
It means in order to get the negative result we must find
the 2’s complement form of the result including the sign
bit.
• When adding 2 numbers of same sign (pos or neg) in 2’s
complement form, if the result cannot be shown in the
available bits then the overflow occurs that indicates the
result is wrong. Generally when the sign of the result
shown in available bits is different from the sign of the
numbers, overflow has been occurred. See the next slide.
A.Abhari
CPS213
31
Arithmetic Addition (2’s Comp)
• Two positive numbers
0 1001
+
0 0100
---------------0 1101
A.Abhari
CPS213
0 1001
0 1000
----------1 0001
Neg result
wrong, overflow
32
Arithmetic Addition (2’s Comp.)
• For example:
+9
0 1001
+ -4
1 1100
-------------------------------1 0 0101
(5)
Discarded final carry. Note that sign bit also
participates in the process
A.Abhari
CPS213
33
Arithmetic Addition (2’s Comp.)
• For example:
+6
0 0000110
+ -13 1 1110011
-------------------------------1 1111001 => 0000111 (2’s
comp.)
it is equal to 7 so the result is -7
A.Abhari
CPS213
34
Arithmetic Addition (2’s Comp.)
• For example:
-9
1 0111
+ -4
1 1100
-------------------------------11 0011 => 01101 (2’s comp.)
it is equal to 13 so the result is -13
A.Abhari
CPS213
35
Arithmetic Subtraction
• In 2’s complement format it is very simple :
Take the 2’s complement of sabtrahend (the
second number) including the sign bit and add it
to minuend (the first number) including the sign
bit and discard a carry out of sign bit
• By taking 2’s complement of the subtrahend its
sign can be changed. Thus, we can change
subtraction to addition operation.
A.Abhari
CPS213
36
Arithmetic Subtraction (2’s Comp)
• For example:
(+9)
-(+4)
(+9)
+(-4)
A.Abhari
0 1001
0 0100 is changed to
0 1001
1 1100
---------------1 0 0101 (+5) discard carry
CPS213
37
Arithmetic Subtraction (2’s Comp)
• For example:
(-4)
-(+9)
1 1100
0 1001 is changed to
(-4)
+
1 1100
1 0111
---------------1 1 0 011 (2’s comp 01101
means magnitude is 13) discard carry => (-13)
A.Abhari
CPS213
38
Arithmetic Subtraction
• For example:
-6
11111010
- -13
11110011 => is changed to
-6
+ +13
A.Abhari
11111010
00001101
----------------100000111 => discard carry
 00000111 is +7
CPS213
39
Binary Coded Decimal (BCD)
• 4 bits used to encode one decimal digit
• For example (4321)10 = 0100 0011 0010 0001
• The problem is BCD can not be used for
conversion from decimal to binary and from
binary to decimal. Because there is no decimal
digits for 1010, 1011,1100,1101,1110,1111
For example : (0111 0010 1100)2= (72?)
there is no decimal digits (0..9) for 1100
A.Abhari
CPS213
40
BCD Arithmetic
1. Add 2 BCD numbers using regular
binary addition
2. Check each nibble ( 4-bit) if result is
greater than 9 add 6 to it
If there is carry between 2 nibble or coming
from 2th nibble add 6
A.Abhari
CPS213
41
BCD Arithmetic
Example: 27
+ 34
A.Abhari
0010 0111
0011 0100
----------------0101 1011 > 9
+
0110
---------------01100001
CPS213
42
BCD Arithmetic
Example:
59
+
39
A.Abhari
1
carry
0101 1001
0011 1001
---------------1001 0010
0110
---------------1001 1000
(98)
CPS213
43
BCD Arithmetic
1
98
+ 89
+
A.Abhari
1
carry
1001 1000
1000 1001
--------------1 0010 0001
0110 0110
--------------11000 0111
(187)
CPS213
44
Character Representation
ASCII – American Standard Code for
Information Interchange
128 characters (7 bits required)
Contains:
• Control characters (non-printing)
• Printing characters (letters, digits,
punctuation)
A.Abhari
CPS213
45
ASCII – Characters
Hex
Equiv.
00
07
09
0A
0D
20
A.Abhari
Binary
Character
00000000
NULL
00000111
Bell
00001001 Horizontal tab
00001010
Line feed
Carriage
00001110
return
00100000 Space (blank)
CPS213
46
ASCII – Characters
Hex
Equiv.
30
31
39
41
42
61
62
A.Abhari
Binary
Character
00110000
00110001
00111001
01000001
01000010
01100001
01100010
0
1
9
A
B
a
b
CPS213
47
Error-Detecting Code
• To detect the error in data communication,
an eighth bit is added to 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
• The 8-bit characters included parity bits
(with even parity) are transmitted to their
destination. If the parity of received
character is not even it means at least one
bits has been changed.
A.Abhari
CPS213
48
Error-Detecting Code
Example:
even parity odd parity
ASCII A = 1000001
01000001 11000001
ASCII T = 1010100
11010100 01010100
• The method of error checking with even
parity detects any odd combinations of
errors in each character that is
transmitted. An even combination of errors
is undetected with this method.
A.Abhari
CPS213
49
Binary Storage and Registers
• Register is a group if binary cells that are
responsible for storing and holding the
binary information.
• Register transfer operation is transferring
binary operation from one set of registers
to another set of registers.
• Digital logic circuits process the binary
information stored in the registers.
A.Abhari
CPS213
50
A.Abhari
CPS213
51
A.Abhari
CPS213
52
Binary Logic
• Binary logic or Boolean algebra deals with
variables that take on two discrete values.
• Binary logic consists of binary variables (e.g.
A,B,C, x,y,z and etc.) that can be 1 or 0 and
logical operations such as:
AND: x.y=z or xy=z (see AND truth table)
OR: x + y =z (see OR truth table)
NOT: x’ =z (not x is equal to z)
• Note that binary logic is different from binary
arithmetic. For example in binary logic 1 + 1 =1
(1OR1) but in binary arithmetic 1 + 1 = 10 (1
PLUS 1)
A.Abhari
CPS213
53
Logic Gates
• Logic gates are electronic circuits that operate
on one or more input signals to produce an
output signal.
• Electrical signal can be voltage.
• Voltage-operated circuits respond to two
separate levels equal to logic 1 or 0.
• Logical gates can be considered as a block of
hardware that produced the equivalent of logic 1
or logic 0 output signals if input logical
requirement are satisfied
A.Abhari
CPS213
54
A.Abhari
CPS213
55
A.Abhari
CPS213
56
A.Abhari
CPS213
57