4.2 Convolución circular y el dft

IntroducciÓN

Usted debería familiarizarse con la convolución discreta , que nos explica como dos señales discretas $x(n)$ , la entrada del sistema, y $h(n)$ , la respuesta del sistema, se puede definir el resultado del sistema como

Formula de la convoluciÓN circular

¿Quépasa cuando multiplicamos dos DFT una con la otra, donde $Y(k)$ es la DFT de $y(n)$ ?

Usando la formula sintetizada de DFT para $y(n)$

Y aplicando análisis a la formula $F(k)=\sum_{m=0}^{N-1} f(m)e^{(-j\frac{2\pi }{N}kn)}$

Pasos para la convoluciÓN circular

Los pasos a seguir para la convolucion cíclica son los mismos que se usan en la convolución linear, excepto que todos los cálculos para todos losíndices están hecho"mod N" = "en la rueda"

Pasos para la convoluciÓN cÍClica

• Paso 1: "Grafique" $f(m)$ y $h({\left((\right(, -, \mathrm{m}, \left), \right))}_N())$

• Paso 2: "Rote" $h({\left((\right(, -, \mathrm{m}, \left), \right))}_N())$ $n$ en la dirección ACW ( dirección opuesta al reloj) para obtener $h({\left((\right(, \mathrm{n}, -, \mathrm{m}, \left), \right))}_N)$ (por ejemplo rote la secuencia, $h(n)$ , en dirección del reloj por $n$ pasos).

• Paso 3: Multiplique punto por punto la rueda $f(m)$ y la rueda $h({\left((\right(, \mathrm{n}, -, \mathrm{m}, \left), \right))}_N)$ wheel. $$\mathrm{sum}=y(n)$$

• Paso 4: Repite para $0\le n\le N-1$

Algoritmo alterno

Algoritmo de convoluciÓN circular alterno

• Paso 1: Calcule el DFT de $f(n)$ que da $F(k)$ y calcule el DFT de $h(n)$ que da $H(k)$ .
• Paso 2: Multiplique punto por punto $Y(k)=F(k)H(k)$
• Paso 3: Invierta el DFT $Y(k)$ que da $y(n)$

Parece una manera repetitiva de hacer las cosas, pero existen maneras rápidas de calcular una secuencia DFT.

Para convolucionar circularmente dos secuencias de $2$ $N$ -puntos: $$y(n)=\sum_{m=0}^{N-1} f(m)h({\left(\right(n-m\left)\right)()}_N)$$ Para cualquier $n$ : $N$ múltiplos, $N-1$ sumas

$N$ puntos implica $N^2$ multiplicaciones, $N(N-1)$ sumas implica una complejidad de $O(N^2)$ .