241CSM--4

Digital Logic
Lecture 5

1
 Conversion from decimal to base b:
(N)10  (?)b

Procedure:
• Convert the Integer Part
• Convert the Fraction Part
• Join the two results with the new radix point

2
Chapter 1 2
 Converting fraction from decimal to base b:

Repeatedly multiply the integer by the new base b and save the integer part of
the result (will never exceed b) until 0 fraction or enough digits
 The digits for the new base are those integers with the MS digit being
that computed first

(0.6875)10 = (??)2
 radix point

Fraction in new base

Continue until
you get either:
 Zero fraction, or
 Enough # of
Chapter 1 3
 Significant fraction digits
Verify Result
3
 Fractions
.14579
• Decimal to binary x 2
3.14579 0.29158
x 2
0.58316
x 2
1.16632
x 2
0.33264
x 2
0.66528
x 2
1.33056
11.001001...
etc.

p. 50
4
 Example: Convert 153.51310to Base 8,
rounding the resulting fraction to 3 octaldigits
1. Convert Integer Part: 153 to Base 8


2. Convert Fraction Part: 0.513 to Base 8:


Get 4 octal digits in the
Fraction for rounding to
3 significant digits

8  (0.407)8 after rounding, since 5 is >4 we add 1 to fraction

Chapter 1 
(0.513)10 = (0.4065)
5
So: 153.513150 = 231.4078
 Contd. Example: Convert 153.51310to Base8

3. Join the results together with the new radix point:

(153.513)10 = (231.407)8
4. Verify the result:
2 1 0 -1 -2 -3
(231.407)8  (----------)10
= 2 x 82 + 3 x 81 + 1 x 80 + 4 x 8-1 + 0 x 8-2 + 7 x 8-3
= 2 x 64 + 3 x 8 + 1 + 0.5 + 7 x 8-3
= (153.506)10
 (153.513)10
(Difference is due to rounding error)
6
Chapter 1 6
 Octal (Hexadecimal) Binary
• Example: Hexadecimal to Binary
(F 9 C . B 7 D)16
= 1111 1001 1100. 1011 0111 1101
= (111110011100.101101111101)2

• Example: Binary to Octal Always start at the radix point

Working your way away from it
(1011010110.0101111)2 in both directions

= (1011010110.0101111)2
Appended 0‟s
= (0 1011010110.0101111 00 2
0 = (1 3 2 6 . 2 7 4 ))
8
7
Chapter 1 7
 Binary Addition
One bit addition:
0 0 1 1 augend /aw-jend/

+0 +1 + 0 +1 addend
----- ------ ------ ------
0 1 1 2 sum

10
carry

2 doesn’t exist in binary!

KFUPM
Binary Addition (cont.)

Example: Q: How to verify?

1 111 A: Convert to decimal
carries
1 1 0 0 0 0 1 1 11 783
+ 0 1 1 1 1 0 1 0 10 + 490
-------------------------- -----------
sum
1 0 0 1 1 1 1 1 0 01 1273

KFUPM
 Binary Subtraction
One bit subtraction:
0 0 1 1 minuend /men-u-end/

-0 -1 - 0 -1 subtrahend /sub-tra-hend/
----- ------ ------ ------
0 1 1 0 difference

• In binary addition, there is a

sum and a carry.
borrow 1 • In binary subtraction, there is a
difference and a borrow
• Note: 0 – 1 = 1 borrow 1

KFUPM
Binary Subtraction (cont.)
Subtract 101 - 011 Larger binary numbers Verify In
1 decimal,
11 11
borrow 783
0101 1 1 0 0 0 0 1 1 11 borrow
- 490
- 0 11 - 0 1 1 1 1 0 1 0 10 ---------
-------------------------- -------------------------- difference 293
difference
010 0100100101

• In Decimal subtraction, the borrow is equal to 10.

• In Binary, the borrow is equal to 2. Therefore, a „1‟ borrowed in
binary will generate a (10)2, which equals to (2)10 in decimal

KFUPM
Binary Multiplication
Multiply 1011 with 101:
Rules (short cut):
1011 multiplicand
1. A ‘1’ digit in the multiplier
x 101 multiplier implies a simple copy of the
----------------- multiplicand

1011 2. A ‘0’ digit in the multiplier

implies a shift left operation
0000 with all 0’s
1011
------------------------
product
110111

KFUPM
Hexadecimal addition
Add (59F)16 and (E46)16
1 1 Carry

59F F + 6 = (21)10 = (15)16

+ E46 5 + E = (19)10 = (13)16
---------
13E5 Rules:
1. For adding individual digits of a Hexadecimal number, a mental
addition of the decimal equivalent digits makes the process
easier.
2. After adding up the decimal digits, you must convert the result
back to Hexadecimal, as shown in the above example.

KFUPM
Octal Multiplication
Multiply (762)8 with(45)8
Carry

Octal Octal Decimal Octal

762 5x2 = (10)10 = (8 x 1) + 2 = 12
x 45 5 x 6 + 1 = (31)10 = (8 x 3) + 7 = 37
-------------- 5 x 7 + 3= (38)10 = (8 x 4) + 6 = 46
4672 4x2 = (8)10 = (8 x 1) + 0 = 10
3710 4 x 6 + 1 = (25)10 = (8 x 3) + 1 = 31
--------------- 4 x 7 + 3= (31)10 = (8 x 3) + 7 = 37
43772
We use decimal representation for ease
of calculation

KFUPM
 Multiplication (2 of 3)

• Binary, two 1-bit values

A B AB
0 0 0
0 1 0
1 0 0
1 1 1

15
 Multiplication (3 of 3)

• Binary, two n-bit values

– As with decimal values
– E.g., 1110
x 1011
1110
1110
0000
1110
10011010
16
 Binary Subtraction

• Just like subtraction in any other base

– Minuend 10110
– Subtrahand - 10010
– Difference 00100
• And when a borrow is needed. Note that the
borrow gives us 2 in the current bit position.

17
17
 Binary subtraction (cont)

• And more ripple -

18
18
 Binary subtraction (cont)

• Now do the operation 4 –6

• Correct difference is -2 or -0010

19
19
 1’s Complement

• 1‟s complement of N is defined as (2n -1)-N.

– If n=4 have (2n -1) being 1 0000 - 1 = 1111
• So for n=4 would subtract any 4-bit binary
number from 1111.
• This is just inverting each bit.
• Example: 1‟s compliment of 1011001
• is 0100110

20
20
 2’s complement

• The 2‟s complement is defined as 2n-N

• Can be done by subtraction of N from 2n or
adding 1 to the 1‟s complement of a number.
• For 6 = 0110
– The 1‟s complement is 1001
– The 2‟s complement is= 1001+ 1 = 1010

21
21
 Operation with 2’scomplement

• Add 4 and -6
• Will use the 2‟s complement of -6 or1010
– 4 0100
– -6 1010
– 1110
• And taking the 2‟s complement of 1110get
0001 + 1 = 0010

22
22
A 2’s complement table for 4bits

• Listing the
values
represented.

23
23
 Human perception

• We naturally live in a base 10 environment

• Computer exist in a base 2 environment
• So give the computer/digital system thetask
of doing the conversions for us.

24
24
 Binary Coded Decimal (BCD)

Decimal digit 0 1 2 3 4
BCD 0000 0001 0010 0011 0100
Decimal digit 5 6 7 8 9
BCD 0101 0110 0111 1000 1001

 Some codes are unused, eg: (1010)BCD, (1011) BCD, …,(1111)

BCD. These codes are considered as errors.
 Easyto convert, but arithmetic operations aremore
complicated.
 Suitable for interfaces such as keypad inputs and digital
readouts.

25
 Binary Coded Decimal (BCD)

Decimal digit 0 1 2 3 4
BCD 0000 0001 0010 0011 0100
Decimal digit 5 6 7 8 9
BCD 0101 0110 0111 1000 1001

 Examples:
(234)10 = (0010 0011 0100)BCD
(7093)10 = (0111 0000 1001 0011)BCD
(1000 0110)BCD = (86)10
(1001 0100 0111 0010)BCD= (9472)10
Notes: BCDis not equivalent tobinary.
Example: (234)10 =(11101010)2
26
 BCD operation

• Consider the following BCDoperation

– Decimal: Add 4 + 1
– Covert to binary 0100
– And 0001
– Getting 0101
– Which is still a BCDrepresentation of a decimal
digit

27
27
 Another

• A second example
– 3 0011
– +3 0011
– Getting 6 or 0 1 1 0
– And in range and a BCDdigit representation

28
28
 And now

• Consider 5 + 5
• 5 0101
• +5 0101
• giving 1 0 1 0 which is binary 10 but not
a BCDdigit!
• What to do?
• Try adding 6??

29
29
 Adding 6

• Had 1010 and want to add 6 or 0110

– so 1010
– plus 6 0 1 1 0
– Giving 1 0 0 0 0
• Or a carry out to the next binary digit, or if the
binary in BCD, the next BCDdigit.
• Final answer is = 0001 0000

30
30
 Another carry example

• Add 7 + 6
– have 7 0 1 1 1
– plus 6 0 1 1 0
– Giving 1 1 0 1 and again out of range
– Adding 6 0 1 1 0
– Giving 1 0 0 1 1 so a 1 carries out to the next BCD
digit
– FINALBCDanswer 0001 0011 or 1310

31
31
 Multibit BCD

• Add the BCDfor 417 to195

• Would expect to get 612
– BCDsetup - start with Least SignificantDigit
– 0100 0001 0111
– 0001 1001 0101
– 1100
– Adding 6 0110
– Gives 1 0010
32
32
 Continuing multibit

• Had a carry to the 2nd BCDdigit position

– 1
– 0100 0001 done
– 0001 1001 0010
– 1011
– add 6 0110
– Giving 1 0001
– And another carry

33
33
 Still Continuing multibit

• Had a carry to the 3rd BCDdigitposition

– 1
– 0100 done done
– 0001 0001 0010
– 0110
– And answer is 0110 0001 0010 or the BCDfor the
base 10 number 612

34
34
 Gray Codes

• When you count up or down in binary, the

number of bit that change with each digit change
varies.
– From 0 to 1 just have a single but
– From 1 to 2 have 2 bits, a 1 to 0transition and a0
to 1 transition
– From 7 to 8 have 3 bits changing back to 0 and 1 bit
changing to a1
• For some applications multiple bit changescause
significant problems.
35
35
 Gray Code

• Contrast of bit changes

– Val Bin Chg Gray Chg
– 0000 000
– 1001 1 001 1
– 2010 2 011 1
– 3011 1 010 1
– 4100 3 110 1
– 5101 1 111 1
– 6110 2 101 1
– 7111 1 100 1
– 0000 3 000 1
36
36
 Gray Code Encoder

• Copy of figure 1-5 from text

37
37
 The Gray Code

 Unweighted (not an arithmeticcode).

 Only a single bit change from one code number to the next.
 Good for error detection.

Decimal Binary Gray Code Decimal Binary Gray code

0 0000 0000 8 1000 1100
1 0001 0001 9 1001 1101
2 0010 0011 10 1010 1111
3 0011 0010 11 1011 1110
4 0100 0110 12 1100 1010
5 0101 0111 13 1101 1011
6 0110 0101 14 1110 1001
7 0111 0100 15 1111 1000
Q. How to generate 5-bit standard Gray code?
Q. How to generate n-bit standard Gray code?
38
38 CS1104-2 The Gray Code
 The Gray Code

0000 1100
0
0001 1101
0
001
01 1111
0
001
00 0110
1
1010
0
0010
1011
0
0011
1001
0
0001
1000
0
00
100

Generating 4-bit standard Gray code.

39
 The Gray Code

sensors

mis-aligned mis-aligned
sensors sensors

Binary coded: 111  110  000 Gray coded: 111  101

40
 Binary-to-Gray Code Conversion

 Retain most significant bit.

 From left to right, add each adjacent pair of binary code bits
to get the next Gray code bit,discarding carries.
 Example: Convert binary number 10110 to Graycode.

1 0 1 1 0 Binary 1 + 0 1 1 0 Binary 1 0 + 1 1 0 Binary

  
1 Gray 1 1 Gray 1 1 1 Gray

1 0 1 + 1 0 Binary 1 0 1 1 + 0 Binary
 
1 1 1 0 Gray 1 1 1 0 1 Gray

(10110)2 = (11101)Gray
41
Binary-to-Gray Code Conversion
 Gray-to-Binary Conversion

 Retain most significant bit.

 From left to right, add each binary code bit generated to the
Gray code bit in thenext position, discarding carries.
 Example: Convert Gray code 11011 to binary.

1 1 0 1 1 Gray 1 1 0 1 1 Gray 1 1 0 1 1 Gray

 +  + 
1 Binary 1 0 Binary 1 0 0 Binary

1 1 0 1 1 Gray 1 1 0 1 1 Gray
+  + 
1 0 0 1 Binary 1 0 0 1 0 Binary

(11011)Gray = (10010)2
43
Gray-to-Binary Conversion
 Alphanumeric Codes

• How do you handle alphanumeric data?

• Easy answer!
• Formulate a binary code to represent
characters! 
• For the 26 letter of the alphabet would need
5 bit for representation.
• But what about the upper case and lower
case, and the digits, and specialcharacters
45
43
 A code calledASCII

• ASCII stands for American Standard Code for

Information Interchange
• The code uses 7 bits to encode 128 unique
characters
• Reference the textbook, pg. 27, for a tableof
the ASCIIcode
• As a note, formally, work to create this code
began in 1960. 1st standard in 1963. Last
updated in 1986.
46
44
 ASCII Code

• Represents the numbers

– All start 011 xxxx and the xxxx is the BCDfor the
digit
• Represent the characters of the alphabet
– Start with either 100, 101, 110, or 111
– A few special characters are in this area
• Start with 010 – space and !”#$%&‟()*+.-,/
• Start with 000 or 001 – controlchar like ESC
47
45
 ASCII Example

• Encoding of 123
– 011 0001 011 0010 011 0011
• Encoding of Joanne
– 100 1010 110 1111 110 0001
– 110 1110 110 1110 110 0101

• Note that these are 7 bit codes

48
46
 Alphanumeric Codes

 Two widely used standards:

ASCII (American Standard Code for Information Interchange)
EBCDIC (Extended BCD Interchange Code)

 ASCII: 7-bit, plus a parity bit Character

0
ASCII Code
0110000
for error detection 1 0110001
(odd/even parity). ... ...
9 0111001
 EBCDIC:8-bit code. :
A
0111010
1000001
B 1000010
... ...
Z 1011010
[ 1011011
\ 1011100

49
 Alphanumeric Codes

 ASCII table:
MSBs
LSBs 000 001 010 011 100 101 110 111
0000 NUL DLE SP 0 @ P ` p
0001 SOH DC1 ! 1 A Q a q
0010 STX DC2 “ 2 B R b r
0011 ETX DC3 # 3 C S c s
0100 EOT DC4 $ 4 D T d t
0101 ENQ NAK % 5 E U e u
0110 ACK SYN & 6 F V f v
0111 BEL ETB „ 7 G W g w
1000 BS CAN ( 8 H X h x
1001 HT EM ) 9 I Y i y
1010 LF SUB * : J Z j z
1011 VT ESC + ; K [ k {
1100 FF FS , < L \ l |
1101 CR GS - = M ] m }
1110 O RS . > N ^ n ~
1111 SI US / ? O _ o DEL
50
Thank you

51