Decoding rule

After receiving a Binary Code through a Binary Symmetric Channel (BSC), we need to decode it.

There are 3 rules we consider when decoding.
Due to the lemma at the bottom, we shall use the Minimum distance decoding rule.

Ideal Observer

The ideal observer decoding rule decodes as the codeword maximising

This is actually the most reasonable decoding rule but it assumes that the observer has information about the probability of each message being sent.

---

Maximum likelihood

The maximum likelihood decoding rule decodes as maximising

Lemma

If all messages are equally likely then maximum likelihood agrees with the Ideal Observer.

Proof

By Baye’s rule trivial.

---

Minimum distance

The minimum distance decoding rule decodes as minimising the Hamming distance .
Some convention needed in the case of a tie, eg. choose at random or ask for message to be sent again.

Lemma

If the probability of a bit being mismatched is then the minimum distance rule agrees with Maximum Likelihood.

Proof

Suppose

Since , choosing to maximise the above probability is the same as choosing to minimize