Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
11. БЫСТРЫЕ АЛГОРИТМЫ ТЕОРЕТИКО-ЧИСЛОВЫХ ПРЕОБРАЗОВАНИЙПусть задана пара ТЧП согласно (2.29)
удовлетворяющая условиям (2.25). Тогда структура матриц Таким образом, для факторизации матриц 11.1. Алгоритмы ТЧП по основанию r по модулю простых чисел ФермаПусть задана пара
Очевидно, что наиболее привлекательным является выбор В то же время, как было показано выше, размерность ТЧП N может быть гораздо большей и достигать Рассмотрим различные варианты быстрых алгоритмов ТЧП Ферма (ТЧП-Ф) и определим для них оценки числа арифметических операций. Таблица 11.1 (см. скан) 11.1.1. Алгоритмы ТЧП-Ф по основанию 2. Матричное выражение алгоритма ТЧП по основанию 2 с прореживанием до частоте
где Для таких алгоритмов ТЧП-Ф последние
т.е. умножение на нечетные степени С учетом сказанного общее число арифметических операции для алгоритмов ТЧП данного класса равно
Например, при
Для сравнения минимальное число арифметических операций в алгоритмах БПФ при обработке вещественного сигнала равно (гл 8)
11.1.2. Алгоритмы ТЧП-Ф по основанию 4. Матричное выражение для алгоритма ТЧП-Ф по основанию X с замещением и прореживанием по частоте имеет вид
где
Как и в предыдущем случае, возможно построение алгоритмов ТЧП-Ф по основанию 4 с замещением типа Для данного класса алгоритмов ТЧП-Ф получаем следующие оценки числа вещественных арифметических операций:
где
11.1.3. Алгоритмы ТЧП-Ф по основанию ... Матричное выражение алгоритма ТЧП-Ф по основанию
где С учетом (11.2) элементыв матрицах
Предположим, что удовлетворяющие сравнению
Тогда, подставляя (11.11) в (11.10) изатемв (11.9), получаем
Следовательно,
Очевидно, что так как Покажем, что сравнение (11.12) разрешимо и имеет Теорема 11.1. Пусть Для нашего случая имеем
Таким образо, (11.11) разрешимо и имеет 1) для 2) для Остальные первообразные корни, удовлетворяющие (11.11), определяются по формуле
Приведем пример для случая, когда
где
На рис. 11.1 приведена структурная схема данного алгоритма ТЧП-Ф. Число умножений в такой структуре равно Аналогичная конструкция разбиения на блоки возможна и для двумерного ТЧП-Ф
Рис. 11.1. Алгоритм ТЧП-Ф по основанию
Рис. 11.2. Алгоритм двумерного ТЧП-Ф по основанию Число арифметических операций для такого алгоритма равно
На рис. 11.2 приведена структурная схема алгоритма (11.16) для случая
|
1 |
Оглавление
|