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

Рассматривается задача кодирования источников информации с известными и неизвестными априори вероятностями порождения символов. Для обоих случаев исследуется сложность кодирования и декодирования в зависимости от избыточности $r$, определяемой как разность между средней длиной кода и энтропией. Известные методы кодирования разбиваются на два класса: для кодов одного из них при уменьшении избыточности $r$, $r\to 0$ память $S$ и среднее время кодирования и декодирования одного символа $T$ растут как $O(\exp(1/r))$ и $O((-\log r))$ соответственно (при реализации кодера и декодера на компьютере). Для других кодов $S=O(r^{-\rm{const}})$, $T=O(r^{-\rm{const}})$ при $r\to 0$. В работе предлагается метод, объединяющий достоинства обоих классов кодов: при уменьшении избыточности $r$ память растет как степенная функция от $1/r$, а время кодирования и декодирования не превосходит степенную функцию от $-\log r$:$S=O(r{-\rm{const}})$, $T=O(r^{-\rm{const}})$ (В этой статье во всех случаях const – некоторое число, не меньшее 1.) Этот же метод используется для построения быстрого нумерационного кодирования (см. определение в [1,2]).