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

• Автор: Алиев, Марат Вячеславович
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Самара
• Количество страниц: 129 с. : ил.

ВВЕДЕНИЕ.
ГЛАВА 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.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. Выводы и результаты главы
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. Сравнительный анализ вычислительной сложности алгоритмов двумерного ГДГ1Ф.
3.2. Алгоритм двумерного ГДПФ вещественного сигнала с декомпозицией по основанию три
3.3. Алгоритмы многомерного ГДПФ в алгебре
3.3.1. Совмещенные алгоритмы многомерного ГДПФ вещественного сигнала.
3.3.1. Алгоритм многомерного ГДПФ гиперкомплексного сигнал с декомпозицией по основанию два
3.3.2. Алгоритм многомерного ГДПФ гиперкомплексного сигнал с декомпозицией по основанию четыре.
3.3.3. Алгоритм многомерного ГДПФ гиперкомплексного сигнала с векторным расщеплением.
3.4. Алгоритм многомерного ГДПФ вещественного сигнала по основанию три.
3.5. Сравнительный анализ вычислительной сложности алгоритмов
3.6 Результаты и выводы главы
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ


Значительный вклад в развитие общей теории дискретных преобразований и их быстрых алгоритмов внесли С. С. Агаян, Айзенберг, В. А. Власенко, В. Г. Лабунец, А. М. Крот, А. М. Трахтман, В. М. Чернов, Л. П. Ярославский, Р. Агарвал, Ш. Виноград, Г. Нуссбаумер, Ч. Рейдер и др. Высокоэффективные алгоритмы конкретных преобразований, адаптированные к характеристикам применяемых вычислительных средств разработаны И. Е. Капориным, Е. Е. Тыртышниковым, А. М. Григоряном и другими исследователями ,, , , , , , 0, , 0, . Настоящая работа относится к направлениям 2 и 3 развития теории дискретных ортогональных преобразований, перечисленным выше, и их быстрых алгоритмов. Необходимость рассмотрения дискретных ортогональных преобразований со значениями спектров в алгебрах, более общих, чем двумерная алгебра комплексных чисел гиперкомплексных алгебрах определяется в основном уже разработанными и перспективными приложениями таких преобразований к решению широкого круга задач информатики. Начиная с работ 1, 2, 6, 1, 2 началось активное применение идей псевдоевклидовой геометрии в теории распознавания образов, а также для моделирования и объяснения структурных свойств гипотетического видимого пространства. В работе В. Г.Лабунца 0 высказано мнение, поддерживающее идею Клейна о том, что геометрия это изучение тех свойств объектов, которые остаются инвариантными под воздействием специфических групп преобразований. Такие инварианты являются характерными именно для геометрических свойств изображений, в то время как классические комплексные спектральные методы ориентированы на анализ, в основном, усредненных, энергетических свойств сигнала и малочувствительны к тонким геометрическим свойствам, которые и являются наиболее информативными. В работах , , 0, 7 изучается возможность построения нейронных сетей в алгебре Клиффорда. В частности, рассматриваются многослойные перцептроны с описанием в терминах алгебры Клиффорда. С помощью полученных многослойных перцептронов строится аппроксимация комплекснозначной функции. В работе 9 рассматривается приложения гиперкомплексного представления сигнала к сегментации текстур. В качестве практического применения демонстрируется использование кватернионной сегментации Габора для обнаружения дефектов на тканевых материалах. Свойством данного алгоритма является его слабая чувствительность к изменению освещенности и низкая вычислительная сложность. В монографии Я. А. Фурмана предложен способ распространения на кватернионные сигналы понятие авто и взаимно корреляционных функций, согласованной фильтрации и т. Ртх,т2 X X нГ,,г2Л2,0тт2Л1, 0. I ц. Псо,,о в лг, 1,. Заметим, что классическое многомерное дискретное преобразование Фурье является частным случаем преобразования 0. Это позволяет утверждать, что с помощью преобразования 0. Фурье быстрое вычисление дискретной свертки, фильтрация, компрессия сигналов и т. В задачи диссертационного исследования не входит рассмотрение примеров решения подобных задач с помощью преобразований 0. Основной целью работы является разработка эффективной алгоритмической поддержки решения указанных задач с помощью новых преобразований 0. Преобразование 0. В работах , 9 преобразование применялось для решения прикладных задач, перечисленных выше в пп. Следует отметить, что использование в цитированных работах некоммутативной алгебры кватернионов создает определенные вычислительные сложности, связанные именно с фактом некоммутативности алгебры кватернионов. В то же время, в работе 9 отмечено, что принципиальным свойством, определяющим эффективность применения преобразования 0. Фурье. Тем не менее, подробных исследований на тему выбора гиперкомплексной алгебры и базиса в ней для оптимальной с точки зрения вычислительной сложности реализации преобразований 0. Эти факторы и определяют в основном задачи диссертационного исследования. Задачи диссертационной работы. Определение структуры гиперкомплексных алгебр, в которых алгебраические операции реализуются посредством минимального числа вещественных операций.