Binary Symmetric Channel (BSC)

Discrete Memoryless Channel (DMC) which has with probability and Channel Matrix

ie is probability a symbol is mistransmitted.

Lemma

Let . A Binary Symmetric Channel (BSC) with error probability is used to send digits. Then

as

Proof

Let

are iid variables

by weak law of large numbers.

Proposition

The capacity of a Binary Symmetric Channel (BSC) with error probability is

Proof

Choose with
We prove reliable encoding at rate
Let be the largest code of length and
??????????? RACHEL PLEASE STOP HIDING YOUR BLACKBOARDS!!!!
12 ferburary lecture

Replacing by subcode gives and still minimum distance
Using minimum distance decoding

Pick st
Then for sufficiently large
Therefore

as by lemma