2017-10-31
673
Кодирование – это установление биективного соответствия между элементами двух множеств: дискретных сообщений и кодовых слов.
Правило, сопоставляющее каждому дискретному сообщению - букве или последовательности букв - кодовое слово называется правилом кодирования.
Сама операция сопоставления называемся кодированием сообщения.
Совокупность кодовых слов, обозначающих дискретные сообщения, называется кодом.
Множество кодовых букв (символов) называется кодовым алфавитом, а их количество - объемом алфавита или основанием кода. Количество букв в кодовом слове называется длиной кодового слова или значностью кода.
Поскольку кодирование есть процедура, требующая расхода ресурсов вычислительной системы, при кодировании сообщений дискретного источника возникает задача выбора правила оптимального кодирования (критерия).
Естественно полагать оптимальным такое правило кодирования (критерий), при котором:
–во-первых, кодовые слова могут быть декодированы в исходную последовательность букв источника;
|
|
|
–во-вторых, число кодовых букв, затрачиваемых на одну букву источника, в среднем минимально.
Первое требование определяет обратимость операции кодирования – однозначность декодирования, а второе - экономность кодирования или быстродействие кодера.
Очевидно, что «экономнее» будет кодер, в котором более вероятным буквам источника сопоставляются более короткие кодовые слова, т.е. в общем случае оптимальный код должен быть неравномерным.
Среднее число кодовых букв на одну букву источника можно определить по формуле
, (2.1)
где ni – число кодовых букв, кодирующих слово xi источника,
P(xi) – вероятность появления буквы xi на выходе дискретного источника.
Данные коды являются оптимальными с точки зрения «экономичности», в них минимизируется избыточность, однако они применимы для передачи информации только в каналах без искажений. Искажение любого бита кода ведет к искажению закодированного слова.
Оптимальный код Шеннона-Фано
В соответствии с этим методом кодирования необходимо:
1. Составить список символов источника в порядке убывания вероятности их появления.
2. Множество возможных символов разбивается горизонтальной чертой так, чтобы суммарные вероятности в обоих группах были одинаковы и приблизительно равны 0,5. Если кодируемый символ относится к первой группе (выше черты), то в качестве первого символа его кодовой комбинации берется "0", а для символов второй группы (ниже черты) в качестве первого символа берется "1".
3. Каждая из групп разбивается на две подгруппы с примерно равными суммарными вероятностями. В качестве второго символа берется "0", если символ находится выше черты деления в подгруппе, и "1" - если ниже. Деление продолжается до тех пор, пока в каждой подгруппе не остается один единственный символ.
|
|
|
Описанный метод кодирования Шеннона-Фано иллюстрируется на примере двоичного кода табл.2.1.
Таблица 2.1.
Приведенный код имеет по (2.1) среднюю длину кодового слова = 2,75 двоичных знаков на один символ алфавита.
Если посчитать энтропию Шеннона источника, то окажется, что она тоже равна 2,75 двоичных знаков на один символ алфавита, т.е. кодирование оказалось идеальным.
Когда вероятности появления символов не позволяют разбить их на группы с равными вероятностями, то вместо одиночных символов возможно рассматрение сообщения из n элементов. Применяя рассмотренный метод к таким блокам символов, можно всегда добиться кодирования, близкого к оптимальному.
Задача. Построить оптимальный код для английского языка.
профессор кафедры № 301
В. КНЯЗЕВ
