13.3: Виведення швидкого перетворення Фур'є

Last updated
Save as PDF

Page ID: 34003

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

Щоб отримати БПФ, ми припускаємо, що тривалість сигналу дорівнює двом:\(N=2^l\). Розглянемо, що відбувається з парними і непарними елементами послідовності в обчисленні DFT.

\[\begin{align}S(k) &=s(0)+s(2) e^{(-j) \frac{2 \pi 2 k}{N}}+\ldots+s(N-2) e^{(-j) \frac{2 \pi(N-2) k}{N}}+s(1) e^{(-j) \frac{2 \pi k}{N}}+s(3) e^{(-j) \frac{2 \pi \times (2+1) k}{N}}+\ldots+s(N-1) e^{(-j) \frac{2 \pi(N-2+1) k}{N}} \nonumber \\ &=s(0)+s(2)e^{(-j)\frac{2\pi k}{\frac{N}{2}}} + \ldots + s(N-2)e^{(-j) \frac{2 \pi\left(\frac{N}{2}-1\right) k}{\frac{N}{2}}} +\left( s(1)+s(3) e^{(-j) \frac{2 \pi k}{\frac{N}{2}}}+\dots+s(N-1) e^{(-j) \frac{2 \pi\left(\frac{N}{2}-1\right) k}{\frac{N}{2}}}\right) e^{\frac{-(j 2 \pi k)}{N}} \end{align} \nonumber \]

Кожен член в квадратних дужках має вигляд a\(\frac{N}{2}\) -length DFT. Перший - це DFT парних елементів, а другий з непарних елементів. Перший ДФТ поєднується з другим помноженим на складну експоненціальну\(e^{\frac{-(j2\pi k)}{N}}\). Перетворення половинної довжини оцінюються за частотними індексами\(k \in\{0, \ldots, N-1\}\). Зазвичай кількість частотних індексів у діапазоні обчислення DFT між нулем та довжиною перетворення мінус одиниця. Обчислювальна перевага БПФ походить від розпізнавання періодичного характеру дискретного перетворення Фур'є. БПФ просто повторно використовує обчислення, зроблені в половинних перетвореннях і поєднує їх за допомогою додавання і множення на\(e^{\frac{-(j2\pi k)}{N}}\), що не є періодичним\(\frac{N}{2}\), щоб переписати Length-N DFT. Малюнок\(\PageIndex{1}\) ілюструє це розкладання. Як вона стоїть, тепер обчислюємо дві length-\(\frac{N}{2}\) перетворення (складність\(2O(\frac{N^2}{4})\)), одну з них множимо на складну експоненціальну (складність\(O(N)\)), і додаємо результати (складність\(O(N)\)). На даний момент загальна складність все ще переважає обчислення DFT на половину довжини, але коефіцієнт пропорційності був зменшений.

Тепер для веселощів. \(N=2^l\)Тому що кожна з половинних перетворень може бути зведена до двох перетворень чверті довжини, кожна з них до двох восьмої довжини і т.д. це розкладання триває до тих пір, поки ми не залишитеся з перетвореннями довжини-2. Це перетворення досить просте, передбачаючи лише доповнення. Таким чином, перший ступінь БПФ має\(\frac{N}{2}\) довжину-2 перетворення (див. Нижню частину рисунка\(\PageIndex{1}\)). Пари цих перетворень об'єднуються шляхом додавання однієї до іншої, помноженої на складну експоненціальну. Кожна пара вимагає 4 складання і 4 множення, що дає загальну кількість обчислень, що дорівнює\(8 \frac{N}{4}=\frac{N}{2}\). Ця кількість обчислень не змінюється від етапу до етапу. Оскільки кількість ступенів, кількість разів довжина може бути розділена на два, дорівнює\(\log_2 N\), складність БПФ є\(O(N \log N)\).

Малюнок\(\PageIndex{1}\): Початкове розкладання DFT довжиною 8 на терміни з використанням парних і непарних індексованих входів позначає першу фазу розробки алгоритму БПФ. Коли ці перетворення на половину довжини послідовно розкладені, ми залишаємо діаграму, показану на нижній панелі, яка зображує обчислення БПФ довжина-8.

Проведення прикладу зробить обчислювальну економію більш очевидною. Давайте розглянемо деталі довжини-8 DFT. Як показано на малюнку\(\PageIndex{1}\), ми спочатку розкладаємо DFT на дві довжини-4 DFT, при цьому виходи додаються та віднімаються разом попарно. Розглядаючи Рисунок,\(\PageIndex{1}\) як індекс частоти йде від 0 до 7, ми переробляємо значення з dlength-4 DFT в остаточний розрахунок через періодичність виходу DFT. Вивчаючи, як збираються пари виходів разом, ми створюємо базовий обчислювальний елемент, відомий як метелик (рис.\(\PageIndex{2}\)).

Малюнок\(\PageIndex{2}\): Основним обчислювальним елементом швидкого перетворення Фур'є є метелик. Він приймає два комплексних числа, представлених a і b, і формує показані величини. Кожній метелику потрібно одне складне множення і два складних складання.

Розглядаючи разом обчислення, що включають загальні вихідні частоти з двох напівдовжини DFT, ми бачимо, що два комплексні множення пов'язані один з одним, і ми можемо зменшити нашу обчислювальну роботу ще більше. Подальше розклавши dlength-4 DFT на дві довжини-2 DFT і об'єднавши їх виходи, приходимо до діаграми, що підсумовує швидке перетворення Фур'є довжина-8 (рис.\(\PageIndex{1}\)). Хоча більшість складних множень досить прості (множення за\(e^{-(j \pi)}\) допомогою заперечення реальної та уявної частин), давайте порахуємо їх для цілей оцінки складності як повні складні множення. Ми маємо\(\frac{N}{2}=4\) складні множники та\(2N=16\) доповнення для кожного етапу та\(\log_2 N = 3\) етапів, роблячи кількість основних обчислень\(\frac{3N}{2}\log_2 N\) відповідно до прогнозів.

Вправа\(\PageIndex{1}\)

Зверніть увагу, що впорядкування вхідної послідовності у двох частинок Figure\(\PageIndex{1}\) не зовсім однакове. Чому б і ні? Як визначається замовлення?

Відповідь: Верхня панель не використовувала алгоритм БПФ для обчислення довжини-4 DFT, тоді як нижня має. Порядок визначається алгоритмом.

Були виявлені інші «швидкі» алгоритми, всі з яких використовують, скільки загальних факторів має довжина перетворення N. У теорії чисел кількість простих множників заданого цілого має виміри, наскільки воно складене. Числа\(16\) і\(81\) дуже складові (рівні\(2^4\) і\(3^4\) відповідно), число менше\(18\) так (\(2^1 3^2\)), а\(17\) зовсім не (воно просте). Протягом більш ніж тридцяти років розробки алгоритму перетворення Фур'є оригінальний алгоритм Кулі-Тукі є далеко і далеко найбільш часто використовуваним. Він настільки обчислювально-ефективний, що потужність двох довжин перетворень часто використовується незалежно від фактичної довжини даних.