Ask Question
1 November, 09:07

Using the bijection rule to count binary strings with even parity.

Let B = {0, 1}. Bn is the set of binary strings with n bits. Define the set En to be the set of binary strings with n bits that have an even number of 1's. Note that zero is an even number, so a string with zero 1's (i. e., a string that is all 0's) has an even number of 1's.

(a) Show a bijection between B9 and E10. Explain why your function is a bijection.

+5
Answers (1)
  1. 1 November, 11:00
    0
    Lets denote c the concatenation of strings. For a binary string a in B9, we define the element f (a) in E10 this way:

    f (a) = a c {1} if a has an odd number of 1's f (a) = a c {0} if a has an even number of 1's

    Step-by-step explanation:

    To show that the function f defined above is a bijective function, we need to prove that f is well defined, injective and surjective.

    f is well defined:

    To see this, we need to show that f sends elements fromo b9 to elements of E10. first note that f (a) has 1 more binary integer than a, thus, it has 10. if a has an even number of 1's, then f (a) also has an even number because a 0 was added. On the other hand, if a has an odd number of 1's, then f (a) has one more 1, as a consecuence it will have an even number of 1's. This shows that, independently of the case, f (a) is an element of E10. Thus, f is well defined.

    f is injective (or one on one):

    If a and b are 2 different binary strings, then f (a) and f (b) will also be different because the first 9 elements of f (a) form a and the first elements of f (b) form b, thus f (a) is different from f (b). This proves that f in injective.

    f is surjective:

    Let y be an element of E10, Let x be the first 9 elements of y, then f (x) = y:

    If x has an even number of 1's, then the last digit of y has to be 0, and f (x) = x c {0} = y If x has an odd number of 1's, then the last digit of y has to be a 1, otherwise it wont be an element of E10, and f (x) = x c {1} = y

    This shows that f is well defined from B9 to E10, injective, and surjective, thus it is a bijection.
Know the Answer?
Not Sure About the Answer?
Get an answer to your question ✅ “Using the bijection rule to count binary strings with even parity. Let B = {0, 1}. Bn is the set of binary strings with n bits. Define the ...” in 📙 Mathematics if there is no answer or all answers are wrong, use a search bar and try to find the answer among similar questions.
Search for Other Answers