9. БЫСТРЫЕ АЛГОРИТМЫ ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ХАРТЛИ

Как было показано в гл. 2, дискретное преобразование Хартли (ДПХ) принадлежит к классу дискретного преобразования Фурье и может быть использовано для спектрального анализа и цифровой фильтрации (вычисление циклической свертки) Причем для этих задач ДПХ имеет перед ДПФ ряд преимуществ. Это — "вещественность" всей арифметики, если входной сигнал принадлежит к полю вещественных чисел. Вторым достоинством ДПХ является идентичность прямого и обратного ДПХ, т.е. что особенно полезно при обработке вещественных сигналов. При обработке вещественных сигналов с помощью безубыточных алгоритмов БПФ

(гл. 8,) такое свойство, к сожалению, не выполняется, что требует применения различных алгоритмов прямого и обратного преобразований.

Впервые на возможность применения дискретного преобразования Хартли для спектрального анализа и фильтрации сигналов указал Брэйсуэлл . Он же рассмотрел основы факторизации ДПХ для получения быстрых алгоритмов [2]. После этого появился ряд работ, посвященных цифровой обработке сигналов на основе ДПХ [3—10] и одновременно вопросам построения быстрых алгоритмов преобразования Хартли Все эти работы в основном рассматривают методы построения алгоритмов БПХ по основанию 2. Более общей является работа [18], где приведено выражение для общего случая факторизации ДПХ на два множителя однако выражение, приведенное авторами, является сложным и структурно неудобным для рекуррентной факторизации. К сожалению, до сих пор нет ни одной работы, рассматривающей факторизацию ДПФ в матричном виде. Это сдерживает, в свою очередь, построение единых методик синтеза алгоритмов БПХ.

В гл. 3 было показано, что возможны две базовые формы факторизации

1. Для произвольных множителей

где — матрица цифроинверсных перестановок по основанию - матрицы соответственно размерностей матрица весовых коэффициентов, определяемая согласно (3.36).

2. Для взаимно-простых множителей

где матрицы перестановок, определяемые правилами

в (9.1) и (9.2) приведены частные случаи факторизации когда

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