How to find MOD-2 Circular convolution for the two sequences $h =[-1,3,-2,1]$ and $x = [1,-1,-2,1,3,2,1,2]$.
I know the answer is $7$ $0$ from matlab but I don't know how to find it graphicly or mathematically
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
Write $h(z) = -1 + 3z -2z^2 + z^3$ and compute $h(z) \bmod (z^2 - 1)$, that is, divide $h(z)$ by $z^2 - 1$ and take just the remainder. While this looks very complicated, if you think about it a bit you will see that all you are doing is dividing $[-1\quad3\ -2\quad 1]$ into $[-1\quad 3]$ and $[-2\quad 1]$ and adding the shorter vectors to get $[-3\quad 4]$. Repeat for $x = [1 \ -1\ -2\quad 1 \quad 3 \quad 2\quad 1 \quad 2]$ to add four vectors of length $2$ to get $[3\quad 4]$. This is presumably not too hard to do in MATLAB though I am not familiar enough with the syntax to suggest specific commands. Next, compute the cyclic convolution of $[-3\quad 4]$ and $[3\quad 4]$ preferably without invoking MATLAB functions. The result is $$[\{(-3)\times 3 + 4\times 4\}\quad \{(-3)\times 4 + 4 \times 3\}] = [7\quad 0]$$
Mathematically, what you are doing is computing $h(z)x(z) \bmod (z^2-1)$ which can be done fancily by first finding $h(z)x(z)$ using FFTs and what have you followed by the $\bmod (z^2-1)$ computation (this effectively chops up the long vector into short pieces and adds them), or more simply by first computing $\hat{h}(z) = h(z) \bmod (z^2-1)$ and $\hat{x}(z) = x(z) \bmod (z^2-1)$ (the chopping up into shorter vectors and adding them) and then computing the cyclic convolution $\hat{z}(z)\hat{x}(z) \bmod (z^2 - 1)$ which is easy to do.
Chop-add-convolve is easier than convolve-chop-add
answered Feb 10, 2012 at 13:22
-
1$\begingroup$ Matlab for "chop add convolve" would be: ifft(fft(sum(reshape(x, 2, length(x) / 2), 2)) .* conj(fft(sum(reshape(h, 2, length(h) / 2), 2)))) $\endgroup$ Commented Feb 10, 2012 at 13:43
-
$\begingroup$ Thanks for suggesting the chop-add code, but I disagree with the ifft(fft part. The cyclic convolution of two length-$2$ vectors should be computed directly without invoking ffts and the like. $$\begin{align*}(a+bz)(c+dz)\bmod(z^2-1)&=(ac+(ad+bc)z+bdz^2)\bmod (z^2-1)\\&=(ac+bd)+(ad+bc)z\end{align*}$$ hardly needs the formal mechanism of ffts and iffts. Modulo-$N$ for larger values of $N$ is a different matter; for Modulo-$2$, it is an overkill. $\endgroup$ Commented Feb 10, 2012 at 14:16
-
$\begingroup$ yes, doing the circular convolution with ifft(fft( ) .* conj(fft( ) )) is useful only for a larger N. $\endgroup$ Commented Feb 10, 2012 at 14:33
-
1$\begingroup$ @pichenettes The fft approach would compute $a+b,a-b, c+d,c-d$ (fft), multiply $e=(a+b)(c+d), f=(a-b)(c-d)$, and then find the convolution result as $(e+f)/2$, $(e-f)/2$ using two mults, two scalings, six adds, whereas the direct computation $ac+bd, ad+bc$ needs four mults and two adds. If coded directly, it is close to a toss-up but I think the direct method has a slight edge. If the overheads of MATLAB subroutine calls are taken into account, the direct method is faster. But of course, all this is a comparison of peanuts in computation time compared to anything else that is being done. $\endgroup$ Commented Feb 10, 2012 at 17:46
$\begingroup$
$\endgroup$
One approach is to "re-wrap" a full size circular convolution:
sum(reshape(ifft(fft(x, 8) .* conj(fft(h, 8))), 2, 8 / 2), 2)
Another implementation is to directly decimate the 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))
If what you want to reproduce is the behavior of cconv from matlab it might be best to just look at its source code in the matlab files :)
answered Feb 10, 2012 at 12:53