Generate Pink Noise Efficiently

Started by Robert Scott March 19, 2013
I am looking for a compute-efficient algorithm to generate pink noise.
The application must run on a smartphone (iPhone or Android w/NDK) and
take up a small fraction of the available compute time.  The
application has other compute-intensive real-time tasks that cannot be
bogged down by this noise-generating task.  The purpose of the pink
noise is to serve as an analog indicator of a measured parameter for a
vision-impaired user.  The center frequency of the pink noise is the
indicated parameter.  It would be sort of like looking at a meter
movement.  The precise value is not important - only the relative
change in the indicated value - whether it is going up or down.  The
center pitch of this pink noise should range over a frequency ratio of
about 2:1.  There are reasons that I won't go into why I can't use the
more obvious solution - a simple sine wave of varying frequency.  The
sound must not sound like a coherent tone, but pink noise with a
spectral bandwidth of about 10% of the center frequency is fine.
Since the purpose of the pink noise is to indicate the relative value
of a measured parameter, the center frequency of the pink noise must
change on very short notice, like 50 msec.  So the pink noise cannot
be pre-computed.  It must be created on-the-fly with very efficient
code.

 I will be generating sound using a sample rate of 22,050 samples per
second in blocks of 512 samples (23 msec) at a time.  Liberal use of
memory is fine.  CPU time is the critical item. I know plenty of
compute-efficient ways to generate a pseudo-random sequence.  I just
don't know an efficient way to turn such a sequence into pink noise
with a given center frequency.  Any suggestions?

Robert Scott
Hopkins, MN

Robert Scott <no-one@notreal.invalid> wrote:
> I am looking for a compute-efficient algorithm to generate pink noise. > The application must run on a smartphone (iPhone or Android w/NDK) and > take up a small fraction of the available compute time. The > application has other compute-intensive real-time tasks that cannot be > bogged down by this noise-generating task.
(snip) Can you tell about how much computation, adds and multiplies, can be done per second? An LFSR should make an efficient white noise generator, but I haven't thought about how to pinkify it. Now, say you generate two streams with different peaks, then take an appropriate fraction of each. That is, instead of shifting the peak of one source shift the fractions of two. That requires at least two multiplies per sample. -- glen
sounds to me (pun intended) that you don't really need the noise to be _pink_ but
just need a tunable. band of noise 
mark
On 3/19/13 11:02 PM, glen herrmannsfeldt wrote:
> Robert Scott<no-one@notreal.invalid> wrote: >> I am looking for a compute-efficient algorithm to generate pink noise. >> The application must run on a smartphone (iPhone or Android w/NDK) and >> take up a small fraction of the available compute time. The >> application has other compute-intensive real-time tasks that cannot be >> bogged down by this noise-generating task.
to repeat a cliche: Google is your friend. also, perhaps in this case is Wikipedia.
> > (snip) > > Can you tell about how much computation, adds and multiplies, > can be done per second? > > An LFSR should make an efficient white noise generator,
single bits, well a bipolar single bit. don't use the shift register word for a random number.
> but I haven't thought about how to pinkify it. >
maybe with a pinkification filter: http://www.firstpr.com.au/dsp/pink-noise/ back in the '80s i came up with a simple 3-pole 3-zero pinking filter: pole zero ---- ---- 0.99572754 0.98443604 0.94790649 0.83392334 0.53567505 0.07568359 the response follows the ideal -3 dB/octave curve to within +/- 0.3 dB over a 10 octave range from 0.0009*nyquist to 0.9*nyquist.
> Now, say you generate two streams with different peaks, then > take an appropriate fraction of each. That is, instead of shifting > the peak of one source shift the fractions of two. That requires > at least two multiplies per sample.
glen, what do you mean regarding "streams" and "peaks"? -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
On Tue, 19 Mar 2013 20:11:04 -0700 (PDT), makolber@yahoo.com wrote:

>sounds to me (pun intended) that you don't really need the noise to be _pink_ but
just need a tunable. band of noise
>mark
Yes, it just needs to give the vague impression of a pitch without sounding too much like a coherent tone. As for the performance figures, the CPUs are those found in the iPhone, which includes a floating point processor. Robert Scott Hopkins, MN
If you have bandpass filtered noise with only a 10% bandwidth, you will hardly be
able to tell the difference between filtered white noise and filtered pink noise. If
you are sweeping bandpass-filtered white noise you can just set the amplitude as you
sweep to get the pinkiness that you desire. This is cheaper than actually
implementing a pink-noise filter.

If you are using this to measure the response of a room, and looking to average out
the detailed notches caused by long delay paths, you could also use an fm-modulated
sine-sweep. I used to work in a place that manufactured speakers, and the sound of
warbled sine-wave-sweeps is forever burned into my brain :(

Bob
robert bristow-johnson <rbj@audioimagination.com> wrote:

>> Robert Scott<no-one@notreal.invalid> wrote: >>> I am looking for a compute-efficient algorithm to generate pink noise.
(snip, I wrote)
>> Can you tell about how much computation, adds and multiplies, >> can be done per second?
>> An LFSR should make an efficient white noise generator,
> single bits, well a bipolar single bit. don't use the shift register > word for a random number.
In general I agree, but for noise it doesn't have to be that random. When listening to a pure tone, you might be able to detect some deviation in the low bits. With noise, I doubt it. There might be a little too much correlation in the high two bits, but you can fix that by moving the bits around.
>> but I haven't thought about how to pinkify it.
> maybe with a pinkification filter:
OK, with minimal computation. Well, no multplies are needed for the LFSR, how many for the filter?
> http://www.firstpr.com.au/dsp/pink-noise/
> back in the '80s i came up with a simple 3-pole 3-zero pinking filter:
> pole zero > ---- ---- > 0.99572754 0.98443604 > 0.94790649 0.83392334 > 0.53567505 0.07568359
> the response follows the ideal -3 dB/octave curve to within +/- 0.3 dB > over a 10 octave range from 0.0009*nyquist to 0.9*nyquist.
>> Now, say you generate two streams with different peaks, then >> take an appropriate fraction of each. That is, instead of shifting >> the peak of one source shift the fractions of two. That requires >> at least two multiplies per sample.
> glen, what do you mean regarding "streams" and "peaks"?
Generate two separate noise sources, filter as appropriate, then add before the DAC. The OP mentioned peaks. Seems like the power spectrum has a peak somewhere in the middle of the audio spectrum. Now, say you have A and B, pink noise sources, with peaks (see above) at 2kHz and 4kHz. Then compute xA+(1-x)B for x between 0 and 1. How will the sound change as x varies slowly from 0 to 1? -- glen
If the IIR filter is still too complex / power hungry, I'd experiment with
integrators and CIC structures in fixed point math, for a lowpass filter
that turns white into pink-ish. 
There are only a few candidates, might be worth to try them.

Another alternative is a bit-shifting FIR, where you choose coefficients
that are powers of two. 
For example
h = [1/4 1/2 1 1/2 1/4]
Exhaustive search is quite manageable for short filters.

Combine http://www.firstpr.com.au/dsp/rand31/ with
http://www.firstpr.com.au/dsp/pink-noise/ and you are pretty much done :)

Br,
Kalvin
keskiviikko, 20. maaliskuuta 2013 11.35.58 UTC+2 kalvi...@gmail.com kirjoitti:
> Combine http://www.firstpr.com.au/dsp/rand31/ with
http://www.firstpr.com.au/dsp/pink-noise/ and you are pretty much done :)
> > > > Br, > > Kalvin
And add suitable band-pass filter to get the desired frequency range, if needed.