Многомерное гиперкомплексное ДПФ: параллельный подход

В работе [1] было дано определение многомерного ГДПФ вещественного сигнала:

N - 1

F ( m n-, m d ) = Е f ( n ^-, n d ) W < ^m,n > , n i ,.., n d = o

d

W < m , n > = n w m k n k , w N = 1,                    (1)

k = 1

предложены и исследованы алгоритмы параллельного вычисления этого преобразования в двумерном случае. Однако, во-первых, существует интерес к вычислению ГДПФ больших размерностей [2], [3], [4], а, во-вторых, проблема эффективных вычислений с гиперкомплексными числами не ограничивается быстрой реализацией ГДПФ [5, 6, 7, 8].

Таким образом, в статье рассматривается многомерная гиперкомплексная алгебра и способ параллельной реализации вычислений с элементами этой алгебры, основанный на ее структуре. Затем предлагается параллельный алгоритм многомерного ГДПФ, использующий разработанный способ вычислений.

Многомерная гиперкомплексная алгебра

Ниже приводятся некоторые сведения о структуре рассматриваемой многомерной гиперкомплексной алгебры (см., например, [9]).

Определение. Коммутативно-ассоциативной гиперкомплексной алгеброй B _d будем называть 2 ^d -мерную R -алгебру с базисом:

Л = Щsа, а, е{0,1} ; I = {1,...,d} ., I ieI                                                  ,

где s ⁰ = 1, s 1 = s i . Закон умножения базисных элементов алгебры индуцирован следующим правилом преобразования произведений базисных элементов пространства V :

^s i ^s j =^s j ^s i , ^{s 2} = ^в i , i , j ^e I , ^в i = ± 1

Произвольный элемент g e B d записывается в виде:

g __i: E 0 + ™ ■- . d _ 1 E ₂ d _ 1 Е - t E t ,          (2)

teT где Et =ns“' , t = Е^2М e T ={o,1,...,2d-1}.

i e I             i e I

В этой гиперкомплексной алгебре операция сложения выполняется покомпонентно. Умножение определяется правилами умножения базисных элементов:

EtEт=^(t,т)EtФт, vt,тг T , где Ф - поразрядное сложение по модулю 2,

Т(t,т) = ПРhi(t’т) ’ hi (t’т) = аiа‘, ie I

т = Еа ‘ 2 i-1.

i e I

Доказательство приведенных соотношений может быть найдено, например, в [9]. Ниже мы будем рассматривать 2d -мерную гиперкомплексную алгебру в d = c+c+...+c,

2 d - 1

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

В этом случае существует, по крайней мере, один элемент а i , которому соответствует р i = - 1 . Далее, без потери общности, будем считать, что Р 1 =- 1 и в i = 1 для остальных значений i e I .

Как показано в [9], такая структура обеспечивает наименьшее количество вещественных операций необходимых для выполнения умножения и сложения элементов алгебры B d . Кроме того, в этом случае существует возможность синтеза эффективного алгоритма распараллеливания арифметических операций над элементами алгебры.

Параллельные вычисления в алгебре B _d

В работе [1] предложен алгоритм вычислений в четырехмерной гиперкомплексной алгебре B ₂ с распараллеливанием операции умножения на 2 ветви.

Пусть произвольный элемент g e B d определяется соотношением (2). Разобьем множество { E t } _{t e} T на две части: t e T ‘ , если E_t не содержит сомножителя S 1 , и t e T" в противном случае. При выбранном способе нумерации элементов первое подмножество будет содержать E_t для четных t , а второе - для нечетных. Введем замену переменных:

U _o = A E _o , U 1 = A E 1 ,                             (3)

где

E ^o = ^{ E t ^} t e T' , E ¹ = ^{{ E t }} t e T ",

U o =

u 0

^u 1

( u 2 d - 1

A = 1

1  1 -П

1   1 -

1 -1 -1

-1   1 -

Каждая строка и каждый столбец матрицы A содержат ровно 2 ^d-2 отрицательных чисел из 2 ^d-1 значений.

Правило умножения новых базисных элементов записывается в виде:

, f Pu j ,        if ^j <  P ,

U/ = 1

^j    - pU - - - 1 if j >  p ,

L      ^{j - 2}

f pu k , if ^k = ^j + p ,

U j U k = 1

J      L0,     otherwise, где p = 2d-1. Заметим, что многие произведения равны нулю. Это позволяет нам представить произведение двух произвольных элементов алгебры Bd следующим образом:

g.s V _ t E t -^ E _t = £ a t u t •£ b _т и т = t e T те Г        t e T      те Г

= Е ( a t u t ⁺ a t + p u t + p )( ^ь и ⁺ b t + p u t + p ) , t e T '

так как остальные слагаемые будут включать произведение U j U k = 0 .

Таким образом, произведение двух произвольных элементов алгебры B d сводится к p независимым произведениям, каждое из которых требует трех вещественных умножений и трех вещественных сложений (по аналогии с умножением комплексных чисел).

В таком представлении вычисления могут быть распараллелены на p независимых ветвей, не требующих обмена данными. Так как замена переменных линейна, сложение остается покомпонентным.

Можно показать, что для произвольного g е B - переход к новому представлению требует 4 d ^{- 1} вещественных сложений. Однако для вещественных и комплексных чисел не требуется выполнения каких-либо нетривиальных арифметических операций. Обратный переход к исходному представлению так же требует 4 d ^{- 1} вещественных сложений.

Пример 1: d =2. См. [1].

Пример 2 : d =3. Произвольный элемент восьмимерной гиперкомплексной алгебры B ₃ имеет вид: