UNIVERSITÉ DE DJIBOUTI

(UD)

DIGITAL CIRCUITS
By
Dr. Yasmin Nasser Mohamed

Faculty of Engineering (FI)

2024/2025

1
Introduction to Digital Circuits
Why is this course necessary?
• We live in a digital world.
o Almost all electronic devices are made up of digital circuits.
o Software plays a vital role in our daily lives.
o Computer programs process digital data.
o Programs run on computers, which consist of digital circuits.
o Many technologies and systems we rely on are based on digital data and the
digital systems that process and store them.
AI, machine learning, decision-making, etc.

Why is this course necessary for electrical Engineering?

o Foundation of Modern Electronics

o Knowledge of binary systems
o Key to microcontrollers and microprocessors
o Logical thinking and problem-solving

2
Introduction to Digital Circuits

Where are digital circuits used?

Today, almost every electronic device is implemented using digital circuits.
Examples:
• Central processing unit (CPU) is a "synchronous sequential" digital circuit. We will see sequential digital
circuits in the second part of this course.
• Computer memory: We will see flip-flops and latches, digital circuits and building blocks of memory.
• Home electronics: TV, washing machine control unit, video and audio devices.
• Cars: ABS, engine control
• Cell phones

https://semiconductor.samsung.com/
https://upload.wikimedia.org/
dram/module/ https://newsroom.intel.de/news-
wikipedia/commons/a/a3/AM
releases/ 3
D_Ryzen_9_7900X.jpg
Introduction to Digital Circuits
Analog – Digital Signals:

Nature of Signal:
In the real world (where we live), many physical quantities (current, voltage, temperature, light intensity, weight of a person, etc.) vary over a
continuous range.
These signals, which can take any possible value between the limits of such a range, are called analog signals.
Analog Signal: It is a continuous signal that represents physical measurements. Analog signals are used to represent data in a continuous range
and can take any value within a given range. They are susceptible to degradation by noise over distance and time. An analog signal has a
theoretically infinite resolution.
Digital Signal: It consists of discrete values, typically binary, representing zeros and ones. Digital signals process data as a sequence of discrete
levels and are generally more resistant to noise, making them more reliable for long-distance transmission and storage. A binary digital signal
may at any moment take on only one of two possible values:
0 - 1, high - low, on - off, True-false, open - closed.

Representation:

Analog Signal: It is represented by sine waves or other continuous

waveforms. It is directly proportional to the original information and can
vary smoothly and continuously over a range of values.

Analog Signal (continuous) 4

Introduction to Digital Circuits
Analog – Digital Signals:

Representation:

Digital Signal: It is represented by square waves and can only take on a

limited number of values, typically two - either a high (1) or a low (0),
corresponding to the bits in digital computing.

Single-Digit Binary Digital Signal (discrete)

Technology:
•Analog Signal: Devices that use analog signals include microphones, speakers, and thermometers. They often require amplifiers and are
generally simpler in technology compared to digital systems.
•Digital Signal: Digital devices include computers, phones, and cameras, which use digital circuits and technology to process, store, and
transmit data.

5
Introduction to Digital Circuits

Steps of Digital System Implementation:

Voltage 0, 1
Text and, or
Temperature not
Speed z = a b+c
Image Mathematical World
Switch Model
(Boolean Algebra) HDL Program
(Hardware Description
Real World Language)
(Physical world, WHEN(A & B) THEN X1-
C; ELSE X2 – E # F;
Problem Domain)
X2 – (!A # C);
……

Abstraction
Coding and
Design Implementation
modelling
6
Introduction to Digital Circuits
The Coding of Integers
In this course, we will deal with INTEGERS.
In numeral systems, every single digit when combined constructs a number.
Radix=> R (R is a positive integer)
Radix or base is the number of unique digits, including zero, used to represent numbers in a positional numeral
system. For example, the decimal system (base-10) uses ten digits (0 through 9), and the binary system (base-2)
uses two digits (0 and 1).
R={0,1,2,3,4,5,6,7,8,9}=> radix-10
Example:
1) If R=10, then the number 547 in radix-10 system can be written as:
54710 = 5x102 +4x 101 +7x 100
R={0,1}=> radix-2
•Example: The binary number 10102
Calculation
10102 = 𝟏 × 𝟐𝟑 + 𝟎 × 𝟐𝟐 + 𝟏 × 𝟐𝟏 + 𝟎 × 𝟐𝟎 = 𝟖 + 𝟎 + 𝟐 + 𝟎 = 𝟏𝟎𝟏𝟎
R={0,1,2,3,4,6,7}=> radix-8
Example: The octal number 1758 7
2 1 0
Calculation: 1 × 8 + 7 × 8 + 5 × 8 = 64 + 56 + 5 = 𝟏𝟐𝟓
Introduction to Digital Circuits
BCD (Binary Coded Decimal) Coding System:
Hexadecimal (Radix-16):
• A four-bit pattern represents each decimal number between 0
•Base: 16 and 9.
•Digits used: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F Natural BCD:
(where A=10, B=11, C=12, D=13, E=14, F=15) Number BCD Number: BCD
•Example: The hexadecimal number 1𝐴316 : Code: Code:
Example:
•Calculation: 1 × 162 + 𝐴 × 161 + 3 × 160 = 256 + 0:
1:
0000
0001
5:
6:
0101
0110 Number: 8 0 5
160 + 3 = 41910 2: 0010 7: 0111 BCD : 1000 0000 0101
3: 0011 8: 1000
4: 0100 9: 1001
• It is a redundant code.
Using 4 bits, 16 different code values can be created, but only 10 of them are used.
• Performing arithmetic operations on BCD numbers require more complex circuits than other representation
methods.
Therefore, modern computers don't use BCD coding for numbers.
3. General Conversion Principle:
Each number system can be converted into another by decomposing the number into a sum of its digits multiplied by the base
raised to the power of the digit's position, counting from right to left starting at zero.
Applications: 8
Introduction to Digital Circuits
•Binary: Used in computing and digital electronics for its simplicity in representing electrical states (off or on).
•Decimal: Commonly used in daily life and general arithmetic.
•Octal: Previously used in computing because of its simplicity in converting to and from binary.
•Hexadecimal: Widely used in computing and programming as it offers a more compact representation of binary values and is
easier to convert to and from binary.
Understanding these different bases is crucial in fields ranging from computer science and electronics to mathematics and
engineering, as different systems utilize different bases for calculations and data representation.
Binary Digital Coding: 3742
• As digital systems operate on binary digital signals, they can process -17 3.14
only two values (binary data): ON-OFF, LOW-HIGH, 0-1.
• Therefore, physical quantities (voltage, temperature, etc.) and any kind
of data (letters, numbers, colors, sounds) must be converted to binary
code words (digitally coded) before digital circuits can process
them. 01101101
• Binary code words consist of bits (binary digits). 00100110
• A bit takes on one of two possible values (0 or 1). Coding 11110011
Real World
• Binary: "Something made of two things or parts ". Bini = Two in Latin 00000011
….

Binary Code Words 9

Introduction to Digital Circuits
Digital Coding (contd):
• Using n bits (binary digits), 2n different “things” can be represented.

n bits 2n different binary code words (“things”)

oFor example, using 4 bits, 24 (16) code words can be generated to represent 16 different “things”:
0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111,
1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111
oUsing 8-bit code words, we can represent 28 (256) different “things”:
00000000, 00000001, 00000010, … , 11111101, 11111110, 11111111.
oThese can be 256 different colors, 256 symbols, integers between 0 and 255, integers from 1 to 256, or integers
between -128 and +127.
• There are different coding systems (methods) for different types of data.
• The meaning of a binary value (for example, 10001101) is determined by the system (hardware or software) that
processes this data.
This value may represent a number, a color, or another type of data.
• The coding of numbers is especially important. Therefore, in this course, we will give some basic information about the
coding methods of integers. 10
Introduction to Digital Circuits
Examples of Digital Coding:
RGB Color System:
• All colors are constructed from a combination of Red, Green, and Blue colors.
• 8 bits are used to represent the 256 levels of each of these three primary colors. This makes 256*256*256 = 16,777,216
possible colors.
• Examples:
Black: R = 00000000 G = 00000000 B = 00000000
Purple: R = 00001011 G = 00001111 B = 00001011

Unicode Text Encoding Standard:

• It is maintained by the Unicode Consortium (https://home.unicode.org/)
designed to support the use of text in all of the world's writing systems that can be digitized.
• UTF-16 (16-bit Unicode Transformation Format): One of the formats supported by Unicode. Others: UTF-8, UTF-32
• Examples:
A: 00000000 01000001
Ç: 00000000 11000111

11
Introduction to Digital Circuits
Examples of Digital Coding (contd):
Tokenization in AI systems built on large language models (LLMs):
• Large language models such as ChatGPT, Gemini, Claude, and Llama convert texts to a set of tokens that the model can
process.
• A token can be a character, a word, a part of a word, or a whole phrase.
• Tokens are transformed into integers the LLM can process.
• A token of an LLM typically contains 16 or 32 bits, depending on the encoding used.

• Example: From OpenAI Platform, GPT-4o (https://platform.openai.com/tokenizer)

• Text: Hello World!
Tokenization: 3 Tokens = [13225, 5922, 0]
T1: 0011001110101001 T2: 0001011100100010 T3: 0000000000000000
• The LLM uses these code words to "interpret" the text and generate results.
Machine-language instructions of CPUs:
• Just like data, CPU instructions are also represented as binary code words.
• Example: MIPS architecture (RISC CPU) Assembler: ADD R1, R2, R3 ; R1 + R2 R3
Machine Code: 000000 00001 00010 00011 00000 100000
12
Introduction to Digital Circuits
Representation of Integers in Digital Systems (and Computers)
• Before coding the integers, we must decide what type of numbers (unsigned or
signed) we will work with.
• This is because unsigned and signed numbers are encoded and represented differently.
Representation of Unsigned Integers:
In computers, unsigned integers are represented using "natural, binary, weighted (positional) coding”.
Binary (base 2), weighted (positional) coding:
• n-bit unsigned binary integer:
bn-1 bn-2 . . . b2 b1 b0 , bi ∈ 𝐵= {0,1}
bn-1: High-order bit “Most Significant Bit – MSB”
b0: Low-order bit “Least Significant Bit – LSB”
• Each bit has a weight based on its position. The weight is a power of two. Thus, the weight of bit bi is 2i.
For example, the weight of bit b0 is 20 = 1, and b1 has a weight of 21 = 2.

13
Introduction to Digital Circuits
Converting unsigned binary integer to decimal:
Decimal value = bn-1 2n-1 + bn-2 2n-2 + . . . + b2 22 + b1 21 + b0 20
weights
Example: 8-bit unsigned integer (n = 8)
(1101 0111)2 = 127 + 126 + 025 + 124 + 023 + 122 + 121 + 120 = 21510
Converting decimal to unsigned binary:
• Divide the given decimal number recursively by 2 until the quotient is 0.
• The remainders are the bits of the binary integer in the reverse order.
• The remainder of the first division is the Least Significant Bit of the binary integer.
Example: 21510
215/2 = 107 remainder 1 Low-order bit “Least Significant Bit – LSB” (rightmost bit)
107/2 = 53 remainder 1
53/2 = 26 remainder 1
26/2 = 13 remainder 0 21510 = (1101 0111)2
13/2 = 6 remainder 1
6/2 = 3 remainder 0
3/2 = 1 remainder 1 High-order bit “Most Significant Bit – MSB”) (leftmost 14
1/2 = 0 remainder 1 bit)
Introduction to Digital Circuits
Representation of Unsigned Integers (cont'd):
Remember: Decimal (base 10), weighted (positional) coding:
Value = dn-1 10n-1 + dn-2 10n-2 + . . . + d1 101 + d0 100 , diD = {0,1,2,3,4,5,6,7,8,9}
Example: 3-digit decimal integer
(704)10 = 7102 + 0101 + 4100

The range of unsigned binary integers:

• The largest unsigned integer that can be represented with n bits: 2n – 1
Examples:
oFor n = 8, the largest unsigned integer is 1111 11112 = 25510 (= 28 - 1 = 256 - 1)
oFor n = 16, the largest unsigned integer is 1111 1111 1111 11112 = 6553510
• The smallest unsigned integer that can be represented with n bits: 0
Examples:
oFor n = 8, 0000 00002 = 010
oFor n = 16, 0000 0000 0000 00002 = 010

The range of n-bit unsigned binary integers: 0 to 2n – 1

15
Introduction to Digital Circuits
The range of positive signed integers that can be represented with n bits:
• The largest signed positive integer that can be represented with n bits: 2n-1 – 1
Examples:
oFor n = 8, the largest positive integer is 0111 11112 = 12710 (= 27 – 1)
oFor n = 16, the largest unsigned integer is 0111 1111 1111 11112 = 3276710

• The smallest signed positive integer that can be represented with n bits: 0
Examples:
oFor n = 8, 0000 00002 = 010
oFor n = 16, 0000 0000 0000 00002 = 010

The range of n-bit positive signed binary integers : 0 to 2n-1 – 1

16
Introduction to Digital Circuits
Representation of Signed Integers:
• The (high-order) most significant bit denotes the sign of the number.
oPositive numbers start with a “0”,
oNegative numbers start with a “1”.
Positive integers:
• In computers, positive integers are represented (like unsigned integers) using "natural
binary weighted (positional) coding”.
• Remember: Positive binary numbers must start with 0.
Examples of Positive Numbers:

8-bit +510 : 0000 0101

8-bit +10010 : 0110 0100
4-bit +510 : 0101
4-bit +710 : 0111

17
Introduction to Digital Circuits
Negative integers (2's complement):
• Negative integers are represented using 2's complement.
• In this representation, negative integers are represented by the 2's complement of
the positive number (absolute value).
To obtain the 2’s complement:
• First, invert (1's complement) the number. Change 0 to 1, 1 to 0.
• Then, add 1 to the inverted number.
2's complement of (𝐴) = ̅ + 1 𝐴 denotes 1's complement of A.

Examples of Negative Numbers:

4-bit +710 : 0111 8-bit +610 : 0000 0110

1's complement : 1000 1’s complement : 1111 1001
: +0001 Add 1 : +0000 0001
Add 1
: 1001 Result = -610 : 1111 1010
Result = -710
Negative
• Note: In the 2's complement system, the bits following the sign (1) of a
negative integer do not directly represent its absolute value. 18
Introduction to Digital Circuits
2's complement system (cont'd):
• Taking the 2's complement of a number changes the sign of the number.
• Taking the 2's complement of a negative number makes it positive.
2's complement operation:
positive  negative
negative  positive
Example: Making a negative number positive :
8-bit -610 : 1111 1010
1's complement : 0000 0101
Add 1 : +0000 0001
Result: +610 : 0000 0110
The absolute value of a negative integer:
• Do NOT think of signed numbers as one bit for the sign, followed by an absolute value that
represents the number.
• The WHOLE sequence of bits represents the number AND its sign.
• The MSB is an indicator of being positive or negative, but to find what the number is equal to in
decimal, all bits have to be taken into consideration. 19
Introduction to Digital Circuits
The range of negative signed integers that can be represented with n bits :
• The smallest (most) negative integer that can be represented with n bits: - 2n-1
Examples:
oFor n = 4, the smallest negative integer is 10002 = -810
oFor n = 8, the smallest negative integer is 1000 00002 = -12810
oFor n = 16, the largest unsigned integer is 1000 0000 0000 00002 = -3276810
• The largest negative integer that can be represented with n bits: -1
Examples:
oFor n = 4, 11112 = -110
oFor n = 8, 1111 11112 = -110
oFor n = 16, 1111 1111 1111 11112 = -110
The range of n-bit negative binary integers: -1 to - 2n-1
The range of n-bit signed binary integers: - 2n-1 to + (2n-1-1)
Examples:
oFor n = 4, the range is: -8 to +7 (Remember: 16 code words)
oFor n = 8, the range is: -128 to +127 (Remember: 256 code words) 20
Introduction to Digital Circuits
Special cases in 2’s complement representation
The negative integer with the largest absolute value (e.g., -8 in the case of 4 bits) is a special case in 2’s
complement representation.

Remember: Using 𝑛 bits, we can represent signed decimal numbers between

−2𝑛−1 and +(2𝑛−1 – 1).

Example:
• Using 4 bits, we can represent signed decimal numbers between
−8 and +7 ((−23 ) and +(23 – 1)).
• The number -8 can be represented with 4 bits: -8 = 1000.
• However, +8 cannot be represented with 4 bits.
• If we take the 2’s complement of 1000 (-8) to obtain +8, the result is 1000.
• However, 1000 cannot be a positive number because it starts with 1.
4-bit -810 : 1000
1's complement : 0111
Add 1 : +0001
Result: ? : 1000

If we take the 2's complement of 4-bit “-8”, we find its 4-bit magnitude (unsigned), i.e., 1000 = (unsigned) 8 (special
case for 4 bits).
21
Introduction to Digital Circuits
Digital Circuits
Special cases in 2’s complement representation (cont'd) Example (contd):
• To obtain the 2's complement 4-bit binary number for the decimal number -8, we also start with
the 4-bit magnitude (unsigned absolute value) of 8.
• We start with the unsigned absolute value of 8. Its UNSIGNED 4-bit binary number equivalent
is 1000.
8 (4-bit magnitude) : 1000
1's complement : 0111
Add 1 : +0001
Result: -8 (4-bit) : 1000
Based on this information, we can update the explanation about the 2's complement
operation as follows:

2's complement operation:

unsigned magnitude  negative
negative  unsigned magnitude

22
Introduction to Digital Circuits
Representing signed numbers on a circular graphic: We can represent signed numbers on a number wheel.
Example: 4-bit numbers:

Subtraction direction Addition direction

Using 4 bits, we can generate 16 codewords and thus represent 16 integers.

When we use the 2's complement method, 8 of the codewords represent positive integers (including 0):
0000 – 0111
The remaining 8 codewords represent negative integers: 1111 – 1000.

23
Introduction to Digital Circuits
The standard coding method for integers in computer systems:
• The standard (default) coding (representation) method for negative integers is 2’s complement.
• For example, when you define a signed integer in a high-level programming language, such as C++, Java, etc.,
the compiler uses 2’s complement to store integers in computer memory.
• Normally, we state explicitly that the method is 2’s complement.
• However, if the coding system for integers is not mentioned clearly, you may assume that 2’s complement is
used.
Programming Examples:
• Examine the following programs to discover how integers are represented in C++.
integer_8.cpp and
integer_16.cpp

• Note: The programs were written using the std module defined in C++23.
If your compiler does not support the standard C++23, you can run the programs with the suffix
"_before20" instead.

24
Introduction to Digital Circuits
The reasons for using the 2’s complement representation:
• Why not to use the "sign-magnitude" representation, which seems simpler and more intuitive?"
oSign-magnitude method: The leftmost bit (MSB) represents the sign of the number (0 for
positive, 1 for negative), and the rest of the bits represent the magnitude of the number.
Example: 8-bit +510 : 0000 0101 8-bit -510 : 1000 0101 (sign-magnitude)
There are two representations for zero! There is a positive zero and a negative zero. +010 : 0000
0000 -010 : 1000 0000 (sign-magnitude)
oThe range is: - (2n-1 -1) to + (2n-1-1) Compare to 2's complement method

Advantages of using the 2's complement representation:

• The 2's complement representation makes adding or subtracting two numbers easy without sign
and magnitude checks.
• This coding system makes it possible to perform subtraction using circuitry designed only for
addition (we will see adder and subtracter circuits). Thus, it simplifies the design of digital
circuits for arithmetic operations.
• It has a unique representation for zero.

25
Introduction to Digital Circuits
Extension (Sign Extension) of Binary Numbers
• In digital systems, a certain number of bits (memory locations) are allocated for binary numbers, e.g., 16 bits, 32 bits, etc.
• In some cases, it is necessary to write a number to a memory space with more bits than necessary (for example, 8-bit number
to 16-bit memory).
• Sometimes, it is necessary to operate on two numbers of different lengths.
• In such cases, the shorter number is extended (word length is increased). For example, extension from 4 bits to 8 bits or
from 8 bits to 16 bits.
• The extension operation is different for unsigned and signed numbers.
Unsigned Numbers: The high-order part of the binary number is filled with "0"s.
Example: 4-bit 310 = 0011 8-bit 310 = 0000 0011
Example: 4-bit 910 = 1001 8-bit 910 = 0000 1001

Signed Numbers: The high-order part of the binary number is filled with the value of the sign bit. This operation is called sign
extension.

Example: 4-bit +310 = 0011 8-bit +310 = 0000 0011

Example: 4-bit -710 = 1001 8-bit -710 = 1111 1001
Example: 4-bit -110 = 1111 8-bit -110 = 1111 1111

26
Introduction to Digital Circuits
Hexadecimal (Base-16) Numbers
• Binary numbers are necessary because digital
circuits can directly process binary values. 0 0000 0
• However, it is difficult for humans to work with large numbers of bits in even 1 0001 1
relatively small binary numbers. (Example: 1110010001011010) 2 0010 2
• Therefore, for documentation (to write and read easily), hexadecimal (base-16) 3 0011 3
numbers are used. 4 0100 4
• Converting from binary to hexadecimal is easy: 5 0101 5
6 0110 6
oEach hex. digit maps to 4 bits. See the table.
7 0111 7
oSeparate binary numbers into groups of 4 bits. 8 1000 8
oFind the single hexadecimal digit corresponding to each group of 4 bits. 9 1001 9
Examples: 10 1010 A
• Binary  Hexadecimal 11 1011 B
010111012 = 0101 1101 (Binary) 12 1100 C
13 1101 D
= 5 D (Hexadecimal)
14 1110 E
• Hexadecimal  Binary 15 1111 F
$87 = 1000 01112
• To express hexadecimal numbers, the symbols $ and h are usually used.
27
Example: $5D , $87 or 5Dh , 87h.
Introduction to Digital Circuits
Addition and Subtraction Operations in Digital Systems
• In computers, the Arithmetic Logic Unit (ALU) performs the integer arithmetic operations.
• As an advantage of 2's complement representation, integer addition and subtraction operations are
performed on unsigned and signed numbers in the same way.
• However, the result is interpreted differently for unsigned and signed numbers.
• Before an operation on numbers of different lengths, a sign extension is necessary.
oRemember: The extension operations are different for unsigned and signed numbers.
Addition:
• The result of the addition of two bits (a and b) is a 2-bit number.
• The LSB of the result is the 1-bit sum, and the MSB is the carry.
• The rules of binary addition are given in the table on the right. Inputs Result
a b Carry Sum
0+0 0 0

0+1 0 1
1+0 0 1
1+1 1 0
28
Introduction to Digital Circuits
Addition:
Unsigned Integers:
The result of the addition of two n-bit unsigned numbers can be a (n+1)-bit number. The
(n+1)st bit is called the carry.
Examples: Addition of two 8-bit unsigned numbers

01110101 : 117
+ 01100011 : Only for
99 testing
11011000 : 216
No Carry (Carry=0)

11111111 : 255 Only for

+ 00000001 : 1 testing
1 00000000 :256+0
The 8-bit result is 0.
(Carry=1) However, using the carry, we can interpret the
result as 256. 29
28 + 0 = 256
Introduction to Digital Circuits
Addition:
Signed Integers:
• The operation is performed as with unsigned numbers, but the result is
interpreted differently.
• As an advantage of 2's complement representation, adding 2's-complement numbers
requires no special processing even if the operands have opposite signs.
• If an (n+1)st bit arises as a result of adding two n-bit signed numbers, this bit is
ignored.
Examples: Addition of 8-bit signed numbers
11111111 : -1
11111111 : -1
+ 11111111 : -1
+ 00000001 : +1
111111110 : -2
100000000 : 0
Ignored
Ignored Sign (-)
Sign (+)
Attention:
• While working with n-bit numbers, the sign bit is always the most significant bit
(counting from right to left), i.e., the nth bit, not the (n+1)st one.
• The (n+1)st bit is the carry bit. 30
Introduction to Digital Circuits
Overflow in addition (signed integers):
• The result of the addition of n-bit signed integers can be too large for the binary system to represent with n bits.
• If the result is out of the range of n bits, an overflow occurs.
• For example, with 8 bits, we can represent signed integers between -128 and +127.
• The existence of overflow after binary addition can be detected by checking the signs of the operands and the result.
• In an addition operation, overflow can occur in two cases:
positive + positive  negative and negative + negative  positive
Examples:
01111111:+127 10000000:-128
+ 00000010: +2 + 11111111: -1
10000001: Cannot be represented 101111111:Cannot be represented
Both operands are positive. Both operands are negative. The result is positive.
The result is negative. There is
There is an overflow. Note: (n+1)st bit is one. It is ignored.
an overflow.
a/
Note: (n+1)st bit is zero. It is
ignored.

31
Introduction to Digital Circuits

Subtraction:
• Computers usually use the method of complements to implement subtraction.
• 2's complement of the second operand is added to the first number.
𝐴 − 𝐵 = 𝐴 + (−𝐵
= 𝐴 + 2 ′𝑠)𝑐𝑜𝑚𝑝𝑙𝑒𝑚𝑒𝑛𝑡 (𝐵)
=𝐴+ 𝐵 + 1
• So, only one addition circuit is sufficient to perform both addition and subtraction (benefit of 2's
complement system).
• In the following Section, we will cover addition and subtraction circuits.

• Like addition, subtraction operations are performed on unsigned and signed integers in the same way
(because of 2's complement representation). However, the interpretation of the result is different for
unsigned and signed integers.

32
Introduction to Digital Circuits
Subtraction (cont'd):
Unsigned Integers:
If the result of subtracting two n-bit unsigned numbers, performed using 2's complement, is a (n+1)-bit
number (there is a carry), then there is no borrow, and the result is valid.
If the (n+1)st bit of the result is zero (no carry), the first operand is smaller than the second, and there
is a borrow.
Carry = 1  no borrow
Carry = 0  borrow
Examples: Subtraction of 8-bit unsigned numbers
2's complement
00000101: 5 00000101: 5
- 00000001: 1 + 11111111:-1
100000100: 4
Carry=1 : No Borrow
00000001: 1
- 00000101: 5 2's complement
00000001: 1
+ 11111011:-5
011111100: Cannot be
represented
No Carry: Borrow 33
Introduction to Digital Circuits
Subtraction (cont'd):
Signed Integers:
Subtraction on signed integers is also performed using 2's complement.

The carry bit is ignored.

Example: To determine its decimal
00000101:+5 2’s complement 00000101: +5 equivalent, we take its 2’s
- 00001100:+12 + 11110100:-12
complement first

11111001: 2’s comp.:00000111:-7

Sign 1, result: negative

Overflow: Just as in addition, an overflow can occur in subtracting signed integers. In subtraction,
overflow can occur in two cases:
positive – negative  negative and negative – positive  positive
Example:
11111101: -3 11111101:-3
- 01111111:+127 2’s complement +10000001:-127
101111110: cannot be represented
Neg. – pos. = pos.  Overflow Sign:0, result: positive. 34
Introduction to Digital Circuits
Comparing integers:
The subtraction operation is used to compare two integers.
After the operation R = A - B, related flags (status bits: carry, overflow) are checked.
Unsigned Integers:

Result (R) Carry, Borrow Comparison

=0 X (not important) A=B
≠0 Carry = 1, NO A>B
≠0 Carry = 0, YES A<B

Signed Integers:
Result (R) Overflow Comparison
=0 X (not important) A=B
Positive, ≠0 NO A>B
Negative NO A<B Because of overflow, the sign of the
Positive YES A<B result is not correct.
Negative YES A>B
35
Introduction to Digital Circuits
Summary of Carry, Borrow, Overflow
Carry: It can occur in the addition of unsigned integers.
It indicates that the result cannot be represented with n bits, and an (n+1)st bit is necessary.
Borrow: It can occur in the subtraction of unsigned numbers (A - B).
It indicates that the first number (A) is smaller than the second one (B, the number being subtracted), i.e.,
A < B.
The result cannot be represented with unsigned numbers.
If the result of the subtraction using 2's complement is an n-bit number (no carry), then there is a borrow, and
the result is invalid.
Overflow: It can occur only on signed numbers in addition and subtraction operations.
It indicates that the result cannot be represented with n bits.
Overflow can be detected by checking the signs of operands and the result. There is an overflow in the
following cases:
pos. + pos.  neg. pos. – neg.  neg.
neg. + neg.  pos. neg. – pos.  pos.

36
Introduction to Digital Circuits
Summary of Carry, Borrow, Overflow

Unsigned Signed
Event Carry Borrow Overflow
Affected Addition Subtraction n-bit Addition/Subtraction n-bit
Operation n-bit integers integers integers
Meaning The result cannot A < B, The result cannot be
be represented The result cannot be represented with n bits. The
with n bits. represented with sign of the result is inverted.
Carry can be used unsigned numbers.
to interpret the
result.
Detection (n+1)st bit of the If the result is an n-bit Check the signs of operands
result is 1. number (Carry=0), and the result
Carry = 1 there is a borrow, and pos. + pos. -> neg.
the result is invalid. pos. – neg. -> neg.
neg. + neg. -> pos.
neg. – pos. -> pos.

37
Introduction to Digital Circuits
Digital Coding-Related Definitions:
We define some coding-related terms that we will use in the following chapters.
Hamming distance: The Hamming distance between two n-bit long code words is the number of bit positions at
which the corresponding bits are different.
Example: Hamming distance between 011 and 101 is 2.
Richard Wesley Hamming (1915-1998) Mathematician, USA
Adjacent code words: If the Hamming distance between two code words is 1 (only one bit changes), these code
words are adjacent. Example: 0101 - 1101
Adjacent coding systems: Between each pair of successive code words, the Hamming distance is 1 (only one bit
changes).
In addition, if the Hamming distance between the first and last code words is 1, then this code is called cyclic
(circular).
Example: A cyclic BCD code (different from natural BCD !)
Number: Code: Number: Code:
0: 0000 5: 1110
1: 0001 6: 1010
2: 0011 7: 1000
3: 0010 8: 1100
4: 0110 9: 0100 38
Introduction to Digital Circuits

Gray Code: A binary (base 2), nonredundant, and cyclic (also adjacent) coding system that
represents 2n elements is called a Gray code.

Example: A 2-bit Gray code:

Num.: Code:
The patent of the Gray Code was issued to physicist
0: 00
Frank Gray in 1953 when he was working at Bell Labs.
1: 01
2: 11 Frank Gray (1887 – 1969) was a physicist and researcher.
3: 10

39
40
41