Духин А.А. Теория информации
Подождите немного. Документ загружается.
211
§
J.
ПРЯМАЯ
И
ОБРАТНАЯ
ТЕОРЕМЫ
ШЕННОНА
ДЛЯ
ДВОИЧНОГО
СИММЕТРИЧНОГО
КАНАЛА
EPeCe^^-Gn +
l^J
p
ra
q
n
-
ra
+(n-m
+
l)^
m
Jp
m
q
n
-
m
£
{5
.
3
.
15)
Гп*
>п-к
р
q +п
|p
m
q
n-m
;
Г
п
2
(V
Г
п
2
(V
1
1
п
+
п
'
J
|p
m
q
n-m
8°.
По условию теоремы
5.3.1:
R-C*
=
R-(l-H(p))<0.
Подберём
р,
удовлетворяющее ограничениям:
(5.3.16)
Р<Р<
А/Р
+
Л/Ч
Причём выберем
р
столь близко
к р,
чтобы выполнялось соотношение:
R-(l-H(p))<0, (5.3.17)
где
Н(р) -
непрерывная функция.
Положим
m =
пр, пренебрегая
при
этом
тем, что это - не
целая
ве-
личина.
Используем асимптотические оценки
2
:
<3
<2
Г
-2
ЕР
с
(е)£
5_ 2
nH
<P) +
п
2
nH
^>p
n
Pq
n
<
1
~P>
>ПН(Р)
В силу неравенства (5.3.17) величина
k
оценивается сверху
единицей:
t
5=2
n
(
H
<P)-
|+R
)<i.
*n-k
Ещё усилим оценку сверху для EPg(e):
EPg(e)<:(n
2
+
n
)2^<P>p
l
V<H
)
>
£
гп
2
^^^.
Логарифмируем:
feg(EP
G
(ё))
£
/og(2n
2
)
+ n(H(p)
-
(-p/ogp
-
(1
-
p)logq)).
См.
Приложение,
П.8.
212
ГЛАВА
V. ДИСКРЕТНЫЕ КЛНЛЛЫ ПЕРЕДАЧИ ИНФОРМАЦИИ
Согласно неравенству [П.11]
3
величина в скобках может быть оценена
следующим образом:
Н(р) - (-pfogp -
(1
- p)/ogq) = -А < 0,
здесь
Л
> 0. В итоге получаем:
logEFq
(ё) <
1
+ 2/ogn-nA = n(-A + 0(1)).
Следовательно, при достаточно больших п:
logE?
n
(ё) £ -А
0
п 0 < А
0
< А.
Величина средней вероятности ошибки удовлетворяет неравенству:
ЕР
е
(ё)<2~
Л
°
п
. <
5
-
3
'
18
)
Следовательно, найдется код G с параметрами пик такой, что
P
G
(E)<EP
G
(E)<2-
A
<>
n
.
Взяв п достаточно большим, можно добиться того, чтобы величина
P
G
(e) была меньше заданного числа е. А
Перейдём к рассмотрению обратной теоремы. Вновь рассмотрим схему
передачи двоичной информации по двоичному симметричному каналу:
I
• •
А
В
С
D
|
Источник
Кодер
КАКАЛ
ДЕКОДЕР
АДРЕСАТ
|
Источник
Кодер
КАКАЛ
ДЕКОДЕР
АДРЕСАТ
Рис.
3.1
Работу схемы передачи двоичной информации будем рассматривать
как преобразование исходов некоторых вероятностных схем
4
. Для
удобства будем считать, что источник информации порождает не от-
дельные символы, а блоки длины k: а =(а
19
...,а
к
),
(Х|=0,1.
Блоки по-
рождаются независимо и равновероятно. С источником свяжем вероят-
ностную схему:
,а =
(а,
а
к
),..Л
A
= i
к
..,2
(5.3.19)
Блок информационных символов а поступает в кодер, который пред-
ставляет собой некоторый преобразователь информации, осуществляю-
щий взаимно однозначное отображение <р: а->Ь, где b = (Piv>P
n
)- На
выходе кодера появляются исходы вероятностной схемы В:
3
См, Приложение, П.11.
4
На протяжении доказательства обратной теоремы кодирования полагаем основание логарифмов
а=;2.
213
§
3.
ПРЯМАЯ
И
ОБРАТНАЯ
ТЕОРЕМЫ
ШЕННОНА
ДЛЯ
ДВОИЧНОГО
СИММЕТРИЧНОГО
КАНАЛА
В
=
•>b = (P
lv
..,p
k
),...
(5.3.20)
В силу взаимной однозначности отображения
ф на
исходах схемы
В
индуцируется также равновероятное распределение. После передачи
по
каналу исхода
b = (P
lv
..,P
n
) на
выходе появляется исход
с =
(у|,...,у
п
),
вообще говоря, отличный
от b.
Выход канала описывается вероятностной схемой:
(
С
=
.,С:
(5.3.21)
D
=
:
(Yl
v?Yk)v'
••>р(с),
Вероятностное распределение {р(с)} определяется вероятностным
распределением |р(Ь)}
и
матрицей
Р
переходных вероятностей канала.
Информация
с
выхода канала поступает
на
декодер, осуществляющий
некоторое отображение множества исходов схемы
С на
множестве исхо-
дов схемы
D,
поступающих адресату
в
качестве информационных сим-
волов.
На
вероятностной схеме
D
задано некоторое распределение:
r
.,d =
(5
lv
..,8
k
),...
>
>P(d)
9
J
Средняя взаимная информация I(A;D) может быть оценена величиной
средней взаимной информации 1(В;С) согласно теореме 1.3.1:
I(A;D)<;i(B;C). (5.3.23)
В обратной теореме кодирования доказывается,
что
невозможно
на-
дёжно передавать информацию
со
скоростью, превосходящей пропуск-
ную способность канала. Превышение пропускной способности приводит
к тому,
что
вероятность ошибки передачи становится больше некоторого
фиксированного числа
е>0.
Идея доказательства сводится
к
тому,
что
вероятность ошибки передачи
Р(ё)
связана
с
величиной I(A;D),
а
сред-
няя взаимная информация 1(В;С) выражается через пропускную способ-
ность канала. Соотношение (5.3.23) позволит получить оценку снизу
для
вероятности ошибки передачи.
Теорема
3.2
(Обратная теорема кодирования
для
ДСК). Если величи-
на
R
превосходит пропускную способность канала
С*,
то найдётся постоянная величина e
0
(R,C)>0 такая,
что
при
любом способе блоковой передачи информации
со скоростью,
не
меньшей
R,
справедлива оценка:
P(e)£e
0
(R,C*). (5.3.24)
214
ГЛАВА
V.
ДИСКРЕТНЫЕ КАНАЛЫ ПЕРЕДАЧИ
ИНФОРМАЦИИ
(l-pjP/ogfl-Pjj)-
Epjj/ogpji
И
Так
как
2д>д=1,
T0
l~Pjf =ZPjf
i i
(5.3.28)
Доказательство.
Оценим снизу величину средней взаимной информа-
ции I(A;D). Доказательство теоремы разобьём
на рад
отдельных пунктов.
1°.
Занумеруем
все 2
к
входных двоичных информационных блоков
a
=
(a
Iv
..,a
k
) индексами
i =
l,...,2
k
,
а
выходные блоки
d =
(5
1
,.„.,8
k
)
ин-
дексами
j =
l,...,2
k
. Проводя нумерацию, будем присваивать одинаковым
блокам одинаковый индекс,
то
есть потребуем, чтобы выполнялось
^ = dj,
j
=
l,...,2
k
. Обозначим посредством Р(а/3)
-
вероятность того,
что был
передан блок
а, при
условии,
что к
адресату поступил блок
d.
P(e/d)
~
вероятность ошибки передачи,
при
условии,
что был
получен блок
d.
Согласно принятой договорённости
о
нумерации блоков получаем:
(аj
/
dj
}-f
|е / dj} =
Q.
Отсюда следует:
p(e/d
J
)
=
l-p(a
j
/d
j
). (5.3.25)
Вероятность ошибки передачи подсчитаем
по
формуле полной
ве-
роятности:
P(e) = £p(
3
j)P(
e/H
i).
(5.3.26)
j
2°.
Согласно свойствам средней взаимной информации (1.3.10) полу-
чаем:
I(A;D)
=
H(A)-H(A/D),
(5
3 2
7)
где H(A/D)
= £p(
d
j)
H
(
A/d
i) =
-XP(
d
j)EP^/
a
i)
fe
SP(^/
d
j)-
j J i
Введём обозначения
для
условных вероятностей:
p(a
t
/dj) =
pj,.
Тогда:
H(A/dj)
=
-Xp
ji
fogp
ji
=-Pjj/ogp
jj
-2:p
ii
/ogpj
i
=
И
=
~Pyjlog
Pjj
-
(1
-
Pjj
)l0g{\
-
p
jj)
+
215
§
3.
ПРЯМАЯ
И
ОБРАТНАЯ
ТЕОРЕМЫ
ШЕННОНА
ДЛЯ
ДВОИЧНОГО
СИММЕТРИЧНОГО
КАНАЛА
Преобразуем выражение, стоящее в квадратных скобках:
(i-Pjj)/<?g(i -Pjp-
ZPji^gPji
i
= IPji'og(l-Pjj)-IPjifogPjj =- SPji[-^0 -Pjj) +
^g
Pjj
=
I
i
i
-CI-PJD
i
1
~Pjj
°
1
"Pjj
Pji
Заметим, что У—-— = 1. Следовательно, величина, стоящая в
i1-Pjj
И
скобках, - суть энтропия некоторой вероятностной схемы с (2
k
-1) -
Pji
исходами, вероятности которых равны
1-
Pjj
Так как согласно 5-й аксиоме Хинчина энтропия не превосходит
log(2
k
-I)
5
, то получаем:
(l-pjj)/0g(1
-Pjj)- SPji/ogpjj
i
И
5(l-
Pj
j)/og(2
k
-1)<£
(1
-p
jj
)k = kp(e/d
j
). (5.3.29)
Используя формулу (5.3.25), получаем:
-
P
ii
l
°sP
jj"
О
-
Pjj)
"
P jj) =
= -(l-p(e/dj)) /og(l-p(e/d
j
))-p(e/d
j
) fogp(e/H,) =
= H(e/dj). (5.3.30)
Выражения_(5.3.29) и_(5.3.30) подставим в (5.3.28):
H(A/d,) й Ще/dj) + kp(e/dj).
5
См.
Главу
I,
§
1,
аксиома
5.
216
ГЛАВА
V.
ДИСКРЕТНЫЕ
КАНАЛЫ
ПЕРЕДАЧИ ИНФОРМА
Ц И
И
Это неравенство умножим
на p(d
J
) и
просуммируем
по j:
H(A/D)^£P(3J)
H(e/dj) + klp(dj) p(e/dj)
=
H(e/D)
+ kP(e).
j
j
Поскольку имеет место H(e/D)^H(e),
то
H(A
/
D)
<
H(e) + kP(e). (5.3.31)
Из (5.3.27)
для
средней взаимной информации получаем
неравенство:
I(
A;
D)
>
Н( А)
-
Н(е)
-
кР(е).
Так
как в
условиях вероятностной схемы
А ее
энтропия Н(А)
= к,
то:
I(A;D)
>
к -
кР(е)
-
Н(е). (5.3.32)
3°.
Оценим сверху величину средней взаимной информации
1(В;С). Так
как
ДСК
есть канал
без
памяти,
то для
любых векторов
b = (P
lv
..,P
n
)
и
с = (y
lv
..,y
n
)
имеет место:
к
p(c/b)
=
nP<VPj)
С учетом этого соотношения:
I(B;C)
=
I(b;c)
» 1(р
1;У1
) +.» + КР
п
;у
п
)
•
По определению пропускной способности
С
каждое слагаемое
l(Pi>Yi)
не
превосходит С*. Следовательно:
1(В;С)<пС*. (5.3.33)
4°.
С
учётом оценок (5.3.23)
и
(5.3.33) получаем:
k-kP(e)-H(e)<;nC*.
Отсюда:
P(
e
)+
"j~)
S
i-V
(5.3.34)
п
Из условия теоремы следует,
что
скорость передачи информации
не
меньше
R>C*.
Следовательно,
в
первой части неравенства (5.3.34)
стоит некоторая положительная постоянная £
0
(R,C)>0.
При
п ->
оо
величина
к ->
<х>,
так как в
противном случае
—
будет
п
меньше
R. Так как
величина
Н(е)
ограниченная,
то -» 0 .
к к-»оо
217
§ 3.
ПРЯМАЯ
И
ОБРАТНАЯ ТЕОРЕМЫ ШЕННОНА
ДЛЯ
ДВОИЧНОГО
СИММЕТРИЧНОГО
КАНАЛА
Отсюда приходим к выводу, что величина Р(е) ограничена снизу
некоторой постоянной e
0
(R,C). А
Прямая и обратная теоремы Шеннона для ДСК позволяют смотреть на
пропускную способность С* как на верхнюю границу скорости передачи
информации, к которой можно подойти сколь угодно близко за счёт
выбора соответствующей длины блока.
§4
Проведём доказательство прямой теоремы кодирования
для
дискретных
каналов
без
памяти (ДКПБ) согласно монографии
по
теории кодирования
1
.
Теорема
4.1.
Рассматривается дискретный канал
без
памяти
с
вход-
ным алфавитом
В =
{b
г
b
г
},
выходным алфавитом
С
=
{y
l5
...,y
s
}
и
матрицей переходных вероятностей
р
=
||P
W
||.
При
любом положительном целом значении
и и
положительном числе
R
рассматривается ансамбль бло-
ковых кодов
с
длиной блока
п, в
котором кодовые слова
выбираются независимо согласно вероятностному рас-
пределению
W(B
n
).
Тогда существует
код с
длиной
блока
п,
вероятность ошибки передачи
для
которого оце-
нивается сверху следующим образом:
Р
е
<exp{-n[vR-f
E
0
(v,W)J},
(5.4.1)
s
r
J_
где E
e
(v,W)
= -ln£ 2>kPff'
r
v
e [0Д1 W = (co
L5
...,G)
R
)5]a)
k
=1
EA
K
£ 0.
(5.4.2)
Доказательство.
1°.
Обозначим посредством
{В
п
} -
множество всех кодовых слов, которые
могут быть переданы
по
каналу связи,
и
посредством {С
п
}
-
множество
по-
следовательностей
(не
обязательно кодовых слов), которые могут быть при-
няты
на
выходе канала. Обозначим
как
р(с/Ь) вероятность того,
что на
выходе канала принято слово
с, при
условии,
что
было передано слово
Ье{В„}.
Рассмотрим фиксированный код, состоящий
из М
кодовых слов. Зануме-
руем кодовые слова рассматриваемого кода:
b
l5
...,b
M
Декодирование
производится
по
методу максимума правдоподобия. Если принято слово
с
1
См.
Библиографию
[62].
ТЕОРЕМЫ КОДИРОВАНИЯ
ДЛЯ ДИСКРЕТНЫХ КАНАЛОВ БЕЗ ПАМЯТИ
219
§
4.
ТЕОРЕМЫ
КОДИРОВАНИЯ
ДЛЯ
ДИСКРЕТНЫХ
КАНАЛОВ БЕЗ
ПАМЯТИ
P(c/b
m
)>P(c/b
m
0, _ (5.4.3)
то декодер максимального правдоподобия декодирует с в b
m
. При этом
может быть правильное декодирование, если было передано слово b
m
и бу-
дет осуществлена ошибка декодирования, если найдётся такое слово b
m
<,
что:
P(c/b
m
)^P(c/b
m
O. (5.4.4)
Вероятность ошибки передачи выражается тогда равенством:
P
m
(e)=£P(c/b
m
)V
m
(c), (5.4.5)
{с„}
где:
. если выполнено (5.4.3),
V
m
(c)
=
если выполнено (5.4.4),
Оценим сверху величину V
m
(c):
1 -iv
V
m
(c):
£р(г/ь
п
.)
p(c/b
m
O
l+v
l+v
v>0.
(5.4.6)
то есть:
a) правая часть неравенства (5.4.6) всегда положительна и, следовательно,
неравенство всегда выполняется, когда V
m
(c) = 0,
b) если V
m
(c) = l, то одно из слагаемых в числителе правой части нера-
венства (5.4.6) в силу неравенства (5.4.4) больше знаменателя, следова-
тельно, весь числитель больше знаменателя.
Подставим неравенство (5.4.6) в формулу (5.4.5):
.V
(5.4.7)
, lp(c/b
m
0
1+v
'
{B
n
}m'*m
Это неравенство справедливо для выбранного кода
{b
lv
..,b
M
}.
Если М ве-
лико,
то формулой пользоваться неудобно. Поэтому произведём усреднение
величин Р
т
(е) по ансамблю кодов, выбранному специальным образом.
2°.
Зададим на множестве всевозможных входных последовательностей {В
п
}
вероятностное распределение W(B
n
), которое определит вероятности пере-
дачи слов из того или иного кода. Вероятность выбрать код в ансамбле ко-
Pm(<0*
Др(с/Ь
т
Я
+у
220
ГЛАВА
V. ДИСКРЕТНЫЕ
КАНАЛЫ
ПЕРЕДАЧИ ИНФОРМАЦИИ
_
_ м _
дов со словами:
{b
1v
..,b
M
},
- равна J~[W(b
m
). Среда кодовых слов могут
m=l
_
быть и повторяющиеся. Распределение W(b
m
) не зависит от выбранного
кода.
Идея теоремы 5.4.1 повторяет соответствующую идею теоремы 5.3.1 для
ДСК. Поскольку в любом ансамбле кодов всегда существует, по крайней
мере, один код, вероятность ошибки декодирования для которого не больше,
чем средняя по ансамблю вероятность ошибки, то, оценивая сверху сред-
нюю вероятность ошибки, докажем существование интересующего кода.
Усредним вероятность ошибки по введённому ансамблю кодов, используя
для этого формулу (5.4.7).
_
V
EP
m
(e)5EEp(c/b
m
)l+v
1
Zp(c/b
m
-)
1+v
m
mVm
(5.4.8)
При этом случайность вносится выбором слова b
m
согласно вероятно-
стному распределению W(B
n
).
Для преобразования правой части неравенства (5.4.8) используем свойст-
ва математического ожидания:
v
EP
m
(e)SEXlKS/b
m
)l+v
1
£p(c/b
m
0
1+v
m'
mVm
= £Ep(c/b
m
)l+v
E
{«nJ
1
£p(c/b
m
<)
1+v
in
mVm
Обозначим случайную величину 2^p(c/b
m
)
1+v
посредством
Согласно свойствам математического ожидания имеем:
E£
V
<(ES)
V
,
2
2
См.
Приложение,
П.6.