A string of 0s and 1s is to be processed and converted to an even-parity string
ID: 3793771 • Letter: A
Question
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.)
Explanation / Answer
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.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.