3.4. Примеры неравномерных кодов

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

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

Простым неравномерным кодом является унарный код. Кодовое слово в нем составлено из одинаковых символов, например единиц, а разделителем является ноль (группа нолей). Декодирование выполняется путем простого подсчета информационных символов, например: 1 → 10; 2 → 110; 3 → 1110 и т.д. Следует отметить, что унарный код скорее «неэффективный», поскольку использует унарное обозначение и его длина экспоненциально растет с ростом длины сообщения.

В практических схемах нашел применение так называемый SSS (Start-Step-Stop) код (старт–стопный код). В нем кодовое слово состоит из двух групп кодовых символов: префиксного кода, определяющего начало кодовой комбинации и номер кодовой группы, и бинарного кода, перекрывающего определенный диапазон кодируемых значений.

Пример SSS (3, 2, 12) кода приведен в табл. 2 (максимально 3 бита в префиксной группе, бинарный код в кодовой комбинации, максимальная длина кода 12 символов).

Таблица 2

Кодовая группа	Кодовое слово	Диапазон кодируемых значений
1	0ххх	0 – 7
2	10ххххх	8 – 39
3	110ххххххх	40 – 167
4	111ххххххххх	168 – 679

Префикс определяет кодовую группу (диапазон кодируемых значений) и используется при декодировании. Например, символ а исходного алфавита (код 55) кодируется (в обратном порядке декодируется) следующим образом. От кодируемого значения вычитается начало диапазона кодируемых значений для третьей группы (55 – 40). Число 15 кодируется бинарным кодом 1111. При необходимости пустые позиции заполняются нулями (см. табл. 2).

Таким образом код символа а имеет вид 110.0001111.

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

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

Код Шеннона - Фано строится следующим образом: знаки исходного алфавита и значения вероятности их появления заносятся в список, упорядоченный по убыванию значений вероятностей. Затем этот список разделяется на такие две группы, суммы вероятностей в которых были бы приблизительно равны. Каждый знак алфавита первой группы получает первым символом его кодового слова «0», вторым, соответственно, «1». Затем каждая из этих групп разбивается по этому же принципу, и так до тех пор, пока в подгруппах не останется по одному знаку.

На практике часто не известны значения вероятностей появления символов, поэтому их заменяют частотой встречаемости символа в сообщении.

Пример. Известна встречаемость букв в тексте: «А» встретилась 9 раз, «Б» – 7, «В» – 5, «Г» – 1, «Д» – 8 раз. Для заданной статистики частот символов алфавита шаги получения кодовых комбинаций по алгоритму Шеннона-Фано представлены в табл. 3.

Таблица 3