Transcript File - IndIanHolmes

ECE 103
DIGITAL LOGIC DESIGN
CHAPTER I
NUMBER SYSTEMS AND
CODES
Reference: M. Morris Mano & Michael D. Ciletti, "Digital Design", Fourth
Edition, Prentice Hall of India Pvt. Ltd., Chapter – Chapter -1
VIT UNIVERSITY
1
Number systems and codes
Representation of numbers
Decimal - Octal - Hexadecimal number
systems
Representation of negative numbers
Complement of a number
Binary arithmetic
Binary codes for decimal numbers
Error detecting and correcting codes
VIT UNIVERSITY
2
Representation of numbers
A number in base-r has coefficients multiplied
by powers of r and is of the form
an r n  an1r n1  ..... a1r1  a0r 0  a1r 1  a2r 2  .... amr m
Range of aj is from 0 to r-1
r is also called radix of the number system
If r = 2, binary number system
If r = 8, octal number system
If r = 16, hexadecimal number system
VIT UNIVERSITY
3
Number base conversions
To convert a number in base r to decimal is
done by expanding the number in a power
series and adding all the terms
If the number includes a radix point, it is
necessary to separate the number k into an
integer part and a fraction part.
Decimal number is converted to number in base
r by dividing the number and all successive
quotients by r and accumulating the remainders.
VIT UNIVERSITY
4
Number base conversions
Example 1: Convert decimal 153 to octal
Example 2: Convert (0.6875)10 to binary
VIT UNIVERSITY
5
Complement of a number
Used for
Simplifying subtraction
Logical manipulation
Two types
Radix complement
Diminished radix complement
VIT UNIVERSITY
6
Complement of a number
Diminished Radix complement
Given a number N in base r having n digits, its
diminished radix complement is (r n 1)  N
Radix complement
Given a number N in base r having n digits, its
n
((
r
 1)  N )  1
diminished radix complement
VIT UNIVERSITY
7
Representation of negative
numbers
Two ways of representation
Sign magnitude form
Sign complement form
signed 1’s complement form
signed 2’s complement form
VIT UNIVERSITY
8
Sign magnitude form
The number consists of magnitude bits
and a sign bit
Used in ordinary arithmetic
It is simple
Drawbacks:
Hardware limitations
Two representations of zero
VIT UNIVERSITY
9
Signed complement form
A negative number is represented by its
complement
positive numbers always start with 0 in the
leftmost position.
The complement will always start with a 1,
indicating a negative number.
VIT UNIVERSITY
10
Representation of negative
numbers
Eg: Represent -9 using 8 bits in both Sign
magnitude form and sign complement
form
VIT UNIVERSITY
11
Binary arithmetic
Addition
Subtraction
Multiplication
Addition
Similar to normal decimal addition
Rules of addition:
1 + 1 = 0 CY = 1
1+0=0+1=1
VIT UNIVERSITY
12
Binary subtraction
The subtraction of two n-digit unsigned numbers
M - N in base r can be done as follows:
1. Add the minuend M to the r's complement of the
subtrahend N. Mathematically, M + (rn - N) = M N + rn
2. If M >= N. the sum will produce an end carry rn
which can be discarded. what is left is the result
M - N.
3. If M < N. the sum does not produce an end carry
and is equal to rn - (N - M) which is r's
complement of (N - M).
4. To obtain the answer, take the r's complement of
the sum and place a negative sign in front.
VIT UNIVERSITY
13
Binary subtraction
Eg: Perform the subtraction a) X – Y and b) Y – X if X = 1010100 and Y
= 1000011 using two’s complement form.
There is no end carry so the answer is – (two’s complement of 1101111)
VIT UNIVERSITY
14
Binary multiplication
Just like normal decimal multiplication
Eg: Find (1 0 1)2 × (1 1 0)2
VIT UNIVERSITY
15
Binary codes for decimal numbers
A binary number of n digits gives 2n
distinct combinations which can be used to
represent distinct group of quantities
Different binary codes available are
weighted codes, un-weighted codes, selfcomplementing codes, reflecting codes
Weighted codes: Each bit position is
assigned a weighing factor and each digit
is evaluated by adding the weights of all
the ones in the coded combination
Eg: BCD code, 2-4-2-1 code, (8, 4,-2,-1)
code, etc
VIT UNIVERSITY
16
Binary codes for decimal numbers
Un-weighted codes: Weight is not
assigned to the bit positions
Eg: Excess-3 code
Self complementing code: 9’s complement
of the decimal number is obtained by
changing 1’s to 0’s and viceversa.
Eg: 2-4-2-1 code, Excess-3 code
VIT UNIVERSITY
17
BCD code
Decimal numbers 0 – 9 can be
represented using 4 bits.
There are 6 unused combinations in this
coding scheme.
VIT UNIVERSITY
18
Different binary codes for decimal
numbers
VIT UNIVERSITY
19
Gray Code
Reflection code
Advantage of Gray
code over the straight
binary number
sequence is that only
one bit in the code
group changes in
going from one
number to the next.
VIT UNIVERSITY
20
ASCII Character code
The “American Standard Code for
Information Interchange“ ASCII was
suggested in 1968
Represents alphanumeric character set.
Uses 7 bits to represent 128 characters
There are special symbols which can be
represented by this code
The coding is given in next slide
VIT UNIVERSITY
21
VIT UNIVERSITY
22
Error detection and correction
 Error detection and correction code
 An error-correcting code generates multiple parity check
bits that are stored with the data word in memory. Each
check bit is a parity over a group of bits in the data word
 When the word is read back from memory, the associated
parity bits are also read back and compared with a new set
of check bits generated from the data that have been read
lf the check bits are correct, no error has occurred.
 If the check bits do not match the stored parity, they
generate a unique pattern, called a syndrome, that can be
used to identify the bit that is in error.
 A single error occurs when a bit changes in value from 1 to
0 or from 0 to 1 during the write or read operation.
 If the specific bit in the error is misidentified, then the error
can be corrected by complementing the erroneous bit.
VIT UNIVERSITY
23
Parity
Simplest form of error detection is
achieved by using parity bits.
A parity bit is an extra bit included with a
message to make the total number of 1's
either even or odd.
Eg:
VIT UNIVERSITY
24
Hamming code
k parity bits are added to an n-bit data
word forming a new word of n + k bits.
The bit positions are numbered in
sequence from 1 to n + k.
The relation between the number of
message bits and parity bits is
Those positions numbered as a power of 2
are reserved for the parity bits
The remaining bits are the data bits
VIT UNIVERSITY
25
Hamming code
Construction of hamming code for
11000100
Calculating parity bits
VIT UNIVERSITY
26
Hamming code
Message bit sequence
Calculation of check bits
Message sequences with no error, error in bit 1 and error in bit 5
Calculation of check bits for the above message sequences
VIT UNIVERSITY
27
Assignments Problems…
 1. Convert the following binary numbers in decimal: 101110; 1110101; and
110110100.
 2. Convert the following decimal numbers to the bases indicated.
a. 7562 to octal
b. 1938 to hexadecimal
c. 175 to binary
 3. Show the value of all bits of a 12-bit register that hold the number
equivalent to
decimal 215 in (a) binary; (b) octal; (c) hexadecimal; (d) binary-coded
decimal (BCD).
 4. Show the following operations using 2s complement:
a. 10000111 – 1011001
b. 1011001 – 10000111
c. 0.1001 – 0.0101
d. 0.0101 – 0.1001
VIT UNIVERSITY
28
Assignments Problems…
 5. Convert the following two decimal numbers to binary, octal, and
hexadecimal numbers.
i) 174.25 ii) 250.8
 6. Convert the following two unsigned binary numbers to octal,
hexadecimal, and decimal numbers.
i) 10101.11 ii) 10110110.001
 7. Show how a 16‐bit computer using a two’s complement number
system would perform the following computations.
(i) (16850)10 + (2925)10 = (?)10
ii) (16850)10 ‐ (2925)10 = (?)10
iii) (2925)10 ‐ (16850)10 = (?)10
iv) ‐(16850)10 ‐ (2925)10 = (?)10
VIT UNIVERSITY
29
Assignments Problems…
 8. Do the following non-textbook problems:
a. Obtain the 1’s and 2’s complements of the following unsigned
binary numbers: 10001000, 10011001, 10101100, 00000000, and
10000000.
b. Perform the indicated subtraction with the following unsigned
binary numbers by taking the 2’s complement of the subtrahend:
a) 11011 – 10000
b) 10110 – 1011
c) 100 – 101000
d) 1011100 – 1011100
Note: You must choose a size for your 2’s complement numbers.
VIT UNIVERSITY
30
Assignments Problems…
c. The following binary numbers are 6-bit
2’s complement numbers. Perform the
indicated arithmetic operations and
verify the answers.
a) 101111 + 111011
b) 001011 + 100010
c) 110001 – 001110
d) 101010 – 110111
VIT UNIVERSITY
31
Assignments Problems…
For more problems :
Refer : M. Morris Mano, "Digital Design",
3rd Edition, Prentice Hall of India Pvt.
Ltd., Chapter Pages()
VIT UNIVERSITY
32