Основы теории кодирования

Кодом называется система условных знаков (символов), для передачи, обработки и хранения информации.

Пусть А – произвольный алфавит. Элементы алфавита А называются буквами, а конечные вектора, составленные из букв – словами.

Длина слова – число букв в слове , обозначается

Соединение слов и обозначим через , а соединение n одинаковых слов – через . Слово называется началом слова , если существует слово , такое что .

Рассмотрим алфавит .

Произвольное отображение произвольного множества М в множество слов в алфавите называется k -ичным кодированием множества М.

При k = 2, – двоичное множество.

Пример 1.

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

Числу ставится в соответствие слово

наименьшей длины, удовлетворяющее условию:

При этом , а длина слова . Последнее условие означает, что n удовлетворяет неравенству

Пусть n = 12.

, т. е. это дробное число между 3 и 4. Инкремент этого логарифма равен , так как это следующее целое, идущее за ним.

Аналогично . Значит, .

Таким образом, двоичный код числа 12 имеет вид:

Пример 2.

Кодирование – двоичная запись натуральных чисел с помощью m букв.

Числу , удовлетворяющему условию

ставится в соответствие слово

Пусть n = 12, m = 3.

Так как неверно то, что , то это означает, что код построить невозможно.

Пусть n = 12, m = 6.

Так как верно то, что , то это означает, что код построить можно, его вид:

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

Код называется разделимым, если разным словам в алфавите А всегда соответствуют разные слова в алфавите V.

Утверждение 1.

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

Равномерный код – это код, в котором все кодовые слова имеют одинаковую длину.

Утверждение 2.

Равномерный код всегда разделим.

Код называется префиксным, если никакое кодовое слово из V не является началом другого кодового слова.

Утверждение 3.

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

Пусть источник случайным образом генерирует буквы алфавита , причем вероятность появления каждой буквы известна. Таким образом задано распределение вероятностей Р вида:

			…
			…

Так как алфавит фиксирован, то это распределение можно записать в виде: .

Стоимостью кода V при распределении P назовем число

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

Префиксный код называется оптимальным при распределении , если его стоимость минимальна по сравнению с другими кодами алфавита А при распределении Р.

Пример 3.

Код Р. Фано, близкий к оптимальному, заключается в следующем. Упорядоченный (в порядке не возрастания вероятностей) список букв алфавита делится на две последовательные части так, чтобы суммы вероятностей входящих в них букв отличались как можно меньше. Буквам из 1-ой части присваивается символ 0, из 2-ой – 1. С каждой частью поступают аналогично. Так делается пока, в каждой из частей не окажется по одной букве. Полученные последовательности нулей и единиц является кодом Фано данного алфавита.

В таблице приведен пример построения кода Фано для распределения Р = {0.30, 0.18, 0.14, 0.14, 0.11, 0.06, 0.05, 0.02}.