Esteve Personal Blog

First of all I must apologize for not having written anything on the blog for so long, I haven’t been much creative lately, and I have had little time to spend on writing, I hope this summer will be more productive.

iPod shuffle has been one of the latest revolutionary products from Apple, it aims to listen to your music collection randomly. But how random is it ? My objective will be to evaluate how random songs are played, thus knowing a little more about the random number generator inside the shuffle.

First Implementation (No iPod used, yet):

The idea is to fill the iPod with a collection of mp3 files, connect it’s header output to the computer’s microphone line, let the iPod play the files and recognize each one, this will give a list of the shuffled files. Once this list is big enough it’s order can be studied to recognize playing patterns and evaluate how random it is.

Encoded MP3 files

The iPod will contain a set of mp3 files that will be easy to recognize when played back to the computer. An identification number will be given to each file, this number will be encoded as audio and then compressed to mp3.

To encode the number we will be using frequency modulation. For this first implementation I will be using a not very efficient but easy to recover modulation. The identification number will be converted to binary and then the audio file will be generated as follows:

• Insert a tone at FREQ_NEW hz.
• For each bit of binary id. number starting at MSB do:
• • Insert a tone at FREQ_SEPARATION hz
  • If the bit is 0, Insert a tone at FREQ_ZERO hz
  • If the bit is 1, Insert a tone at FREQ_ONE hz

To generate each tone I will use a sine at the specified frequency, to generate them I found a tool called sgen from siggen set of tools. This tool lets generate through command line raw audio files containing a single tone at a specified frequency. To generate each file from a number I used a shell script that receives as parameter the Id number and uses sgen to create an audio file.

As an example we will create the id audio file 91. The 91 to binary is 1 0 1 1 0 1 1, so the end file will contain the following tones:

• NEW
• SEPARATION
• ONE
• ZERO
• ONE
• ONE
• ZERO
• ONE
• ONE

As it can be seen this is not very space effective but is really easy to implement and to recover.

The script can be found here, it only requires siggen and lame.

Recognize each file :

Previous to do any attempt with a real iPod I implemented a program that recognizes each file. The input to this program is a WAV file with a number encoded inside as described above, the program will analyze the input and then output the number. This same technique will be used to recognize each file the shuffle is playing.

The objective is to be able to recognize each tone, this will be accomplished doing a Fourier transform of a sample of the file and try to detect a predominating frequency, once the frequency of each tone is recognized the conversion to a number is direct ( see encoding above ).

To perform the FFT I have used the fftw libraries. I go through the input file sampling chunks of it, and then detecting the main frequency from each.

I found this interesting example on how to use the fftw libraries to plot a spectrogram from a sample.

A first version of the program can be found here , it does well the recognition of files, I have tested adding noise to each of the files and seems to perform well, I will show the tests later on this post. The program needs the fftw to compile and expects an encoded wav file as input.

The File Set:

I have generated a set of about 500 files that will be uploaded to the iPod, these files have been generated with the gen_number.sh script and they have the particularity that each ID number is a prime number, this way when recognizing back each file, if the recognition returns a non prime number there is an error and the number should be discarded.

To test that the decoder program works well each of this file has been decoded back to its id number, none of the 500 files has failed the test.