Lecture # 2

24 Aug 2021

Digital Design Google Classroom code:

nzdcewi
CS F215/ECE F215/EEE F215/INSTR F215
AUGUST 2021
I N S T R U C TO R : D R . M A N I S H
Consultation hours: Tue, Thu, Fri : 12 noon - 1 PM
https://meet.google.com/cfy-bmps-cib
2. Complement of numbers
•Complements are used in digital systems to simplify the subtraction operation and for logic
simplification
•Logic simplification leads to circuits that have smaller size, cheaper cost, less power requirement

Two types of complements

•Radix complement (r’s complement)
•Diminished radix complement (r-1)’s complement
[For binary r=2; for decimal r=10]
so a.k.a 2’s complement/10’s complement or 1’s complement/ 9’s complement for
binary and decimal numbers respectively
Diminished radix complement
Given a number N of base r which has n digits
(r-1)’s complement = (𝑟 𝑛 −1) − 𝑁
Example:
For decimal numbers : r=10 which gives 9’s complement = (10𝑛 −1) − 𝑁 = 9999. . . −𝑁
•Find 9’s complement of N = 225
Solution: n=3 so (10𝑛 −1) − 𝑁 = 999-225 = 774
•Find 9’s complement of N = 01234
Solution: n=5 so 99999 – 01234 = 98765
Notice that 9’s complement of a decimal number is expressed by subtracting each digit by 9
Diminished radix complement
Given a number N of base r which has n digits
(r-1)’s complement = (𝑟 𝑛 −1) − 𝑁
Example:
For binary numbers : r=2 which gives 1’s complement = (2𝑛 −1) − 𝑁 = 1111. . . −𝑁
•Find 1’s complement of N = 101
Solution: n=3 so (2𝑛 −1) − 𝑁 = 111-101 = 010
•Find 1’s complement of N = 10101
Solution: n=5 so 11111 – 10101 = 01010
Notice that 1’s complement of a binary number is expressed by subtracting each digit by 1
(or changing 1 to 0 and 0 to 1)
For octal and hexadecimal systems we would subtract each digit by either 7 (octal) or F (hexadecimal).
Radix complement
Given a number N of base r which has n digits
(r)’s complement = 𝑟 𝑛 − 𝑁 for N≠ 0; and 0 for N = 0.
Can be obtained by adding 1 to the (r-1)’s complement: 𝑟 𝑛 − 𝑁 = (𝑟 𝑛 − 1 − 𝑁) + 1
Example:
For decimal numbers : r=10 which gives 10’s complement = (9999. . . −𝑁) + 1
•Find 10’s complement of N = 225
Solution: n=3 so 10𝑛 − 𝑁 = 999 - 225 +1 = 775
•Find 10’s complement of N = 01234
Solution: n=5 so 99999 – 01234 + 1= 98766
Radix complement
Given a number N of base r which has n digits
(r)’s complement = 𝑟 𝑛 − 𝑁 for N≠ 0; and 0 for N = 0.
Can be obtained by adding 1 to the (r-1)’s complement
Example:
For binary numbers : r=2 which gives 1’s complement = (1111. . . −𝑁) + 1
•Find 2’s complement of N = 10100
Solution: n=5 so (2𝑛 −1) − 𝑁 + 1 = 11111-10100 +1 = 01011 +1 = 01100
•Find 2’s complement of N = 10101
Solution: n=5 so (11111 – 10101) + 1 = 01010 +1 =01011
Notice that 2’s complement of a binary number is expressed by leaving all least significant 0’s and first
1 unchanged; and replacing other 1 to 0 and 0 to 1.
The complement of a complement restores the number to its original value.
Subtraction with r’s complements
1. Add r’s complement of one number to the other number : M + (𝑟 𝑛 −𝑁) = 𝑟 𝑛 + (M – N)
2. Discard the end carry (𝑟 𝑛 )
Example:
•Using 10’s complement, subtract 225 – 220
Solution: 225 + (779+1) → 1005 → 5
•Using 2’s complement, subtract 1010100 – 1000011
Solution: 1010100 + (0111100+1) → 10010001 → 0010001
Subtraction with (r-1)’s complement
1. Add (r-1)’s complement of one number to the other number : M + (𝑟 𝑛 −1 − 𝑁) = (𝑟 𝑛 -1) +
(M – N)
2. Add 1 to the answer: (𝑟 𝑛 -1) + (M – N) +1 = 𝑟 𝑛 + (M – N) This step is also known
as end around carry
3. Discard the end carry (𝑟 𝑛 )
Example:
• Using 9’s complement, subtract 225 – 220
Solution: 225 + 779 → 1004 + 1 → 1005 → 5
• Using 1’s complement, subtract 1010100 – 1000011
Solution: 1010100 + 0111100 → 10010000 +1 → 10010001 → 0010001
Subtraction when there is no end carry
(with r’s complement)
1. Add r’s complement of one number to the other number
2. When there is no end carry, we take the r’s complement of the obtained answer.
3. Assign a negative sign to the answer

Example:
•Using 10’s complement, subtract 220 – 225
Solution: 220 + (774+1) = 995 → 004+1 → – 5
•Using 2’s complement, subtract 1000011 – 1010100
Solution: 1000011+ (0101011+1) =1101111 → 0010001 → – 0010001
Subtraction when there is no end carry
(with r-1’s complement)
1. Add r-1’s complement of one number to the other number
2. When no end carry, take r-1’s complement of the answer Same procedure as
previous example
3. Assign a negative sign to the answer

Example:
•Using 9’s complement, subtract 220 – 225
Solution: 220 + 774 = 994 → 005 → –5
•Using 1’s complement, subtract 1000011 – 1010100
Solution: 1000011+ (0101011) =1101110 → 0010001 → – 0010001
Why do we prefer these methods?
Addition is a simpler operation to implement on hardware, we just need to use an OR gate in our
hardware design. So we prefer to subtract using complement methods so that the design has to perform
only addition operations.
Homework:
X=11010010; Y=0101011
Perform X-Y and Y-X using both 1’s and 2’s complement methods
Answer: X-Y = 011 1111 and Y-X = - 011 1111
Signed Binary numbers
•Conventionally leftmost bit can represent the sign of the signed binary number:
◦ 0 represents positive number
◦ 1 represents negative number

•If the binary number is unsigned, the leftmost bit represent the most significant bit of the number
Example: signed binary number 11001 = (−9)10
Unsigned binary number 11001 = (25)10
•This representation is also known as signed-magnitude representation
Signed complement system
•For performing arithmetic operations, signed-complement representation is used
•Here, a complement represent the negative of a number
Example: Represent decimal +10 and -10 in various ways in 8 bit binary numbers
Signed-magnitude representation + 10 = 00001010
Signed 1’ complement representation of +10 = 00001010 (no change)
Signed 2’ complement representation of +10 = 00001010 (no change)
Signed-magnitude representation - 10 = 10001010
Signed 1’ complement representation of -10 = 11110101 (1’s complement of 10)
Signed 2’ complement representation of +10 = 11110110 (2’s complement) Most commonly
preferred
 Arithmetic addition
(When –ve numbers are represented in signed 2’s complement form)
Procedure: Simply add and discard the carry
Example:
+6 = 0000 0110
-11 = 1111 0101
-5 = 1111 1011 (which is 2’s complement of +5)

Homework : Add following:

(a) +6 – 13 (b) - 6 -13
Answers: (a) 1111 1001 (b) 1110 1101
Arithmetic subtraction
•Subtraction can simply be seen as addition :
A – (+B) = A + (-B)
A – (-B) = A + B
• Example: subtract -6 – (-13).
-6 = 1111 1010 (2’s complement of 6)
+13 = 0000 0111
+7 = 0000 0111 (after discarding the carry)

Homework:
Perform +4 -11 = -7
Answer: 1111 1001
Binary codes
•Let’s suppose we need 4 codes, these can be:
00, 01, 10, 11 : Binary numbers having only 2 bits are enough
•Let’s suppose we need 8 codes, these can be:
000, 001, 010, 011, 100, 101, 110 , 111 : Binary numbers having only 3 bits are enough
•Let’s suppose we need 2𝑛 codes : Binary numbers having n bits will be required
Binary-coded decimal (BCD) codes
This code is simply the 4 bits binary representation of each decimal number: 125 = 0001 0010 0101

The binary combinations from 1010 to 1111 are not used in BCD and have
no meaning.
Realize that BCD numbers are decimal numbers essentially (not binary
numbers). Only that each decimal digit is represented by a binary code.
Example: 12 in BCD = 0001 0010
12 in binary value = 1100
Addition in BCD representation
Remember we have discarded 6 codes (1010 to 1111) in BCD?
So whenever, we have an unidentified answer in the sum, we add 6 to bring it to a recognizable
BCD code.
The addition of 6 = (0110) 2 converts it to the correct digit and also produces a carry as required.
Example: 1 1
184 = 0001 1000 0100
576 = 0101 0111 0110
= 0111 10000 1010
Add 6 = 0110 0110
Sum = 0111 0110 0000
Subtraction in BCD
Just like the previous method
Use 10’s complement number for negative signed number
Example:
370 + (-250) = 120
Solution: 0011 0111 0000
750 = 0111 0101 0000 (10’s complement)
1100 0000
0110
1011 10010 0000
0110
10001 0010 0000 = 120
More Binary code types
•Excess 3 is an unweighted code (add +3)
•2421, and excee-3 are self complimentary codes;
i.e., 9’s complement of the decimal number is
obtained by flipping each bit 0 to 1 and 1 to 0.
•Example: 395 in excess-3 code = 0110 1100 1000
•9’s complement = 604 in excess-3 = 1001 0011 0111
Gray code
We change only 1 bit from one number to next number
Advantage: To reduce error: Let’s say moving from 7 (0111) to 8
(1000) requires changes in all 4 bits. Probability of error is higher.
In gray code, only one bit needs to be changed (0100 to 1100); and
hence lesser probability of error.
Error detecting code
Eigth bit is added in ASCII code to detect error : called parity bit
ASCII A = 100 0001 0100 0001 (even parity)
1100 0001 (odd parity)
In general, one parity scheme is adopted. The receiver counts even or add parity, if there is an
error, re-transmission is asked.
Next lecture
Boolean Algebra (basic theorem and properties)