Параметрический вариант быстрого преобразования Фурье тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

Просеков Олег Валерьевич

ПАРАМЕТРИЧЕСКИЙ ВАРИАНТ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (МНОГОМЕРНЫЙ СЛУЧАЙ)

01 01 07 — вычислительная математика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Работа выполнена на ффедре исследования операций

математико-механического факультета Санкт-Петербургского Государственного Университета

НАУЧНЫЙ РУКОВОДИТЕЛЬ !

доктор физико-математических наук, профессор Малоземов Василий Николаевич

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ

доктор физико-математических наук, профессор Рябов Виктор Михайлович,

кандидат физико-математических паук Третьяков Алексей Андреевич

ВЕДУЩАЯ ОРГАНИЗАЦИЯ

Санкт-Петербургский Государственный Электротехнический Университет «ЛЭТИ» имени В И Ульянова (Ленина)

Защита состоится 21 февраля 2008 г в 13 часов на заседании диссертационного совета Д 212 232 49 по защите диссертаций на соискание ученой степени доктора наук при Санкт-Петербургском Государственном Университете по адресу 198504, Санкт-Петербург, Старый Петергоф, Университетский пр , д 28, математико-механический факультет, ауд 405

С диссертацией можно ознакомиться в Научной библиотеке им М Горького Санкт-Петербургского государственного университета по адресу 199034, Санкт-Петербург, Университетская наб , 7/9

Автореферат разослан января 2008 г

Ученый секретарь 0 р

диссертационного совета, профессор О—' А А Архипова

Общая характеристика работы

Актуальность темы. Быстрые алгоритмы играют важную роль при обработке дискретных периодических сигналов, особенно в многомерном случае Наиболее популярным и по-прежнему востребованным является быстрое преобразование Фурье (БПФ) Отметим, что теория БПФ далеко не проста Классическими трудами по БПФ стали книги Макклеллана и Рейдера, Блейхута, Нуссбаумера

Ключевой работой в теории БПФ явилась работа Кули и Тьюки 1965 года Немаловажную роль в то время сыграло развитие вычислительных средств В работе Кули и Тьюки приводится время работы реализации трехмерного БПФ на «новых» тогда ЭВМ IBM 7094 С тех пор интерес к БПФ не угасает В известном обзорном отчете Барраса 1997 года упоминается более 3400 работ по БПФ Большая часть из них — это работы, связанные с вычислительными аспектами БПФ и вопросами реализации БПФ на различных архитектурах ЭВМ Вопрос о быстродействии стоит очень остро в связи с обработкой сигналов в реальном времени, а дискретное преобразование Фурье (ДПФ) является базовой операцией для других алгоритмов, и быстродействие системы в целом сильно зависит от эффективной реализации БПФ Типичные приложения — это цифровые устройства связи, аудио- и видеоустройства

Несмотря на то, что эффективные алгоритмы БПФ существуют для практически любых длин периодов, длина, равная степени двойки, остается самой популярной В этом случае БПФ достаточно легко реализуется, и основной вычислительный модуль «бабочка» задается всего несколькими инструкциями Более сложный по реализации, но более эффективный алгоритм БПФ «split-radix» позволяет сократить число вещественных арифметических операций на 20%, а алгоритм, описанный в новой работе Фриго и Джонсона 2007 года, — еще примерно на 6%

Различные алгоритмы БПФ зависят от арифметических свойств длины периода сигнала Если эта длина — число составное, то используется алгоритм Кули-Тьюки В случае, когда длина сигнала может быть представлена в виде произведения попарно взаимно простых чисел, применим алгоритм простых множителей, разработанный Гудом в 1958 году В вычислительном отношении алгоритм простых множителей проще алгоритма Кули-Тьюки

Если длина сигнала является простым числом, то можно воспользоваться алгоритмом Рейдера В этом случае задача вычисления ДПФ сводится к задаче вычисления циклической свертки Эффектное применение этой идеи нашел Виноград для вычисления ДПФ небольшой длины Задача быстрого вычисления циклической свертки решается с помощью полиномиальной техники По сути, метод Винограда дает разложение матрицы Фурье малого порядка в произведение трех матриц — матрицы предсложений, диагональной

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

Идея факторизации матрицы Фурье представляется наиболее перспективной Общий подход к построению быстрых алгоритмов связан с разложением матрицы Фурье в произведение слабо заполненных матриц Поскольку такие разложения не единственны, возникает возможность выбора наилучших в некотором смысле разложений Впервые на базе кронекерова умножения матриц факторизация матрицы Фурье была получена в работе Пиза 1968 года В этой статье рассматривался вопрос о параллельных вычислениях Позже в 1979 году Корном и Ламбиотом были получены факторизации матрицы Фурье, ориентированные на векторные вычисления

В теории быстрых ортогональных преобразований важную роль играют перестановки Обычно перестановки особым образом изменяют порядок входных или выходных отсчетов сигнала Это не всегда удобно Алгоритмы, не требующие перестановки данных до или после преобразования, получили название «БеК-Бог^гщ» Впервые такой алгоритм БПФ был получен Стокхемом в 1967 году Другой алгоритм, основанный на факторизации матрицы Фурье, был разработан Глассманом Детально такие алгоритмы рассмотрены в обзорной работе Темпертона 1983 года

Особенно эффективно идея БПФ работает в многомерном случае Традиционно используют построчно-столбцевой метод В этом методе для каждой размерности применяется соответствующий одномерный алгоритм БПФ Более эффективный двумерный алгоритм, похожий на алгоритм Кули-Тьюки, предложил Райворд в 1977 году Использовать полиномиальные преобразования для вычисления ДПФ предложили Нуссбаумер и Квенделл Другой алгоритм с похожими характеристиками получили Ауслендер, Фейг и Виноград Варианты БПФ основываются на разных представлениях (кодировании) индексов сигнала Смешанный код используется в методе Кули-Тьюки (если длина периода равна степени двойки, то это бинарный код) Китайский и руритаский коды — в методе простых множителей М Б Свердлик в своих работах середины 1980-х годов предложил обобщенное представление индексов, связанное с введении вектора параметров Это послужило основой для параметрической факторизации матрицы Фурье

Цель работы.

1) Исследование различных вариантов факторизации матрицы Фурье на базе кронекерова умножения матриц

2) Разработка общего подхода к вычислению ДПФ, основанного на параметрическом кодировании индексов

3) Построение параметрического алгоритма БПФ в многомерном случае

4) Получение более детальной факторизации матриц Фурье малых порядков

Методика исследования В диссертационной работе использовался математический аппарат дискретного гармонического анализа и матричной алгебры

Научная новизна В диссертации получены следующие основные результаты

1) Выведены рекуррентные соотношения для матриц реверсных перестановок и на этой основе получены четыре факторизации таких матриц

2) Получена наиболее глубокая параметрическая факторизация матрицы Фурье Попутно указаны факторизации матриц параметрических перестановок

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

4) Разработан параметрический алгоритм БПФ в многомерном случае для произвольной матрицы параметров

5) Усовершенствованы факторизации матриц Фурье малых порядков 3,4,5,6,7,8,9,10,11,12 и 16

Практическая ценность. Работа носит теоретический характер Построена параметрическая теория БПФ С точки зрения реализации все полученные результаты ориентированны на параллельные и векторные вычисления Это особенно актуально в связи с развитием современных технологий Результаты диссертации могут быть использованы в цифровой обработке сигналов, например, для быстрого формирования характеристик направленности антенных решеток

Апробация работы и публикации. По результатам диссертации сделаны доклады на семинаре кафедры исследования операций мат-мех факультета СПбГУ, на семинаре по дискретному гармоническому анализу и геометрическому моделированию (ВНА & САСБ), на седьмой международной конференции «Прикладные технологии гидроакустики и гидрофизики» (Санкт-Петербург, 8-10 июня 2004 г) Некоторые результаты диссертации внедрены в

«Концерн «Океанприбор» при разработке цифровых гидроакустических комплексов По теме диссертации опубликовано семь работ В совместных работах [1, 3-5] научному руководителю принадлежит общая постановка задач и указание на идею исследования, а детальная реализация идеи полностью принадлежит диссертанту В совместной работе [2] С Н Пахомов обосновал алгоритм быстрого вычисления ревеверсных перестановок Работы [1, 2] опубликованы в издании по перечню ВАК

Структура и объем работы. Диссертация состоит из введения, 9 параграфов, списка литературы и одного приложения Объем диссертации — 118 страниц Список литературы насчитывает 51 наименование В диссертации имеется 1 рисунок и 1 таблица

Содержание работы

Во введении дан краткий исторический обзор и сформулированы основные результаты диссертации

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

Во втором параграфе рассматривается вопрос о факторизации матриц реверсных перестановок Пусть $ и ni,n2, ,ns — натуральные числа, отличные от единицы Введем обозначения

N = П\П2 ns ,

Д„ = П\П2 nv-1 при V € 2 s + 1, Ai = 1, Nv = nu+in„+2 ns при I/ GO s — 1, Ns = 1

Очевидно, что N0 = N и ¿S.vnvNv — N при всех v £ 0 s Любое число г б О N — 1с помощью последовательного деления можно единственным образом представить в виде

s

г = г3(пв-1 т) + г3-1 (ns_2 т) + + г2 rix +1\ = У^ К ,

v=l

где iv € 0 nv — 1 Коэффициенты г^ этого разложения образуют смешанный код числа г, г = (г8, ii)n„

Реверсная перестановка связана с переворачиванием смешанного кода целых неотрицательных чисел

Г6Vni)7,2 yns ((i5, 2s_i, , il)ra,,na-i, ~ C®li i 's)ni П2, ,ns

Матрица реверсных перестановок определяется так Revnun2, ,„.[»,j] =

10 в остальных случаях

Отметим, что (Rev„b„2, ,Пв)Т = Revns,„s_u

В диссертации получены четыре варианта факторизации матриц реверсных перестановок

ТЕОРЕМА 2.2 Справедливы разложения

S—1

Revni,n2, ,п. = П(7л" ® Rev"' W

г/=1 з

Revnii„2, ,„s = J]_(In„ О RevA„,n„), (2)

«/=2 а-1

Revni

= П(йеуп,_1/,Л-._„®-?'д,-„), (3)

е=1 е-2

Revnun2, ,n, = П(Яеуд5_„,„,_„ <g> 7jv,_„) , (4)

¡/=0

где <g) — операция кронекерова умножения и In — единичная матрица порядка N

В правых частях формул (1)-(4) присутствуют матрицы Rev, зависящие только от двух параметров

В третьем параграфе предлагаются различные варианты факторизации матрицы Фурье по методу Кули-Тьюки на базе кронекерова умножения матриц Рассмотрим матрицу Фурье Fjv с элементами

:- /. 1 •>

FN[k.j]=w%, kje О N- 1,

где = ехр(27n/N) — корень N-й степени из единицы Справедливы разложения

FN= Fn, ® In„) {Ia„ ® TwidNl/,n„) ) Revns, ,ni, (5)

Fn = ( RevД,/

Rev„si ,ni, (6)

V=i

= ( П (Рп- ® ® -^Д^ЙеУлг/^^ 1 Деу„., ,П1, (7)

^ = П ® (Тт^,п„ <8> /д„) (Яеу^ ® /д>/) (8)

1^=1

Здесь Т'№1с1м1/1П1/ и — диагональные матрицы вращений с элементами

+ + = геО ЛГ„-1, ^ е 0 гг„ — 1,

геО п„ - 1, 3еО Я/п» - 1

Разложение (5) представляет собой наиболее общую и совершенную форму результата, полученного Кули и Тьюки Формула (6) соответствует алгоритму БПФ, ориентированному на параллельные вычисления, а формула (7) — на векторные В алгоритме БПФ, порождаемом формулой (8), не требуются перестановки данных до или после преобразования

В четвертом параграфе представлен усовершенствованный вариант общего подхода к вычислению ДПФ, предложенного М Б Свердликом Предположим, что при всех V € 1 в найдутся числа р„, ^ из 1 N — 1, взаимно простые с и натуральные такие, что любые ^ £ 0 N — 1

допускают представления

3 = (У2,ЭиРиЕ>и) , >е0 п„-1,

1/=1

n

к = ( ^^ ) ' € 0 пм - 1

VI ' м

Векторы р = (рг,р2, ,рв) и д = (дъ <72, будем называть векторами

параметров

Сокращение количества арифметических операций при вычислении ДПФ возможно в трех случаях выбора базисов {0„} и {С?д}

1) Д, = £„ и = где Д, = Ы/п„ В этом случае

при условии что (д„р,/Д/)п„ = 1 при всех V € 1 в Указанный выбор приводит к параметрическому варианту метода простых множителей для вычисления ДПФ

2) Dv = Nv и G^ = Ам В этом случае

;/=1 t/=2

при условии, что = 1 при всех и £ I в Указанный выбор

приводит к параметрическому варианту БПФ с прореживанием по времени

3) Оу — Д„ и = Л^ В этом случае

,к1 _ "ПГ, ТТ, КчиТО.^ЗиРгЬ»

fi—1 д=2

при условии, что {qvPv)n„ = 1 при всех i/g 1 s Указанный выбор приводит к параметрическому варианту БПФ с прореживанием по частоте

В пятом параграфе рассматривается параметрический вариант метода простых множителей Введем перестановку perm^1,' сопоставляющую

ЧИСЛу j = (js, ,,?l)ns, ,ni ЧИСЛО

4=1 I N

Эта перестановка определена и при s = 1 Запись fc = perm^(j) означает, что к = (jpi)m Такая перестановка называется эйлеровой

Матрица эйлеровых перестановок Perm^1' ^ определяется стандартным способом При pi = р2 = = ps = 1 получим матрицу руританских перестановок

ТЕОРЕМА 5.1 Справедливо разложение

S

Регш<££; = (Perm&-> ® Perm® ® Perm^) JJ(/*„ ® РегшЩ

¡/=2

Из теоремы 5 1 при pi = р2 = = ps = 1 следует разложение матрицы руританских перестановок

= ПС«. ® Ре™д:1)

к=2

Более того, само заключение теоремы 5 1 можно переписать в виде Регт&'£; *;) = (Perm^ ® Perm® ® Perm^Perm^ ^

ТЕОРЕМА 5.2 Пусть N = щп2 п„ г<3е сомножители п„ попарно взаимно просты Тогда при любом векторе параметров р = (pi,í>2, >Ps) матрица Фурье Fn допускает представление

FN = (Perm^; ® Fn._, ® ® £>, (9)

где q = (91,92, >9«) сопряженный вектор параметров, компоненты которого определяются условием (qvpvBv)nv — l, v € 1 s

В связи с теоремой 5 2 представляют интерес самосопряженные векторы параметров р, такие, что сопряженный вектор параметров q совпадает с р В этом случае в разложении (9) присутствует только одна матрица перестановок Обозначим через bv единственное на множестве 1 n¡, — 1 решение уравнения (xBv)n¡/ = 1 Самосопряженный вектор параметров существует тогда и только тогда, когда при всех v € 1 s число bv является квадратичным вычетом по модулю nv

Пусть р„ — решение уравнения (х2)Пи = bv при v € 1 s В таком случае вектор параметров р = {р\,р2, ,í>a) будет самосопряженным Например, при s = 2, п\ = 4, ri2 = 25 существует четыре самосопряженных вектора параметров р = (1,12), р = (1,13), р = (3,12) и р = (3,13)

Еще один пример при s = 3, П\ = 2, п^ = 3, щ = 5 самосопряженным будет руританский вектор параметров р = (1,1 1) Самосопряженными руританские коды будут также в следующих случаях п = (2,3,7,41), п = (2,3 11,13), п = (2,3,7,83,85), п = (2,3,11,17,59)

В шестом параграфе рассматривается параметрический метод быстрого преобразования Фурье в общем случае Введем перестановки mix^1' и revfe tn'\ сопоставляющие числу j = (js, ,Ji)n., числа

mix^; =

V=1

revn¿n%' = (ÍZ^PuK)

w < n

Матрицы перестановок Mix^ и ñev^1' определяются стандартным способом Отметим что ñevlf1' i?*' = Revi1, Mix^s ^

ТЕОРЕМА 6 1. При s > 2 справедливы разложения

£ = П(/лг„ ® Де^)

Нам потребуется диагональная параметрическая матрица вращений Тжк! с элементами

Здесь ] = ,л)п„,п„_х, л По определению

— Лг1

ТЕОРЕМА 6.2. При N = щпг н« и любом векторе параметров р — (р\, Р2, ,Рв) матрица Фурье Рм допускает представление

где д = (д\,д2, ,дв) — сопряженный вектор параметров, компоненты которого определяются условием {д^р»)^ = 1, ^ 6 1 в

Алгоритм БПФ, соответствующий факторизации матрицы Фурье в теореме б 2, связан с прореживанием по частоте Как следствие, можно получить факторизацию матрицы Фурье, соответствующую БПФ с прореживанием по времени

Вектор параметров можно подобрать таким образом, что число нетривиальных элементов (отличных от ±1 и ±г) в параметрической матрице вращений уменьшится по сравнению с обычной (непараметрической) матрицей вращений Например, если положить п = (2,3,4), то ТмпС^Р содержит 2 нетривиальных элемента — 12 элементов Если положить р = (3,2,3) и д = (1,2,3), то в матрице Тчук^Р все диагональные элементы станут триви-

(3 2} (з 2 з^

альными (Тшс^ — 1%), а в матрице Ттг№¡34 останется только 6 нетривиальных элементов

В седьмом параграфе на основе предыдущих результатов предложен параметрический вариант метода простых множителей с последовательными перестановками Для соответствующего алгоритма БПФ не требуется сложные перестановки данных до или после преобразования, а вычисления происходят совместно с перестановками

ТЕОРЕМА 7.2. Пусть N = щщ п8, где сомножители пи попарно взаимно просты Тогда при любом векторе параметров р = (рьр2, матрица Фурье ^ допускает представление

э

= п((^йй)т ®/д") ® ^ ® ® РегшЙЙ)'

¡/=1

где д = (91,92, — сопряженный вектор параметров, компоненты ко-

торого определяются условием {<м>иВи)Пи = 1, и € 1 э

В восьмом параграфе получен параметрический вариант БПФ в многомерном случае Пусть Ш1, тг, , т4 — натуральные числа, отличные от единицы Введем обозначения

771 =(шь 7712, ,1Гк),

М = ТП\П%2 тПг, Лд = 77117712 771^-1 При ¡Л, € 2 = тпм+1тм+2 гщ при ¡1 е О

Многомерное дискретное преобразование Фурье х х Ст(, определяется формулой

ГГЦ — ! »12 — 1 ГП\ — 1

Хт(к1,к2, Л) =

где ^60 4

От многомерного дискретного преобразования можно перейти к кронеке-рову произведению матриц преобразований по каждому измерению

ПРЕДЛОЖЕНИЕ. Пусть х{п + ;2 Ах + + л Л() = , и

X = ®

где [&,.?] = к,з е 0 том - ц е 1 4 Тогда

¿2, , = Х(/г1 + Л1 + + кг Л4)

Рассмотрим один из вариантов факторизации матрицы <8> ® <8> ® Введем матрицу тг = {тг^} (у € 1 8, д € 1 такую, что тод = = п8ф Считаем > 1 Пусть

А^ = при V е 2 в + 1, Д1)1[г = 1,

= ^„-и^Пу+г.д тг8,А при ¡/60 в - 1, = 1

Выберем матрицу параметров р = {Рг>,ц} {у € 1 в, // € 1 £), такую, что каждое взаимно просто с

¿+1, Лх = 1, ¿-1, М( = 1

сигнала хт € Ст1 х Ст2 х 7Л ш~к131и)~к2П

> Л) "/т1 шт2 гщ '

ТЕОРЕМА 8.1. При любой матрице параметров р = {рматрица Рть® ® ® Рт2 ® Рт1 допускает представление

^ ® ® Р^ ® ^ = (Я$)Т( Д Т^ ® ^ ® ,

V„=1 ^=1 /

где д = — матрица сопряженных параметров, элементы которой

определяются условием {Чи^Ри,^)^^ = 1> Вт1 и — матрицы перестановок вида

в-1 4

= П Ш1«. ® ® 'w,) ,

е=0 /i=l

= П ® ®/л«) •

Tin'' — диагональная матрица с элементами

t S

т£> Е Е Е Е За* Да,„л J = Цо/

M=1

где v £2 s, ц £ 1 t и ja € 0 — 1

Рассмотрен пример, демонстрирующий преимущество параметрического

т-г ^ол ^ Г2111 Гз 1 1 П Г1 о о] „

подхода Пусть m = (24,6,2) и n = з 2 l , р — 231,5= 210 В мат-

.4 3 2. .323. 1.321.

рице Tm^ все диагональные элементы тривиальные (Т^ = hss) В матрице Тт среди диагональных элементов 72 нетривиальных В непараметрическом случае (все pv^ и равны единице)

в матрице Тгп среди диагональных эле' ' (з) ментов 96 нетривиальных, а в матрице Тт ~~ 180 нетривиальных

Девятый параграф замыкает тему БПФ Все факторизации матрицы Фурье рассмотренные ранее, содержат матрицы Фурье малых порядков, которые для более эффективного вычисления ДПФ тоже необходимо фактори-зовать Напомним, что ДПФ определятся формулой

JV-1

вд = 5>ы<

'n >

А; € 0 N —1

(10)

j=o

Быстрый алгоритм Винограда вычисления ДПФ, разработанный в 1978 году, основан на приведении формулы (10) к виду

X = СБА х 13

Здесь В — диагональная матрица, ответственная за умножения, А и С — матрицы, элементы которых равны 0, 1 или —1 Матрицы А и С называются соответственно матрицей предсложений и матрицей постсложений

Факторизация (11) имеет целью минимизировать число умножений Чтобы минимизировать число сложений, нужно факторизовать матрицы А ж С, т е перейти к разложению

X = С1С2 СтВАпАп_! Ахх, (12)

в котором сомножители Ск и А1 обладают следующими свойствами их элементы по-прежнему равны 0 1 или —1, но в каждой строке этих сомножителей содержится, по возможности, не более двух отличных от нуля элементов Разложение (12) не единственно, поэтому можно ставить дополнительные условия Например, можно потребовать, чтобы матрицы Ск и А; были, в основном, симметричными, чтобы значение —1 стояло, по возможности, на диагоналях и т д Такие дополнительные условия трудно формализовать В диссертации приведен вывод «совершенных» разложений вида (12) при N = 3,4,5,6 В приложении указаны разложения при N — 7,8,9,10, 11,12,16 В таблице 1 приведены характеристики полученных алгоритмов

Таблица 1 Характеристики алгоритмов БПФ

Порядок алгоритма БПФ Число сомножителей в факторизации Порядок диагональной матрицы Число умножений Число сложений

2 1 2 0 2

3 5 3 2 6

4 3 4 0 8

5 7 6 5 17

6 6 6 4 18

7 7 9 8 36

8 6 8 2 26

9 7 12 10 42

10 8 12 10 44

11 9 21 20 84

12 7 12 8 48

16 9 18 10 74

Основные результаты диссертации опубликованы в работах

1 Малоземов В Н , Просеков О В О быстром преобразовании Фурье малых порядков // Вестник СПбГУ Сер 1 2003 Вып 1 (№ 1) С 36-45

2 Пахомов С Н , Просеков О В Вычислительные аспекты быстрого преобразования Фурье // Вестник СПбГУ Сер 1 2004 Вып 4 С 44-50

3 Просеков О В Алгоритмы быстрого преобразования Фурье для нетрадиционного числа точек // Труды седьмой международной конференции «Прикладные технологии гидроакустики и гидрофизики» 8-10 июня 2004 г Санкт-Петербург С 394-399

4 Малоземов В Н , Просеков О В Факторизация матриц реверсных перестановок // Электронный архив препринтов С -Петербургского матем общества Препринт 2007-04

(http //www mathsoc spb ru/preprint/2007/index html#04)

5 Малоземов В H , Просеков О В Параметрический вариант метода простых множителей // Электронный архив препринтов С -Петербургского матем общества Препринт 2007-05

(http //www mathsoc spb ru/preprint/2007/index html#05)

6 Малоземов В H, Просеков О В Параметрическая факторизация матрицы Фурье / / Электронный архив препринтов С -Петербургского матем общества Препринт 2007-06

(http //www mathsoc spb ru/preprint/2007/index html#06)

7 Просеков О В Параметрический вариант многомерного быстрого преобразования Фурье / / Электронный архив препринтов С -Петербургского матем общества Препринт 2007-07

(http //www mathsoc spb ru/prepnnt/2007/iiidex html#07)

Полный текст диссертации можно найти в Интернете по адресу http //dha spb ru/prosekov/

Подписано в печать 28 12 2007 г Формат 60 х 90 1/16 Уел печ л 1,0 Бумага офсетная Печать цифровая Тираж 100 экз Заказ 4015

Отпечатано в издательстве «ВВМ» 196247, Санкт-Петербург, а/я 49

ВВЕДЕНИЕ

§ 1. Перестановки и кронекерово произведение матриц

§ 2. Факторизация матриц реверсных перестановок.

§ 3. Факторизация Кули-Тьюки матрицы Фурье

§ 4. Общий подход к вычислению дискретного преобразования Фурье

§ 5. Параметрический вариант метода простых множителей

§ 6. Параметрический вариант быстрого преобразования Фурье.

§ 7. Параметрический вариант метода простых множителей с последовательными перестановками

§ 8. Параметрический вариант многомерного быстрого преобразования Фурье

§ 9. Быстрое преобразование Фурье малых порядков

Быстрые алгоритмы играют важную роль при обработке дискретных периодических сигналов, особенно в многомерном случае. Наиболее популярным и но-прежнему востребованным является быстрое преобразование Фурье (БПФ). Отметим, что теория БПФ далеко не проста [2, 3, 6, 9, 24]. Хороший обзор её развития дан в [40]. Ключевой работой в теории БПФ явилась работа Кули и Тьюки 1965 года [38]. Немаловажную роль в то время сыграло развитие вычислительных средств. В [38] приводится время работы реализации трёхмерпого БНФ на «новых» тогда ЭВМ IBM 7094. С тех пор интерес к БНФ не угасает. В известном обзорном отчёте Барраса 1997 года [36] упоминается более 3400 работ но БНФ. Большая часть из них это работы, связанные с вычислительными аспектами БНФ и вопросами реализации БНФ на различных архитектурах ЭВМ. Вопрос о быстродействии стоит очень остро в связи с обработкой сигналов в реальном времени, а дискретное преобразовапие Фурье (ДНФ) является базовой операцией для других алгоритмов, и быстродействие системы в целом сильно зависит от эффективной реализации БНФ. Типичные приложения это цифровые устройства связи, аудио- и видеоустройства. С развитием микроэлектроники появилось множество микропроцессоров с сильно различаюп;ейся архитектурой. В связи с этим встал вопрос об универсальном подходе к реализации БНФ. Самой известпой работой в этой области является система FFTW, разработанная Фриго и Джонсоном [42]. Система анализирует вычислительные графы БНФ и адантирует их для конкретной 3 вычислительной архитектуры ЭВМ. Для большинства длин нериодов и большинства ЭВМ это самая быстрая реализация БПФ на сегодня. Другой не менее известной работой является нроект SPIRAL [48], в котором реализуется новый нодход к дискретным нреобразованиям, основанный на теории нредставлений. Несмотря на то, что эффективные алгоритмы БПФ суш,ествуют для нрактически любых длин нериодов, длина, равная стенени двойки, остаётся самой нонулярной. В этом случае ВПФ достаточно легко реализуется, и основной вычислительный модуль «бабочка» задаётся всего несколькими инструкциями. Более сложный но реализации, но более эффективный алгоритм БПФ «split-radix» [39, 51] нозволяет сократить число веш,ественных арифметических онераций на 20%, а алгоритм, онисанный в новой работе [41], еш,ё нримерно на 6%. Различные алгоритмы БПФ зависят от арифметических свойств длины нериода сигнала. Если эта длина число составное, то применим алгоритм Кули-Тьюки. Описание различных вариантов алгоритма Кули-Тьюки можно найти в [37]. В случае, когда длина сигнала может быть нредставлена в виде нроизведения понарно взаимно простых чисел, применим алгоритм нростых множителей, разработанный Гудом в 1958 году [8]. В вычислительном отношении алгоритм нростых множителей нрош,е алгоритма Кули-Тьюки. Если длина сигнала является простым числом, то можно воснользоваться алгоритмом Рейдера [31]. В этом случае задача вычисления ДПФ сводится к задаче вычисления циклической свёртки. Эффектное применение этой идеи нашёл Виноград для вычисления ДПФ небольшой длины [4]. Задача быстрого вычисления циклической свёртки решается с помон],ыо полиномиальной тех1шки. По сути, метод Винограда даёт разложение матрицы Фурье малого норядка в нроизведение трёх матриц матрицы предсложений, диагональной матрицы и матрицы постсложений. Такое разложение имеет целью мннимизировать число умножений. Сложения оптимизируются вручную. Алгоритмы Винограда малых длин эффективно иснользуются в алгоритмах БПФ для составных длин. Идея факторизации матрицы Фурье представляется наиболее перспективной. Обш,ий подход к построепию быстрых алгоритмов связап с разложением матрицы Фурье в произведение слабо заполпенпых матриц. Поскольку такие разложения не единственны, возникает возможность выбора наилучших в некотором смысле разложений. Впервые на базе кронекерова умножения матриц факторизация матрицы Фурье была нолучена в работе 1968 года [47]. В этой статье рассматривался вонрос о параллельных вычислениях. Позже в [46] были получены факторизации матрицы Фурье, ориентированные на векторные вычисления. Паиболее нолно техника факторизации матриц представлена в обзорной статье [45]. В ней нодробно рассмотрены варианты реализации БПФ па различных архитектурах ЭВМ. Педавно был разработан новый подход к формировапию вейвлет-пакетов, основанный на построении последовательности ортогопальных базисов в пространстве сигналов [И, 12, 23]. Это значительно расширяет возможности цифровой обработки сигналов. Вейвлет-пакеты позволяют получать детальные частотно-временные нортреты сигналов, варьируя разрешение (масштабность) но времени и частоте. В этом смысле анализ сигналов с помощью вейвлет-пакетов можно рассматривать как мон],ное донолнение к традиционному анализу Фурье. В теории быстрых ортогональных преобразовапий важную роль играют перестановки. Обычно перестаповки особым образом изменяют порядок входпых или выходных отсчётов сигнала. Это не всегда удобно. Алгоритмы, не требуюш,ие перестановки данных до или носле преобразования, получили название «self-sorting». Впервые такой алгоритм БПФ был нолучен Стокхемом и описан в [37]. Другой алгоритм, основанный на факторизации матрицы Фурье, был разработан Глассмапом [43]. Детально такие алгоритмы рассмотрены в работе [50]. Особенно эффективно идея БПФ работает в многомерном случае. Традиционно иснользуют нострочно-столбцевой метод [24, с. 94]. В этом методе для каждой размерности нрименяется соответствуюищй одномерный алгоритм БПФ. Более эффективный двумерный алгоритм, нохожий на алгоритм Кули-Тьюки, предложил Райворд[49]. Обобщение этого алгоритма было нолучено в работе [44]. Использовать полиномиальные преобразования для вычисления ДПФ предложили Нуссбаумер и Квенделл [24]. Другой алгоритм с похожими характеристиками был получен в работе [35]. Варианты БПФ основываются на разных представлениях (кодировании) индексов сигнала. Смешанный код иснользуется в методе Кули-Тьюки (если длина нериода равна степени двойки, то это бинарный код). Китайский и руритаский коды в методе простых множителей. М. Б. Свердлик в своих работах [32-34] предложил обобщённое представление индексов, связанное с введепием вектора параметров. Это послужило основой для параметрической факторизации матрицы Фурье. Целью диссертационной работы является: 1) Исследование различных вариантов факторизации матрицы Фурье на базе кронекерова умнооюения матриц. 2) Разработка общего подхода к вычислению ДПФ, основанного на параметрическом кодировавши индексов. 3) Построение параметрического алгоритма БПФ в многомерном случае. 4) Получение более детальной факторизации матриц Фурье малых порядков.Данная работа носит теоретический характер. Построена параметрическая теория БПФ. С практической точки зрения все полученные результаты ориентированны на параллельные и векторные вычисления, что особенно актуально в связи с развитием современных технологий. Приведём краткий обзор содержания диссертации. Работа состоит из девяти нараграфов, одной таблицы, одного рисунка, сниска литературы и одного приложения. Порядок ссылок на теоремы и формулы онределяется двумя числами: первое число указывает номер

1. Ахмед Н., Рао К. Р. Ортогональные преобразования при обработке цифровых сигналов. М.: Связь, 1980. 248 с.

2. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. М.: Мир,1989. 448 с.

3. Виноград С. О вычислении дискретного преобразования Фурье / В кн. 9. с. 117-136.

4. Власенко В. А., Лаппа Ю. М. Матричный подход к построению быстрых алгоритмов многомерного ДПФ // Изв. вузов. Радиоэлектроника. 1986. Т. 29. № 1. С. 86-89.

5. Власенко В. А., Лаппа Ю. М., Ярославский Л. П. Методы синтеза быстрых алгоритмов свёртки и спектрального анализа сигналов. М.: Наука,1990. 180 с.

6. Воеводин В. В., Кузнецов Ю. А. Матрицы и вычисления. М.: Наука, 1984. 320 с.

7. Гуд И. Дж. О взаимоотношении между двумя быстрыми преобразованиями Фурье / В кн. 9. с. 136-147.

8. Макклеллан Дж. X., Рейдер Ч. М. Применение теории чисел в цифровой обработке сигналов. М.: Радио и связь, 1983. 264 с.

9. Малозёмов В. Н. Параметрическое кодирование индексов // Семинар по дискретному гармоническому анализу и геометрическому моделированию (DHA & CAGD). Избранные доклады. 19 мая 2004 г.http://www.dha.spb.ru/reps04.shtml#0519)

10. Малозёмов В. H., Машарский С. М. Основы дискретного гармонического анализа. Части 1-3. СПб.: НИИММ, 2003. 320 с.

11. Малозёмов В. Н., Машарский С. М. Формула Глассмапа, быстрое преобразование Фурье и вейвлетпые разложения // Труды С.-Петербургского Матем. Общества. 2001. Т. 9. С. 97-119.

12. Малозёмов В. Н., Просеков О. В. О быстром преобразовании Фурье малых порядков // Вестник СПбГУ. Сер. 1. 2003. Вып. 1 (№ 1). С. 36-45.

13. Малозёмов В. Н., Просеков О. В. Общий подход к вычислению ДПФ // Семинар по дискретному гармоническому анализу и геометрическому моделированию (DHA k CAGD). Избранные доклады. 12 сентября 2006 г. (http://www.dha.spb.ru/reps06.shtml#0912)

14. Малозёмов В. H., Просеков О. В. Параметрическая факторизация матрицы Фурье // Электронный архив препринтов С.-Петербургского матем. общества. Препринт 2007-06.http://www.mathsoc.spb.ru/preprint/2007/index.html#06)

15. Малозёмов В. H., Просеков О. В. Параметрический вариант метода простых множителей // Электронный архив препринтов С.-Петербургского матем. общества. Препринт 2007-05.http://www.mathsoc.spb.ru/preprint/2007/index.html#05)

16. Малозёмов В. H., Просеков О. В. Факторизация Гуда матрицы Фурье // Семинар по дискретному гармоническому анализу и геометрическому моделированию (DHA & CAGD). Избранные доклады. 5 мая 2004 г. (http://www.dha.spb.ru/reps04.shtml#0505)

17. Малозёмов В. H., Просеков О. В. Факторизация Кули-Тыоки матрицы Фурье // Семинар по дискретному гармоническому анализу и геометричсскому моделированию (DHA k CAGD). Избранные доклады. 14 апреля 2004 г. (http: //www. dha. spb. ru/reps04. shtml#0414)

18. Малозёмов В. H., Просеков О. В. Факторизация матриц реверсных перестановок // Электронный архив препринтов С.-Петербургского матем. общества. Препринт 2007-04.http://www.mathsoc.spb.ru/preprint/2007/index.html#04)

19. Малозёмов В. H., Третьяков А. А. Новый подход к алгоритму Кули-Тьюки // Вестник СПбГУ. Сер. 1. 1997. Вып. 3 (№ 15). С. 57-60.

20. Нуссбаумер Г. Быстрое преобразование Фурье и алгоритмы вычисления свёрток. М.: Радио и связь, 1985. 248 с.

21. Пахомов С. Н., Просеков О. В. Вычислительные аспекты быстрого преобразования Фурье II Вестник СПбГУ. Сер. 1. 2004. Вып. 4 С. 44-50.

22. Просеков О. В. Алгоритмы быстрого преобразования Фурье для нетрадиционного числа точек // Труды седьмой международной конференции «Прикладные технологии гидроакустики и гидрофизики». 8-10 июня 2004 г. Санкт-Петербург. С. 394-399.

23. Просеков О. В. Быстрое преобразование Фурье малых порядков // Семинар по дискретному гармоническому анализу и геометрическому моделированию (DHA & CAGD). Избранные доклады. 6 декабря 2005 г.http://www.dha.spb.ru/reps05.shtml#1206)

24. Просеков О. В. Параметрический вариант многомерного быстрого преобразования Фурье // Электронный архив препринтов С.-Петербургского матем. общества. Препринт 2007-07.http://www.mathsoc.spb.ru/preprint/2007/index.html#07)

25. Просеков О. В. Разработка алгоритма БПФ для нетрадиционного числа точек // Сборник докладов I научно-технической конференции молодых специалистов «ЦНИИ «Морфизприбор». 22-25 апреля 2003 г. Санкт-Петербург. С. 116-121.

26. Рейдер Ч. М. Дискретное преобразование Фурье, когда число отсчётов простое / В кн. 9. с. 89-91.

27. Свердлик М. Б. Матричная интерпретация алгоритма БПФ для взаимно простых сомножителей // Радиотехника и электроника. 1983. № 10. С. 1931-1938.

28. Свердлик М. Б. Матричная интерпретация и вычислительная эффективность алгоритмов БПФ // Радиотехника и электроника. 1984. № 2. С. 265-274.

29. Свердлик М. Б., Троянский А. В. Обобщённое матричное описание алгоритма БПФ II Радиоэлектроника. 1995. № 7. С. 27-33.

30. Auslander L., Feig Е., Winograd S. New algorithms for the multidimensional Fourier transform // IEEE Transactions on Acoustics, Speech, and Signal Processing. 1983. V. ASSP-31. No. 2. P. 338-403.

31. Burrus C. S. Notes on the FFT // Department of Electrical and Computer Engineering, Rice University, Houston, TX 77251-1892, September 29,1997.

32. Cooley J. W., Tukey J. W. An algorithm for the machine calculation of complex Fourier series // Mathematics of Computation. 1965. V. 19. No. 90. P. 297-301.

33. Duhamel P., Hollmann H. Split-radix FFT algorithm // Electronics Letters. 1984. V. 20. No. 1. P. 14-16.

34. Duhamel P., Vetterli M. Fast Fourier transforms: a tutorial review and a state of the art // Signal Processing. April 1990. V. 19. No. 4. P. 259-299.

35. Frigo M., Johnson S. G. A modified split-radix FFT with fewer arithmetic operations // IEEE Transactions on Signal Processing. 2007. V. 55 No. 1. P. 111-119.

36. Frigo M., Johnson S. G. The design and implementation of FFTW3 // Proceedings of the IEEE, special issue on "Program Generation, Optimization, and Adaptation". 2005. V. 93. No. 2. P. 216-231.http://www.fftw.org/)

37. Glassman J. A. A generalization of the fast Fourier transform // IEEE Transactions on Computers. 1970. V. C-19. No. 2. P. 105-116.

38. Harris D., McClellan J., Chan D., Schuessler H. Vector radix fast Fourier transform // IEEE International Conference on Acoustics, Speech, and Signal Processing. 1977. V 2. P. 548-551.

39. Johnson J., Johnson R. W., Rodriguez D., Tolimieri R. A methodology for designing, modifying and implementing Fourier transform algorithms on various architectures // Journal of Circuits, Systems, and Signal Processing. 1990. V. 9. No. 4. P. 449-500.

40. Korn D. G., Lambiotte J. J. Jr. Computing the fast Fourier transform on a vector computer // Mathematics of Computation. 1979. V. 33. No. 147. P. 977-992.

41. Pease M. C. An adaptation of the fast Fourier transform for parallel processing // Journal of the Association for Computing Machinery. 1968. V. 15. No. 2. P. 252-264.

42. Rivard G. E. Direct fast Fourier transform of bivariant functions // IEEE Transactions on Acoustics, Speech, and Signal Processing. 1977. V. 25. No. 3. P. 250-252.

43. Temperton C. Self-sorting mixed-radix fast Fourier transforms // Journal of Computational Physics. 1983. V. 52. No. 1. P. 1-23.

44. Yavne R. An economical method for calculating the discrete Fourier transform // Proceedings of the Fall Joint Computer Conference. 1968. V. 33. P. 115-125.