Главная > Быстрые алгоритмы в цифровой обработке изображений
НАПИШУ ВСЁ ЧТО ЗАДАЛИ
СЕКРЕТНЫЙ БОТ В ТЕЛЕГЕ
<< Предыдущий параграф Следующий параграф >>
Пред.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
След.
Макеты страниц

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

Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике

ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO

4.5. Базовые алгоритмы ДПФ для N = 4, 9

Из (4.2) можно увидеть, что при использовании схем, полученных в последнем разделе, наивысигий реализуемый порядок . Учитывая это, добавим тривиальный алгоритм для (рис. 4.9), увеличив таким образом максимальное значение до 210.

Если бы мы захотели получить еще большие нам нужно было бы или построить новые схемы для следующих по порядку простых чисел ( или придумать новые схемы для — простое). Выберем последнее.

Рис. 4.9. Алгоритм ДПФ порядка 2

4.5.1. ДПФ порядка 4

, т. е. в соответствии с (4.12)

Примитивный корень из 4 равен 3. Отсюда

Число строк, исключаемых из ЛЦ-таблицы, равно 2. Оно значительно увеличивается в последующих таблицах, достигая 8 при Это обстоятельство требует новой и слегка модифицированной терминологии для облегчения работы с частью матрицы, не являющейся левым циркулянтом.

Во-первых, расширим определение так, чтобы (4.15) включало теперь (4.16):

Подобным образом для индексов столбца о. теперь имеем

В этом и в следующем разделах будем придерживаться такого расширенного определения без явного упоминания об этом.

Дополним теперь (4.19) — (4.21):

И, наконец, зная, что элемент матрицы ДПФ (4.9) — это , введем «экспоненциальную-» матрицу Е:

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

Рис. 4.10. Алгоритм ДПФ порядка 4

В данном случае

Здесь добавлены оба типа индексов строки и столбца. Проще всего получить Е непосредственно из определения (4.99). Выписывая эту матрицу, нужно следить за тем, чтобы незаключенные в скобки индексы а следовали в порядке Этим матрице придается ЛЦ-структура. Последовательность других индексов безразлична.

Видно, что (4.100), как и следовало ожидать, представляет ЛЦ-подматрицу второго порядка. Используем действие этой подматрицы вместе со схемой на рис. 4.1, начиная с вычисления

Следовательно (см. рис. 4.1),

Отсюда следует, что только строка (За лает вклад в формирование Перепишем ее в строку (53 на рис. 4.10. Выходной вектор (см. рис. 4.10) оказывается неупорядоченным по своим составляющим. В разд. 4.9 будут показаны преимущества некоторых схемных структур, которые обеспечивают экономию объема памяти при реализации алгоритма. Схемы, построенные до этого, имеют и такого рода структуру, и упорядоченную индексацию выходного вектора Начиная с этого момента, по-видимому, уже невозможно иметь оба желаемых свойства одновременно. Мы выбрали структуру, экономящую объем памяти, что представляется более важным, поэтому имеем неупорядоченный выходной вектор. В данном случае закон перемешивания индексов достаточно прост, но при он становится сложным. Для облегчения выкладок введем дополнительный вектор в формируемые схемы. Неупоря дочеиный вектор идентичен упорядоченному 1] (см. рис. 4.10).

Теперь вернемся к реализации оставшейся части матрицы Е (4.100)

Здесь использован тот факт, что Равенства, подобные (4.100), могут быть выведены непосредственно из матрицы Е.

Такие равенства будут даваться в дальнейшем без каких-либо комментариев:

Этим завершается вывод.

4.5.2. ДПФ порядка 9

Следовательно, из (4.12) имеем

Примитивным корнем из 9 является примитивный корень из 3, а именно 2. Это приводит к

Отсюда матрица Е имеет вид

Поскольку здесь применима схема рис. 4.4. Рассмотрим сначала Матрица Е (4.106) отображает последовательность а; [это согласуется также с (4.76)]. Тогда

Рис. 4.11. Вычисление для алгоритма ДПФ порядка 9 (см. скан)

Вычисление - показано на рис. 4.11. Заметим, что в терминологии рис. 4.4, 4.11

Это означает, что в реализации которая выполняется копированием рис. 4.4, 4.11 в рис. 4.13, члены, связанные с , должны быть отброшены. При копировании этих рисунков используем некоторые перестановки, кроме очевидных перестановок входных и выходных переменных. Эти перестановки расшифрованы на рис. 4.12. Заметим, что перестановка показана за два последовательных шага: (Например,

Обратимся к учету оставшейся части матрицы, используя в качестве руководства (4.106). При этом нам встретятся следующие константы:

Рис. 4.12. Перестановка индексов для формирования рис. 4.13

которые будут применяться в дальнейшем.

Воздержимся пока от дальнейшей разработки этого случая перейдем к следующей группе. .

Этот случай по сравнению с предыдущим требует замены на . Отсюда . С этих позиций обе группа можно реализовать так, как показано на рис. 4.13.

Теперь реализуем Из (4.106)

(кликните для просмотра скана)

Обратимся теперь к . Единственное отличие здесь состоит в замене на . Отсюда

Наконец,

Этим завершается вывод.

С двумя схемами, разработанными в этом разделе, максимальное реализуемое значение достигает Мы увеличим его до 5040 с помощью схем, рассматриваемых в следующем разделе.

1
Оглавление
email@scask.ru