Fundamentals of Mathematical Informatics
Communication through Noisy Channels

Francesco Buscemi

Lecture FourFrancesco Buscemi

Fundamentals of Mathematical Informatics

Lecture Four1 / 21

Lecture Four2 / 21

General communication scheme

Francesco Buscemi

Fundamentals of Mathematical Informatics

The discrete memoryless channel (DMC)
In lecture one, we said that a RV X is like a ‘device’ that outputs an element froma set {x1 , · · · , xn } with probability Pr{X = xi } = pi .
Imagine now a ‘device’ that has an output and an input: it accepts strings ofsymbols from its input alphabet Σ1 = {a1 , · · · , am } and emits strings of symbols
from an output alphabet Σ2 = {b1 , · · · , bn }.
A discrete memoryless channel (DMC) is given by: an input alphabet
Σ1 = {a1 , · · · , am }, an output alphabet Σ2 = {b1 , · · · , bn }, and a channel matrix
P = [[pij ]]ij (1 6 i 6 m, 1 6 j 6 n) of transition probabilities:
def

def

pij = p(bj |ai ) = Pr{output is bj |input was ai }.
PTherefore, pij > 0 for all i and j, and j pij = 1 for all i.
Memory trick. To remember which is the input and which is the output, think as
if pij = pi→j .
The channel is ‘discrete’ because input and output alphabets are discrete sets.
The channel is ‘memoryless’ because the channel matrix P remains the same forrepeated uses.
Francesco Buscemi

Fundamentals of Mathematical Informatics

Lecture Four3 / 21

Lecture Four4 / 21

Example: the binary erasure channel

In this case, Σ1 = {0, 1}, Σ2 = {0, 1, /}, andP = 01Francesco Buscemi

01−0

101−

/


Fundamentals of Mathematical Informatics

Example: the binary symmetric channel

In this case, Σ1 = Σ2 = {0, 1} andP = 01

Francesco Buscemi

01−pp1p1−pFundamentals of Mathematical Informatics

Lecture Four

5 / 21Input and output of a DMC as RVs
Let X be a RV with range X = {x1 , · · · , xm } and probability distribution(p1 , · · · , pm ).
Take now a DMC N with input alphabet X , output alphabet Y = {y1 , · · · , yn },and channel matrix P = [[pij ]].
What happens if we ‘feed’ X through N ?
PPm
Pr{‘output is yj ’} = m
i=1 Pr{X = xi }pij =i=1 pi pij .
We obtain another RV YP, with range equal to Y and probability distribution(q1 , · · · , qn ) where qj = i pi pij .

I/O joint distribution
With the notation introduced above, the action of a DMC channel N on
an input RV X gives rise to a pair of dependent RVs (X, Y ) with joint
probability distribution given byPr{X = xi and Y = yj } = pi pij .
Sometimes we write Y = N (X).
Francesco Buscemi

Fundamentals of Mathematical Informatics

Lecture Four

6 / 21

r-th extension of a DMC: in series(r)What happens when we feed a string of r symbols (α1 , · · · , αr ) ∈ Σ1
memoryless channel?

through a discrete

The r-th extension of a DMC is then itself a DMC from an input r-dimensional RV X with(r)(r)
range Σ1 , to an output r-dimensional RV Y with range Σ2 . The channel matrix is given by
the product of the transition probabilities:
defPr{Y = β1 · · · βr |X = α1 · · · αr } = p(Y |X) = p(β1 |α1 ) · · · p(βr |αr ).
Francesco Buscemi

Fundamentals of Mathematical Informatics

Lecture Four

7 / 21r-th extension of a DMC: in parallel
We can also think of channel extensions this way:

We have now many copies of the same noisy channel acting ‘in parallel.’Mathematically, serial and parallel extensions are equivalent.
Francesco Buscemi

Fundamentals of Mathematical Informatics

Lecture Four

8 / 21

Example: sending a message through a binary symmetricchannelImagine that we want to send one word si , chosen at random among
eight possible words {s1 , · · · , s8 }, via a binary symmetric DMC.
First, we have to encode all words in binary alphabet (the channel
only accepts 0s and 1s!).
s1 7→ 000, s2 7→ 001, · · · , s8 7→ 111.
Here we use the third extension of the binary symmetric channel (theinput consists of three bits.)
What is the probability that the receiver gets the wrong word?
Pr{wrong word} = 1 − Pr{correct word} = 1 − (1 − p)3 =p(3 − 3p + p2 ). (For p = 0.5 is ≈ 0.88; for p = 0.1 is ≈ 0.27.)
Can we do better?

Francesco Buscemi

Fundamentals of Mathematical Informatics

Lecture Four

9 / 21First idea: repetition codes (repeating words)
Let’s try to send each word twice through the channel, i.e.,s1 7→ 000 000, s2 7→ 001 001, · · · , s8 7→ 111 111.
As a decoding rule, if the receiver does not get the same word twice in succession, sherequests an immediate resending.
What is the probability of decoding error in this case, i.e., the probability that the receivergets the wrong word without detecting it?
First possibility: one error in the first three bits and one error, in the same position, in thesecond three bits. This contributes with 3 × p(1 − p)2 × p(1 − p)2 = 3p2 (1 − p)4 .
Second possibility: two errors in the first three bits, and two errors, in the same positions,in the second three bits. This contributes with 3 × p2 (1 − p) × p2 (1 − p) = 3p4 (1 − p)2 .
Third possibility: six errors in a row. This contributes with p6 .
Total decoding error probability: p2 (3 − 12p + 21p2 − 18p3 + 7p4 ). (For p = 0.5 is≈ 0.11; for p = 0.1 is ≈ 0.02.)
But: it requires feedback from the receiver, for each letter sent.
But: with increasing length, the receiver will almost always request a resending.
Hence: zero total decoding error requires infinite repetitions (no reliable communication ispossible)

Francesco Buscemi

Fundamentals of Mathematical Informatics

Lecture Four

10 / 21Second idea: parity-check codesInstead of just repeating codewords, we can try to exploit another idea.
Parity-check coding: it adds one extra bit (the ‘parity bit’) at the end ofeach codeword, so that the sum of the digits is always even.
In our case, this gives:
s1 7→ 000 0, s2 7→ 001 1, s3 7→ 010 1, s4 7→ 011 0, · · · s8 7→ 111 1.
If the receiver gets four bits whose sum is odd, she requests an immediateresending. (Hence the name, ‘parity-check.’)
What is the probability of decoding error in this case, i.e., the probabilitythat the receiver gets the wrong word without detecting it?
A wrong decoding happens if there were two or four errors, therefore thedecoding error probability is 6p2 (1 − p)2 + p4 . (For p = 0.5 is ≈ 0.44; forp = 0.1 is ≈ 0.05.)
But: this code requires feedback.
Remark: this simple idea can be improved, and it is at the basis of somevery important families of codes (Low Density Parity-Check, LDPC).
Francesco Buscemi

Fundamentals of Mathematical Informatics

Lecture Four

11 / 21

Third idea: Shannon approach (definitions)

Take a DMC with Σ1 and Σ2 as input and output alphabets,respectively.
An (M, n) code consists of the following:
123An index set {1, 2, · · · , M }.
def(n)
An encoding function c : {1, 2, · · · , M } → Σ1 (i.e., each ci = c(i) is
a string of n symbols in Σ1 , e.g., ci = α1 α2 · · · αn ).
(n)A decoding function g : Σ2 → {1, 2, · · · , M }.

The collection C = {c1 , · · · , cM } is called the codebook and itselements are called the codewords. M (the number of codewords) isthe size of the code, while n (the length of each codeword) is its
length.

Francesco Buscemi

Fundamentals of Mathematical Informatics

Lecture Four

12 / 21

Encoding-transmission-decoding: chain of RVs
The encoding-transmission-decoding process can be summarized as:
EN

Dnnn
W −→
X −→
Y −→
Ŵ

What does this mean?
W , the message: a RV with range {w1 , · · · , wM } and probabilities p1 , · · · pM .
En : W → X, the length-n encoding: a DMC with input alphabet {w1 , · · · , wM },(n)output alphabet Σ1 , and channel matrix given bydefp(X|wi ) = Pr{X = α1 · · · αn |W = wi } = δX,ci .
Nn : X → Y , the n-th extension of the communication channel: a DMC with(n)(n)
input alphabet Σ1 , output alphabet Σ2 , and channel matrixdefp(Y |X) = Pr{Y = β1 · · · βn |X = α1 · · · αn } = p(β1 |α1 ) · · · p(βn |αn ).
(n)Dn : X → Ŵ , the decoding: a DMC with input alphabet Σ2 , output alphabet{w1 , · · · , wM }, and channel matrix given bydefp(wj |Y ) = Pr{Ŵ = wj |Y = β1 · · · βn } = δg(β1 ···βn ),j .
A decoding error happens whenever Ŵ 6= W . What is the probability that adecoding error occurs?
Francesco Buscemi

Fundamentals of Mathematical Informatics

Lecture Four

13 / 21

Fundamentals of Mathematical Informatics

Lecture Four

14 / 21

A picture

Francesco Buscemi

Decoding error probability
How to compute the error probability, i.e. Pr{Ŵ 6= W }?
defPr{Ŵ 6= W } =M
XXPr{Ŵ = wj , W = wi }j6=i i=1=M
X

Pr{Ŵ = wj , W = wi } −i,j=1=1−

M
X

Pr{Ŵ = wi , W = wi }

i=1

M
X

Pr{Ŵ = wi , W = wi }i=1=1−XXX
i=1−

X

XXX
i=1−

p(wi |Y )p(Y |X)p(X|wi )piYXδg(Y ),i p(Y |X)δX,ci pi

YXXiY ∈g −1 (i)p(Y |ci )pi

The error probability crucially depends on the choice of the decoding function g.
Francesco Buscemi

Fundamentals of Mathematical Informatics

Lecture Four

15 / 21

Ideal-observer (minimum error) decoding
Pr{Ŵ 6= W } = 1 −P Pj

Y δj,g(Y ) p(Y |cj )pj .
def

Rewrite p(Y |cj )pj as p(cj , Y ) = Pr{cj sent and Y received}.
Rewrite it again as p(cj , Y ) = p(cj |Y )pY , whereP
defpY = Pr{Y received} = M
j=1 p(cj , Y ).
P P
Then, Pr{Ŵ 6= W } = 1 − Y j δj,g(Y ) p(cj |Y )pY .
(n)Choose the decoding function g : Σ2 → {1, 2, · · · , M } in such a
way that p(cg(Y ) |Y ) > p(cj |Y ), for all 1 6 j 6 M .
Equivalently: g(Y ) = arg maxj p(cj |Y ).
This decoding method is called ideal-observer or minimum-error,because it minimizes the error probability.
Meaning: upon receiving Y , use this piece of information to infer
the most probable codeword.
The ideal-observer decoding is optimal! However: the construction
depends on the choice of probabilities p1 , · · · , pM , which is a serious
disadvantage.
Francesco Buscemi

Fundamentals of Mathematical Informatics

Lecture Four

16 / 21

Maximum-likelihood decodingPr{Ŵ 6= W } = 1 −P PY δj,g(Y ) p(Y |cj )pj .
(n)Choose a decoding function g : Σ2 → {1, 2, · · · , M } such thatjp(Y |cg(Y ) ) > p(Y |cj ), for all 1 6 j 6 M .
Equivalently: g(Y ) = arg maxj p(Y |cj ).
This decoding method is called maximum-likelihood (ML).
Meaning: upon receiving Y , decode it with the codeword ci that, ifsent, maximizes the probability of receiving Y .
Since, in general, p(Y |ci ) 6= p(ci |Y ), ML decoding and ideal-observer
decoding may give different results.
Con: sub-optimal. Pro: independent of the pi ’s, much easier toimplement.
Question: when do ML and ideal-observer decodings agree?
1Answer: they agree if p1 = p2 = · · · = pM = M.
Francesco Buscemi

Fundamentals of Mathematical Informatics

Lecture Four

17 / 21

Example: minimum-error vs max-likelihood
Suppose you are at the receiver’s end of a binary symmetric channel
def
9with error probability  = p0→1 = p1→0 = 10.
Suppose you receive a ‘zero.’ What is the best guess for the input?
Since the channel introduce an error 90% of the times, one would say:the best guess is that the input was ‘one.’
This is what a max-likelihood strategy says.
However, imagine that you know that the sender sends ‘zero’ with191
probability p(in=0) = 20
and ‘one’ with p(in=1) = 20.
and out=0)
p(in=1)
Then, p(in=1|out=0) = p(in=1=p(out=0)(1−)p(in=0)+p(in=1) =9 1
10 20
1 19
9 1+ 10
10 20
20

9= 28
≈ 0.32.

Therefore p(in=0|out=0) = 1 − p(in=1|out=0) ≈ 0.68.
According to the ideal-observer rule (the optimal one), the best guessis that the input was ‘zero.’Francesco Buscemi

Fundamentals of Mathematical Informatics

Lecture Four18 / 21

Minimum-distance decoding (Hamming distance)
Let Vn be the set of all binary sequences of length n.
Definition: given x, y ∈ Vn , their Hamming distance d(x, y) is defined as
the number of places in which x and y differ.
Example: take V4 and x = 0001 and y = 1011; then d(x, y) = 2 (first andthird digits are different).
Minimum-distance decoding: choose the decoding function(n)g : Σ2 → {1, · · · , M } such that d(Y , cg(Y ) ) 6 d(Y , cj ), for all
1 6 j 6 M.
Meaning: upon receiving Y , decode it with a codeword ci that is ‘as close
as possible’ to Y , according to the Hamming distance.

Min-Distance ≡ Max-Likelihood (for binary symmetric channels)
Proof. Let  6 1/2 the bit-flip probability of the channel. For any x, y ∈ Vn withd(x, y) = k,Pr{y received|x sent} = k (1 − )n−k ,which is maximum when k is minimum.
Francesco Buscemi

Fundamentals of Mathematical Informatics

Lecture Four

19 / 21

Summary of lecture four

Discrete memoryless channels provide a simple (but very important)model of communication channels
The coding problem is to design encoding-decoding methods thatallow the receiver to guess (with high reliability) the correct input,
avoiding errors.
The optimal decoding method is called ideal-observer decoding, but it
is not practical.
The maximum-likelihood and the minimum-distance decoding arepreferable.

Francesco Buscemi

Fundamentals of Mathematical Informatics

Lecture Four

20 / 21

Keywords of lecture four

discrete memoryless channel, binary symmetric channel, r-th extension ofa DMC, repetition codes, parity-check codes,
encoding-transmission-decoding scheme, decoding error probability,
ideal-observer decoding, maximum-likelihood decoding, Hamming
distance, minimum-distance decoding

Francesco Buscemi

Fundamentals of Mathematical Informatics

Lecture Four

21 / 21