linear n circular convolution relation

Started by romio June 17, 2008
I have the knowledge of fourier transform of the circular convoluion of two
vectors say h and s, ie i know FFT (s ** h) [saying ** stands for circular
convolution].
I want to know FFT of linear convolution of s and h ie my target is to
calculate FFT(s*h) [where * is the linear convolution].

I neither know s nor h.

Is it possible and if yes then how?


Linear convolution can be performed using the DFT (FFT) by simply zero-
padding the input sequences, s and h.  If s has length N1 and h has
length N2, you can append zeros to each sequence in order to make them
both of length (N1 + N2 - 1).  In other words, append N2-1 zeros to s
and N1-1 zeros to h.  With the zeros, circular convolution gives the
same result as linear convolution, that is:   s*h =
IFFT(FFT(s')FFT(h')) where s' and h' are the zero padded sequences.

-Jason
romio wrote:
> I have the knowledge of fourier transform of the circular convoluion of two > vectors say h and s, ie i know FFT (s ** h) [saying ** stands for circular > convolution]. > I want to know FFT of linear convolution of s and h ie my target is to > calculate FFT(s*h) [where * is the linear convolution]. > > I neither know s nor h. > > Is it possible and if yes then how?
It's not possible to derive linear from circular convolution (the other way round, however, is possible). You'll see why if you write out s * h and s ** h in components for the simple case where s = (s1,s2) and h = (h1,h2). Regards, Andor
>I want to know FFT of linear convolution of s and h ie my target is to >calculate FFT(s*h) [where * is the linear convolution]. > >I neither know s nor h. > >Is it possible and if yes then how?
Without knowing s and h you can not calculate s*h, or its Fourier transform, unless you have some other specifying information. Your question is like saying "Can I make an omelette without eggs?" Emre
emre wrote:
>> I want to know FFT of linear convolution of s and h ie my target is to >> calculate FFT(s*h) [where * is the linear convolution]. >> >> I neither know s nor h. >> >> Is it possible and if yes then how? > > Without knowing s and h you can not calculate s*h, or its Fourier > transform, unless you have some other specifying information. Your > question is like saying "Can I make an omelette without eggs?"
Not eggzactly. It's more like asking if scrambled eggs can be converted to sunny side up. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
>>> I neither know s nor h.
>> Without knowing s and h you can not calculate s*h, or its Fourier >> transform, unless you have some other specifying information. Your >> question is like saying "Can I make an omelette without eggs?"
>Not eggzactly. It's more like asking if scrambled eggs can be converted >to sunny side up. > >Jerry
Good one, Jerry. But you know that the point of my eggzample was that the OP has no eggs to start with, whether scrambled or not. :-) Emre
>I have the knowledge of fourier transform of the circular convoluion of
two
>vectors say h and s, ie i know FFT (s ** h) [saying ** stands for
circular
>convolution].
Oh, I misunderstood the first line. The OP does have the necessary information. Sorry if I eggzaggerated. :-) Emre