Apologies for the delay in posting the solution; I’ve been swamped at work. Here it is!
The first person to solve the Parity Encoding Puzzle correctly after I published it was Vittorio’s wife, Iwona, with a very elegant and compact solution, which is slightly different from mine.
First, I will explain my thought process in solving the puzzle, then show my code, and then show you Iwona’s code (which makes my code look clumsy). If you still want to try solving it for yourself, don’t read any further. If you have solved it using another language or technique, feel free to post your solution here.
With a 2-bit buffer
The first step is to start with a smaller version of the problem. If a buffer of size 2^n can store n bits of information, then a 2-bit buffer can store 1 bit. All possible initial states of the random buffer are:
00
01
10
11
It’s pretty easy to see what to do. If you want to send a ‘1’, just flip the first bit if it’s zero, otherwise flip the second bit.
At this point, you’re probably noticing that the second bit has no informational value; it’s sort of a “throwaway bit”. If the rules were different, and you were permitted to either flip a bit or abstain, it would be similar (for the case of a 2-bit buffer).
With a 4-bit buffer
In a 4-bit buffer, you can store 2 bits of information (4 possible values). A 4-bit buffer has only 16 possible initial states, so it’s easy to sketch on paper, and try the 4 possible coded values.
Encoding the first bit of the information is easy. Just apply the pattern from the 2-bit solution, but use the parity of the first 2-bits of the 4-bit buffer as your value. In other words, if the first bit of your information is a ‘1’, the parity of the left half of the 4-bit buffer should be even, otherwise it should be odd.
Switching the parity is easy; you just flip a bit in the target half, and the parity toggles. But you’re then faced with the question of which bit to flip. For example, if your starting buffer is 1011 and the value to code is 10, you need to flip a bit on the left half – you could do that by flipping either the first or second bit, resulting in either 1111 or 0011. Additionally, you’re faced with the problem that you’ve used up your only allowed toggle, and you still haven’t encoded the second bit.
This latter fact should make the way forward obvious. The bit that you choose to flip (resulting in a 0011 or 1111) should be determined by the second bit of information (10). You can do this by saying that the parity of the opposite half (the final 2 bits in this case: 1011) must match the value of the second bit in the half being toggled (in this case, the 1011), if the bit being communicated is a 1. You can arbitrarily decide that a bit value of 0 represents odd parity, and 1 represents even parity. In this case, the second bit of information (10) is not a 1, so you want the value of the second bit to be different from the parity of the opposite side. The second bit, representing odd parity (1011) is already different from the parity of the opposite half (1011) so you needn’t flip the second bit – flip the first bit instead. The encoded buffer, therefore, is 0011.
You can easily prove this technique on paper or by writing a quick program. It is worth working through the combinations yourself to make sure you understand what’s happening.
Note that you always think in terms of “opposite side”, since you’ll only be flipping a bit on the left side half of the time. Also note that the decision to compare the second bit to the parity of the opposite side is completely arbitrary, just like the decision to use 1 to mean “even”. You could change the rules, as long as you are consistent.
With an 8-bit buffer
At this point, you might be feeling confident, and think that you only need to recursively apply the 4-bit solution to manage a buffer of any size. You would be right, but it’s easier said than done. My first attempt worked 90+% of the time, but failed on some edge cases.
An 8-bit buffer holds 3 bits of information. You could try something like this (colors show parity comparison):
- 1010 1010 – first bit
- 1010 1010 – second bit
- 1010 1010 – third bit
Obviously, the position of the second and third bit will vary, depending on where the previous bits are selected.
Observation: If you implement this, you’ll notice 2 things (besides the fact that it fails some of the time). First is that decoding has no idea whether you moved left or right in a given step, so half the time it will get the right answer only accidentally. Second is that you’re leaving a lot of bits unused (for parity comparison purposes), which intuitively shouldn’t work. It’s true that you will have a “throwaway bit”, but it should only be one bit.
This leads to the key intuition required to solve the puzzle generally.
The Solution
You need to “stripe” the parities; using every bit except the throwaway bit. An simple example of decoding a value will make it clear. Suppose that the received buffer is 10110000. How do you decode it?
(For this case, we arbitrarily decide that parity equals the number of 1’s in the red area, and that 1 is “odd” [since it has an odd number of 1’s])
- 1011 0000 – parity of left half = 1 (odd)
- 1011 0000 – parity = 1 (odd)
- 1011 0000 – parity = 0 (even)
Therefore, the encoded value is 110.
Step 3 is the key step: you notice that we are using 2 extra bits in our parity calculation more than we used in the failed attempt. The only bit which is never used is the last bit, which you would flip only if the random buffer exactly matched the message you wanted to send.
You can also detect a pattern here:
- Step 1: combine alternating blocks of 4 bits and calculate parity.
- Step 2: combine alternating blocks of 2 bits and calculate parity.
- Step 3: combine alternating blocks of 1 bits and calculate parity.
It’s easy to generalize this to a buffer of any size. For example, if you are using a 128 bit buffer, you would use parity “stripes” of size 64, 32, 16, 8, 4, 2, and 1 (for 7 bits of information).
If you’d like to try writing your own code before looking at mine, you can pause here.
My Code
I used a very direct implementation of the process described above. The “Parity” function takes a bit buffer and a width, and combines alternating blocks of size “width” before spitting out a parity. The Encode and Decode functions use this Parity function. You can trace through a few examples on paper to see how easy it is.
public int Parity(int width, BitBuffer buffer)
{
int p = 0;
bool even = true;
while (p < buffer.Length)
{
for (int i = 0; i < width; i++)
{
if (buffer[p + i] == 1) even = !even;
}
p += width * 2;
}
return (even ? 0 : 1);
}
public BitBuffer Decode(BitBuffer buff)
{
string value = "";
int width = buff.Length;
while (width > 1)
{
width = (int)Math.Truncate((double)width / 2);
value += Parity(width, buff).ToString();
}
return new BitBuffer(value);
}
public void Encode(BitBuffer encode, BitBuffer initial )
{
int[] bits = encode.GetBuffer();
int pos = 0;
int width = initial.Length;
for (int idx = 0; idx < bits.Length; idx++)
{
pos *= 2;
width = (int)Math.Truncate((double)width / 2);
int half = (int)Math.Truncate((double)initial.Length / width / 2);
if (Parity(width) == bits[idx]) pos += 1; // the left half is good; don't mess with it
}
if (initial[pos] == 0) initial[pos] = 1;
else initial[pos] = 0;
}
Iwona’s Code
Iwona’s Code is very compact, using xors and bit shifts, and not needing a separate parity stripe test (solved for 64-bit, but will work on any buffer size). Very nice!
private static UInt64 Encode(UInt64 buffer, byte number)
{
byte i = 0;
UInt64 tempBuffer = buffer;
while (tempBuffer > 0)
{
if (tempBuffer % 2 == 1)
{
number ^= i;
}
i++;
tempBuffer = (tempBuffer >> 1);
}
return buffer ^ ((UInt64)1 << number);
}
private static byte Decode(UInt64 buffer)
{
byte i = 0;
byte number = 0;
while (buffer > 0)
{
if (buffer % 2 == 1)
{
number ^= i;
}
i++;
buffer = (buffer >> 1);
}
return number;
}
