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

Целью настоящей работы является разработка быстрых алгоритмов вычисления так называемых «гиперкомплексных» дискретных преобразований Фурье (ДПФ) и анализ их вычислительных характеристик.

Интерес к многомерному преобразованию

N - 1

F ( mi, ^ , md ) = 2 f ( n^ — , ⁿ_n W ^т’^П>    (1)

” 1 , — , n d = 0

– аналогу классического ДПФ, где

d

W^m,” П wmknk , WN = 1, k=1

mm,n} = m1 n1 + — + mdnd , а корни wk N -й степени лежат в различных подалгебрах, изоморфных С, некоторой многомерной алгебры, наметился в последнее десятилетие.

Впервые такие преобразования в алгебре кватернионов были введены в [1], [2], как вспомогательные преобразования, способствующие снижению вычислительной сложности некоторых алгоритмов двумерного ДПФ. Различные версии алгоритмов этого класса рассмотрены в [3], [4].

Как самостоятельное преобразование, полезное при решении «анизотропных» задач обработки изображений, преобразование (1) для d = 2 рассматривалось в [5].

К настоящему времени различным теоретическим аспектам гиперкомплексных ДПФ и их практическим приложениям посвящено значительное число работ [6]-[15].

Настоящая работа посвящена, в основном, оптимизации выбора гиперкомплексной алгебры и структуры алгоритмов с точки зрения минимизации их мультипликативной сложности.

1. Коммутативно-ассоциативные гиперкомплексные алгебры

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

Пусть V есть d -мерное пространство над Ж с базисом £ ₁, £ 2 , — £ _d .

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

л = ща а= 0,1; i = {1,—,dИ,(2)

[ i e I где £,0 = 1, £ = £i. Определим умножения базис -ных элементов пространства V :

£i£j = £j£i, £i Pi, i, j e I.

Связывая с двоичными наборами индексов

(a1,—,ad) целые числа t e T, где T = {0,1,—,2d -1} t = a1 + a22 + — + ad 2d 1, aj e{0,1} можем занумеровать элементы множества Л :

a1

Et £1 — £d .(5)

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

Операция сложения в алгебре Bd осуществляется покомпонетно. Пусть g = 2 ^tEt, h = 2 ntEt, g, hе Bd,(7)

teTt тогда

(g+h) = 2(^t+nt)Et.(8)

t e T

Нетрудно проверить, что алгебра B _d является коммутативной группой относительно операции сложения.

Операция умножения элементов B _d , представленных в форме (6), определяется правилом умножения базисных элементов пространства V . Утверждение следующей леммы позволяет указать явную связь между номерами (4) сомножителей и номером элемента, являющегося произведением

Лемма 1. Пусть ® - поразрядное сложение по модулю 2:

® :TхT ^ T,t ® т = 2((ai + a/)mod2)2i-1 , (9)

где

t = (a1,—,ad), т = («;,—,ad);

t, т e T ; a i , a i = 0,1; i e I ,

функция h i : T х T ^ { 0,1 } (битовая конъюнкция)

определена равенством:

h i ( t , ^т ) = ^ai' ^a i ; i ^e I ,

а функция ^ : T х T ^ { - 1,1 } равенством:

^ ( t , T ) = n в ^{( t, T} ) , A = { - 1,1 } .

i e I

Тогда правила умножения базисных элементов Л можно записать в следующем виде:

E t E _T = ^ ( t, т ) E t . , V t, те T

Доказательство. Пусть, согласно (4),

Et =п S-, Ет =п ■■, i e I                 i e I тогда

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

Теорема 1. Для любого d >  1 существует только две неизоморфных 2 ^d -мерных алгебры с операциями, определенными соотношениями (8), (13):

в + = R + R + . + .R, '---------------V---------------'

2 d

Et ■ ET

п « рп <^a  п « "^ ² h^;""²

i e I      i e I         i e I

в- =с + с + _ + с, '---------------V---------------'

d

Учитывая, что ai + ai - 2hi (ai,a')i = ai + a/ mod2, получаем п =      Et „ = ^( t ,T) Et „• i e I

Таким образом, умножение произвольных элементов g, h e Bd можно записать в виде матричного произведения:

h ■ g = H ■ G ,                                (14)

где З - матрица размера 2 ^d х 2 ^d

Н = к . , * ( t . t ® • Х2 d X 2 d

,

а G – вектор-столбец

T

G = (& ,, ^ 2 d - 1 ) .

Так как ¥ ( t , t . i ) = 1 1, то умножения на ¥ ( t , t . i ) можно не учитывать. Поэтому вычисление произведения (14) требует не более 2^{2 d} вещественных умножений и 2 ^d ( 2 ^d - 1 ) вещественных сложений.

Из определения 1 непосредственно не следует единственность алгебры B _d , с базисом Л и умножением, порожденным соотношением (3).

Лемма 2. Если для некоторого l e I справедливо равенство P l = - 1, то I E t = 0.

t e T

Доказательство. Разобьем сумму I Et на две teT суммы, таким образом, что в одну будут входить 2

элемент s _z , а в другую нет, тогда получим:

Z Et2 = 2 Et2 + I Et2 =(1 + Pl) Z Et2 = 0

teT        teT             teT                      teT hl (t, l )*0          hi (t, l )=0                        hi (t, l )=0

.

Следствие 1 . Если существует t e T такое, что E ^ = - 1, тогда в алгебре B _d содержится ровно 2 ^{d - 1} элементов, квадрат которых равен ( - 1 ) .

Коммутативно-ассоциативную алгебру B _d , в которой p i = 1 для каждого i e I , будем обозначать в d .

где знак + означает прямую сумму алгебр.

Доказательство. Из Леммы 2 следует, что существует, по крайней мере, один базисный элемент st =-1, где l e I, пространства V (без ограничения общности можно считать, что l = 1). В базисе Л ему соответствует элемент E1. Выберем еще один элемент Et, такой что Et = 1 и h1 (t,1) = 0. Такой элемент существует, т.к. либо существует pl = 1, либо можно взять комбинацию slsk = El.k, где pl =-1, Pk =-1, l * 1, k * 1. Пусть hk (t, k) = 1, тогда любой элемент h e Bd можно представить в следующем виде:

h = I niEi = Z niEi + ieT            ieT hi (i, k )*0

+

2 ^ ( t , i ) n i E i E t i e T

( h i ( i , k ) = 0

E_t = a + bE_t ,

где a , b e B _d - 1 .

Таким образом, непосредственно проверяется, что отображение 0 : Bd ^ Bd-1 + (R + g), задаваемое следующим правилом h = a + yEt ^ (a + /,a + T(t, t) у) e Bd-1 -+ (R -+R), является изоморфизмом. Применяя последовательно 0 к Bd- 1 и так далее, несложной индукцией получаем

B + = B- + R + R + ... + R,

^{V 2} ( ^d - 1 )

а так как

B- = с, то, следовательно:

B- = с -+C + . -+C.

4 V ^

d

Соотношение (15) доказывается аналогично. Таким образом, утверждения теоремы доказаны.

Поэтому везде далее под алгеброй B_d будем понимать алгебру со следующим соотношением для умножений базисных элементов V :

s i s j = S j S i , si =d 1, s i = 1 i = 2, d . (17)

Легко проверить, что для произвольного номера l , где l e T , и операция ® есть поразрядное сложение по модулю 2, верны равенства:

0 ® 0 = l ® l , l ® 0 = 0 ® l , (18)

а для функции Y и произвольного номера l e T , справедливы равенства:

Y ( 0,0 ) = Y ( 0, l ) = Y ( l ,0 ) = p l Y ( l , l ) ,       (19)

и

Y ( 0,0 ® 0 ) = P l Y ( l , l ® 0 ) =

= Y ( 0, l ® 0 ) = Y ( l ,0 ® 0 ) .

Лемма 3. Пусть B есть одномерная подалгебра алгебры B _d , порожденная подпространством V 1 с V , с базисом { s _l } для любого l e I , тогда матрица умножения элементов g , h e B примет следующий вид:

h . J§ 0 ( % ^d П ) + П ( § 0 + P l § 1 ) ) g I § 0 ( П 1 ^d П 0 ) + П 0 ( § 0 + § 1 ) J '

Доказательство. С учетом соотношения (20) матрица умножения элементов g , h примет следующий вид:

,     fП 0 Pn ) f § 0

h ■ g = 1                  1’1

l П 1     П 0 J I § 1

после очевидных преобразований получим:

h ■ = § ( % ^d П ) + П ( § 0 + P l § 1 ) )

g l § 0 ( П ^d П 0 ) + П 0 ( § 0 ⁺ § 1 ) J '

Из соотношений (18),(19),(20) и Леммы 3 следует теорема.

Теорема 2. Пусть g = §0 + §1E1, h = П0 + П1E1, g, h e B , где

§0, §1, n0, n1 e B d d1, тогда операцию умножения h ■ g можно осуществить за 3 умножения и 3 сложения матриц размерности 2dd1, если считать, что (§0 + §1) и (§0 + Р§) выполнены заранее.

Следствие 2. Пусть g,h e B d , g = §0 + §1E1, h = П0 + П1E1, где §0, §1, Пе, П1 e Bdd1 и Ei = 1, тогда операцию умножение элементов h и g h■ = (§ + §1 )(П) + П1 ) + (П1 dП0)(§0 d§1)) g l(§0 + §1 )(П0 + П1 )d(n1 dП0)(§0 d§1 )J можно осуществить за 2 умножения и за 4 сложения d d1

матриц размерности 2   , если считать, что

( § ₀ + § 1 ) и ( § ₀ d § 1 ) выполнены заранее.

Следствие 3. Умножение в алгебре B d можно реализовать за 2 ^d вещественных умножений и 4 ^d вещественных сложений.

Следствие 4. Умножение в алгебре B d можно реализовать за 3 ■ 2 ^{d d 1} вещественных умножений и 3 ■ 4 ^{d d 1} вещественных сложений.

Следствие 5. Пусть g e B ^d , h e B ^d k <  d . Тогда умножение элементов g и h реализуется за 3 ■ 2 ^{d d 1} вещественных умножений и 3 ■ 4 ^{d d 1} вещест -венных сложений.

Следствие 6. Пусть g e B _k , h e B ^d k <  d . Тогда умножение элементов g и h реализуется за 2 ^d вещественных умножений и 3 ■ 4 ^{d d 1} вещественных сложений.

Теорема 3. Пусть у : T х T ^ { d 1,1 } :

V ( J , t ) = H ( d 1 ) h^{i (} j ’ t ) ,                           (22)

ieT тогда множество из 2d отображений стj :

®: Bd^B d , таких, что стj (X) = z cy (J, i)Ei ,                     (23)

ieT где x e Bd, ci e R, J e T, является множеством автоморфизмов алгебры Bd .

Доказательство. Для доказательства изоморфности необходимо проверить, что отображение биективно и сохраняет операции сложения и умножения.

Базисные элементы Л не являются делителями нуля, и отображения ст j - линейно. Таким образом, отображения ст j является биекцией.

Проверим, сохраняют ли отображения ст _j операции сложения и умножение. Пусть g , h e B представлены в форме (6), тогда должно выполняться:

^ст j ( g ^{+ h} ) = ^ст j ( g ) ^{+ ct} j ( ^h ) ,                    ⁽²⁴⁾

^ct j ( gh ) = ^ct j ( g ) ■ ^ct j ( ^h ) .                         ⁽²⁵⁾

Справедливость соотношения (24) очевидна:

^ct j ( g ^{+ h} ) = Z ( § i ⁺ n ) y ( ^J , i ) ^E i = i e T

= E § i V ( ^J , i ) ^E i ⁺ E W ( ^J , i ) ^E i = ^CT J ( g ) ^{+ CT} J ( ^h ) .

i e T                   i e T

Для доказательства соотношения (25) преобразуем правую часть этого равенства:

aj (gh) E E T ( t, t ®i) 6® nv( j, i) Ei = ieT teT

E n t E ^ ( t , t ® i ) ⁶ ® v ( j , i ) Ei - t e T i e T

Далее, используя соотношения (13), (18) и учитывая что i — t ® i ® t , получим:

E nv ( ^j , t ) ^ ( t , t ) E t E - ■ v ( j , i ® t ) ^ ( t , t ® i ) E i ® t t e T                          i e T

Так как i принимает все значения множества T , то и i ® t принимает все значения множества T . Поэтому, полагая т — t ® i , получаем:

E nv (j, t) Et E 6v( j ,t) et = aj (g )• aj (h).

t e T                Te T

Предположим a j ( x ) = a _p ( x ) для j * p , тогда последовательно получаем цепочку равенств:

^a j ⁽ X ) = ^a p ⁽ X )

,

П(-1)h,(j,1) —П(-1)h(p’ 1), 1 = 0,2d — 1, ieT                 ieT

E hi( j, 1 ) = E hi( P, 1), 1 = 0,2 d — 1, ieT             ieT которая приводит к противоречию: j = p . Из этого следует, что если j * p , тогда и aj (x) * ap (X)-Так как card T — 2d , то и различных автоморфизмов будет 2d .

Лемма 4. Пусть Q множество автоморфизмов (23) алгебры B _d . Пусть далее элемент x определен равенством (4). Тогда система уравнений относительно c_t :

a j ( x ) = n j ,    a j eQ ,                    (26)

имеет единственное решение при любых h = ( n o,..., n ₂ d - 1 )^{e B} d .

Доказательство. Рассмотрим матрицу

A =I k ^{( j} , i )l L d x 2 d -

Заметим, что k ( j , i ) = ^ ( j , i ) при P i = - 1, для любого i e I . Используя соотношение (19) матрицу A можно преобразовать к следующему виду:

А - ^f A ¹ A ¹ )

A              ,

V A1    A1J где

A 1 = ^{k (} j , i )l L d - ' x 2 d - 1 -

Поэтому detl V(j, i )l Ld x2 d =-2 • detlk( j, i )l Ld -x2 d-1 -

Применяя аналогичные рассуждения далее, получим det| V ( j , i )lL d x 2 d — ( - 1 ) ^{d 2 d} * ^0-

Отсюда следует существование и единственность решения.

Решение в общем виде выглядит следующим образом:

2dctEt = E v (t, i) a( h), te T - ieT

2. Алгоритм 2 ^d -мерного ГДПФ в алгебре B _d с декомпозицией по основанию 2

Пусть      н —(П1,.,nd),      м —(^1,.,md), с —(r1,., rd), F (v) - гиперкомплексное ДПФ:

N - 1

F ( м ) — E f ( н ) W ( м, н ) ,       (27)

n t , . , n d ^{— 0}

где

W (м, н) — П ®m'n', ®i— e^N - i e I

Тогда

F" ( м ) — E F C ( м ) W ( м, с ) —

Г Х .; r d — 0

1                   N 2 - 1

• — E W ( м.с ) E f ( н + с ) W ( м,2н ) , (28)

• r , . , r d ^{— 0}             n 1 , . n d ^{— 0}

где

_        NA ¹

F e ( м ) — E f ( н + с ) W ( м ,2 н ) ,

П 1 , . , n d — 0

0 <  m 1 , . , m_d <-- 1 -

Вычисление спектра для остальных значений вектора м производится без дополнительных умножений, а именно:

F ( м + N 2 ф ) — E ^ ( с , Ф ) F : ( м ) W ( м , с ) ,(29)

Г 1 , . , r d — 0

где ф— (t1,., td ), 0 < t1,..., td < 1-

Кроме того, умножения на фазовые множители W ( м , с ) достаточно выполнять только для фундаментальной области

Q0 —{0 < т1,.,md < N4}, остальные значения определяются с использованием автоморфизмов алгебры Bd без дополнительных умножений. Действительно, пусть вычислены значения

W(м,с)F (м), для мe Q0 и м1 — N2ф-м, тогда

W ( м 1 , с ) F e ( м 1 ) —Т ( с,ф ) a ф ( W ( м,с ) Т^ с ( м ) ) -    (30)

Таким образом, вычисление значений полного спектра в алгебре B _d производится в следующем порядке.

Шаг 1. Находятся значения суммы в (29) для м е Q 0 .

Шаг 2. По формуле (30) вычисляются элементы спектра в областях, отличающихся от Q 0 сдвигом на ^N ₂ по каждой из координат.

Шаг 3. Остальные области заполняются на основании следующих свойств ДПФ вещественного сигнала в алгебре B _d :

F ( N - фм ) = ст ф ( F ( N - фм ) ) .

Из сказанного выше с учётом сложности умножения (теорема 2 и следствия 3-6) следует, что для оценки мультипликативной сложности ГДПФ по модулю 2 в алгебре B - справедливо соотношение:

M ( N d ) = 2 ^dM ( (%) d ) + ^ ^d l 3 ■ 2 d ^{- 1} C d

N^d ₂2 d ^.

Упрощая, получаем

M ( N d ) = 2 ^dM ( ( N 2 ) ^d ) + JL ■ ( 2 ^d - 1 ) N^d . (32)

Суммируя, получаем

. . 3 ■ (2 ^d - 1)                          . .

M ( N d ) =    2 _{d + 1}  N d log₂ N + O ( N d ) =

= 2 ( 1 - F ] N d '° ^{8 2} N + O ( N d ) .

• 3.    Алгоритм 2 ^d -мерного Г ДПФ в алгебре B _d с декомпозицией по основанию 4

Пусть, как и выше,

H = ( ⁿ 1 , - ,n d ) , ^м = ( m b-, m d ) , с = ( r 1 , - ,r d ) ,

F ( v ) - гиперкомплексное ДПФ (27). Тогда

F ( м ) = S F ( м ) W ( м, с ) =

Г , - , r d = 0

N

3/4

= S W ( мс ) £ f ( н + с ) W ( м ,4 н ) , ^r 1 . - . r d = 0             ⁿ 1 , - n d = 0

где

.N44

F (м)=  S  f (н + C) W (м>4н),(34)

n ,..., n d = 0

N

Вычисление спектра для остальных значений вектора м производится без дополнительных умножений, а именно:

^F ( м + N 4 ^ф ) =   S П s ir ■ F c M W ( м^с ) , ⁽³⁵⁾

Г-,rd =0 ‘еI где

N

• ^ф = ( t 1,---, t d ) , ⁰ <  t 1 , - , t d ^ J.

Кроме того, умножения на фазовые множители W ( м , с ) достаточно выполнять только для фундаментальной области

Q1 ={0< m1,-,md < N8}, остальные значения определяются с использованием автоморфизмов алгебры Bd без дополнительных умножений. Действительно, пусть вычислены значения

W(м,с)Fc (м), для ме Q1 и м1 = N4 ф-м, тогда

W ( ^м 1 , ^с ) 1 ^ с ( м 1 ) = П s r ■ ^ст ф ( W ( м> ^с ) ^F ( ^м ) ) .(36) i е I

Окончательное вычисление значений спектра в алгебре B _d производится в следующем порядке.

Шаг 1. Находятся значения суммы в (35) для м е Q 1 .

Шаг 2. По формуле (36) вычисляются элементы спектра в областях, отличающихся от Q 1 сдвигом на ^N ₄ по каждой из координат.

Шаг 3. Остальные области заполняются на основании свойств (31) ГДПФ вещественного сигнала в алгебре B _d .

Из выше сказанного с учётом сложности умножение (теорема 2 и следствия 3-6) следует, что для оценки мультипликативной сложности ГДПФ по модулю 4 в алгебре B ^- справедливо соотношение:

M ( N d ) = 4 ^dM ( ( N 4 ) ^d ) + 3 ■ 2 ^{d - 1} ( 2^{2 d} - 1 ) N d- .

Упрощая, получаем

M ( N d ) = 4 ^dM ( ( N 4 ) d ) + 2 2 3 + 1 ■ ( 2^{2 d} - 1 ) N d .(37)

Суммируя, получаем

. . 3(4 ^d - 1)                        . .

M ( N d ) = ^v4 d +1 ' N d '°g₂ N + O ( N d ) =

= 4 ( 1 - dd } N d '°g₂ N + O ( N d ) .          (3 ⁸ )

Заключение

Рассмотренные в работе быстрые алгоритмы гиперкомплексных ДПФ обладают уменьшенной вычислительной сложностью по сравнению с описанными в [9], [11], [12]. Снижение вычислительной сложности обеспечивается одновременным применением двух взаимосвязанных идей:

• •    использования принципа совмещенного вычисления частей спектра, что, в свою очередь, представляет собой одну из форм учета «избыточности» представления вещественного числа как элемента 2 ^d –мерной гиперкомплексной алгебры.

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