Быстрые алгоритмы гиперкомплексного дискретного преобразования Фурье тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Алиев, Марат Вячеславович

• Алиев, Марат Вячеславович
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Алиев, Марат Вячеславович

Перечень сокращений и основных обозначений.

ВВЕДЕНИЕ.

ГЛАВА 1. ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ ИЗ АЛГЕБРЫ И ТЕОРИИ БЫСТРЫХ АЛГОРИТМОВ ДИСКРЕТНЫХ ОРТОГОНАЛЬНЫХ ПРЕОБРАЗОВАНИЙ.

1.1. Конечномерные алгебры.

1.1.1. Матричное представление операций.

1.1.2. Процедура удвоения Грассмана-Клиффорда.

1.1.3. Сложность операций в гиперкомплексных алгебрах.

1.1.4. Представление комплексных чисел в у -кодах.

1.2. Быстрые алгоритмы дискретного преобразования Фурье.

1.2.1. Декомпозиция Кули-Тьюки.

1.2.1.1 Декомпозиция Кули-Тьюки "по основанию два".

1 Г.! ? „'т • ••!'?т .•*. ванию четыре".

1.2.3.3. Декомпозиция Кули-Тьюки "с расщеплением основания" (сплит-радикс алгоритм).

1.2.2. Декомпозиция многомерных ДПФ.

1.2.3. Совмещенные алгоритмы ДПФ.

1.3. Гиперкомплексные ДПФ вещественного сигнала.

1.3.1. Кватернионное ДПФ вещественного сигнала.

1.3.1.1. Алгоритм КДПФ с декомпозицией "по основанию два".

1.3.1.2. Алгоритм КДПФ с декомпозицией "по основанию четыре".

1.3.1.3. Алгоритм КДПФ "с расщеплением основания".

ГЛАВА 2. ИССЛЕДОВАНИЕ СТРУКТУРЫ ИСПОЛЬЗУЕМЫХ

КОНЕЧНОМЕРНЫХ АЛГЕБР.

2.1. Четырехмерная коммутативно-ассоциативная гиперкомплексная алгебра.

2.2. Арифметическая сложность операций в двумерной коммутативноассоциативной гиперкомплексной алгебре.

2.3. Представления четырехмерной ассоциативно-коммутативной гиперкомплексной алгебры в у - кодах.

2.4. Арифметическая сложность операций в у-кодах.

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

2.6. Арифметическая сложность операций в многомерной коммутативно-ассоциативной гиперкомплексной алгебре.

2.7. Представления в обобщенных у - кодах.

2.8. Арифметическая сложность операций в обобщенных у - кодах.

2.9. Выводы и результаты главы 2.

3. БЫСТРЫЕ АЛГОРИТМЫ ГИПЕРКОМПЛЕКСНОГО ДПФ.

3.1. Алгоритмы двумерного гиперкомплексного ДПФ.

3.1.1. Совмещенный алгоритм двумерного ГДПФ вещественного сигнала.

3.1.1.1. Алгоритм двумерного ГДПФ гиперкомплексного сигнала по основанию два".

3.1.1.2. Алгоритм двумерного ГДПФ гиперкомплексного сигнала по основанию четыре".

3.1.1.3. Алгоритм двумерного ГДПФ гиперкомплексного сигнала с векторным расщеплением".

3.1.2. Использование принципа симметрий гиперкомплексной алгебры при синтезе ГДПФ.

3.1.2.1. Алгоритм двумерного ГДПФ вещественного сигнала "по основанию два".

3.1.2.2. Алгоритм двумерного ГДПФ вещественного сигнала "по основанию четыре".

3.1.3. Сравнительный анализ вычислительной сложности алгоритмов двумерного ГДПФ.

3.2. Алгоритм двумерного ГДПФ вещественного сигнала с декомпозицией "по основанию три".

3.3. Алгоритмы многомерного ГДПФ в алгебре Е»^.

3.3.1. Совмещенные алгоритмы многомерного ГДПФ вещественного сигнала.

3.3.1. Алгоритм многомерного ГДПФ гиперкомплексного сигнал с декомпозицией "по основанию два".

3.3.2. Алгоритм многомерного ГДПФ гиперкомплексного сигнал с декомпозицией "по основанию четыре".

3.3.3. Алгоритм многомерного ГДПФ гиперкомплексного сигнала "с векторным расщеплением".

3.4. Алгоритм многомерного ГДПФ вещественного сигнала "по основанию три".

3.5. Сравнительный анализ вычислительной сложности алгоритмов.

3.6 Результаты и выводы главы 3.

Введение диссертации (часть автореферата) на тему «Быстрые алгоритмы гиперкомплексного дискретного преобразования Фурье»

Целью работы является разработка вычислительно эффективных (быстрых) алгоритмов дискретных ортогональных преобразований со значениями спектра в гиперкомплексных алгебрах.

Актуальность темы. Историю быстрых алгоритмов обработки сигналов принято отсчитывать с 1965 г., когда Кули и Тьюки [118] опубликовали свой быстрый алгоритм вычисления дискретного преобразования Фурье (БПФ), хотя ранее Гуд (1960г.) и Томас (1963г.) опубликовали в практически незамеченных современниками работах [133, 151] свои быстрые алгоритмы дискретного преобразования Фурье, базирующиеся на несколько ином подходе. За время, прошедшее с первых публикаций, дискретный спектральный анализ стал одним из основных средств решения задач цифровой обработки сигналов, распознавания образов, машинного зрения, компьютерной оптики и т.д.

Разработке эффективных (быстрых) алгоритмов вычисления спектров различных дискретных преобразований посвящено большое количество публикаций, как у нас в стране, так и за рубежом [16, 18, 19, 20, 25, 26, 30, 34, 35,44-46, 52, 54, 58, 60, 68, 72-76, 84, 86, 95, 107-108, 110, 116, 148, 152].

Значительный вклад в развитие общей теории дискретных преобразований и их быстрых алгоритмов внесли С.С. Агаян, Н.Н. Айзенберг, В.А. Власенко, В.Г. Лабунец, A.M. Крот, A.M. Трахтман, В.М. Чернов, Л.П. Ярославский, Р. Агарвал, Ш. Виноград, Г. Нуссбаумер, Ч. Рейдер и др.

Высокоэффективные алгоритмы конкретных преобразований, адаптированные к характеристикам применяемых вычислительных средств разработаны И.Е. Капориным, Е.Е. Тыртышниковым, A.M. Григоряном и другими исследователями [29,30, 37, 41, 64, 66, 67, 110, 121-123, 150, 153-156].

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

1) синтез параметрических семейств новых ортогональных базисов со структурой быстрых алгоритмов, инвариантной по отношению к той или иной принятой авторами концепции синтеза таких алгоритмов (кронекеровская факторизация, полиномиальные преобразования и т.п.) [48, 50,51,78, 80, 87-88];

2) распространение идей и методов классического дискретного "комплексного" спектрального анализа на функции, определенные на группах и принимающие значения в алгебрах достаточно общего вида [6, 47,49,53,84, 99-105, 112];

3) разработка новых конкретных алгоритмов, обладающих повышенной точностью и быстродействием, адекватных по структуре вычислений последним разработкам в области специализированных процессоров [2,3,4].

Настоящая работа относится к направлениям 2) и 3) развития теории дискретных ортогональных преобразований, перечисленным выше, и их быстрых алгоритмов. Необходимость рассмотрения дискретных ортогональных преобразований со значениями спектров в алгебрах, более общих, чем двумерная алгебра комплексных чисел (гиперкомплексных алгебрах) определяется в основном уже разработанными и перспективными приложениями таких преобразований к решению широкого круга задач информатики. Так, например:

1. Начиная с работ [131, 132, 136, 141, 142] началось активное применение идей псевдоевклидовой геометрии в теории распознавания образов, а также для моделирования и объяснения структурных свойств гипотетического видимого пространства. В работе В.Г.Лабунца [140] высказано мнение, поддерживающее идею Клейна о том, что геометрия -это изучение тех свойств объектов, которые остаются инвариантными под воздействием специфических групп преобразований. Представление данных в гиперкомплексных алгебрах Клиффорда позволило разработать новые методы распознавания инвариантов изображения в евклидовом и неевклидовом двумерном, трехмерном и n-мерном пространстве. Такие инварианты являются характерными именно для геометрических свойств изображений, в то время как классические "комплексные" спектральные методы ориентированы на анализ, в основном, "усредненных", "энергетических" свойств сигнала и малочувствительны к тонким геометрическим свойствам, которые и являются наиболее информативными.

2. В работах [92, 97, 130, 147] изучается возможность построения нейронных сетей в алгебре Клиффорда. В частности, рассматриваются многослойные перцептроны с описанием в терминах алгебры Клиффорда. С помощью полученных многослойных перцептронов строится аппроксимация комплекснозначной функции.

3. В работе [149] рассматривается приложения гиперкомплексного представления сигнала к сегментации текстур. В качестве практического применения демонстрируется использование кватернионной сегментации Габора для обнаружения дефектов на тканевых материалах. Свойством данного алгоритма является его слабая чувствительность к изменению освещенности и низкая вычислительная сложность.

4. В монографии Я.А. Фурмана [70] предложен способ распространения на кватернионные сигналы понятие авто- и взаимно корреляционных функций, согласованной фильтрации и т.д., что позволило с единых позиций рассматривать обработку как контуров, так и групповых точечных объектов, заданных на плоскости или в трехмерном пространстве.

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

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

F{Щ,т2)= £ ]Г /("1 ,n2)w^,0<mbm2<N-l, (0.1) и1=0п2=0

27IEj 2ле2/ где w}=e /N, w2=e , cl582 ~ образующие элементы некоторой четырехмерной гиперкомплексной алгебры, а также его многомерные обобщения:

00= Z /(v)^(n,v) (0.2) nx,.,nd= 0

2nZj / где ц = (тx,.,md), v = (wl,.,wd), = ' / = {1,.,йГ}, е/

8образующие элементы некоторой 2d-мерной гиперкомплексной алгебры.

Заметим, что классическое многомерное дискретное преобразование Фурье является частным случаем преобразования (0.2) при е{ =. = zd = i. Это позволяет утверждать, что с помощью преобразования (0.2) эффективно решается весь круг задач, цифровой обработки сигналов, для решения которых используется дискретное преобразование Фурье (быстрое вычисление дискретной свертки, фильтрация, компрессия сигналов и т.д.). В задачи диссертационного исследования не входит рассмотрение примеров решения подобных задач с помощью преобразований (0.2). Основной целью работы является разработка эффективной алгоритмической поддержки решения указанных задач с помощью новых преобразований (0.2) со значениями в тех гиперкомплексных алгебрах, для которых быстрые алгоритмы ГПДФ обладают минимальной вычислительной сложностью

Преобразование (0.1) для случая алгебры кватернионов [24, 134, 135] введено впервые в работе [84, 104] как вспомогательное преобразование. В работах [137-142, 149] преобразование применялось для решения прикладных задач, перечисленных выше в пп.1-4.

Следует отметить, что использование в цитированных работах некоммутативной алгебры кватернионов создает определенные вычислительные сложности, связанные именно с фактом некоммутативности алгебры кватернионов. В то же время, в работе [149] отмечено, что принципиальным свойством, определяющим эффективность применения преобразования (0.2), является не конкретная структура гиперкомплексной алгебры, а только существование в ней достаточного количества изоморфных копий комплексной алгебры, определяющих как структуру системы корней так и структуру алгоритмов быстрого вычисления гиперкомплексных спектров F(^i). Кроме того, реализация базовых операций в конечномерных алгебрах существенно зависит как от структуры алгебры, причем не только от ее размерности над основным (вещественным) полем, так и от выбора базиса алгебры, который может варьироваться с целью обеспечения минимальной вычислительной сложности аналогов быстрых алгоритмов "канонического" дискретного преобразования Фурье. Тем не менее, подробных исследований на тему выбора гиперкомплексной алгебры и базиса в ней для оптимальной с точки зрения вычислительной сложности реализации преобразований (0.1) и (0.2) к настоящему времени не проводилось.

Эти факторы и определяют в основном задачи диссертационного исследования.

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

2. Нахождение тривиально реализуемых автоморфизмов этих алгебр и синтез быстрых алгоритмов преобразований (0.1) и (0.2) "совмещенного" типа.

3. Определение базисов найденных алгебр, в которых представление параметров преобразований (0.1) и (0.2) обеспечивает снижение арифметической сложности алгоритмов вычисления преобразований "неканонических" длин (объемов), отличных от степени двойки.

Перечисленные задачи определяют структуру работы и содержание отдельных глав.

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

Заключение диссертации по теме «Теоретические основы информатики», Алиев, Марат Вячеславович

ЗАКЛЮЧЕНИЕ

Перечислим наиболее важные на наш взгляд выводы, следующие из диссертационного исследования.

1. Многомерные дискретные преобразования со значениями в гиперкомплексных алгебрах являются обобщениями многомерных комплексных дискретных преобразований Фурье, и как показано в ряде работ других авторов, позволяют эффективно решать широкий круг прикладных задач цифровой обработки многомерных сигналов.

2. Использование коммутативных алгебр как области значений спектра этих преобразований позволяет существенно снизить сложность быстрых алгоритмов ГПДФ по сравнению с их "некоммутативными" прототипами (кватернионное ГПДФ, клиффордово ГПДФ).

3. В отличие от "некоммутативных" прототипов, быстрые алгоритмы ГПДФ со значениями в КГА имеют невозрастающую мультипликативную сложность как функцию размерности.

4. Для ГПДФ возможен синтез эффективных алгоритмов "нетрадиционных" линейных размеров, отличных от степени двойки, за счет выбора базисных элементов алгебры, согласованного со структурой быстрых алгоритмов.

5. В практически важном для обработки изображений случае двумерного ГПДФ использование КГА вместо алгебры кватернионов позволяет снизить общую вычислительную сложность алгоритмов примерно на 30% при снижении мультипликативной сложности примерно в три раза.

Список литературы диссертационного исследования кандидат физико-математических наук Алиев, Марат Вячеславович, 2004 год

1. Автоморфизмы классических групп. Сб. переводов с англ. и франц.-М.: Мир, 1976.-264 с.

2. Агаян С. С. Оптимальные алгоритмы быстрых ортогональных преобразований и их реализация на ЭВМ //Кибернетика и вычислительная техника.- М.: Наука, 1986.- вып. 2.- с. 231-301.

3. Агаян С.С., Геворкян Д.З. Сложность и параллельные алгоритмы дискретных ортогональных преобразований //Кибернетика и выч. техника. М: Наука, 1988. - Вып 4. - с.124-169.

4. Агаян С.С., Баядан Г.Л., Геворкян Д.З. Вопросы устойчивости суммирования ортогональных рядов и вычисления линейных преобразований //Кибернетика и выч. техника. М: Наука, 1990. - Вып 5. -с.132-168.

5. Айзенберг Н.Н.,Семирот М.С. Цифровая обработка сигналов на конечных группах //Применение ортогональных методов при обработке сигналов и анализе систем.- Свердловск, 1980. Вып. 1. - с.96-105.

6. Алгебра и теория чисел (с приложениями). Избранные доклады семинара Н.Бурбаки. Сб. статей. Перев. с франц. и англ.-М.: Мир, 1987.-271 с.

7. Алиев М.В., Чичева М.А. Дискретные ортогональные преобразования с биэкспоненциальным базисом //Тезисы докладов 2-ой международной конференции молодых ученых и студентов, Часть1, Самара, 2001, с. 18.

8. Алиев М.В., Чернов В.М., Чичева М.А. Дискретные ортогональные преобразования с мультиэкспоненциальным базисом //Тезисы докладов X Всероссийской конференции "Математические методы распознавания образов", Москва, 2001, с. 5-6.

9. Алиев М.В. Синтез алгоритмов двумерного ДПФ в гиперкомплексной алгебре // Труды 6-ой международной конференции "Распознавание образов и анализ изображений: Новые информационные технологии", Великий Новгород, 2002, с. 11-15.

10. Алиев М.В. Быстрые алгоритмы многомерного ДПФ вещественного сигнала спредставлением данных в коммутативно-ассоциативных алгебрах //Компьютерная оптика, № 24, 2002. с. 130-136.

11. Арнольд И.В. Теория чисел: Пособие для ин-тов М.: Учпедгиз Наркомпроса РСФСР, 1939.-286с.

12. Атья М., Макдональд И. Введение в коммутативную алгебру. Перев. с англ.-М.: Факториал Пресс, 2003.-144 с.

13. Ахмед Н., Рао К. Р. Ортогональные преобразования при обработке цифровых сигналов.- М.: Связь, 1980. 248с.

14. Березин Ф.А. Введение в алгебру и анализ с антикоммутирующими переменными. М., Издательство МГУ, 1983.

15. Блейхат Р. Э. Алгебраические поля, обработка сигналов, контроль ошибок //ТИИЭР, 1985. т.73. - №5. - с.30-53.

16. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. М.: Мир, 1987. - 448с.

17. Брейсуэлл Р. Преобразование Хартли. М.: Мир, 1990. - 175с.

18. Бурлаков М.П. Клиффордовы структуры на многообразиях // Итоги науки и техники. Современная математика и ее приложения. М.: ВИНИТИ, 1995. Т. 30: Геометрия 3, с. 205-257.

19. Бухбиндер И.Л. Знакомство с суперматематикой //Соросовский Образовательный Журнал. 1998, № 8, с. 115-120.

20. Бухштаб А.А. Теория чисел -2-е, испр. изд. М.: Просвещение, 1966.-384с.

21. Ван дер Варден Б.Л. Алгебра. М.: Наука, 1976. 648с.

22. Вариченко JI. В., Лабунец В. Г., Раков М. А. Абстрактные алгебраические системы и цифровая обработка сигналов. Киев: Наукова думка, 1986.247c.

23. Власенко В. A., JIanna Ю. М., Ярославский Л. П. Методы синтеза быстрых алгоритмов свертки и спектрального анализа сигналов. М.: Наука, 1990. - 180с.

24. Гельфанд И.М. Лекции по линейной алгебре 5-е, испр. изд. - М.: Добросвет, 1998.-319с.

25. Гельфонд А.О. Исчисление конечных разностей. М: Наука, 1967. - 375с.

26. Гречишников А. И. Модифицированные алгоритмы БПФ с уменьшенным числом операций умножения //Радиотехника и электроника, 1983. т.28. -№1. - с.195-197.

27. Григорян A.M. Алгоритм вычисления двумерного дискретного преобразования Фурье с произвольными порядками //Журнал выч. матем. иматем. физ., 1991. т.31. - №10. - с.1576-1581.

28. Гроссман И., Магнус В. Группы и их графы. М.: Мир, 1971.

29. Дагман Э.Е., Кухарев Г.А. Быстрые дискретные ортогональные преобразования. Новосибирск: Наука, 1983. 232с.

30. Дэвенпорт Высшая арифметика. М., Наука, 1965. 176 с.

31. Задирака В.К. Теория вычисления преобразования Фурье. Киев: Наукова думка, 1983.

32. Залманзон Л. А. Преобразования Фурье, Уолша, Хаара и их применения в управлении, связи и других областях. М.: Наука, 1989. - 494с.

33. Зарисский О., Самюэль П. Коммутативная алгебра, т.1. Перев. с англ. М.: ИЛ, 1963.-373 с.

34. Иваненко В.Г. Рекуррентное вычисление дискретного преобразования Фурье. М.: МИФИ, 1987. Препр.014-87. - 16с.

35. Ивлев Д.Д. О двойных числах и их функциях // Математическое просвещение. М.: Изд-во физ.-мат. лит., 1961. Вып. 6, с. 197-203.

36. Ильин В.А., Позняк Э.Г. Линейная алгебра: Учеб. Для ВУЗов 4-ое изд. -М: Физматлит, 1999 - 296 с.

37. Кантор И.Л., Солодовников А.С. Гиперкомплексные числа. М.: Наука, 1973. 144 с.

38. Кецарис А. А. Основания математической физики. М.: Ассоциация независимых издателей, 1997.-280 с.

39. Капорин И. Е. Новый алгоритм быстрого преобразования Фурье.

40. Журнал вычислительной математики и математической физики, т. 20, № 4, 1980.-с. 1054-1058.

41. Кострикин А. И. Введение в алгебру. Основы алгебры. М.: Наука, 1994. -318 с.

42. Крот A.M., Минервина Е.Б. Синтез алгоритмов дискретного преобразования Фурье для действительных последовательностей на основе полиномиальной алгебры //РЭ, 1987. -т.22. №6. - с.1217-1229.

43. Крот A.M. Дискретные модели динамических систем на основе полиномиальной алгебры. Минск: Навука i тэхшка, 1990. - 311 с.

44. Кухарев Г. А., Шмерко В. П., Зайцева Е. Н. Алгоритмы и систолические процессоры для обработки многозначных данных. Минск: Навука i тэхшка, 1990. - 296 с.

45. Лабунец В.Г. Обобщенные и быстрые преобразования Фурье на произвольной конечной абелевой группе //Гармонический анализ на группах в абстрактной теории систем. Свердловск, 1976. - с.24-43.

46. Лабунец В. Г. Единый подход к алгоритмам быстрых преобразований //Применение ортогональных методов при обработке сигналов и анализе систем. Свердловск: УПИ, 1980. - с.4-14.

47. Лабунец В. Г. Теоретико-числовые преобразования над полями алгебраических чисел //Применение ортогональных методов при обработке сигналов и анализе систем. Свердловск: УПИ, 1981. - с.44-54.

48. Лабунец В. Г. Фурье-подобные преобразования //Применение ортогональных методов при обработке сигналов и анализе систем. -Свердловск: УПИ, 1981. с.4-14.

49. Лабунец В.Г. Колмогоров Г.С. Стратегии настройки многопараметрических преобразований //Применение ортогональных методов при обработке сигналов и анализе систем. Свердловск: УПИ, 1983. - с.4-26.

50. Лабунец В. Г. Алгебраическая теория сигналов и систем: Цифровая обработка сигналов. Красноярск: Изд-во Красноярск, ун - та, 1984. - 244 с.

51. Лабунец В. Г. Функции с двойной ортогональностью в обобщенном гармоническом анализе //Цифровые методы в управлении, радиолокации и связи. Свердловск: УПИ, 1986. - с.4-15.

52. Лабунец В. Г. Алгебраическая теория сигналов и систем. Свердловск: Изд-во УрГУ, 1989. - 196с.

53. Ланкастер П. Теория матриц. М.: Наука, 1978. 280 с.

54. Ленг С. Алгебра. М.: Мир, 1965. 564с.

55. Маккеллан Дж. X., Рейдер Ч. М. Применение теории чисел в цифровой обработке сигналов. М.:Радио и связь, 1983. - 263с.

56. Математическая энциклопедия, М., «Советская энциклопедия», 1979, т.2.

57. Мельников О. В., Ремесленников В. Н., Романьков В. А. и др. Общая алгебра. /Под ред. Скорнякова И. А., т. 1. М.:Наука, 1990. - 592с.

58. Нуссбаумер Г. Быстрое преобразование Фурье и алгоритмы вычисления сверток. М.: Радио и связь, 1985. - 248с.

59. ПершинаМ. В., ЧичеваМ. А. Декомпозиция двумерного ДПФ с представлением данных в алгебре кватернионов. //Компьютерная оптика, № 14-15, Часть 2, 1995. с. 13-21.

60. Понтрягин Л.С. Обобщения чисел. М.: Наука, 1986. 120 с.

61. Сергеев В.В., Усачев А.В. Новый алгоритм быстрого преобразования Хартли //Компьютерная оптика, 1990. Вып. 7. - с.66-67.

62. Сильвестров В.В. Системы чисел //Соросовский Образовательный Журнал. 1998, № 8, с. 121-127.

63. Судаков Ю.А. Алгоритм быстрого преобразования Фурье с минимальным числом умножений //Радиотехника и электроника, 1990. т.35. - №6. -с. 1260-1266.

64. Судаков Ю.А. Формы минимального алгоритма быстрого преобразования Фурье //Радиотехника и электроника, 1992. т.37. - №1. - с.117-125.

65. Трахтман A.M., Трахтман В.А. Основы теории сигналов на конечных интервалах. М.: Советское радио, 1975. - 207 с.

66. Фаддеев Д.К. Лекции по алгебре. М.: Наука, 1984.

67. Фурман Я.А., Кревецкий А.В., Передреев А.К. Введение в контурный анализ; приложения к обработке изображений и сигналов. Под ред. Фурмана А.Я. М.: ФИЗМАТЛИТ, 2002. - 592 с.

68. Чернов В.М. Двумерные дискретные ортогональные преобразования с рекуррентным базисом //Научное приборостроение, 1993. т.З. - №1.с.110-115.

69. Чернов В.М. Реализация теоретико-числовых преобразований в кодах, порожденных избыточными системами счисления //Электронное моделирование, 1993. т.15. - №4. - с.33-37.

70. Чернов В.М. Алгоритмы дискретного преобразования Фурье с представлением данных в полях алгебраических чисел //Автоматика и выч. техника, 1994. №4. -с.64-69.

71. Чернов В.М. Алгоритмы дискретных ортогональных преобразований, реализуемые в кодах Гамильтона Эйзенштейна //Проблемы передачи информации, 1995. - т.31. - №3. - с.38-46.

72. Чернов В.М. Новый алгоритм дискретного преобразования Фурье по основанию пять //Компьютерная оптика, 1995. №14-15. - ч.2. - с.4-12.

73. Чернов В.М. О сложности алгоритмов дискретных ортогональных преобразований в расщепленной арифметике //Тезисы докладов 7-ой Всесоюзной конференции "Математические методы распознавания образов (ММРО-7)". Звенигород, 1995, - с.61.

74. Чернов В.М. Об иерархии групповых алгебр, связанной с параметризацией быстрых алгоритмов дискретных ортогональных преобразований //Доклады Академии наук, 1997. т.357. - №3. - с.317-319.

75. Чернов В.М., Першина М.В. Реализация дискретных преобразований с представлением данных в избыточных системах счисления //Методы и средства обработки сложной графической информации: Тезисы докладов

76. Всесоюзной конференции. Нижний Новгород: Нижегородский госуниверситет, 1991. - с.82.

77. Чернов В.М., Чернов А.В. О классах преобразований изображений, представимых вращениями в алгебре Клиффорда // Тезисы докладов 8-ой Всесоюзной конференции "Математические методы распознавания образов (ММРО-8)". -М., 1997. с.119.

78. Чернов В.М., Чернов А.В. О классах преобразований изображений, представимых вращениями в алгебре Клиффорда. Доклады Академии наук, т.357, N 3, 1997, с.119.

79. Чернов В.М., Чичева М.А. Алгебро-арифметические методы синтеза быстрых алгоритмов дискретных ортогональных преобразований. В книге "Методы компьютерной обработки изображений" (под ред.В.А.Сойфера), М.:Наука., 2001, с. 301-384.

80. Ярославский JI. П. Введение в цифровую обработку изображений. М.: Советское радио, 1979. - 312с.

81. Ярославский JI. П. Цифровая обработка сигналов в оптике и голографии: введение в цифровую оптику.- М.: Радио и связь, 1987. 297с.

82. Agayan S.S., Grigoriyan A.M. Discrete unitary transfer- mations and their relation to covering of fundamental periods (Part 1) //Pattern Recogn. and Image Analysis, 1993. V.4. - № 1. - pp. 16-23.

83. Agayan S.S., Grigoriyan A.M. Discrete unitary transfor- mations and their relation to covering of fundamental periods (Part 11) //Pattern Recogn. and Image Analysis, 1993. V.4. - №1. - pp.24-31.

84. Aliev M.V., Chernov V.M. Two-dimensional FFT-like algorithms with overlapping //Optical Memory and Neural Networks (Information Optics), v.ll, no. 1,2002 p.29-38.

85. Aliev M. V. Synthesis of Two-Dimensional DFT Algorithms in the Hypercomplex Algebra //Pattern Recognition and Image Analysis, Vol. 13, No. 1,2003 p. 61-63.

86. Allenby, R.B.J.T., Rings, Fields and Groups: An Introduction to Abstract Algebra, 2nd edition, 1991.

87. Arena P., Fortuna L., Re R., and Xibilia M.G. Multilayer perceptrones to approximate comlex valued functions. Neural Systems, 6:435-446, 1995.

88. Bouguezal S., Chikouche D., Khellaf A. An Efficient Algorithm for the Computation of the Multidimensional Discrete Fourier Transform //Multidimensional Systems and Signal Processing, pp. 275-304, 10 (3) July1999.

89. Boyer, Carl В. , revised by Merzbach, Uta C., A History of Mathematics, 2nd edition, 1991.

90. Briggs W.L., Van Henson E. The DFT: An owner's manual for the discrete Fourier transform. -SIAM, 1995. 434p.

91. Brigham E.O. The Fast Fourier Transform and its Applications //Prentice Hall, Englewood Cliffs, NJ, 1988.

92. Buchholz S. Algebraische Einbettungen Neuronaler Netze. Master's thesis, Cognitive Systems Group, Inst, of Сотр. Sci., Univ. of Kiel, Germany, 1997.

93. Buchholz S. In G. Sommer, editor, Geometric Computing with Clifford Algebra. Springer-Verlag, Heidelberg, pp. 187-207, 2001.

94. Buelow T. Global and Local Hypercomplex Spectral Signal Representations for Image Processing and Analysis. PhD thesis, Christian-Albrechts-University of Kiel, 1999.

95. Buelow Т., Sommer G. Algebraically extended representations of multidimensional signals //Proc. SCIA'97. Lappeenranta, Finland, 1997. - pp.559566.

96. Buelow Г., Sommer G. Das Konzepi einer zweidimensionale Phase unter Vervendung einer algebraisch erweiteren Signalrepresentation //19. DAGM Simposium Muster- erkennung.-Braunschweig, 1997. S.351-358.

97. Buelow Т., Sommer G. Multi-dimensional signal processing using an algebraically extended signal representation //Proc. AFPAC'97. Kiel, Germany, 1997. - Springer, - LNCS 1315. - pp.148-163.

98. Buelow Т., Felsberg M., Sommer G. Non-commutative hypercomplex Fourier transforms of multidimensional signals. In G. Sommer, editor, Geometric Computing with Clifford Algebra. Springer-Verlag, Heidelberg, pp. 187-207, 2001.

99. Chernov V.M. Non-Archimedian Normalized Fields and Algorithms for Two-Dimensional Discrete Fourier Transform // Pattern Recogn. and Image Analysis, 1991. V.l. - №4. - pp.426-429.

100. Chernov V.M. Fast algorithms of discrete orthogonal transforms for data represented in cyclotomic fields //Pattern Recogn. and Image Analysis, 1993. -V.3. -pp.455-458.

101. Chernov V.M. A metric unified treatment of two- -dimensional FFT //Proc.of ICPR'96.-Vienna, 1996. V.2. - Track B. - pp.662-669.

102. Chernov V.M. Algorithms, relalizable in Hamilton-Eisenstein codes, for two-dimensional discrete orthogonal transforms. Problem Inform. Transmission, No. 3., pp. 228-235, 1996.

103. Chernov V.M. Chess algorithms of the two-dimensional discrete Fourier transform //Pattern Recogn. and Image Analysis, 1996. V.6.- №1. - p. 189.

104. Chernov V.M. Vector-radix FFT with splitting the radix of fractional order //Proc. of the 10th Scandinavian Conference on Image Analysis (SCIA'97). -Lappeenranta, Finland, 1997. V.2. -pp.551-558.

105. O.Chernov V.M., Bayro-Corrochano E. Clifford models of image transforms. //Pattern Recognition and Image Analysis. V.8, N 2, pp. 272-273, 1998.

106. Chernov V., Buelow Т., Felsberg M. Synthesis of fast algorithms for discrete Fourier-Clifford transform //Pattern Recognition and Image Analysis, V.8, N 2, pp. 274-275, 1998.

107. Chernov V.M. Clifford algebras are group algebras projections. In: E.Bayro-Corrochano, G.Sobczyk (Eds) Advanches in Geometric Algebra with Applications in Science and Engineering.-Birkhauser, Boston, pp. 467-482, 2001.

108. Chernov V.M. Discrete Stockes theorem and multidimensional DFTs //The 4-th Open Russian-German Workshop "Pattern Recogn. and Image Analysis". -Extended abstract. pp.40-44.

109. Chichyeva M.A. Algorithms of discrete cosine transform with data representation in Eisenstein's codes //Image Proc. and Commun., 1996. V.2. -№4. - pp.53-60.

110. Chichyeva M A., Pershina M. V. On various schemes of 2D-DFT decomposition with data representation in the quaternion algebra. //Image Processing and Com^iuriWtiori^ Institute of TelecornmnmVations Bydgoszcz, Poland, Vol. 2, No. 1, pp. 13-20 , 1996.

111. Chichyeva M. A. Synthesis of fast algorithms of two-dimensional discrete cosine transforms based on quaternion algebra. //Pattern Recognition and Image Analysis, Vol. 8, No. 2, pp. 280-282, 1998.

112. Cizek V. Discrete Fourier transforms and their applications. -A.Hilger Publ., 1986.- 14 lp.

113. Clifford W. Preliminary Scetch of Biquaternions. Proc. of London Math. Soc., Vol IV, pp. 381-393, 1873.

114. Cooley J.W., Tukey J.W. An Algorithm for the Machine Computation of Complex Fourier Series //Math. Сотр., 1965. №19. - p. 297-301.

115. Dubois E., Venetsanopoulos A.N. A new algorithm for the radix3 FFT //IEEE Trans., 1978. -ASSP-26. №3, - pp.222-225.

116. Dubois E., Venetsanopoulos A.N. The generalized discrete Fourier transform in ring of algebraic integers //IEEE Trans., 1980. ASSP-28. - №2. - pp. 169-175.

117. Duhamel L., Hollman H. Split-radix FFT algorithm //Electron Lett., 1984. -V.20. №17 - p. 14-16.

118. Duhamel P. Implementation of split-radix FFT algorithm for complex, real, and real-symmetric data //IEEE Trans., 1984. ASSP-34. - V.34. - №2. - pp.285295.

119. Duhamel P., Vetterli M. Fast Fourier Transforms: A Tutorial review and a state of theart //Signal Processing, Vol. 19, No. 4, pp. 259-299, April 1990.

120. Ell T.A. Quaternion-Fourier transform for analysis of 2-dimensional linear time-invariant partial- differential systems //Proc. of the 32th IEEE Conf. on Decision and Control, 1993. V.l-4. -pp. 1830-1841.

121. Felsberg M., Buelow Т., Sommer G., Chernov V.M. Fast Algorithms of Hypercomplex Fourier Transforms. In: G.Sommer (Eds) Geometric Computing with Clifford Algebras. Springer-Verlag, pp. 231-254, 2000.

122. Felsberg M., Sommer G. Fast algorithms for the hypercomplex Fourier transforms //In 2nd International Workshop on Transforms and Filters Banks, Brandenburg an der Havel, pp. 295-302, 2000.

123. Felsberg ML, Buelow Т., Sommer G. Commutative hypercomplex Fourier transforms of multidimensional signals. In G. Sommer, editor, Geometric Computing with Clifford Algebra. Springer-Verlag, Heidelberg, pp. 209-229, 2001.

124. Felsberg M., Sommer G. The structure multivector. In L. Dorst, C. Doran and J. Lasenby, editors, Applications of Geometric Algebra in Computer Science and Engineering, pp. 437-446. Proc. AGACSE 2001, Cambridge, UK, Birkhauser Boston, 2002.

125. Georgiou G. and Koutsougeras C. Complex domain backpropagation. IEEE Trans. Circ. And Syst. II, 39:330 334, 1990.

126. Gibson J.J. Optical motions and transformations as stimuli for visual perception. Psych. Rev., 64(5):288 295, 1957.

127. Gibson J.J. The Ecological Approach to Visual Perception. Houghton Mifflin Company, 1979.

128. Good I.J. The interaction algorithm and practical Fourier analysis //J.Royal Stat. Soc., 1958. V.B-20. - pp.361-372.

129. Grassmann H. Der Opt der Hamilton4 schen Quatemionen in der Ausdehnungslehre. Mathematische Annalen, 12:357, 1877.

130. Hamilton W.R. Lectures on Quaternions. Dublin, 1853.

131. Kienle G. Experiments concerning the non-Euclidian structure of the visual space. Bioastronautics., 4:386 400, 1964.

132. Kosheleva O., Cabrera S.D., Gibson G.A., Koshelev M. Fast implementations of fuzzy arithmetic operations using fast Fourier transform (FFT) //Fuzzy Sets and Systems, No. 2, pp. 269-277, 1997.

133. Labunets E.V. Group-Theoretical Methods in Image Recognition. Technical report, LiTH-ISY-R-1855. Linkoping University, 1996.

134. Labunets E.V. Labunets V.G., and Greutzburg R. Fast factorial trigonometrical transform. In Second Workshop on Transforms and Filterbanks, Brandenburg, 1999.

135. Labunets E.V. Labunets V.G., Egiazarian K., and Astola J. Hypercomplex moments application in invariant image recognition. In Int. Conf. On Image Processing 98, pages 256-261, 1998.

136. Luneburg R.K. Metric methods in binocular visual perception. Studies and Essays. Courant Anniv., 1:215 239,1948.

137. Luneburg R.K. The metric methods in binocular visual space. J. Opt. Soc. Amer., 40(10):627 642, 1950.

138. Lasenby, A.N., Doran, C.J.L. and Gull, S.F. (1996). Lectures in Geometric Algebra, In: W. E. Baylis, Ed., Cliord (Geometric) Algebras with Applications to Physics, Mathematics and Engineering, Birkhouser, Boston, 256 p.

139. Lee Y.-Y., Lo P.-C. Real-time implementation of the split-radix FFT An algorithm to efficiently construct local butterfly modules //Signal Processing, Vol. 71, No. 3, pp. 291-299, 1998.

140. Liu G., Wang Q., Liu S.B. A three-dimensional thermomechanical asperity contact model for two nominally flat surfaces in contact, to appear in ASME Journal of Tribology, Vol. 123, pp. 595-602, 2001.

141. Lo P.-C., Lee Y.-Y. Real-time implementation of the moving FFT algorithm //Signal Processing, Vol. 79, No. 3, pp. 251-259,1999.

142. Pearson J.K. Clifford Networks. PhD thesis, Univ. of Kent, 1994.

143. Sipp F., Wade W.R., Simon P. Walsh series: An introduction to the dyadic harmonic analysis. A. Hilger Publ., 1990. - 528p.

144. Sorensen H. V., Heideman M. Т., Burrus C. S. On computing the split-radix FFT//IEEE Trans., 1986. ASSP-34. - №1. - p. 152-156.

145. Thomas L. H. Using a Comhuter to Solve Problems in Physics, in Applications and of Digital Computer //Ginn and Co. Boston, Mass. - 1963.

146. Van Loan C. Computational frameworks for the fast Fourier transform. -SI AM, 1992. 273p.

147. Wang Z. Fast algorithms for the discrete W transform and for the discrete Fourier transform /ЯЕЕЕ Trans., 1984. ASSP-32. - №4. - p.803-816.

148. Winograd S. On Computing the Discrete Fourier Transform //Proc. Nat. Acad. Sci. USA, 1976. V.73. - p.1005-1006.

149. Winograd S. On the Discrete Fourier Transform //Math. Сотр., 1978. №32. -pp. 175-199.

150. Winograd S. Arithmetic complexity of computations. SLAM, 1980. - 93p.

151. Yamamoto S. Effective implementations of multi-dimensional radix-2 FFT //Computer Physics Communications, Vol. 125 ,pp. 1-7, 2000.