Кодеры, основанные на системе сжатия без потерь информации
В данном случае кодирующее устройство должно удовлетворять следующим условиям:
1. Обеспечивать безошибочную передачу информации, то есть взаимно однозначное соответствие между и (рисунок 11.2).
2. Обеспечивать кодирование наиболее экономным образом (с минимальной избыточностью).
Для выполнения первого требования:
а) необходимо, чтобы различным буквам алфавита соответствовали различные кодовые слова;
б) необходимо, чтобы была предусмотрена возможность разделения кодовых слов при их последовательной передаче. Для обеспечения этой возможности:
- используют специальные разделяющие символы;
- применяют кодовые слова одинаковой длины (равномерное кодирование);
- кодовая таблица составляется таким образом, чтобы никакое кодовое слово не являлось началом другого кодового слова.
Для выполнения второго требования необходимо добиваться при кодировании минимальной средней длины кодового слова:
.
(11.3)
где – это длина -ого слова с учетом разделительной буквы (если она используется).
Теорема 1. Теорема Шеннона о кодировании в дискретных каналах без шума.При кодировании множества сигналов с энтропией при условии отсутствия шумов средняя длина кодового слова не может быть меньше, чем , где – размер алфавита кодера, 2 – основание алфавита кода.
Если вероятности сигналов не являются целочисленными отрицательными степенями (то есть все вероятности сообщений имеют вид: , где – целое положительное число), достижение указанной нижней границы невозможно, но при кодировании достаточно длинными блоками к ней можно сколь угодно приближаться.
Существует несколько способов, позволяющих получать коды с малой избыточностью; причем все они обладают следующими свойствами:
1. Более вероятным буквам источника ставятся в соответствие более короткие кодовые слова.
2. Никакое кодовое слово не является началом другого более длинного кодового слова.
3. Все буквы алфавита, используемые для передачи информации приблизительно равновероятны.
4. Символы в последовательности на выходе кодера практически независимы.
Простейшими кодами, с помощью которых можно выполнять сжатие информации, являются коды без памяти:
- код Хаффмана;
- код Шеннона;
- код Шеннона-Фано;
- код Гильбера-Мура.
Наилучшим из кодов, обладающих свойствами, перечисленными выше, является код Хаффмана. Его мы и рассмотрим в ходе этой лекции, а остальные коды рассмотрим в последующих лекциях.
Код Хаффмана – это двоичный префиксный код без памяти. Далее рассмотрим некоторые теоретические основы этого кода.
Префиксным множеством двоичных последовательностей S называется конечное множество двоичных последовательностей таких, что ни одна последовательность в этом множестве не является префиксом, или началом, другой последовательности в S.
Например, множество двоичных слов является префиксным множеством, а – не является т. к. здесь двоичных последовательность 00 является началом, другой последовательности 001 в S2.
Каждый префиксный код является дешифрируемым (обратное утверждение неверно).
Кодирование кодом без памяти осуществляется следующим образом:
1. Необходимо составить полный список символов алфавита входного сигнала; на j-ом месте стоит символ с вероятностью , то есть на первом месте стоит наиболее часто встречающийся символ.
2. Для любого назначить кодовое слово из префиксного множества двоичной последовательности S.
3. На выходе кодера объединить в одну последовательность все полученные двоичные слова.
Если – префиксное множество, то можно определить некоторый вектор , состоящий из чисел, являющихся длинами соответствующих префиксных последовательностей ( является длиной ). Вектор состоит из неуменьшающихся положительных целых чисел и называется вектор Крафта. Для него выполняется неравенство Крафта:
(11.4)
Длины двоичных последовательностей в префиксном множестве удовлетворяют данному соотношению. Если в (11.4) имеет место строгое равенство, то код называется оптимальным.
