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

• Автор: Байкова, Аниса Талгатовна
• Шифр специальности: 05.12.02
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Ленинград
• Количество страниц: 265 c. : ил

1. АНАЛИЗ АЛГОРИТМОВ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ И ЦИКЛИЧЕСКОЙ СВЕРТКИ, ОСНОВАННЫХ НА ПРЯМОУГОЛЬНЫХ ПРЕОБРАЗОВАНИЯХ

1.1. Постановка задачи

1.2. Основные определения

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

1.3.1. Модульная арифметика полиномов

1.3.2. Синтез прямоугольных преобразований

1.3.3. Синтез алгоритмов быстрого преобразования Фурье на основе прямоугольных преобразований
1.4. "Гнездовой" алгоритм вычисления циклической свертки длинных последовательностей

1.5. Алгоритмы быстрого преобразования Фурье длинных последовательностей

1.5.1. Алгоритм с множителями поворота

1.5. 2.Алгоритм простых множителей

1.5.3. "Гнездовой" алгоритм Винограда
1.6. Сопоставление алгоритмов быстрого преобразования Фурье
1.6.1. Объем вычислений
1.6.2. Объем памяти
1.6.3. 3|)фекты конечной разрядности
Выв оды
2. НОВЫЙ МЕТОД СИНТЕЗА ПРЯМОУГОЛЬНЫХ ПРЕОБРАЗОВАНИЙ
2.1. Теоретические основы предлагаемого метода
2.1.1. Свойство цикличности свертки
2.1.2. Транспозиция алгоритма
2.1.3. Метод решения системы линейных уравнений,
когда уравнений больше, чем неизвестных
2.2. Синтез прямоугольных преобразований
2.2.1. Синтез матриц А и В
2.2.2. Вычисление матрицы С
2.2.3. Цример синтеза
2.3. Вопросы реализации предлагаемого метода на ЭВМ
2.4. Оценка мультипликативной сложности новых алгоритмов
быстрого преобразования Фурье
Вы в о д ы
СИНТЕЗ ПРЯМОУГОЛЬНЫХ ПРЕОБРАЗОВАНИЙ НАД АЛГЕБРАИЧЕСКИМИ РАСШИРЕНИЯМИ ПОЛЯ РАЦИОНАЛЬНЫХ ЧИСЕЛ
3.1. Введение алгебры над алгебраическими расширениями
3.2. Швод базового алгоритма
3.3. Оценка вычислительной сложности
3.4. Синтез прямоугольных преобразований над полем корней
N -ой степени из единицы, где N -простое
3.5. Синтез прямоугольных преобразований над полем корней 8-ой степени из единицы
3.6. Оценка вычислительной сложности новых алгоритмов
для преобразования многомерных последовательностей
3.7. Синтез прямоугольных преобразований над полем
чисел Эйзенштейна
Вы в о ды
СИНТЕЗ И АНАЛИЗ АЛГОРИТМОВ ШСГРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ ДЛЯ ЦИФРОВЫХ УСТРОЙСТВ СОПРЯЖЕНИЯ АНАЛОГОВЫХ И ЦИФРОВЫХ СИСТЕМ ПЕРЕДАЧИ
4.1. Применение дискретного преобразования Щурье в устройствах сопряжения
4.2. Разработка теоретических вопросов

4.2.1. Модификации алгоритма простых множителей для действительных и эрмитово-симметричных последовательностей
4.2.2. Анализ вычислительных ошибок алгоритма простых множителей в системе счисления с фиксированной запятой
4.2.3. Эффективная программная реализация умножений в алгоритмах быстрого преобразования Фурье коротких последовательностей
4.3. Синтез и анализ алгоритмов быстрого преобразования Фурье для N =14, 28, 72 и
4.3.1. Синтез базовых алгоритмов
4.3.2. Объем вычислений
4.3.3. Анализ вычислительных ошибок
4.4. Разработка процессора 144-точечного быстрого преобразования Фурье для цифрового многоканального модема
4.4.1. Вычислительный алгоритм
4.4.2. Вычислительные ошибки. Выбор разрядности процессора
4.4.3. Моделирование процессора быстрого преобразования Фурье на ЭВМ
4.4.4. Описание работы процессора
4.4.5. Основные параметры процессора быстрого преобразования Фурье
4.5. Разработка эффективного алгоритма тактовой синхронизации цифрового многоканального модема
Вы в о ды
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА

в работах /12,15,41,48/.
Алгоритмы Иули-Тыоки со смешанным основанием, как нетрудно определить по аналогии с алгоритмом Синглетона, требуют памяти объемом в
СЬ = 2М -1- Ч так Не,
{=1 V
АГВ /41,47/:
0.£ = 4 N ,
и АВ /41,48/:
Оз = 4 N + |-т +
слов.
Результаты подсчета требуемого объема памяти сведены в таблицу 1.4, где для сравнения приводятся данные для алгоритма Кули-Тьюки с основанием 2, объем памяти в случае реализации которого по схеме с замещением составляет /5/ О/, = 2.И слов.
Графическая иллюстрация полученных результатов приведена на рис. 1.3, откуда видно, что объем памяти, требуемый для алгоритмов 1^ули-Тьюки, АГВ и АВ, находится в соотношении, близком к
1:2: 5.2.
1.6.3. Эффекты конечной разрядности
В цифровых устройствах числа представляются с помощью конечного числа двоичных разрядов. Существует два основных вида представления чисел: с плавающей и фиксированной запятой.
Система счисления с плавающей запятой обеспечивает более высокую точность и гибкость вычислений, более широкий динамический диапазон входных данных. С другой стороны, она является более сложной с точки зрения аппаратурных затрат, менее быстродействующей и в основном реализуется в универсальных вычислительных системах.