Skip to main content
LibreTexts - Ukrayinska

8: Алгоритм швидкого перетворення Фур'є Кулі-Тукі

  1. Last updated
  2. Save as PDF
  • Page ID
    34316

    • \( \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}}\)

    Публікація Кулі і Тукі в 1965 році ефективного алгоритму розрахунку ДФТ стало головним поворотним моментом у розвитку цифрової обробки сигналів. Протягом п'яти або близько того років, що послідували, різні розширення та модифікації були внесені в оригінальний алгоритм. До початку 1970-х років практичні програми були в основному у формі, яка використовується сьогодні. Розробка стандарту показує, як DFT послідовності довжина-N можна просто обчислити з двох DFT довжини N/2 парних членів індексу та непарних членів індексу. Потім це застосовується до двох половинної довжини DFT, щоб дати чотири чверті довжини DFT, і повторюється, поки не залишаться N скалярів, які є значеннями DFT. Через поперемінне прийняття парних і непарних членів індексу дві форми результуючих програм називаються децимація-в-часі і розрідження-в-частоті. Для довжини\(2^M\), процес ділення повторюється\(M=\log _{2}N\) раз і вимагає N множень кожного разу. Це дає знамениту формулу обчислювальної складності БПФ,\(N\log _{2}N\) яка була виведена в багатовимірному відображенні індексів.