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
A store manager orders T-shirts that 15 out of every 35 or medium. How many medium T-shirts would you expect to find when there
sladkih [1.3K]

There would be 60 medium shirts

3 0
3 years ago
The area of the kite is 30 m2. What is the value of x? Explain
astra-53 [7]

Answer:

x = 5

Step-by-step explanation:

5 0
3 years ago
So there is 400 student and 12% kids want to be athletes how many kids want to be athlete?
lisabon 2012 [21]

Answer:

48

Step-by-step explanation:

8 0
3 years ago
Activity 1<br>Calculate the following:<br>1. 68% of 418,​
il63 [147K]

Answer:

284.24

Step-by-step explanation:

by multiplying 0.68 to 418 we get 68% of 418

7 0
3 years ago
Read 2 more answers
At a local restaurant, the health inspector visits every 7 days, and the fire inspector visits every 12 days.
Svetllana [295]
They will both come on the 84th day
8 0
3 years ago
Other questions:
  • Please help me<br> What is the area of the orange figure? *
    13·2 answers
  • Branliest offered
    5·1 answer
  • Explain how to use a coordinate plane to find the area of a rectangle with vertices (–4, 9), (–4, –3), (–1, –3), and (–1, 9). wh
    10·2 answers
  • A number with one or more digits to the right of the decimal point is called a
    9·2 answers
  • What is 21-123+12*196
    10·1 answer
  • During the period of time that a local university takes phone-in registrations, calls come in at the rate of one every two minut
    8·1 answer
  • Exactly 512 tickets were sold for the talent show at Cypress Middle School. The number of student tickets sold was three times t
    5·1 answer
  • A dozen large muffins cost $7.99.<br> How much does each muffin cost?
    8·2 answers
  • 25% of what number is 20?​
    10·2 answers
  • Express 3.847* 10^(3 )in scientific notation
    7·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!