[FFmpeg-devel] [PATCH] normal PRNG using ziggurat method

Michael Niedermayer michaelni
Wed Sep 10 02:27:05 CEST 2008


On Tue, Sep 09, 2008 at 06:32:05PM -0400, Justin Ruggles wrote:
> Michael Niedermayer wrote:
> > On Mon, Sep 08, 2008 at 11:04:48PM -0400, Justin Ruggles wrote:
> >> Michael Niedermayer wrote:
> >>> On Mon, Sep 08, 2008 at 08:05:34PM -0400, Justin Ruggles wrote:
> >>>> Hi,
> >>>>
> >>>> This is a patch to add a PRNG which generates numbers with standard
> >>>> normal distribution.  It uses the ziggurat method, which is quite fast
> >>>> compared to other methods.
> >>>>
> >>>> I was working on another implementation based on the original paper,
> >>>> which had sample code in it that I was using as a starting point.  Then
> >>>> I noticed the teeny tiny print at the bottom of the journal's download
> >>>> page which states that the code is under GPL... :(  I found another
> >>>> implementation which was based on the paper without using the
> >>>> accompanying code and is under a BSD-style license.  I trimmed it down,
> >>>> cleaned-up it up, and adapted it for FFmpeg.
> >>>>
> >>>> I need this for spectral extension processing in the E-AC-3 decoder.
> >>>> The spec requires that the generated noise which is blended with
> >>>> translated coeffs have "zero-mean, unity variance".
> >>> is "zero-mean, unity variance" everything the spec requires or is there
> >>> more?
> >> That is all it requires.
> >>
> >>> Because any signal (like the output of any PRNG) can be scaled and translated
> >>> to have that, there would be no need for normal distributed PRNG.
> >>>
> >>>
> >>> [...]
> >> This does scale and translate output from one of the already existing
> >> PRNG's...sort of. :)
> >>
> >> The zero mean part is easy enough.  If there is a simpler (and faster)
> >> way to generate random noise with unity variance distribution, please
> >> tell me.
> > 
> > well lets assume you have a PRNG that returns 32bit values between 
> > 1-(1<<31) and (1<<31)-1 then its variance is
> > 
> > 0x155555551555555580000000 / 0xFFFFFFFF
> > 
> > or
> > 4611686016279904256 / 3
> > 
> > or
> > (2^62 - 2^31) / 3
> > 
> > if you want to have unit variance then you have to scale the output of the
> > PRNG by the inverse of the sqare root of above
> > that is
> > / sqrt((2^62 - 2^31) / 3)
> > thats about
> > * .0000000008065490089227220965715845679045014243097423344385291291108274584648500175464441618401658093...
> 
> Thanks for the explanation.
> That is a tiny number...
> 
> I re-read the section in the spec, which I should have done before.  It
> turns out that I misinterpreted it.  The part about zero-mean,
> unity-variance (and the accompanying pseudocode) is only an
> implementation suggestion.
> 
> This is the only actual requirement:
> "In order to properly blend the translated transform coefficients with
> pseudo-random noise, the noise components for each band must be scaled
> to match the energy of the translated transform coefficients in the band."
> 
> The spec follows with a suggestion:
> "The energy matching can be achieved by scaling all the noise components
> in a given band by the RMS energy of the translated transform
> coefficients in that band, provided the noise components are generated
> by a zero-mean, unity-variance noise generator."
> 
> I think I'm missing something here... If a zero-mean, unity-variance
> distribution can be achieved by merely translating and scaling the
> uniform noise, why would it matter what the variance is if we just end
> up scaling it back up to match the energy of the signal coefficients?

It doesnt
the way i interpret the quoted part is
you must scale it to match the energy
That means for example if your noise generator had a variance of 1 then you
have to scale it by the RMS energy of ...


[...]

-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

Why not whip the teacher when the pupil misbehaves? -- Diogenes of Sinope
-------------- 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/20080910/d1c4210b/attachment.pgp>



More information about the ffmpeg-devel mailing list