Connexions

You are here: Home » Content » Convolución Circular y el DFT
Content Actions
Lenses

What is a lens?

Lenses

A lens is a custom view of Connexions content. You can think of it as a fancy kind of list that will let you see Connexions through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to Connexions materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual Connexions member, a community, or a respected organization.

This content is ...
Affiliated with (?)
This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.

  • This module is included inLens: Rice University OpenCourseWare
    By: OpenCourseWare ConsortiumAs a part of collection:"Señales y Sistemas"

    Click the "Rice University OCW" link to see all content affiliated with them.

    Rice University OCW
Tags

(?)

These tags come from the endorsement, affiliation, and other lenses that include this content.

Convolución Circular y el DFT

Module by: Justin Romberg Translated by: Fara Meza, Erika JacksonBased on: Circular Convolution and the DFT por Justin Romberg

Summary: Este modulo describe el elgoritmo de convolucion cicular y un algoritmo alterno

Introducción

Usted debería familiarizarse con la convolución discreta, que nos explica como dos señales discretas xn x n , la entrada del sistema, y hn h n , la respuesta del sistema, se puede definir el resultado del sistema como
yn=xn*hn=∑k=-∞∞xkhn-k y n x n h n k x k h n k (1)
Cuando dos DFT son dadas (secuencias de tamaño finito usualmente del tamaño NN), 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 n N así la multiplicación de estas dos señales será no cero para n≥N 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=01…N-1 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 Yk Y k es la DFT de yn y n ?
Yk=FkHk Y k F k H k (2)
cuando 0≤k≤N-1 0 k N 1
Usando la formula sintetizada de DFT para yn y n
yn=1N∑k=0N-1FkHkⅇj2πNkn y n 1 N k 0 N 1 F k H k j 2 N k n (3)
Y aplicando análisis a la formula Fk=∑m=0N-1fmⅇ-j2πNkn F k m 0 N 1 f m j 2 N k n
yn=1N∑k=0N-1∑m=0N-1fmⅇ-j2πNknHkⅇj2πNkn=∑m=0N-1fm1N∑k=0N-1Hkⅇj2πNkn-m 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 (4)
donde podemos reducir la segunda sumatoria de la ecuación de arriba en h ( ( n − m ) ) N =1N∑k=0N-1Hkⅇj2πNkn-m h ( ( n − m ) ) N 1 N k 0 N 1 H k j 2 N k n m yn=∑m=0N-1fmh ( ( n − m ) ) N y n m 0 N 1 f m h ( ( n − m ) ) N Igual a la convolución circular! cuando tenemos 0≤n≤N-1 0 n N 1 arriba , para obtener dos:
yn≡fn⊛hn y n ⊛ f n h n (5)
note: 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" fm f m y h ( ( − m ) ) N h ( ( − m ) ) N
cconv_s1.pngcconv_s2.png
Subfigure 1.1
Subfigure 1.2
Figura 1: Step 1
  • Paso 2: "Rote" h ( ( − m ) ) N h ( ( − m ) ) N n n en la dirección ACW ( dirección opuesta al reloj) para obtener h ( ( n − m ) ) N h ( ( n − m ) ) N (por ejemplo rote la secuencia, hn h n , en dirección del reloj por nn pasos).
cconv_s3.png
Figura 2: Step 2
  • Paso 3: Multiplique punto por punto la rueda fm f m y la rueda h ( ( n − m ) ) N h ( ( n − m ) ) N wheel. sum=yn sum y n
  • Paso 4: Repite para 0≤n≤N-1 0 n N 1
Ejemplo 1: Convolve (n = 4) 
cconv_p1.pngcconv_p2.png
Subfigure 3.1
Subfigure 3.2
Figura 3: Dos señales discretas que seran convolucionadas.
  • h ( ( − m ) ) N h ( ( − m ) ) N
cconv_p3.png
Figura 4
Multiplique fm f m y sume sume para dar: y0=3 y 0 3
  • h ( ( 1 − m ) ) N h ( ( 1 − m ) ) N
cconv_p4.png
Figura 5
Multiplique fm f m y sume sume para dar: y1=5 y 1 5
  • h ( ( 2 − m ) ) N h ( ( 2 − m ) ) N
cconv_p5.png
Figura 6
Multiplique fm f m y sume sume para dar: y2=3 y 2 3
  • h ( ( 3 − m ) ) N h ( ( 3 − m ) ) N
cconv_p6.png
Figura 7
Multiplique fm f m y sume sume para dar: y3=1 y 3 1
Ejemplo 2 
La Siguiente Demostración le permite este algoritmo. Vea aquí para instrucciones de como se usa este demo.
LabVIEW Example: (run) (source)

Algoritmo Alterno

    Algoritmo de Convolución Circular Alterno
  • Paso 1: Calcule el DFT de fn f n que da Fk F k y calcule el DFT de hn h n que da Hk H k .
  • Paso 2: Multiplique punto por punto Yk=FkHk Y k F k H k
  • Paso 3: Invierta el DFT Yk Y k que da yn 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 2 N N-puntos: yn=∑m=0N-1fmh ( ( n − m ) ) N y n m 0 N 1 f m h ( ( n − m ) ) N Para cualquier n n : N N múltiplos, N-1 N 1 sumas
N N puntos implica N2 N 2 multiplicaciones, NN-1 N N 1 sumas implica una complejidad de ON2 O N 2 .

Comments, questions, feedback, criticisms?

Send feedback