11.5. Теоретико-числовое преобразование Хартли

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

В конечных полях в предыдущих разделах была показана перспективность построения конструкций ТЧП в позволяющих синтезировать экономичные (по сравнению с БПФ) быстрые алгоритмы. Однако вычисления в подобны вычислениям в комплексной арифметике, что не экономично при обработке вещественных сигналов. В связи с этим представляет интерес задача построения аналога ДПХ в теоретико-числовой области.

Пусть задана пара ТЧП в простое Мерсенна) с первообразным корнем а

Определим расширенную конструкцию ТЧП в виде

где

Пусть где Положим коэффициенты равными соответственно

Предположим также, что да, при котором

Тогда

Преобразование типа можно определить как теоретико-числовое преобразование Хартли (ТЧПХ), так как оно аналогично по конструкции дискретному преобразованию Хартли (2.44). Согласно (11.33) и (11.34) пара преобразований ТЧПХ имеет вид

Переход между обычным ТЧП и ТЧПХ определяется выражениями

где

Через тчпх можно определить циклическую свертку двух сигналов согласно выражению

где

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

Как отмечалось выше, для построения ТЧПХ необходимо, чтобы корень удовлетворял условию Возможность существования таких корней определяется из следующей теоремы

Теорема 11.2. Уравнение имеет решений, если решений, если

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

Рассмотрим теперь какова максимальная размерность преобразования, для которого возможно построение ТЧПХ. Пусть в задан элемент степени которого образуют мультипликативную группу Из [5] мы уже приводили следующий результат:

Согласно [5] такой элемент может быть определен из условия (11.19).

Определим новый элемент тогда Следовательно, степени элемента образуют мультипликативную группу Определим теперь

Таким образом, максимальная размерность ТЧПХ может быть равной при этом первообразный корень выбирается исходя из (11.19) согласно условиям

Далее степени и а определяют как

Рассмотрим пример. Пусть тогда согласно теореме 11.2 существует 32 корня а, таких, что В табл. 11.3 приведены такие значения.

Элемента согласно (11.38) равен

Согласно сказанному, для возможно построить ТЧПХ с

Таблица 11.3 (см. скан)

максимальной размерностью При этом первообразный корень Теперь пусть нам необходимо построить ТЧПХ размерностью Для этого определим корень восьмой степени а как т.е. отсюда Преобразование в этом случае имеет вид

Легко проверить, что

Так как ТЧПХ по своей структуре аналогично ДПХ, то очевидно, что для него полностью применима теория построения быстрых алгоритмов преобразования Хартли, рассмотренная в гл. 3, 9.

Например, матричное выражение факторизации ТЧПХ по основанию 2 имеет вид

где

На рис. 11.6 приведен граф БПХ для алгоритма (11.39). Так как то базовый корень может быть факторизовано по основанию 4. В этом случае получаем следующее матричное выражение для алгоритма

где

Рис. 11.6. Теоретико-числовое преобразование Хартли в быстрый алгоритм по основанию 2)

Алгоритм (11.40) удобнее реализовать в более симметричной форме, а именно:

Граф такого алгоритма БПФ изображен на рис. 11.7 (базовый элемент

(кликните для просмотра скана)

По аналогии с (9.25) для ТЧПХ может быть синтезирован быстрый алгоритм с расщепленным основанием.

На рис. 11.8 приведен граф такого алгоритма для Число арифметических операций для ТЧПХ по основанию 2 равно

или с учетом факторизации вида

модифицированное число операций равно

Аналогично для алгоритма ТЧПХ по основанию 4 имеем

или с учетом факторизации (11.41)

Для алгоритма ТЧПХ с расщепленным основанием получаем следующие оценки:

или с учетом факторизации (11.41)

При обработке комплексных сигналов не требуется структурная перестройка ядер ТЧПХ. Оценка числа арифметических операций в этом случае удваивается.