Skip to main content
LibreTexts - Ukrayinska

5.2: БПФ від факторингу оператора DFT

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

    • \( \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 у багатовимірному відображенні індексів можна записати як матрично-векторну операцію шляхом\(C=WX \; \; \text{where}\; \; N=8\)

    \[\begin{bmatrix} C(0)\\ C(1)\\ C(2)\\ C(3)\\ C(4)\\ C(5)\\ C(6)\\ C(7) \end{bmatrix}=\begin{bmatrix} W^{0} & W^{0} & W^{0} & W^{0} & W^{0} & W^{0} & W^{0} & W^{0}\\ W^{0} & W^{1} & W^{2} & W^{3} & W^{4} & W^{5} & W^{6} & W^{7}\\ W^{0} & W^{2} & W^{4} & W^{6} & W^{8} & W^{10} & W^{12} & W^{14}\\ W^{0} & W^{3} & W^{6} & W^{9} & W^{12} & W^{15} & W^{18} & W^{21}\\ W^{0} & W^{4} & W^{8} & W^{12} & W^{16} & W^{20} & W^{24} & W^{28}\\ W^{0} & W^{5} & W^{10} & W^{15} & W^{20} & W^{25} & W^{30} & W^{35}\\ W^{0} & W^{6} & W^{12} & W^{18} & W^{24} & W^{30} & W^{36} & W^{42}\\ W^{0} & W^{7} & W^{14} & W^{21} & W^{28} & W^{35} & W^{42} & W^{49} \end{bmatrix}\begin{bmatrix} x(0)\\ x(1)\\ x(2)\\ x(3)\\ x(4)\\ x(5)\\ x(6)\\ x(7) \end{bmatrix} \nonumber \]

    що явно вимагає\(N^2=64\) складних множень і\(N(N-1)\) доповнень. Факторизація оператора DFT\(W\), дає\(W=F_{1}F_{2}F_{3}\; \; and\; \; C=F_{1}F_{2}F_{3}X\).

    Розширення на що дає

    \[\begin{bmatrix} C(0)\\ C(4)\\ C(2)\\ C(6)\\ C(1)\\ C(5)\\ C(3)\\ C(7) \end{bmatrix}=\begin{bmatrix} 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 1 & -1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & -1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & -1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & -1 \end{bmatrix}\begin{bmatrix} 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0\\ W^{0} & 0 & -W^{2} & 0 & 0 & 0 & 0 & 0\\ 0 & W^{0} & 0 & -W^{2} & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1\\ 0 & 0 & 0 & 0 & W^{0} & 0 & -W^{0} & 0\\ 0 & 0 & 0 & 0 & 0 & W^{2} & 0 & -W^{2} \end{bmatrix} \nonumber \]

    \[\begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1\\ W_{0} & 0 & 0 & 0 & -W_{0} & 0 & 0 & 0\\ 0 & W_{1} & 0 & 0 & 0 & -W_{1} & 0 & 0\\ 0 & 0 & W_{2} & 0 & 0 & 0 & -W_{2} & 0\\ 0 & 0 & 0 & W_{3} & 0 & 0 & 0 & -W_{3} \end{bmatrix}\begin{bmatrix} x(0)\\ x(1)\\ x(2)\\ x(3)\\ x(4)\\ x(5)\\ x(6)\\ x(7) \end{bmatrix} \nonumber \]

    де\(F_i\) матриці розріджені. Зверніть увагу, що кожен з\(16\; (\text{or}\; 2N)\) них має ненульові терміни\(F_2\) і\(F_3\) мають умови, що\(8\; (\text{or}\; N)\) не єдності. Якщо\(N=2^M\), то кількість факторів є\(\log (N)=M\). В іншій формі з множниками twiddle розділені таким чином, щоб підрахувати складні множення, які ми маємо

    \[\begin{bmatrix} C(0)\\ C(4)\\ C(2)\\ C(6)\\ C(1)\\ C(5)\\ C(3)\\ C(7) \end{bmatrix}=\begin{bmatrix} 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 1 & -1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & -1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & -1 & 0 & 0\\ 0 & 0 & 0 & & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & -1 \end{bmatrix} \nonumber \]

    \[\begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & W^{0} & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & W^{2} & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0& 0 & 0 & W^{0} & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & W^{2} \end{bmatrix}\begin{bmatrix} 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0\\ 1 & 0 & -1 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & -1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1\\ 0 & 0 & 0 & 0 & 1 & 0 & -1 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & -1 \end{bmatrix} \nonumber \]

    \[\begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & W^{0} & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & W^{1} & 0 & 0\\ 0 & 0 & 0 & 0& 0 & 0 & W^{2} & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & W^{3} \end{bmatrix}\begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 0 & -1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & -1 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & -1 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & -1 \end{bmatrix}\begin{bmatrix} x(0)\\ x(1)\\ x(2)\\ x(3)\\ x(4)\\ x(5)\\ x(6)\\ x(7) \end{bmatrix} \nonumber \]

    який знаходиться у вигляді

    C=A1М1A2М2A3ХC=A1М1A2М2A3Х«role="презентація» стиль = «позиція: відносна;» tabindex = «0">