Рассмотрены
как классические БА ДОП, так и оригинальные авторские методы, существенно снижающие
вычислительную сложность алгоритмов. <...> Приведены различные алгоритмы одно- и
двумерного дискретного преобразования Фурье, дискретного косинусного преобразования,
синтезированные в рамках единого алгебраического подхода. <...> 3
ОГЛАВЛЕНИЕ
1 Предварительные сведения
5
1.1 О проблеме синтеза быстрых алгоритмов дискретных ортогональных
преобразований
5
1.2 Конечномерные ассоциативные алгебры
9
1.3 Основные схемы редукции
10
1.3.1 Декомпозиция Кули-Тьюки "по основанию 2"
10
1.3.2 Декомпозиция Кули-Тьюки "по основанию 4"
11
1.3.3 Декомпозиция Кули-Тьюки с расгцеплением основания (снлит-радикс
алгоритм)
12
1.3.4 Декомпозиция ДПФ Гуда-Томаса
13
2 Совмегценные алгоритмы дискретных ортогональных преобразований
15
2.1 Двумерный БА ДПФ с совмегцением в алгебре кватернионов
16
2.2 БПФ с представлением данных в алгебре (2х2)-матриц
18
2.3 Кватернионное двумерное ДПФ
20
2.3.1 Алгоритм К ДПФ с декомпозицией по основанию 2
21
2.3.2 Алгоритм К ДПФ с декомпозицией по основанию 4
23
2.3.3 Алгоритм К ДПФ с расщеплением основания
25
2.4 Совмегценные алгоритмы дискретного косинусного преобразования
28
2.4.1 Алгоритм одномерного ДКП четной длины
29
2.4.2 Алгоритм двумерного ДКП четной длины
32
3 Быстрые алгоритмы ДОП при специальном представлении данных
3.1 Представление данных в круговых кодах
3.1. <...> 1 Декомпозиция Кули-Тьюки "по основанию р"
3.2 Алгоритмы одномерного ДПФ при длине преобразования 7V=3^
3.3 Алгоритмы дискретного косинусного преобразования длиной Л^З^
39
39
39
40
42
3.4 Алгоритмы дискретных ортогональных преобразований, реализуемые в
кодах Гамильтона-Эйзенштейна
44
3.4.1 Быстрый алгоритм двумерного ДПФ
47
3.4.2 Быстрый алгоритм дискретного косинусного преобразования
49
3.5 Алгоритмы дискретного косинусного преобразования коротких длин
3.5.1 Алгебраические принципы синтеза БА ДКП коротких длин
53
53
4
3.5.2 Алгоритм дискретного косинусного нреобразования длиной N = 8
56
3.5.3 Алгоритм <...>
Алгебро-арифметические_методы_синтеза_быстрых_алгоритмов_дискретных_ортогональных_преобразований_[Электронный_ресурс]_.pdf
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВБ1СШЕГ0 НРОФЕССИОНАЛБНОГО ОБРАЗОВАНИЯ
«САМАРСКИЙ Г0СУДАРСТВЕННБ1Й АЭРОКОСМИЧЕСКИЙ
УНИВЕРСИТЕТ имени академика С.Н.КОРОЛЕВА
(НАЦИ0НАЛБНБ1Й ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ)»
В.М. Чернов, М.А. Чичева
Алгебро-арифметические методы синтеза
быстрых алгоритмов
дискретных ортогональных преобразований
Электронное учебное пособие
САМАРА
2010
Стр.1
2
Авторы:
ЧЕРНОВ Владимир Михайлович,
ЧИЧЕВА Марина Алексаидролвиа,
Учебное пособие содержит описание алгебро-арифметических методов синтеза
быстрых алгоритмов дискретных ортогональных преобразований (БА ДОП). Рассмотрены
как классические БА ДОП, так и оригинальные авторские методы, существенно снижающие
вычислительную сложность алгоритмов. Приведены различные алгоритмы одно- и
двумерного дискретного преобразования Фурье, дискретного косинусного преобразования,
синтезированные в рамках единого алгебраического подхода. Также дано практическое
применение части описанных алгоритмов.
Пособие предназначено для магистров по направлению 010400.68 "Прикладная
математика и информатика", обучающихся по программе «Математические и компьютерные
методы обработки изображений и геоинформатики».
Стр.2
3
ОГЛАВЛЕНИЕ
1 Предварительные сведения
1.1 О проблеме синтеза быстрых алгоритмов дискретных ортогональных
преобразований
1.2 Конечномерные ассоциативные алгебры
1.3 Основные схемы редукции
1.3.1 Декомпозиция Кули-Тьюки "по основанию 2"
1.3.2 Декомпозиция Кули-Тьюки "по основанию 4"
5
5
9
10
10
11
1.3.3 Декомпозиция Кули-Тьюки с расгцеплением основания (снлит-радикс
алгоритм)
12
1.3.4 Декомпозиция ДПФ Гуда-Томаса
2 Совмегценные алгоритмы дискретных ортогональных преобразований
2.1 Двумерный БА ДПФ с совмегцением в алгебре кватернионов
2.2 БПФ с представлением данных в алгебре (2х2)-матриц
2.3 Кватернионное двумерное ДПФ
2.3.1 Алгоритм К ДПФ с декомпозицией по основанию 2
2.3.2 Алгоритм К ДПФ с декомпозицией по основанию 4
2.3.3 Алгоритм К ДПФ с расщеплением основания
2.4 Совмегценные алгоритмы дискретного косинусного преобразования
2.4.1 Алгоритм одномерного ДКП четной длины
2.4.2 Алгоритм двумерного ДКП четной длины
3 Быстрые алгоритмы ДОП при специальном представлении данных
3.1 Представление данных в круговых кодах
3.1.1 Декомпозиция Кули-Тьюки "по основанию р"
3.2 Алгоритмы одномерного ДПФ при длине преобразования 7V=3^
3.3 Алгоритмы дискретного косинусного преобразования длиной Л^З^
3.4 Алгоритмы дискретных ортогональных преобразований, реализуемые в
кодах Гамильтона-Эйзенштейна
3.4.1 Быстрый алгоритм двумерного ДПФ
3.4.2 Быстрый алгоритм дискретного косинусного преобразования
3.5 Алгоритмы дискретного косинусного преобразования коротких длин
3.5.1 Алгебраические принципы синтеза БА ДКП коротких длин
13
15
16
18
20
21
23
25
28
29
32
39
39
39
40
42
44
47
49
53
53
Стр.3