Por que a convolução circular é usada no DSP? Por que não convolução linear?
On Novembro 29, 2020 by admin-
Por que estamos usando a convolução circular no DSP?
-
Qual é a principal razão sólida para o uso dele no processamento digital?
-
Por que o conceito de circular a convolução vem com mais frequência do que a convolução linear?
Comentários
- você notará que todas as suas respostas incluem uma menção da Transformada Discreta de Fourier, que é implementada de forma mais eficiente com a FFT. A DFT estende de forma inerente e periódica as sequências de comprimento finito passadas a ela (que é circular). A convolução circular raramente é o objetivo . geralmente a convolução linear é a meta, mas ao multiplicar o DFT ‘ s $ X [k] $ e $ H [k] $ juntos, isso corresponde à convolução circular das duas sequências estendidas periodicamente, $ x [n] $ e $ h [n] $ passadas para os DFTs. o problema é, de alguma forma, transformar isso em uma convolução linear.
Resposta
Dado um sistema LTI de tempo discreto com resposta ao impulso $ h [n] $ , pode-se calcular sua resposta a qualquer entrada $ x [n] $ por um convolução soma: $$ y [n] = x [n] \ star h [n] = \ sum_ {k = – \ infty} ^ {\ infty} {h [k] x [nk]} \ tag {1} $$
Sem nada mais declarado, a definição acima é para a convolução linear (convolução aperiódica) entre $ h [n] $ e $ x [n] $ , que são sequências de tempo discreto aperiódicas de comprimento possivelmente infinito, a menos que indicado de outra forma. Isso é diferente de uma convolução circular que está entre duas sequências periódicas de período $ N $ e calculado em um único período.
Você pode calcular um linear convolução no domínio do tempo pela Eq.1 ou no domínio da frequência usando a seguinte propriedade DTFT (transformação de Fourier de tempo discreto): $$ y [n] = x [n] \ star h [n] \ implica Y (e ^ {j \ omega}) = X (e ^ {j \ omega}) H (e ^ {j \ omega}) \ tag {2} $$
O DTFT está naturalmente relacionado com a convolução linear, pois lida com sequências aperiódicas teoricamente existentes que podem se estender de $ – \ infty $ a $ \ infty $ refletido em seus limites da soma definidora: $$ X (e ^ {j \ omega}) = \ sum_ {n = – \ infty} ^ {\ infty} x [n] e ^ {- j \ omega n} \ tag {3} $$
Quando você quiser fazer um cálculo manualmente, usando expressões simbólicas para sinais, como $ x [n] = a ^ nu [n] $ e $ h [n] = b ^ nu [n] $ , você pode calcular os resultados em domínios de tempo ou frequência conforme descrito acima.
Além disso, quando você deseja calcular o mesmo resultado usando um computador, você pode usar a abordagem de domínio do tempo com base em uma recursão LCCDE (para sistemas IIR) ou soma de convolução finita direta (para sistemas FIR), MAS a abordagem do domínio da frequência não funcionará com DTFT; pois é principalmente uma ferramenta usada para desenvolver a matemática dos sinais & teoria dos sistemas e não é adequada para computador digital implementações, pois sua variável $ \ omega $ é um real contínuo número.
O que é usado em vez disso é DFT (transformação discreta de Fourier) definida como $$ X [k] = X (e ^ {j \ omega}) | _ {\ omega = \ frac {2 \ pi k} {N}} \ tag {4} $$
onde $ k = 0,1, …, N-1 $ e $ N $ é o comprimento do DFT, que” é então chamado de ponto N DFT do sinal $ x [n] $ .
Eq.4 implica que a sequência DFT $ X [k] $ é obtida como as amostras uniformes da DTFT $ X (e ^ {j \ omega}) $ , que é uma função periódica, portanto, DFT $ X [k] $ é também periódico, mas consideramos apenas seu primeiro período de $ k = 0 $ a $ N-1 $ .
Como as sequências DFT são inerentemente periódicas, suas convoluções também serão periódicas (circulares).Portanto, enquanto uma linear convolução entre sinais aperiódicos $ x [n] $ e $ y [n] $ está implícito na expressão I-DTFT $$ y [n] = \ mathcal {I-DTFT} \ {X (e ^ {j \ omega}) H (e ^ {j \ omega}) \} $$ em vez de convolução circular entre duas sequências periódicas está implícita na expressão I-DFT $$ \ tilde {y} [n] = \ mathcal { I-DFT} \ {X [k] H [k] \} $$
Então, dado que queremos calcular uma convolução linear entre duas sequências aperiódicas $ x [n] $ e $ h [n] $ de comprimentos $ L_x $ e $ L_h $ respectivamente, usando o domínio de frequência por seus $ N $ pontos DFTs, $ X [k] $ e $ H [k] $ , na verdade temos que calcular uma convolução circular entre as extensões periódicas dos sinais $ \ tilde {x} [n] $ e $ \ tilde {h} [n] $ de períodos $ N $ .
A chave está em escolher um comprimento adequado $ N $ dos DFTs, que deve ser longo o suficiente para evitar qualquer domínio de tempo aliasing da sequência $ \ tilde {y} [n] $ , retornado pelo cálculo IDFT: $$ \ tilde {y} [n] = \ sum_ {r = – \ infty} ^ {\ infty} y [n-rN] \ tag {5 } $$
onde $ y [n] $ é o resultado da convolução linear que seria retornada pelo inverso teórico DTFT e $ \ tilde {y} [n] $ é o resultado periódico da convolução periódica (circular) implícita pela DFT inversa.
Observe que se qualquer um dos sinais tiver comprimento infinito, então “s NÃO é possível para calcular sua convolução linear usando a abordagem DFT, já que $ N $ iria ao infinito, praticamente impossível. A implementação de uma convolução linear via DFT tem as seguintes etapas:
-
Escolha N de acordo com os seguintes critérios: $$ N \ geq L_x + L_h -1 $$ que garante uma reconstrução sem alias do sinal inverso $ y [n] $ de seu DFT $ Y [k] $ da convolução circular calculada via $ X [k] H [k] $ .
-
Calcule DFTs de N pontos $ X [k] $ e $ H [k] $ de $ x [n] $ e $ h [n] $ .
-
Calcule $ Y [k] = X [k ] H [k] $
-
Calcule DFT inverso de N pontos de $ Y [k] $ para produzir a saída $ y [n] $
Resposta
Respondendo às suas perguntas:
- Por que estamos usando a convolução circular no DSP?
No DSP, normalmente lidamos com sequências discretas de comprimento finito (mesmo se o sinal em estudo for infinito, só podemos analisar uma parte finita dele por vez ) Quando se trata de processar um sinal, a forma de processá-lo deve ser implementável em um dispositivo lógico discreto (ou seja, um dispositivo que não pode armazenar valores contínuos porque esses valores são infinitos e tem uma quantidade finita de memória, armazenamento, etc). Isso explica porque a Transformada de Fourier de Tempo Discreto (DTFT), que transforma uma sequência de tempo discreta em uma sequência de frequência contínua, não pode ser implementada no hardware. A convolução linear no tempo é equivalente à multiplicação de 2 sequências DTFTs, mas como a DTFT não pode “ser implementada em hardware, esta não é a maneira de obter a convolução linear. Transformada discreta de Fourier (DFT), por outro lado, transforma uma sequência de tempo discreta em uma sequência de frequência discreta e esta permite que seja implementada em No entanto, a multiplicação de 2 sequências DFTs é equivalente à convolução circular em princípio (convolução linear também pode ser obtida se as sequências de tempo forem previamente preenchidas com zeros suficientes, consulte a explicação abaixo).A razão pela qual multiplicar 2 sequências DFTs é equivalente à convolução circular e não linear vem do fato de que DFT para uma sequência de comprimento de tempo finito é equivalente à Série Discreta de Fourier (DFS) dessa mesma sequência de comprimento de tempo finito periodicamente estendida (concatenando o seqüência de comprimento de tempo finito infinitamente no eixo do tempo) tomada ao longo de um período. O DFS também é periódico no domínio da frequência, portanto a convolução linear não se aplica lá (ver 8.2.5 e 8.6.5 do Processamento de Sinal de Tempo Discreto de Oppenheim 3ª edição)
- Qual é a principal razão sólida para seu uso no processamento digital?
É obtido por multiplicação DFT e o DFT é facilmente implementado no hardware. Além disso, algoritmos muito eficientes, como FFT, existem para calcular o DFT
- Por que o conceito de convolução circular surge com mais frequência do que convolução linear?
Isso depende da aplicação. A convolução circular também pode produzir a convolução linear. Por exemplo, digamos estamos trabalhando com o sinal A de comprimento N e o sinal B também de comprimento N (também pode ser feito para comprimentos diferentes). A convolução circular terá comprimento N. Para obter a convolução linear, A e B devem ser preenchidos com zeros até atingirem um comprimento de pelo menos 2 * N – 1. Em seguida, aplicar o DFT em ambos, multiplicando-os e aplicando o inverso O DFT lhe dará a convolução linear
Resposta
Aqui “um pouco de intuição:
Quando você lidar com sinais digitalmente, você está sempre lidando com um sinal finito. Isso ocorre porque você só pode processar uma quantidade finita de pontos de dados.
O problema, entretanto, é que quando você realiza transformações no domínio da frequência usando o DFT, por definição um sinal não pode ser finito. Portanto, ao fazer uma operação DFT, há uma alteração implícita no seu sinal de finito para periódico, mesmo que seu sinal não seja periódico.
Isso a periodicidade do sinal leva à necessidade de usar a convolução de maneira circular.
Resposta
O DFT / FFT é um “martelo” computacional útil, mas todos os seus vetores de base de transformação são circulares (periódicos inteiros) na abertura e podem ser infinitamente estendidos como funções periódicas, que alguns usuários confundem com a natureza de seus dados de entrada.
Se você zerar por uma quantidade suficiente, a convolução circular produz o mesmo resultado que a convolução linear, mas com um custo computacional ligeiramente maior do que a circular.
Deixe uma resposta