Channel Coding
1
Binary entropy function
H(p)
H ( X ) = − p log p − (1 − p) log(1 − p)
H=0: no uncertainty
H=1: most uncertainty
1 bit for binary information
Probability p
2
Mutual information
• Two discrete random variables: X and Y
I ( X ; Y ) = P[ X = x, Y = y ]I ( x, y )
P[ x | y ]
= P[ X = x, Y = y ] log
P[ x]
P[ x, y ]
= P[ X = x, Y = y ] log
P[ x]P[ y ]
• Measures the information knowing either variables
provides about the other
• What if X and Y are fully independent or dependent?
3
I ( X ;Y ) = H ( X ) − H ( X | Y )
= H (Y ) − H (Y | X )
= H ( X ) + H (Y ) − H ( X , Y )
4
Some properties
Entropy is maximized when probabilities are equal
5
Joint and conditional entropy
• Joint entropy
H ( X , Y ) = P[ X = x, Y = y ] logP[ X = x, Y = y ]
• Conditional entropy of Y given X
H (Y | X ) = P[ X = x]H (Y | X = x)
= − P[ X = x, Y = y ] log P[Y = y | X = x]
6
Joint and conditional entropy
• Chain rule for entropies
H ( X 1 , X 2 , , X n ) = H ( X 1 ) + H ( X 2 | X 1 ) + H ( X 3 | X 1 , X 2 )
+ + H ( X n X 1 , X 2 ,, X n−1 )
• Therefore,
n
H ( X 1 , X 2 ,, X n ) H ( X i )
i =1
• If Xi are iid
H ( X 1 , X 2 ,, X n ) = nH ( X ) 7
Lossless coding of information source
• Source sequence with length n
n is assumed to be large
x = [ X 1 , X 2 ,, X n ]
X = {x1 , x2 ,, xL }
pi = P[ X = xi ]
• Without any source coding
we need log L bits per symbol
8
Lossless source coding
• Typical sequence
– Number of occurrence of xi is roughly npi
– When n → , any x will be “typical”
L N
log P[ x ] log ( pi ) npi = npi log pi = − nH ( X )
i =1 i =1
P[ x ] 2− nH ( X ) All typical sequences have
the same probability
P[ x ] → 1 when n →
9
Communications Channel
• Channel: source of randomness (interference,
fading, noise, etc.).
• Random nature of the channel is described by
a probability distribution over the output of
the channel.
• That distribution will often be dependent on
the input chosen to be transmitted.
• Discrete case: Both input and output symbols
belong to a finite alphabet.
10
Discrete Channel
• If we apply a sequence x1, x2, . . . , xn from an
alphabet X at the input of a channel, then at the
output we will receive a sequence y1, y2, . . . , yn
belonging to an alphabet Y .
• Usually the probability distribution over the
outputs depend on the input and on the state of
the channel.
• Some channels have memory. For example, the
output symbol yn might be dependent on
previous inputs or outputs.
• Causal behavior: In general y1, y2 , . . . , yn do not
need to consider inputs beyond x1 , x2, . . . , xn .
11
Discrete Channel
• Given an input alphabet X , an output alphabet Y and a
set of states S , a discrete channel is defined as a
system of conditional probability distributions
P (y1, y2, . . . , yn |x1, x2, . . . , xn ; s)
where x1, x2, . . . , xn ∈ X , y1, y2, . . . , yn ∈ Y and s ∈ S
• P (y1, y2, . . . , yn |x1, x2, . . . , xn; s) can be interpreted
as the probability that the sequence y1, y2 , . . . , yn
will appear at the output of the channel if the
sequence x1, x2, . . . , xn is applied at the input and the
initial state of the channel is s.
• Initial state here is defined as the state before applying
x1 at the input.
12
Discrete Memoryless Channel
• A discrete channel is memoryless if
P (y1 , y2 , . . . , yn |x1 , x2 , . . . , xn ; s)
does not depend on s so it can be written
as P (y1 , y2 , . . . , yn |x1 , x2 , . . . , xn )
• P (y1 , y2 , . . . , yn |x1 , x2 , . . . , xn ) = P (y1
|x1 ) P (y2 |x2 ) . . . P (yn |xn ).
where x1 , x2 , . . . , xn ∈ X , y1 , y2 , . . . , yn
∈ Y and s ∈ S .
13
Information Processed by a Channel
• Let the input uncertainty be H (X ), H (Y ) is the output
uncertainty and the conditional uncertainties H (X |Y ) and H (Y
|X ). We define the information processed by the channel as
I (X ; Y ) = H (X ) − H (X |Y ) = H (Y ) − H (Y |X )
• The information processed by a channel depends on the input
distribution pX (x).
• We may vary the input distribution until the information
reaches a maximum; the maximum information is called the
channel capacity.
C = max I (X ; Y ).
pX (x)
14
Properties of Channel Capacity
• Properties of channel capacity
➢ C ≥ 0, since I (X ; Y ) ≥ 0.
➢ C ≤ log |X |, since C = max I (X ; Y ) ≤ max H (X ) =
log |X |
➢ C ≤ log |Y |, for the same reason.
➢ I (X ; Y ) is a continuous function on pX (x).
➢ I (X ; Y ) is a concave function of pX (x).
• Global maximum.
15
Classification of Channels
• A channel is lossless if H (X |Y ) = 0 for all input
distributions.
• Input is determined from the output and no
transmission errors can occur.
• A channel is deterministic if P (Y = yi |X = xj ) = 1 or 0
for all i, j. The output is determined by the input, that
is, H (Y |X ) = 0 for all input distributions.
• A channel is noiseless also lossless and deterministic.
• A channel is useless (or zero-capacity) if I (X ; Y ) = 0 for
all input distributions. Input X and output Y are
independent.
16
Symmetric Channel
• A channel is symmetric if the rows of the channel transition matrix
are permutations of each other, and the column are permutations of
each other
1/3 1/3 1/6 1/6 ]
P (Y |X ) = [
1/6 1/6 1/3 1/3
1/ 2 1/ 3 1/ 6
P (Y |X) = [ 1/6 1/2 1/3 ]
1/3 1/6 1/2
• The entry at the i-th row and j-th column denotes the conditional
probability P (Y = y j |X = x i ) that y j is received given that x i was
sent.
Symmetric Channel
• A channel is weakly symmetric if the rows of the channel
transition matrix are permutations of each other, and
the sums of the columns are equal.
1/3 1/2 1/6
P (Y |X ) =
1/3 1/6 1/2
Channel models and channel capacity
• Channel models
input sequence x = ( x1 , x2 , , xn )
output sequence y = ( y1 , y2 , , yn )
A channel is memoryless if
n
P[ y | x ] = P[ yi | xi ]
i =1
19
Binary symmetric channel (BSC) model
Source Output
data data
Channel Binary Demodulator Channel
Channel
encoder modulator and detector decoder
Composite discrete-input discrete output channel
20
Binary symmetric channel (BSC) model
1-p
0 0
p
Input Output
p
1 1
1-p
P[Y = 0 | X = 1] = P[Y = 1 | X = 0] = p
P[Y = 1 | X = 1] = P[Y = 0 | X = 0] = 1 − p
21
Binary Erasure Channel
• Bits are lost instead of being flipped.
• A fraction α of bits is lost and the receiver
knows that a bit was supposed to arrive.
• Packet communications
P (Y |X ) =
22
Discrete memoryless channel (DMC)
{X} {Y}
Input x0 y0 Output
x1 y1
…
xM-1
…… P[ y | x ]
can be arranged
yQ-1
in a matrix
23
Why the channel capacity is important?
• Shannon proved that the channel capacity
is the maximum number of bits that can
be reliably transmitted over the channel.
• Reliably = probability of error can be made
arbitrarily small.
24
Channel Capacity
• Noiseless Binary Channel
➢ One error-free bit can be transmitted per use of the channel.
➢ C = 1 bit, and is achieved with uniform input distribution.
• Lossless channel
➢ Input can be determined from the output. Every transmitted
bit can be recovered without error.
➢ For our example, C = 1 bit, and is achieved with uniform input
distribution.
• Noisy Typewriter
➢ Channel input is either received unchanged at the output with
probability 1/2 or it is transformed to the next letter with
probability 1/2. That is, if A is transmitted, we can receive A or
B. Each with probability 1/2.
➢ Input has 26 symbols. If we use alternate input symbols (A, C,
E), we can transmit 13 symbols without error.
C = max H (Y ) − H (Y |X ) = max H (Y ) − 1 = log 26 − 1 = log 13.
25
Channel Capacity for BSC
• Bounding the mutual information for the BSC:
I(X; Y ) = H(Y ) − H(Y |X)
= H(Y ) −ΣH(Y |X = x)pX(x)
= H(Y ) −Σ H(p)pX(x)
= H(Y ) − H(p)
≤ 1 − H(p)
• Equality is achieved when the input distribution is
uniform.
C = 1 − H(p)
26
Channel Capacity for BEC
• C = 1 − α.
• This result is somewhat intuitive: since a
fraction α of the input bits is erased, we can
recover (at most) 1 − α of the bits.
27
Channel capacity
• Capacity for abitray discrete memoryless channel
C = max I ( X ; Y )
p
• Maximize mutual information between input and
output, over all p = ( p1 , p2 , , p X )
• Shannon’s Second Theorem – noisy channel coding
- R < C, reliable communication is possible
- R > C, reliable communication is impossible
31
Channel capacity
1
For binary symmetric channel P[ X = 1] = P[ X = 0] =
2
C = 1 + p log 2 p + (1 − p) log 2(1 − p) = 1 − H ( p)
32
Channel capacity
Discrete-time AWGN channel with an input
power constraint
Y = X +N E[ X ] P
2
For large n,
1 2
y → E[ X 2 ] + E[ N 2 ] P + 2
n
1 1 2
y − x = n → 2
2
n n
33
Channel capacity
Discrete-time AWGN channel with an input
power constraint
Y = X +N E[ X 2 ] P
Maximum number of symbols to transmit
( n( P + ) )
n
2 n
P
M= = (1 + )
( n )
2
2
n
2
Transmission rate
1 1 P Can be obtained by directly
R = log 2 M = log 2 (1 + 2 ) maximizing I(X;Y), subject to
n 2 power constraint 34
Channel capacity
Band-limited waveform AWGN channel with
input power constraint
- Equivalent to 2W use per second of discrete-
time channel
P
1 2W 1 P
C = log 2 (1 + ) = log 2 (1 + ) bits/channel use
2 N 0 2 N 0W
2
1 P P
C = 2W log 2 (1 + ) = W log 2 (1 + ) bits/s
2 N 0W N 0W
35
Channel capacity
P
C = W log 2 (1 + )
N 0W
P→ C →
P
W → C → 1.44
N0
36
38