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.  Сравнительные графики времени выполнения БПФ с учетом и 

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


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


 

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

3298. Город Лицей на 59-м градусе северной широты 43.33 KB
  Город Лицей на 59-м градусе северной широты» (лицейский годы Пушкина). ХОД МЕРОПРИЯТИЯ Учитель: Сегодня у нас необычная встреча. Мы приглашаем всех отправиться совсем недалеко – всего на два столетия назад, в первые десятилетия 19 века. Мы поз...
3299. Внеклассное мероприятие Знай и люби свой край 34.5 KB
  Внеклассное мероприятие Знай и люби свой край Конкурс 1. Лекарственные растения. 1.Перечислите правила сбора лекарственных растений (нельзя заготавливать вблизи дорог и в черте города; собирать только в сухую ясную погоду; нельзя собирать больные ...
3300. Внеклассное мероприятие. Семья, как много в этом слове 37 KB
  Семья, как много в этом слове Цели внеклассного мероприятия: сформировать уважение к членам семьи, сформировать у детей понимание сущности основных социальных ролей: дочери, сына, мужа, жены. Задачи внеклассного мероприятия: сформировать представлен...
3301. Внеклассное мероприятие на тему: 30 KB
  Формировать толерантное и уважительное отношение к одноклассникам, людям другой национальности Задачи: Ввести и закрепить определение термина “толерантность”. Учить находить ком...
3302. Подумай, оглянись вокруг, реши – что важно в жизни для твоей души 34.12 KB
  Внеклассное мероприятие по пропаганде здорового образа жизни среди подростков "Подумай, оглянись вокруг, реши – что важно в жизни для твоей души…" 10–11-й классы Оборудование: тематические плакаты, выставочный стенд художественной литерату...
3303. Законність та відповідальність у державному управлінні 24.29 KB
  Досягненню зазначених цілей служать такі основні принципи здійснення юридичної відповідальності: відповідальність лише за поведінку, а не за думки; відповідальність тільки за протиправні діяння і тільки при наявності вини (презумпція невинності); законність, справедливість, доцільність і невідворотність.
3304. Внеклассное мероприятие. Суд над ядерной энергией 33.96 KB
  Внеклассное мероприятие по предмету «Физика». Тема:  «Суд над ядерной энергией». Тип мероприятия: ролевая игра Цели и задачи: • Обобщить теоретический материал по применению ядерной энергии • Показать грандиозные успехи в использовании ядерной ...
3305. Методы получения 3-амино-4-(5-R-1,3,4-оксадиазол-2-ил) фуразанов и их физико–химические свойства 197.5 KB
  Исследования в области поиска эффективных методов получения гетероциклических веществ для изучения связи «структура-свойство». 1,3,4-оксадиазольные основания вошли в практику терапии ряда патологических заболеваний вследствие их способности к образованию одного из универсальных регуляторов клеточного метаболизма – оксида азота...
3306. Внеклассное мероприятие по технологии В гостях у Золушки 30.5 KB
  Внеклассное мероприятие по технологии «В гостях у Золушки!»? 5 класс Внеклассное мероприятие по технологии «В гостях у Золушки!» среди учащихся 5-х классов. 02.03.2012г. Подготовила и провела учитель технологии Максимова Ирина Ивановна.Ведущий: Не за...