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

1. cykhic
(edited )
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...

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.

2. [3]
Comment deleted by author
1. [2]
cfabbro
(edited )
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...

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:

These will likely be spoilers, so I wouldn't recommend watching them before trying to come up with a solution yourself first, but Computerphile has actually done a number of videos on Error Detection/Correction:

1 vote
1. [2]
Comment deleted by author