39414

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

Курсовая

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

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

Русский

2013-10-04

308.5 KB

27 чел.

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

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

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

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

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

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

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

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

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

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

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


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


 

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

57827. Урок-суд «Сталин – кто он?» 137 KB
  ЦЕЛЬ: обобщить и закрепить знания учащихся по теме «СССР в 30-е годы ХХ века», рассмотреть основные направления внутренней и внешней политики в этот период развития СССР на примере деятельности исторической личности Иосифа Виссарионовича Сталина...
57828. Запліднення. Генетичне визначення статі. Вагітність 72.5 KB
  Основне поняття: сперматозоїд яйцеклітина овуляція запліднення вагітність зигота ембріон плід плацента хромосоми. Робота в парах Слайд 3 Обличчям до обличчя один – у двох усі разом Девіз: Думати працювати у парі обмінюватися думками...
57829. Прийняття рішень в умовах невизначеності 527 KB
  Чим займається наука статистика Відповідь. Що таке математична статистика Відповідь. Що таке вибірка Навіщо використовують вибіркове спостереження Відповідь. Що таке ранжування Відповідь.
57830. Внутрішня будова стебла. Транспорт речовин по рослині 113 KB
  Мета уроку: Сформувати в учнів поняття про внутрішню будову стебла, зокрема кору, камбій, деревину, серцевину, їх будову і значення, про взаємозв’язок будови клітин і тканин стебла з їх фунціями...
57831. ВЛАСТИВОСТІ СТЕПЕНЯ ІЗ ЦІЛИМ ПОКАЗНИКОМ 2.17 MB
  Мета: працювати над засвоєнням учнями означення степеня з цілим показником та його властивостей; формувати вміння застосовувати означення і властивості степеня з цілим показником до обчислення значень виразів і перетворення виразів зі змінними...
57832. Перетворення виразів, що містять степінь з цілим показником 651 KB
  Число до якого ми підносимо основу степеня називається показником 3 Як називається число до якого ми підносимо основу степеня 3 Число яке ми підносимо до степеняназивається основою 4 Яке число ми отримуємо при піднесенні до...
57833. Степінь з цілим показником 79 KB
  Що називається степенем числа а з натуральним показником n 2. Парна степінь відємного числа завжди яке число 4. Непарна степінь відємного числа завжди яке число 5. Як називаються два дійсних числа сума яких дорівнює нулю 6.
57834. Штучні супутники Землі. Розвиток космонавтики 355.5 KB
  Розвивати творчу ініціативу і активність учнів, спостережливість, здатність логічно мислити, вміння робити висновки, узагальнення, розвивати пізнавальні здібності, навички працювати з науково-популярною літературою...
57835. Світ після Другої світової війни 756.5 KB
  При викладенні матеріалу застосовано дослідницькопошуковий метод і метод проектної роботи з історичним матеріалом розкрито творчий потенціал учнів. Продемонстровано різні методи...