Материал: Методические указания к выполнению курсовой работы по дисциплине «Теория информации» для студентов специальности «Компьютерная безопасность». Поздышева О.В., Остапенко А.Г

Общее правило составления уравнений Колмогорова для предельных вероятностей pi(t) можно сформулировать следующим образом:

•в левой части уравнения стоит сумма произведений вероятностей всех состояний, из которых идут стрелки в i-ое состояние, на интенсивности соответствующих потоков минус сумма интенсивностей всех потоков, выводящих систему из данного (j-го) состояния, умноженная на вероятность данного (j-го) состояния;

•в правой части уравнения стоит 0.

19

2. МЕТОДЫ ЭФФЕКТИВНОГО КОДИРОВАНИЯ

Под кодированием понимают отображение состояний некоторой системы (источника сообщений) с помощью состояний сложного сигнала, который представляет собой последовательность из nэлементарных сигналов [11, 15].

Состояние сложного сигнала описывается последовательностью из нулей и единиц, которая называется кодовым словом. Если кодовые слова имеют разную длину, то код называется неравномерным, а если одинаковую, то код называется равномерным.

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

Методы сжатия данных были разработаны как математическая теория, которая до первой половины 80-х годов 20 века мало использовалась в компьютерной технике.

Методы или алгоритмы сжатия данных без потерь можно разделить на:

1.Статистические методы или алгоритмы. Например, методы Шеннона-Фано, Хаффмана и др.

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

2.Адаптивные методы или алгоритмы. Например, модифицированные коды Хаффмана, арифметическое кодирование и др.

20

Здесь распределение вероятностей символов сначала считается равномерным на заданном интервале, а потом оно меняется по мере накопления статистики.

3. Динамические методы или алгоритмы. Они являются универсальными и не нуждаются в априорной статистике. Например, метод Лемпела-Зива.

Основные информационные характеристики при кодировании:

При решении задачи сжатия естественным является вопрос, насколько эффективна та или иная система сжатия. Поскольку, в основном используется двоичное кодирование, то такой мерой может служить коэффициент сжатия r, определяемый как отношение

где dimA - размер алфавита данных A.

Таким образом, коэффициент сжатия r= 2 означает, что объем сжатых данных составляет половину от объема данных источника. Чем больше коэффициент сжатия r, тем лучше работает система сжатия данных.

21

Наряду с коэффициентом сжатия r эффективность системы сжатия может быть охарактеризована скоростью сжатия R, определяемой как отношение

R = k/n

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

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

Такое кодирование называется статистическим. Неравномерный код при статистическом кодирова-

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

2.1.Метод кодирования Шеннона - Фано

Другим простейшим способом статистического кодирования является кодирование по методу ШеннонаФано [19]. Кодирование в соответствии с этим алгоритмом производится так:

- сначала все буквы из алфавита сообщения записывают в порядке убывания их вероятностей;

22

-затем всю совокупность букв разбивают на две примерно равные по сумме вероятностей группы; одной из них (в группе может быть любое число символов, в том числе – один) присваивают символ «1», другой - «0»;

-каждую из этих групп снова разбивают (если это возможно) на две части и каждой из частей присваивают

«1» и «0» и т.д.

Процедура кодирования по методу Шеннона-Фано иллюстрируется табл.1.

Таблица 1 Процедура кодирования по методу Шеннона-Фано

̅ = ∑8=1 = =(0,25*2+0,25*2+0,15*3+0,15*3+0,05*4+0,05*4+0,05*4+

+0,15*4)=2,7 бит

23