Теория информации


Сжатие информации - часть 2


Подобное кодирование практически не реализуемо из-за того, что с ростом длины сообщения трудоемкость построения этого кода становится недопустимо большой. Кроме того, такое кодирование делает невозможным отправку сообщения по частям, что необходимо для непрерывных процессов передачи данных. Дополнительным недостатком этого способа кодирования является необходимость отправки или хранения собственно полученного кода вместе с его исходной длиной, что снижает эффект от сжатия. На практике для повышения степени сжатия используют метод блокирования.

По выбранному значению можно выбрать такое , что если разбить все сообщение на блоки длиной (всего будет блоков), то кодированием Шеннона-Фэно таких блоков, рассматриваемых как единицы сообщения, можно сделать среднее количество бит на единицу сообщения б\'ольшим энтропии менее, чем на . Действительно, пусть , , и т.д., т.е. . Тогда и , следовательно,

т.е. достаточно брать . Минимум по заданному может быть гораздо меньшим .

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

Минимальное кодирование здесь - это коды 0 и 1 с длиной 1 бит каждый. При таком кодировании количество бит в среднем на единицу сообщения равно 1. Разобьем сообщение на блоки длины 2. Закон распределения вероятностей и кодирование для 2-мерной д.с.в. -

Тогда при таком минимальном кодировании количество бит в среднем на единицу сообщения будет уже

т.е. меньше, чем для неблочного кодирования. Для блоков длины 3 количество бит в среднем на единицу сообщения можно сделать , для блоков длины 4 - и т.д.

Все изложенное ранее подразумевало, что рассматриваемые д.с.в. кодируются только двумя значениями (обычно 0 и 1). Пусть д.с.в. кодируются значениями. Тогда для д.с.в. и любого ее кодирования верно, что и . Кроме того, существует кодирование такое, что и , где .

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




- Начало -  - Назад -  - Вперед -



Книжный магазин