Before discussing the theory of self-complementing codes, we must have an idea about complementary numbers. Consider a number system with radix r. The basic elements of this family are numbers from 0 to r ‒ 1.
A number in a system with radix 2 is said to be the complementary of another number in the same system, if the sum of the two numbers amounts to the highest number (i.e., r ‒ 1) in that system. The first number is then said to be the (r ‒1)’s complement of the second number. If we add a ‘+1’ to the first number, we then get the r’s complement. The following steps will help in determining the complement of a given number.
1. Find the radix of the given number. Let it be r.
2. Find the basic elements of this number system. These will be 0, 1, …, r ‒ 1.
3. Find the highest basic number, which is r ‒ 1.
4. To find the complement of a given number, subtract it from r ‒ 1. Thus, if k is a given number in the system with radix r, then its complement will be (r ‒ 1) ‒k = r ‒ 1‒ k.
We now illustrate the use of the steps given above with some examples.
Example 19: Obtain the complement of decimal number 1.
Solution: In this example, we have to get the complement of k = 1.
Using 1, for decimal number system r = 10.
Using 2, the basic elements of this scheme are digits 0 to 9.
Using 3, the highest number is r ‒ 1 = 10 ‒ 1 = 9.
Using 4, complement of 1 = 9 ‒ 1 = 8.
One’s (1’s) Complement
In the binary number system, 1’s complement and 2’s complement play important roles in the subtraction of numbers. In this section, we explain the idea of 1’s complement using examples.
Example 20: Obtain the complement of binary numbers 0 and 1.
Solution: In this example, we have to get the complement of k = 0 and k = 1.
Using 1, for decimal number system r = 2.
Using 2, the basic elements of this scheme are digits 0 and 1.
Using 3, the highest number is r ‒ 1 = 2 ‒ 1 = 1.
Using 4, complement of 0 = 1 ‒ k = 1 ‒ 0 = 1
Using 4 again, complement of 1 = 1 ‒ 1 = 0
We thus find that the complement of 1 is 0 and the complement of 0 is 1. The advantage of this scheme is that any binary number has its complement easily obtained by simply replacing the 1s in it with 0s and 0s in it with 1s.
Example 21: Obtain the complementary number of 10110.
Solution: Replacing the 0s and 1s in 10110 with 1s and 0s, respectively, we obtain the complementary number of 10110 = 01001.
r’s and 2’s Complements
The r’s complement of a given number = (r ‒ 1)’s complement + 1. Thus, 2’s complement of a binary number = 1’s complement of that number + 1.
Example 22: Obtain the 2’s complement of 10110.
Solution: Replacing the 0s and 1s in 10110 with 1s and 0s, respectively, we obtain the 1’s complement of 10110 as 01001. Adding bit 1 to 01001 yields 01010. Thus
2’s complement of 10110 = 01010