Статья

Название статьи О ПАРАЛЛЕЛЬНОЙ ФОРМЕ ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ
Автор Я.Е. Ромм, В.В. Забеглов
Рубрика РАЗДЕЛ II. АЛГОРИТМИЧЕСКОЕ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ
Месяц, год 05, 2010
Индекс УДК 519.6: 681.3
DOI
Аннотация Изложена схема параллельного выполнения дискретного преобразования Фурье (ДПФ). Схема включает вычисление базиса ДПФ на основе кусочно-полиномиальной аппроксимации функций с помощью интерполяционного полинома Ньютона. При произвольно заданной априори границе погрешности временная сложность вычисления базиса составляет O(1). Параллельное выполнение ДПФ, включая вычисление базиса, оценивается временной сложностью O(log2N).

Скачать в PDF

Ключевые слова Дискретное преобразование Фурье.
Библиографический список 1. Аксайская Л. Н. Разработка и исследование параллельных схем цифровой обработки сигналов на основе минимизации временной сложности вычисления функций / Автореферат диссертации на соискание ученой степени кандидата технических наук. – Таганрог: ТТИ ЮФУ. – 2008. – 18 с.
2. Ахмед Н., Рао К.Р. Ортогональные преобразования при обработке цифровых сигналов: Пер. с англ. Т.Э. Кренкеля / Под ред. И.Б. Фоменко. – М.: Связь, 1980. – 248 с.
3. Миклошко Й. Связь между алгоритмами, программами и структурой параллельных ЭВМ. – В кн.: Алгоритмы математического обеспечения и архитектура многопроцессорных вычислительных систем / Под ред. А.П. Ершова. – М.: Наука, 1982. – С. 6-36.
4. Ромм Я.Е. Бесконфликтные и устойчивые методы детерминированной параллельной обработки / Дис… д-ра техн. наук. – Таганрог: ТРТУ, 1998. – 546 с.; ВНТИ Центр. – № 05.990.001006.
5. Ромм Я.Е. Локализация и устойчивое вычисление нулей многочлена на основе сортировки. II // Кибернетика и системный анализ. – 2007. – № 2. – C.161-174.
6. Солодовников В.И. Верхние оценки сложности решения систем линейных уравнений // Теория сложности вычислений. 1: Записки научных семинаров ЛОМИ АН СССР. – Л., 1982. – Т. 118. – С. 159-187.

Comments are closed.