Message Delivery

Computer Science Level 2

When delivering binary messages, Chris has a bad habit to turn off some set bits. To ensure that Bob does not receive the wrong message, both Alice and Bob agrees on a checking scheme - Alice will send two messages, one consists of the original message and the other one stores the amount of off bits in binary. For example, the message $0 1 0 0 1 0$ will be compiled into $(0 1 0 0 1 0 \text{ , } 1 0 0)$ because the original message has 4 off bits, the check bits will be $100$ , which is 4 in decimal.

Now, Bob received the following compiled message $(1 0 0 1 1 0 0 0 0 1 0 1 0 0 \text{ , } 1 0 0 1)$

Which option bests describe the compiled message sent to Bob?

Details and Assumptions

It is possible for Chris to turn off the set bits in the check bits as well.

The message is delivered correctly The message is delivered wrongly Could not be determined

2 solutions

Christopher Boo
Sep 19, 2016

Observe the invariance when we investigate the 3 cases Chris can change the compiled message :

Case 1 : Only the check bits are changed
The check bits will get strictly smaller, thus will not match the amount of off bit in the original message.

Case 2 : Only the original message is changed
The amount of off bit in the original message will get strictly higher, thus the check bits will not match the amount of off bit in the original message.

Case 3 : Both check bits and original message are changed
The amount of off bit will get strictly higher but the check bits will get strictly smaller, thus they will never match.

These three cases tell us that no matter how Chris changes the compiled message, the check bits will not match the amount of off bit in the original message. In other words, since the check bits truly describe the amount of off bit in the original message, we conclude that Chris didn't change any bit and the message is delivered correctly.

This error-detecting method, called Berger Code , is implemented in the real world. As this problem suggests, Berger Code can only detect unidirectional errors. If Chris can change 0 to 1 and vice versa, this method is not going to work.

Ivan Koswara
Sep 18, 2016

We will prove that this method will allow Bob to check whether a message is sent correctly or not. (That is, if the message appears correct, as in the number of 0 bits is as stated, then the message is indeed correct.)

Suppose Bob receives the message $(m, c)$ (message, checksum). Observe that Chris only turns 1 bits to 0, not 0 bits to 1. Thus if $m$ has $x$ 0 bits, then the original message cannot have more than $x$ 0 bits. At the same time, if $c$ states the number $y$ , then the original checksum cannot be less than $y$ (because flipping bits to 0 will always reduce the value of a binary number). Thus if $x = y$ , we can be sure that the original message has exactly $x$ bits and the original checksum is exactly $y$ .

In the problem, this is the case; there are 9 zero bits in the message, and $1001_2 = 9$ , so the message is delivered correctly.

Message Delivery

2 solutions

0 pending reports