Encoding of 2-bit numbers A + B

Question

Consider two 2-bit binary numbers A and B ranging from integers [0,3]. Each bit in A and B have an equal probability of being either 0 0r 1.

Consider an encoding scheme for A+B (where A+B ranges from [0,6]), such that the decoder has access to any single bit in A+B. The question is: what is the encoding scheme that leaves the decoder with an equal probability of A, B being one among {0,1,2,3} by looking at any one of the bits in A+B?

Example: encoding scheme {000,001,010,011,100,101,110} leaves A with equal probability on {0,1,2,3} if we look LSB but not true for MSB.

In addition, the encoder should also satisfy the boolean addition properties. For example, if 0 is encoded as 'abc', $a,b,c \in \{0,1\}$ and 1 is encoded as 001, 0 + 1 (abc+001) should yield 001.

Any such boolean encoders or suggestions/references?

Answer 1

If I have understood your question correctly, there can be no such encoding, even if we neglect the "addition property".

Namely, look at every single bit in the output. We can prove that this bit must be "periodic with period $4$", i.e. it must be the same on encoding the sums $n$ and $n+4$, for $n=0,1,2$. As every bit in a multi-bit encoding must be periodic, this means that, no matter how many bits we use, we cannot possibly distinguish, say, sum $0$ from $4$, or $1$ from $5$, or $2$ from $6$.

Let $b_n\in \{0,1\}$ be a single-bit encoding of $n=0,1,2,\ldots,6$. We can see that $\frac{1}{16}(b_n+b_{n+1}+b_{n+2}+b_{n+3})$ (for $n=0,1,2,3$) is the same as the probability that $A=n$ and the encoding of $A+B$ is $1$. This is proportional (by a constant factor independent on $n$) to the conditional probability that $A=n$ assuming encoding of $A+B$ is $1$. But we want that conditional probability to stay the same, independent on $n$. Thus:

$$\frac{1}{16}(b_n+b_{n+1}+b_{n+2}+b_{n+3})=\frac{1}{16}(b_{n+1}+b_{n+2}+b_{n+3}+b_{n+4})$$

for $n=0,1,2$, which implies $b_{n+4}=b_n$.

Note that, in your example, both bits $0$ (LSB) and $1$ are periodic with period $4$ and both satisfy the desired property. The bit $2$ (MSB) is not periodic, and that is why (as per above proof) it cannot satisfy the desired property.

Answer 2

Here is a truth table of the addition encoding. A, B and A+B columns represent the decimal value of addition. The bits s2, s1, s0 represent the binary representation of the addition.

We observe that the frequency distribution of the 1s in s2, s1 and s0 and note that s1 and s0 have 50% probability of a 1 (or 0) whereas s2 is skewed with a probability of 6/16 (for 1s).

We also note that an encoding scheme is an automorphism in $GF(7)$ composed with a permutation of the resulting bits of s2, s1, s0. So, regardless of the permutation scheme used for the encoding, we need to use the non-skewed bit ie., s1 or s0 in the original unpermuted binary encoding of the sum if we want A+B to be 0, 1, 2 or 3 with equal probabilities after looking at just a single bit of the output.