¿Por qué se utiliza la convolución circular en DSP? ¿Por qué no convolución lineal?
On noviembre 29, 2020 by admin-
¿Por qué utilizamos la convolución circular en DSP?
-
¿Cuál es la principal razón sólida para su uso en el procesamiento digital?
-
¿Por qué el concepto de circular ¿la convolución es más frecuente que la convolución lineal?
Comentarios
- notarás que todas tus respuestas incluyen una mención de la Transformada de Fourier Discreta que se implementa de manera más eficiente con la FFT. La DFT extiende periódicamente de forma inherente las secuencias de longitud finita que se le pasan (que es circular). La convolución circular rara vez es el objetivo . Por lo general, la convolución lineal es el objetivo. pero al multiplicar el DFT ‘ s $ X [k] $ y $ H [k] $ juntos, eso corresponde a la convolución circular de las dos secuencias extendidas periódicamente, $ x [n] $ y $ h [n] $ pasaron a las DFT. El problema es entonces convertir esto en convolución lineal.
Respuesta
Dado un sistema LTI de tiempo discreto con respuesta de impulso $ h [n] $ , se puede calcular su respuesta a cualquier entrada $ x [n] $ mediante un convolución suma: $$ y [n] = x [n] \ star h [n] = \ sum_ {k = – \ infty} ^ {\ infty} {h [k] x [nk]} \ tag {1} $$
Sin más información, la definición anterior es para la convolución lineal (convolución aperiódica) entre $ h [n] $ y $ x [n] $ , que son secuencias de tiempo discreto aperiódicas de longitud posiblemente infinita, a menos que se indique lo contrario. Esto es diferente de una convolución circular que se encuentra entre dos secuencias periódicas de período $ N $ y se calcula en un solo período.
Puede calcular una convolución en el dominio del tiempo por la Ec. 1, o en el dominio de la frecuencia usando la siguiente propiedad DTFT (transformada de Fourier de tiempo discreto): $$ y [n] = x [n] \ star h [n] \ implica Y (e ^ {j \ omega}) = X (e ^ {j \ omega}) H (e ^ {j \ omega}) \ tag {2} $$
DTFT está naturalmente relacionado con la convolución lineal, ya que trata con secuencias aperiódicas teóricamente existentes que pueden extenderse desde $ – \ infty $ a $ \ infty $ reflejado en sus límites de la suma definitoria: $$ X (e ^ {j \ omega}) = \ sum_ {n = – \ infty} ^ {\ infty} x [n] e ^ {- j \ omega n} \ tag {3} $$
Cuando desee hacer un cálculo a mano, usando expresiones simbólicas para señales, como $ x [n] = a ^ nu [n] $ y $ h [n] = b ^ nu [n] $ , puede calcular los resultados en dominios de tiempo o frecuencia como se describe anteriormente.
Además, cuando desee calcular el mismo resultado mediante el uso de una computadora, puede utilizar el enfoque de dominio del tiempo basado en una recursividad LCCDE (para sistemas IIR) o suma de convolución finita directa (para sistemas FIR), PERO el enfoque del dominio de la frecuencia no funcionará con DTFT, ya que es principalmente una herramienta que se utiliza para desarrollar las matemáticas de la teoría de sistemas & de señales, y no es adecuada para computadoras digitales implementaciones, ya que su variable $ \ omega $ es una continua número.
Lo que se usa en su lugar es DFT (transformada discreta de Fourier) definida como $$ X [k] = X (e ^ {j \ omega}) | _ {\ omega = \ frac {2 \ pi k} {N}} \ tag {4} $$
donde $ k = 0,1, …, N-1 $ y $ N $ es la longitud de la DFT, que» luego se llama como N-point DFT de la señal $ x [n] $ .
La ecuación 4 implica que la secuencia DFT $ X [k] $ se obtiene como las muestras uniformes de la DTFT $ X (e ^ {j \ omega}) $ , que es una función periódica, por lo tanto, DFT $ X [k] $ es también es periódico, pero solo consideramos su primer período desde $ k = 0 $ a $ N-1 $ .
Dado que las secuencias DFT son inherentemente periódicas, sus convoluciones también serán periódicas (circulares).Por lo tanto, mientras que una convolución lineal entre señales aperiódicas $ x [n] $ y $ y [n] $ está implícito en la expresión I-DTFT $$ y [n] = \ mathcal {I-DTFT} \ {X (e ^ {j \ omega}) H (e ^ {j \ omega}) \} $$ en lugar de un La convolución circular entre dos secuencias periódicas está implícita en la expresión I-DFT $$ \ tilde {y} [n] = \ mathcal { I-DFT} \ {X [k] H [k] \} $$
Entonces, dado que queremos calcular una convolución lineal entre dos secuencias aperiódicas $ x [n] $ y $ h [n] $ de longitudes $ L_x $ y $ L_h $ respectivamente, utilizando el dominio de frecuencia por sus $ N $ puntos DFT, $ X [k] $ y $ H [k] $ , en realidad tenemos que calcular una convolución circular entre las extensiones periódicas de las señales $ \ tilde {x} [n] $ y $ \ tilde {h} [n] $ de períodos $ N $ .
La clave está en elegir una longitud adecuada $ N $ de las DFT, que debe ser lo suficientemente larga para evitar cualquier dominio de tiempo alias de la secuencia $ \ tilde {y} [n] $ , devuelto por el cálculo IDFT: $$ \ tilde {y} [n] = \ sum_ {r = – \ infty} ^ {\ infty} y [n-rN] \ tag {5 } $$
donde $ y [n] $ es el resultado de la convolución lineal que devolvería la inversa teórica DTFT y $ \ tilde {y} [n] $ es el resultado periódico de la convolución periódica (circular) implícita en la DFT inversa.
Tenga en cuenta que si alguna de las señales tiene una longitud infinita, entonces «es NO posible para calcular su convolución lineal utilizando el enfoque DFT, ya que $ N $ iría al infinito, prácticamente imposible. La implementación de una convolución lineal a través de DFT tiene los siguientes pasos:
-
Elija N de acuerdo con los siguientes criterios: $$ N \ geq L_x + L_h -1 $$ que garantiza una reconstrucción sin alias de la señal inversa $ y [n] $ de su DFT $ Y [k] $ de la convolución circular calculada a través de $ X [k] H [k] $ .
-
Calcule DFT de N puntos $ X [k] $ y $ H [k] $ de $ x [n] $ y $ h [n] $ .
-
Calcular $ Y [k] = X [k ] H [k] $
-
Calcule la DFT inversa de N puntos de $ Y [k] $ para producir la salida $ y [n] $
Respuesta
Respondiendo a sus preguntas:
- ¿Por qué utilizamos la convolución circular en DSP?
En DSP normalmente tratamos con secuencias discretas de longitud finita (incluso si la señal en estudio es infinita, solo podemos analizar una porción finita de ella a la vez ). Cuando se trata de procesar una señal, la forma de procesarla debe ser implementable en un dispositivo lógico discreto (es decir, un dispositivo que no puede almacenar valores continuos porque estos valores son infinitos y tiene una cantidad finita de memoria, almacenamiento, etc.). Esto explica por qué la Transformada de Fourier de Tiempo Discreto (DTFT), que transforma una secuencia de tiempo discreta en una secuencia de frecuencia continua, no se puede implementar en el hardware. La convolución lineal en el tiempo es equivalente a la multiplicación de 2 secuencias DTFT, pero como DTFT no se puede implementar en hardware, esta no es la forma de obtener la convolución lineal. La transformada discreta de Fourier (DFT), por otro lado, transforma una secuencia de tiempo discreta en una secuencia de frecuencia discreta y esto permite que se implemente en Sin embargo, multiplicar 2 secuencias DFT equivale en principio a una convolución circular (también se puede obtener una convolución lineal si las secuencias de tiempo se rellenan previamente con suficientes ceros, ver explicación a continuación).La razón por la que multiplicar 2 secuencias DFT es equivalente a una convolución circular y no lineal proviene del hecho de que DFT para una secuencia de tiempo finito es equivalente a la Serie de Fourier Discreta (DFS) de esa misma secuencia de tiempo finito periódicamente extendida (concatenando el secuencia de duración de tiempo finita infinitamente en el eje de tiempo) tomada durante un período. DFS también es periódico en el dominio de frecuencia, por lo que la convolución lineal no se aplica allí (consulte 8.2.5 y 8.6.5 de Oppenheim «s Discrete Time Signal Processing 3rd edition)
- ¿Cuál es la principal razón sólida para su uso en el procesamiento digital?
Se obtiene mediante la multiplicación de DFT y DFT se implementa fácilmente en hardware. Además, existen algoritmos muy eficientes como FFT para calcular la DFT
- ¿Por qué el concepto de convolución circular aparece con más frecuencia que ¿convolución lineal?
Eso depende de la aplicación. La convolución circular también puede producir la convolución lineal. Por ejemplo, digamos estamos trabajando con la señal A de longitud N y la señal B también de longitud N (también se puede hacer para diferentes longitudes). La circunvolución circular será de longitud N. Para obtener la convolución lineal tanto A como B deben rellenarse con ceros hasta que alcancen una longitud de al menos 2 * N – 1. Luego aplicando la DFT en ambas, multiplicándolas y aplicando la inversa. DFT le dará la convolución lineal
Respuesta
Aquí tiene un poco de intuición:
Cuando tratar con señales digitalmente, siempre se trata de una señal finita. Esto se debe a que solo puede procesar en una cantidad finita de puntos de datos.
Sin embargo, el problema es que cuando realiza transformaciones en el dominio de frecuencia utilizando la DFT, por definición, una señal no puede ser finita. Por lo tanto, cuando se hace una operación DFT, hay una alteración implícita en su señal de ser finita a periódica, incluso si su señal no es periódica.
Esto La periodicidad de la señal lleva a la necesidad de utilizar la convolución de manera circular.
Respuesta
La DFT / FFT es un «martillo» computacional útil, pero todos sus vectores de base de transformación son circulares (enteros periódicos) en apertura y pueden extenderse infinitamente como funciones periódicas, que algunos usuarios confunden con la naturaleza de sus datos de entrada.
Si realiza un pad-cero en una cantidad suficiente, la convolución circular produce el mismo resultado que la convolución lineal, pero a un costo computacional ligeramente mayor que la circular.
Deja una respuesta