Bit Reversal Permutation Access

It'll take me a while to get to my point, but stick with me.  Recently while I was waiting for a train, a freight train passed the station and I came up with an interesting thought experiment.  I wondered "where is that train going, what does its journey look like, and how could I find out?"  It's relatively simple to just Google the answer or look up satellite maps of the trains tracks, but that doesn't tell you information about where it was at what time, what speed it was doing, or something a little stranger like weather conditions.

Note: Before I get into things, I should point out that this is just a thought experiment.  Sometimes I like to think of problems and try to solve them just to keep my mind busy when I'm bored.  Sticking a random piece of electronics to a train would be a dumb and potentially dangerous thing to do.  Don't be stupid.  Now, on to the problem at hand.

I wondered could a tracking device be attached to the train to take readings and report back?  Of course it can, there's nothing too complicated about that.  A few sensors, a single board computer, a battery, and some powerful magnets to hold it in place and you're done.  But how does the data get back to you?  At the moment the Raspberry Pi 3 is the new hotness in the maker community and it comes with built in WiFi.  As the train makes its way across the countryside, instead of using the mobile phone network to return the information could the data be transmitted back to the user by latching on to fleeting connections to the internet via open WiFi hotspot, kind of like a monkey swinging from vine to vine in the jungle. #LabouredSimile

Now an arrangement like this where you have unpredictable and limited connection to the internet means you have to transmit the data in the most useful way possible.  Let's say the data is stored in regularly sampled records, what's the best order to transmit those back?  Well, the first thing I want to know is where the train is now.  The next most useful thing to transmit back isn't the next record, because it won't differ that much from the previously transmitted record.  What you really want next is the record half way between the start and the previously transmitted record.  This will fill in the missing data in a way that gives you the most useful information first.  If we continue this pattern you just keep filling in the records that are midway between the ones transmitted previously.

I thought about it and realised that if you have an incrementing binary counter, almost all you need to do is reverse the order of the bits in the counter and access the records in that order.  That gets you most of the way there, unfortunately it gives you the oldest data first.  To fix that, just invert the bits.  That sounds pretty complicated, but hopefully the animation below can hep you out.  It assumes we have 16 records to transmit and demonstrates the "In Order", "Reversed", and "Reversed & Inverted" methods.

Bit Reversal Permutation Access

You can see that the "Reversed & Inverted" method returns the data in the order required.  It returns the newest data first and keeps returning records in between already returned records.  After a bit of Googling I discovered this is called Bit Reversal Permutation, and is used in the process of calculating Fast Fourier Transforms.

There are a lot of assumptions in my scenario, like adequate WiFi strength, and power of two records.  It's just a bit of fun that as it turns out has a real world application.