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

[Alex Converse]

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:

Forward Transform, negative sign convention:
xhat[n] = x[2n] + j*x[2n+1],
Xhat[k] = sum(n=0..N/2-1) xhat[n] e^(-2pi*j*n*k/N),
X[k] = (Xhat[k] + Xhat*[N/2-k])/2 + j*(Xhat[k] - Xhat*[N/2-k])/2*e^(2*pi*j*k/N)

Forward Transform, positive sign convention:
xhat[n] = x_even[2n] + j x_odd[2n+1],
Xhat[k] = sum(n=0..N/2-1) xhat[n] e^(+2pi*j*n*k/N),
X[k] = (Xhat[k] + Xhat*[N/2-k])/2 + j*(Xhat[k] - Xhat*[N/2-k])/2*e^(-2*pi*j*k/N)

Inverse Transform, negative sign convention:

Xhat[k] = (X[k] + X*[N/2-k])/2 - j*(X[k] - X*[N/2-k])/2*e^(-2*pi*j*k/N)
xhat[n] = sum(k=0..N/2-1) Xhat[k] e^(2pi*j*n*k/N)
x[2*n] = re(xhat[n]), x[2*n+1] = im(xhat[n])

Inverse Transform, positive sign convention:

Xhat[k] = (X[k] + X*[N/2-k])/2 - j*(X[k] - X*[N/2-k])/2*e^(2*pi*j*k/N)
xhat[n] = sum(k=0..N/2-1) Xhat[k] e^(-2pi*j*n*k/N)
x[2*n] = re(xhat[n]), x[2*n+1] = im(xhat[n])

(I hope I didn't make any transcription errors)

--Alex