P U S A N U N I V E RS I T Y

Logic
Circuits
Chapter 1. Number systems

VISION Lab.
In this lecture,
• We will learn
• Number systems
• Converting the representation between different number systems
• Operations on binary numbers

VISION Lab. 1
Number Systems
• Number system is a system which defines how to represent or express
numbers.
• It needs to provide unique representation of each number.
• Example
• Decimal number system: 0,1,2,3,4,5,6,7,8,9,10….
• Binary number system : 0,1,10,11,100,…
• Ex) 正,正,正
• Ex) I, II, III, IV, V, VI, VII,

VISION Lab. 2
Integer Expression

• n: number of digits
• r: base or radix
• ai: coefficient

VISION Lab. 3
Decimal Number System (10진법)
• Decimal number system : use 0~9 to represent a given number
• Represent 1253 using decimal number system

• Digit is the coefficient which corresponds to each order of 10.

• To clearly label the number with a specific number system, radix(기수) is
written in the subscript.

VISION Lab. 4
Binary Number System (2진법)
• Binary number system : use 0 and 1 to represent a given number
• Radix = 2
• Example)
• Simple
• Needs longer place to write a big number
• To represent a large number, binary number system requires larger digits(or bits)*.
* Bits = Binary digits

VISION Lab. 5
Hexadecimal Number System (16진수)
• Represent the number using 0~9 and A~F
Decimal 0 1 2 3 4 5 6 7
Hexadecimal 0 1 2 3 4 5 6 7
Binary 0000 0001 0010 0011 0100 0101 0110 0111

Decimal 8 9 10 11 12 13 14 15
Hexadecimal 8 9 A B C D E F
Binary 1000 1001 1010 1011 1100 1101 1110 1111

• Example) 6C7.3A (16) = 6  100(16) + C  10(16) + 7  1(16) + 3  0.1 (16)+ A  0.01 (16)
= 6 16 2 + C 161 + 7 160 + 3 16-1 + A 16-2
• 4 digits of binary number is equivalent to single digit of hexadecimal
number : 24 = 161

VISION Lab. 6
Hexadecimal Number System (16진수)
• Example : Binary – hexadecimal convert
• Make a group for 4 digits of binary number from 0-th order, and convert each group
into hexadecimal number

10101110100010.0111111(2) = 10 1011 1010 0010.0111 111(2)

= 0010 1011 1010 0010.0111 1110(2)
= 2 B A 2. 7 E (16)

VISION Lab. 7
Binary, Hexadecimal, Decimal Numbers
• Equivalent representation of binary, hexadecimal and decimal numbers
Binary Hexadecimal Decimal
0000 0 0
0001 1 1
0010 2 2
0011 3 3
0100 4 4
0101 5 5
0110 6 6
0111 7 7
1000 8 8
1001 9 9
1010 A 10
1011 B 11
1100 C 12
1101 D 13
1110 E 14
1111 F 15

VISION Lab. 8
Converting Number Systems
• Binary representation of a number

• How to find given

• When X is represented by decimal number system, how we can find binary
representation of X?

VISION Lab. 9
Converting Number Systems
• From decimal to binary
• Converting integer number(정수) and decimal point(소수) separately
• Divide integer part by 2 and Multiply decimal point by 2
• Example ) 75.6875 (decimal to binary)
2 75 Remainder Binary Binary Integer Decimal point
2 37 ... 1 1 0. 6875
X 2
2 18 ... 1 11 0.1 1. 3750
Write integer part after
multiplication
2 9 ... 0 011 X 2
0.10 0. 7500
2 4 ... 1 1011
X 2
2 2 ... 0 01011 0.101 1. 5000
2 1 ... 0 001011 X 2 Repeat the multiplication
0.1011 1. 0 until decimal part
0 ... 1 1001011 becomes 0
Quotient

75.6875(10) = 1001011.1011(2)

VISION Lab. 10
Converting Number Systems
• Example ) 75.6 (decimal to binary)

VISION Lab. 11
Converting Number Systems
• Example ) 75.6 (decimal to binary)

2 75 Remainder → Binary Binary  Integer , decimal point

2 37 ... 1 1 0. 6
X 2
2 18 ... 1 11
0.1 1. 2
2 9 ... 0 011 X 2
2 4 ... 1 1011 0.10 0. 4
X 2
2 2 ... 0 01011
0.100 0. 8
2 1 ... 0 001011 X 2
0 ... 1 1001011 0.1001 1. 6
X 2
0.10011 1. 2 Decimal point does not
become 0 and is repeated
75.6(10) = 1001011.1001 1001 1001 1001......(2)
VISION Lab. 12
Converting Number Systems
• Another converting way

• Special feature of binary system :

• Find the largest power of 2 but less than or equal to the number
• Subtract from the number
• Repeat the process

VISION Lab. 13
Converting Number Systems
• Example 1.6) 746
1. → Subtract 512 from 746 : 746-512 = 234

2. → Subtract 128 from 234 : 234 - 128 = 106

3. → Subtract 64 from 106 : 106 - 64 = 42

4. → Subtract 32 from 42 : 42 - 32 = 10

5. → Subtract 8 from 10 : 10 - 8 = 2

6. → Done.

VISION Lab. 14
Binary Operations
• Binary addition
• Logic is the same with decimal number
• Add numbers on each digit at a time and place a carry to the next digit if a carry
comes out.
• Example)
carry 11 carry 1 1
00110001 1101
+ 00111010 + 0110
01101011 10011

VISION Lab. 15
Overflow
• In many digital system, there exists limitation on the range of numbers that
the system deals with.
• Example) Internet protocol address

VISION Lab. 16
Overflow
• In other words, only the numbers within the pre-defined range are allowed.
• However, what happens if we add two binary numbers and the result exceed
s the range?
• Overflow occurs
• For 4-bits memory, if we do 1101 + 0110, we have 10011 which is 5-bits-number.
• However, for 4-bit memory, there is no way to represent the first 1 in 10011.
• Hence, final output is given as 0011, which is different from correct answer.
• When overflow occurs, we have wrong answer.
• We need to check whether overflow occurs or not.

VISION Lab. 17
4-bit Adder
• Binary addition example • 1-bit Adder
carry 11
00110001
+ 00111010
01101011
<Truth table>
• 4-bit Adder
• a+b (binary)
• a = a4a3a2a1
• b = b4b3b2b1

VISION Lab. 18
Signed Numbers
• In our number systems, we also need negative numbers (ex. -7, -1101).
• However, negative sign is not a number that digital systems can
understand.
• Thus, we need a rule to represent signed numbers
• The followings are well-known ways of representing signed numbers
1. Signed-magnitude
2. One’s complement
3. Two’s complement

VISION Lab. 19
Signed-Magnitude
• The most significant bit(MSB, the most-left bit) is used to indicate sign of
the number and the other bits are used to represent magnitude

• Given n-bits, the range of representation becomes

• Note that there exist two zeros(0) : +0: 0000 and -0 : 1000

VISION Lab. 20
One’s complement
• For a positive number X, -X is represented as exchanging each bit of X
oppositely.
• Example X = 0101 → -X = 1010
• The reason why it is called as one(=1)’s complement (1의 보수) is that
negation of the number can be formed by subtracting the number from
long sequence of 1.
• X = 0101
• -X = 1111 – X = 1111 – 0101 = 1010
• Given n-bits, the range of representation becomes

• Note that there are two zeros in one’s complement

(+0 : 0000 and -0: 1111)
VISION Lab. 21
Two’s complement
• For a positive number X, -X is represented as exchanging each bit of X
oppositely and adding 1
• Example X = 0101 → -X = 1010 + 0001 = 1011
• The reason why it is called Two(2)’s complement (2의보수) is that negation
of X is made from subtracting X from the large power of 2.
→ –X is stored as the binary equivalent of 2n – X in an n-bit system.
• X = 0101
• -X = 10000 – 0101 = 1011
• -X = (1111 + 0001) – 0101 = 1111 – 0101 + 0001 = (One’s complement of X) + 0001
• Two’s complement can be written as the sum of one’s complement and 1.

VISION Lab. 22
Two’s complement
• Given n-bits, the range of representation becomes

• Note that in Two’s complement there exist single zero (0 = 00000)

• X = 0000 → -X = 1111 + 1 = 10000 (this is equivalent to 0000 given limit of bits
length)

VISION Lab. 23
Radix Complement
• Negative numbers, -a, in n digits are stored as rn – a.
• In decimal for example, this is called ten’s complement!
• ex) 2-digit decimal system, -16 would be stored as 100 – 16 = 84.

VISION Lab. 24
Binary Operation
• Binary subtraction
• With our intuition, subtraction can be considered as adding negation of the second
operand.

• Now, we want to see the result of subtraction based on our intuition.

• Examples : Given 4 bits,
• Representation of -0010
• Signed-magnitude : 1010
• One’s complement : 1101
• Two’s complement : 1110
• Results of subtraction
• Signed-magnitude : 0110 + 1010 = 10000 = 0(10) Something is wrong
• One’s complement : 0110 + 1101 = 10011 = 3(10) Something is wrong
• Two’s complement : 0110 + 1110 = 10100 = 4(10)

VISION Lab. 25
Binary Operation
• Binary subtraction
• Depending on the representation of signed number, we have different ways of
subtraction.
1. Signed-magnitude
• Check the operation, sign of all operands and magnitudes of all operands
• Calculate signs and magnitude with correct order

VISION Lab. 26
Binary Operation
• Binary subtraction
• Depending on the representation of signed number, we have different ways of
subtraction.
2. One’s complement
• Change the second operand to negated one
• If there exist any result carry, add 1 to the results
• Example)for 3-bit operation, - 2 + 3 = (-2) + (3) = (101) + (011)

101
+ 011
1 000 Carry comes out (called end-around carry)
+ 001 Discard carry and Add 1 to the result
001 Final answer

VISION Lab. 27
Binary Operation
• Binary subtraction
• One’s complement

Decimal 0 1 2 3 4 5 6 7

Unsigned 000 001 010 011 100 101 110 111

One’s complement 0 1 2 3 -3 -2 -1 -0

• Consider : -2 + 3 = -2 + 1 +1 +1 = 1
• ➔ -2(5) + 1 = -1(6) ➔ -1(6) + 1 = 0 (7) ➔ 0 + 1 = 0 (0)
• Since there exists two 0s ==> Even we add 1 to 111 (=0), still, we have 0 (=000).
• Thus, when the results of operation have carry, we need to add 1.

VISION Lab. 28
Binary Operation
• Binary subtraction
• Depending on the representation of signed number, we have different ways of
subtraction.
2. Two’s complement
• Change the second operand to negated one, and Add
• Example) 2 – 1
10
+ 11
1 01 Discard the carry
01 Final answer

• Due to its simplicity, two’s complement is widely used for binary

subtraction. Decimal 0 1 2 3 4 5 6 7

Unsigned 000 001 010 011 100 101 110 111

One’s complement 0 1 2 3 -4 -3 -2 -1
VISION Lab. 29
Binary Coded Decimal
• In digital systems such as computers, binary number are used for
processing.
• However, human operator interacts the digital systems with decimal
numbers.
• Converting process from decimal input to binary and from binary to
decimal output is necessary. Converting decimal to
binary

Decimal
7182 Binary
01010111
Decimal
1726
Converting binary to
VISION Lab.
decimal 30
Binary Coded Decimal
• Binary coded decimal is one of the way to map binary and decimal.
• Each digit of decimal number is mapped to binary.
• Since each digit of decimal can have 10 different values (0~9), we need at
least 4bits for each digit of decimal.
• Example) 256 → 2 = 0010, 5 = 0101, 6 = 0110
• 256 is mapped to 0010 0101 0110 in BCD.
• Requires larger size of bits than necessary
• 256(100000000) can be represented by 9 bits in unsigned binary number system
but is represented with 12 bits in BCD.

VISION Lab. 31
Binary Coded Decimal
• This converting (=code) is also called as 8421 code
• Each decimal digit is the weighted sum of binary number

Single decimal digit

• As each digit is represented by 4 bits, there are redundant binary numbers

which are not used. (10~15 → 0110 ~ 1111)
• We have different coding scheme (=different mapping scheme).
• 5421 code, 2421 code, excess 3

VISION Lab. 32
Other BCD codes
• 10’s Complement
• 275 (5421 code)
→0010 1010 1000
• 275 (2421 code)
→0010 1101 1011
• 275 (Excess 3 code)
→0101 1010 1000

VISION Lab. 33
Other Codes
• ASCII Code

VISION Lab. 34
Other Codes
• Gray code

VISION Lab. 35