5.2: La FFT de Factorizar el Operador DFT

Última actualización
Guardar como PDF

Page ID: 87103

$ \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}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

La definición de la DFT en el Mapeo de Índice Multidimensional puede escribirse como una operación matriz-vector por$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 \]

lo que claramente requiere multiplicaciones y$N(N-1)$ adiciones$N^2=64$ complejas. Una factorización del operador DFT,$W$, da$W=F_{1}F_{2}F_{3}\; \; and\; \; C=F_{1}F_{2}F_{3}X$.

Ampliando en eso da

\[\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 \]

donde las$F_i$ matrices son escasas. Tenga en cuenta que cada uno tiene términos$16\; (\text{or}\; 2N)$ distintos de cero$F_2$ y y$F_3$ tienen términos$8\; (\text{or}\; N)$ no unitarios. Si$N=2^M$, entonces el número de factores es$\log (N)=M$. En otra forma con los factores de twiddle separados para contar las multiplicaciones complejas que tenemos

\[\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 \]

que está en la forma

$C = A 1 M 1 A 2 M 2 A 3 X “role="presentación” style="position:relative;” tabindex="0">$

descrito por el mapa índice. $A_1$,$A_2$, y$A_3$ cada una representa$8$ adiciones, o, en general,$N$ adiciones. $M_1$y$M_2$ cada uno representa$4$ (o$N/2$) multiplicaciones.

Este es un resultado muy interesante que muestra que implementar la DFT usando la forma factorizada requiere considerablemente menos aritmética que la definición de factor único. En efecto, la forma de la fórmula que derivaron Cooley y Tukey mostrando que la cantidad de aritmética requerida por la FFT está en el orden de se$N\log N$ puede ver a partir de la formulación factorizada del operador.

Gran parte de la teoría de la FFT se puede desarrollar utilizando factorización de operadores y tiene algunas ventajas para la implementación de arquitecturas computacionales paralelas y vectoriales. El enfoque del espacio propio es algo del mismo tipo.

Colaborador

ContribeeBurrus