Введение
1. Анализ алгоритмов быстрого преобразования фурье и циклической свертки, основанных на прямоугольных преобразованиях
1.1. Постановка задачи 15
1.2. Основные определения 20
1.3. Синтез алгоритмов быстрого преобразования Фурье и циклической свертки коротких последовательностей
1.3.1. Модульная арифметика полиномов 22
1.3.2. Синтез прямоугольных преобразований 25
1.3.3. Синтез алгоритмов быстрого преобразования Фурье на основе прямоугольных преобразований 29
1.4. "Гнездовой" алгоритм вычисления циклической свертки длинных последовательностей 36
1.5. Алгоритмы быстрого преобразования Фурье длинных последовательностей
1.5.I. Алгоритм с множителями поворота 38
1.5. 2.Алгоритм простых множителей 41
1.5.3. "Гнездовой" алгоритм Винограда 44
1.6. Сопоставление алгоритмов быстрого преобразования Фурье :
1.6.1. Объем вычислений 46
1.6.2. Объем памяти 48
1.6.3. Эфекты конечной разрядности 50
2. Новый метод синтеза прямоугольных преобразований
2.1. Теоретические основы предлагаемого метода
2.I.I. Свойство цикличности свертки
2.1.2. Транспозиция алгоритма
2.1.3. Метод решения системы линейных уравнений, когда уравнений больше, чем неизвестных 59
2.2. Синтез прямоугольных преобразований
2.2.1. Синтез матриц А и В
2.2.2. Вычисление матрицы С
2.2.3. Пример синтеза 72
2.3. Вопросы реализации предлагаемого метода на ЭВМ 76
2.4. Оценка мультипликативной сложности новых алгоритмов быстрого преобразования Фурье 82
3. Синтез прямоугольных прюбразований над алгебраичёсшми расширениями поля ращоналшых чисел
3.1. Введение алгебры над алгебраическими расширениями 90
3.2. Швод базового алгоритма 93
3.3. Оценка вычислительной сложности 95
3.4. Синтез прямоугольных преобразований над полем корней N-ой степени из единицы, где N -простое 98
3.5. Синтез прямоугольных преобразований над полем корней 8-ой степени из единицы 104
3.6. Оценка вычислительной сложности новых алгоритмов для преобразования многомерных последовательностей 106
3.7. Синтез прямоугольных преобразований над полем чисел Эйзенштейна 115
4. Синтез и анализ алгоритмов быстрого преобразования фурье для цифровых устройств сопряжения аналоговых и цифрошх систем періщачи
4.1. Применение дискретного преобразования Щурье в устройствах сопряжения 120
4.2. Разработка теоретических вопросов
4.2.1. Модификации алгоритма простых множителей для действительных и эрмитово-симметричных последовательностей 129
4.2.2. Анализ вычислительных ошибок алгоритма простых множителей в системе счисления с фиксированной запятой 136
4.2.3. Эффективная программная реализация умножений в алгоритмах быстрого преобразования Фурье коротких последовательностей 146
4.3. Синтез и анализ алгоритмов быстрого преобразования Фурье для N =14, 28, 72 и 144
4.3.1. Синтез базовых алгоритмов 150
4.3.2. Объем вычислений 163
4.3.3. Анализ вычислительных ошибок 163
4.4. Разработка процессораточечного быстрого преобразования Фурье для цифрового многоканального модема
4.4.1. Вычислительный алгоритм 1?2
4.4.2. Вычислительные ошибки. Выбор разрядности процессора 176
4.4.3. Моделирование процессора быстрого преобразования Фурье на ЭВМ 179
4.4.4. Описание работы процессора 183
4.4.5. Основные параметры процессора быстрого преобразования Фурье 190
4.5. Разработка эффективного алгоритма тактовой синхронизации цифрового многоканального модема 193
Выводы 198
Заключение 201
Литература 204
Приложения
