If the binary symmetric channel has crossover probability
εε then if xx is
transmitted then by the Law of Large Numbers the output yy is
different from xx in
nε
n
ε
places if nn is very large.
d
H
xy≃nε
d
H
x
y
n
ε
(1)
The number of sequences of length
nn
that are different from
xx of length
nn at
nε
n
ε
is
nnε=n!(nε)!(n−nε)!
n
n
ε
n
n
ε
n
n
ε
(2)
x=000T
x
0
0
0
and
ε=13
ε
1
3
and
nε=3×13
n
ε
3
1
3
.
The number of output sequences different from
xx
by one element:
3!1!2!=3×2×11×2=3
3
1
2
3
2
1
1
2
3
given by
101T
1
0
1
,
011T
0
1
1
, and
000T
0
0
0
.
Using Stirling's approximation
n!≃nne−n2πn
n
n
n
n
2
n
(3)
we can approximate
nnε≃2n((−(εlog
2
ε))−(1−ε)log
2
(1−ε))=2n
H
b
ε
n
n
ε
2
n
ε
2
ε
1
ε
2
1
ε
2
n
H
b
ε
(4)
where
H
b
ε≡(−(εlog
2
ε))−(1−ε)log
2
(1−ε)
H
b
ε
ε
2
ε
1
ε
2
1
ε
is the entropy of a binary memoryless source. For any
xx
there are
2n
H
b
ε
2
n
H
b
ε
highly probable outputs that correspond to this input.
Consider the output vector
YY
as a very long random vector with entropy
nHY
n
H
Y
. As discussed earlier, the number of typical
sequences (or highly probably) is roughly
2nHY
2
n
H
Y
.
Therefore,
2n
2
n
is the total number of binary sequences,
2nHY
2
n
H
Y
is the number of typical sequences, and
2n
H
b
ε
2
n
H
b
ε
is the number of elements in a group of possible outputs for one
input vector. The maximum number of input sequences that
produce nonoverlapping output sequences
M=2nHY2n
H
b
ε=2n(HY−
H
b
ε)
M
2
n
H
Y
2
n
H
b
ε
2
n
H
Y
H
b
ε
(5)
The number of distinguishable input sequences of length
nn is
2n(HY−
H
b
ε)
2
n
H
Y
H
b
ε
(6)
The number of information bits that can be sent across the
channel reliably per
nn channel
uses
n(HY−
H
b
ε)
n
H
Y
H
b
ε
The maximum reliable transmission rate per channel use
R=log
2
Mn=n(HY−
H
b
ε)n=HY−
H
b
ε
R
2
M
n
n
H
Y
H
b
ε
n
H
Y
H
b
ε
(7)
The maximum rate can be increased by increasing
HY
H
Y
.
Note that
H
b
ε
H
b
ε
is only a function of the crossover probability and can not be minimized
any further.
The entropy of the channel output is the entropy of a binary random
variable. If the input is chosen to be uniformly distributed with
p
X
0=
p
X
1=12
p
X
0
p
X
1
1
2
.
Then
p
Y
0=1
p
X
0+ε
p
X
1=12
p
Y
0
1
ε
p
X
0
ε
p
X
1
1
2
(8)
and
p
Y
1=1
p
X
1+ε
p
X
0=12
p
Y
1
1
ε
p
X
1
ε
p
X
0
1
2
(9)
Then,
HY
H
Y
takes its maximum value of 1. Resulting in a maximum rate
R=1−
H
b
ε
R
1
H
b
ε
when
p
X
0=
p
X
1=12
p
X
0
p
X
1
1
2
.
This result says that ordinarily one bit is transmitted across a BSC with
reliability
1−ε
1
ε
.
If one needs to have probability of error to reach zero then one
should reduce transmission of information to
1−
H
b
ε
1
H
b
ε
and add redundancy.
Recall that for Binary Symmetric Channels (BSC)
H
Y
|
X
=
p
x
0H
Y
|
X
=
0
+
p
x
1H
Y
|
X
=
1
=
p
x
0(−((1−ε)log
2
(1−ε)−εlog
2
ε))+
p
x
1(−((1−ε)log
2
(1−ε)−εlog
2
ε))=(−((1−ε)log
2
(1−ε)))−εlog
2
ε=
H
b
ε
H
Y
|
X
p
x
0
H
Y
|
X
=
0
p
x
1
H
Y
|
X
=
1
p
x
0
1
ε
2
1
ε
ε
2
ε
p
x
1
1
ε
2
1
ε
ε
2
ε
1
ε
2
1
ε
ε
2
ε
H
b
ε
(10)
Therefore, the maximum rate indeed was
R=HY−H
Y
|
X
=ℐX;Y
R
H
Y
H
Y
|
X
X
Y
(11)
The maximum reliable rate for a BSC is
1−
H
b
ε
1
H
b
ε
.
The rate is 1 when
ε=0
ε
0
or
ε=1
ε
1
.
The rate is 0 when
ε=12
ε
1
2
This module provides background information necessary for an
understanding of Shannon's Noisy
Channel Coding Theorem. It is also closely related to material
presented in Mutual
Information.
