11.2. Кодированные сигналы

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

В позиционной системе счисления с основанием хчислоq– это сокращенная запись полинома

,

где l– номер разряда числа;L–разрядность числа;a_l[0;x–1] – разрядный коэффициент.

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

Сокращенно полином можно представить совокупностью разрядных коэффициентов

,

а сигнал передающий значение этого числа s_q– совокупностью элементарных сигналов, отображающих разрядные коэффициенты. Каждый элементарный сигнал называется символом, вся совокупность символов – алфавитом. Количество различных символов – мощность множества символов или, что то же самое, размерность алфавита, равнах. Очевидно, что при помощиLсимволов, выбранных из алфавита размерностьюх, можно представить всегоN=x^Lразных чисел и, соответственно, разных кодированных сигналов. При этомL– количество символов, которые употребляются для представления любого изNкодированных сигналов, называется значностью кода.

При использовании двухосновного кодирования алфавит содержит всего два символа, поэтому N=2^L. Вся совокупностьNвозможных сигналов называется кодом, а каждый изNсигналов – кодовой комбинацией или кодовым словом.

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

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

У равномерных кодов все кодовые комбинации имеют одинаковую длину, т. е. содержат одинаковое количество элементарных символов. Это количество символов в каждой комбинации равномерного кода называется значностью кода. В использованном представлении кодовых комбинаций таких символов – значность кода – L. Если количество символов в кодовых комбинациях не одинаково, коды относят к неравномерным.

11.2.1. Эффективное кодирование

Предположим, что источник информации формирует 8 возможных сообщений с s₀, …,s₇с вероятностямир₀, …р₇, приведенными в табл. 11.1. Для представление любого из восьми сообщений последовательностями равномерного двоичного кода требуется 3 двоичных символа.

Таблица 11.1.

Сообщение	Кодированная последовательность символов	Вероятность
s0	000	р0=1/2
s1	001	Р1=1/4
s2	010	Р2=1/8
s3	011	Р3=1/16
s4	100	Р4=1/32
s5	101	Р5=1/64
s6	110	Р6=1/128
s7	111	Р7=1/128

Для такого источника нетрудно подсчитать энтропию, т. е. среднее количество двоичных единиц, которое требуется для передачи одного сообщения:

.

Это означает, что при использовании для кодирования сообщений данного источника равномерным трехзначным двоичным кодом вносится более, чем полуторократная избыточность. Для того чтобы избежать внесения избыточности, правило кодирования можно построить иначе, используя, например, процедуру кодирования Шеннона-Фано. В соответствии с этой процедурой все сообщения сортируются по убыванию вероятности (как в табл. 11.1). Затем их делят на две группы так, чтобы вероятности сообщений из каждой группы были бы примерно одинаковыми. Всем сообщениям первой группы присваивается символ 1, а всем сообщениям второй группы – 0. Каждую из полученных групп, в свою очередь, разбивают на две подгруппы с одинаковыми суммарными вероятностями, которым также присваиваются символы 1 и 0. Итерационно эта процедура повторяется до тех пор, пока от всего исходного множества сообщений не останется одна последняя пара.

Для конкретного массива сообщений табл. 11.1 процедура кодирования выглядит следующим образом.

1 итерация: s₀1; {s₁, s₂, s₃, s₄, s₅, s₆, s₇}0;

2 итерация s₁01; {s₂, s₃, s₄, s₅, s₆, s₇}00;

3 итерация s₂001; {s₃, s₄, s₅, s₆, s₇}000;

4 итерация s₃0001; {s₄, s₅, s₆, s₇}0000;

5 итерация s₄00001; {s₅, s₆, s₇}00000;

6 итерация s₅000001; {s₆, s₇}000000;

7 итерация s₆0000001; s₇0000000.

Как видно, для передачи сигнала s₀используется 1 символ,s₁– 2 символа, и т. д.s₆иs₇– по 7 символов. Среднее количество символов на одно сообщение

,

т. е. ровно столько, сколько требуется при безызбыточном кодировании. Разумеется, в более общем случае, когда вероятности разных сообщений не кратны отрицательной степени двойки, среднее число символов на каждый кодированный сигнал будет не меньше энтропии, но всегда меньше, чем log₂N.

Методика Шеннона-Фано не всегда приводит к однозначному построению кода, поскольку при разбиении сообщений (и сигналов) на подгруппы можно присваивать символ 1 как более вероятной, так и менее вероятной группе.

Другая процедура оптимального кодирования связана с именем Хаффмена, которая, в отличие от методики Шеннона-Фано, всегда приводит к однозначному построению кода. Работа методики Хаффмена иллюстрируется табл. 11.2.

Таблица 11.2.

Процедура кодирования иллюстрируется графом (деревом) рис. 11.1.

Рис. 11.1. Кодовое дерево для массива сообщений из табл.11.2.

Из точки, соответствующей вероятности 1, направляются две ветви, причем ветви с большей вероятностью (0,58) присваивается символ 1, а с меньшей (0,42) – символ 0. Такое последовательное ветвление продолжается до тех пор, пока ребра графа не доходят до каждого конкретного сообщения. Двигаясь по кодовому дереву сверху вниз можно сформировать кодовую комбинацию для каждого сигнала:

s0	s1	s2	s3	s4	s5	s6	s7
01	00	111	110	100	1011	10101	10100

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

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

s0	s1	s2	s3
00	01	101	100

декодируется однозначно:

100	00	01	101	101	101	00
s3	s0	s1	s2	s2	s2	s0

Последовательность 000101010101 комбинаций непрефиксного кода, например кода

s0	s1	s2	s3
00	01	101	010

(комбинация 01 является началом комбинации 010), может быть декодирована по-разному

00	01	01	01	010	101
s0	s1	s1	s1	s3	s2

или

00	010	101	010	101
s0	s3	s2	s3	s2

или

00	01	010	101	01	01
s0	s1	s3	s2	s1	s1

Коды, получаемые в результате применения методики Шеннона-Фано или Хаффмена, являются префиксными.

Рассмотренные процедуры оптимального кодирования не учитывали корреляционных связей между разными сообщениями, принадлежащими одному и тому же ансамблю. Учет таких связей, если они имеются, позволяет устранить избыточность кодированных сообщений в еще большей степени. Для эффективного кодирования коррелированных сигналов необходимо модифицировать процедуры Шеннона – Фано и Хаффмена.

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