Быстрое преобразование Фурье

но часто, то целесообразно  фазовые множители вычислять  всего один раз и

хранить их в массиве как  константы. Индекс для элемента массива  фазо-

вых множителей можно вычислять  по выражению k

k

q

l j rq / r

0

÷ ÷

ø

ö

ç ç

è

æ

× × Õ=

, которое

легко реализуется без  операций умножения и деления  для любого этапа ал-

горитма БПФ k (2.32) – (2.34).

При описанной выше реализации обобщенного алгоритма БПФ по

смешанным основаниям (2.32) – (2.34) выражение для дисперсии ошибки

округления (2.57) будет совпадать  с приведенным в работе [23] выражени-

ем для алгоритмов БПФ  по основанию 2 с точностью до значения члена

ak ·D2. Количество комплексных  сложений в обоих случаях совпадает,  раз-

личается только количество комплексных умножений. Однако количество

умножений в [23] определяется очень грубо, и дисперсия ошибки, вноси-

мой умножением, в шесть  раз меньше дисперсии ошибки, вносимой сло-

жением. Эти обстоятельства позволяют для оценки верхней  границы дис-

персии ошибки реализации обобщенного алгоритма БПФ по смешанным

основаниям использовать выкладки и выражения из работы [8]. Тогда вы-

ражение для верхней границы  стандартного отклонения ошибки реализа-

ции алгоритма БПФ по смешанным  основаниям (sош) в зависимости от

разрядности операндов (s) и длины блока данных (N) можно записать

(2.58)

0.3 2 s 8 N.

sош » × × × - (2.58)

Если известно допустимое стандартное отклонение ошибки реализа-

ции обобщенного алгоритма  БПФ sдоп, то на основе зависимости (2.58)

легко получить разрядность  операндов, обеспечивающую заданное допус-

тимое стандартное отклонение ошибки (2.59)

s log 0,3 8 N ,

доп

2 ê

êë

é

ú úû

ù

÷ ÷ø

ö

ç çè

æ

s

× ×

= (2.59)

где sдоп – допустимое стандартное отклонение ошибки реализации алго-

ритмов дискретной циклической  свертки;

– 67 –

]·[ – функция округления  до целого в большую сторону.

2.10.2. Обобщенный гнездовой  алгоритм БПФ

В работе [6] приведен обобщенный гнездовой алгоритм БПФ. Осно-

вой рассматриваемого обобщенного  гнездового алгоритма БПФ являются

базовые алгоритмы Винограда [1, 25] для малых размерностей блоков

входных данных ni = (2, 3, 4, 5, 7, 8, 9, 16). Базовые алгоритмы имеют вид

X = Ci Bi Ai x,

где x – блок входных данных размерности (ni); Ai – матрица предсложений

размерности (ni' ´ ni), элементами матрицы являются целые числа 0, -1, 1,

2. Умножение матрицы на  вектор x реализуется без нетривиальных умно-

жений; Bi – диагональная матрица размерности (ni' ´ ni'), элементами мат-

рицы являются вещественные числа; Ci – матрица постсложений размер-

ности (ni ´ ni'). Элементами матрицы являются комплексные числа 0, ±1,

± -1 (либо 0, либо чисто мнимые, либо вещественные). Умножение мат-

рицы C на вектор размерности ni' вещественных или комплексных чисел

реализуется без нетривиальных  умножений; X – блок выходных данных

(результат) размерности ni.

Матрицы базовых алгоритмов Винограда приведены в справочной

литературе, например [1, 25]. Из вышеописанного следует, что базовые  ал-

горитмы реализуются за ni' умножений. Однако при анализе матриц Bi,

видно, что некоторые диагональные элементы этих матриц равны единице.

Число нетривиальных умножений  в базовых алгоритмах меньше ni'.

Если Õ

-

=

=

1

0

m

k

N nk (где nk – взаимно простые числа из множества про-

стых чисел и их степеней, а m – число вложений гнездового алгоритма), то

гнездовые алгоритмы предполагают преобразование одномерной входной

последовательности в m-мерную таблицу (переиндексация на входе), обра-

ботку m-мерной таблицы с помощью матриц базовых алгоритмов

Ak, Ck, k = 0, ..., m - 1 и m-мерной таблицы Bb, полученной из матриц базо-

вых алгоритмов Bk, k = 0, ..., m - 1, и преобразования результирующей m-

мерной таблицы в одномерную (переиндексация на выходе). Нетривиаль-

ные умножения в гнездовом  алгоритме возможны только при обработке m-

мерной таблицы таблицей Bb.

При организации третьего метода масштабирования выражение  для

вычисления дисперсии  ошибки округления можно записать

при возникновении переполнения;

ïî

ïí ì

+ D

× + × ×D

=

-

-

2

1

2

2 1 4 6

k

k

k D

D

D

при обработке таблицей Bb.

(2.60)

– 68 –

Начальное значение дисперсии D-1 = 0. Предположим, что перепол-

нения для случая (2.48) возникли m раз. Выведем формулу для дисперсии

ошибки Dm-1 при возникновении переполнений, для чего запишем

D0 = 2 · D -1 + 4 · 6 · D2,

D 1 = 2(2 · D -1 + 4 · 6 · D2) + 4 · 6 · D2,

D 2 = 2(2(2 · D -1 + 4 · 6 · D2) + 4 · 6 · D2) + 4 · 6 ·D2,

D i = 2( ... 2(2 · D -1 + 4 · 6 · D2) + 4 · 6 · D2 ... ) + 4 · 6 · D2,

... и методом индукции  получим

Dm-1 = 2m· D-1 + (2m - 1)·( 4 · 6 · D2). (2.61)

При обработке таблицей Bb (поэлементное умножение двух

m-мерных таблиц) переполнений не может быть, поэтому нет множителей

2 и 4 в выражении (2.60). Для оценки верхней границы  дисперсии ошибки

округления необходимо знать  матрицы предсложений Ak и постсложений

Ck, чтобы определить максимально возможное количество переполнений

при обработке m-мерной таблицы  этими матрицами. Определим сначала

коэффициенты максимального  увеличения мощности отсчетов при обра-

ботке m-мерной таблицы данных матрицами предсложений (KAi) и пост-

сложений (KCi). Очевидно, эти коэффициенты равны максимальному коли-

честву ненулевых элементов  в строке для каждой матрицы. Тогда  макси-

мальное количество переполнений при обработке m-мерной таблицы дан-

ных матрицами предсложений (PAi) и постсложений (PCi) будут на единицу

меньше соответствующих  коэффициентов максимального увеличения

мощности отсчетов, т. е.

PAi = KAi - 1,

PCi = KCi - 1.

Сведем описанные коэффициенты для матриц базовых алгоритмов

БПФ, приведенных в работах [1, 25], табл. 2.2.

Таблица 2.2

Коэффициенты для матриц базовых алгоритмов БПФ

ni

Размерность

матрицы Ai

KAi PAi Размерность

матрицы Ai

KCi PCi

2 2 ´ 2 2 1 2 ´ 2 1 0

3 3 ´ 3 3 2 3 ´ 3 3 2

4 4 ´ 4 4 3 4 ´ 4 2 1

5 6 ´ 5 5 4 5 ´ 6 5 4

7 9 ´ 7 7 6 7 ´ 9 7 6

8 8 ´ 8 8 7 8 ´ 8 4 3

9 11 ´ 9 9 8 9 ´ 11 8 7

16 18 ´ 16 16 15 16 ´ 18 8 7

– 69 –

На основе формул (2.60), (2.61) и табл. 2.2 запишем алгоритм оценки

верхней границы дисперсии (Dош) и стандартного отклонения (sош) ошибки

реализации обобщенного  гнездового алгоритма БПФ в виде (2.62) – (2.67).

D-1 := 0; (2.62)

: 2 (2P 1)24 2 , = 0,..., -1;

1

D Ak D Ak k m k

P

k = - + - D (2.63)

: 2 ;

Dm = Dm-1 + D (2.64)

: 2 (2 1)24 2 , = +1,...,2 ;

-1

D Ck-m-1D PCk-m-1 k m m

k

P

k = + - D (2.65)

Dош := D2m; (2.66)

sош := Dош . (2.67)

Выражение (2.62) задает начальное  значение дисперсии, выражение

(2.63) определяет дисперсию  ошибки при обработке m-мерной таблицы

данных матрицами предсложений, выражение (2.64) – при обработке m-

мерной таблицы Bb, выражение (2.65) – матрицами постсложений, а выра-

жения (2.66), (2.67) определяют соответственно значения дисперсии и

стандартного отклонения ошибки реализации обобщенного гнездового ал-

горитма БПФ.

Введя обозначения å-

=

=

1

0

m

i

Ai A P S , å-

=

=

1

0

m

i

SC PCi , легко получить формулы

для Dош и sош (2.68) и (2.69) соответственно

Dош = 2SC D2 (24 × 2SA - 23) + (2SC -1)24D2 , (2.68)

s = D 2SC (24 × 2SA - 23) + 24 × (2SC -1) =

ош

= 2-s 2SC (24 × 2SA - 23)/12 + 2 × (2SC -1). (2.69)

Приведенные формулы (2.68), (2.69) позволяют оценить верхнюю__

 

Введение в проблему

Дискретное преобразование Фурье (ДПФ) широко применяется при

анализе дискретных сигналов для выделения из них основной информа-

ционной части. Подобная обработка  необходима для процессов сжатия

и восстановления информации при передаче аудио- и видео-сигналов на

большие расстояния, а также  при анализе томографической  информа-

ции и т.п. Ввиду чрезвычайно  больших объемов подобной информации

были разработаны быстрые  методы ее обработки: быстрое преобразо-

вание Фурье (БПФ Кули-Тьюки), алгоритм Винограда и др. Основная

идея этих методов —  в однократной обработке часто  встречающихся

в преобразовании одинаковых выражений; эта идея реализуется  соот-

ветствующей группировкой выражений  и правильной последовательно-

стью их вычисления. Многие из этих методов допускают эффективное

распараллеливание, а следовательно, — эффективную реализацию на

параллельных вычислительных системах (ПВС). Во многих случаях эта

задача облегчается тем, что каждая параллельная система  снабжается

средствами параллельного  программирования; в большинстве  случаев

— это интерфейс MPI — Message Passing Interface (см., например, [2],

с. 153-159), реализованный на параллельных системах обычно в языках

C, C++ и F ortran в виде библиотеки  процедур. Использование этого

стандарта в значительной степени гарантирует переносимость  и мас-

штабируемость (т.е. независимость  программы от числа используемых

процессоров и других устройств); таким образом, полученную програм-

му можно использовать на других параллельных системах (см. [3], с.

275-300).

на введение