11. БЫСТРЫЕ АЛГОРИТМЫ ТЕОРЕТИКО-ЧИСЛОВЫХ ПРЕОБРАЗОВАНИЙ

Пусть задана пара ТЧП согласно (2.29)

удовлетворяющая условиям (2.25). Тогда структура матриц и аналогична структуре матриц и с учетом определения их в соответствующем конечном поле (кольце) (см. табл. 11.1).

Таким образом, для факторизации матриц применима теория, изложенная в гл. 3—10. Однако, как будет показано ниже, при факторизации матриц (аналогично существуют некоторые особенности, позволяющие получить быстрые алгоритмы с существенной экономией числа арифметических операций по сравнению с алгоритмами БПФ соответствующих классов.

11.1. Алгоритмы ТЧП по основанию r по модулю простых чисел Ферма

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

Очевидно, что наиболее привлекательным является выбор (известно как ТЧП Рейдера [1]). При этом операция умножения на весовые коэффициенты заменяются операциями циклического сдвига. Однако при таком выборе а максимальный размер преобразования жестко связан с длиной разрядной сетки и модулем и равен

В то же время, как было показано выше, размерность ТЧП N может быть гораздо большей и достигать но при этом возникают нетривиальные умножения в процессе вычислений.

Рассмотрим различные варианты быстрых алгоритмов ТЧП Ферма (ТЧП-Ф) и определим для них оценки числа арифметических операций.

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

11.1.1. Алгоритмы ТЧП-Ф по основанию 2. Матричное выражение алгоритма ТЧП по основанию 2 с прореживанием до частоте и с замещением имеет

где Транспонирование (113) дает алгоритм с прореживанием по времзни Аналогично (5 7) выражение (11.3) может быть преобразовано в алгоритм с постоянной структурой типа или

Для таких алгоритмов ТЧП-Ф последние этапов не требуют умножений, так как весоьые коэффициенты будут равны степени двоики Кроме того, на этапе появляются весовые коэффициенты типа которые могут быть представлены в виде [2]

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

С учетом сказанного общее число арифметических операции для алгоритмов ТЧП данного класса равно

Например, при имеем

Для сравнения минимальное число арифметических операций в алгоритмах БПФ при обработке вещественного сигнала равно (гл 8)

11.1.2. Алгоритмы ТЧП-Ф по основанию 4. Матричное выражение для алгоритма ТЧП-Ф по основанию X с замещением и прореживанием по частоте имеет вид

где

Как и в предыдущем случае, возможно построение алгоритмов ТЧП-Ф по основанию 4 с замещением типа и с постоянной структурой типа или

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

где наименьшее четное число от Например, при получаем

11.1.3. Алгоритмы ТЧП-Ф по основанию ... Матричное выражение алгоритма ТЧП-Ф по основанию (форма с замещением) имеет вид [3]

где

С учетом (11.2) элементыв матрицах равны

Предположим, что удовлетворяющие сравнению

Тогда, подставляя (11.11) в (11.10) изатемв (11.9), получаем

Следовательно, в (11-9) являются преобразованиями Рейдера и, таким образом, не требуют операций умножения. В этом случае число арифметических операций равно

Очевидно, что так как то для больших алгоритм (11.9) является гораздо более экономичным, чем быстрые алгоритмы ТЧП по основанию 2 и 4.

Покажем, что сравнение (11.12) разрешимо и имеет решений. Это следует из следующей теоремы [4].

Теорема 11.1. Пусть тогда необходимое и достаточное условие разрешимости сравнения есть причем в случае разрешимости указанное сравнение имеет решений.

Для нашего случая имеем Так как то Так как то Кроме того, Отсюда проверочное условие имеет вид

Таким образо, (11.11) разрешимо и имеет решений. Численные оценки дают следующие решения (11.11):

1) для имеем

2) для имеем

Остальные первообразные корни, удовлетворяющие (11.11), определяются по формуле

Приведем пример для случая, когда Тогда

где

На рис. 11.1 приведена структурная схема данного алгоритма ТЧП-Ф. Число умножений в такой структуре равно т.е. меньше одного на отсчет. Причем для и для

Аналогичная конструкция разбиения на блоки возможна и для двумерного ТЧП-Ф

Рис. 11.1. Алгоритм ТЧП-Ф по основанию размерностью

Рис. 11.2. Алгоритм двумерного ТЧП-Ф по основанию размерностью

Число арифметических операций для такого алгоритма равно

На рис. 11.2 приведена структурная схема алгоритма (11.16) для случая