2: Багатовимірне відображення індексів
- Page ID
- 34395
\( \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}}\)
Потужний підхід до розробки ефективних алгоритмів полягає в розбиванні великої задачі на кілька дрібних. Один метод для цього як з DFT, так і згортки використовує лінійну зміну індексних змінних для відображення вихідної одновимірної задачі в багатовимірну задачу. Такий підхід забезпечує уніфіковане виведення БПФ Кулі-Тукі, алгоритму БПФ простого фактора (PFA) та алгоритму перетворення Фур'є Вінограда (WFTA) БПФ. Він також може бути застосований безпосередньо до згортки, щоб розбити його на кілька коротких згорток, які можуть бути виконані швидше, ніж пряма реалізація. Часто легко перевести алгоритм за допомогою відображення індексів в ефективну програму.