CST 203

LOGIC SYSTEM
DESIGN
1
LOGIC SYSTEM DESIGN

2
 LOGIC SYSTEM DESIGN

CO1 Illustrate decimal, binary, octal, hexadecimal and BCD number systems, perform
conversions among them and do the operations - complementation, addition,
subtraction, multiplication and division on binary numbers (Cognitive Knowledge
Level: Understand)

CO2 Simplify a given Boolean Function and design a combinational circuit to implement the simplified
function using Digital Logic Gates (Cognitive Knowledge level:
Apply)

CO3 Design combinational circuits - Adders, Code Convertors, Decoders, MagnitudeComparators, Parity
Generator/Checker and design the Programmable Logic Devices - ROM and PLA. (Cognitive
Knowledge level: Apply)

CO4 Design sequential circuits - Registers, Counters and Shift Registers. (Cognitive
Knowledge level: Apply)

CO5 Use algorithms to perform addition and subtraction on binary, BCD and floating point
numbers (Cognitive Knowledge level: Understand)
3
MODULE 1
Decimal

NUMBER SYSTEMS Binary

Octal
Hexadecimal
4
 COMMON NUMBER
SYSTEMS
Used by Used in
System Base Symbols humans? computers?
Decimal 10 0, 1, … 9 Yes No
Binary 2 0, 1 No Yes
Octal 8 0, 1, … 7 No No
Hexa- 16 0, 1, … 9, No No
decimal A, B, … F

Number systems 5
 QUANTITIES/
COUNTING
Hexa- Hexa-
Decimal Binary Octal decimal Decimal Binary Octal decimal
0 0 0 0 8 1000 10 8
1 1 1 1 9 1001 11 9
2 10 2 2 10 1010 12 A
3 11 3 3 11 1011 13 B
4 100 4 4 12 1100 14 C
5 101 5 5 13 1101 15 D
6 110 6 6 14 1110 16 E
7 111 7 7 15 1111 17 F

Number systems 6
 QUANTITIES/
COUNTING
Hexa-
Decimal Binary Octal decimal
16 10000 20 10
17 10001 21 11
18 10010 22 12
19 10011 23 13
20 10100 24 14
21 10101 25 15
22 10110 26 16
23 10111 27 17

Number systems LOGIC SYSTEM DESIGN||MODULE 1||DR. BIBIN VINCENT||ASSOCIATE PROFESSOR||KMEA 7

 CONVERSION AMONG
BASES
The possibilities:

Decimal Octal

Binary Hexadecimal

Number systems 8
QUICK EXAMPLE

2510 = 110012 = 318 = 1916

Number systems 9
 DECIMAL TO DECIMAL

Decimal Octal

Binary Hexadecima
l

Number systems 10
 Weight
2 1 0 Position

1 2 5
12510 => 5 x 100 = 5
2 x 101 = 20 102 101 100 Weights

1 x 102 = 100

125

Base

Number systems 11
 BINARY TO DECIMAL

Decimal Octal

Binary Hexadecimal

Number systems 12
BINARY TO DECIMAL
Technique

Multiply each bit by 2n, where n is the “weight” of

the bit

The weight is the position of the bit, starting from

0 on the right

Add the results

Number systems 13
EXAMPLE
Bit “0”

1010112 => 1 x 20 = 1
1 x 21 = 2
0 x 22 = 0
1 x 23 = 8
0 x 24 = 0
1 x 25 = 32
4310

Number systems 14
OCTAL TO DECIMAL

Decimal Octal

Binary Hexadecimal

Number systems 15
OCTAL TO DECIMAL
Technique

Multiply each bit by 8n, where n is the “weight” of the bit

The weight is the position of the bit, starting from 0 on

the right

Add the results

Number systems 16
EXAMPLE

7248 => 4 x 80 = 4
2 x 81 = 16
7 x 82 = 448

46810

Number systems 17
HEXADECIMAL TO
DECIMAL
Decimal Octal

Binary Hexadecimal

Number systems 18
HEXADECIMAL TO
DECIMAL
Technique

Multiply each bit by 16n, where n is the “weight” of the bit

The weight is the position of the bit, starting from 0 on the

right

Add the results

Number systems 19
EXAMPLE

ABC16 => C x 160 = 12 x 1 = 12

B x 161 = 11 x 16 = 176
A x 162 = 10 x 256 = 2560
274810

Number systems 20
DECIMAL TO BINARY

Decimal Octal

Binary Hexadecimal

Number systems 21
DECIMAL TO BINARY
Technique

Divide by two, keep track of the remainder

First remainder is bit 0 (LSB, least-significant bit)

Second remainder is bit 1

Etc.

Number systems 22
EXAMPLE
2 125
12510 = ?2 2 62 1
2 31 0
2 15 1
2 7 1
2 3 1
2 1 1
0 1

12510 = 11111012
OCTAL TO BINARY

Decimal Octal

Binary Hexadecimal

Number systems 24
OCTAL TO BINARY
Technique
Convert each octal digit to a 3-bit equivalent binary
representation
EXAMPLE
7058 = ?2 7 0 5

111 000 101

7058 = 1110001012

Number systems 25
HEXADECIMAL TO
BINARY
Decimal Octal

Binary Hexadecimal

Number systems 26
HEXADECIMAL TO BINARY
Technique
Convert each hexadecimal digit to a 4-bit equivalent binary
representation
EXAMPLE
1 0 A F
10AF16 = ?2

0001 0000 1010 1111

10AF16 = 00010000101011112

Number systems 27
DECIMAL TO OCTAL

Decimal Octal

Binary Hexadecimal

Number systems 28
DECIMAL TO OCTAL
Technique
 Divide by 8
 Keep track of the remainder

EXAMPLE
8 1234
123410 = ?8 8 154 2
8 19 2
8 2 3
0 2

123410 = 23228
Number systems 29
DECIMAL TO
HEXADECIMAL
Decimal Octal

Binary Hexadecimal

Number systems 30
DECIMAL TO HEXADECIMAL
Technique
 Divide by 16
 Keep track of the remainder

123410 = ?16 16 1234

16 77 2
16 4 13 = D
0 4

123410 = 4D216
Number systems 31
BINARY TO OCTAL

Decimal Octal

Binary Hexadecimal

Number systems 32
BINARY TO OCTAL
Technique
Group bits in threes, starting on right
Convert to octal digits

10110101112 = ?8
1 011 010 111

1 3 2 7

10110101112 = 13278

Number systems 33
BINARY TO HEXADECIMAL

Decimal Octal

Binary Hexadecimal

Number systems 34
BINARY TO HEXADECIMAL
Technique
 Group bits in fours, starting on right
 Convert to hexadecimal digits

10101110112 = ?16
10 1011 1011

2 B B

10101110112 = 2BB16

Number systems 35
OCTAL TO
HEXADECIMAL
Decimal Octal

Binary Hexadecimal

Number systems 36
OCTAL TO HEXADECIMAL
Technique
 Use binary as an intermediary

1 0 7 6
10768 = ?16

001 000 111 110

2 3 E

10768 = 23E16
Number systems 37
HEXADECIMAL TO
OCTAL
Decimal Octal

Binary Hexadecimal

Number systems 38
HEXADECIMAL TO OCTAL
Technique
Use binary as an intermediary

1F0C16 = ?8 1 F 0 C

0001 1111 0000 1100

1 7 4 1 4

1F0C16 = 174148
Number systems 39
EXERCISE
Hexa-
Decimal Binary Octal decimal
33
1110101
703
1AF

Skip answer Answer

Number systems 40
 EXERCISE – CONVERT …
Answer

Hexa-
Decimal Binary Octal decimal
33 100001 41 21
117 1110101 165 75
451 111000011 703 1C3
431 110101111 657 1AF

Number systems 41
FRACTIONS
Decimal to decimal

3.14 => 4 x 10-2 = 0.04

1 x 10-1 = 0.1
3 x 100 = 3
3.14

Number systems 42
FRACTIONS
Binary to decimal

10.1011 => 1 x 2-4 = 0.0625

1 x 2-3 = 0.125
0 x 2-2 = 0.0
1 x 2-1 = 0.5
0 x 20 = 0.0
1 x 21 = 2.0
2.6875

Number systems 43
FRACTIONS
Decimal to binary .14579
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.
Number systems 44
EXERCISE
Hexa-
Decimal Binary Octal decimal
29.8
101.1101
3.07
C.82

Skip answer Answer

Number systems 45
 EXERCISE
Answer

Hexa-
Decimal Binary Octal decimal
29.8 11101.110011… 35.63… [Link]…
5.8125 101.1101 5.64 5.D
3.109375 11.000111 3.07 3.1C
12.5078125 1100.10000010 14.404 C.82

Number systems 46
MODULE 1
BINARY NUMBER
1’s and 2’s compliment
Signed number
representation
SYSTEM Binary arithmetic
Binary subtraction
47
BINARY ADDITION (1 OF 2)
Two 1-bit values

A B A+B
0 0 0
0 1 1
1 0 1
1 1 10
“two”

Number systems 40
BINARY ADDITION
Two n-bit values
Add individual bits
Propagate carries
E.g.,
1 1
10101 21
+ 11001 + 25
101110 46

Number systems 49
Binary Subtraction

Number systems 50
Binary Subtraction

Number systems 51
Binary Multiplication Binary Division

Number systems 52
Number systems 53
Number systems 54
REPRESENTING SIGNED NUMBERS
DECIMAL N  N
Ex. 4-bit signed magnitude 0 0000 1000
1 bit for sign
1 0001 1001
3 bits for magnitude
2 0010 1010
3 0011 1011
4 0100 1100
5 0101 1101
6 0110 1110
SIGN BIT
7 0111 1111
Number systems 55
Ex 1. Find the sign/mag representation of -610

Step1: find binary representation using 8 bits

610 = 000001102

Step2: if the number is a negative number flip left

most bit
10000110
So: -610 = 100001102 (in 8-bit sign/magnitude form)
Number systems 56
 Ex 2. Find the signmag representation of -3610

Step 1: find binary representation using 8 bits

3610 = 001001002
Step 2: if the number is a negative number flip left
most bit
10100100
So: -3610 = 101001002 (in 8-bit sign/magnitude
form)

Number systems 57
 Ex 3. Find the signmag representation of 7010

Step 1: find binary representation using 8 bits

7010 = 010001102
Step 2: if the number is a negative number flip
left most bit
01000110 (no flipping, since it is +ve)

So: 7010 = 010001102 (in 8-bit sign/magnitude

form)
Number systems 58
 What is this sign-mag number?

100000002

The machine will think of it as - 0 , which is a non

valid value.

Number systems 59
TWO’S COMPLEMENT
REPRESENTATION
Ex. Find the two’s complement
representation of –610

Step1: find binary representation in 8 bits

610 = 000001102

Number systems 60
TWO’S COMPLEMENT
REPRESENTATION
Step 2: Complement the entire positive number, and then
add one

00000110
(complemented) ->11111001
(add one) ->+ 1
11111010

So: -610 = 111110102 (in 2's complement form)

Number systems 61
TWO’S COMPLEMENT
REPRESENTATION
Alternative method for step 2

Scan binary representation from right

too left, find first one bit, from low-order
(right) end, and complement the
remaining pattern to the left.

00000110
(left complemented) --> 11111010

Number systems 62
Ex 2: Find the Two’s Complement of -7610

Step 1: Find the 8 bit binary representation of the positive value.

7610 = 010011002

Step 2:
Find first one bit, from low-order (right) end, and complement the pattern to the left.
01001100
(left complemented) -> 10110100

So: -7610 = 101101002 (in 2's complement form, using any of above methods)

Number systems 63
Ex 3: Find the Two’s Complement of 7210

Step 1: Find the 8 bit binary representation of the

positive value.

7210 = 010010002
Step 2:

Since number is positive do

nothing.

So: 7210 = 010010002 (in 2's complement form, using

any of above methods)
Number systems 64
 Binary subtraction using 2’s
compliment
To subtract +7 from +3, we add the code for -7, 1001, to that of +3,
0011:

0011 (+3)
+1001 (-7)
1100 (-4)
The result, 1100, is the code for -4, the result of
subtracting +7 from +3.

Number systems 65
MODULE 1
Grey Code

BINARY CODES
BCD Code
Excess -3 Code
Parity and Hamming Code
ASCII Code
66
BCD
The BCD is simply the 4 bit
representation of the decimal digit.
For multiple digit base 10 numbers,
each symbol is represented by its
BCD digit
What happened to 6 digits not
used?

Number systems 67
BCD
Would it be easy for you if you can
replace a decimal number with an
individual binary code?
Such as 00011001 = 1910

The 8421 code is a type of BCD to do

that.
BCD code provides an excellent interface
to binary systems:
Keypad inputs
Digital readouts 68
 BCD
Decimal 0 1 2 3 4 5 6 7 8 9
Digit
BCD 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001

Note: 1010, 1011, 1100, 1101, 1110, and 1111 are INVALID CODE!

Let’s crack these…

ex1: dec-to-BCD ex2: BCD-to-dec
a) 35 a) 10000110
b) 98 b) 001101010001
c) 170 c) 1001010001110000
d) 2469

Number systems 69
BCD OPERATION
Consider the following BCD operation
Decimal: Add 4 + 1

Covert to binary 0100

And 0001
Getting 0101
Which is still a BCD representation of a
decimal digit
Number systems 70
A second example
 3 0011
 +3 0011
Getting 6 or 0 1 1 0

And in range and a BCD digit

representation

Number systems 71
AND NOW
Consider 5 + 5
5 0101
+5 0 1 0 1
giving 1 0 1 0 which is binary 10 but not a BCD
digit!
What to do?
Try adding 6 !!

Number systems 72
ADDING 6
Had 1010 and want to add 6 or 0110
 so 1010
 plus 6 0110
Giving 10000

Or a carry out to the next binary digit, or if

the binary in BCD, the next BCD digit.

Number systems 73
ANOTHER CARRY EXAMPLE
Add 7 + 6

 have 7 0111
 plus 6 0110
Giving 1 1 0 1 and again out of range
Adding 6 0110
Giving1 0 0 1 1 so a 1 carries out to the next BCD
digit

FINAL BCD answer 0001 0011 or 1310 74

MULTIBIT BCD
Add the BCD for 417 to 195
Would expect to get 612

BCD setup - start with Least Significant Digit

 0100 0001 0111
 0001 1001 0101
 1100
Adding 6 0110
Gives 10010

Number systems 75
CONTINUING MULTIBIT
Had a carry to the 2nd BCD digit position
 1
 0100 0001 done
 0001 1001 0010
 1011
Again must add 6 0 1 1 0
Giving 10001
And another carry

Number systems 76
STILL CONTINUING
MULTIBIT
Had a carry to the 3rd BCD digit position
 1
 0 1 0 0 done done
 000100010010
 0110

And answer is 0110 0001 0010 or the BCD for the

base 10 number 612

Number systems 77
GRAY CODES
Gray code. The reflected binary code
(RBC), also known as Gray code after
Frank Gray, is a binary numeral system
where two successive values differ in
only one bit (binary digit).

Number systems 78
GRAY CODES
The Gray code is unweighted and is not an
arithmetic code.

There are no specific weights assigned to the bit

positions.

Important: the Gray code exhibits only a

single bit change from one code word to
the next in sequence.

Number systems 79
GRAY CODES

Number systems 80
Binary-to-Gray code conversion

The MSB in the Gray code is the same as

corresponding MSB in the binary number.
Going from left to right, add each adjacent pair of
binary code bits to get the next Gray code bit.
Discard carries.

ex: 101102 to Gray code

convert
1 + 0 + 1 + 1 + 0 binary

1 1 1 0 1 Gray
Number systems 81
Gray-to-Binary Conversion

The MSB in the binary code is the same as the

corresponding bit in the Gray code.
Add each binary code bit generated to the Gray code bit in
the next adjacent position. Discard carries.
ex: convert the Gray code word 11011 to binary
1 1 0 1 1 Gray
+ + + +
1 0 0 1 0 Binary
Number systems 82
The Excess-3 (XS-3) Code

The Excess-3 (XS-3) BCD code does not use the principle of
positional weights into consideration while converting the decimal
numbers to 4-bit BCD system. Therefore, we can say that this code
is a non-weighted BCD code.
The function of XS-3 code is to transform the decimal numbers into
their corresponding 4-bit BCD code.

In this code, the decimal number is transformed to the 4-bit BCD

code by first adding 3 to all the digits of the number and then
converting the excess digits, so obtained, into their corresponding
8421 BCD code. Therefore, we can say that the XS-3 code is
strongly related with 8421 BCD code in its functioning.

Number systems 83
The Excess-3 (XS-3) Code

Decimal digits Excess-3 BCD code

0 0011
1 0100
2 0101
3 0110
4 0111
5 1000
6 1001
7 1010
8 1011
9 1100

Number systems 84
ASCII CODES
ASCII stands for American Standard Code for
Information Interchange
The code uses 7 bits to encode 128 unique
characters
It has the word length 7 and codes decimal digits, the characters
of the latin alphabet as well as special character. From the 128
possible binary words are 32 pseudo-words and/or control
characters.

Number systems 85
ASCII CODES

Number systems 86
ER ROR DETECTION / COR RECTING CODES

Why might we need Error detection/correction?

Even & Odd Parity

 Error detection

Hamming code
 Used for error detection & error correction

Number systems 87
PARITY BITS
ASCII – 7 bit code (hex 00 to 7F)
Could use “8th” bit for parity bit:
X1011010

 Even parity: make total number of “1” bits is even

01011010

Odd parity: make total number of “1” bits odd

11011010
If a parity bit is added to a bit stream, then there is a basis to
check for bit(s) being corrupted.
Number systems 88
Suppose you receive a binary bit word
“0101” and you know you are using an
odd parity.
Is the binary word errored?
The answer is yes:
 There are 2 1-bit, which is an even number
 We are using an odd parity
 So there must have an error.

Number systems 89
 A single bit is appended to each data
chunk
makes the number of 1 bits even/odd
Example: even parity
(1)1000000
(0)1111101
(1)1001001
Example: odd parity
(0)1000000
(1)1111101
(0)1001001
Number systems 90
 Suppose you are using an odd parity.
What should the binary word “1010”
look like after you add the parity bit?
Answer:
There is an even number of 1-bits.
 So we need to add another 1-bit
Our new word will look like “10101”.

Number systems 91
 Hamming Code (7,4) [1 bit error correction]

A Hamming code is a linear error-correcting code named after its

inventor, Richard Hamming. Hamming codes can detect up to two bit
errors, and correct single-bit errors. This method of error correction is best
suited for situations in which randomly occurring errors are likely, not for
errors that come in bursts.

Number systems 92
The format of a Hamming code is:
12 3 4 5 6 7
P1 P2 D3 P4 D5 D6 D7
• Here 1,2,4 are the parity bits and 3,5,6,7 are the
Information/Data bits

Number systems 93
Example: Encode the data bits 1101 into a 7-bit even parity Hamming code.

Number systems 94
Number systems 95
Number systems 96
Number systems 97
Number systems LOGIC SYSTEM DESIGN||MODULE 1||DR. DILEESH E D 98