TrueRandom is not truly random

A while ago I had to get microcontrollers to generate truly random addresses for themselves, truly random 32-bit addresses to minimize collisions.  I looked around for inspiration and found the TrueRandom library for Arduino.   After testing it, I realized it’s not actually random and shouldn’t be used for anything important.

Here’s a scatterplot of 4800 values from TrueRandom.randomByte():

TrueRandom clustering at powers of 2

and histogram:

TrueRandom histogram

Clearly these are not randomly distributed.  They’re strongly centered around 0 and low powers of 2, probably due to the von Neumann whitening algorithm they threw in there?  “This technique works no matter how the bits have been generated. It cannot assure randomness in its output, however. What it can do (with significant numbers of discarded bits) is transform a biased random bit stream into an unbiased one.”

See Randomness testing of Arduino TrueRandom for details.

It should look like this, uniformly distributed with no clustering:

/dev/urandom no clustering

With the 8051-based micro I was working with, the least significant 2 or 3 bits of the ADC were random thermal noise, even with the input pin grounded, so I used that as my entropy source.  If you XOR a random bit stream with an uncorrelated non-random stream, the output is still random, so I measured the ADC 8 times, bit-rotated each result an increasing amount, and XORed them all together, to spread the randomness around to all 8 bits.  As far as I can tell, this is a good method to produce uniformly distributed, truly random bytes.  (Please correct me if I’m wrong.)

On the Arduino, though, the ADC does not produce any noisy bits, so it can’t be used for this purpose.  The LSBs are just stuck at 0 all the time, and the value can be exactly the same many times in a row:

temperature sensor vs AVCC plot

Ardrand: The Arduino as a Hardware Random-Number Generator “We explore various methods to extract true randomness from the micro-controller and conclude that it should not be used to produce randomness from its analog pins.”

So for Arduino, I used the frequency difference between the watchdog timer and Timer 1 as the entropy source (suggested near the end of True Random Number Generation on an AtmelAVR Microcontroller, but not actually tested).   It uses the watchdog timer to sample (and reset) Timer 1.  Since the watchdog timer runs on its own RC oscillator, and Timer 1 is on the crystal oscillator, there is random variation in the value read. Then the randomness is spread around to all 8 bits by the same method.  The watchdog timer’s minimum length is not short, so this method only produces about 64 bit/s, vs TrueRandom’s 3200 bit/s.  But they’re good bits.

Since TrueRandom doesn’t live up to its name, and I’m not a cryptographic expert, I erred on the side of caution and named it ProbablyRandom:

The output looks uniformly distributed to me (and ent says it’s good, too):

65536 samples watchdog xorshifted plot

65k with TimerOne disabled histogram

I think the main flaw would be if the two oscillators become locked with each other at a certain temperature and supply voltage or something, but I haven’t noticed any drop in randomness, despite running it continuously for days.

Note: This has since been developed into the Entropy library for Arduino.

A mapping between musical notes and colors

bpert said:

If you take A = 440 Hz and keep doubling and doubling until you get into the range of light you will find ROYGBIV = F, G, A, Bb, B, C, D, E, F. Try it yourself.

So I did!  If you take the frequencies of each note in Hz (in equal temperament) and multiply them by 240 (40 octaves), you get a number in the THz, which would fall into the visual range if it represented the frequency of an electromagnetic wave instead of a sound wave. “A typical human eye will respond to wavelengths from about 390 to 750 nm.” Does it match up with ROYGBIV? Kinda.

Note Freq (Hz) +40 oct. (THz) Wavelength (nm) R G B Color HTML name
F♯4 370 407 737 174 0 0 dark red
G4 392 431 696 255 0 0 red
G♯4 415 457 657 255 0 0 red
A4 440 484 620 255 102 0 orange-red
B♭4 466 513 585 255 239 0 yellow
B4 494 543 552 153 255 0 chartreuse
C5 523 575 521 40 255 0 lime
C♯5 554 610 492 0 255 242 aqua
D5 587 646 464 0 122 255 sky blue
D♯5 622 684 438 5 0 255 blue
E5 659 725 414 71 0 237 blue
F5 698 768 390 99 0 178 indigo

I used this Python code to generate the RGB values for each wavelength, and Wolfram Alpha to find the nearest named HTML color.  Should find the nearest color names from the XKCD color survey instead (and “nearest” should be defined as distance in L*a*b* space, not in RGB space).

Since the starting point of F♯ is arbitrary, basically all this means is that our visual range covers about 1 octave.  Our audible range is 9–10 octaves, for comparison.

Find Duplicates

This program is super old, but I still use it. The original GeoCities website has been destroyed:

http://www.geocities.com/hirak_99/goodies/finddups.html

So here is a copy of the zip file:

finddups

There are a number of alternatives in this question and on alternative.to, but I’m not sure if they meet my needs yet.  Since this still works in Wine (with a dll from a real installation of Windows) and Windows 7, I’ll probably continue to use it.

Strengths:

  • Colors clearly separate groups of identical files
  • Arranged in order of size, so you can cancel the search, delete a few files, and clear up lots of space, without wasting time on small files
  • It won’t delete all copies of a file unless you explicitly tell it to.  It always keeps at least one.
  • It allows you to select a directory, so that all files in that directory or subdirectories will be marked for deletion (unless that would delete all copies of a file).
  • If it deletes all files in a directory, it can be set to delete the directory itself, too, so you can clean out an entire directory tree at once, automatically, without accidentally losing anything unique

Weaknesses:

  • Written a long time ago
  • Doesn’t look right with high-res screens.
  • Can’t read files with Unicode filenames
  • In Wine, it sees links as regular files, and will delete an actual file while sparing the link.

Update: I’ve been using AllDup instead.

Android audio applications

Signal generator 1.0.2

  • Outputs sine, pink noise, and white noise
  • Volume and frequency sliders
    • Controls are hard to grab at the edges
    • Volume control is independent from the phone’s volume control
    • Doesn’t go below 100 Hz
  • Sine waves are distorted and badly aliased at high frequencies.  THD+N measurements:
    • 100 Hz 0.149%
    • 1 kHz: 0.08%
    • 10 kHz: 7.1%
    • 20 kHz: 20.15%
    • Spectrum for 997 Hz:
    • signal generator 997 Hz
  • Although the control says “1.00 kHz” at startup, it’s actually playing 765 Hz.  Frequencies are correct after you start moving it around, though.
  • White noise level is higher than sine wave — sine wave never reaches the peak output of the phone, even at “0 dB”
  • There doesn’t seem to be any way to enter levels other than 0 dB manually, since it doesn’t let you type a minus sign.
  • White noise sounds like it’s repeating every 1.4 seconds
  • Noise is the same in both channels

Frequency generator 200909150

  • Outputs sine, square, triangle, sawtooth
  • Playing more than one sine wave causes clipping, but you can decrease the phone’s volume control
  • Default setting is 440, 444, and 448 Hz, but when played together, the waveform changes abruptly once per second
  • Sine wave THD+N:
    • 40 Hz: 1.00%
    • 440 Hz: 0.056%
    • 10 kHz: 0.051%
    • 20 kHz: 0.222%
  • I don’t know how the square, triangle and sawtooth are generated, but it ain’t right.
    • This is what the “square wave” looks like at 10 kHz:
    • freq gen square 10 kHz
    • And this is the spectrum:
    • frequency generator 10 kHz square
    • Nooot even close

(Using ExtUSB headphone cable, Adobe Audition, Audio Precision.)

A simple FastICA example

Wikipedia describes independent component analysis as “a computational method for separating a multivariate signal into additive subcomponents supposing the mutual statistical independence of the non-Gaussian source signals”. (Clearly, this was written as part of their campaign to make technical articles accessible.)

In normal people words, ICA is a form of blind source separation — a method of unmixing signals after they have been mixed together, without knowing exactly how they were mixed. It’s not as bad as Wikipedia makes it sound. It’s just the signal processing equivalent of this:

One of the problems I always have with learning stuff like this is the lack of clear examples. They exist, but they’re not generally very good. (And why do researchers always work with awful noisy 3-second 8 kHz recordings?) So, upon getting working results, I wrote up this little example.  This is in Python and requires the MDP (python-mdp in Ubuntu) and Audiolab packages (sudo easy_install scikits.audiolab).

In order for ICA to work, it requires at least one different recording for each signal you want to unmix. So if you have two musical instruments playing together in a room, and want to unmix them to get separate recordings of each individual instrument, you’ll need two different recordings of the mixture to work with (like a stereo microphone). If you have three instruments playing together, you’ll need three microphones to separate out all three original signals, etc. So, first, create the mix:

  1. Find or make two mono sound files. I just used clips of music.
  2. Mix them together to a stereo track, with both sounds mixed into both channels, but with each panned a little differently, so the two channels are not identical. They should sound all jumbled together, but the left channel should sound slightly different from the right.
  3. Save in a format that libsndfile can read, like FLAC or WAV (not mp3):
    • Mixed music
    • [audio:http://www.endolith.com/wordpress/wp-content/uploads/2009/11/Mixed-NIN-and-Mazzy-Star.mp3]

Alternatively, just mix them in Python:

sig1, fs1, enc1 = wavread('file1.wav')
sig2, fs2, enc2 = wavread('file2.wav')
mixed1 = sig1 + 0.5 * sig2
mixed2 = sig2 + 0.6 * sig1

So now you have the mixed signals, and you can pretend you don’t know how they were mixed. To unmix them automatically, run something like this in Python:

from mdp import fastica
from scikits.audiolab import flacread, flacwrite
from numpy import abs, max

# Load in the stereo file
recording, fs, enc = flacread('mix.flac')

# Perform FastICA algorithm on the two channels
sources = fastica(recording)

# The output levels of this algorithm are arbitrary, so normalize them to 1.0.
sources /= max(abs(sources), axis = 0)

# Write back to a file
flacwrite(sources, 'sources.flac', fs, enc)

The output has each signal in its own channel:

You can hear some crosstalk, but it’s pretty good:

[audio:http://www.endolith.com/wordpress/wp-content/uploads/2009/11/Unmixed-Mazzy.mp3]
[audio:http://www.endolith.com/wordpress/wp-content/uploads/2009/11/Unmixed-NIN.mp3]

For more than two sources, I just read them in separately and combined them in Python:

rec1, fs, enc = flacread('Mixdown (1).flac') # Mono file
rec2, fs, enc = flacread('Mixdown (2).flac')
rec3, fs, enc = flacread('Mixdown (3).flac')

sources = fastica(array([rec1,rec2,rec3]).transpose())

flacwrite() has no problem writing multi-channel files.

Mixed speech:

[audio:http://www.endolith.com/wordpress/wp-content/uploads/2009/11/Mix.mp3]

After demixing, there’s very little crosstalk, though the noise floor increases considerably.  This seems to be the case when the mixes are very similar:

[audio:http://www.endolith.com/wordpress/wp-content/uploads/2009/11/Source-1.mp3] [audio:http://www.endolith.com/wordpress/wp-content/uploads/2009/11/Source-2.mp3] [audio:http://www.endolith.com/wordpress/wp-content/uploads/2009/11/Source-3.mp3]

Although this method was recommended to me for real-life audio signals and microphones, as I’ve described above, it turns out that ICA doesn’t actually work well when the signals occur at different delays in the different sensor channels; it assumes instantaneous mixing (that the signals are in perfect sync with each other in all the different recordings).  Delay would happen in a real-life situation with performers and microphones, since each source is a different distance from each microphone. This is exactly the application I had in mind, though, so I don’t really have any further interest in ICA…

Two improvements to Google Earth

  1. In wide views, it should show whole-Earth (or whole-Mars, etc) images like the Blue Marble instead of a patchwork of smaller images.
  2. There should be a “fovea” at the poles to avoid the problem of hundreds of converging strips when zoomed into the poles.  This happens for both the planets and sky views, making Polaris look like you’re going into hyperspace.

Polaris

Is Ubuntu getting any better?

Here’s the same Ubuntu Forums experience polls charts as in Ubuntu release quality, but I’ll keep this one up-to-date with each release:

These charts lump together upgrades and clean installs, since the ratios are similar for both, and it shows more clearly the overall trend.

Feisty (1,387)
47% 23% 30%
Gutsy (5,479)
22% 44% 34%
Hardy (4,296)
23% 46% 31%
Intrepid (1,962)
21% 35% 44%
Jaunty (2,025)
30% 37% 33%
Karmic (4,326)
31% 33% 36%
Lucid (2,608)
27% 34% 39%
Maverick (604)
41% 29% 30%
  • The green bar is for the percent of users who found the release “worked flawlessly”.
  • Yellow is for “few things to fix, nothing serious though”.
  • Red is for “many problems that I’ve not been able to solve”.

There are some small changes between releases, but overall they aren’t terribly different. Considering there are millions of Ubuntu users, there are a huge number of people who have major problems with every single release. I’d like to see that red bar get drastically shorter with each release, but it doesn’t seem to be one of Canonical’s priorities…

Jaunty fresh install notes

Similar to the Intrepid fresh install notes, I kept notes while installing Jaunty from the CD on my Dell Inspiron 8600, trying to see it the way a complete newcomer would.

  • Again, the language selection screen is ugly.
    • language-selection
  • Again, you have to reboot after checking the CD for errors.
  • Currently it says “Press F4 to select alternative start-up and installation modes“, but it should explicitly say “Press F1 for help.”, first, for ultimate newcomers.
    • press-f4
  • After pressing F1, Help page should describe basics at top, for ultimate newcomers.  “Use arrow keys to move, press Enter to select etc”. Right now it just looks like this:
    •  HELP INDEX 
      
       KEY    TOPIC 
      
      <F1>   This page, the help index.
      <F2>   Prerequisites for running Ubuntu.
      <F3>   Boot methods for special ways of using this CD-ROM.
      <F4>   Additional boot methods; rescuing a broken system.
      <F5>   Special boot parameters, overview.
      <F6>   Special boot parameters for special machines.
      <F7>   Special boot parameters for selected disk controllers.
      <F8>   Special boot parameters for the bootstrap system.
      <F9>   How to get help.
      <F10>  Copyrights and warranties.
    • help-screen
  • Release note complaints still apply.
    • It should show a rich text box with scroll bars that contains the most recent release notes, and offer to download the rest if you have a connection. If there is a connection, download the latest rich text release notes and display them automatically.  If not, display the ones packaged with the CD, and a note saying they are out of date.
    • “If you have Internet access, read the release notes for information on problems that may affect you.”    (Bug 254639)
    • release-notes
    • Why in the world does it open up Firefox when it could just display the release notes in a rich text box in the installer itself?  There’s plenty of room.
    • release-notes-error
    • Should be able to prompt for a wireless key
  • It says “Select your time zone from the map”, but you’re really selecting location, not just time zone.  Does this affect language, keyboard layout, weather, units, or other local properties?  If not, it probably should.  (Bug 380171)
    • select-time-zone
  • Partitioner is the worst part:
    • “Install them side by side” needs wording improvement.  What is “them”?
    • It’s good that it warns “This will delete x and install y
    • Don’t show a drop-down box for disk selection if there is only one disk  (Bug 380175)
      • Use a list (with dynamic scrollbar if needed) instead so they can see and understand instantly that they have multiple choices; plenty of screen real estate for this
    • If you have multiple disks, it only shows a color bar for one disk at a time.  This drop-down selector is for that, too?  If so, shouldn’t it be at the top, instead of inside an option so that it looks like it only applies to that option?
    • If there is a big empty space on a drive, default to that. If the disk is full of partitions, but one is Linux format and completely empty, default to that.
      • This isn’t just a matter of what option comes up as default, it’s also a matter of the slider not stopping at partition boundaries.
      • So if you try to use an empty space, you’ll end up resizing an existing partition because the graphical slider mechanism only gives you so much accuracy.
      • It should just default to the boundaries of the empty space if possible, and the slider should stop at partition boundaries.
      • “Use the largest continuous free space” doesn’t even work.
    • If there are human-readable descriptions of disks and partitions, show those first.  Showing /dev/whatever should be parenthetical.
    • Why does it show a brown bar if I select manual install?  What is brown supposed to signify?
    • Slider behaves super oddly, moving all above partitions at once as I slide it.
    • This partitioner scares me, so i canceled it and modified the partitions in GParted first, then went back into the installer and used manual mode to mount the partition I wanted as root.
      • I’d like to see Canonical take a survey about the partitioner.  Does anyone actually use it?  Do most just use manual mode?  Does it really only work on drives that have Windows and nothing else on them?
    • Ask if I want to shrink another partition?
    • Partitions are not obvious.  Brown and a different shade of brown right next to each other.
    • Should show used and free space for each partition.  This helps in identifying them, helps in seeing how much space there is to work with when resizing them.
    • Should have same functions as GParted, basically (Idea 19218)
  • “What is the name of this computer?” prompt:  Are there any recommendations on what this should be?  Should it be all lowercase or less than a certain length for compatibility?  If so, it should say so.
  • In step 6, it says “Migrate documents and settings”, which presumably copies settings from existing partitions?  It didn’t recognize my Windows partition or my Ubuntu partition for migration.  It should do both.
  • It should show the password strength meter when entering the main user’s password for the first time. (Bug 155308)  Apparently it does show a “weak password” dialog if you type less than 8 characters, though.
  • The boot noise infuriates me.  I’ve heard it so many times now, and there’s no way to shut it off.  If you boot to the LiveCD, there’s going to be an extremely loud drum sound on startup, and you can’t do anything about it.  The volume buttons don’t kick in until after the sound has played.  I tried to leave the room whenever I knew it was going to happen, or cover the laptop with pillows.  (Bug 114160)
  • After finishing the installation, my computer would no longer boot.  Bad Ubuntu.  It should warn the user before installing in a location that’s not accessible by the BIOS.  I had to create a separate boot partition to get it to work.  (Bug 379348)

Ubuntu newcomer experience

I recently got a new hard drive, and installed Ubuntu on it from scratch.  I decided to put myself in the mindset of a newcomer and see how the experience compares now that I’ve been using it for two years. My unorganized notes:

  • Language selection screen after booting from CD is jarring, not totally intuitive, ugly. Fills the entire screen with no explanation of what you are supposed to do with it, though this might seem obvious.
      Ubuntu Ubiquity installer languages selection screen
  • After checking the CD for errors, why does it need to reboot again?  It should just go back to the CD menu.
    • why-do-i-have-to-reboot
  • Progress bar during startup of LiveCD should have some explanatory text about what it’s doing (“Please wait — loading the Ubuntu desktop”)
  • Startup sound can be pretty startling if the sound is turned all the way up by default.  The sound file itself should not start with a sudden onset of sound, but be a gradual increase.   Then, even if it’s loud, you would at least have some warning.
  • “If you have Internet access, read the release notes for information on problems that may affect you.”  What a stupid message.
    • It should be able to tell automatically if you have Internet access.
    • If you don’t have Internet access, then there’s no way for you to know that you are going to have problems. The release notes should be installed on the CD itself, and it should show the date at which they were last updated.
    • If you do have Internet access, it should download the latest release notes automatically and show them to you.
    • LP #254639: Installer doesn’t know whether you have Internet access
  • Keyboard layout selection should include images of keyboard layouts, and a better explanation of what a keyboard layout actually is.
  • “How do you want to partition the disk” isn’t newb-friendly.  Explain what it means to partition a disk and why you might want to do it differently.
    • “Guided” isn’t very explanatory.
    • guided-use-entire-disk
  • System beeps are scary.  They occur throughout the installation and even after the installation.  Why?
  • Icons and button icons should follow color scheme.  If you change the selection color, the title bars change color, but the folder icons are still orange.  (If icons are SVG, could this be done with CSS-based colors?)
    • UB #5238: Simple way to change the Human theme base color
  • While waiting for things to install, looked through the Examples directory.  Howard County library PDF has a typo: “central Marylan”
    • LP #223382: Embarrassing spelling error in hardy example-content
  • Examples could use a major revamp.
  • Another document in the Examples folder says to click on a document to open it.  This is dumb because:
    • They have to do that to open the document they are reading in the first place.
    • It’s a double-click by default.
  • We really need a beginner’s tutorial.
    • Tutorial/intro should be purely optional, easy to kill, and not get in the way, but it should be obvious and discoverable, too.
      • Notification area balloon that pops up each time you log in until you click it and choose to either go through the tutorial or tell it to shut up.
      • Icon on the Desktop that you can delete
    • Maybe include a downloadable video tutorial, too?  Won’t fit on the CD unless you use a format specially made for screencasts?  Animated GIF?
    • Don’t give false expectations:  “Ubuntu has a wealth of programs to choose from – over 19,000 at last count!”  Most of these are just components of other programs, and many are useless garbage.  Be realistic and then new users won’t be so pissed off when things don’t work.  Sell Ubuntu by making Ubuntu better, not by lying about what it’s capable of.
    • “Ubuntu is free of charge and open source, and is created and maintained by volunteer/Canonical employees.  If you’re having trouble, remember that there’s probably a way to do what you want, even if it’s not the way you’re used to.   For instance, instead of browsing the web with Internet Explorer, Ubuntu comes with Firefox web browser, which is stable, extensible, blah blah.  (You can install Firefox in Windows and OS X too, but in Ubuntu it’s the default browser.)  Instead of Microsoft Office, try OpenOffice or GnomeOffice, they’re under the “Office” tab in the Applications menu.  OpenOffice has much of the same functionality of MS Office, and can open your old files, too.  Instead of downloading .EXEs to install programs, we download all packages from the Ubuntu repositories, which ensures that it has been thoroughly tested and built specifically for Ubuntu...”
    • Maybe just make one of the Examples a PDF with a table of common actions in Windows, Mac OS X, and Ubuntu, both as a cheatsheet newcomer reference and to drive home the point that Ubuntu is not Windows; it is a different OS, just like OS X is a different OS from Windows.
  • Openoffice splash screen takes too long to load after double click.  Appears like nothing has happened.  Firefox has the same problem.  Always should have some kind of feedback.
  • After upgrading to a new kernel and booting into it x times, it should assume that everything’s working fine and pop up a notification balloon explaining what a kernel is and telling you it’s probably ok to remove the old one and this is how you do it.  Won’t appear again for that kernel, and can be easily turned off permanently for those people who are infuriated whenever the computer offers a helpful message.
  • When installing restricted drivers in Jockey
    • “In order to use your hardware more efficiently, you can enable drivers which are not free software.”
      • Let’s be realistic.  99% of users don’t care a bit whether they have the freedom to modify and redistribute their video drivers.  Most don’t even know how to write a bash script (and we should all be working towards a world where they’ll never have to)
    • There’s a long pause where it says “downloading and installing”, but the progress bar just sits there at 0%, appearing to be broken.  Feedback, please!
    • Jockey gives stupid unnecessarily scary message about how proprietary drivers from Ubuntu’s repositories “represent a risk to you”, as if they are somehow malicious or more buggy than the Free ones.  (Yeah, right.)   LP# 381805
    • Does the sideways screen widening attack thing, but that’s been fixed.
      • LP #278071: jockey-gtk weird installed driver display
  • Flash installer is cryptic
    • “Choose a plugin” provides three possibilities, but no explanation of what they are, what the benefits of each are, or what anything means.  (Screenshot)
    • “No description found in plugin database”.   Great.  Thanks.
    • Then it asks to install it again if I go to another tab that has Flash content without restarting first.
  • Sound themes:
    • should be a link to download more sound themes
    • When browsing for sound files, it’s not obvious where the sound themes are stored.  There is actually a link on the bottom left, which is helpful, but it doesn’t go there by default and is not obvious at the bottom of a list of drives.
    • Instead of a file chooser window, there should  be a dedicated System Sounds Chooser.  If you want a sound that’s not provided by that, then you can use a file chooser to select it.   But all the theme sounds should be available from a simple app with a previewer/player.
  • Fonts are too small and seem strangely fuzzy by default — weird, since they were working fine in my previous install.  Maybe settings are different.
  • Scrolling in Firefox is jerky no matter how I set up Compiz or turn it off.  (There are so many bugs filed about this I don’t even know which is the culprit and I don’t care to pursue it.)
  • Title bars keep screwing up, probably just Compiz.
  • Backspace in Firefox does nothing.
    • (Yeah right — like that’s ever going to be fixed.)
    • LP #60995: The backspace key pages up instead of going back in history
  • Touchpad tapping is enabled by default, and does not seem to turn off while typing, which causes me to click things by accident.

I should also have written down the stuff that I was impressed with, though, since there actually was a lot.  “Hey, that actually works out of the box now?  Nice!” Maybe I’ll do it again with Lubi or VirtualBox and keep more positive notes. 🙂