When I first learned Fourier Transformation in signal processing, I was told that the convolution of two signals in time domain (or spatial domain) was equivalent to the multiplication of those two signals in frequency domain. That was amazing, but I got no intuition about why it worked.
Then one day, it hit me that I had been doing convolution since I was a kid in elementary school. Every time we multiply two decimal numbers, we are not really performing the multiplication. We are actually computing the convolution of their digits. For example, the reason why we know 22*33 is 726 is because we compute the convolution of the two signals (2,2) and (3,3), which gives us the signal (6, 2, 7). (Note: I put the least significant digit to the left, so they look more like the signal in the “transformed” domain.)
Still didn’t get it? Then think about this. What is the meaning of the decimal number system that we have taken for granted? Imagine the world 5,000 years ago. How would a farmer count the number of plants in his land? For example, if he has 22 rows of plants, and 33 plants in each row, how does he count the total number of plants? Does he know the total is simply 22*33 if he doesn’t yet know the multiplication of two decimal numbers?
- 22 and 33 are the results of projection to the tens and the singles digits of the decimal system.
- 726 is the result of the convolution between (2,2) and (3,3).
Filed under: Technical Notes | Tagged: Intuition, Math |
Chun-Fa Chang's Home Page & Weblog 
I just had that realization myself. Said in other words, convolution is equivalent to multiplying the coefficients of polynomials.
(Over here in America)
How about 12 x 34, which we know is 408? We can represent that as (1,2) * (3,4). I’m getting (4,11,6). How do we get 408 from that? Did I do something wrong with my convolution?
You probably forgot to reverse one of the signals. This Wikipedia figure may help.
It is 408.
12 x 34
[1*3],[1*3 + 2*4] , [2*4]
3,11,8
3, [substract 10 and add remainder to 3] , [8]
4,0,8
See details here
https://ccrma.stanford.edu/~jos/mdft/Multiplication_Decimal_Numbers.html
Anil,
Thank you for the “Multiplication of Decimal Numbers” link. However, I think it should be applied this way:
12 x 34
=> [1*3],[1*4 + 2*3] , [2*4]
=> 3,10,8
=> 3, [subtract 10 and add carry to 3] , [8]
=> 4,0,8
Convolution is more “primitive” than multiplication
0D value = 1D binary
1D value = 2D binary
2D value = 3D binary
(A,B) = (a,b)
That the right way to think
Scalar product A x B
= 0D value x 0D value
= convolution( 1D binary , 1D binary)
= ifft(fft(a).*fft(b))
Convolution product on vector A x B
= 1D value x 1D value
= convolution( 2D binary , 2D binary)
= ifft2(fft2(a).*fft2(b))
Matrix product A x B
= 2D value x 2D value
= convolution( 3D binary , 3D binary)
= ifft3(fft3(a).*fft3(b))
…But…
Division A / B
= DE-convolution !! (since why so hard)
= ifft(fft(a)./fft(b)) can’t
= inverse circulant binary matrix –> not binary !