Práctica 2: Análisis de Fourier - Resoluciones (Ej. 20 a 24)

Transformada de Fourier Discreta (DFT)

Marco Teórico Previo

Pasamos del dominio continuo al dominio discreto y de longitud finita. La señal es un vector de $N$ muestras: $f = (f[0], f[1], \dots, f[N-1])$.

• Transformada Discreta de Fourier (DFT):

$$\hat{f}[k] = \sum_{j=0}^{N-1} f[j] e^{-i \frac{2\pi}{N} j k} = \sum_{j=0}^{N-1} f[j] W_N^{jk}$$

donde $W_N = e^{-i 2\pi / N}$ es la raíz $N$-ésima primitiva de la unidad.

• Periodicidad Espectral: Por definición de las exponenciales discretas complejas, el espectro es periódico de período $N$, es decir, $\hat{f}[k] = \hat{f}[k + N]$. En particular, índices negativos como $\hat{f}[-k]$ equivalen a evaluar $\hat{f}[N-k]$.

---

Ejercicio 20: Simetría Conjugada de Señales Reales

Intuición Didáctica

Al igual que en el caso continuo, si una señal es estrictamente real, la Transformada de Fourier debe reflejar esa falta de componentes complejas inherentes a la señal mediante un balance perfecto en las frecuencias positivas y negativas.

Resolución Rigurosa

1. Demostración de la Simetría Conjugada ($\overline{\hat{f}[k]} = \hat{f}[-k]$) Asumimos que $f[j] \in \mathbb{R}$ para todo $j$, lo que implica que $\overline{f[j]} = f[j]$. Partimos de la definición de la DFT y le aplicamos el operador de conjugación a ambos lados:

$$\overline{\hat{f}[k]} = \overline{\sum_{j=0}^{N-1} f[j] e^{-i \frac{2\pi}{N} j k}} = \sum_{j=0}^{N-1} \overline{f[j]} \, \overline{e^{-i \frac{2\pi}{N} j k}}$$

Sustituyendo $\overline{f[j]}$ por su valor real $f[j]$ e invirtiendo el signo de la fase imaginaria:

$$\overline{\hat{f}[k]} = \sum_{j=0}^{N-1} f[j] e^{i \frac{2\pi}{N} j k}$$

Podemos agrupar el signo negativo dentro del índice frecuencial $k$:

$$\overline{\hat{f}[k]} = \sum_{j=0}^{N-1} f[j] e^{-i \frac{2\pi}{N} j (-k)} = \hat{f}[-k]$$

Dado que $\hat{f}[-k] = \hat{f}[N-k]$ por periodicidad, esto demuestra la simetría conjugada alrededor del índice medio (frecuencia de Nyquist).

2. Demostración para Función Par Ahora sumamos la hipótesis de que $f$ es par: $f[j] = f[N-j]$. Sabemos que cualquier suma exponencial se descompone por Euler en su parte real (coseno) e imaginaria (seno):

$$\hat{f}[k] = \sum_{j=0}^{N-1} f[j] \cos\left(\frac{2\pi}{N} j k\right) - i \sum_{j=0}^{N-1} f[j] \sin\left(\frac{2\pi}{N} j k\right)$$

Analicemos la parte imaginaria. Como $f$ es par, sus muestras equidistantes del centro son iguales. El núcleo del seno, por el contrario, es impar:

$$\sin\left(\frac{2\pi}{N} (N-j) k\right) = \sin\left(2\pi k - \frac{2\pi}{N} j k\right) = -\sin\left(\frac{2\pi}{N} j k\right)$$

Al sumar sobre todo el período simétrico, los pares de muestras $f[j]\sin(\dots)$ y $f[N-j]\sin(\dots)$ se cancelan exactamente. (Los puntos $j=0$ y $j=N/2$ dan seno cero directamente). Por lo tanto, la parte imaginaria es idénticamente nula. Esto significa que $\hat{f}[k] \in \mathbb{R}$ (es estrictamente real). Finalmente, por la simetría conjugada demostrada en el punto 1, si la función es real: $\hat{f}[-k] = \overline{\hat{f}[k]} = \hat{f}[k]$ (el conjugado de un número real es sí mismo). Lo que define que $\hat{f}[k] = \hat{f}[-k]$, probando que el espectro es PAR.

[!infobox] Ejercicio 20: Simetría Conjugada Discreta
Contexto: Propiedades base de la DFT sobre vectores en R^N.
Demostración Rigurosa: 
Tomando el conjugado complejo de la sumatoria DFT y recordando que f[j] = f*[j] por ser real, el conjugado invierte el signo de la fase exponencial, lo cual por definición equivale a evaluar la transformada en la frecuencia negativa (-k). Así, (F[f][k])* = F[f][-k].
Para f par, la sumatoria imaginaria del seno evalúa a 0 por antisimetría del núcleo trigonométrico. La DFT resulta real y, al aplicar la propiedad anterior, hereda la paridad de la señal original.
Advertencia/Clave: A diferencia del caso continuo, el "eje temporal" discreto es cíclico. f[-j] es equivalente a la muestra en f[N-j]. Por eso la simetría se observa pivotando respecto a N/2 (frecuencia de Nyquist), no respecto al "origen".

---

Ejercicio 21: Transformadas Básicas en $\mathbb{C}^4$

Intuición Didáctica

Aquí $N=4$. La raíz de la unidad es $W_4 = e^{-i 2\pi / 4} = e^{-i \pi/2} = -i$. Esto simplifica las potencias enormemente, pues conforman ciclos del tipo $1, -i, -1, i$.

Resolución Rigurosa

1. Transformada de $(1, 1, 1, 1)$ La fórmula escalar da:

$$\hat{f}[k] = \sum_{j=0}^{3} (1) (-i)^{jk}$$

• Para $k=0$: $\hat{f}[0] = 1^0 + 1^0 + 1^0 + 1^0 = 4$.
• Para $k=1, 2, 3$: La suma es una progresión geométrica de razón $(-i)^k \neq 1$. Usamos la fórmula de la serie geométrica $\sum_{j=0}^{N-1} r^j = \frac{1 - r^N}{1 - r}$:

$$\sum_{j=0}^3 (-i)^{jk} = \frac{1 - ((-i)^k)^4}{1 - (-i)^k} = \frac{1 - (-i)^{4k}}{1 - (-i)^k} = \frac{1 - 1^k}{1 - (-i)^k} = 0$$

Resultado: $\hat{f} = (4, 0, 0, 0)$. (Interpretación física: una señal constante (continua) sólo tiene componente de frecuencia 0).

2. Transformada de $(1, -i, -1, i)$ Notemos que el vector ingresado es exactamente la sucesión de potencias $W_4^j = (-i)^j$. Aplicamos la fórmula:

$$\hat{f}[k] = \sum_{j=0}^{3} (-i)^j (-i)^{jk} = \sum_{j=0}^{3} (-i)^{j(k+1)}$$

Esta es otra suma geométrica con razón $r = (-i)^{k+1}$.

• Si $k+1$ es múltiplo de $4$ (esto ocurre cuando $k=3$ para el dominio $[0,3]$): La razón es $(-i)^4 = 1$. La suma de cuatro unos da $4$. Por ende, $\hat{f}[3] = 4$.
• Para el resto de las frecuencias ($k \in \{0, 1, 2\}$): La razón $r \neq 1$, y la suma geométrica da $0$ debido al numerador $(1 - r^4) = 1 - ((-i)^{k+1})^4 = 1 - 1 = 0$. Resultado: $\hat{f} = (0, 0, 0, 4)$. (Interpretación física: inyectamos en el sistema una única onda compleja pura que corresponde exactamente al 3er armónico).

---

Ejercicio 22: Espectro de un Pulso en $N=8$

Resolución Rigurosa

$N=8$, vector $f = (1, 1, 0, 0, 0, 0, 0, 0)$. La base frecuencial usa $W_8 = e^{-i 2\pi / 8} = e^{-i \pi / 4} = \cos(-\pi/4) + i \sin(-\pi/4) = \frac{\sqrt{2}}{2} - i \frac{\sqrt{2}}{2}$. Dado que solo las muestras $j=0$ y $j=1$ son no nulas, la sumatoria colapsa a dos términos:

$$\hat{f}[k] = f[0] W_8^{0} + f[1] W_8^{k} = 1 + W_8^k = 1 + e^{-i k \frac{\pi}{4}}$$

Calculamos componente a componente:

• $\hat{f}[0] = 1 + e^0 = 1 + 1 = 2$
• $\hat{f}[1] = 1 + \left(\frac{\sqrt{2}}{2} - i \frac{\sqrt{2}}{2}\right) = (1 + \frac{\sqrt{2}}{2}) - i \frac{\sqrt{2}}{2}$
• $\hat{f}[2] = 1 + e^{-i \pi / 2} = 1 - i$
• $\hat{f}[3] = 1 + \left(-\frac{\sqrt{2}}{2} - i \frac{\sqrt{2}}{2}\right) = (1 - \frac{\sqrt{2}}{2}) - i \frac{\sqrt{2}}{2}$
• $\hat{f}[4] = 1 + e^{-i \pi} = 1 - 1 = 0$
• $\hat{f}[5] = 1 + \left(-\frac{\sqrt{2}}{2} + i \frac{\sqrt{2}}{2}\right) = (1 - \frac{\sqrt{2}}{2}) + i \frac{\sqrt{2}}{2}$
• $\hat{f}[6] = 1 + e^{-i 3\pi / 2} = 1 + i$
• $\hat{f}[7] = 1 + \left(\frac{\sqrt{2}}{2} + i \frac{\sqrt{2}}{2}\right) = (1 + \frac{\sqrt{2}}{2}) + i \frac{\sqrt{2}}{2}$

(Podemos constatar la simetría conjugada al ser una señal real: $\hat{f}[1] = \overline{\hat{f}[7]}$, $\hat{f}[2] = \overline{\hat{f}[6]}$, etc).

---

Ejercicio 23: Algoritmo FFT de Cooley-Tukey ($N=8 \to 4 \times N=2$)

Intuición Didáctica

En lugar de hacer $N^2 = 64$ multiplicaciones para calcular el espectro, el algoritmo divide recursivamente la señal en índices pares e impares, resolviendo sub-problemas hasta llegar a pares atómicos de 2 elementos ("mariposas"). El costo computacional se reduce dramáticamente a $O(N \log N)$.

Resolución Rigurosa

El método de Decimación en el Tiempo (Radix-2) establece que para $N=8$:

$$\hat{f}[k] = \text{DFT}_{\text{pares}}[k] + W_8^k \cdot \text{DFT}_{\text{impares}}[k]$$

Y explotando la periodicidad para la segunda mitad del espectro:

$$\hat{f}[k+4] = \text{DFT}_{\text{pares}}[k] - W_8^k \cdot \text{DFT}_{\text{impares}}[k]$$

Paso 1: División Radix-2 Inicial Sea $E$ la DFT de los índices pares $(f[0], f[2], f[4], f[6])$ y $O$ la DFT de los impares $(f[1], f[3], f[5], f[7])$. Ambas $E$ y $O$ son transformadas de tamaño $N=4$.

$$\hat{f}[k] = E[k] + W_8^k O[k] \quad \text{y} \quad \hat{f}[k+4] = E[k] - W_8^k O[k] \quad (para \ k=0,1,2,3)$$

Paso 2: División Recursiva a bloques de $N=2$ Para calcular $E$ (tamaño 4), subdividimos de nuevo en pares e impares respecto a su propio sub-índice:

• Pares de los pares: $(f[0], f[4])$
• Impares de los pares: $(f[2], f[6])$

Hacemos lo mismo para el vector $O$:

• Pares de los impares: $(f[1], f[5])$
• Impares de los impares: $(f[3], f[7])$

Definimos las cuatro transformadas bases de $\mathbb{C}^2$: $T_1 = \text{DFT}(f[0], f[4])$ $T_2 = \text{DFT}(f[2], f[6])$ $T_3 = \text{DFT}(f[1], f[5])$ $T_4 = \text{DFT}(f[3], f[7])$

Soporte de $\mathbb{C}^2$: Para una entrada genérica $(a, b)$, su DFT bidimensional es analíticamente $(a+b, a-b)$ ya que $W_2^0 = 1$ y $W_2^1 = -1$. Luego, estas 4 transformadas bases se combinan para reconstruir los espectros $E$ y $O$ de tamaño $N=4$ usando el factor de rotación respectivo $W_4^k$: $E[k] = T_1[k] + W_4^k T_2[k]$, $E[k+2] = T_1[k] - W_4^k T_2[k]$ (para $k=0,1$) $O[k] = T_3[k] + W_4^k T_4[k]$, $O[k+2] = T_3[k] - W_4^k T_4[k]$ (para $k=0,1$) (Hemos completado la estructuración del algoritmo tal cual requería el enunciado).

---

Ejercicio 24: Cálculo Analítico de FFT sobre función dada

Resolución Rigurosa

Entrada: $f = (1, 1, 1, 1, 1, 1, 6, 7)$. Evaluaremos aplicando estrictamente la arquitectura del Ejercicio 23.

Nivel 1: Cuatro Transformadas de $\mathbb{C}^2$ Sabiendo que DFT$(a,b) = (a+b, a-b)$: $T_1 = \text{DFT}(f[0], f[4]) = \text{DFT}(1, 1) = (2, 0)$ $T_2 = \text{DFT}(f[2], f[6]) = \text{DFT}(1, 6) = (7, -5)$ $T_3 = \text{DFT}(f[1], f[5]) = \text{DFT}(1, 1) = (2, 0)$ $T_4 = \text{DFT}(f[3], f[7]) = \text{DFT}(1, 7) = (8, -6)$

Nivel 2: Composición intermedia para tamaño $N=4$ ($E$ y $O$) Utilizamos $W_4^0 = 1$ y $W_4^1 = -i$. Para el vector de las muestras originalmente pares ($E$): $E[0] = T_1[0] + 1 \cdot T_2[0] = 2 + 7 = 9$ $E[1] = T_1[1] - i \cdot T_2[1] = 0 - i(-5) = 5i$ $E[2] = T_1[0] - 1 \cdot T_2[0] = 2 - 7 = -5$ $E[3] = T_1[1] - (-i) \cdot T_2[1] = 0 + i(-5) = -5i$ Sub-espectro: $E = (9, 5i, -5, -5i)$.

Para el vector de las muestras originalmente impares ($O$): $O[0] = T_3[0] + 1 \cdot T_4[0] = 2 + 8 = 10$ $O[1] = T_3[1] - i \cdot T_4[1] = 0 - i(-6) = 6i$ $O[2] = T_3[0] - 1 \cdot T_4[0] = 2 - 8 = -6$ $O[3] = T_3[1] - (-i) \cdot T_4[1] = 0 + i(-6) = -6i$ Sub-espectro: $O = (10, 6i, -6, -6i)$.

Nivel 3: Síntesis Final tamaño $N=8$ ($\hat{f}$) Factores de rotación: $W_8^0 = 1$, $W_8^1 = \frac{\sqrt{2}}{2}(1-i)$, $W_8^2 = -i$, $W_8^3 = -\frac{\sqrt{2}}{2}(1+i)$. Fórmula base: $\hat{f}[k] = E[k] + W_8^k O[k]$ y $\hat{f}[k+4] = E[k] - W_8^k O[k]$.

Para $k=0$: $\hat{f}[0] = 9 + 10 = 19$ $\hat{f}[4] = 9 - 10 = -1$

Para $k=1$: Rotación: $W_8^1 \cdot O[1] = \left[\frac{\sqrt{2}}{2}(1-i)\right](6i) = 3\sqrt{2}(i - i^2) = 3\sqrt{2}(1+i)$. $\hat{f}[1] = 5i + 3\sqrt{2}(1+i) = 3\sqrt{2} + i(5 + 3\sqrt{2})$ $\hat{f}[5] = 5i - 3\sqrt{2}(1+i) = -3\sqrt{2} + i(5 - 3\sqrt{2})$

Para $k=2$: Rotación: $W_8^2 \cdot O[2] = (-i)(-6) = 6i$. $\hat{f}[2] = -5 + 6i$ $\hat{f}[6] = -5 - 6i$

Para $k=3$: Rotación: $W_8^3 \cdot O[3] = \left[-\frac{\sqrt{2}}{2}(1+i)\right](-6i) = 3\sqrt{2}(i + i^2) = 3\sqrt{2}(-1 + i) = -3\sqrt{2} + i3\sqrt{2}$. $\hat{f}[3] = -5i + (-3\sqrt{2} + i3\sqrt{2}) = -3\sqrt{2} + i(3\sqrt{2} - 5)$ $\hat{f}[7] = -5i - (-3\sqrt{2} + i3\sqrt{2}) = 3\sqrt{2} - i(3\sqrt{2} + 5)$

(Test de Sanidad: Verificamos simetría conjugada para la señal real de origen: $\hat{f}[7] = \overline{\hat{f}[1]}$ y $\hat{f}[6] = \overline{\hat{f}[2]}$. ¡Funciona perfectamente!).

[!infobox] Ejercicio 23 y 24: Algoritmo Fast Fourier Transform (FFT) Radix-2
Contexto: Descomposición arborescente de Cooley-Tukey para cálculo eficiente.
Demostración Rigurosa:
Al operar N=8, se reordena la señal base utilizando "bit-reversal" para aislar los nodos pares e impares de manera recursiva hasta subvectores atómicos de C².
Luego, se ejecutan operaciones cruzadas de "mariposa":
1) Cuatro DFT de tamaño 2 sin coeficientes de rotación (sumas y restas simples).
2) Dos DFT de tamaño 4 (E y O) introduciendo W_4.
3) La síntesis final donde el espectro total de tamaño 8 es la combinación E[k] +/- W_8^k * O[k].
Advertencia/Clave: El error usual durante una evaluación escrita es arrastrar equivocadamente un signo "i" de las rotaciones angulares o perderse en la recomposición de los índices. Siempre realizar el "Test de Sanidad" en la última capa comprobando la simetría conjugada del resultado.