In: Computer Science
A string of 0s and 1s is to be processed and converted to an
even-parity string by adding a parity bit to the
end of the string.(For an explanation of the use of parity bits,
see Example 30 in Chapter 9.) The parity
bit is initially 0. When a 0 character is processed, the parity bit
remains unchanged. When a 1 character
is processed, the parity bit is switched from 0 to 1 or from 1 to
0. Prove that the number of 1s in the final
string, that is, including the parity bit, is always even. (Hint:
Consider various cases.)
The information used to prove the given statement is as follows:
Proof:
When the first 1 is added to the string the parity bit is switched to 1, when the second 1 is added to the string it is again switched back to zero, for the third one it is again switched to 1 and so on.
Therefore, whenever there are (2n + 1) ones in the string then the parity bit is 1 and for 2n ones in the string the parity bit is 0, where (n>=0; n is an integer).
Case 1: When there are (2n+1) ones in the string:
Since, the parity bit is 1 in this case the total number of ones in the final string is equal to the number of ones in the original string plus 1.
Total number of ones in the final string = (2n + 1) + 1
= (2n + 2)
= 2(n+1)
A number multiplied by 2 is always an even number, therefore the total number of 1’s in this case will always be even.
Case 2: When there are (2n) ones in the string:
Since, the parity bit is zero in this case the total number of ones in the final string is equal to the number of ones in the original string only.
Total number of ones in the final string = 2n
A number multiplied by 2 is always an even number, therefore the total number of 1’s in this case will always be even.
Since, for all the cases, the total number of ones are always even in the final string (including the parity bit.) , therefore, the given statement is true.
Hence, proved.