39414

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

Курсовая

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

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

Русский

2013-10-04

308.5 KB

29 чел.

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

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

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

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

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

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

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

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

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

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

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


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


 

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

30786. Технология устройства гидроизоляции 15.47 KB
  Гидроизоляция: Окрасочная Литая Оклеечная Жёсткая Окрасочную изоляцию жидкими составами толщиной 02. Литую асфальтовую изоляцию в виде сплошного водонепроницаемого слоя асфальтовой массы толщиной 10. На нее наносят слой битумной мастики толщиной 1. Швы между полотнищами очередных слоев смещают по отношению друг к другу Жесткая гидроизоляция цементнопесчаная гидроизоляция толщиной до 25 мм состава 1:1; 1 : 2; 1 : 3 устраивают двумя способами торкретированием и оштукатуриванием.
30787. Виды теплоизоляционных покрытий. Технология 15.75 KB
  Теплоизоляция: Засыпная Мастичная Литая Обвалакивающая Сборноблочная Вакуумная Засыпная в стену приваривают шпильки 335 см на них крепят мелкую металлическую сетку с ячейками в которые засыпается диатомовая крошка перлитовый песок мин и стекловата. Мастичная на стену с помощью шпилек устанавливают мелкую армирующую сетку. Мастику наносят на сетку 1 слой набрызг затем разглаживание последний слой укладывают рейкой. При устройстве однослойной изоляции поверх войлока укладывают оцинкованную металлическую сетку и закрепляют ее...
30788. Назначение кровель. Кровельные материалы. Виды кровель и требования к ним 14.37 KB
  Кровельные материалы. Кровли: Мягкие рулонные материалы мембраны мастичные Жёсткие листовые материалы штучные. Скатные кровли более 15 уклон штучные листовые материалы черепица металлочерепица рулонные.
30789. Устройство рулонных кровель 15.32 KB
  К вертикальной поверхности пополнительный слой гидроизоляции. Ковер начинают наклеивать с пониженных мест воронок внутреннего водостока ендов карнизов послойно: сначала первый слой по всей площади захватки после его проверки и приемки второй слой до 5. Наклейка : послойная слой за слоем по всей площади крыши ступенчатая3 5 слоёв сразу. Наплавляемый рубероид нижний слой полимерное покрытие нагревают путём разогрева газовыми горелками.
30790. Устройство мастичной кровли 14.78 KB
  К вертикальной поверхности пополнительный слой гидроизоляции. Разливают слой битумнополимерной мастики. В неё втапливают арматурный слой стеклосетку 34слоя. Сверху защитный слой мелкого гравия.
30791. Мембранные кровли 16.44 KB
  Наносится с использованием клеевой технологии. ТПО смесь каучука и полимеров повышающих механическую прочность менее эластичны ПВХ мембраны Способы соединения полотнищ: сварка горячим воздухом клеевой способ 2хсторонние склеивающие ленты Способы закрепления мембранных кровель: Баластный способ свободное положение закрепляют по периметру в местах примыкания к вертикальным поверхностям. Наносят клеевой состав и раскатывают катком.
30792. Устройство металлических кровель 13.66 KB
  Основание для покрытия кровельной сталью выполняют в виде обрешетки из деревянных брусков 50 х 50 мм и досок от 50 х 120 до 50 х 110 мм. Конек устраивают из соединяемых под углом досок. Расстояние между осями досок принимают равным 1390 мм чтобы стыки листов попадали на них.
30793. Устройство кровель из асбесто-цементных волокнистых листов (шифер) 13.2 KB
  Устройство кровель из асбестоцементных волокнистых листов шифер Волнистые асбестоцементные листы обыкновенного профиля и средневолнистые размером 678 х 1200 мм укладывают на деревянной обрешетке из брусьев сечением 60 х 60 мм. Для плотного прилегания листов к обрешетке и друг к другу карнизный брусок поднимают с помощью прокладок на 6 мм а последующие четные бруски на 3 мм. Плотное прилегание листов в рядах вдоль и поперек ската обеспечивают уменьшением количества слоев в нахлестке. Для этого при укладке обрезают углы двух листов или...
30794. Виды и назначение отделочных покрытий 14.22 KB
  Их назначение придать зданию или сооружению законченный вид отвечающий заданным утилитарным и эстетическим требованиям. Назначение отделочных работ защита строительных конструкций от вредных воздействий окружающей среды увеличение срока их службы и придание поверхностям красивого внешнего вида.