# linear n circular convolution relation

Started by 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.
&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;
```
```>>> 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
```