Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике 6.2.1. ВЫЧИСЛЕНИЯ С ЗАМЕЩЕНИЕМГраф вычислений, изображенный на рис. 6.7, ойисывает алгоритм вычисления дискретного преобразования Фурье. В графе на рис. 6.7 важны ветви, соединяющие узлы, и передачи каждой ветви. Как бы не были переставлены узлы в этом графе, он всегда будет представлять одно и то же вычисление при условии, что соединения между узлами и передачи этих соединений остаются прежними. Частный вид графа, изображенного на рис. 6.7, появился в результате вывода алгоритма путем разделения исходной последовательности на четные и нечетные точки, а затем получения все более мелких подпоследовательностей аналогичным образом. Интересным промежуточным результатом этого вывода является то, что граф рис. 6.7 вдобавок к описанию эффективной процедуры вычисления дискретного преобразования Фурье предлагает полезный способ запоминания исходных данных и результатов вычислений в промежуточных массивах. Чтобы убедиться в этом, полезно отметить, что согласно рис. 6.7 на каждой ступени вычислений происходит преобразование множества из
Используя эту запись и это упорядочение, можно видеть, что основным вычислением в графе на рис. 6.7 является вычисление по схеме рис. 6.8. Уравнение, соответствующее этому графу, имеет вид
Из-за вида графа на рис. 6.8 эта операция называется «бабочкой». Выражение (6.15) подсказывает метод сокращения числа комплексных умножений вдвое. Чтобы увидеть это, заметим, что
Выражения (6.16) изображены графом на рис. 6.9. Следовательно, так как имеются В (6.16)
Рис. 6.8. Направленный граф операции «бабочка» — основной операции на рис. 6.7
Рис. 6.9. Направленный граф упрощенной «бабочки», требующий только одного комплексного умножения
Рис. 6.10. Направленный граф восьмиточечного ДПФ, использующий «бабочку», изображенную на рис. 6.9 Из рис. 6.9 и 6.10 ясно, что для вычисления элементов комплексный массив из Чтобы вычисления выполнялись так, как сказано выше, входные данные должны быть записаны в необычном порядке, который называется двоичной инверсией. Чтобы понять смысл этой терминологии, заметим, что для рассматриваемого восьмиточечного графа требуются три двоичные цифры для нумерации данных. Если мы запишем индексы в (6.14) в двоичной форме, получим
Если Понять, почему для алгоритма с замещением необходима двоичная инверсия, можно, если вспомнить процесс, который привел к алгоритму, изображенному на рис. 6.7. Последовательность
Рис. 6.11. Дерево, изображающее двоичную инверсию сделать, рассматривая второй разряд в индексе. Рассматривая сначала подпоследовательность с четными номерами, убеждаемся, что если второй разряд равен 0, то значение соответствует четному числу этой подпоследовательности, а если второй разряд равен 1, то — нечетному. Тот же процесс проводится и для подпоследовательности, сформированной из нечетных членов исходной подпоследовательности. Этот процесс повторяется до тех пор, пока не получится N подпоследовательностей длины 1. Эта сортировка на четные и нечетные подпоследовательности изображена на рис. 6.11. Таким образом, необходимость упорядочения последовательности
|
1 |
Оглавление
|