Transcript Digital Systems

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
Numbering Systems
• Decimal numbering systems:
102 is the combination of 2 digits from the values of
0,1,2,3,4,5,6,7,8 and 9 . 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
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
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
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
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
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
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
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
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
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
Number Base Conversions
• For converting decimal number to binary number
REPETETIVE DIVISION is used as follows:
Algorithm that generates binary digits from 0 to n:
Q = decimal number
While Q is not equal to 0 do the
following
Binary digit = Q mod 2
Q = Q / 2
(quotient)
End While
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
29
14
7
3
1
1
Ans: (111010)2
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
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
Binary to Hex
Just as simple, reverse to process
(111001010101011101) 2
=(0011 1001 0101 0101 1101) 2
=(3955D) 16
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
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.
Complements
Complements are using for two purposes:
• For simplifying subtraction operation
• For logical operations
There are two types of complements for
Base-r:
• r’s complement ( radix complement )
• (r-1)’s complement ( diminished radix
complement)
(r-1)’s Complements
(r-1)’s complement for a number N in base-r
with n digits is (rn -1 ) – N
For example for decimal numbers r =10
( 10n – 1) – N
9’s complement of 12389 is
(105 -1 ) - 12389 = 99999 -12389= 87610
9’s complement of 2389 is
(104 -1) – 2389 = 9999 -2389 = 7610
(r-1)’s Complements
1’s complement 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 0001111 becomes 1110000
(r’s complement)
(r’s) complement for number N in base r with n digits is (rn –
N)
also r’s complement= ( r-1)’s complement +1
For example:
10’s complement 2389= 7610 + 1 = 7611
2’s complement 101100= 010011
1’s complement
+
1
-------------010100
Or 2n – N = 1000000
- 0101100
---------------------0010100
Subtraction with complements
(Unsigned Numbers)
For doing the subtraction on two n digits unsigned
minuend M
- subtrahend N
in base r
1- add M to r’s complement of N
2- If M>=N subtract 10n form the result
3- if M<N put “-” and r’s complement of result
Subtraction with complements
(Unsigned Numbers)
• For example 3250 -72532
M = 03250
10’s complement of N = + 27468
-----------30718
- (10’s complement 30718) =-69282
Subtraction with complements
(Unsigned Numbers)
• For Binary numbers the algorithm is same
• 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 (end-around carry):
X = 1010100
1010100
2’scopml ( Y= 1000011)+ Y = 0111101 1’s +0111100
------------------------------10010001
10010000
-10000000 - 10000000
1
-------------------- ---------------0010001
0010001
Signed Binary Numbers
A negative binary number assumed to be signed or
unsigned. For example:
01001
unsigned binary = 9
signed binary = +9
11001
unsigned binary = 25
signed binary = -9
Signed-magnitude convention ( 0 for + and 1 for -)
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 )
Decimal
signed-2’s
complement
-------------------+7
0111
+2
0010
+1
0001
+0
0000
-0
---1
1111
-2
1110
-7
1001
-8
1000
signed-1’s
signed
complement magnitude
----------------------0111
0111
0010
0010
0001
0001
0000
0000
1111
1000
1110
1001
1101
1010
1000
1111
------------
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
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 can be
obtained by adding the two numbers including their sign
bits. The carry of sign bit is discarded and negative
results are automatically in 2’s complement form.
• In order to get the negative result we must find the 2’s
complement form
• When adding 2 numbers of same sign (pos or neg) in 2’s
complement form if result cannot be shown in bits
available, then overflow occurs that indicates result is
wrong.
Arithmetic Addition (2’s Comp)
• Two positive numbers
0 1001
+
0 0100
---------------0 1101
0 1001
0 1000
----------1 0001
Neg result
wrong, overflow
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
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
Arithmetic Addition (2’s Comp.)
• For example:
-9
1 0111
+ -4
1 1100
-------------------------------11 0011 => 1101 (2’s comp.)
it is equal to 13 so the result is -13
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.
Arithmetic Subtraction (2’s Comp)
• For example:
(+9)
-(+4)
(+9)
+(-4)
0 1001
0 0100 is changed to
0 1001
1 1100
---------------1 0 0101 (+5) discard carry
Arithmetic Subtraction (2’s Comp)
• For example:
(-4)
-(+9)
(-4)
+
1 1100
0 1001 is changed to
1 1100
1 0111
---------------1 1 0 011 (2’s comp 01101
means magnitude is 13) discard carry => (-13)
Arithmetic Subtraction
• For example:
-6
11111010
- -13
11110011 => is changed to
-6
+ +13
11111010
00001101
----------------100000111 => discard carry
 00000111 is +7
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
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
BCD Arithmetic
Example: 27
+ 34
0010 0111
0011 0100
----------------0101 1011 > 9
+
0110
---------------01100001
BCD Arithmetic
Example:
59
+
39
1
carry
0101 1001
0011 1001
---------------1001 0010
0110
---------------1001 1000
(98)
BCD Arithmetic
1
98
+ 89
+
1
carry
1001 1000
1000 1001
--------------1 0010 0001
0110 0110
--------------11000 0111
(187)
Character Representation
ASCII – American Standard Code for
Information Interchange
128 characters (7 bits required)
Contains:
• Control characters (non-printing)
• Printing characters (letters, digits,
punctuation)
ASCII – Characters
Hex
Equiv.
00
07
09
0A
0D
20
Binary
Character
00000000
NULL
00000111
Bell
00001001 Horizontal tab
00001010
Line feed
Carriage
00001110
return
00100000 Space (blank)
ASCII – Characters
Hex
Equiv.
30
31
39
41
42
61
62
Binary
Character
00110000
00110001
00111001
01000001
01000010
01100001
01100010
0
1
9
A
B
a
b
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.
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.
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.
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 zy=z (see AND truth table)
OR: x + y =z (see OR truth table)
NOT: x’ =z (not x is equal to z)
• Not 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)
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