Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
circular conv

Subject: circular conv

From: David Epstein

Date: 21 Dec, 2012 10:36:08

Message: 1 of 8

I have sequences u=(u_1,...,u_N) and v=(v_1,...,v_N) of complex numbers. The indices are "circular", that is, they are interpreted mod N. Is there a Matlab command that gives the vector w, where w_r = u_{1+r}v_1 + u_{2+r}v_2 + ... u_{N+r}v_N? All the Matlab functions I've looked at give a vector of length 2N-1, instead of a vector of length N. I suppose I could just take u twice over, and pad v with zeros, but then conv or whatever will do unnecessary work. In this application efficiency is important.

Subject: circular conv

From: Bruno Luong

Date: 21 Dec, 2012 11:52:07

Message: 2 of 8

"David Epstein" <David.Epstein.spam@remove.warwick.ac.uk> wrote in message <kb1e2o$bj1$1@newscl01ah.mathworks.com>...
> I have sequences u=(u_1,...,u_N) and v=(v_1,...,v_N) of complex numbers. The indices are "circular", that is, they are interpreted mod N. Is there a Matlab command that gives the vector w, where w_r = u_{1+r}v_1 + u_{2+r}v_2 + ... u_{N+r}v_N? All the Matlab functions I've looked at give a vector of length 2N-1, instead of a vector of length N. I suppose I could just take u twice over, and pad v with zeros, but then conv or whatever will do unnecessary work. In this application efficiency is important.

a=ceil(10*rand(1,n))
b=ceil(10*rand(1,n))

% Fast convolution
c = real(ifft(fft(a).*fft(b)))

% it does this:
c = zeros(1,n);
for k=1:n
    c(k) = sum(a.*b(mod(k-(1:n),n)+1));
end
c

Subject: circular conv

From: David Epstein

Date: 21 Dec, 2012 12:45:09

Message: 3 of 8

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <kb1ih7$pcf$1@newscl01ah.mathworks.com>...
> "David Epstein" <David.Epstein.spam@remove.warwick.ac.uk> wrote in message <kb1e2o$bj1$1@newscl01ah.mathworks.com>...
> > I have sequences u=(u_1,...,u_N) and v=(v_1,...,v_N) of complex numbers. The indices are "circular", that is, they are interpreted mod N. Is there a Matlab command that gives the vector w, where w_r = u_{1+r}v_1 + u_{2+r}v_2 + ... u_{N+r}v_N? All the Matlab functions I've looked at give a vector of length 2N-1, instead of a vector of length N. I suppose I could just take u twice over, and pad v with zeros, but then conv or whatever will do unnecessary work. In this application efficiency is important.
>
> c = real(ifft(fft(a).*fft(b)))

Thanks a lot. I should have known this.
"real" must be a typo.

Subject: circular conv

From: Bruno Luong

Date: 21 Dec, 2012 13:12:10

Message: 4 of 8

"David Epstein" <David.Epstein.spam@remove.warwick.ac.uk> wrote in message <kb1lkl$61t$1@newscl01ah.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message
>
> Thanks a lot. I should have known this.
> "real" must be a typo.

Not a typo, the purpose is to force the imaginary part to be zero assuming you work with non-complex data.

Bruno

Subject: circular conv

From: David Epstein

Date: 21 Dec, 2012 17:48:16

Message: 5 of 8

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <kb1n7a$bdq$1@newscl01ah.mathworks.com>...
> "David Epstein" <David.Epstein.spam@remove.warwick.ac.uk> wrote in message <kb1lkl$61t$1@newscl01ah.mathworks.com>...
> > "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message
> >
> > Thanks a lot. I should have known this.
> > "real" must be a typo.
>
> Not a typo, the purpose is to force the imaginary part to be zero assuming you work with non-complex data.
>
> Bruno

Thanks, Bruno. I see your point, but I specified in my original posting that my data was complex.
David

Subject: circular conv

From: Matt J

Date: 22 Dec, 2012 08:23:07

Message: 6 of 8

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <kb1ih7$pcf$1@newscl01ah.mathworks.com>...
>
> % Fast convolution
> c = real(ifft(fft(a).*fft(b)))
>


%Should be faster?

c = ifft( fft(a).*fft(b) ,'symmetric' )

Subject: circular conv

From: Bruno Luong

Date: 22 Dec, 2012 08:26:13

Message: 7 of 8

"Matt J" wrote in message <kb3qlb$650$1@newscl01ah.mathworks.com>...
> %Should be faster?
>
> c = ifft( fft(a).*fft(b) ,'symmetric' )

Possibly, in case of real data. I believe David has complex data.

Bruno

Subject: circular conv

From: David Epstein

Date: 22 Dec, 2012 15:28:06

Message: 8 of 8

"Matt J" wrote in message <kb3qlb$650$1@newscl01ah.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <kb1ih7$pcf$1@newscl01ah.mathworks.com>...
> >
> > % Fast convolution
> > c = real(ifft(fft(a).*fft(b)))
> >
>
>
> %Should be faster?
>
> c = ifft( fft(a).*fft(b) ,'symmetric' )

In my case, the input to ifft will not be conjugate symmetric, so the checks for 'symmetric' would actually slow things down a bit.

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us