Читать в оригинале

<< ПредыдущаяОглавлениеСледующая >>


2.2. Пропускная способность дискретного канала без шумов

Если в дискретном канале алфавиты кодовых символов  на входе и  на выходе одинаковы и

т. е. символы на выходе и входе всегда совпадают, то такой канал называют дискретным каналом без шумов. Он полностью характеризуется основанием кода  и количеством символов , пропускаемых в среднем в единицу времени.

В таком канале количество информации  содержащееся в принятых символах  относительно переданных символов , всегда равно энтропии источника . Это следует из того, что

так как , поскольку при известном значении  событие  определено однозначно.

Пропускная способность  дискретного канала без шумов, равная, по определению, максимальному значению , достигается в том случае, когда на вход канала поступают символы с максимальной допустимой скоростью  от источника, имеющего максимальную энтропию . Для этого необходимо и достаточно, чтобы источник выдавал символы алфавита объемом  с равными вероятностями и независимо друг от друга. При этом в соответствии с (1.8)  и, следовательно,

                                 (2.4)

Теорему кодирования для дискретного канала без шумов в случае источника с управляемой скоростью можно сформулировать следующим образом [1].

Если источник сообщения имеет энтропию  (двоичных единиц на букву), то можно закодировать сообщения источника таким образом, чтобы передавать их сколь угодно точно по дискретному каналу без шумов со средней скоростью

 , букв/сек,                                      (2.5)

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

Передавать их сколь угодно точно со скоростью, большей, чем , нельзя.

Очевидным следствием этой теоремы, применимым к источнику с фиксированной скоростью, является следующее утверждение.

Сообщения источника с производительностью  (двоичных единиц в секунду) можно закодировать так, чтобы передавать их сколь угодно точно по дискретному каналу без шумов, при условии, что

                                          (2.6)

Это невозможно, если

                                                               (2.7)

Эти теоремы являются частными случаями теоремы кодирования Шеннона, изложенной в первой главе. Рассмотрим некоторые простейшие случаи их применения.

1. Пусть источник выбирает элементы сообщения независимо от предыдущих и с одинаковыми вероятностями, равными , тогда . Если к тому же , то кодирование сводится попросту к установлению любым образом взаимно однозначного соответствия каждого из элементов сообщения  символу кода .

Очевидно, что при этом можно передавать но каналу  элементов сообщения в секунду. Но . Таким образом, при этих условиях теорема справедлива даже при . В этом случае иногда (впрочем, без особого основания) считают, что сообщение передается без кодирования.

2. Пусть по-прежнему , но , где  — целое число. Построим все возможные последовательности из кодовых символов («кодовые комбинации») длиной . Очевидно, их число равно . Установим взаимно однозначное соответствие каждого элемента сообщения  кодовой комбинации. Таким образом, каждая комбинация из  символов, переданная по каналу, соответствует одному элементу сообщения и, следовательно, скорость передачи элементов сообщения

.                                                      (2.8)

Таким образом, и в этом случае теорема справедлива даже при . Такой код, в котором все кодовые комбинации имеют одинаковую длину , называется равномерным  - разрядным кодом.

3. Пусть для того же источника с  объем алфавита  не является целой степенью числа . Так, например, пусть источник выбирает независимо и с равной вероятностью любую из десяти цифр 0, 1,..., 9, а канал имеет два символа (обозначим их 0 и 1) и позволяет передаватьсимволов в секунду.

Здесь  дв. ед. и . Согласно теореме скорость передачи цифр в таком канале может быть сделана сколь угодно близкой к .

Попытаемся достигнуть этого, кодируя каждую цифру равномерным -разрядным кодом. Это сводится, в сущности, к тому, чго каждая из десяти цифр 0, 1,..., 9 изображается двоичным числом: 0000, 0001,..., 1001. Очевидно, что для этого потребуются четырехразрядные двоичные числа. Таким образом, на каждый элемент сообщения (цифру) при таком кодировании потребуется 4 кодовых символа, тогда как теорема утверждает, что можно осуществить более «экономное» кодирование, приближаясь к количеству кодовых символов 3,332 на цифру.

Покажем, что это можно сделать, если до кодирования произвести укрупнение алфавита источника. Будем рассматривать каждую пару цифр, выдаваемых источником, как двухразрядное десятичное число, т. е., перейдем от  и сведем по-прежнему «кодирование к изображению этого числа в двоичном счислении. Всякое число меньше 100 можно представить семиразрядным двоичным числом (на том основании, что 27 = 128 > 100, тогда как 26 = 64 и поэтому шестиразрядных двоичных чисел не хватит для представления всех двухразрядных десятичных чисел). При таком кодировании на каждые два знака сообщения потребуется семь кодовых символов, т. е. в среднем 3,5 кодового символа на цифру, а не 4, как было до укрупнения алфавита.

Продолжим укрупнение алфавита, рассматривая каждые три цифры, выдаваемые источником, как трехразрядное десятичное число. Его можно представить в двоичном счислении 10-разрядным числом (так как 210=1024>1000). Следовательно, при таком кодировании на одну цифру потребуется 10/3=3,333 кодового символа, что уже очень близко к теоретической величине 3,332.

Дальнейшие укрупнения алфавита позволят еще больше приблизить скорость передачи цифр по такому двоичному каналу к величине , но, конечно, не превзойти ее. Действительно, если объединить  цифр, выдаваемых источником, в -разрядное десятичное число, то его можно изобразить -разрядным двоичным числом при условии, что   или , откуда

.                                                     (2.9)

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

Вообще, когда , но  не является целой или рациональной степенью , можно для любого числа  найти такое число , при котором справедливы неравенства

                                        (2.10)

Будем рассматривать каждые  букв сообщения как букву укрупненного алфавита объемом  элементов и установим взаимно однозначное соответствие укрупненных букв кодовым комбинациям равномерного -разрядного кода, что всегда можно сделать на основании (2.10) (так как ), причем часть комбинаций останется неиспользованной. Тогда каждая комбинация из  символов, переданная по каналу, соответствует  буквам первичного алфавита сообщения. Скорость передачи сообщения при этом равна

                                                  (2.11)

Из (2.10) имеем , где

Это выражение можно записать в форме

                                    (2.12)

Отсюда

            (2.13)

Если число  выбрать из условия  то

                                  (2.14)

что и требовалось доказать.

Полученный результат показывает, что в канале с пропускной способностью  можно, применяя равномерный код, передавать сообщения любого источника, имеющего объем алфавита , со скоростью, сколь угодно близкой к  -  букв в секунду. Такой метод кодирования мы будем называть примитивным. Это утверждение, конечно, более слабое, чем требование теоремы, по которому для любого источника с энтропией  скорость передачи может быть сколь угодно близкой к

 



<< ПредыдущаяОглавлениеСледующая >>