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 y n x n h n k x k h n k Cuando dos DFT son dadas (secuencias de tamaño finito usualmente del tamaño N), nosotros no podemos multiplicar esas dos señales así como así, como lo sugiere la formula de arriba usualmente conocida como convolución linear. Ya que las DFT son periódicas, tienen valores no cero para n N así la multiplicación de estas dos señales será no cero para n N . Necesitamos definir otro tipo de convolucion que dará como resultado nuestra señal convuelta teniendo el valor de cero fuera del rango n 0 1 … N 1 . Esto nos ayuda a desarrollar la idea de convolución circular, también conocida como convolución cíclica o periódica.

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 ? Y k F k H k cuando 0 k N 1 Usando la formula sintetizada de DFT para y n y n 1 N k 0 N 1 F k H k j 2 N k n Y aplicando análisis a la formula F k m 0 N 1 f m j 2 N k n y n 1 N k 0 N 1 m 0 N 1 f m j 2 N k n H k j 2 N k n m 0 N 1 f m 1 N k 0 N 1 H k j 2 N k n m donde podemos reducir la segunda sumatoria de la ecuación de arriba en h ( ( n − m ) ) N 1 N k 0 N 1 H k j 2 N k n m y n m 0 N 1 f m h ( ( n − m ) ) N Igual a la convolución circular! cuando tenemos 0 n N 1 arriba , para obtener dos: y n ⊛ f n h n Que la notación ⊛ representa la convolucion circular "mod N".

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 ( ( − m ) ) N

Step 1 Paso 2: "Rote" h ( ( − m ) ) N n en la dirección ACW ( dirección opuesta al reloj) para obtener h ( ( n − m ) ) N (por ejemplo rote la secuencia, h n , en dirección del reloj por n pasos).

Step 2 Paso 3: Multiplique punto por punto la rueda f m y la rueda h ( ( n − m ) ) N wheel. sum y n Paso 4: Repite para 0 n N 1 Convolve (n = 4)

Dos señales discretas que seran convolucionadas. h ( ( − m ) ) N

Multiplique f m y sume para dar: y 0 3 h ( ( 1 − m ) ) N

Multiplique f m y sume para dar: y 1 5 h ( ( 2 − m ) ) N

Multiplique f m y sume para dar: y 2 3 h ( ( 3 − m ) ) N

Multiplique f m y sume para dar: y 3 1 La Siguiente Demostración le permite este algoritmo. Vea aquí para instrucciones de como se usa este demo.

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 m 0 N 1 f m h ( ( n − m ) ) 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 .