Постановка задачи кодирования, Первая теорема Шеннона

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

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

Введем ряд с определений.

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

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

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

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

Пусть первичный алфавит %%А%% состоит из %%N%% знаков со средней информацией на знак %%I(A)%%, а вторичный алфавит %%B%% - из %%М%% знаков со средней информацией на знак %%I(B)%%. Пусть также исходное сообщение, представленное в первичном алфавите, содержит n знаков, а закодированное сообщение - m знаков. Если исходное сообщение содержит %%I_{st}(A)%% информации, а закодированное - %%I_{fin}(B)%%, то условие обратимости кодирования, т.е. неисчезновения информации при кодировании, очевидно, может быть записано следующим образом:

$$I_{st}(A)\leqslant I_{fin}(B)$$

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

$$n\cdot I_{(A)}\leqslant m\cdot I_{(B)}$$ или $$I_{(A)}\leqslant \frac{m}{n}\cdot I_{(B)}$$

Отношение m/n, очевидно, характеризует среднее число знаков вторичного алфавита, которое приходится использовать для кодирования одного знака первичного алфавита - будем называть его длиной кода или длиной кодовой цепочки и обозначим К(А,В). Следовательно

$$K(A,B)\geqslant \frac{I_{(A)}}{I_{(B)}}~~~(3.1)$$

Обычно %%N > M%% и %%I(А) > I(B)%%, откуда %%K(A,B) > 1%%, т.е. один знак первичного алфавита представляется несколькими знаками вторичного. Поскольку способов построения кодов при фиксированных алфавитах А и В существует множество, возникает проблема выбора (или построения) наилучшего варианта - будем называть его оптимальным кодом. Выгодность кода при передаче и хранении информации - это экономический фактор, так как более эффективный код позволяет затратить на передачу сообщения меньше энергии, а также времени и, соответственно, меньше занимать линию связи; при хранении используется меньше площади поверхности (объема) носителя. При этом следует сознавать, что выгодность кода не идентична временной выгодности всей цепочки кодирование-передача-декодирование; возможна ситуация, когда за использование эффективного кода при передаче придется расплачиваться тем, что операции кодирования и декодирования будут занимать больше времени и иных ресурсов (например, места в памяти технического устройства, если эти операции производятся с его помощью).

Как следует из (3.1), минимально возможным значением средней длины кода будет:

$$K^{min}(A,B)=\frac{I_{(A)}}{I_{(B)}}~~~(3.2)$$

Данное выражение следует воспринимать как соотношение оценочного характера, устанавливающее нижний предел длины кода, однако, из него неясно, в какой степени в реальных схемах кодирования возможно приближение %%K(A,B)%% к %%K_{min}(А,В)%%. По этой причине для теории кодирования и теории связи важнейшее значение имеют две теоремы, доказанные Шенноном. Первая - ее мы сейчас рассмотрим - затрагивает ситуацию с кодированием при отсутствии помех, искажающих сообщение. Вторая теорема относится к реальным линиям связи с помехами и будет обсуждаться позже.

Первая теорема Шеннона, которая называется основной теоремой о кодировании при отсутствии помех, формулируется следующим образом:

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

Приведенное утверждение является теоремой и, следовательно, должно доказываться. Мы опустим доказательство в рамках данного курса. Для нас важно, что теорема открывает принципиальную возможность оптимального кодирования, т.е. построения кода со средней длиной %%K_{min}(A,B)%%. Однако необходимо сознавать, что из самой теоремы никоим образом не следует, как такое кодирование осуществить практически - для этого должны привлекаться какие-то дополнительные соображения, что и станет предметом нашего последующего обсуждения.

Из (3.2) видно, что имеются два пути сокращения %%K_{min}(A,B)%%:

• уменьшение числителя - это возможно, если при кодировании учесть различие частот появления разных знаков в сообщении, корреляции двухбуквенные, трехбуквенные и т.п.
• увеличение знаменателя - для этого необходимо применить такой способ кодирования, при котором появление знаков вторичного алфавита было бы равновероятным, т.е. %%I(B) = log_2 M%%.

В частной ситуации, рассмотренной подробно К. Шенноном, при кодировании сообщения в первичном алфавите учитывается различная вероятность появления знаков (то, что в п.2.3. мы назвали «первым приближением»), однако, их корреляции не отслеживаются - источники подобных сообщений называются источниками без памяти. Если при этом обеспечена равная вероятность появления знаков вторичного алфавита, то, как следует из (3.2), для минимальной средней длины кода оказывается справедливым соотношение:

$$K_{min}(А,В)=\frac{I_1^{(A)}}{log_2M}~~~(3.3)$$

В качестве меры превышения К(А,В) над %%K_{min}(А,В)%% можно ввести относительную избыточность кода Q(А,В):

$$Q(А,В)=\frac{K(A,B)-K_{min}(А,В))}{K_{min}(А,В)}=\frac{K(А,В)}{K_{min}(А,В)}-1=\frac{K(А,В)\cdot I^{(B)}}{I^{(A)}}=1~~~(3.4)$$

Данная величина показывает, насколько операция кодирования увеличила длину исходного сообщения. Очевидно, %%Q(A,B) → 0%% при %%К(А,В) → K_{min}(А,В)%%. Следовательно, решение проблемы оптимизации кода состоит в нахождении таких схем кодирования, которые обеспечили бы приближение средней длины кода к значению Кmin(А,В), равному отношению средних информации на знак первичного и вторичного алфавитов. Легко показать, что чем меньше %%Q(A,B)%%, тем %%I_{fin}(В)%% ближе к %%I_{st}(A))%%, т.е. возникает меньше информации, связанной с кодированием, более выгодным оказывается код и более эффективной операция кодирования.

Используя понятие избыточности кода, можно построить иную формулировку теоремы Шеннона:

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

Наиболее важной для практики оказывается ситуация, когда %%М = 2%%, т.е. для представления кодов в линии связи используется лишь два типа сигналов - технически это наиболее просто реализуемый вариант (например, существование напряжения в проводе (будем называть это импульсом) или его отсутствие (пауза); наличие или отсутствие отверстия на перфокарте или намагниченной области на дискете); подобное кодирование называется двоичным. Знаки двоичного алфавита принято обозначать «0» и «1», но нужно воспринимать их как буквы, а не цифры. Удобство двоичных кодов и в том, что при равных длительностях и вероятностях каждый элементарный сигнал (0 или 1) несет в себе 1 бит информации %%(log_2 M = 1)%%; тогда из (3.3)

$$Q(A,2)=\frac{K(A,2)}{I_1^{(A)}}-1~~~(3.5)$$

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

• элементарные сигналы (0 и 1) могут иметь одинаковые длительности %%(τ_0= τ_1)%% или разные %%(τ_0 ≠ τ_1)%%;
• длина кода может быть одинаковой для всех знаков первичного алфавита (в этом случае код называется равномерным) или же коды разных знаков первичного алфавита могут иметь различную длину (неравномерный код);
• коды могут строиться для отдельного знака первичного алфавита (алфавитное кодирование) или для их комбинаций (кодирование блоков, слов).

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