39414

Реализация и исследование быстрого алгоритма двумерного вещественного ДПФ с расщеплением основания с представлением данных в алгебре кватернионов

Курсовая

Информатика, кибернетика и программирование

ЗАДАНИЕ Реализация и исследование быстрого алгоритма двумерного вещественного ДПФ с расщеплением основания с представлением данных в алгебре кватернионов. Текст программы 1 Постановка задачи Нахождение спектра квадратной матрицы размера с помощью быстрого алгоритма двумерного вещественного ДПФ с расщеплением основания с представлением данных в алгебре кватернионов. Тестирование полученной реализации алгоритма ее исследование и сравнение с обычным алгоритмом двумерного ДПФ. Рассмотрим...

Русский

2013-10-04

308.5 KB

26 чел.

Федеральное агентство по образованию

Государственное образовательное учреждение

высшего профессионального образования

«Самарский государственный аэрокосмический

университет  имени академика С.П. Королева»

Кафедра геоинформатики

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту по дисциплине

"Компьютерная алгебра"

Тема № 6

Cтудент: Валеев Д. Р.
группа 65
7

Руководитель проекта: Чичева М. А.

Оценка: ____________

Дата: ____________

Самара 2010

ЗАДАНИЕ

Реализация и исследование быстрого алгоритма двумерного вещественного ДПФ с расщеплением основания  с представлением данных в алгебре кватернионов.


ОГЛАВЛЕНИЕ

[1] ЗАДАНИЕ

[2]
ОГЛАВЛЕНИЕ

[3]
2 Теоретический материал

[3.1] 2.1 Двумерное преобразование Фурье

[3.2] 2.2 Алгебра кватернионов

[3.3] 2.3 Учет вещественности

[4]
3 Описание разработанного алгоритма и программы

[4.1] 3.1 Описание работы программы

[4.2] 3.2 Описание разработанного алгоритма

[5]
4 Тестирование программы

[6]
5 Исследование алгоритма

[7]
Приложение А. Текст программы


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

Нахождение спектра квадратной матрицы размера  с помощью быстрого алгоритма двумерного вещественного ДПФ с расщеплением основания  с представлением данных в алгебре кватернионов. Тестирование полученной реализации алгоритма, ее исследование и сравнение с «обычным» алгоритмом двумерного ДПФ.


2 Теоретический материал

2.1 Двумерное преобразование Фурье

Пусть  - входной массив размера N×N. Тогда его комплексный спектр Фурье

,  ,   (1.1)

где  - комплексный корень из единицы степени N.

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

.  (1.2)

Основная идея такого преобразования заключается в погружении входного сигнала и корней  в четырехмерную алгебру кватернионов H. При этом корни  лежат в разных экземплярах поля комплексных чисел, вложенных в H, у них разные мнимые единицы - i и j.

Отметим, что умножения на степени  и  в соотношении (1.2) записаны слева и справа от входного сигнала. Это сделано для унификации записи. При использовании алгебры кватернионов H это принципиально, так как умножение в ней некоммутативно.

Поскольку элемент алгебры H (кватернион ) определяется набором четырех вещественных чисел , то комплексный спектр (1) может быть получен из спектра (2) в алгебре H  следующим образом:

   (1.3)

где  – вектор компонент спектра,

.   (1.4)

Таким образом, мультипликативная сложность вычисления  совпадает со сложностью вычисления спектра в алгебре H, т.к. умножения на матрицы L, I не требуют выполнения нетривиальных операций вещественного умножения.

Рассмотрим алгоритм вычисления двумерного ДПФ с расщеплением основания. Это – схема декомпозиции двумерного спектра (1.2), в которой ДПФ объема  сводится к одной ДПФ  элементов входной последовательности с четными индексами и двенадцати ДПФ объемом  с элементами, имеющими хотя бы один нечетный индекс. Пусть

,

тогда

   (1.5)

(1.6)

где размерность ДПФ на текущем шаге.

2.2 Алгебра кватернионов

Под телом H гамильтоновых кватернионов понимается четырехмерная ассоциативная алгебра над R

 H  R

с определяющими соотношениями для умножений базисных элементов {1, ijk}:

       (2.1)

Поле комплексных чисел C  канонически вкладывается в H:

       (2.2)

Кроме того, справедливо соотношение

      (2.3)

Операция сложения кватернионов осуществляется покомпонентно, а умножения - с учетом правил (2.1) и с приведением подобных членов.

Далее, отображения

    (2.4)

являются автоморфизмами H над R, причем

         (2.5)

Система уравнений (2.5), рассматриваемая относительно a, b, c, d, разрешима при любых значениях левых частей и требует для решения не более четырех вещественных умножений:

      (2.6)

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

Определим число вещественных умножений, необходимых для перемножения двух кватернионов. Умножение комплексных чисел может быть реализовано по схеме "три умножения, три сложения", тогда, в соответствии с представлением (1.3), умножение двух кватернионов общего вида может быть реализовано с помощью девяти вещественных умножений. Пусть далее  - i-кватернион; - j-кватернион. Тогда для вычисления произведений sq и qt необходимо по шесть вещественных умножений, а для одновременного вычисления произведения sqt - девять вещественных умножений:

    (2.7)

  (2.8)

При этом считаем, что произведения и суммы констант  выполнены заранее.

2.3 Учет вещественности

Первоначально преобразование (1.2) использовалось как вспомогательное для эффективного вычисления преобразования (1.1) при вещественном входном сигнале. Рассмотрим один из способов учета вещественности входного сигнала – учет симметрий спектра в рассматриваемой алгебре H.

Основное свойство спектра вещественного сигнала в рассматриваемой алгебре H – это его симметрия. Так, спектр вещественного сигнала удовлетворяет следующим свойствам симметрии:

,
,      (3.1)
,

где  – автоморфизмы алгебры H (2.6).

Таким образом, достаточно рассчитать значения всего  элементов вместо  по формуле (1.6), взяв значения  при ,  при и  при ,  при  Недостающие отсчеты заполняются на основании свойств (3,1) в соответствии со схемой, показанной на рис. 1.


Рис. 1. Заполнение недостающих областей на основании свойств симметрии


3 Описание разработанного алгоритма и программы

3.1 Описание работы программы

Заданный алгоритм был реализован программно с помощью технологии Microsoft .NET Framework на языке программирования C#.

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

После запуска приложения пользователь видит консоль с предложением ввести размер квадратного массива (рис. 2)

Рис. 2. Консоль приложения после запуска

После ввода пользователем размера массива  производится проверка   Если условия не выполняются, генерируется исключение. Затем создается вещественная матрица размерности  и заполняется с помощью генератора псевдослучайных чисел. Эта матрица, симулирующая входной сигнал (изображение), передается в качестве параметров методам подсчета ДПФ и БПФ из библиотеки FFT. Производится замер времени выполнения методов (вычисления ДПФ, БПФ и БПФ с учетом вещественности), которое выводится на экран. Результаты вычислений выводятся в текстовые файлы right result.txt (ДПФ), result.txt (БПФ) и resultWithConsiderReality.txt (БПФ с учетом вещественности). Пример работы программы приведен на рисунке 3.

Библиотека FFT содержит несколько классов:

  1.  Класс FFT содержит методы вычисления ДПФ по формуле комплексного двумерного сигнала и его перегрузки; 2 БПФ  двумерного сигнала в алгебре кватернионов: одно – учитывающее вещественность входного сигнала, другое – нет; вспомогательные методы для удобного вызова БПФ; а также метод, реализующий бинарную инверсию входного сигнала.
  2.  Класс TreeNode используется при подсчете ДПФ на каждом шаге. Фактически, в экземпляре этого класса хранится вся необходимая информация о подматрицах, в которых необходимо посчитать ДПФ. Метод TreeNode CreateTree(UInt32 N) класса создает дерево для матрицы размером   и возвращает элемент дерева, соответствующий той подматрице, которую необходимо посчитать первой. Каждый узел дерева имеет ссылки на узел-«родитель» и 13 узлов-«потомков» (если таковые имеются), а также размер соответсвующей матрицы и координату ее верхнего левого угла в основной матрице. Метод Boolean MoveToNext(ref TreeNode current) переводит ссылку на элемент дерева current на следующий узел, БПФ для которого нужно подсчитать.
  3.  Класс Complex реализует простейшую функциональность множества комплексных чисел, операции над ними, а также метод домножения на фазовый множитель  необходимый при подсчете ДПФ.
  4.  Класс Quaternion реализует функциональность алгебры кватернионов, операции над ними, а также методы домножения на  на фазовые множители  необходимые при подсчете БПФ.

Листинг программы представлен в приложении А.

Рис. 3. Пример работы программы

3.2 Описание разработанного алгоритма

Метод, реализующий БПФ, получает на вход двумерный массив кватернионов. «На месте» осуществляется бинарная инверсия, по имеющемуся резмеру  составляется дерево с информацией о подматрицах, в которых необходимо вычислить ДПФ.

Далее запускается цикл, в котором перебираются все элементы дерева и считаются БПФ в соответствующих этим элементам подматрицам.

В случае, если рассматриваемая подматрица имеет размер  то ДПФ вычисляется с помощью двумерной «бабочки» размера Если  – с помощью четырехмерной «бабочки» размера  В остальных случаях вычисления производятся по формуле (1.6). В алгоритме, учитывающем вещественность входного сигнала также учитываются замечания из п. 2.3, используются формулы (2.6) и (3.1).


4 Тестирование программы

Проверка результатов работы программы производилась с помощью реализованного алгоритма подсчета двумерного ДПФ по формуле. Значения отсчетов полученных разными способами спектров в тестовых примерах (для ) совпали с точностью до 12 знака после запятой. Полученную погрешность вполне обоснованно можно считать машинной погрешностью вычислений.


5 Исследование алгоритма

Убедиться в эффективности разработанного алгоритма позволяет таблица сравнения времени выполнения этого алгоритма с вычислением ДПФ по формуле (таб. 1).

N

Время вычисления ДПФ по формуле, с

Время вычисления БПФ, с

8

0,0018

0,0108

16

0,0162

0,0129

32

0,2303

0,0256

64

3,6968

0,0864

128

59,2014

0,4078

Таблица 1. Сравнение времени выполнения БПФ и  ДПФ по формуле

Приведенную таблицу хорошо иллюстрирует рисунок 4.

Рис. 4.  Сравнительные графики времени выполнения БПФ и  ДПФ по формуле 

Более того, неплохой прирост производительности дает учет вещественности входного сигнала. В таблице 2 приведены сравнительные результаты времени выполнения алгоритма БПФ с учетом и без учета вещественности.


N

Время вычисления БПФ без учета вещественности, с

Время вычисления БПФ с учетом вещественности, с

8

0,0108

0,0075

16

0,0129

0,0084

32

0,0256

0,0137

64

0,0864

0,0398

128

0,4078

0,1589

256

1,8156

0,672

512

8,5489

3,0825

Таблица 2. Сравнение времени выполнения БПФ с учетом и без учета 

вещественности входного сигнала

На рисунке 5 приведены построенные по данной таблице графики.

Рис. 5.  Сравнительные графики времени выполнения БПФ с учетом и 

без учета вещественности входного сигнала


Приложение А. Текст программы


 

А также другие работы, которые могут Вас заинтересовать

16118. Державне управління. Навчальний посібник 3.49 MB
  Посібник подає у формі навчального матеріалу основні теоретичні засади науки державного управління. Викладені у ньому основи адміністративно-управлінської науки - історія та теорія державного управління - розглядаються в контексті сучасних досягнень у цій галузі й базуються на практичній управлінській діяльності.
16119. Сучасні правові системи світу. Навчальний посібник 1.79 MB
  Курси порівняльного правознавства у західних університетах є традиційними вже багато років. В юридичних вузах багатьох країн світу викладається навчальний курс Основні правові системи сучасності. Нині існує нагальна потреба в оновленні системи вищої юридичної освіти в Україні, приведення її у відповідність з потребами нашого часу, загальноєвропейськими вимогами.
16120. нститут адміністративної відповідальності, ароблеми розвитку. Навчальний посібник 864.5 KB
  Монографія присвячена одному Із основних інститутів адміністративного права — Інституту адміністративної відповідальності. Розглядається Історія його розвитку та сучасний стан. Основна увага приділяється найбільш актуальним проблемам адміністративної відповідальності, зокрема відповідальності юридичних осіб. її підставам. принципам і функціям. Для науковців, аспірантів і студентів юридичних навчальних закладів.
16121. Кримінально-процесуальне право 2.55 MB
  У посібнику викладено основні поняття кримінальне-процесуальної науки та проблеми практики застосування норм кримінально-процесуального права органами дізнання, досудового слідства, прокуратури та суду. Книгу підготовлено з урахуванням багаторічного досвіду читання лекцій з кримінально-процесуального права у вищих юридичних нав¬чальних закладах III та IV рівнів акредитації.
16122. Кримінально-процесуальне право. Навчальний посібник 3.34 MB
  У посібнику викладено основні поняття кримінально-процесуальної науки та проблеми практики застосування норм кримінально-процесуального права органами дізнання, досудового слідства, прокуратури та суду. Книгу підготовлено з урахуванням багаторічного досвіду читання лекцій з кримінально-процесуального права у вищих юридичних навчальних закладах III та IV рівнів акредитації.
16123. Конституція України. Матеріали до вивчення. Навчальний посібник 1.36 MB
  У посібнику розглянуто основні теоретичні питання конституції, коротку історію українського конституціоналізму, його ідеї та спроби їх реалізації, здійснювані на різних етапах розвитку нашого суспільства. Докладно висвітлено зміст основних положень Конституції незалежної України, роз'яснено відповідну юридичну термінологію
16124. Кримінальне право, злочин, покарання, судочинство. Англійський підхід 917 KB
  У книжці стисло розказано про англійську систему кри¬мінального судочинства, різновиди та ієрархію судів, основні типи злочинів, найголовніші закони, що регулюють царину кримінального права. Розповідь не переобтяжена спеціальною термінологією, проілюстрована багатьма повчальними судовими прецедентами і безперечно буде цікава як усім представникам судового і правничого фаху, так і нефахівцям, що матимуть змогу познайомитись із кримінальним судочинством.
16125. Права жінок, зміст, стан та перспективи розвитку 2.17 MB
  Книга присвячена аналізу міжнародних документів з прав жінок, можливостей та практики їх застосування в незалежній Україні, а також виявлення протиріч між положеннями міжнародних документів щодо прав жінок та реаліями українського суспільства.
16126. Вопросы обеспечения допустимости доказательств в уголовном процессе 455.5 KB
  Возврат к списку научных трудов Сильнов М.А. Вопросы обеспечения допустимости доказательств в уголовном процессе досудебные стадии Москва 2001 Оглавление Введение I.Допустимость доказательств в уголовном судопроизводстве и задачи прокурора по ее обеспеч...