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

• Автор: Селезнев, Михаил Евгеньевич
• Шифр специальности: 05.13.05
• Научная степень: Кандидатская
• Год защиты: 2000
• Место защиты: Курск
• Количество страниц: 223 с. : ил.

Глава 1. Глава 2. Винограда вычисления свертки и ДПФ. Выводы 8 7

Глава 3. Глава 4. ПРИЛОЖЕНИЕ 8

Алгоритм КулиТьюки быстрого преобразования Фурье имеет хорошую структурированность и поэтому удобен для реализации на вычислительных устройствах различного типа. Недостатком этого алгоритма является то, что эффективная эго реализация возможна только при длинах последовательностей, равных степеням двойки. Поэтому вследствие широкой распространенности этого алгоритма установилось мнение, что эффективное вычисление ДПФ возможно только на таких последовательностях, что не является верным. Кроме того, существуют алгоритмы 5ПФ, намного эффективнее с точки зрения числа операций умножения и сложения. Другой широко известный, но мало популярный алгоритм быстрого преобразования Фурье алгоритм Винограда . Алгоритм Винограда для быстрого преобразования Фурье малой длины относится к алгоритмам БПФ, основанным на сведении ДФ к сверке и основывается на двух идеях. Дискретное преобразование Фурье сводится к свертке с помощью алгоритма Рейдера.

Преобразование Фурье здесь записано в виде циклической свертки по

следовательностей V1 у и со . Далее свертка вычисляется с помощью алгоритма Винограда для коротких сверток. Виноградом разработан алгоритм для вычисления преобразования Фурье большой длины . Он представляет собой метод эффективного вычисления дискретного преобразования Фурье, если длина л преобразования распадается в произведение взаимно простых делителей, для которых существуют малые БПФалгоритмы Винограда. Идея этого алгоритма состоит в том, что одномерное ДПФ согласно китайской теореме об остатках преобразуется в многомерное, затем многомерное ДПФ вычисляется с помощью гнездового метода. Большой ВПФалгоритм Винограда по числу умножений в 4 6 раз эффективнее алгоритма КулиТьюки, но имеет сложную структуру. Поэтому он не нашел широкого применения. Существуют алгоритмы, специально разработанные для вычисления многомерных преобразований Фурье. Один из эффективных алгоритмов построен с помощью полиномиального представления расширения полей и носит название перестановочного алгоритма НуссбаумераКвенделла ,. Он строится сведением многомерного преобразования к вычислению некоторого количества одномерных преобразований Фурье. Недостатком его является то, что он применим только тогда, когда многомерное преобразование имеет одинаковую длину по всем измерениям или когда все длины имеют общий множитель, так что можно применить китайскую теорему об остатках. Для обработки и анализа дискретных сигналов могут быть успешно использованы ортогональные преобразования, отличные от преобразования Фурье .