9

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

Jav_Rock
  • 1,213
  • 2
  • 14
  • 24
saleh khalaf
  • 91
  • 1
  • 2

2 Answers2

8

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

Dilip Sarwate
  • 20,349
  • 4
  • 48
  • 94
  • 1
    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)))) – pichenettes Feb 10 '12 at 13:43
  • 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. – Dilip Sarwate Feb 10 '12 at 14:16
  • yes, doing the circular convolution with ifft(fft( ) .* conj(fft( ) )) is useful only for a larger N. – pichenettes Feb 10 '12 at 14:33
  • 1
    @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. – Dilip Sarwate Feb 10 '12 at 17:46
5

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

pichenettes
  • 19,413
  • 1
  • 50
  • 69