Духин А.А. Теория информации

Подождите немного. Документ загружается.

201

§ 2.

ВЫЧИСЛЕНИЕ

ПРОПУСКНОЙ

СПОСОБНОСТИ

для

ДКБП

Это выражение означает, что пропускная способность равна пропускной

способности канала без шума минус потери, вызванные стиранием - q-ве-

роятность стирания.

Рассмотрим вычисление пропускной способности ДКПБ в общем случае.

Эта задача сводится к нахождению глобального максимума непрерывной

функции

1(В;С) = Н(С)-Н(С/В),

определённой на замкнутом

-мерном симплексе:

5> Р:£р|=1> Pi*0

w )

Известно, что у функции 1(В;С) существует максимум. Докажем теорему,

на которой основан метод нахождения пропускной способности канала.

Теорема

2.2. Для распределения вероятностей р = (р,,...,р

), максими-

зирующего 1(В;С), значение условной взаимной инфор-

мации I(b

;C), усредненное по вероятностной схеме С,

не зависит от входного символа b

, если р

* 0, и равно

КЬ

;0= I p

,/b

),o

P<^ = c*,

(52

13)

где С* - максимальное значение 1(В;С), то есть пропуск-

ная способность канала.

Доказательство. Без ограничения общности будем рассматривать энтропию

в натуральных единицах, принимая основание логарифмов а равным е.

Пусть в точке р =(p

..,p

)eX средняя взаимная информация 1(В;С) дос-

тигает своего максимального значения. Согласно методу неопределённых мно-

жителей Лагранжа функция 1(В;С) переменных

..,p

стационарна на ги-

перплоскости

k=l

когда г переменных удовлетворяют системе г уравнений:

а (

г Л

—[1(В;С) +

-l

] = 0 k =

l,2,...,r,

(5.2.14)

202

ГЛАВА

ДИСКРЕТНЫЕ

КАНАЛЫ

ПЕРЕДАЧИ ИНФОРМАЦИИ

где

X -

неопределённый множитель Лагранжа, вводимый уравнением связи:

9(Plv»

Pr)

l]Pk=

к=1

Из свойств выпуклости средней взаимной информации

следует, что любая

точка стационарности

1(В;С)

(точка,

которой

все

частные производные

обращаются

нуль), находящаяся внутри

£,

должна быть точкой максимума

со значением, равным наибольшему значению

1(В;С).

Почленно продифференцируем (5.2.14):

аН(С)

SH(C)dq^

» г _ 1

/ /и ч

I~^r

= -Zli+^qd

р(у^/ь

)

i +

Zp(Y//b

)^q^

Так как

Н(С/В)

= -ЁЁРкР(У^Ь

)/лр(у^ /Ь

f=lk=l

то,

дифференцируя по р

, получаем:

ЭЩС/В)

~ZP(Yf/b

)/«p(y^/b

)

;

^=1

Фк£

Подставляя вычисленные производные

формулу (5.2.14), получим:

1(В;С)

Фк

Н(С)-Н(С/В)

-1

XPOV

'K)lnq

(

+XP(Y«/b

)/«p(y

)

Xp(Y

)/;z

P(Yf/bk)

+X-l

к =

0,l,2,...,r.

f=1

Имеем:

(

y«P^>

I(b

;C).

См.

теорему

1.4.1.

203

§ 2.

ВЫЧИСЛЕНИЕ ПРОПУСКНОЙ СПОСОБНОСТИ

ДЛЯ ДКБП

Последнюю формулу можно переписать

следующем виде:

1(Ь

;С)

= С\

где С*

А,

постоянная величина.

Для завершения доказательства теоремы

5.2.2

умножим

это

равенство

на

просуммируем

по В.

Получаем:

I(b

;C)

I(B;C)

C*.

(5.2.15)

к=1

Так

как по

условию теоремы вероятностное распределение p

..,p

макси-

мизирует среднюю взаимную информацию

1(В;С),

то по

свойству выпуклости

1(В;С)

найденный максимум является пропускной способностью канала.

Таким образом,

для

распределения, максимизирующего I(b

;C), величина

условной взаимной информации

не

зависит

от к и

совпадает

пропускной

способностью канала.

Используя теорему

5.2.1,

получим Систему уравнений, решая которую

найдём точку стационарности

максимум 1(В;С).

Из формулы (5.2.13) получим:

£Р(У/

/Ь

)Р*

/*q,]= ~H(C/b

)

к =

1,...,г

(

)

Согласно соотношению (5.2.2)

= SPkP(v^

i,».,s.

к=1

Суммируя

по

множеству выходных сигналов, получаем:

S Г Г S

=ZZPkPfr<

/ b

ZPkZP^

/Ь

к) =

•

(5.2.18)

Ы\

Ы\к=\ к=1 Ы\

Выражения (5.2.16), (5.2.17), (5.2,18) задают нелинейную систему уравне-

ний

S с г

+ s +

неизвестными: Pi,...,p

; qj,...,q

;

С*.

Первые

уравне-

ний

трансцендентные,

так как

неизвестные вероятности

...

входят

под

знак логарифма. Решение введённой системы уравнений

позволяет найти

неизвестное значение пропускной способности

С* и

набор выходных вероят-

ностей,

на

которых

это

значение достигается.

(5.2.17)

204

ГЛАВА

V. ДИСКРЕТНЫЕ КАНАЛЫ ПЕРЕДАЧИ

ИНФОРМАЦИИ

Предположим, что в результате решения системы ни одна из вероятностей

входных символов не оказалось отрицательной. Тогда значение средней взаим-

ной информации

1(В;С),

вычисленное для этих вероятностей, даст величину

пропускной способности. Предположим противное, что среди вероятностей

входных символов при решении системы S, по крайней мере, одна оказалась

отрицательной. Это означает, что непрерывная функция

1(В;С)

переменных

р,,...,р

принимает своё максимальное значение на границе симплекса £.

Для нахождения точки максимума последовательно приравнивают аргументы

к нулю:

0,р

..,p

0,р

0,...,р

* 0; и так далее.

Рассматривают функцию

1(В;С)

от г-1 переменного. Каждый раз

определяют решение системы S, задаваемое уравнениями (5.2.16), (5.2.17),

(5.2.18),

и подсчитывают значение

1(В;С).

Наибольшее приемлемое из

полученных таким образом значений

1(В;С)

является пропускной

способностью канала. Не существует никакого простого способа определения,

какой из символов р

должен быть исключён. Поэтому, вообще говоря,

приходится рассматривать г систем уравнений.

Если при последовательном исключении р

1,...,г

при решении каж-

дой из систем будут получаться отрицательные значения вероятностей вход-

ных символов, то следует исключать пары р

р^, то есть рассматривать ое-

(Л

шения систем S.

Среди множества допустимых решений выбрать максимальное значение

1(В;С),

которое и будет пропускной способностью. Если при последователь-

ном исключении пар

{р

рЛ

всякий раз при решении будут получаться отри-

цательные значения вероятностей, то следует перейти к исключению всевоз-

можных троек, четвёрок и т.д. Рассмотренная процедура обязательно приведёт

к нахождению максимума

1(В;С)

на симплексе £ по свойствам непрерывных

функций, заданных на замкнутом множестве.

В заключение параграфа рассмотрим частный случай канала связи. Пусть

г = s и матрица переходных вероятностей Р невырождена, то есть у нее су-

ществует обратная

Q = Р

= =

= 1

»—>

' (5.2.19)

где п

кг

- алгебраическое дополнение элемента р(У

/Ь

)

ке

205

§ 2.

ВЫЧИСЛЕНИЕ

ПРОПУСКНОЙ

СПОСОБНОСТИ

ДЛЯ

ДКБП

Перепишем первые s уравнений (5.2.16) системы S в матричной форме:

+ /nq,

,H(C/b

)

;

(5.2.16')

Умножая (5.2.16') на Q, получаем:

+lnq

H(C/b

)

-Q

,H(C/b

);

Выделим

£ -ю

строку:

C*+/«q

-]Tq^H(C/b

(5.2.20)

k=l

Рассматривая соотношение (5.2J20) как равенство показателей, напишем

равенство для степеней с основанием е:

=е

k=1

(5.2.21)

Суммируя равенства (5.2.21) по ^ = l,...,s, получаем:

ы\ ы\

Следовательно, пропускная способность рассматриваемого канала связи

равна:

-£qflcH(C/b

)

(5.2.22)

Вероятностное распределение, на котором достигается пропускная спо-

собность, находится из соотношения:

(Piv..,p

)

(qiv..,q

)Q,

где

q,,...,q

определяются из формулы (5.2.21):

s ,

-2>«н<с/ь,)

=е 2>

i=sl

««*

(5.2.23)

(5.2.24)

§3

См. Библиографию [77].

ПРЯМАЯ И ОБРАТНАЯ ТЕОРЕМЫ ШЕННОНА

ДЛЯ ДВОИЧНОГО СИММЕТРИЧНОГО КАНАЛА

В прямой теореме будет доказано, что при скорости передачи информации

по ДСК меньше пропускной способности, возможна сколь угодно надёжная

связь, то есть вероятность ошибки декодирования может быть сделана меньше

любого наперёд заданного числа, путём выбора достаточной длины кодового

слова.

Доказательство приведём согласно Шоломову

. Прямую теорему докажем в

следующих предположениях. Для кодирования используем систематические

(п,

к)-коды.

Последовательные сигналы, поступающие на вход канала, предпо-

лагаются независимыми. Декодирование осуществляется по методу макси-

мального правдоподобия. Так как порождающая матрица таких кодов имеет

вид:

= (E

|p)> kxn, (5.3.1)•

то различных систематических кодов будет

2*"~

k)k

по числу различных мат-

риц Р.

Лемма 3.1. Пусть a = (a

..,a

) - ненулевой вектор из V

(GF(2)). Тог-

да существует не более

1)(n

кодов рассматриваемого

типа, в которых может содержаться рассматриваемый

вектор.

Доказательство.

a) Пусть первые к компонент вектора а нулевые: a

..,a

=0, а среди ос-

тальных n - к компонент имеются ненулевые. Тогда а - не кодовый вектор

и, следовательно, нет кодов, содержащих его. Оценка выполняется три-

виальным образом.

b) Пусть среди к первых компонент имеется хотя бы одна ненулевая. Для оп-

ределённости оц^О. Всякий систематический код G, содержащий а, мо-

жет быть задан (к -1) строкой порождающей матрицы G и самим векто-

ром а. Действительно, будем рассматривать а в качестве i -й строки мат-

рицы:

207

ПРЯМАЯ

ОБРАТНАЯ ТЕОРЕМЫ

ШЕННОНА

ДЛЯ

ДВОИЧНОГО

СИММЕТРИЧНОГО

КАНАЛА

<*.

а»

k+J

... a

,°

0 1 Pkl

Pkn-k>

Линейными комбинациями остальных строк матрицы получим

-ю компо-

ненту, равную единице, остальные первые

к-1

компонент сделаем нену-

левыми.

Так

определяется

-я строка порождающей матрицы. Остальные

(к-1) строк можно выбрать произвольно.

Это

можно осуществить

2(k-t)(n-k)

спосо

бами. Каждая такая матрица порождает систематический

(п,к)-код, содержащий вектор

а. А

Теорема 3.1 (Теорема кодирования для ДСК):

Для

любого числа

мень-

шего пропускной способности

С*, и

любого

> 0 сущест-

вует такой систематический линейный

код с

длиной блока

п(е) со

скоростью передачи,

не

меньшей

—

= R, у

которо-

го вероятность ошибки

р(е) не

превосходит

е.

Доказательство. Для удобства выделим ряд отдельных утверждений.

1°.

Пусть

k =

nR. Мы будем пренебрегать величиной

х> где

k + x

]nR[.

Ве-

личина

больших

будет пренебрежительно мала. Рассмотрим мно-

жество всех линейных систематических

(n,k)-кодов

докажем,

что

сред-

няя

по

этому множеству вероятность ошибки декодирования стремится

нулю

при

—>

оо.

Поскольку минимальная вероятность ошибки

для

кодов

из этого множества

не

больше средней,

то тем

самым будет установлено

существование кодов со сколь угодно малой вероятностью ошибки.

2°.

Пусть

G -

систематический (п,к)-код. Обозначим

как

(ё)

вероят-

ность ошибки передачи при использовании этого кода. Эта ошибка передачи

получается

в том

случае, когда

канале

на

передаваемое слово воздейст-

вует ошибка

= (e

..,e

)

при декодировании

на

выходе декодера кодо-

вое слово оказывается отличным

от

переданного.

Согласно формуле полной вероятности:

(ё)

= Хр(г)р

(ё7ё),

(

-2)

где

Ре(ё) -

вероятность того,

что в

канале произошла ошибка

(8j,.,.,e

Рс(ё/в)

вероятность декодирования

слово, отличное

от

переданного.

208

ГЛАВА

ДИСКРЕТНЫЕ КАНАЛЫ ПЕРЕДАЧИ

ИНФОРМАЦИИ

3°.

Осуществляем декодирование

ближайший кодовый вектор. Пусть переда-

вали кодовое слово

aeG и

произошла ошибка

ё.

Принятый вектор

= а + ё

будет декодирован неправильно, если существует кодовое слово

а'

такое,

что у = а

ё = а' + ё', и при

этом W(e)> W(e').

силу линей-

ности кода

G a-fa' = e +

€G. Следовательно, ошибка передачи

при

ошиб-

ке

канале

может возникнуть только тогда, когда существует вектор

г'

ё,

удовлетворяющий условиям:

ё + ё'

€

W(e')£W(e).

33)

Обозначим

как

1Ч(ё)

число всех таких векторов

ё'.

Справедлива оценка:

(e/e)^N

(e).

(5.3.4)

Если N(e)

= 0, то

таких векторов

нет, и, при

Р(ё/ё)

= 0,

ошибки декоди-

рования

не

возникают. Если

же

N(e)

то

неравенство

(5.3.4)

выполняет-

ся тривиальным образом.

Рассмотрим m

€

N, m

—

представим формулу

(5.3.2)

следующем

виде:

W)*

EP<e)N

(e)+ Ер(ё)Рб(е/ё)>

(5.3.5)

ё|\У(ё)<т

e|W(8)>m

4°.

Пусть Ер

(ё)

средняя вероятность ошибки

по

всем систематическим

ли-

нейным (n,k)-кодом. Следовательно,

ВД=т^Е

о(ё)^тй(ЬоЕ

Урооадн

Тт-

(5.3.6)

]GJ

{G}E:{W(E)^M}

E:{W(E)>M}

-ГЕ5=Е7

, I

Р(ё>5Х(ё)

£р(ё).

E:{W(E)^M}

{G}

E:{W(I)>M}

5°.

Оценим сумму ^Ng(s)

при

заданном

ё.

Пусть W(e)

Рассмотр]

им

произвольный отличный

от ё

вектор

ё'.

Пусть

его вес

W(e)

= i

Сог-

ласно лемме

5.3.1

ненулевой вектор

ё'

принадлежит

не

более

чем

2(k~i)(n-k)

систематическим К

одам. Вектор

ё'

даёт вклад

сумму ^Г[Ч

(ё),

не превосходящий

1)(n

Общий вклад

сумму векторов, веса

i, не

(

превосходит

дения для всех

i й

получаем оценку:

t так как

самих

векторов

Проводя рассуж-

209

ПРЯМАЯ

ОБРАТНАЯ

ТЕОРЕМЫ

ШЕННОНА

ДЛЯ

ДВОИЧНОГО

СИММЕТРИЧНОГО

КАНАЛА

e)<i:

(к

,)(п

к)

(5.3.7)

6°.

Вероятность р(е) ошибки е веса j в двоичном симметричном канале

равна

pd) = p

q"-

Следовательно, для первой суммы в формуле (5.3.6) получаем:

£ p(6)2>

(e)<;

5:{w(E)Sm}

j<;

hSjVV

<k-l)(n-k)

(5.3.8)

n n f

Так как i < j

m < -, то при i <

—

с ростом i величина I

возрастает,

2 2 ^ *

то есть

<, и, следовательно:

(5.3.9)

Так как i + l£m + l£n, следовательно, для первого слагаемого в оценке

(5.3.6) получаем:

P(g)lN

(e)^n2(

-^-

e:{\V(E)^m}

6 \йт

Аналогично оцениваем второе слагаемое в формуле:

E:{W(E)>m}

j>mVJy

j^mVJ/

Подставим оценки (5.3.10) и (5.3.11) в формулу (5.3.6):

EPo(e)^Zf:TpV-^lf:W-

(5.3.10)

(5.3.11)

(5.3.12)

7°.

Выберем параметр m таким образом, чтобы в первой сумме формулы

(5.3.12) последнее слагаемое было максимальным, а во второй сумме

первое слагаемое было максимальным. Составим отношение для первой

суммы последующего j

-го

слагаемого к j -1 -му предыдущему:

210

ГЛАВА

V. ДИСКР ЕТНЫЕ КАНАЛЫ ПЕРЕДАЧИ

ИНФОРМАЦИИ

' п ^

pj-y-j+J

(n-j + 1)

(n-j)

•2

~ -2 '

j q j q

Потребуем, чтобы было выполнено:

(n-j)

Отсюда получаем неравенство (n -

J)VP

^ iVi

•

из

которого следует:

л/p+Vq'

Получаем первое ограничение на m:

л/р"

m <п

Vp+Vq'

(5.3.13)

Аналогично поступаем со слагаемыми второй суммы:

И;

(j+i)q Jq

Из условия, что ——— < 1, находим, что j

пр + q = пр.

Это приводит ко второму ограничению на т:

т > пр. (5.3.14)

Убедимся, что условия (5.3.13) и (5.3.14) непротиворечивы, то есть су-

ществуют такие m, которые удовлетворяют (5.3.13) и (5.3.14):

_V?L_

Е >-

-=р.

Vp+Vq p+VpVq p+q

Следовательно, неравенство (5.3.13) и неравенство (5.3.14) могут быть

удовлетворены одновременно. Предположим, что m удовлетворяют

одновременно двум неравенствам (5.3.13) и (5.3.14). Тогда из оценки

(5.3.12) получим: