Coding Challenge - Design network communication protocol
It's time for another coding challenge!
This challenge isn't mine, it's this challenge (year 5, season 3, challenge 3) by ČVUT FIKS.
The task is to design a network communication protocol. You're sending large amount of bits over the network. The problem is that network is not perfect and the message sometimes arrives corrupted. Design a network protocol, that will guarantee that the decoded message will be exactly same as the message that was encoded.
MESSAGE => (encoding) => message corrupted => (decoding) => MESSAGE
Corruption
Transmitting the message might corrupt it and introduce errors. Each error in a message (there might be more than one error in a single message) will flip all following bits of the message.
Example:
011101 => 011|010
(| is place where an error occured).
There might be more than one error in a message, but there are some rules:
-
Minimum distance between two errors in a single message is
k -
Number of bits between two errors is always odd number
According to these rules, describe a communication protocol, that will encode a message, and later decode message with errors.
Bonus
-
Guarantee your protocol will work always - even when errors are as common as possible
-
Try to make the protocol as short as possible.
Firstly, if k = 1, the task is impossible, because an adversary can make any message map onto any other message. So the worst-case k to consider is k = 3.
My encoding uses 4 encoded bits per message bit.
Encoding
The encoding procedure is simple: encode bit "b" as "0b0b". A message of "011" would therefore be encoded as "000001010101".
Decoding
To decode, first split into chunks of four bits, and consider them separately. Notice that there is at most one error between the first and last bit of the message ("a|b|c|d").
Let's denote the encoded message as "axby", where a,x,b,y take values {0,1}.
Recall that "a" and "b" were always initially encoded as 0.
If "a" = "b", then because there is only one error, we know that the error must fall at "axb|y", and "x" is of the same error parity as "a". Return "a" XOR "x" as the value of this decoded bit.
Else, if "a" != "b", then we know the error falls either right before somewhere in "a|x|by". Hence we know "b" is of the same error parity as "y". Return "b" XOR "y" as the value of this decoded bit.
Edit:
In fact, there's an even better solution.
Encoding
Message "abcd" gets encoded to "a0ab0bc0cd0d".
Decoding
Split the message into chunks of 3 bits, and let variable "p" = 0 to start. "p" denotes the current known message parity.
Begin decoding with the leftmost 3-bit chunk. Denote this chunk by "xay". Recall that "a" was initially encoded as 0, and "x" and "y" were initially encoded as the same bit, the message bit.
If "p" = "a", then there was no error between the previous chunk and "a", and we infer the error parity of "x" and "a" are the same. Return message bit "m" = "a" XOR "x" for this bit. Additionally, set "p" = "m" XOR "y", so that "p" is the error parity of "y".
Else, if "p" != "a", we know an error falls within "|x|ay". Then, we know that "a" and "y" have the same error parity, and return "m" = "a" XOR "y". Set "p" = "a", and continue.
LOL, funny you should mention that since I was actually going to post some Computerphile videos where they covered basic error detection and correction... but instead decided to PM @Soptik to see if they were cool with it first, since I didn't want to ruin the challenge. So I am kinda of curious to hear people's thoughts on this too.
Edit: Soptik gave the thumbs up, so here was the comment I was originally gonna post:
Anyone who frequents Usenet, especially the binaries, has probably also heard of and regularly used parchive (parity+archive) files, e.g. .PAR2 (spoilers since that link explains how they work), to verify the integrity of and recover corrupted data as well. There are so many unique and interesting ways to solve the problem. :)