Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 210
Текст из файла (страница 210)
Таким образом, возвращаемый процедурой Кнсикз(чс-ГгТ вектор У действительно представляет собой ДПФ исходного вектора а. В строках 11 и 12 выполняется умножение каждого значения уь на ш„для [1) й = О, 1,..., и/2 — 1. Строка 11 прибавляет это произведение к у„, а строка 12 [с! В строках б и 7 определяется вектор коэффициентов для полиномов А[о) и А[1). Строки 4, 5 и !3 гарантируют, что ш обновляется надлежащим образом, т.е. всякий раз, когда выполняются строки 11 и 12, мы имеем ш = ш„".
(Сохранение текущего значения ш от одной итерации к другой позволяет экономить время по сравнению с многократным вычислением шь с нуля с помощью цикла Гог.) В строках 8 и 9 выполняются рекурсивные вычисления ДПФ„(2 с установкой для )с = О, 1,..., и/2 — 1 следующих значений Глава 30. Полинины и быстрое преобразование Фурье 955 вычитает его. Посюльку мы используем каждый множитель шь как в положительном, так и в отрицательном виде, множители ы„называются поворачивающими ь множителями (ЬонЫ!е Гас(огз). Чтобы определить время работы процедуры Кис()кз)чк-ГАЕТ, заметим, что, за исключением рекурсивных вызовов, каждый вызов занимает время еу(п), где и — длина исходного вектора.
Таким образом, рекуррентное соотношение для времени выполнения имеет вид Т(п) = 2Т(п/2) + й(и) = 9(и!йп) . Итак, используя быстрое преобразование Фурье, можно вычислить полинам с границей степени и в комплексных корнях единицы п-й степени за вре- мя б)(и1яи). Интерполяция в комплексных корнях единицы Завершим рассмотрение схемы умножения полиномов, показав, как выполняется интерполяция юмплексных корней из единицы некоторым полиномом, что позволяет перейти ст формы значений в точках обратно к форме коэффициентов. Для этого ДПФ записывается в виде матричного уравнения, после чего выполняется поиск обратной матрицы. Из уравнения (30.4) можно записать ДПФ как произведение матриц у = е'„а, где $и является матрицей Вандермонд~ содержащей соответствующие степени ыи: ао Уа У1 У2 Уз аз аз аз Уи-2 аи и 1 2(и-1) 3(и-1) (и-1)(и-1) оли сои ~ои ' ' ши ()е, 5)-м элементом матрицы )У„является ьо„у при 5, к = О, 1,..., п степеней элементов матрицы Ъ'„образуют таблицу умножения.
Для выполнения обратной операции, которую запишем как нужно умножить матрицу Ъ'„2, обратную к Ъ"„, на у. — 1. Показатели а =ДПФ„~(у), Теорема 30. 7 (5,я)-й элемент матрицы 1и ' представляет собой о~„у/и для 5, lс = 0,1,. п — 1. 1 1 1 1 м„м„ ши ыи „3 6 1 з ши б ши 9 Ж~ 1 и — 1 2(и-1) ши з( -0 сои 956 Часть Пд Избранные тены Доказательство. Покажем, что ь'„1$'„= 1„, единичной матрице размера п х и.
Рассмотрим (5,)н)-й элемент ~'„1К,: (Ун 1$З„) З = ~~) (ЬЗ„ЬЗ/П)(ЬЗЬЗ ) а=о н — 1 ш„(з з))зь . Эта сумма равна 1 при )н = 5 и 0 — в противном случае согласно лемме о суммировании (лемма 30.6). Чтобы применить эту лемму, заметим, что — (и — 1) < )з — 5 < п — 1, так что )з — 5 не делится на п. Для заданной обратной матрицы 1Г„1 обратное преобразование ДПФ„' (у) вычисляется по формуле а = — Ч~~ уььз„~з 1 н-1 (30.11) п а=о для 5 = О, 1,..., п — 1. Сравнивая уравнения (30.8) и (30.11), мы видим, что если модифицировать алгоритм БПФ путем обмена ролей а и у, замены ы„ на аз„г и деления каждого элемента результата на п, то получится обратное ДПФ (см. упр. 30.2.4). Следовательно, ДПФ„' также можно вычислить за время 1В(п18п). Таким образом, с помощью прямого и обратного БПФ можно преобразовывать полинам с границей степени и из формы коэффициентов в форму значений в точках и обратно за время 1В(п 18 и).
Применительно к умножению полиномов мы показали следующее. Теорема ЗОно (Теорема о свертке) Для любых двух векторов а и Ь длиной и, где и является степенью 2, справедливо соотношение а Э Ь = ДПФг„(ДПФг„(а) ДПФгн(Ь)), где векторы а и Ь дополняются нулями до длины 2и, а "" обозначает покомпо- нентное произведение двух 2п-элементных векторов. Упражнения зо.г.) Докажите следствие 30.4.
зо.г.г Вычислите ДПФ вектора (О, 1, 2, 3). 957 Глава зц Геолинаыы н быстрое нреобразованае Фурье 30.2.3 Выполните упр. 30.1.1, используя схему со временем выполнения й(и 1я и). 30.2.4 Напишите псевдокод для вычисления ДПФ,,' за время й(и 1яи). 30.2.5 Опишите обобщение процедуры БПФ для случая, когда и является степенью 3. Приведите рекуррентное соотношение для времени выполнения и решите его. 30.2.б * Предположим, что вместо выполнения и-элементного БПФ над полем комплексных чисел (где и чстно) мы используем кольцо К целых чисел по модулю т = 2е"~г+', где г — произвольное положительное целое число.
Используйте ы = 2' вместо ь~„в качестве главного значения корня и-й степени из единицы по модулю из. Докажите, что прямое и обратное ДПФ в этой системе является вполне определенным. 30.2. 7 Покажите, как для заданного списка значений хс, зы..., х„з (возможно, с повторениями) найти коэффициенты полинома Р(х) с границей степени и+ 1, который имеет нули только в точках ес, зы ., з„1 (возможно, с повторениями).
Процедура должна выполняться за время 0(и1йг и). (Указание: полинам Р(х) имеет нулевое значение в точке х тогда и только тогда, когда Р(х) кратен (х — зу).) 30.2.0 * Чнрн-преобразованием (сйпр папзТопп) некоторого вектора а = (ас,аы..., ан з) ЯвлаетсЯ вектоР У = (Уо, Уы.,.,Ун 1), где Уь = 2 " „а з"з, а з — пРоизвольное комплексное число. Таким образом, ДПФ является частным случаем чирп-преобразования при з = ш„. Покажите, как за время 0(и !я и) вычислить чирп-преобразование для любого комплексного числа з.
(Указание: воспользуйтесь уравнением хь'1г~ (абхаз) (з (ь 51'1г) чтобы рассматривать чирп-преобразование как свертку.) 30.3. Эффективные реализации БПФ Поскольку практические приложения ДПФ, такие как обработка сигналов, требуют максимальной скорости, в данном разделе мы рассмотрим две наиболее эффективные реализации БПФ. Сначала будет описана итеративная версия алгоритма БПФ, время выполнения которой составляет О(и!ли), однако при этом Часть (71 Избранные темы 95(( в Й скрыта меньшая константа, чем в случае рекурсивной реализации, предло- женной в разделе 30.2. После этого мы вернемся к интуитивным соображениям, приведшим нас к итеративной реализации, чтобы разработать эффективную па- раллельную схему БПФ. Итеративная реализации БПФ Прежде всего заметим, что цикл бог в строках 10-13 процедуры КБС()кб(ЧБГЕТ дважды вычисляет значение ш„уь .
В терминологии компиляторов такое )() значение называется общим иодныраззсеиием (сопппоп зпЬехргеззюп). Можно изменить цикл так, чтобы вычислять это значение только один раз, сохраняя его во временной переменной с. 1ог й = 0 Зо п(2 — 1 1 — Уь 1)) Уа=рь +т )о1 )о) Уь+(пуз) = Уь оз = (п(ап )о) ь (ц Уь Ч-ызУь Уь +ыьУь (о) ь (ц )о) Уь (о) )о) ь (Ц Уь ь' Уь )о) ь [ц Уь 'ьрь (з) Уь (з) Уь (б) (а) Рис.
30.3. Преобразование бабочхи. (а) Слева поступают два входных значения, поворачивающий множитель ьз„" умножается на у„и соответствуюшие сумма и разность выводятся справа, (1 (б) Упрошенная схема преобразования бабочян. Это представление будет использоваться в параллельной схеме БПФ. Выполняемая в данном цикле операция (умножение поворачивающего мнвкителя аз = озь на у„, сохранение произведения в переменной г, прибавление и вычитание 1 из уь ) известна как преобразование бабочки (Ьпнетйу орегайоп), схемати)о) чески представленное на рис. 30.3. Теперь покажем, как сделать алгоритм БПФ итеративным, а не рекурсивным. На рис.
30.4 мы организовали входные векторы рекурсивных вызовов в обрашении к процедуре Кйс()кб1чб-ГРТ в древовидную структуру, в которой первый вызов выполняется для и = 8. Данное дерево содержит по одному узлу для каждого вызова процедуры, помеченному соответствующим входным вектором. Каждое обращение к процедуре Кбс()кз(чй-РЕТ производит два рекурсивных вызова, пока не получит 1-элементный вектор. Первый вызов находится в левом дочернем узле, а второй — в правом. Рассматривая дерево, можно заметить, что если бы можно было расположить элементы исходного вектора а в том порядке, в котором они появляются в листьях дерева, то можно было бы увидеть выполнение процедуры КБС()кз(ЧБ-ЕРТ Глава 30.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
