Coding Challenge - Design network communication protocol
Previous challenges 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...
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.