ИННОВАЦИИ БИЗНЕСУ

Номер

19-019-03

Наименование проекта

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

Назначение

Реализация эффективного вычисления кумулятивных частот (вероятностей) сообщений для арифметического кодера

Рекомендуемая область применения

Программно-аппаратные средства компрессии цифровой информации

Описание

Результат выполнения научно-исследовательской работы.

Арифметическое кодирование потока сообщений обычно требует подсчета их кумулятивных (накапливающихся) частот на каждом шаге кодирования. Предлагается алгоритм сложности , где - мощность алфавита сообщений. Используется одномерный массив частот сообщений, где . Массив инициализируется значениями, вычисленными рекурсивной функцией:

где - начальное значение счетчика -го сообщения, следующим образом: , .

Быстрый алгоритм вычисления суммы текущих частот вида , , т.е. кумулятивной частоты -го сообщения:

Алгоритм изменения связанных с -м сообщением элементов массива частот:

Как видно из приведенного выше описания, алгоритмы и легко объединить.

Объем используемой памяти m=2 n-1, где n - ближайшая сверху к мощности алфавита сообщений целая степень числа 2.

Вычислительная сложность: o( log2n).

Преимущества перед известными аналогами

Низкая вычислительная сложность алгоритма

Стадия освоения

Внедрено в производство

Результаты испытаний

Технология обеспечивает получение стабильных результатов

Технико-экономический эффект

Снижение затрат времени центрального процессора ЭВМ на 30%

Возможность передачи за рубеж

Возможна передача за рубеж

Дата поступления материала

28.02.2003