Skip to content Skip to navigation

Connexions

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

Navigation

Content Actions
  • Download module PDF
  • Add to ...
    Add the module to:
    • My Favorites
    • A lens
    • An external social bookmarking service
    • My Favorites (What is 'My Favorites'?)
      'My Favorites' is a special kind of lens which you can use to bookmark modules and collections directly in Connexions. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need a Connexions account to use 'My Favorites'.
    • A lens (What is a lens?)

      Definition of 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.

      What are tags? tag icon

      Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

    • External bookmarks
  • E-mail the author
  • Rate this module (How does the rating system work?)

    Rating system

    Ratings

    Ratings allow you to judge the quality of modules. If other users have ranked the module then its average rating is displayed below. Ratings are calculated on a scale from one star (Poor) to five stars (Excellent).

    How to rate a module

    Hover over the star that corresponds to the rating you wish to assign. Click on the star to add your rating. Your rating should be based on the quality of the content. You must have an account and be logged in to rate content.

    		(0 ratings)

Lenses

What is a lens?

Definition of 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.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

Affiliated with (What does "Affiliated with" mean?)

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.
  • Featured Content display tagshide tags

    This module is included inLens: Connexions Featured Content
    By: ConnexionsAs a part of collection:"Señales y Sistemas"

    Comments:

    "Señales y Sistemas is a Spanish translation of Dr. Rich Baraniuk's collection Signals and Systems (col10064). The translation was coordinated by an an assistant electrical engineering professor […]"

    Click the "Featured Content" link to see all content affiliated with them.

    Click the tag icon tag icon to display tags associated with this content.

Recently Viewed

This feature requires Javascript to be enabled.

Tags

(What is a tag?)

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 by Justin Romberg

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

Note: Your browser may not currently support MathML. See our browser support page for additional details. You can always view the correct math in the PDF version.

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
Figura 1: Step 1
(a) (b)
Figura 1(a) (cconv_s1.png)Figura 1(b) (cconv_s2.png)
  • 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).
Figura 2: Step 2
Figura 2 (cconv_s3.png)
  • 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)

Figura 3: Dos señales discretas que seran convolucionadas.
(a) (b)
Figura 3(a) (cconv_p1.png)Figura 3(b) (cconv_p2.png)

  • h ( ( − m ) ) N h ( ( − m ) ) N

Figura 4
Figura 4 (cconv_p3.png)

Multiplique fm f m y sume sume para dar: y0=3 y 0 3

  • h ( ( 1 − m ) ) N h ( ( 1 − m ) ) N

Figura 5
Figura 5 (cconv_p4.png)

Multiplique fm f m y sume sume para dar: y1=5 y 1 5

  • h ( ( 2 − m ) ) N h ( ( 2 − m ) ) N

Figura 6
Figura 6 (cconv_p5.png)

Multiplique fm f m y sume sume para dar: y2=3 y 2 3

  • h ( ( 3 − m ) ) N h ( ( 3 − m ) ) N

Figura 7
Figura 7 (cconv_p6.png)

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