Toward the 'noise maker' aspect of the sleep mask I'm designing, I've done some work toward generating white and colored noise on the AVR XMEGA hardware. My goal was to generate white, pink and red/brown noise so that any of the three could be chosen by a user to aid their sleep. So far, I have generated white, pink and red noise in simulation (using a model of the XMEGA's CRC generator) and have translated these simulations successfully to the actual microcontroller for the white and red cases. UPDATE: pink case also successfully implemented.
Background
Many devices and applications exist which generate various sounds/noises to aid sleep and drown out the irregular sounds which can interrupt deep sleep. Three commonly provided sounds are white, pink and red noise; white noise has the most high-frequency content, pink less and red the least.
Colored noise
White noise refers, generally, to noise whose samples are totally independent of each other; knowledge of one sample gives no information about any other sample, previous or subsequent. As a result, a white noise signal's autocorrelation is unity at zero lag and zero elsewhere. Additionally, a white noise signal has equal power at all frequencies. Different types of noise are commonly referred to by their 'color': white is so-called because it contains all frequencies, analogous to the way that white light contains all colors. Pink noise is similar to white noise, except that it has a decreasing amount of power as frequency increases; where white noise has a constant power level (P(f) = 1, let's say), pink noise has 1/f power (P(f) = 1/f). Red noise takes it a step further, having even less power at high frequencies (P(f) = 1/f^2).
Pink and red noise can be generated from white noise. Red noise can be generated by integrating white noise (this is where its other name, brown/brownian noise, comes from: the path of the signal in time is a Brownian walk). Pink is more difficult to generate; where red noise can be generated using integration or a first-order lowpass, generating pink noise would require some sort of half-order filter. From my researches, there are two commonly-implemented methods for generating pink noise computationally from white noise: using a specially-specified higher-order filter, and the Voss-McCartney method. These methods are quite capably and completely explained and expounded upon here and here; since the special filter method involved a lot of multiplication and tweaking and maybe even floating point math, I chose the Voss-McCartney method. It is very clever, and only relies on addition, subtraction and keeping track of a very small buffer of past-generated white noise samples. I will go over it further when I describe my implementation below (I assure you, though, the sites above are quite top-notch).
Random and no-so-random numbers
The difficulty in generating white noise is finding a signal source whose output at one point in time is totally independent of its output at a subsequent time. Or course, this is impossible with any normal computer system; its state at one clock cycle is deterministically derived from its state at the previous cycle. It is possible to access randomness in the form of analog signals in the environment around the computer; if we have a bit of radioisotope, its decay will serve as a great random process. A reverse-biased diode can also be used, as can the randomness in the timing of user interactions (if we happen to have a user close at hand). The problems with the above hardware random number generators (and hardware random number generators in general) are twofold: first, the extra hardware can be expensive; second, the rate of random bit generation can be very slow (especially true in the case of the user input).
Faced with these costs, it would be nice if we could, deterministically within the computer, generate numbers which are random-like. While the computer's state completely predicts the next pseudorandom number, the string of numbers in question may appear random enough for a specific purpose. Since our success criterion is 'does it sound good', even a poor pseudorandom number generator (PRNG) will be good enough. There are a variety of algorithms extant; Linear Feedback Shift Registers (LFSR) are one such class of PRNG. They work by shifting a register and exclusive-OR-ing some of its members every clock cycle. The XORshift algorithm is a cheap and capable method invented by George Marsaglia. I implemented and tested a version of it (for the 8-bit platform, developed by William Donnelly) before I realized that the Cyclic Redundancy Check hardware on the XMEGA, intended to check the integrity of the program flash memory and USB transmissions, was also an LFSR and might afford me four bytes of decent pseudorandom numbers every clock cycle.
Hardware and software implementation
The central question going into this was 'will the hardware CRC peripheral be able to produce samples of data that sound sufficiently white?'. I had already implemented the 8-bit Xorshift algorithm provided by William Donnelly, and it performed well. However, it took over 70 cycles to generate one sample, so the possibility of ONE cycle samples was too good not to investigate.
Setting up and using the CRC to generate pseudorandom numbers
The CRC peripheral on the USB-capable XMEGAs is fairly straightforward: a control byte, a status byte, a data input byte and four output bytes. It can take as input the flash memories, the DMA channels or a 'manual' single-byte IO channel, so that user applications can more easily take advantage of the hardware. I had some difficulty with getting the thing to take my IO data and getting it to perform the full 32-bit CRC (instead of getting stuck in the 16-bit mode), so here's my sequence for initializing it for my nefarious purposes:
//set up the CRC thingy to accept data from the IO bus, CRC-32
//also set the current state of the CRC generator to all 1's (if //it resets with all 0's, this will go nowhere)
CRC_CTRL |= CRC_RESET_RESET1_gc;
//set up the input to be the data byte
CRC_CTRL &= CRC_SOURCE_gm;
CRC_CTRL |= CRC_SOURCE_IO_gc;
//set to 32 bit width; first set busy byte to allow the change
CRC_STATUS |= CRC_BUSY_bm;
CRC_CTRL |= CRC_CRC32_bm;
Every time I want to get a new random number set in the outputs, I feed all zeros into the CRC (other bytes may be valid), and read out the changed checksum a mere single cycle later.
//change the checksum
CRC_DATAIN = 0b00000000;
//get the bytes
uint8_t crc_out3 = CRC_CHECKSUM3;
uint8_t crc_out2 = CRC_CHECKSUM2;
uint8_t crc_out1 = CRC_CHECKSUM1;
uint8_t crc_out0 = CRC_CHECKSUM0;
Bear in mind that this set-up only works for my situation of steady-state generation of pseudo-random checksums by passing more and more constant bytes into the CRC hardware. If the CRC hardware is required for other tasks (like, for example, checking out USB packets), it will be necessary to save the current state and reset the generator (including, possibly, changing the data source and bit width) before using it. Before going back to using the CRC as a PRNG, it is necessary to pause the generator, load it with the saved state, and set the input and bit width as above.
To verify that I understood how the CRC hardware worked and how to access it, I created a firmware which generates a new CRC checksum (by adding an all-zero byte to the input) and transmits it over the serial peripheral. The source is available here (that component is actually commented out in a big block in the middle).
Simulating a sequence of random numbers; implemented coloration
Using the data output over the serial channel above, I tested a MATLAB function which implemented the activity of the CRC as detailed in the device datasheet (available in this zip file, 'benCRC32guess.m'). Once I was satisfied that my model of its working was correct (bear in mind, that file assumes that the input to the CRC is all zeros), I used it to generate a sequence of bytes as the hardware would. I then did the simplest test of white-ness possible: auto- and cross-correlation.
The first plot is the autocorrelation for the first byte of the CRC checksum; It is high for only one sample and low elsewhere (not sure why the scaling was all wonky).
The second test was cross-correlation between the bytes; even getting only one random byte per cycle would be great, but if I could use all four (that is, if they were also independent of each other) would be super-great. As shown below, the cross-correlations were all nada (same weird scaling as above).
Note that the above two plots are exemplars (top was for byte 1, bottom was betwen bytes 1 and 2); the autocorrelations of the other 3 bytes and cross-correlations between the other 5 pairs were similarly acceptable. The final (and most important) test was the by-ear test; does it sound right? As linked above (and here), the white noise from the simulation sounded right.
Now that I was confident that the CRC PRNG method was acceptable, I moved on to implementing the red and pink noise generators. The brown was the simplest; simply integrate the input from the white sample generated above (taking care to prevent values outside a finite range). This first pass was okay... but exhibited some nasty clipping-ish atrifacts, due to the fact that I just put a hard limit on the valid range (that is... once you hit the ceiling/floor, you hit hard, and saturate). To soften this, I set up 'buffer' ranges within the valid range. The middle range allowed for integration as normal; however, progressively farther out ranges scale down input samples which would move the integrand away from the middle of the range. This was implemented in the MATLAB file 'brownMakerSoftedge.m' in the zip file linked above (and here). While I have no idea what this does to the statistics of the signal, it makes it sound better, and thus is awesome.
Implementing the Voss-McCartney algorithm for pink noise generation was slightly more involved (but only slightly). While the links above explain in more detail the ins and outs of the algorithm and its statistical properties, I will describe it briefly here. Basically, the output of the generator is the sum of 8 white noise generators. Each generator is sampled progressively more slowly; the first generator is updated every sample, the second every two samples, the third every four samples... Since each generator exhibits more and more low-frequency power, the sum of the set ends up having a more-or-less 1/f power spectrum. By scheduling the updates appropriately, only two new white noise bytes are required every sample. My implementation is in the MATLAB ZIP file, as 'pinkBuffer.m'; the sample sound is here. As above, it sounds right, so it is right.
Porting the colorizers to the hardware
The MATLAB business above was more-or-less directly ported to C for compilation and loading onto the ATXMEGA32A4U. The source is in these three files (various bits of code will need to be commented/uncommented). I set up the generators to continuously transmit samples over the serial channel; these samples were read into MATLAB using the 'getSerialCRCtest.m' file in the ZIP archive. They were then converted to floating point values, zero-meaned and scaled so that they could be exported as WAV files. The hardware-generated white noise is here, and the hardware-generated red noise is here. They sound good, so I'm satisfied. Currently, the hardware pink output does not sound good (and, upon visual analysis, also does not look good), so I am still working on that. UPDATE: I changed the source slightly, so the pink works now (and sounds right). Modified source is here.
Next steps
The first step is to figure out whats going wrong with the XMEGA implementation of the Voss-McCartney algorithm. Probably some sort of overflow issue.
The next step is to read up on the XMEGA DACs and start passing the generator outputs to the outside world. After achieving that, I'll mock up the headphone amplifier and see if lowpassing is necessary to eliminate DAC switching transients in the output (if not, I can use the internal-resistor amplifiers, which would reduce overall parts count).
Once all of that is settled, I'll tidy up the code to make it more modular/portable, probably including a save/load state feature to allow CRC hardware use by other functions to be interleaved with the use here.
UPDATE: The pink noise generator works now. Instead of updating the buffer sum, I completely re-calculate it with each iteration. The modified source is here.
The next step is to read up on the XMEGA DACs and start passing the generator outputs to the outside world. After achieving that, I'll mock up the headphone amplifier and see if lowpassing is necessary to eliminate DAC switching transients in the output (if not, I can use the internal-resistor amplifiers, which would reduce overall parts count).
Once all of that is settled, I'll tidy up the code to make it more modular/portable, probably including a save/load state feature to allow CRC hardware use by other functions to be interleaved with the use here.
UPDATE: The pink noise generator works now. Instead of updating the buffer sum, I completely re-calculate it with each iteration. The modified source is here.
No comments:
Post a Comment