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

Justin Ruggles justin.ruggles
Wed Sep 10 04:20:37 CEST 2008


Michael Niedermayer wrote:
> 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 ...

I see. It works for me. Ignore the patch. Who knows, we may actually
need Gaussian noise sometime in the future, so I'll keep the code on
file just in case. :)

Thanks for the help!

-Justin




More information about the ffmpeg-devel mailing list