3-Bit Sensors

A remote weather station uses two redundant 3-bit sensors to measure atmospheric pressure. Both sensors transmit their readings to a central processor, but bandwidth is limited. The engineers know the sensors are well-calibrated—their readings can differ by at most one bit.

The station’s designer claims that sensor B only needs to send 2 bits instead of 3, and the processor can still reconstruct B’s full reading. Sensor B knows that sensor A has already sent its 3-bit sequence to the processor, but B doesn’t know what that sequence was. How can this work?

Solution

Answer: B sends two bits: $x_{b} = b_{1} \oplus b_{2}$ and $y_{b} = b_{2} \oplus b_{3}$ , where $\oplus$ denotes XOR.

Let’s say A’s reading is $(a_{1}, a_{2}, a_{3})$ and B’s reading is $(b_{1}, b_{2}, b_{3})$ . B computes and transmits:

$x_{b} = b_{1} \oplus b_{2}$
$y_{b} = b_{2} \oplus b_{3}$

The processor receives A’s full reading and B’s two bits $(x_{b}, y_{b})$ . To reconstruct B’s reading, the processor computes the same XOR operations on A’s reading:

$x_{a} = a_{1} \oplus a_{2}$
$y_{a} = a_{2} \oplus a_{3}$

Now the processor compares $(x_{b}, y_{b})$ with $(x_{a}, y_{a})$ . There are four cases:

Case 1: Both match ( $x_{b} = x_{a}$ and $y_{b} = y_{a}$ ) A and B are identical. B’s reading is $(a_{1}, a_{2}, a_{3})$ .

Case 2: Only x differs ( $x_{b} \neq x_{a}$ and $y_{b} = y_{a}$ ) Since $b_{1} \oplus b_{2} \neq a_{1} \oplus a_{2}$ but $b_{2} \oplus b_{3} = a_{2} \oplus a_{3}$ , we know $b_{2} = a_{2}$ and $b_{3} = a_{3}$ , so $b_{1}$ must differ from $a_{1}$ . B’s reading is $(a_{1} ‾, a_{2}, a_{3})$ , where $a_{1} ‾$ denotes the negation of $a_{1}$ .

Case 3: Only y differs ( $x_{b} = x_{a}$ and $y_{b} \neq y_{a}$ ) By similar reasoning, $b_{3}$ differs from $a_{3}$ . B’s reading is $(a_{1}, a_{2}, a_{3} ‾)$ .

Case 4: Both differ ( $x_{b} \neq x_{a}$ and $y_{b} \neq y_{a}$ ) Since $b_{1} \oplus b_{2} \neq a_{1} \oplus a_{2}$ and $b_{2} \oplus b_{3} \neq a_{2} \oplus a_{3}$ , the middle bit $b_{2}$ must be the one that changed (it appears in both XOR operations). B’s reading is $(a_{1}, a_{2} ‾, a_{3})$ .

Let’s verify with a concrete example. Suppose A’s reading is 101 and B’s reading is 100 (the third bit differs).

B computes: $x_{b} = 1 \oplus 0 = 1$ and $y_{b} = 0 \oplus 0 = 0$ , and sends $(1, 0)$ .

The processor computes from A: $x_{a} = 1 \oplus 0 = 1$ and $y_{a} = 0 \oplus 1 = 1$ .

The processor sees: $x_{b} = x_{a}$ (both are 1) but $y_{b} \neq y_{a}$ (0 ≠ 1). This is Case 3, so the third bit changed.

The processor reconstructs: $(1, 0, 1 ‾) = (1, 0, 0)$ . Correct!

This encoding works because each bit position has a unique “signature” in the two XOR values:

$b_{1}$ appears only in $x_{b}$
$b_{3}$ appears only in $y_{b}$
$b_{2}$ appears in both $x_{b}$ and $y_{b}$
No change means $x_{b} = x_{a}$ and $y_{b} = y_{a}$

This creates four distinct patterns, exactly matching the four possible cases under the “at most one bit different” constraint.

Try These Next

Planting Trees 2

Chain Link 2

Treasure and Locks