Существуют следующие пути преодоления трудностей реализации

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

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

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

В конце 60-x годов, 20 – го века, Колмогоровым была доказана возможность построения кодирования, получившего название универсального кодирования.

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

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

· Создание новых методов универсального кодирования.

· Разработка методики оптимального выбора длины исходных блоков.

· Разработка менее трудоемких способов нумерации кодовых элементов.

· Использование достижений современной элементной базы (флэш - технологии, ЭВМ на одном кристалле и т.д.).

В данной лекции рассмотрим результаты работы по созданию и исследованию конкретного метода универсального коди­рования (УК).

Одним из путей преодоления трудностей реализации являет­ся поиск новых методов нумерации элементов подмножеств, после разбиения всего множества исходных двоичных комбинаций по каким - либо признакам.

Допустим, что известны какой-либо параметры n - блока. В этом случае после исходного разбиения по признаку соответствия n - блока этим параметрам, в подмножествах окажется меньше элементов, чем 2ⁿ. Но тогда можно предполо­жить, что трудоемкость кодирования уменьшится, за счет уменьше­ния количества элементов в подмножествах и не будет носить экспоненциальный характер.

В связи с этим сформулируем метод УК и в дальнейшем исследуем его эффек­тивность и трудоемкость.

Пусть источник порождает последовательность статистически независимых символов «1» и «0» с вероятностями p и q, нам неизвестными.

Разобьем всю последовательностьдвоичных символов,порождаемуюисточником наблокидлиной n (n -блоки).

Под избыточностью, приходящейся на символ исходнойпоследова­тельности,будем понимать величину:

Rn (p) = n_ср /n - Н (p), где (1)

n_ср - средняя длина кодового слова - это

сумма произведений всехвозможных кодовых слов на вероятности их появления.

Н (p) - энтропия источника, минимальная теоретически возможная избыточность:

Н (р) =-(plog₂p+q log₂q)

Качество кодирования будет определяться величиной R_n ­- избыточностью кодирования:

R_n = Sup R_n (p), где 0‹p‹1 (2).

Данный код является универсальным, если для него выполняется условие:

ℓim R_n = 0 (3).

n → ∞

Дата добавления: 2014-01-13