2 Методы эффективного кодирования
Под кодированием понимают отображение состояний некоторой системы (источника сообщений) с помощью состояний сложного сигнала, который представляет собой последовательность из nэлементарных сигналов[11, 15].
Состояние сложного сигнала описывается последовательностью из нулей и единиц, которая называется кодовым словом. Если кодовые слова имеют разную длину, то код называется неравномерным, а если одинаковую, то код называется равномерным.
Процедуру оптимального кодирования часто называют сжатием данных. Тогда задача сжатия данных есть минимизация технических затрат на хранение или передачу информации путем оптимального кодирования.
Методы сжатия данных были разработаны как математическая теория, которая до первой половины 80-х годов 20 века мало использовалась в компьютерной технике.
Методы или алгоритмы сжатия данных без потерь можно разделить на:
Статистические методы или алгоритмы. Например, методы Шеннона-Фано, Хаффмана и др.
Они базируются на априорной статистике (вероятностях появления букв алфавита). Это главный недостаток таких кодов, так как априорная статистика кодов заранее не известна, а, следовательно, эффективному кодированию должен предстоять так называемый частотный анализ, т.е. анализ частоты появления символов в кодовой комбинации.
Адаптивные методы или алгоритмы. Например, модифицированные коды Хаффмана, арифметическое кодирование и др.
Здесь распределение вероятностей символов сначала считается равномерным на заданном интервале, а потом оно меняется по мере накопления статистики.
Динамические методы или алгоритмы. Они являются универсальными и не нуждаются в априорной статистике. Например, метод Лемпела-Зива.
Основные информационные характеристики при кодировании:
-
энтропия источника 
;
-
избыточность источника 
;
-среднее
число символов в коде 
;
-
избыточность кода 
.
При решении задачи сжатия естественным является вопрос, насколько эффективна та или иная система сжатия. Поскольку, в основном используется двоичное кодирование, то такой мерой может служить коэффициент сжатия r, определяемый как отношение
где dimA - размер алфавита данных A.
Таким образом, коэффициент сжатия r= 2 означает, что объем сжатых данных составляет половину от объема данных источника. Чем больше коэффициент сжатия r, тем лучше работает система сжатия данных.
Наряду с коэффициентом сжатия rэффективность системы сжатия может быть охарактеризована скоростью сжатия R, определяемой как отношение
R = k/n
и измеряемой в "количестве кодовых бит, приходящихся на отсчет данных источника". Система, имеющая больший коэффициент сжатия, обеспечивает меньшую скорость сжатия.
В связи с тем, что при кодировании неравновероятных сообщений равномерные коды обладают большой избыточностью, было предложено использовать неравномерные коды, длительность кодовых комбинаций которых была бы согласована с вероятностью выпадения различных букв.
Такое кодирование называется статистическим.
Неравномерный код при статистическом кодировании выбирают так, чтобы более вероятные буквы передавались с помощью более коротких комбинаций кода, менее вероятные - с помощью более длинных. В результате уменьшается средняя длина кодовой группы в сравнении со случаем равномерного кодирования.