7
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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

$\endgroup$
  • 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$ – pichenettes Feb 10 '12 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$ – Dilip Sarwate Feb 10 '12 at 14:16
  • $\begingroup$ yes, doing the circular convolution with ifft(fft( ) .* conj(fft( ) )) is useful only for a larger N. $\endgroup$ – pichenettes Feb 10 '12 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$ – Dilip Sarwate Feb 10 '12 at 17:46
3
$\begingroup$

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 :)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.