overlap and add/ FFT/DCT

Topic: overlap and add/ FFT/DCT (Read 6240 times) previous topic - next topic

0 Members and 1 Guest are viewing this topic.

overlap and add/ FFT/DCT

2005-04-25 10:11:14

Hello,

The transform coders use FFT . After performing an FFT we need to do overlap and add because we need linear convolution rather than circular convolution of FFT. so we perform a overlap and add so that the samples which are wrapped around are put in proper place and to reduce the distortion.now my question is can we remove overlap and add so that we use only FFT ??

This comes from the fact that in my WMA(i know most of u dont like this codec) we perform a 2048 point FFT and then overlap and add.My friend argues that we can remove the overlap and add provided that we do a 1024 point FFT. Is this true ??

what i think is , since using FFT gives circular convolution and we need linear convolution what ever may be 576 or 1024 or 2048 point FFT u have to do a overlap and add since the output of FFT is wrapped around .

can anyone make it clear for me

?
thanking u guys in advance ......

overlap and add/ FFT/DCT

Reply #1 – 2005-04-25 11:28:18

Current transform coders are using MDCT to code data rather than FFT. The MDCT is naturally overlapping.

Overlap is necessary to reduce artefacts around block limits (similar to an highly compressed JPEG).

overlap and add/ FFT/DCT

Reply #2 – 2005-04-25 12:15:46

Quote

Current transform coders are using MDCT to code data rather than FFT. The MDCT is naturally overlapping.

Overlap is necessary to reduce artefacts around block limits (similar to an highly compressed JPEG).
[a href="index.php?act=findpost&pid=293232"][{POST_SNAPBACK}][/a]

Hello gabriel .. thanks u r the first ...
but let me tell u that MDCT uses FFT .
so u need overlap and add again even if u go with MDCT.
My question is can we get rid of the overlap and add by reducing the T/F size.
i,e from 2048 to 1024 so that u dont need overlap and add.
Is it correct & Is it possible ??

thanks.....

overlap and add/ FFT/DCT

Reply #3 – 2005-04-25 12:40:00

Of course it is possible to create a transform codec using only an FFT, but it is not desirable because of artifacts at block boundaries.

overlap and add/ FFT/DCT

Reply #4 – 2005-04-25 13:08:01

Quote

Of course it is possible to create a transform codec using only an FFT, but it is not desirable because of artifacts at block boundaries.
[a href="index.php?act=findpost&pid=293244"][{POST_SNAPBACK}][/a]

but the thing is i wanna optimize the code so that it can run in real time on a PMP.if i dont use FFT normal calculation will consume a lot of cycles which inturn reduces the processor power.

overlap and add/ FFT/DCT

Reply #5 – 2005-04-25 15:47:13

Quote

The transform coders use FFT.
[a href="index.php?act=findpost&pid=293225"][{POST_SNAPBACK}][/a]

Yes, most of'em if not all (mostly for spectral analysis or as part of the MDCT, though).

Quote

After performing an FFT we need to do overlap and add because we need linear convolution rather than circular convolution of FFT.
[a href="index.php?act=findpost&pid=293225"][{POST_SNAPBACK}][/a]

Convolution ? I thought you were talking about transform coders !?

Quote

so we perform a overlap and add so that the samples which are wrapped around are put in proper place and to reduce the distortion.now my question is can we remove overlap and add so that we use only FFT ??
[a href="index.php?act=findpost&pid=293225"][{POST_SNAPBACK}][/a]

Yes, but this will create blocking artefacts.

Quote

This comes from the fact that in my WMA(i know most of u dont like this codec) we perform a 2048 point FFT and then overlap and add.My friend argues that we can remove the overlap and add provided that we do a 1024 point FFT. Is this true ??
[a href="index.php?act=findpost&pid=293225"][{POST_SNAPBACK}][/a]

You can do many things. Depends on what you are trying to achieve.

Quote

what i think is , since using FFT gives circular convolution and we need linear convolution what ever may be 576 or 1024 or 2048 point FFT u have to do a overlap and add since the output of FFT is wrapped around .
[a href="index.php?act=findpost&pid=293225"][{POST_SNAPBACK}][/a]

What's with the "linear convolution" all the time ?!

Quote

Hello gabriel .. thanks u r the first ...
but let me tell u that MDCT uses FFT .
so u need overlap and add again even if u go with MDCT.
My question is can we get rid of the overlap and add by reducing the T/F size.
i,e from 2048 to 1024 so that u dont need overlap and add.
Is it correct & Is it possible ??
[a href="index.php?act=findpost&pid=293238"][{POST_SNAPBACK}][/a]

It does not make sense.
Yes, an MDCT can be calculated via FFT and some simple (O(n)) pre- and post-"twiddeling"-transform. Why would you want to get rid of "overlap & add" ? This is the only way to prevent blocking artefacts. When you go with the MDCT you won't get blocking artefacts (due to the overlap & add part) while remaining critically sampled data. (Yay!)

Quote

but the thing is i wanna optimize the code so that it can run in real time on a PMP.if i dont use FFT normal calculation will consume a lot of cycles which inturn reduces the processor power.
[a href="index.php?act=findpost&pid=293250"][{POST_SNAPBACK}][/a]

As I said: You can brake the MDCT into smaller "transform-pieces", including the FFT while most of the processing power will be required for the FFT. So, if the developement tools for the PMP already inlcude the (possibly hardware optimized) FFT you can make use of it for efficiently computing the MDCT.

Anyhow, you don't want to develop a new transform codec, do you ?
Get the sources of libVorbis and replace the MDCT code (AFAIK Vorbis does not use an FFT for computing the MDCT) or FAAC/FAAD if you feel like porting Vorbis or AAC to the PMP.

AFAIK the PMP supports already MP3 and Atrac3plus nativly (in hardware - via FPGA?). So why the hassle ?

SebastianG

edit: Oups! I was thinking of Sony's PSP all the time. What's PMP ?

overlap and add/ FFT/DCT

Reply #6 – 2005-04-26 05:11:23

Quote

Quote
The transform coders use FFT.
[a href="index.php?act=findpost&pid=293225"][{POST_SNAPBACK}][/a]

Yes, most of'em if not all (mostly for spectral analysis or as part of the MDCT, though).

Quote
After performing an FFT we need to do overlap and add because we need linear convolution rather than circular convolution of FFT.
[a href="index.php?act=findpost&pid=293225"][{POST_SNAPBACK}][/a]

Convolution ? I thought you were talking about transform coders !?

Quote
so we perform a overlap and add so that the samples which are wrapped around are put in proper place and to reduce the distortion.now my question is can we remove overlap and add so that we use only FFT ??
[a href="index.php?act=findpost&pid=293225"][{POST_SNAPBACK}][/a]

Yes, but this will create blocking artefacts.

Quote
This comes from the fact that in my WMA(i know most of u dont like this codec) we perform a 2048 point FFT and then overlap and add.My friend argues that we can remove the overlap and add provided that we do a 1024 point FFT. Is this true ??
[a href="index.php?act=findpost&pid=293225"][{POST_SNAPBACK}][/a]

You can do many things. Depends on what you are trying to achieve.

Quote
what i think is , since using FFT gives circular convolution and we need linear convolution what ever may be 576 or 1024 or 2048 point FFT u have to do a overlap and add since the output of FFT is wrapped around .
[a href="index.php?act=findpost&pid=293225"][{POST_SNAPBACK}][/a]

What's with the "linear convolution" all the time ?!

Quote
Hello gabriel .. thanks u r the first ...
but let me tell u that MDCT uses FFT .
so u need overlap and add again even if u go with MDCT.
My question is can we get rid of the overlap and add by reducing the T/F size.
i,e from 2048 to 1024 so that u dont need overlap and add.
Is it correct & Is it possible ??
[a href="index.php?act=findpost&pid=293238"][{POST_SNAPBACK}][/a]

It does not make sense.
Yes, an MDCT can be calculated via FFT and some simple (O(n)) pre- and post-"twiddeling"-transform. Why would you want to get rid of "overlap & add" ? This is the only way to prevent blocking artefacts. When you go with the MDCT you won't get blocking artefacts (due to the overlap & add part) while remaining critically sampled data. (Yay!)

i wanna get rid of overlap and add because i wanna reduce the MIPS.There are many ways of reducing MIPS like asm coding and all but if i remove this block i will be able to gain a better reduction in MIPS.

Quote
but the thing is i wanna optimize the code so that it can run in real time on a PMP.if i dont use FFT normal calculation will consume a lot of cycles which inturn reduces the processor power.
[a href="index.php?act=findpost&pid=293250"][{POST_SNAPBACK}][/a]

As I said: You can brake the MDCT into smaller "transform-pieces", including the FFT while most of the processing power will be required for the FFT. So, if the developement tools for the PMP already inlcude the (possibly hardware optimized) FFT you can make use of it for efficiently computing the MDCT.

Anyhow, you don't want to develop a new transform codec, do you ?
Get the sources of libVorbis and replace the MDCT code (AFAIK Vorbis does not use an FFT for computing the MDCT) or FAAC/FAAD if you feel like porting Vorbis or AAC to the PMP.

AFAIK the PMP supports already MP3 and Atrac3plus nativly (in hardware - via FPGA?). So why the hassle ?

hello we r not using FPGA we r using only DSP here.

SebastianG

edit: Oups! I was thinking of Sony's PSP all the time. What's PMP ?
[a href="index.php?act=findpost&pid=293281"][{POST_SNAPBACK}][/a]

PMP is portable multimedia player which we develop here this is something like playing audio and video.all file formats will be supported like mp4,avi,asf etc..

overlap and add/ FFT/DCT

Reply #7 – 2005-04-26 21:28:30

Quote

Hello gabriel .. thanks u r the first ...
but let me tell u that MDCT uses FFT .
so u need overlap and add again even if u go with MDCT

I can't quite make sense of this. An MDCT has an intrinisic overlap that you can't get rid of. If you use an MDCT with the standard Princen-Bradley (sine) window, you can't avoid overlap.

The overlap, modulo using a strange window that doesn't make sense, is obligatory in an MDCT. It is written in.

You say that "MDCT uses FFT". Why does this have anything to do with anything? A standard PQMF uses an FFT, but it certainly has overlap, for instance. So does an MDCT.

You might get a copy of Malvar's book if this isn't clear to you.

overlap and add/ FFT/DCT

Reply #8 – 2005-04-27 15:44:09

Quote

I can't quite make sense of this. An MDCT has an intrinisic overlap that you can't get rid of. If you use an MDCT with the standard Princen-Bradley (sine) window, you can't avoid overlap.
[a href="index.php?act=findpost&pid=293547"][{POST_SNAPBACK}][/a]

A rectangular window like

Code: [Select]

     +-------+
     |       |
     |       |
+---+       +---+

(which is a valid MDCT window) practically leads to a DCT_4 (without overlap & add).
=> slight speed improvement (maybe 3% for a common blocksize)
=> blocking artefacts (duh!)

@OP: I don't think you really want this.

SebastianG

overlap and add/ FFT/DCT

Reply #9 – 2005-04-28 06:54:23

Quote

Quote
I can't quite make sense of this. An MDCT has an intrinisic overlap that you can't get rid of. If you use an MDCT with the standard Princen-Bradley (sine) window, you can't avoid overlap.
[a href="index.php?act=findpost&pid=293547"][{POST_SNAPBACK}][/a]

A rectangular window like
Code: [Select]
     +-------+
     |       |
     |       |
+---+       +---+
(which is a valid MDCT window) practically leads to a DCT_4 (without overlap & add).
=> slight speed improvement (maybe 3% for a common blocksize)
=> blocking artefacts (duh!)

@OP: I don't think you really want this.

SebastianG
[a href="index.php?act=findpost&pid=293682"][{POST_SNAPBACK}][/a]

Blah! (perhaps thanks to a timeout in the original submission, my comments vanished)

Somewhere, I said something to the effect that the MDCT formulation includes overlap, and what you're doing here is simply setting the window to zero.

In terms of the original Princen formula, at least, even though the window is zero, you'll be summing up a bunch of zero terms.

My point was that the formulation includes overlap, which it does, even if the window is zero, and thereby defeating that overlap.

Notice