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