1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
Ainat [17]
3 years ago
8

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

Mathematics
1 answer:
AleksandrR [38]3 years ago
3 0

Answer:

Lets denote c the concatenation of strings. For a binary string <em>a</em> 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.

You might be interested in
In the 2016 Rio Olympic games, the total of gold, silver and bronze medals won by China was 70.
Oksana_A [137]
26 gold metals

Explanation: 70 - 18 silver = 52 metals left

52/2= 26 … so 26 + 26= 52 52 + 18=70
3 0
2 years ago
Amanda has 4 liters of juice and some glasses. She will pour 1/4 liter of juice into each glass. What is the total number of gla
scZoUnD [109]

Answer:

16 glasses

Step-by-step explanation:

If 1 glass = 1/4 liter of juice

then 16 glasses = 4 liters of juice

because 4 divided by 1/4 = 16

8 0
3 years ago
The Pythagorean theorem can be used for any type of triangle. true or false
notka56 [123]
False. Only right triangles.
8 0
3 years ago
For 15 points plz help
blondinia [14]

Answer:

the number that goes in the blank is 8

Step-by-step explanation:

5 0
3 years ago
Is the following statment true or false? explain your reasoning <br> 15+ (4x6) = (15+4) x6
Levart [38]

Answer:foot

Step-by-step explanation:

4 0
3 years ago
Read 2 more answers
Other questions:
  • United Flight 15 from New York's JFK airport to San Francisco uses a Boeing 757-200 with 182 seats. Because some people with res
    14·1 answer
  • Calculate the volume of the cylinder.<br><br> 4cm<br> 10 cm<br> Use<br> h = 3. 14.
    15·1 answer
  • Need help ASAP test finishes in 30 mins
    9·1 answer
  • What is the domain of f(x)=(1/2)^x
    9·1 answer
  • Simplify, using the distributive property and then combining like terms. 2(x+y)+(2x−2y)
    7·1 answer
  • Use the figure to find the measures of the numbered angles, help! 7,8,9
    15·1 answer
  • Can someone help me with this please
    7·1 answer
  • The graph represents the number of cans produced at a factory with four machines.
    9·1 answer
  • Given IQ scores are approximately normally distributed with a mean of 100 and a standard deviation of 15 , the proportion of peo
    13·1 answer
  • Solve for "y" if 2x + 8y = 6
    6·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!