Разработка программно-математического обеспечения корреляционного совмещения изображений с использованием быстрого преобразования Фурье
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
а четную и нечетную последовательности (обозначены красными и синими стрелками). Потом четная и нечетная последовательности в свою очередь делятся на четную и нечетную последовательности. При N=2L такое деление можно делать (L-1) раз. В нашем случае L=3. Данная процедура называется двоично-инверсной перестановкой, так можно выполнить перенумерацию отсчетов переписав номер отсчета в двоичной системе в обратном направлении. Например s(4) имеет индекс в десятичной системе счисления 410=1002, если же 1002 переписать справа налево то получим 0012, то есть s(4) после разбиения на четные нечетные перед первой операцией Бабочка встанет на место s(1), которая в свою очередь встанет на место s(4). По аналогичному правилу поменяются местами все отсчеты, при этом некоторые останутся на месте, в частности s(2), так как если 210=0102 переписать справа налево то все равно останется 0102, аналогично s(0), s(5) и s(7). Очень важно понять, что данный метод перенумерации должен применяться при записи числа в двоичной системе состоящей из L разрядов.
Можно сказать что напрямую двоично-инверсная перестановка удобна когда заранее количество отсчетов входного сигнала фиксировано, однако в универсальных алгоритмах БПФ на различные размеры N, двоично-инверсная перестановка не эффективна, проще и быстрее поменять отсчеты местами.
После двоично-инверсной перестановки получаем четыре 2-точечных ДПФ:
(3.67)
На основе четырех 2-точечных ДПФ формируются два 4-точечных ДПФ:
(3.68)
И на последнем уровне формируется полный спектр входного сигнала.
Поворотные коэффициенты
Рассмотрим подробнее поворотные коэффициенты .
На первом уровне (выражение (3.67)) требуется всего один поворотный коэффициент , это означает что на первом уровне расчета спектра операции умножения не требуются (умножения на 1 называются тривиальными, так как при умножении на 1 множитель остается неизменным или меняет свой знак на противоположный).
На втором уровне имеем два поворотных коэффициента: ;
(3.69)
Умножение на мнимую единицу также можно считать тривиальным, так как реальные и мнимые части комплексного числа просто меняются местами и изменяют свой знак.
На третьем уровне имеем уже 4 поворотных коэффициента:
(3.70)
Графически поворотные коэффициенты можно представить как векторы на комплексной плоскости (рисунок 3.12):
Рисунок 3.12 - Поворотные коэффициенты алгоритма БПФ с прореживанием по времени при N=8
Можно заметить что на всех уровнях объединения количество поворотных коэффициентов удваивается, причем все поворотные коэффициенты предыдущего уровня объединения присутствуют и на следующем уровне. Таким образом для того чтобы перейти на следующий уровень необходимо между поворотными коэффициентами текущего уровня вставить поворотные коэффициенты следующего. Графически для перехода на следующий уровень при N =16 необходимо дополнить рисунок 3.12 как это показано на рисунке 3.13. Серые вектора показывают поворотные коэффициенты, которые будут присутствовать на последнем уровне при N=16, которых нет при N=8 .
Рисунок 3.13 - Поворотные коэффициенты алгоритма БПФ с прореживанием по времени при N=16
Необходимо также отметить, что все поворотные коэффициенты за исключением нулевого, находятся в нижней полуплоскости комплексной плоскости.
Вычислительная эффективность алгоритма БПФ с прореживанием по времени
Алгоритм с прореживанием по времени на каждом уровне требует N комплексных умножений и сложений. При N=2L количество уровней разложения - объединения равно L, таким образом общее количество операций умножения и сложения равно LN.
Рассмотрим во сколько раз алгоритм БПФ с прореживанием по времени эффективнее ДПФ. Для этого рассмотрим коэффициент ускорения K отношение количества комплексных умножение и сложений при использовании ДПФ и БПФ, при этом учтем что L=log2(N)
раз. (3.71)
В таблице ниже приведено требуемое количество операций Mоп для алгоритма ДПФ при различном N=2L и при использовании БПФ с прореживанием по времени.
Таблица 3.1. Эффективность БПФ с прореживанием по времени
L4681012N166425610244096Mоп ДПФ256409665536104857616777216Моп БПФ6438420481024049152К, раз410,732102,4341
Из таблицы хорошо видно, что использование БПФ приводит к существенному уменьшению требуемого количества вычислительных операций. Так например при Т=1024 БПФ требует в 100 раз меньше операций чем ДПФ, а при Т=4096 в 341 раз. Первое опубликование данных результатов произвело эффект разорвавшийся бомбы, всколыхнув всю научную общественность. При этом очень важно, что выигрыш по производительности тем больше, чем больше размер выборки N. Так например при N=216 выигрыш составит216/16=212=4096 раз.
Таким образом, для получения эффективного алгоритма БПФ по основанию 2 с прореживанием по времени, при N=2L необходимо:
Осуществить двоично-инверсную перестановку отсчетов входного сигнала, тем самым обеспечив разбиение последовательности.
Используя поворотные коэффициенты сделать N/2 операций Бабочка согласно выражению (3.68) для получения первого объединения
Повторить операцию Бабочка согласно выражению (3.68) для объединения на следующий уровень еще L-1 раз, также используя поворотные коэффициенты.
На выходе получим ДПФ входной последовательности.
3.9 Алгоритм