Chapter 2

Number Systems and Logic Gates

(Digital Logic Design, ECEg 3142)

Faculty of computing and INFORMATICS

Sileshi A.
(sileshi120@gmail.com) 2021/2022
 Number system
 Decimal (base 10)
 Weights in powers of 10
 Decimal digits: 0, 1,….9
 Octal (base 8)
 Weights in powers of 8
 Octal digits: 0, 1, 2, 3, 4, 5, 6, 7.
 Hexadecimal (base 16)
 Weights in powers of 16
 Hexadecimal digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.
 Binary (base 2)
 Weights in powers of 2
 Binary digits (bits): 0, 1
 Decimal Number System

 Base (also called radix) = 10

 10 digits { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
2 1 0 -1 -2
 Digit Position
 Integer & fraction
5 1 2 7 4

 Digit Weight 100 10 1 0.1 0.01

Position
 Weight = (Base) 5 1 2 7 4
 Magnitude 500 10 2 0.7 0.04
 Sum of “Digit x Weight” d2*B2+d1*B1+d0*B0+d-1*B-1+d-2*B-2

 Formal Notation (512.74)10

 Octal Number System
 Base = 8 2 1 0 -1 -2
 8 digits { 0, 1, 2, 3, 4, 5, 6, 7 } 5 1 2 7 4
 Weights 64 8 1 1/8 1/64
 Weight = (Base) Position 5 1 2 7 4
 Magnitude 2 1 0 -1 -2
5*82+1 *81+2 *80+7 *8-1+4 *8-2
 Sum of “Digit x Weight”
=(330.9375)10
 Formal Notation
(512.74)8
 Hexadecimal Number System
 Base = 16
 16 digits { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F }

 Weights
256 16 1 1/16 1/256
Position
 Weight = (Base)
1 E 5 7 A
 Magnitude 2 1 0 -1 -2

 Sum of “Digit x Weight” 1 *162+14 *161+5 *160+7 *16-1+10 *16-2

 Formal Notation =(485.4765625)10

(1E5.7A)16
 Binary Number System

 Base = 2

 2 digits { 0, 1 }, called binary digits or “bits”

4 2 1 1/2 1/4
 Weights
Position
1 0 1 0 1
 Weight = (Base)
2 1 0 -1 -2
 Magnitude 1*22+0 *21+1 *20+0 *2-1+1 *2-2
 Sum of “Bit x Weight” =(5.25)10
 Formal Notation (101.01)2
 Groups of bits 4 bits = Nibble 1011
8 bits = Byte
11000101
 The Power of 2

n 2n n 2n
0 20=1 8 28=256
1 21=2 9 29=512
2 22=4 10 210=1024 Kilo

3 23=8 11 211=2048
4 24=16 12 212=4096
5 25=32 20 220=1M Mega

6 26=64 30 230=1G Giga

7 27=128 40 240=1T Tera

 Addition
 Decimal Addition

1 1 Carry
5 5
+ 5 5

1 1 0
= Ten ≥ Base
 Subtract a Base
 Binary Addition
 Column Addition

1 1 1 1 1 1
1 1 1 1 0 1 = 61
+ 1 0 1 1 1 = 23

1 0 1 0 1 0 0 = 84

≥ (2)10
 Binary Subtraction
 Borrow a “Base” when needed

1 2 = (10)2
0 2 2 0 0 2
1 0 0 1 1 0 1 = 77
− 1 0 1 1 1 = 23

0 1 1 0 1 1 0 = 54
 Exercise:
1 1 0 0 1 1 0 1 0
− 1 1 1 1 0 0
 Binary Multiplication

 Bit by bit

1 0 1 1 1
x 1 0 1 0
0 0 0 0 0
1 0 1 1 1
0 0 0 0 0
1 0 1 1 1

1 1 1 0 0 1 1 0
Number Base Conversions
Evaluate Magnitude

Octal
(Base 8)

Evaluate Magnitude
Decimal Binary
(Base 10) (Base 2)

Hexadecimal
Evaluate Magnitude (Base 16)
 Decimal (Integer) to Binary Conversion
 Divide the number by the ‘Base’ (=2)

 Take the remainder (either 0 or 1) as a coefficient

 Take the quotient and repeat the division

Example: (13)10
Operation Quotient Remainder Coefficient
13 / 2 = 6 1 a0 = 1
6 /2= 3 0 a1 = 0
3 /2= 1 1 a2 = 1
1 /2= 0 1 a3 = 1
Answer: (13)10 = (a3 a2 a1 a0)2 = (1101)2

MSB LSB
 Decimal (Fraction) to Binary Conversion
 Multiply the number by the ‘Base’ (=2)

 Take the integer (either 0 or 1) as a coefficient

 Take the resultant fraction and repeat the

multiplication
Example: (0.625)10
Operation Integer Fraction Coefficient
0.625 * 2 = 1 . 25 a-1 = 1
0.25 * 2 = 0 . 5 a-2 = 0
0.5 *2= 1 . 0 a-3 = 1
Answer: (0.625)10 = (0.a-1 a-2 a-3)2 = (0.101)2

MSB LSB
 Decimal to Octal Conversion
Example: (175)10

Operation Quotient Remainder Coefficient

175 / 8 = 21 7 a0 = 7
21 / 8 = 2 5 a1 = 5
2 /8= 0 2 a2 = 2
Answer: (175)10 = (a2 a1 a0)8 = (257)8
Example: (0.3125)10

Operation Integer Fraction Coefficient

0.3125 * 8 = 2 . 5 a-1 = 2
0.5 *8= 4 . 0 a-2 = 4
Answer: (0.3125)10 = (0.a-1 a-2 a-3)8 = (0.24)8

Exercise : convert it to octal (575.6125)10

 Binary − Octal Conversion
Octal Binary
 8 = 23
 Each group of 3 bits represents an octal 0 000
digit
1 001
2 010
Example: Assume Zeros
3 011

( 1 0 1 1 0 . 0 1 )2 4 100
5 101
6 110
( 2 6 . 2 )8 7 111
 Binary − Hexadecimal Conversion
Hex Binary
 16 = 24 0 0000
 Each group of 4 bits represents a 1 0001
hexadecimal digit 2 0010
3 0011
4 0100
5 0101
Example: Assume Zeros 6 0110
7 0111
8 1000
( 1 0 1 1 0 . 0 1 )2 9 1001
A 1010
B 1011
C 1100
D 1101
(1 6 . 4 )16 E 1110
F 1111
 Octal − Hexadecimal Conversion
 Convert to Binary as an intermediate step
Example:

( 2 6 . 2 )8

Assume Zeros Assume Zeros

( 0 1 0 1 1 0 . 0 1 0 )2

(1 6 . 4 )16
Decimal, Binary, Octal and Hexadecimal

Decimal Binary Octal Hex

00 0000 00 0
01 0001 01 1
02 0010 02 2
03 0011 03 3
04 0100 04 4
05 0101 05 5
06 0110 06 6
07 0111 07 7
08 1000 10 8
09 1001 11 9
10 1010 12 A
11 1011 13 B
12 1100 14 C
13 1101 15 D
14 1110 16 E
15 1111 17 F
 Complements
 Unsigned numbers: only non-negative values.

 Signed numbers: include all values (positive and negative)

 There are 3 common representations for signed

binary numbers:
 1s Complement

 2s Complement

 Sign-and-Magnitude
 Complements
 There are two types of complements for each base-r system: the radix
complement and diminished radix complement.
 Diminished Radix Complement (r-1)’s Complement
 Given a number N in base r having n digits, the (r–1)’s
complement of N is defined as:
(rn –1) – N
 Example for 6-digit decimal numbers:
 9’s complement is (rn – 1)–N = (106–1)–N = 999999–N
 9’s complement of 546700 is 999999–546700 =
453299
 Example for 6-digit binary numbers:
 1’s complement is (rn – 1) – N = (26–1)–N = 111111–N
 1’s complement of 101100 is 111111–101100 =
010011
 Complements
 1’s Complement (Diminished Radix Complement)

 All ‘0’s become ‘1’s

 All ‘1’s become ‘0’s

Example (10110000)2

 (01001111)2

If you add a number and its 1’s complement …

10110000
+ 01001111
11111111
 Complements
 Radix Complement
The r's complement of an n-digit number N in base r is defined as
rn – N for N ≠ 0 and as 0 for N = 0. Comparing with the (r  1) 's
complement, we note that the r's complement is obtained by adding
1 to the (r  1) 's complement, since rn – N = [(rn  1) – N] + 1.

 Example: Base-10

The 10's complement of 012398 is 987602

The 10's complement of 246700 is 753300

 Example: Base-2

The 2's complement of 1101100 is 0010100

The 2's complement of 0110111 is 1001001
 Complements
 2’s Complement (Radix Complement)

 Take 1’s complement then add 1

Example:

10110000
01001111
+ 1
01010000
 Signed Binary Numbers
 To represent negative integers, we need a notation for negative values.

 It is customary to represent the sign with a bit placed in the leftmost

position of the number in binary digits.

 The convention is to make the sign bit 0 for positive and 1 for negative.

 Example:
 Signed Binary Numbers
 Arithmetic addition:

 The addition of two numbers in the signed-magnitude system follows the rules of
ordinary arithmetic. If the signs are the same, we add the two magnitudes and give
the sum the common sign. If the signs are different, we subtract the smaller
magnitude from the larger and give the difference the sign if the larger magnitude.

 The addition of two signed binary numbers with negative numbers represented in
signed-2's-complement form is obtained from the addition of the two numbers,
including their sign bits.

 A carry out of the sign-bit position is discarded.

 Example:
 Signed Binary Numbers
 Arithmetic Subtraction
 In 2’s-complement form:
1. Take the 2’s complement of the subtrahend (including the sign bit)
and add it to the minuend (including sign bit).
2. A carry out of sign-bit position is discarded.

(  A)  (  B )  (  A)  (  B )
(  A)  (  B )  (  A)  (  B )

 Example:

( 6)  ( 13) (11111010  11110011)

(11111010 + 00001101)
00000111 (+ 7)
 Binary codes
 If we want to represent a Decimal number in a binary

form, we have more ways than the obvious choice of a

straight conversion.

 There are a dozen or more ways of representing a Decimal

number , each with their own advantages and disadvantages.

 If the input to a circuit gives rise to a binary code at the

output, we have what we call a 'binary coded decimal' or

BCD.
 Binary Coded Decimal (BCD)
 BCD Code
 A number with n decimal digits will
require 4n bits in BCD.

 Decimal 396 is represented in BCD

with 12bits as 0011 1001 0110,
with each group of 4 bits
representing one decimal digit.

 A decimal number in BCD is the

same as its equivalent binary
number only when the number is
between 0 and 9.

 The binary combinations 1010

through 1111 are not used and have
no meaning in BCD.
 BCD
 Example:
 Consider decimal 185 and its corresponding value in BCD
and binary:

 BCD addition
 Binary Code
 Example:
 Consider the addition of 184 + 576 = 760 in BCD:

 Decimal Arithmetic: (+375) + (-240) = +135

Hint 6: using 10’s of BCD

 Alphanumeric Codes
 American Standard Code for Information Interchange
(ASCII) Character Code
 ASCII Character Code
 ASCII Character Codes
 American Standard Code for Information Interchange (Refer to

the above tables)

 A popular code used to represent information sent as character-

based data.

 It uses 7-bits to represent:

 94 Graphic printing characters.

 34 Non-printing characters.

 Some non-printing characters are used for text format (e.g. BS =

Backspace, CR = carriage return).

 Other non-printing characters are used for record marking and

flow control (e.g. STX and ETX start and end text areas).
 ASCII Properties
 ASCII has some interesting properties:

 Digits 0 to 9 span Hexadecimal values 3016 to 3916

 Upper case A-Z span 4116 to 5A16

 Lower case a-z span 6116 to 7A16

» Lower to upper case translation (and vice versa) occurs by

flipping bit 6.
 Binary Codes
 Error-Detecting Code
 To detect errors in data communication and processing, an
eighth bit is sometimes added to the 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.
 Example:
 Consider the following two characters and their even and
odd parity:
 Binary Codes
 Error-Detecting Code:
 Redundancy (e.g. extra information), in the form of extra bits, can
be incorporated into binary code words to detect and correct errors.

 A simple form of redundancy is parity, an extra bit appended onto

the code word to make the number of 1’s odd or even. Parity can
detect all single-bit errors and some multiple-bit errors.

 A code word has even parity if the number of 1’s in the code word is
even.

 A code word has odd parity if the number of 1’s in the code word is
odd.

 Example: Message A: 10001001 1 (even parity)

Message B: 10001001 0 (odd parity)
 Error Detection Codes
 Parity bit.
 Even parity: additional bit supplied to make total number of

‘1’s even.

 Odd parity: additional bit supplied to make total number of

‘1’s odd.
Character ASCII Code
 Example: Odd parity. 0 0110000 1
1 0110001 0
... ...
Parity bits
9 0111001 1
: 0111010 1
A 1000001 1
B 1000010 1
... ...
Z 1011010 1
[ 1011011 0
\ 1011100 1
 Gray Code
 In a Gray code only one bit changes between each pair of successive

code words.

 Unweight (not an arithmetic code).

 Gray code is a reflected code.

 It can be defined recursively using the following rules:

 A 1-bit Gray code has two code words, 0 and 1.

 The first 2n code words of an (n+1)-bit Gray code equal the code words of an n-
bit gray code, written in order with a leading 0 appended.

 The last 2n code words of an (n+1)-bit Gray code equal the code words of an n-
bit gray code, but written in reverse order with a leading 1 appended.
Gray Code
 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 Gray code.

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
 Logic Gates
 A gate is an electronic device that produces a result
based on two or more input values.
 In reality, gates consist of one to six transistors, but
digital designers think of them as a single unit.

 Integrated circuits contain collections of gates suited

to a particular purpose.

 Basic Logic gates: NOT, AND, OR

 Derived logic gates: NAND, NOR, XOR, XNOR

Logic Gates
 Binary Logic
 Truth Tables, Boolean Expressions, and Logic Gates

AND OR NOT
x y z x y z x z
0 0 0 0 0 0 0 1
0 1 0 0 1 1 1 0
1 0 0 1 0 1
1 1 1 1 1 1

z=x•y=xy z=x+y z = x = x’

x x x
y z y z z
 Switching Circuits

AND OR
Implementation of Inverter (NOT) gate
Implementation of AND gate
Implementation of OR gate
 NAND Gate

NAND
A B C
A 0 0 1
0 1 1
Z
1 0 1
B 1 1 0

C = ~(A & B)
nand(C,A,B)
 NAND Gate

NOT-AND
A B D C
A 0 0 0 1
D 0 1 0 1
C
1 0 0 1
B 1 1 1 0

D = A & B

C = ~D = ~(A & B)
 NOR Gate

NOR
A B C
A 0 0 1
C 0 1 0
B 1 0 0
1 1 0
C = ~(A | B)
nor(C,A,B)
 NOR Gate

NOT-OR
A B D C
A 0 0 0 1
D C 0 1 1 0
B 1 0 1 0
1 1 1 0
D = A | B

C = ~D = ~(A | B)
 NAND Gate

A C A C
=
B B

C = ~(A & B) Z = ~A | ~B

A B D C A B ~A ~B C
0 0 0 1 0 0 1 1 1
0 1 0 1 0 1 1 0 1
1 0 0 1 1 0 0 1 1
1 1 1 0 1 1 0 0 0
De Morgan’s Theorem-1

~(A & B) = ~A | ~B

• NOT all variables

• Change & to | and | to &
• NOT the result
 NOR Gate

A A
C C
B B

C = ~(A | B) C = ~A & ~B

A B C A B ~A ~B C
0 0 1 0 0 1 1 1
0 1 0 0 1 1 0 0
1 0 0 1 0 0 1 0
1 1 0 1 1 0 0 0
De Morgan’s Theorem-2

~(A | B) = ~A & ~B

• NOT all variables

• Change & to | and | to &
• NOT the result
Implementation of NAND gate
Implementation of NOR gate
 Exclusive-OR Gate

XOR A B C
A
C 0 0 0
B
0 1 1
C = A ^ B 1 0 1
xor(C,A,B)
1 1 0
 Exclusive-NOR Gate

XNOR A B C
A
C 0 0 1
B
0 1 0
C = ~(A ^ B)
C = A ~^ B 1 0 0
xnor(C,A,B) 1 1 1
Multiple-input Gates

C1 C2

C3 C4
DLD Assignment from Chapter 2 (Individual Assignment)
1. Convert the binary number 1001.0010 to decimal.
2. Explain in detail: a. The difference between 1’s and 2’s complement. b. The
advantage of 2’s complement over 1’s complement.
3. What is the procedure for converting a decimal number to 2's complement representation?
4. Decode the following ASCII code: 10100111010100101010110001001011001
01000001001000100000110100101000100
5. Convert binary 111111110010 to hexadecimal.
6. Represent ±165 decimal number using sing-magnitude and 2’s techniques with an appropriate bit size.
7. Convert the given Octal 7652 to an equivalent hexadecimal
8. Encode the following massage to ASCII code: BME GC of 2015
9. Convert the decimal value 659.725 to BCD
10. Convert 8B3F to binary.
11. Which one is the proper odd parity bit to the code 111001: A. 1111011 B. 0111111 C. 1111001
D. 0011111 E. None
12. Convert the following binary number to octal: 010111100
13. Convert the following signed binary number to decimal: 10011010
14. Convert the given binary, 1100101000110101 to hexadecimal.
15. Generate a truth table and Boolean expression for a three-input AND and OR gate.
16. Implement the AND, OR,NOT , NOR, XOR and XNOR gates using the universal NAND
gate. Do the questions according to your class number
(odds – do the odds while evens – do the evens).
The end of chapter 2