5.8: DFT - Complejidad Computacional
- Page ID
- 85407
\( \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}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)- Una breve explicación de la complejidad del cálculo y cómo la complejidad de la transformada discreta de Fourier es de orden N al cuadrado.
Ahora tenemos una forma de calcular el espectro para una señal arbitraria: La Transformada Discreta de Fourier (DFT) calcula el espectro a N frecuencias igualmente espaciadas a partir de una secuencia de longitud- N. Un problema que nunca surge en el “cálculo” analógico, como el que realiza un circuito, es cuánto trabajo se necesita para realizar la operación de procesamiento de señal como el filtrado. En cómputos, esta consideración se traduce en el número de pasos computacionales básicos requeridos para realizar el procesamiento necesario. El número de pasos, conocido como la complejidad, se vuelve equivalente a cuánto tiempo lleva el cálculo (cuánto tiempo debemos esperar una respuesta). La complejidad no está tanto ligada a computadoras o lenguajes de programación específicos sino a cuántos pasos se requieren en cualquier computadora. Así, la complejidad declarada de un procedimiento dice que el tiempo empleado será proporcional a alguna función de la cantidad de datos utilizados en el cómputo y la cantidad demandada.
Por ejemplo, considere la fórmula para la transformada discreta de Fourier. Para cada frecuencia que elegimos, debemos multiplicar cada valor de señal por un número complejo y sumar los resultados. Para una señal de valor real, cada multiplicación compleja en tiempo real requiere dos multiplicaciones reales, lo que significa que tenemos 2N multiplicaciones para realizar. Para sumar los resultados, debemos mantener separadas las partes real e imaginaria. Agregar N números requiere N-1 adiciones. En consecuencia, cada frecuencia requiere
\[2N+2(N-1)=4N-2 \nonumber \]
pasos computacionales básicos. Como tenemos N frecuencias, el número total de cálculos es
\[N(4N-2) \nonumber \]
En los cálculos de complejidad, solo nos preocupamos por lo que sucede a medida que aumentan las longitudes de los datos, y tomamos el término dominante, aquí el término 4N 2, como reflejo de cuánto trabajo implica hacer el cálculo. Como las constantes multiplicativas no importan ya que estamos haciendo una evaluación “proporcional a”, encontramos que la DFT es un procedimiento computacional O (N 2). Esta notación se lee “orden N -cuadrado”. Así, si duplicamos la longitud de los datos, esperaríamos que el tiempo de cómputo se cuadruplicara aproximadamente.
Al hacer la evaluación de complejidad para el DFT, asumimos que los datos eran reales. Surgen tres preguntas. En primer lugar, los espectros de tales señales tienen simetría conjugada, es decir, que los componentes de frecuencia negativa\ [k=\ left\ {\ frac {N} {2} +1,... , N+1\ derecho\}\
en la DFT) pueden calcularse a partir de los componentes de frecuencia positiva correspondientes. ¿Esta simetría cambia la complejidad de la DFT? En segundo lugar, supongamos que los datos son de valor complejo; ¿cuál es la complejidad de la DFT ahora? Por último, una pregunta menos importante pero interesante es suponer que queremos valores de frecuencia K en lugar de N; ahora ¿cuál es la complejidad?
Solución
Cuando la señal es de valor real, es posible que solo necesitemos la mitad de los valores espectrales, pero la complejidad permanece sin cambios. Si los datos son de valor complejo, lo que exige retener todos los valores de frecuencia, la complejidad vuelve a ser la misma. Cuando solo se necesitan K frecuencias, la complejidad es O (KN).