Вероятность: основные понятия, структура, методы. - Скороход A.B.

1|3 (2,, Z2,. . . )= (2,), % (Z2), • • • )•

Один из способов кодирования: разбиение последовательности со
общений на отрезки длины п и кодирование каждого такого"
отрезка. Если Мр (zx,. . ., z„) == (хххт), гр (2,,. . ., z„) = (хи_. ■ ■
• • • > -Хт), ТО гр (Z\, z2,. . ., zn, zx,. . ., zn) = (xx,. . . , Xm, X\,. . ., -£/n).

Декодирование определяется функцией 6 из У°° в U°°, кото-
рая также должна быть неупреждающей. Наиболее естествен-
ный случай, когда U может быть отождествлено с Z. Если это
так и передача сообщений происходит без ошибок, наша цель
получить на выходе ту же последовательность сообщений, ко-
торую вырабатывает источник информации. Поэтому последо-
вательность отображений

lb ф 9

ZOO Л7-СО TrCO гуОО

должна быть такой, чтобы суперпозиция 6 о ср о гр была в неко-
тором смысле тождественным отображением (это не означает,
что по конечному отрезку zu z2,...,zn мы восстанавливаем
этот же отрезок, но по нему мы восстанавливаем Z},...,Zkn-
где kn^n, п—kn — величина запаздывания передачи). Поэтому
функция 8, задающая декодирование, определяется функцией
чр, задающей кодирование (канал связи при этом фиксирован,
<р не меняется). Иногда функция декодирования задается по-

следовательностью функций Эп, определенных на Уп и прини-
мающих значения в Ъ^п , не убывает, и при разных п со-
гласованных следующим образом: при из равенства
6п {у и ■■■,Уп) = (г и ■ гип) вытекает, что

6т (Уи ■ • •, Уп, ■ ■ ■, Ут) = (г„.. •, г„п,г„т).

Можно рассматривать также рандомизированные правила де-
кодирования, когда задаются вероятности

Р(6т (Уи- • .,Уя) = (г,,. • ., гкп))

(они зависят от у{ и г,).

Пример. Пусть Х=У= {0,1}, канал без памяти и без шу-
ма, 0 переводится в нуль, 1 в 1. 1={\, 2, 3}, сообщения появ-
ляются независимо и равновероятно. За время п может по-
явиться Зп равновероятных сообщений. Чтобы их закодировать
двоичными символами, нужно не менее п ^23 таких символов,
поэтому сообщения длины п не могут быть приняты раньше,

чем через время п ^23, з> и запаздывание примерно

пропорционально длине сообщения.

§ 3. Теорема Шеннона

Пример, приведенный в конце предыдущего параграфа, по-
казывает, что с помощью данного канала связи не всегда
можно передавать сообщения источника информации таким
образом, чтобы запаздывание не возрастало неограниченно.
Очевидно, если бы в этом примере Ъ={\, 2}, то возможна бы
была передача сообщений без запаздывания. Заметим, что эн-
тропия процесса на выходе канала связи (на единицу време-
ни) не превосходит пропускной способности канала, которая в
рассматриваемом примере, как легко видеть, равна 1 = ^22.
Поэтому если бы было возможно взаимно однозначное отобра-
жение процесса, являющегося потоком сообщений, вырабаты-
ваемых источником информации, в процесс, получаемый на
выходе канала связи, то энтропия источника сообщений не
должна была превышать единицы, так как при взаимно одно-
значном отображении экспериментов друг в друга энтропия не
меняется. Это общий факт: нельзя без неограниченно возрас-
тающего запаздывания передать сообщения источника информа-
ции, если его энтропия больше пропускной способности кана-
ла. Теорема Шеннона утверждает, что в том случае, когда эн-
тропия источника информации меньше пропускной способности
канала, то с вероятностью сколь-угодно близкой к единице та-
кая передача возможна. Более точную формулировку мы при-
ведем ниже. Укажем также, что сам Шеннон рассмотрел слу-
чай, когда источник информации вырабатывает последователь-
ность независимых одинаково распределенных сообщений, а

канал связи является стационарным каналом без памяти. Будем
называть этот случай простейшим. Обобщения этой теоремы
мы будем также называть «теоремой Шеннона».

3.1. Простейший случай передачи информации. Поток сооб-
щений, вырабатываемый источником информации, есть процесс
{£п, п^\}, где — независимые одинаково распределенные
случайные величины, принимающие значения из Ъ. Энтропия
источника сообщений равна

Стационарный канал связи без памяти определяется вероятнос-
тями

Его пропускная способность равна с. Будем считать, что U=Z.
Пусть выбраны кодирование и декодирование. Запаздыванием
передачи за время N называется rN = max[n—kn], где kn число

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

где £*,...,£* —последовательность, полученная декодированием

п

сообщений после передачи . . ., £лг.

Теорема Шеннона. Пусть Же. Тогда для всякого
е>0 можно указать такое Ыг, что для всех существуют