Основные особенности алгоритма двоичного арифметического кодирования

ОСНОВНЫЕ ОСОБЕННОСТИ АЛГОРИТМА ДВОИЧНОГО АРИФМЕТИЧЕСКОГО КОДИРОВАНИЯ

Значительный рост информационных потоков данных характеризует современный этап развития общества. В настоящее время, методы сжатия данных, для их передачи и хранения, приобретают важный практический и коммерческий интерес. Разработаны различные способы и алгоритмы обработки сигналов, применение которых позволяет уменьшить ресурсы при хранении и передаче данных[1-2].

В настоящее время актуальной задачей является кодирование и декодирование различных информационных потоков. Одними из основных классов аппаратно-реализуемых алгоритмов сжатия данных является методы арифметического кодирования. К данным методам относится алгоритм двоичного арифметического кодирования (Binary Arithmetic Coding Algorithm[3]).

Проведенный анализ показал, что известные средства двоичного арифметического кодирования/декодирования(кодеки) не в полной мере соответствует современным требованиям как по скорости кодирова- ния/декодирования, так и по степени сжатия данных.

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

С целью выявления основных особенностей схемы двоичного арифметического кодирования проведен анализ алгоритма кодирования/декодирования. Алгоритм описан стандартом ЕСМА-159 (декабрь 1991г.). Стандарт описывает блочное сжатие. Каждый информационный пакет входного потока разбивается на блоки данных по 512 байт. Блоки последовательно подаются на вход одному из 8 компрессоров. Результаты сжатия объединяются в той же последовательности. Каждый из 8 компрессоров является независимым друг от друга. Они сбрасываются в первоначальное состояние после каждого кодирования/декодирования. Алгоритм двоичного арифметического кодирования, при обработке текущего блока данных, формирует кодовые слова, генерирует и модифицирует таблицу переходов и вероятностей. В зависимости от режима запуска таблица может быть заблокирована для изменений, тогда компрессор будет использовать последние состояние.

В ходе анализа сжатого потока были выявлены следующие особенности:

Каждый сжатый информационный блок завершается меткой кон- ца(1111 1111 1ЮОЬ или 1111 1111 1001b) и, если необходимо выравнивание, нулевыми битами до размера кратного четному числу байт;

Начало информационного блока данных определяется по наличию метки конца предыдущего блока.

Синхронизация кодера и декодера происходит а начале каждого информационного блока, т.к. компрессоры являются независимыми;

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

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

Вывод.

Решение задачи создания кодеков двоичного арифметического кодирования требует учета всех выявленных особенностей с целью повышения эффективности кодирования/декодирования данных с его использованием. Высокая сложность используемых структур данных и преобразований при сжатии информации требует использования адекватного ситуации структурно-алгебраического подхода на основе метаграмматик[4-6].

Список литературы

Потапенко, А.М. Приложение графов к исследованию сетевых структур в телекоммуникациях: учеб, пособие/ А.М. Потапенко, Р.А. Томакова, М.В. Томаков; Курск, гос. техн. ун-т Курск, 2010. 148с.

Томакова, Р.А. Гибридные технологии выделения медленных волн из квазипе- риодических сигналов/Р.А. Томакова, М.А. Ефремов, С.А. Филист, О.В. Шаталова// Известия Юго-Зап. гос. ун-та. 2011. №1(34). - С.66-73.

Standard ЕСМА-159, «Data compression for information interchange - Binary Arithmetic Compression Algorithm», December 1991

Атакищев, О.И. Метаграмматики и особенности их применения для формального описания сигналов и протоколов документальных служб связи и передачи данных Ч. Е Метаграмматики. Основные понятия и определения [Текст] / О.И. Атакищев // Телекоммуникации. 2001. №10

Атакищев, О.И. Метаграмматики и особенности их применения для формального описания сигналов и протоколов документальных служб связи и передачи данных. Часть 2. Классификация метаграмматик // Телекоммуникации. 2001. № 12, 2 - 8с

Атакищева, И.В. Эталонная модель двойственно-атрибутной транслирующей метаграмматики и структурно-лингвистический способ обработки сложноорганизованных данных [Текст]/ И.В.Атакищева, С.Г. Емельянов, В.Ю.Мудрик [и др.]//Известия Тульского государственного университета. Серия Технологическая системати- ка.Вып.14-Тула:Изд-во ТулГУ,2006.-С.24-28.

УДК: 004.00

Количество показов: 854