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

Justin Ruggles justin.ruggles
Wed Sep 10 00:32:05 CEST 2008


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?

-Justin




More information about the ffmpeg-devel mailing list