Saltar al contenido principal
LibreTexts Español

7.5: Convolución Circular de Tiempo Discreto y el DTFS

  • Page ID
    86500
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Introducción

    Este módulo relaciona la convolución circular de señales periódicas en un dominio con la multiplicación en el otro dominio.

    Debe estar familiarizado con Convolución de Tiempo Discreto (Sección 4.3), que nos dice que dadas dos señales de tiempo discreto\(x[n]\), la entrada del sistema y\(h[n]\), la respuesta del sistema, definimos la salida del sistema como

    \ [\ begin {align}
    y [n] &=x [n] * h [n]\ nonumber\\
    &=\ sum_ {k=-\ infty} ^ {\ infty} x [k] h [n-k]
    \ end {align}\ nonumber\]

    Cuando se nos dan dos DFT (secuencias de longitud finita generalmente de longitud\(N\)), no podemos simplemente multiplicarlas juntas como lo hacemos en la fórmula de convolución anterior, a menudo denominada convolución lineal. Debido a que los DFT son periódicos, tienen valores distintos de cero para\(n≥N\) y así la multiplicación de estos dos DFT será distinta de cero para\(n≥N\). Necesitamos definir un nuevo tipo de operación de convolución que resulte en que nuestra señal convolutiva sea cero fuera del rango\(n={0,1,…,N−1}\). Esta idea condujo al desarrollo de convolución circular, también llamada convolución cíclica o periódica.

    Convolución Circular de Señal

    Dada una señal\(f[n]\) con coeficientes de Fourier\(c_k\) y una señal\(g[n]\) con coeficientes de Fourier\(d_k\), podemos definir una nueva señal,\(v[n]\), donde\(v[n]=f[n] \circledast g[n]\). Encontramos que la representación de la Serie de Fourier de\(v[n]\)\(a_k\),, es tal que\(a_k=c_kd_k\). \(f[n] \circledast g[n]\)es la convolución circular (Sección 7.5) de dos señales periódicas y es equivalente a la convolución en un intervalo, i.e\(\displaystyle{f[n] \circledast g[n] = \sum_{n=0}^{N} \sum_{\eta=0}^{N} f[\eta] g[n-\eta]}\).

    Nota

    La convolución circular en el dominio del tiempo es equivalente a la multiplicación de los coeficientes de Fourier.

    Esto se demuestra de la siguiente manera

    \ [\ begin {align}
    a_ {k} &=\ frac {1} {N}\ suma_ {n=0} ^ {N} v [n] e^ {-\ izquierda (j\ omega_ {0} k n\ derecha)}\ nonumber\\
    &=\ frac {1} {N^ {2}}\ sum_ {n=0} ^ {N}\ sum_ {n=0} ^ {\ eta} f [\ eta] g [n-\ eta] e^ {-\ izquierda (j\ omega_ {0} k n\ derecha)}\ nonumber\\
    &=\ frac {1} {N}\ suma_ {\ eta=0} ^ {N} f [\ eta]\ izquierda (\ frac {1} {N}\ suma_ {n=0} ^ {N} g [n-\ eta] e^ {-\ izquierda (j\ omega_ {0} k n\ derecha)}\ derecha)\ nonumber\\
    &=\ izquierda (\ frac {1} {N}\ suma_ {\ eta=0} ^ {N} f [eta\]\ izquierda (\ frac {1} {N}\ sum_ {\ nu=-\ eta} ^ {N-\ eta} g [\ nu] e^ {-\ izquierda (j\ omega_ {0} (\ nu+\ eta)\ derecha)}\ derecha)\ derecha)\ quad,\ quad\ nu = n -\ eta\ nonumber\\
    &=\ frac {1} {N}\ suma_ {\ eta=0} ^ {N} f [\ eta]\ izquierda (\ frac {1} {N}\ suma_ {\ nu=-\ eta} ^ {N-\ eta} g [\ nu] e^ {-\ izquierda (j\ omega_ {0} k\ nu\ derecha)}\ derecha) e^ - {\ izquierda (j\ omega_ {0} k\ eta\ derecha)}\ nonumber\\
    &=\ frac {1} {N}\ suma_ {\ eta=0} ^ {N} f [\ eta] d_ {k} e^ {-\ izquierda (j\ omega_ {0} k\ eta\ derecha)}\ nonumber\\
    &=d_ {k}\ izquierda (\ frac {1} {N}\ suma_ {\ eta=0} ^ {N} f [\ eta] e^ {-\ izquierda (j\ omega_ {0} k\ eta\ derecha)}\ derecha)\ nonumber\\
    &=c_ {k} d_ {k}
    \ end {align}\ nonumber\ er\]

    Fórmula de convolución circular

    ¿Qué sucede cuando multiplicamos dos DFT juntos, de dónde\(Y[k]\) está el DFT\(y[n]\)?

    \[ Y[k] = F[k]H[k] \nonumber \]

    cuando\(0≤k≤N−1\)

    Uso de la fórmula de síntesis DFT para\(y[n]\)

    \[y[n]=\frac{1}{N} \sum_{k=0}^{N-1} F[k] H[k] e^{j \frac{2 \pi}{N} k n} \nonumber \]

    Y luego aplicando la fórmula de análisis\(F[k]=\sum_{m=0}^{N-1} f[m] e^{(-j) \frac{2 \pi}{N} k n}\)

    \ [\ begin {align}
    y [n] &=\ frac {1} {N}\ suma_ {k=0} ^ {N-1}\ suma_ {m=0} ^ {N-1} f [m] e^ {(-j)\ frac {2\ pi} {N} k n} H [k] e^ {j\ frac {2\ pi} {N k}}\ nonumber\\
    &=\ suma_ {m=0} ^ {N-1} f [m]\ izquierda (\ frac {1} {N}\ suma_ {k=0} ^ {N-1} H [k] e^ {j\ frac {2\ pi} {N} k (n-m)}\ derecha)
    \ end {align}\ nonumber\]

    donde podemos reducir la segunda suma que se encuentra en la ecuación anterior en la\(h\left[((n-m))_{N}\right]=\frac{1}{N} \sum_{k=0}^{N-1} H[k] e^{j \frac{2 \pi}{N} k(n-m)} y[n]=\sum_{m=0}^{N-1} f[m] h\left[((n-m))_{N}\right]\) que equivale a convolución circular! Cuando tenemos\(0≤n≤N−1\) en lo anterior, entonces obtenemos:

    \[y[n] \equiv f[n] \circledast h[n] \nonumber \]

    Nota

    La notación\(\circledast\) representa la convolución cíclica “mod N”.

    Fórmula de convolución alternativa

    Algoritmo de convolución circular alternativo

    • Paso 1: Calcular el DFT de los\(f[n]\) cuales rinde\(F[k]\) y calcular el DFT de los\(h[n]\) cuales rendimientos\(H[k]\).
    • Paso 2: Multiplicar puntualmente\(Y[k]=F[k]H[k]\)
    • Paso 3: DFT inverso\(Y[k]\) que rinde\(y[n]\)

    Parece una forma rotonda de hacer las cosas, pero resulta que hay formas extremadamente rápidas de calcular el DFT de una secuencia.

    Para convolucionar circularmente secuencias\(N\) de 2 puntos:\(y[n]=\sum_{m=0}^{N-1} f[m] h\left[((n-m))_{N}\right]\). Para cada uno\(n\):\(N\) múltiplos,\(N−1\) adiciones.

    \(N\)puntos implica\(N^2\) multiplicaciones,\(N(N−1)\) adiciones implica\(O(N^2)\) complejidad.

    Pasos para Convolución Circular

    Podemos imaginar secuencias periódicas (Sección 6.1) como que tienen puntos discretos en un círculo como dominio

    Figura\(\PageIndex{1}\)

    Cambiar por\(m\),\(f(n+m)\), corresponde a girar las\(m\) muescas del cilindro ACW (en sentido contrario a las agujas del reloj). Para\(m=−2\), obtenemos un turno igual al de la siguiente ilustración:

    Figura\(\PageIndex{2}\): para\(m=−2\)

    Figura\(\PageIndex{3}\)

    Para el desplazamiento cíclico seguimos estos pasos:

    1) Escribir\(f(n)\) en un cilindro, ACW

    Figura\(\PageIndex{4}\):\(N=8\)

    2) Para desplazamiento cíclico por\(m\), cilindro de giro m puntos ACW

    \[f[n] \rightarrow f\left[((n+m))_{N}\right] \nonumber \]

    Figura\(\PageIndex{5}\):\(m=−3\)

    Notas sobre el desplazamiento circular

    \(f[((n+N))_N]=f[n]\)Girar\(N\) puntos es lo mismo que girar todo el camino, o no girar en absoluto.

    \(f[((n+N))_N]=f[((n−(N−m)))_N]\)Cambio ACW mm es equivalente a cambio CW\(N−m\)

    Figura\(\PageIndex{6}\)

    \(f[((−n))_N]\)La expresión anterior, simplemente escribe los valores de las\(f[n]\) agujas del reloj.

    (a)\(f[n]\)

    b)\(f[((−n))_N]\)

    Figura\(\PageIndex{7}\)

    Ejemplo\(\PageIndex{1}\)

    Convolución (n = 4)

    (a)
    b)
    Figura\(\PageIndex{8}\): Dos señales de tiempo discreto a convolucionar.
    • \(h[((−(m()()_N]\)

    Figura\(\PageIndex{9}\)

    Multiplicar\(f[m]\) y sumar para rendir:\(y[0]=3\)

    • \(h[((1(−(m()()_N]\)

    Figura\(\PageIndex{10}\)

    Multiplicar\(f[m]\) y sumar para rendir:\(y[1]=5\)

    • \(h[((2(−(m()()_N]\)

    Figura\(\PageIndex{11}\)

    Multiplicar\(f[m]\) y sumar para rendir:\(y[2]=3\)

    • \(h[((3(−(m()()_N]\)

    Figura\(\PageIndex{12}\)

    Multiplicar\(f[m]\) y sumar para rendir:\(y[3]=1\)

    Ejercicio

    Echa un vistazo a un pulso cuadrado con un periodo de\(T\).

    Para esta señal\ (c_ {k} =\ left\ {\ begin {array} {l}
    \ frac {1} {N}\ text {if} k=0\\
    \ frac {1} {2}\ frac {\ sin\ left (\ frac {\ pi} {2} k\ right)} {\ frac {\ pi} {2} k}\ text {de lo contrario}
    \ end {array}\ right.\)

    Echa un vistazo a un tren de pulsos triangular con un periodo de\(T\).

    Esta señal se crea convolucionando circularmente el pulso cuadrado consigo mismo. Los coeficientes de Fourier para esta señal son\(a_{k}=c_{k}^{2}=\frac{1}{4} \frac{\sin ^{2}}{\left(\frac{x}{2} k\right)}\)

    Ejercicio\(\PageIndex{1}\)

    Encuentra los coeficientes de Fourier de la señal que se crea cuando se convoluciona el pulso cuadrado y el pulso triangular.

    Contestar

    \ (a_ {k} =\ left\ {\ begin {array} {ll}
    \ text {undefined} & k=0\\
    \ frac {1} {8}\ frac {\ sin ^ {3}\ izquierda [\ frac {\ pi} {2} k\ derecha]} {\ izquierda [\ frac {\ pi} {2} k\ derecha] ^ {3}} &\ texto {de lo contrario}
    \ end {array}\ derecho.\)

    Desplazamientos circulares y el DFT

    Teorema\(\PageIndex{1}\): Circular Shifts and DFT

    Si\(f[n] \stackrel{\mathrm{DFT}}{\longleftrightarrow} F[k]\) entonces\(f\left[((n-m))_{N}\right] \stackrel{\mathrm{DFT}}{\longleftrightarrow} e^{-\left(j \frac{2 \pi}{N} k m\right)} F[k]\) (es decir, desplazamiento circular en el dominio del tiempo = desplazamiento de fase en DFT)

    Prueba

    \[ f[n]=\frac{1}{N} \sum_{k=0}^{N-1} F[k] e^{j \frac{2 \pi}{N} k n} \nonumber \]

    por lo que el desplazamiento de fase del DFT

    \ begin {align}
    f [n] &=\ frac {1} {N}\ suma_ {k=0} ^ {N-1} F [k] e^ {-\ left (j\ frac {2\ pi} {N} k n\ derecha)} e^ {j\ frac {2\ pi} {N} k n}\ nonumber\\
    &=\ frac {1} {N}\ suma_ {k=0} ^ {N-1} F [k] e^ {j\ frac {2\ pi} {N} k (n-m)}\ nonumber\\
    &=f\ izquierda [((n-m)) _ {N}\ derecha]
    \ fin {align}

    Demostración de convolución circular

    CircularShiftsDemo
    Figura\(\PageIndex{13}\): Interactuar (cuando esté en línea) con un CDF de Mathematica demostrando Cambios Circulares.

    Conclusión

    La convolución circular en el dominio del tiempo es equivalente a la multiplicación de los coeficientes de Fourier en el dominio de la frecuencia.


    This page titled 7.5: Convolución Circular de Tiempo Discreto y el DTFS is shared under a CC BY license and was authored, remixed, and/or curated by Richard Baraniuk et al..