ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 24.10.2024
Просмотров: 53
Скачиваний: 0
Р е ш е н и е . Как следует из решений двух предыду
щих задач, |
максимальное количество информации, |
несо |
|
мое одним |
двоичным символом, |
передаваемым по сим |
|
метричной линии связи: |
|
|
|
Лшх = 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