E1121 DIGITAL LOGIC (A)

FALL 2018
Lecture 1
Number System
Course information
 Lecture Schedule Th. 11.30AM – 1.10 PM
 Instructor
 Dr. Marwa Abdelrazik Elmenyawi
 Marwa.elmenyawi@bhit.bu.edu.eg
 Office Hours: Tuesday 1.30-2.30 PM.
 Teaching Assistants
 Eng. Nada
 Eng Eman
 Eng. Mariam
Course information
 Grading
 Section & lab 10% (typically every week)
 Midterm 25% ( at 9 th week)

 Interview and Lab exam 15%

The student will be informed with any change

 Textbook
 M. Morris Mano and Michael D. Ciletti, Digital Design: With an Introduction to the Verilog HDL,
5th Edition, Prentice Hall. 2013
 Promises

 Detail: We will try to explain every construct used in this course in sufficient detail for
real understanding
 There is no “magic”
 Utility: We will try to explain only useful concepts, constructs, and techniques
 We will not try to explain every obscure detail
 Completeness: The concepts, constructs, and techniques can be used in combination to
construct useful programs
 There are, of course, many useful concepts, constructs, and techniques beyond what is taught here
 Simplicity: The examples used are among the simplest realistic ones that illustrate the
concepts, constructs, and techniques
 Your exercises and projects will provide more complex examples
Why are we here?
 Obvious reasons
 Course is “required”, prerequisite for some courses such as
 E1222 Computer Architecture
 E1321 Microprocessors I , E1322Microprocessors II
 Digital systems are widespread in use.
 Integrated Circuits that operate on digital data are in 95% of every electrical powered device
in the U.S.

 More important reasons

 Inherent parallelism in hardware;
 The job market for engineers and computer scientists with Digital Design
skills is at high and will continue growing.
Course Objectives

 Explain the elements of digital system abstractions such as

 digital logic, Boolean algebra…… etc.

 Design simple digital systems based on these digital abstractions

 Use basic digital tools and devices such as FPGA and VHDL.

 Work in a design team that

 can propose, design, successfully implement, and report on a digital circuit design project.
Course Outcomes

 Use Boolean Algebra and resulting logic for control and data paths

 Analyze a given digital system and decompose it into logical blocks.

 Do simple design with basic digital building blocks such as multiplexors, decoder, adder…etc

 Use industry standard CAD software that implements VHDL and can be used to program
devices.

 Synthesize a given system starting with problem requirements, identifying and designing the building
blocks, and then integrating blocks designed earlier
Course Topics
 Number Systems
 Logic Gates
 Boolean Algebra
 Karnaugh Map
 Combinational circuits
 Boolean function, truth table, circuit
 Decoder/Encoder
 Multiplexer/Demultiplexer
 Adder/Subracter/Multiplier

 Hardware Description Language

Chapter 1 Number Systems and Codes

• Computers and other digital systems process information as their

primary function.
• It is necessary to have methods and systems for representing
information in forms that can be manipulated and stored using
electronic or other types of hardware.
Outline of Chapter 1
 Number Systems
 Number-base Conversions
 Arithmetic Operations
 Complements
 Signed Binary Numbers
 Binary Codes
Outline of Chapter 1
 Number Systems
 Number-base Conversions
 Arithmetic Operations
 Complements
 Signed Binary Numbers
 Binary Codes
 Introduction to Numbering Systems
1

 We are all familiar with the decimal number system (Base 10). Some
other number systems that we will work with are:

 Binary
 Octal
 Hexadecimal
 Binary numbers?
2

 Computers work only on two states

 On
 Off

 Basic memory elements hold only two states

 Zero / One

 Thus a number system with two elements {0,1}

 A binary digit – bit !
 Octal & Hexadecimal System
3

 Computer scientists are often looking for shortcuts to do things

 One of the ways in which we can represent binary numbers is to use

their octal equivalents instead

 This is especially helpful when we have to do fairly complicated tasks

using numbers

14
 Numbers
4

 Each number system is associated with a base or radix

 For example: The decimal number system is said to be of base or radix 10

 A number in base r contains r digits 0,1,2,...,r-1

 Decimal (Base 10): 0,1,2,3,4,5,6,7,8,9

 Numbers are usually expressed in positional notation

– MSD: most significant digit

– LSD: least significant digit
 Characteristics of Numbering Systems
5

1) The digits are consecutive.

2) The number of basic digits is equal to the size of the base.

3) Zero is always the first digit.

4) The base number is never a digit.

5) When 1 is added to the largest basic digit, a sum of zero and a carry of one results.

6) Numeric values are determined by the implicit positional values of the digits.
 Common Number Systems
6

Used by Used in
System Base Basic digit humans? computers?
Decimal 10 0, 1, … 9 Yes No
Binary 2 0, 1 No Yes
Octal 8 0, 1, … 7 No No
Hexadecimal 16 0, 1, … 9, No No
A, B, … F
 Quantities/Counting
7
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
16 10000 20 10
17 10001 21 11
Outline of Chapter 1
 Number Systems
 Number-base Conversions
 Arithmetic Operations
 Complements
 Signed Binary Numbers
 Binary Codes
 Bridging the Digital Divide
8

Decimal-to-Binary
Conversion

Binary-to-Decimal
Conversion
 Number Base Conversions
9
Evaluate
Magnitude
Octal
(Base 8)

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

Hexadecimal
(Base 16)
Evaluate
Magnitude
 Base R to decimal conversion
10

 A number expressed in base R can be converted to its decimal equivalent by using the
Positional representation rule [ multiplying each digit to R power of the digit place and
adding]
 N=
Examples:
4 3 2 1 0 -1-2
(11010. 1 1)2 ( ? )10
N = 124 + 123 + 022 + 121 + 020 + 12-1 + 12-2 = (26.75)10
2 1 0 -1
(628.4)9  ( ? )10
N = 692 + 291 + 890 + 49-1 = (512.1111)10
2 1 0 -1
(95A.D)16  ( ? )10
N = 9162 + 5161 + 10160 + 1316-1 = (2394.8125)10
 Converting Decimal to Base R
11

 To convert a decimal integer into base R, keep dividing by R until the quotient is 0.
Collect the remainders in forward order
 To convert a fraction, keep multiplying the fractional part by R until it becomes 0.
Collect the integer parts in reverse order
 Example: (162.375)10 = (10100010.011)2
162 0.375 x 2 = 0.750
81 0 0.750 x 2 = 1.500
40 1 0.500 x 2 = 1.000
20 0
10 0
5 0
2 1
1 0
0 1
 Binary and Octal Conversions
12
 Converting from octal to binary: Replace each octal digit with its 421
equivalent 3-bit binary sequence
( 2 6 . 2 )8 Octal Binary
0 000
1 001
( 0 1 0 1 1 0 . 0 1 0 )2
 Converting from binary to octal: Make groups of 3 bits, starting 2 010
from the binary point. Add 0s to the ends of the number if needed. 3 011
Convert each bit group to its corresponding octal digit.
Assume Zeros 4 100
5 101
( 1 0 1 1 0 . 0 1 )2
6 110
7 111
( 2 6 . 2 )8
 Binary and Hex Conversions
13
 Converting from hex to binary: Replace each hex digit with its 8421
equivalent 4-bit binary sequence Hex Binary
( 2 B . 4 )16 0 0000
1 0001
2 0010
( 0010 1011 . 0100 )2 3
4
0011
0100
5 0101
6 0110
 Converting from binary to hex: Make groups of 4 bits, starting 7 0111
from the binary point. Add 0s to the ends of the number if needed. 8 1000
9 1001
Convert each bit group to its corresponding hex digit A 1010
Assume Zeros B 1011
C 1100
( 1 0 1 011 . 0 1 )2 D 1101
E 1110
F 1111

( 2 B . 4 )16
 Base Conversion
14

 To convert from base 9 to base 11

 Example
(18.6)9 = ( ? )11
(a) Convert to base 10 using series substitution method:
N10 = 1  91 + 8  90 + 6  9-1
= 9 + 8 + 0.666…
= (17.666…)10
(b) Convert from base 10 to base 11 using radix divide and multiply
method:
17 7.326  0.666  11
1 6 3.586  0.326  11
0 1 6.446  0.586  11
N11 = (16.736 …)11
 Exercise – Convert ...
15

Decimal Binary Octal Hexadecimal

29.8
101.1101
3.07
C.82
 Exercise – Convert …
16

Answer

Decimal Binary Octal Hexadecimal

29.8 11101.110011… 35.63… 1D.CC…

5.8125 101.1101 5.64 5.D
3.109375 11.000111 3.07 3.1C
12.5078125 1100.10000010 14.404 C.82
 Common Powers
17
 Base 10 • Base 2

Power Preface Symbol Value Power Preface Symbol Value

10-12 pico p .000000000001 210 kilo k 1024

10-9 nano n .000000001 220 mega M 1048576

10-6 micro  .000001 230 Giga G 1073741824

10-3 milli m .001

103 kilo k 1000

106 mega M 1000000

109 giga G 1000000000

1012 tera T 1000000000000
Outline of Chapter 1
 Number Systems
 Number-base Conversions
 Arithmetic Operations
 Complements
 Signed Binary Numbers
 Binary Codes
 Decimal Addition Example
18

1) Add 8 + 7 = 15 > 10  15 -10

Add 3758 to 4657: Write down 5, carry 1

2) Add 5 + 5 + 1 = 11 > 10 11 -10

1 11 Write down 1, carry 1
3758
3) Add 7 + 6 + 1 = 14 > 10 11 -10
+ 4657 Write down 4, carry 1

8 415 4) Add 3 + 4 + 1 = 8 < 10

Write down 8
 Decimal Addition Explanation
19

What just happened?

111
1 1 1 (carry)
3758 3 7 5 8
+ 4657 +4 6 5 7
8 14 11 15 (sum)
8415 - 10 10 10 (subtract the base)

So when the sum of a column is equal to or greater than 8 4 1 5

the base, we subtract the base from the sum, record the
difference, and carry one to the next column to the left.
 Binary Addition Explanation
20

In the first two columns, there were no carries.

What is actually happened In column 3, we add 1 + 1 = 2
when we carried in binary? Since 2 is equal to the base, subtract
the base from the sum and carry 1.
In column 4, we also subtract
1 1 1 1
the base from the sum and carry 1.
1 1 0 1 1 1
In column 5, we also subtract
+ 0 1 1 1 0 0
the base from the sum and carry 1.
2 3 2 2 In column 6, we also subtract
2 2 2 2 the base from the sum and carry 1.
10 1 0 0 1 1 In column 7, we just bring down the
carried 1
 Binary Addition Verification
21

Verification
You can always check your answer by
converting the figures to decimal, doing 1101112  5510
the addition, and comparing the +0111002 + 2810
answers.
8310

1 1 0 1 1 1
64 32 16 8 4 2 1
+ 0 1 1 1 0 0
1 0 1 0 0 1 1
1 0 1 0 0 1 1
= 64 + 16 + 2 +1
= 8310
 Hexadecimal Addition
22

Hex Decimal Equivalent

1 1 Carry
2 6 B 3 2 6 11 3
1 A 9 C 1 10 9 12

4 17 20 15
4 1 4 F 4 1 4 15

 For sums greater than 15, subtract 16 and carry 1 to the next position.
 Decimal Subtraction Example
23
1) Try to subtract 5 – 7  can’t.
Subtract Must borrow 10 from next column.
Add the borrowed 10 to the original 5.
4657 from 8025:
Then subtract 15 – 7 = 8.
2) Try to subtract 1 – 5  can’t.
7 9 11 Must borrow 10 from next column.
8 10 2 15 But next column is 0, so must go to
- 4 6 5 7 column after next to borrow.
Add the borrowed 10 to the original 0.
3 3 6 8 Now you can borrow 10 from this column.
Add the borrowed 10 to the original 1..
Then subtract 11 – 5 = 6
3) Subtract 9 – 6 = 3
4) Subtract 7 – 4 = 3
 Decimal Subtraction Explanation
24

8 0 2 5
- 4 6 5 7

3 3 6 8

 So when you cannot subtract, you borrow from the column to

the left.
 The amount borrowed is 1 base unit, which in decimal is
10.
 The 10 is added to the original column value, so you will be
able to subtract.
 Binary Subtraction Explanation
25

 In binary, the base unit is 2

 So when you cannot subtract, you borrow from the column to the left.
 The amount borrowed is 2.

 The 2 is added to the original column value, so you will be able to

subtract.
 Binary Subtraction Example 1
Col 1) Subtract 1 – 0 = 1
Col 2) Subtract 1 – 0 = 1
Example 1: Subtract
Col 3) Try to subtract 0 – 1  can’t.
binary 11100 from 110011 Must borrow 2 from next column.
But next column is 0, so must go to
column after next to borrow.
2 1 Add the borrowed 2 to the 0 on the right.
0 0 2 2 Now you can borrow from this column
(leaving 1 remaining).
1 1 0 0 1 1 Add the borrowed 2 to the original 0.
Then subtract 2 – 1 = 1
- 1 1 1 0 0 Col 4) Subtract 1 – 1 = 0
1 0 1 1 1 Col 5) Try to subtract 0 – 1  can’t.
Must borrow from next column.
Add the borrowed 2 to the remaining 0.
Then subtract 2 – 1 = 1
Col 6) Remaining leading 0 can be ignored.
 Binary Subtraction Verification
27

Verification
Subtract binary
11100 from 110011: 1100112  5110
- 111002 - 2810
2 1
0 0 2 2 2310
1 1 0 0 1 1 64 32 16 8 4 2 1
- 1 1 1 0 0 1 0 1 1 1
1 0 1 1 1 = 16 + 4 + 2 + 1
= 2310
 Hexadecimal Subtraction
28

Hex Decimal Equivalent

1 16+6 10 16+3 borrow
2 6 B 3 2 6 11 3
-
1 A 9 C 1 10 9 12

C 1 7 12 1 7

 To subtract the least significant digit, borrow base (16) from the
previous position
Feedback request

 Please mail questions and constructive comments to

marwa.elmenyawi@bhit.bu.edu.eg

 Your feedback will be most appreciated

 On style, contents, detail, examples, clarity, conceptual
problems, exercises, missing information, depth, etc.
The next lecture

 Will talk about Complement, signed number and binary

codes.