close

Вход

Забыли?

вход по аккаунту

?

Алгоритм многомерного гиперкомплексного ДПФ реализуемый в кодах Гамильтона-Эйзенштейна.

код для вставкиСкачать
АЛГОРИТМ МНОГОМЕРНОГО ГИПЕРКОМПЛЕКСНОГО ДПФ,
РЕАЛИЗУЕМЫЙ В КОДАХ ГАМИЛЬТОНА-ЭЙЗЕНШТЕЙНА
Алиев М. В. 1, Чичева М. А. 2 , Алиева М. Ф. 1
1
2
Адыгейский государственный университет
Институт систем обработки изображений РАН
Аннотация
В работе синтезируется «совмещенный» алгоритм многомерного гиперкомплексного дискретного преобразования Фурье вещественного сигнала по основанию три с представлением данных в обобщенных кодах Гамильтона-Эйзенштейна. Получена сложность арифметических операций в коммутативно-ассоциативной гиперкомплексной алгебре и ее представлении в обобщенных кодах. Приводятся оценки вычислительной сложности синтезируемого алгоритма.
Определение 1. Упорядоченный набор вещестВведение
венных чисел η0 ,… , ηi ,… , η2d −1 таких, что:
В работе синтезируется «совмещенный» алгоритм
многомерного гиперкомплексного дискретного преобd
ι +1
разования Фурье (ГДПФ) вещественного сигнала:
h = ∑ ηi ⋅∏ γ jj ,
(5)
(
F (µ )=
где
N −1
∑
n1 ,…, nd =0
f ( ν ) W ( µ, ν ) ,
µ = ( m1 ,… , md ) ,
m1 ,… , md = 0,1,..., N −1 ,
W ( µ, ν ) = ∏
I ={1,… , d } ,
(1)
i∈I
ωimi ni
,
ωi = e
2 πεi
N
,
а
ε12 =...=ε d2 =−1 , ε1 ,… , ε d – образующие элементы
d
некоторой 2 -мерной коммутативно-ассоциативной
гиперкомплексной алгебры (КГА).
Как показано в ряде работ [3, 4] для синтеза быстрых алгоритмов ДПФ длины N = 3 p , p∈N предпочтительней использовать представление комплексных чисел и кватернионов в так называемых
циклотомических кодах ( γ− кодах). В настоящей
работе производится обобщение данного представления на случай многомерной КГА.
1. Коммутативно-ассоциативные
гиперкомплексные алгебры
d
гласно [1], будем называть 2 –мерную алгебру над
R с базисом:


Λ= ∏ εiαi , αi = 0,1 ,
(2)
 i∈I

где εi0 =1, ε1i =εi – образующие элементы со следующим правилом умножения:
εi ε j =ε j εi ,
i, j∈I .
(3)
Алгебра Bd представима в виде прямой суммы
2d −1 комплексных алгебр [1].
Введем следующие обозначения
γ i ∈C ( εi ) , γ i = e
2 πεi
3
, i∈I ,
(4)
а гиперкомплексные числа γi есть соответствующие образы в Bd элементов, сопряженных в C ( εi )
элементам γ i .
j =1
{
}
где T = 0,… , 2d −1 , i=ι1 … ιd , ι={0,1} назовем
обобщенным γ− кодом элемента h и будем обозначать h .
Множество
d
ι +1


ϒ= Γi = ∏ γ jj , i =ι1 … ιd , ι j ={0,1} ,
j =1


(6)
назовем базисом представления алгебры Bd , а по
лученную алгебру обозначим Bd . Данное представление элементов алгебры Bd однозначно и произвольный элемент g ∈Bd примет вид:
g = ∑ ξi Γ i .
i∈T
Пусть ψ ( j , t ) = ∏ ( −1)
Коммутативно-ассоциативной алгеброй Bd , со-
εi2 =βi ,
i∈T
)
hi ( j ,t )
i∈I
, где функция hi -
умножение i-го разряда двоичного представления
j , t . Тогда множество из 2d отображений σ j :
σ j : Bd →Bd ,
(7)
таких, что σ j ( χ ) = ∑ ci ψ ( j , i ) Ei , где χ∈Bd , ci ∈R ,
i∈T
j∈T , является множеством автоморфизмов алгеб-
ры Bd .
Заметим, что σ j ( Γi ) =Γi⊕ j , где
сложение
по
1+h j , j
σ j γi = γi i ( )
( )
основанию
= γi , i ∈ I ,
⊕
2,
– поразрядное
так
как
j ∈T . Тогда автомор-
физмы (7) алгебры Bd над R приводят к следующему преобразованию кодов
σ j ( g ) = ∑ ξ i⊕ j Γ i⊕ j ,
(8)
i∈T
причем переход от гиперкомплексного элемента к
его автоморфному образу реализуется в кодах три-
виально, путем перестановки, и не требует дополнительных вещественных умножений.
В работе [1] показано, что для любого d ≥1 существует только две различных коммутативноассоциативных алгебры: алгебра B+d , в которой
βi =1 для каждого i∈I и алгебра B−d , в которой существует i∈I такое, что βi =−1 .
Будем считать, что при оценке вычислительной
сложности рассматриваемых алгоритмов один из
сомножителей предполагается постоянным, поэтому
все арифметические операции над его компонентами могут быть реализованы заранее. Умножения на
степени числа 2 являются более простыми операциями, чем сложения и умножения и не учитываются при анализе вычислительной сложности алгоритмов ДПФ [2, 4].
Теорема 1. Умножение двух произвольных элементов в алгебре B−d можно реализовать за 3⋅2d −1
( 4d −1)⋅2d −1
вещественных умножений и
вещест-
венных сложений.
Доказательство. Пусть g = ∑ ξt Et , h = ∑ ηt Et ,
t∈T
d −1
ξ1 ∈B-d −1
t∈T
g , h∈B-d и η0d −1 , η1d −1 , ξ0d −1 ,
тогда данные
элементы можно представить в следующем виде:
h =η0d −1 +η1d −1 E , g =ξ0d −1 +ξ1d −1 E ,
где, согласно [1], E 2 =1 . Тогда
( )( η )+( η )( ξ )  ,
( )( η )−( η )( ξ ) 
 +
1 ξ
h⋅ g = 
2  ξ+

+
−
+
−
каждого шага значения η0d −k +η1d −k
)
hg
можно
(
ний и 3 3d − 2d
) вещественных сложений.
Доказательство. Заметим, что в обобщенных
кодах также имеет место соотношение:
g =αγ i +βγi , h = a γ i + b γi ,
(10)
α , β , a , b ∈Bd −1 . Тогда умножение
где
hg
можно реализовать за 3 умножения и за 3 сложения
обобщенных кодов размерности 2d −1 . Получаем
алгоритм вычисления умножения в обобщенных
кодах, аналогичный синтезированному в теореме 1.
Суммируя сложность на каждом шаге, получаем,
что умножение двух произвольных элементов алгебры Bd реализуется посредством 3d веществен-
∑ 3i 2d −i =3 ( 3d − 2d )
d
ных умножений и
веществен-
i=1
ных сложений, что и требовалось доказать.
Следствие 1. Пусть g∈Bk , h∈Bd , где k < d . Тогда умножение элементов
k d −k
посредством 3 2
3⋅2
d −k
(
k
⋅ 3 −2
k
и
g
h
реализуется
вещественных умножений и
) вещественных сложений.
2. Алгоритм многомерного ГДПФ
вещественного сигнала по основанию три
Пусть f ( ν )∈R - преобразуемый многомерный
) и (η
d −k
0
−η1d −k
)
могут быть рассчитаны заранее. Тогда количество
вещественных умножений можно сократить, используя на последнем шаге заранее вычисленное
произведение соответствующих констант. Следовательно, мультипликативная сложность вычисления
произведения двух произвольных элементов алгебры B−d составляет 3⋅2d −1 вещественных умножений.
Аналогичными рассуждениями получаем, что
аддитивная сложность умножения двух элементов
алгебры B−d составляет ( 4d −1)⋅2d −1 вещественных
сложений.
)
выполнить посредством 3d вещественных умноже-
(9)
где ξ ± =ξ0d −1 ±ξ1d −1 , η± =η0d −1 ±η1d −1 . Следовательно,
требуется выполнить два умножения элементов
КГА размерности 2d −1 и четыре сложения элементов КГА размерности 2d −1 . Применяя те же самые
рассуждения к Bd −1 и далее, получаем алгоритм
вычисления, на последнем шаге которого производится умножение элементов алгебры C (комплексных чисел). На k -ом шаге имеем 2k узлов, то есть
2k арифметических операций в алгебрах Bd −k . Для
(
(
h = η0 ,… , η2d −1 , тогда умножения
−
−
(
g = ξ0 ,… , ξ2d −1 ,
Пусть
Теорема 2.
(N )
d
– массив, N =3r . Его гиперкомплексный
спектр определяется соотношением (1). Константы
W ( µ, ν ) , ωi считаются заданными обобщенными
кодами Гамильтона-Эйзенштейна.
Спектр (1) можно представить в форме:
F (µ )=
2
∑
r1 ,…, rd =0
Fρ ( µ ) W ( µ, ρ ) ,
где
Fρ ( µ ) =
N −1
3
∑
n1 ,…, n2 =0
fρ ( 3ν + ρ )W ( µ,3ν + ρ ) .
Значения Fρ ( µ ) достаточно полностью вычислять для векторов µ∈∆ , где ∆ - фундаментальная
область:
∆= µ:0 ≤ m1 ,… , md ≤ N −1 .
3
{
}
Значения Fρ ( µ + a ) для векторов µ + a , лежащих
в областях, полученных из области ∆ аддитивными
сдвигами на векторы
Заключение
N
 N
a =  α1 ,… , α d  , αi = 0, 1, 2 ,
3
3

отличаются от соответствующих Fρ ( µ ) лишь множителями γ1 ,… , γ d , γ1 ,… , γd , и не требуют для вычисления дополнительных вещественных операций.
При вычислении Fρ ( µ ) достаточно ограничиться
значениями µ∈∆ 0 ⊂∆ :
(
)
1


∆ 0 = µ:0 ≤ m1 ,… , md ≤ N +1  .
3
2


Значения спектра в остальных точках области ∆
вычисляются с использованием тождеств:
(
σρ Fρ ( µ ) ω1aµ ωb2υ
(
)∏ γ
i∈I
αi +1
=
i
) (
= Fρ ( µ ) N ⋅a + µ W N ⋅a + µ
3
3
Умножения на
∏ γi
αi
)
и выполнение отображе-
ний σρ не требуют нетривиальных вещественных
умножений.
Учитывая сложность арифметических операций
в обобщенных γ–кодах, получаем:
( )
( )
A3d N d =
3d
4d − 3
3d −1
( )
(11)
( )
(12)
N d log 3 N + O N d ,
N d log3 N + O N d ,
d +1
( ) 4 3 −10 N log N + O ( N ) , (13)
( N ) , A ( N ) , G ( N ) соответственно
G3d N d =
где M 3d
4d −1
d
d
d
3
d
d
3
d
d
3
Благодарности
Работа выполнена при поддержке Министерства
образования РФ, Администрации Самарской области и Американского фонда гражданских исследований и развития (CRDF Project SA-014-02) в рамках
российско-американской программы «Фундаментальные исследования и высшее образование»
(BRHE); а также при поддержке Российского фонда
фундаментальных исследований (РФФИ), проекты
№№ 03-01-00736, 05-01-96501.
Литература
i∈I
M 3d N d =
Предлагаемое представление КГА позволяет
синтезировать алгоритмы ГДПФ по основанию три
произвольной размерности входного сигнала. При
этом с ростом размерности сложность алгоритма
возрастает достаточно медленно.
d
мультипликативная, аддитивная и общая сложность
алгоритма.
1. Алиев М.В. Быстрые алгоритмы d-мерного ДПФ вещественного сигнала в коммутативно-ассоциативных
алгебрах 2d размерности над полем действительных
чисел // Компьютерная оптика, 2002. № 24. C. 130-136
2. Алиев М.В., Чичева М.А. Алгоритмы двумерного
ДПФ с представлением данных в алгебре гиперкомплексных чисел // Алгебра и линейная оптимизация:
Труды международного семинара, посвященного 90летию со дня рождения С.Н. Черникова. Екатеринбург: УрО РАН, 2002. C. 18-26
3. Фурман Я.А., Кревецкий А.В., Передреев .К. Введение
в контурный анализ; приложения к обработке
изображений и сигналов // Под ред. Фурмана Я.А. М.:
ФИЗМАТЛИТ, 2002. 592с.
4. Geometric Computing with Clifford Algebra // Sommer G.
(Ed.). Berlin: Springer-Verlag, Springer Series in
Information Sciences, 2001.
5. Labunets E.V., Labunets V.G., Egiazarian K., Astola J.
Hypercomplex moments application in invariant image
recognition // Int. Conf. On Image Processing 98, 1998.
P. 256–261.
Документ
Категория
Без категории
Просмотров
3
Размер файла
238 Кб
Теги
многомерного, дпф, эйзенштейн, алгоритм, гамильтон, кода, гиперкомплексные, реализуемая
1/--страниц
Пожаловаться на содержимое документа