Coding Challenge - Design network communication protocol

Soptik
2019-04-17T13:12:44Z

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 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.

Comments URL: https://tildes.net/~comp/cf7/coding_challenge_design_network_communication_protocol

Votes: 8

Comments: 3