Convolução circular MOD-N

7

Como encontrar a convolução circular MOD-2 para as duas seqüências e .h=[−1,3,−2,1]x=[1,−1,−2,1,3,2,1,2]

Eu sei que a resposta é 0 do matlab, mas não sei como encontrá-la gráfica ou matematicamente7 0

discrete-signals convolution saleh khalaf
fonte

Respostas:

6

Escreva h(z)=−1+3z−2z2+z3 e calcule h (z) \ bmod (z ^ 2-1 )h(z)mod(z2−1) , ou seja, divida h(z) por z2−1 e tome apenas o restante. Embora isso pareça muito complicado, se você pensar um pouco, verá que tudo o que você está fazendo é dividir [−13 −21] em [−13] e [−21] e adicionando os vetores mais curtos para obter [−34] . Repita para x=[1 −1 −213212] para adicionar quatro vetores de comprimento 2 para obter [34]. Presumivelmente, isso não é muito difícil de fazer no MATLAB, embora eu não esteja familiarizado o suficiente com a sintaxe para sugerir comandos específicos. Em seguida, calcule a convolução cíclica de [−34] e [34] preferência sem chamar as funções MATLAB. O resultado é

[{(−3)×3+4×4}{(−3)×4+4×3}]=[70]

Matematicamente, o que você está fazendo é computar que pode ser feito de maneira fantástica ao encontrar primeiro usando FFTs e o que você seguiu. (isso efetivamente divide o vetor longo em pedaços curtos e os adiciona), ou mais simplesmente computando primeiro e (dividindo em vetores mais curtos e adicionando-os) e calculando a convolução cíclica que é fácil de fazer.h(z)x(z)mod(z2−1)h(z)x(z)mod(z2−1)h^(z)=h(z)mod(z2−1)x^(z)=x(z)mod(z2−1)z^(z)x^(z)mod(z2−1)

Chop-add-convolve é mais fácil do que convolve-chop-add

Dilip Sarwate
fonte
11
O Matlab para "chop add convolve" seria: ifft (fft (sum (remodelar (x, 2, comprimento (x) / 2), 2), 2))). * Conj (fft (sum (remodelar (h, 2, comprimento (h ) / 2), 2))))
pichenettes
Obrigado por sugerir o código chop-add, mas não concordo com o ifft (parte fft. A convolução cíclica de dois vetores de comprimento deve ser calculada diretamente sem chamar ffts e similares. Begin dificilmente precisa do mecanismo formal de ffts e iffts. O módulo para valores maiores de é uma questão diferente; para o módulo , é um exagero.2
(a+bz)(c+dz)mod(z2−1)=(ac+(ad+bc)z+bdz2)mod(z2−1)=(ac+bd)+(ad+bc)z
NN2
Dilip Sarwate
sim, fazendo a convolução circular com IFFT (fft () * fft conj (()).) é útil apenas para uma maior N.
pichenettes
11
@pichenettes A abordagem fft calcula (fft), multiplica e encontra a convolução resultado como , usando duas barras, duas escalas, seis adições, enquanto o cálculo direto precisa de quatro barras e duas adições. Se codificado diretamente, é quase um empate, mas acho que o método direto tem uma ligeira vantagem. Se as despesas gerais das chamadas de sub-rotina do MATLAB forem levadas em consideração, o método direto será mais rápido. Mas é claro, tudo isso é uma comparação de amendoins no tempo de computação em comparação com qualquer outra coisa que está sendo feita. a+b,a−b,c+d,c−de=(a+b)(c+d),f=(a−b)(c−d)(e+f)/2(e−f)/2ac+bd,ad+bc
Dilip Sarwate
3

Uma abordagem é "embrulhar" uma convolução circular em tamanho real:

sum(reshape(ifft(fft(x, 8) .* conj(fft(h, 8))), 2, 8 / 2), 2)

Outra implementação é dizimar diretamente a FFT:

N = 2;
Xf = fft(x); Xf = Xf(1:length(Xf) / N:end);
Hf = fft(h); Hf = Hf(1:length(Hf) / N:end);
ifft(Xf .* conj(Hf))

Se o que você deseja reproduzir é o comportamento do cconv do matlab, talvez seja melhor apenas olhar para o código-fonte nos arquivos matlab :)

pichenettes
fonte