[FFmpeg-devel] [PATCH] RDFT for Bink and QDM2

[Michael Niedermayer]

On Thu, Jan 22, 2009 at 11:56:24AM -0500, Alex Converse wrote:
> On Wed, Jan 21, 2009 at 6:14 PM, Michael Niedermayer <michaelni at gmx.at> wrote:
> > On Wed, Jan 21, 2009 at 06:03:36PM -0500, Alex Converse wrote:
> >> On Wed, Jan 21, 2009 at 5:53 PM, Michael Niedermayer <michaelni at gmx.at> wrote:
> >> > On Wed, Jan 21, 2009 at 04:45:09PM -0500, Alex Converse wrote:
> >> >> On Wed, Jan 21, 2009 at 4:25 PM, Michael Niedermayer <michaelni at gmx.at> wrote:
> >> >> > On Wed, Jan 21, 2009 at 01:12:30PM -0500, Alex Converse wrote:
> >> >> >> On Wed, Jan 21, 2009 at 8:36 AM, Michael Niedermayer <michaelni at gmx.at> wrote:
> >> >> >> >
> >> >> >> > On Tue, Jan 20, 2009 at 03:19:46PM -0500, Alex Converse wrote:
> >> >> >> > > On Tue, Jan 20, 2009 at 1:50 PM, Michael Niedermayer <michaelni at gmx.at> wrote:
> >> >> >> > > > On Tue, Jan 20, 2009 at 12:24:06PM -0500, Alex Converse wrote:
> >> >> >> > > >> On Tue, Jan 20, 2009 at 11:52 AM, Michael Niedermayer <michaelni at gmx.at> wrote:
> >> >> >> > > >> > On Mon, Jan 19, 2009 at 07:44:38PM -0500, Alex Converse wrote:
> >> >> >> > > > [...]
> >> >> >> > > >> >
> >> >> >> > > >> > [...]
> >> >> >> > > >> >
> >> >> >> > > >> >> +/**
> >> >> >> > > >> >> + * Sets up a real FFT.
> >> >> >> > > >> >> + * @param nbits           Log2 of the length of the input array
> >> >> >> > > >> >
> >> >> >> > > >> >> + * @param inverse         If TRUE, perform the inverse of the transform
> >> >> >> > > >> >
> >> >> >> > > >> > i suggest if 0 perform the forward transform, if 1 perform the inverse
> >> >> >> > > >>
> >> >> >> > > >> I believe these are equivalent.
> >> >> >> > > >
> >> >> >> > > > I searched for TRUE in the iso C standard and found no match.
> >> >> >> > > > But lets assume it where defined as 1, this doesnt document any
> >> >> >> > > > other value, is inverse=2 or 0 invalid? the forward transform?
> >> >> >> > > > 99% of the people will guess correct but why write something ambigous if
> >> >> >> > > > it can be written unambigous ...
> >> >> >> > > >
> >> >> >> > > >
> >> >> >> > > >>
> >> >> >> > > >> >
> >> >> >> > > >> >
> >> >> >> > > >> >> + * @param sign_convention The sign of j of the forward FFT.
> >> >> >> > > >> >
> >> >> >> > > >> > i do not understand this, j is a variable that has no clear relation to a FFT
> >> >> >> > > >> >
> >> >> >> > > >>
> >> >> >> > > >> j is the unit vector in the vertical direction on the complex plane. j
> >> >> >> > > >> = sqrt(-1).
> >> >> >> > > >
> >> >> >> > > > wasnt that i, i for imaginary?
> >> >> >> > > >
> >> >> >> > > >
> >> >> >> > > >>
> >> >> >> > > >> The forward DFT can be defined as:
> >> >> >> > > >> X_k = \sum_{n=0}^{N-1} x_n e^{-{2\pi j \over N} nk }
> >> >> >> > > >>
> >> >> >> > > >> It also can be defined as
> >> >> >> > > >> X_k = \sum_{n=0}^{N-1} x_n e^{{2\pi j \over N} nk }
> >> >> >> > > >
> >> >> >> > > > you can, but why would we need it?
> >> >> >> > > >
> >> >> >> > >
> >> >> >> > > Bink uses it. As per the comments, the inverse of this transform is
> >> >> >> > > not simply the transform with the opposite sign convention.
> >> >> >> >
> >> >> >> > maybe iam too tired but i see just one transform
> >> >> >> >
> >> >> >> > X[  k] = sum(n=0..N-1) x[n] e^(-2pi*i*n*k / N)
> >> >> >> >        | k= N-m
> >> >> >> > X[N-m] = sum(n=0..N-1) x[n] e^(-2pi*i*n*(N-m) / N)
> >> >> >> > X[N-m] = sum(n=0..N-1) x[n] e^(-2pi*i*n*N / N - 2pi*i*n*-m / N)
> >> >> >> > X[N-m] = sum(n=0..N-1) x[n] e^(-2pi*i*n + 2pi*i*n*m / N)
> >> >> >> > X[N-m] = sum(n=0..N-1) x[n] e^( 2pi*i*n*m / N)e^(-2pi*i*n)
> >> >> >> > X[N-m] = sum(n=0..N-1) x[n] e^( 2pi*i*n*m / N)
> >> >> >>
> >> >> >> The twiddle has to happen in the frequency domain so we have 4 cases:
> >> >> >
> >> >> > i have no clue what you talk about, but after a little testing i have
> >> >> > some doubt that your code works at all.
> >> >> > for example
> >> >> >
> >> >> >    ff_rdft_init(&one, 7, 1, 0);
> >> >> >
> >> >>
> >> >> sign_convention takes +/- 1. I'm sorry if that wasn't clear.
> >> >
> >> > followng shows empirically
> >> > that the transforms are identical short of trivial changes
> >> >
> >> >    ff_rdft_init(&one, bits, 1, -1);
> >> >    ff_rdft_init(&two, bits, 1,  1);
> >> >
> >> >    for(i=0; i<N; i++)
> >> >        src[i] = dst1[i] = (i + 2*i*i - 7*i*i*i + 123) % 1000;
> >> >
> >> >    for(i=0; i<N; i++){
> >> >        dst2[i] = dst1[i];
> >> >        if((i&1) && i!=1)
> >> >            dst2[i]*=-1;
> >> >    }
> >> >
> >> >    ff_rdft_calc(&one, dst1);
> >> >    ff_rdft_calc(&two, dst2);
> >> >
> >>
> >> Yes, it can be done as yet another pre/post processing loop. Or it can
> >> be simply included as part of the transform.
> >
> > or the decoder can be fixed so it stores the values with the correct signs
> >
> 
> There is no such thing as "the correct sign." It's simply a matter of
> convention, 

Well, if you define teh RDFT as a real input DFT than there is no convention
that you can change unless you change the DFT as well

for the half output variant that you implemented you surely can choose between
0..N/2 and N/2..N, though i must admit that the first has a somehow more
correct feeling to it but then thats just feeling no argument ...


> and in this case, considering the code we already have,
> the problem is easier to solve with the positive sign convention.

We should surely pick what is simpler, used by more important codecs
and allows more tables to be shared and is closer to established conventions
i dont know which of the 2 that neccessarily is ...


[...]
-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

I have often repented speaking, but never of holding my tongue.
-- Xenocrates
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20090122/674c12e1/attachment.pgp>