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ε=313
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!≈nnⅇ-n2πn
n
n
n
n
2
n
(3)
we can approximate
nnε≈2n-εlog2ε-1-εlog21-ε=2n
H
b
ε
n
n
ε
2
n
ε
2
ε
1
ε
2
1
ε
2
n
H
b
ε
(4)
where
H
b
ε≡-εlog2ε-1-εlog21-ε
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
ε=2nHY-
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
2nHY-
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
nHY-
H
b
ε
n
H
Y
H
b
ε
The maximum reliable transmission rate per channel use
R=log2Mn=nHY-
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-εlog21-ε-εlog2ε+
p
x
1-1-εlog21-ε-εlog2ε=-1-εlog21-ε-εlog2ε=
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.
