Digital Logic Design
Course
Second Year Students
Lecturers : Dr. Fatma Sakr
Dr. Doaa Al-Ebiary
Chapter 3: Complement Systems
Lecture 4
Complements
• Complements are used in digital
computers to simplify the subtraction
operation and for logical manipulation.
• Simplifying operations leads to simpler and less
expensive circuits to implement the operations.
• Two types of complements:
• Radix complement (r’s complement)
• Diminished complement ( (r-1)’s complement )
i.e : For binary numbers : 1's & 2’s complement
1's Complement
• In 8- bit 1’s Complement: (+3) is: 00000011
• (-3) is: 11111100
• In 1’s complement, as with signed magnitude, negative
values
• are indicated by a 1 in the high-order bit.
• Complement systems are useful because they eliminate
the need
• for subtraction. The difference of two values is found by
adding the
• minuend to the complement of the subtrahend.
1's Complement
Example: Using 1’s complement
binary arithmetic,
find the sum of 48 and - 19
(48) 10= (110000) 2
48
(19) 10 = (10011) 2 −19
29
Add the end-carry to the result
Dealing with 1’s Complement’s Overflow
• Find [ (-5)10 + (-20)10 ] using 1’s complement?
11010 −5
(5)10 + (20)10 ---> (00101)2 + (10100)2 −25
+01011
00101 +6
+1 Decimal
check!
(-5)10 + (-20)10 ---> (11010)1’s + (01011)1’s = 00110 1’s
1
Dealing with 1’s Complement’s Overflow
• Solution :
→ Insert two zeros to the left of the MSB of the positive dec. numbers
(5)10 + (20)10 ---> (0000101)2 + (0010100)2
(-5)10 + (-20)10 ---> (1111010)1’s + (1101011) 1’s
1111010 −5
+ 1101011 −20
1 1100101 −25
+1
= 𝟏100110
Dealing with 1’s Complement’s Overflow
• Although the “end carry around” adds some complexity,
1’s complement is simpler to implement than signed
magnitude.
• But it still has the disadvantage of having two
different representations for zero: positive zero and
negative zero.
• 2’s complement solves this problem.
2’s Complement
❑ To express a value in 2’s complement:
• If the number is positive, just convert it to binary
and you’re done.
• If the number is negative, find the 1’s
complement of the number and then add 1.
• Example:
➢ In 8-bit 1’s complement, (+3) is: 00000011
➢ (-3) in 1’s complement is: 11111100
➢ Adding 1 gives us (-3) in 2’s complement form:
11111101.
2’s Complement
Example: Using 2’s
complement binary
arithmetic,
find the sum of 48 and -
19 (48)10 = 48
(110000)2 −
(19)10 = 19
(10011)2 29
(-19)10 =
Discard any
(10011) 2’s
carries emitted from the
high order bit.
2’s Complement
• When we use any finite number of bits to represent a
number, we always run the risk of the result of our
calculations becoming too large to be stored in the
computer.
• While we can’t always prevent overflow, we can always detect
• overflow.
• In complement arithmetic, an overflow condition is easy to
detect.
❑ NOTE :
•The difference between using the (r)’s and (r-1)’s complements
is the method of dealing with the “end-carry”
Dealing with 2’s Complement’s Overflow
❑ Rule for detecting signed two’s complement overflow:
When the “carry in” and the “carry out” of the sign
bit differ, overflow has occurred.
• (107)2’s + (46)2’s = (??) 107
+ 46
−103
• Solution :
→ Insert two zeros to the left of the MSB of the positive numbers
0001101011 107
+ 0000101110 + 46
010011001 𝟏𝟓𝟑
Codes
❑ BCD “Binary Coded Decimal” (8 4 2 1)
❑ Excess-3
❑ Gray code
❑ Error detection code (Parity)
BCD Code
• (958)10 = (1001 0101 1000)BCD
• (1702)10 = (0001 0111 0000 0010)BCD
• Most famous use: in designing
7-segment display
Excess-3 Code
(5 7 1 )10
+3 +3 +3
( 1000 1010 0100)Exc-3
( 0110 1000 0101 1011)Exc-3
-3 -3 -3 -3
(3 5 2 8 )10
Conversion from Gray to Binary code
(Vice Versa)
Binary : 1 -+-> 0 -+-> 1 -+-> 1 -+-> 0
start
Gray : 1 1 1 0 1 Result
Gray: 1 1 0 1 1 0
+ + + + +
Binary : 1 0 0 1 0 0 Result
→ Note : addition when “Gray -> Binary” without carry.
→Note : only 1-bit changes in gray code counting
sequence
→Very important for some industrial apps (Shaft encoders)
Examples
Example : 1101 (binary ) == 13 == 1011 (Gray code)
1 0 1 1 (Gray) === 1101
Error detection codes (Parity)
• Parity is used to detect single bit errors, but can not be
used to correct error.
Even Parity Odd
Contains Contains
even odd
number of number of
ones ones
Error detection codes (Parity)
•Ex. A receiver detected an error when received the
following code (1100 1101), What is the parity used
Even/Odd?
Ans. :
11001101 ----------------> 5 ones [odd]
Since Error
detected
Therefore the
used parity is Even
Hamming Code
• Hamming Code Hamming Code uses multiple parity
bits. It can detect and correct error bits. A Hamming
Code with n parity bits can have up to 2n – n - 1 data
bits, making a maximum code length of 2n - 1 bits.
Parity Bits Data Bits Total Bits
2n – n - 1 2n - 1
3 4 7
4 11 15
5 26 31
A Hamming Code with 4 Parity Bits
• Four parity bits can check up to 11 data bits, making a 15-bit
code. The parity bits P1, P2, P4 and P8 are placed at bit
positions 1, 2, 4 and 8, respectively, as shown below. The other
bits are data bits. Number of Parity Bits = n = 4 Number of Data
Bits = 2n – n - 1 = 16 – 4 – 1 = 11
• Parity Bits P1, P2, P4 and P8
• Data Bits D1, D2, D3, D4, D5, D6, D7, D8, D9, D10 and D11 Bit
• Position: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
• Code : P1 P2 D1 P4 D2 D3 D4 P8 D5 D6 D7 D8 D9 D10 D11
A Hamming Code with 4 Parity Bits:
P1, P2, P4 and P8
• Parity bit Pi checks all the bit positions, whose (Bit #) binary
representation has 1’s in position i.
Examples:
• P1 checks the bits 1,3,5,7,9,11,13 and 15 for “odd parity”
• P2 checks the bits 2,3,6,7,10,11,14 and 15 for “odd parity”
• P4 checks the bits 4,5,6,7,12,13,14 and 15 for “odd parity”
• P8 checks the bits 8,9,10,11,12,13,14 and 15 for “odd parity”
The Hamming Codes
• What is the 15 bit
Hamming code?
1- Bits 1, 2, 4, and 8
will be parity bits, and
the remaining 11 bits
will hold data.
2- Set bit 1 so that bits
1, 3, 5, 7, 9, 11, 13, and
15 will be in odd parity.
3- Set bit 2 so that bits
2, 3, 6, 7, 10, 11, 14,
and 15 will be in odd
parity.
Hamming Code
• What is the code for binary 1010 1001 010 for
Hamming (15, 11)?
• The Hamming (15, 11) codes for the binary sequences
1010 1001 010 and 1010 1101 010
are 101 1 01001010 001 and 101101101010001,
respectively.
Hamming codes use parity bits to correct errors during
data transmission.
Questions ?
Thank You