книги из ГПНТБ / Бовбель, Е. И. Элементы теории информации
.pdfI
Подставляя (4.4) и (4.5) в (4.3), получаем
/(Z , У) = lim
М-СО
MH{Z) — МН(Zf У) |
= 4 [H(Z)-H(Z;Y)\. |
М т |
|
По формуле (4.2) пропускная способность
Сс = 4 п1ах[H(Z) - H(Z/Y)].
Разность H(Z) — Ii(Z/Y) максимальна, когда максималь на энтропия H(Z) и минимальна энтропия H(Z/Y). Но ус ловная энтропия H(Z/Y) зависит только от статистики пе редаваемых сигналов (Po и Р\) и статистики шумов, дей ствующих в линии связи (Р{ и Р п ), которые по условию задачи заданы. Поэтому разность H(Z) — H(Z/Y) макси мальна, когда максимально первое слагаемое; энтропия H(Z) максимальна, когда P(ZQ) = P(Z)i и равна Ii(Z) = 1.
Таким образом,
Cc = 4 [ l - t f ( Z / y ) ] . |
(4.6) |
Вычислим энтропию H(Z/Y) по формуле
H{ZY) = - 2 2 р & ь У]) l°g Р ^ ' У ) ) -
/=0 ;=О
По формуле полной вероятности и теореме умножения
P(Zo) = 2 |
P(Zо, yj) = |
P(Z0, у0) + P(Z0, у,) = |
||
|
;=о |
|
|
|
|
= Р(Уо) P ( Z o ly 0) + Р ( У і ) - Р Р М = |
|||
= Р(Уо)[1 - |
P(Zt/y0)] + Р Ш Р & в!уі) = |
Яо(1 - Р и) + Р ^ г |
||
|
|
|
|
I |
P ( Z i ) |
= 2 |
P ( z 1. yj) = P ( Z u У0) + P { Z X. Уі) = |
||
|
j=o |
|
|
|
= |
P(yо) P(Zb Уо) + |
P(y,)[l - |
P(Zo!yi)] = |
|
|
|
= P0P 1I + |
P1( 1 - P 1). |
|
Подставляя полученные выражения в условную энтро пию, будем иметь:
H(Z y) = —P{Z0, уо) log P(Z0!y0) — P(Zt, |
ijo) log PfZt/y0) — |
— P(Z0, yi) log P(Z0 'yi) — P{Zl, i/i) log PtZi/y,) = . |
|
= — P(Z0, г/o) log [1 — P (Zj/Уо)] - P(Z„ |
y0) log P(Zi/y0) — |
•90
- P(Z0, ІЯ) log P(Z0/Уі) - P(Zlt y t) log [ 1 - P(Z0'yl)] =
« - |
PoV - Prf log (1 - P n) - P0P n log P ,, = |
|
|
= — P \P Xlog p |
P i (1 — Pj) log (1 — P,). |
(4.7) |
|
Наконец, подставим выражение (4.7) в (4.6): |
|
||
сс= 4 т і |
+ р0о - |
P i^ o g o - P iij + PoPniogp,, + |
|
+ P,Pi log Р , - р . (1 - р . ) log ( і - р , ) ] . |
(4.8) |
||
Задача 2. В условиях предыдущей задачи определить пропускную способность симметричной линии связи, в ко торой Р { = Л , = Яоиі=І/2. Объяснить полученный резуль
тат.
Р е ш е н и е . Подставим в формулу (4.8) предыдущей задачи Р{ = Рі{ = Л>ш:
= 4 [1 + (1 — Рош)lo g (1 — Рош) + РошlogP 0,„]. (4.9)
Из (4.9) видно, что с ростом Рош от 0 до 0,5 пропускная способность Сс монотонно убывает от своего максималь
ного значения, равного до 0. Результат Сс= 0 при
Pqui -0,5 станет очевидным, если заметить, что равенства
^ош ^ |
Р(^оіУі) = Р(^о;Уо) = 0*5; |
|
Рош” |
Р{%і!Уо) = Р(^і!Уі) —0)5 |
(4.10) |
1 |
|
сигналы |
показывают, что передаваемые и принимаемые |
||
полностью статистически независимы (см. задачу 2 § 3 гл. 1). При этом, как нам известно, количество получае мой информации равно нулю. Иначе говоря, приняв, к примеру, сигнал Z\ (см. 3.46), мы с равной вероятностью можем утверждать, что был передан сигнал у\ либо сиг нал і/0. Эти утверждения имеют такую же ценность, как если бы передача сигналов вовсе прекращалась и мы принимали решение о передаче того или иного сигнала по результатам бросания монеты.
Задача 3. В памяти ЭВМ накоплено 10е двоичных еди ниц информации. Для ее передачи используют двоичную симметричную линиюсвязи. Техническая скорость пере дачи в линии связи V =500000 бит/с, а вероятность ошиб ки Рош= 0,0035. -Найти минимальное время передачи на копленной в ЭВМ информации.
9
91
Р е ш е н и е . Как следует из решений двух предыду
щих задач, |
максимальное количество информации, |
несо |
|
мое одним |
двоичным символом, |
передаваемым по сим |
|
метричной линии связи: |
|
|
|
Лшх = 1 |
-Г Рот log Рот + (1 — |
Рот ) lo g (1 — Я 0ш) |
= |
= 1 + 0,0035 log 0,0035 -Ь 0,9965 log 0,9965 = 0,966 (бит). '
При этом максимально возможная скорость передачи
С = ^ /тач = 500000-0,966 = 483000 (бит/с).
Искомое время передачи |
|
|
/ . — |
юс |
2 07 (с) |
_ = |
||
m,n |
483000 |
' |
Заметим, что в отсутствие шумов / тах = 1, С = ѵ и / П]іп =
= 2с.
>
§ 3. Теоремы о кодировании в присутствии шумов
Теорема 1 (К. Шеннон). Если поток информации Н(Х), создаваемый источником,
Н ( Х ) = С с— г, |
, |
(4.11) |
где г 'может быть как угодно малым положительным числом, то существует такой код, при котором вероятность ошибок на приемном конце сколь угодно мала.
Д о к а з а т е л ь с т в о . Входные сообщения линии свя зи будем обозначать буквой я, а выходные — буквой у.
Пусть Hq(X), Ho(Y), H(X/Y) — безусловные и условный потоки информации, при которых достигается максималь ная скорость передачи Сс линии связи. Как мы знаем (сім. § 2 гл. 2), при эргодическом характере входных и вы ходных сообщений линии связи о количестве соответству ющих последовательностей сообщений достаточно боль шой длительности Т можно утверждать следующее:
1) число входных последовательностей (типичных)
линии связи приолизительно равно 2 ; 2) число выходных последовательностей (типичных)
линии связи приблизительно равно 2 ///()) ;
3) каждая выходная типичная |
последовательность |
могла произойти примерно от 2 |
входных последо |
вательностей линии связи; |
|
4) каждой входной типичной последовательности соответствует около 2 01 выходных последовательно стей линии связи.
При Т= со утверждения 1—4 становятся точными. На рис. 5 входные последовательности представлены точками слева, а выходные — точками справа. Расходящиеся ли нии («веер») наверху изображают ряд возможных случа ев для типичного выходного эффекта. Нижний «веер»
представляет возможные |
г" |
• |
|
|
|||||
случаи |
для |
типичного |
|
‘g |
|||||
входного эффекта. В обо |
I |
|
|
||||||
их |
примерах |
отброшены |
п |
|
|
||||
нетипичные |
|
последова |
|
|
|||||
|
г. Т Н 0 (А/у/ в о з м о ж н ы х |
||||||||
|
причин для каждого уу |
||||||||
тельности. |
|
|
|
||||||
Пусть по той же линии |
J |
|
|
|
|||||
связи передается информа |
|
|
|
||||||
ция со скоростью на вхо- |
S |
|
|
||||||
де_ Н(Х) = Сс =Н^(Х) — |
|
|
|||||||
—Hq(X/Y). При этом чис |
I |
|
|
|
|||||
ло |
типичных |
отправля |
2• hо 'У/**бозложных |
||||||
емых сообщений длитель |
Чэ |
следстбии для каждого Х[ |
|||||||
|
|
|
<г |
||||||
ностью |
Т |
будет |
равно |
|
|
|
|||
|
|
|
$ |
||||||
2™(х) < |
2™о{Х) |
|
|
|
|
|
|||
Для отыскания средней |
|
|
|
1 |
|||||
|
|
|
В |
||||||
вероятности |
ошибки вос |
|
|
|
.А |
||||
|
|
|
К |
||||||
пользуемся |
|
с л у ч а й |
|
|
|
<N1 |
|||
ным |
к о д и р о в а н и - |
|
|
|
|
||||
е м. |
При |
таком |
коди |
|
|
|
|
||
ровании |
выбор |
определенного |
кода |
состоит в указа- |
|||||
ним того, какие именно |
из 2™о{Х) |
возможных после |
|||||||
довательностей выбираются в качестве 2 Г/ /(Х) |
разрешен |
||||||||
ных |
к |
отправке |
и как |
разбиваются на |
2 ГЯ(Х) под- |
||||
групп 2 выходных последовательностей. Рассмотрим класс всевозможных кодов, которые получатся, если
2™{Х) разрешенных последовательностей размещать
случайным образом среди 2 ТН(X).возможных типичных последовательностей.
Вероятность того, что заданная последовательность на выходе линии связи не попадет в число разрешенных, равна
93
|
2 THt(X) |
|
Пусть |
мы приняли |
последовательность у у. Ей соответст- |
вует |
(см. рис. 5) 2 |
' возможных точек верхнего |
«веера». Вероятность того, что ни одна точка «веера» не
будет разрешенной последовательностью (кроме одной |
||
действительно отправленной), будет равна |
|
|
р _ £j |
2ПЯ(А-)~Д,(Л')] j (2ТИ^ХІѴ) - 1) |
(4.12) |
|
|
|
Это и есть вероятность безошибочного приема. Из |
(4.11) |
|
с учетом того, |
что Н(Х)<ССс = Н$(Х)— H0(X/Y), |
имеем |
H ( X ) - H 0( X ) = - H 0( X / Y ) - s . |
(4.13) |
|
Подставляя |
(4.13) |
в |
(4.12), получаем |
|
Р |
= |
1 [ |
-9-г//в(.Ѵ/П-* |
„ n T IfQ(XiV) |
тг |
||||
Прологарифмируем обе части последнего равенства и вы числим предел"
lim |
log Р = |
lim [2г/Уо(Л }) |
log (1 |
2-Г(л/„(ЛѴ)-н-0п |
||
Т-г оо |
с |
оо |
|
|
|
|
lim |
H«WV) + * |
|
,-T t |
= 0, . (4.14) |
||
1_ 2- і а д і)+ гі’’ |
||||||
T-rOO |
I MXj Y) |
|
||||
откуда lim P — 1. Таким образом, |
при случайном кодиро- |
|||||
|
Г-.00 |
|
|
|
|
|
вании достаточно длительных последовательностей сооб щений средняя вероятность ошибки как угодно мала.
Так как равенство (4.14) справедливо при любом ма лом е > 0 , поток информации в (4.11) может быть как угодно близок к пропускной способности линии связи, что придает особый смысл понятию пропускной способности: пропускная способность — это максимально возможная скорость передачи, при которой еще возможна передача со сколь угодно малой вероятностью ошибки.
Теорема 2 (К. Шеннон). Если поток информации, соз даваемый источником, H(X) — Cc — s, где s > 0 , то сре ди кодов, обеспечивающих сколь угодно малую вероят ность ошибки, существует код, при котором скорость пе редачи информации
Д о к а з а т е л ь с т в о . Для |
доказательства теоремы |
||||
достаточно показать, что скорость передачи |
|||||
I = lim |
І(Х т, ) |
Н(ХТ ) |
lim |
Н{ХТ І Г Т) |
|
Т |
= lim |
т |
т |
||
г—°о |
Т-+ °0 |
г - оо |
|||
|
= ЩХ) — lim |
H( XT I Y T ) |
|
||
|
|
Т |
|
||
|
|
Т-> оо |
|
|
|
будет максимальна и равна Н(Х), если среди кодов, обе спечивающих сколько угодно малую вероятность ошибки, существует код, для которого
lim |
H( XT/ Y T) |
(4.15) |
|
'1 |
|||
'/-►00 |
|
где Х тн Yf — соответственно входная и выходная после довательности линии связи длительностью Т.
Заметим, что H(XTIYт) есть та неопределенность, ко торая остается после приема последовательности УѴ* Чтобы снять эту неопределенность, необходимо распо лагать дополнительным количеством информации, чис ленно равным H(XTIYT), на каждую последовательность YT. Это количество информации состоит из двух слагае
мых: количества информации, необходимого для того, что бы установить, совершена ли ошибка при передаче, и ко личества информации (если ошибка совершена), необхо димого для того, чтобы* установить, какая из NT— 1 ос
тальных возможных типичных последовательностей дейст вительно была передана. Если вероятность ошибки равна
Рош, то первое |
слагаемое отмеченной суммы в среднем |
|
равно |
• * |
|
|
Н і = — |
Рош log Рош — (1 — Рош ) log (1 — Рош ), |
а второе в среднем не будет превышать величины
, |
я 2 = |
Pomlog(/Vr — 1). |
|
|
Поэтому |
|
|
|
|
Щ |
Х ТІГ Т ) < / Л |
+ |
Я , = Рош lo g { X т |
1) - |
- |
Рош log Рош - |
(1 |
- Рош ) log (1 - Рош ). |
(4.16) |
Так как по условию теоремы вероятность ошибки может быть сделана меньше любого наперед заданного положи тельного числа е, т©
95
H ( X T;YT) ^ B\ o g( Nr — 1) — slo g s — (1 — s) log (1 — s) <
< slogO V r - |
1)4-1 |
< |
г TCc -|- 1. |
(4.17) |
|||
Подставляя |
(4.17) |
в |
(4.15), |
получаем |
|
||
lim- H{XT\YT) < lim e TCc + 1 |
|
||||||
7- oo |
T |
7'—oo |
t |
|
|||
Ввиду произвольной малости |
£ |
|
|
||||
|
|
|
lim |
|
|
|
|
|
|
|
У'-*- со |
|
|
|
|
что и требовалось доказать. |
|
|
|
||||
_____ Теорема 3 |
(К. |
Шеннон). |
|
Если поток |
информации |
||
Н ( Х ) = Сс + |
г, |
где |
£ |
> 0 , то никакой код не может сде |
|||
лать вероятность ошибки сколь угодно малой. Минималь ные потери информации в единицу времени [H(XjY)] рав
ны £. |
Из |
неравенства (4.16) |
и эрго- |
Д о к а з а т е л ь с т в о . |
|||
дпческой теоремы (см. § 2 гл. 2) |
при достаточно большом Т |
||
Т Ь = Н ( Х Т) - H(XTt!Y т) > |
log N T- P omlog (Л^ - |
1) - 1. |
|
По определению пропускной способности І^ССс, поэто му
|
log N T |
|
I -{-CT |
ош > |
log (NT - |
1) |
log (NT- 1) ~ |
— 1 |
1 + CT |
= 1 |
1 + CT |
|
10 g N T |
|
H(X)T ’ |
откуда видно, что, как бы велико Т ни было, вероятность ошибки Р ош не может быть сделана как угодно малой, что и доказывает первую часть теоремы.
Второе утверждение теоремы непосредственно следует из определения пропускной способности как максималь ной скорости передачи:
T = 7 f ( X ) - H ( X j Y ) 4 £ C c,
откуда
H ( X / Y ) > H ( X ) - C c = t,
что и требовалось доказать.
Доказанные теоремы являются теоремами существо вания. Из доказательства этих теорем не следует, каким
96
образом построить код и произвести декодирование, что бы вероятность ошибки была как угодно мала, а скорость передачи как угодно близка к пропускной способности ли нии связи. Поэтому можно сказать, что теоремы о кодиро вании в присутствии шумов оправдывают поиск помехо устойчивых кодов, не давая рецептов к их .отысканию.
Задача 1. В запоминающем устройстве накоплено ІО4 дв. единиц информации. Для ее передачи можно вос
пользоваться |
одним из двух симметричных каналов с |
иезависимы ми |
ошибками. Определить, каким каиалом |
следует воспользоваться, чтобы передать накопленную ин формацию за минимальное время с высокой верностью при следующих параметрах каналов: Ѵк— скорость пере дачи канальных символов; Р ош— вероятность ошибки в канале. Найти время передачи в каждом канале. Срав нить со временем передачи по каналу без помех.'Обсу дить результаты. (В обоих случаях допускается кодиро вание с любой сложностью. и1= 2000 бит/с, ѵ2= 1000 бит/с,
Ріош =0,03, Р2ош==0,003.)
Ре ш е и и е. Пропускная способность двоичного сим
метричного канала связи определяется по формуле
с = V [Н - |
Рошlog Р ош + |
(1 — Р ош) log (1 - Рош )] • |
Для первого капала связи |
|
|
С{ = 2000(1 + |
0,03 log 0,03 + |
0,97 log 0,97) ^1611 (бит/с), |
для второго |
|
|
С2 = 1000(1 + 0,003 log 0,003 + 0,997 log 0,997) = '
= 970 (бит/с).
Время передачи накопленной информации по первому и второму каналам соответственно равно:
/1 = - Ш Г ~ 6>21 (°); ^ = - ^ ~ 1 . 3 Н с ) .
Согласно теоремам Шеннона, для обоих каналов всег да существует код, при котором вероятность ошибочного приема может быть сделана как угодно малой величиной. Поэтому для передачи 10000 бит информации целесооб разно воспользоваться вторым каналом, так как время пе редачи при этом меньше примерно в 5 раз.
7 За к. 2340. |
97 |
Г Л А В А 5
НЕПРЕРЫВНЫЕ КАНАЛЫ С ШУМАМИ
§ 1. Пропускная способность непрерывных каналов
Под сообщением, вырабатываемым источником, будем понимать реализацию x(t) случайного процесса, задан ную на конечном интервале времени Т. Будем считать, что входные сообщения x(t) и Еыходиые у(і) линии связи являются стационарными, эргодическими и стационарно связанными случайными функциями времени.
Произвольную реализацию x(t) случайной функции, заданной на конечном интервале времени Т с как угодно большой степенью точности, можно представить вектором X, координаты которого суть коэффициенты разложения x(t) по некоторой системе регулярных функций (см. при ложение). Это представление будет тем более точно, чем больше число членов разложения берется. В дальнейшем будем считать, что разложение производится согласно теореме. Котельникова (см. приложение). Тогда коорди натами ъектора X являются значения функции х (t) в точ ках опроса:
2 \ |
/п — 1 \ |
2Wу |
•••’ Хп [ 2\Ѵ )' |
Для различных сообщений эти координаты принимают различные значения. Координаты вектора X являются случайными величинами, которые в'общем случае непре рывны. Статистическое описание такой совокупности случайных величин дается п-мерной плотностью вероят ности w(xь х2, ..., хп).
Врезультате воздействия шумов входное сообщение
х(і) линии связи отличается от соответствующего выход ного сообщения y(t).
Для определения количества информации, содержа
щегося в сообщении y(t) и x(t),
I ( X T , Y T )^= H ( Y т) - H i ? т; X T) |
(5.1) |
98
определим H ( Y T) и H(YTiXT):
H{YT) = — ?... |
[ш(уі, |
yn)logw(yu |
yn) dyv |
dyn. |
• (5.2)
Если у I, #2/ •••> У n— независимые случайные величины, то
w{ yt. у а , . . . , уп) = ад(Уі) а д ( у 2) ... w ( * f o ) - '
Подставляя (5.2) в (5.1) и выполняя интегрирование, получаем
ЩУТ) = - 2 |
Тад(у;) logco (у<) dyi = 2WTH(Y), |
(5.3) |
/=1 -do
так как для стационарных функций для всех i w (уі) одинаковы, а число точек опроса на интервале [О, Т], со гласно теореме Котельникова, равно 2WT, где W — поло са частот, занимаемая сигналом y(t).
Условную энтропию H(Yr/ X T) определим по формуле
|
|
00 |
|
00 |
|
СО |
|
. . . |
I' |
|
|
|
ЩѴТІХТ) = - |
1I ' |
. . .Ir |
|
I’V |
... |
..., -vn; i/i, .. .y„)X |
||||||
|
|
|
|
|
|
J йфгь |
||||||
|
|
00 |
— |
00 |
— |
00 |
|
— |
00 |
|
|
|
X Іоg w ( y ly • • *j |
У |
|
*• • > xn) d x 1...dx„dyl ...dyn. |
|
||||||||
Положим, что значение уі |
|
зависит лишь от значения х |
||||||||||
и не зависит |
|
от xj, |
если / |
|
фі. |
Так как, |
|
кроме того, |
уі и |
|||
уу-— независимые случайные величины, то |
|
|||||||||||
w(xu ..., хп; |
|
уи ..., |
y„) = |
|
w(x1, y j w( x 2, уг) ...w(x„, |
y„). |
||||||
Поэтому |
|
|
|
|
|
|
|
|
|
|
|
|
H{YT / х т) = |
— V |
f ... |
j |
w(xi, |
Уі) legwiyii'Xi) dxidyi = |
|||||||
|
|
/==1 — bo |
— OO |
|
|
|
|
|
|
|||
|
|
= 2WTH(Y;X), |
|
|
|
(5.4) |
||||||
где мы воспользовались тем, что процессы x(t) и y(t) стационарно связаны, т. е. ад (я/, у^) и wix^yi) для всех і~ одинаковы.
Подставив (5.3) и (5.4) в (5.1), получим
І(ХТ, Y T) = 2WT[H(Y) - H(Y/X)] .
По определению скорости передачи
Т{Х, Y) = lim -/(Лт' І Т] • = 2W[H(Y) — H(Y:tX)\. |
(5.5) |
г- 00 1
9 9