Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I came across this question on Willy Wu's riddle site

You have two 3-bit sensors, A and B, that measure the same thing, whatever it is -- temperature of the room, radioactivity levels, whatever. Both sensors are hooked up to the same CPU, which takes in the sensor readings. You know that the sensors are designed so that their readings can be off by at most one bit. We claim that if B knows that A has sent the CPU a 3-bit sequence, then B only needs to send 2 bits, and the CPU will be able to reconstruct B's 3-bit measurement, thereby conserving bandwidth. How is this so?

This was apparently a research-level question from Wu's prof, so I doubt I'm misunderstanding a simple question of finding a bijection of 4 items.

My understanding is that the first bit is not the most significant bit (that would be trivial), they're 3 independent bits, and A and B's measurements differs from the actual by at most 1 bit somewhere. So say the actual measurement was [111], A can be [101] and B can be [011].

If you consider the Hamming distance between A and B, the maximum distance between A and B is 2, the minimum is 0. (From now on I will refer to "the Hamming distance between A and B" as "Hamming distance" for simplicity.)

At first glance this seems like an impossible task to represent all possible values of B given A. i.e., if you take A XOR B, you will get 7 possibilities {000, 001, 010, 011, 100, 101, 110}.

I think that somehow the 3 bits that A passes to the CPU must also contain information about B's 3 bits. Perhaps we could uniquely define B by the possible values of the actual measurement.

I also noted that whenever the Hamming distance is 2, there are 2 possible actual measurements, and they differ by a Hamming distance of 2. Whenever the Hamming distance is 1, there are 2 possible actual values and they differ by a Hamming distance of 1. Whenever the Hamming distance is 0 there are 4 possible actual values and they differ by a Hamming distance of 1.

Any ideas?

(Also, I apologise in advance if I overlooked some rules or standards. Please excuse me as it's my first time posting.)

share|improve this question
    
"My understanding is that the first bit is not the most significant bit (that would be trivial)" I'm not sure if this is not the correct reading, though. –  leonbloy Nov 1 '13 at 12:49

1 Answer 1

up vote 2 down vote accepted

Assuming that you reading of the problem statement is correct:

$B$ and $A$ can differ on 1 bit (or none), hence the difference (A XOR B) can take four possible values (000 001 010 100) . B only need to encode these 4 values, and it can be done with 2 bits.

Of course, this requires that B knows the value of A (it's not clear it does)


Update: better still (this does not require B to know A)

Let $B=(b_1,b_2,b_3)$ Trasmit $C=(c_1,c_2)$ where $c_1 = b_1 \oplus b_3$, $c_2 = b_2 \oplus b_3$

On the receiver side, it compares $c_1$ and $c_2$ with the analogous values for A: $c'_1=a_1 \oplus a_3$, $c'_2 =a_2\oplus a_3$ This is enough to reconstruct B

If $c'_1 = c_1$ and $c'_2 = c_2$ then no bits were changed ($A=B$)

If $c'_1 \ne c_1$ and $c'_2 = c_2$ then bit 1 has changed.

If $c'_1 \ne c_1$ and $c'_2 = c_2$ then bit 2 has changed.

If $c'_1 \ne c_1$ and $c'_2 \ne c_2$ then bit 3 has changed.

share|improve this answer
    
If A and B are allowed to each differ from the actual measurement by 1 bit, is there a solution? I guess I misunderstood the original question but I'm wondering if this is possible, and if not, can it be proven? –  chell Nov 16 '13 at 8:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.