Decoding the Falcon
Occasionally an aircraft operator will send us data that is in a format we have never seen before. The aircraft maintainer has followed the manuals and downloaded a data file and sent this to us and, quite reasonably, he thinks we must be able to read it. He supplies all the information he has and wonders why answers are not immediately available.
One such case came up recently and our normal tools for examining data didn’t work, so we had to go back to first principles. In the next blog I will show how this was decoded, and the mystery we uncovered. In this blog, however I will show you some photographs of combs which I am sure you will enjoy.
Looking at Combs
Here are two identical plastic combs, one pink and one blue.
OK, for the pedants out there they’re not identical, because one is blue and one is pink, but you know what I mean; they are the same design. For the sake of this demonstration, we are always going to line up the bottoms of the comb. Also, we are going to ignore the narrow section on the right and focus on the broader part of the comb. Finally, for those readers unfamiliar with the parts of a comb, the individual bars of a comb are called tines.
Nicely Lined Up
If I put the pink one on top of the blue it covers it up like this:
The pink one covers the blue extremely well at this point. This is where the difference in position between the ends of the comb is zero. (Can you feel the mathematics creeping in yet?)
If I move the pink comb a fraction, it really does not cover the blue one well at all. You can see all the tines of the blue comb through the pink comb. The end of the pink comb has moved by about half the tine spacing.
When the pink comb has moved one tine space along, the coverage is almost as good as when we started. Very little of the blue can be seen, except for the first tine which is peeking out from the end of the pink comb.
Three tine spaces and the coverage is still quite good with just the end of the blue exposed.
Four and a half spaces and again, the coverage is poor.
Five tine spaces and again the coverage is good where the pink is over the blue, but more of the end can be seen.
Combs have a set of tines that are regularly spaced, and when we move one across another the two match well each time that the tines line up, and they do not match well when they don’t. This pattern repeats as the pink comb moves each tine space, and the further we go from perfect alignment the more blue we can see poking out the end.
Now, I used pink and blue combs because (a) it photographs quite nicely and (b) I don’t have a red comb. But it was essential that I had two combs of the same design.
Moving Towards Mathematics
In computing, we have an easy way of making two identical “combs” – we just copy the data and then we know it’s identical.
The mathematical name for how well two things match is correlation, and when we compare something with itself it’s called autocorrelation. The autocorrelation function shows how well a pattern of numbers matches with itself when displaced by one, two or more sample intervals.
Let’s do a simple example. Our comb is a list of numbers like this:
[0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1]
OK, it’s easier to see in a graph:
And the autocorrelation function for this is:
Mathematicians will writhe in horror at my engineering explanation, but here goes. With zero mismatch, the four one-high bars overlap perfectly, giving an overlap of four hence an autocorrelation value of four for zero displacement. When one copy is moved one or two spaces to the right (as below) there is no overlap, so the red autocorrelation for 2 steps is zero.
Then, when moved three spaces to the right, three bars overlap giving an autocorrelation value of 3 for three steps and so on.
Note: The zero displacement bar will always give the highest reading as, unsurprisingly, data always matches itself quite well. For convenience I like to divide the data by this value to normalize the graphs otherwise the y-axes can be numerically huge.
If we have some data that we think is going to be repetitive, an autocorrelation plot will tell us what the repetition interval is. More than that, if there are multiple patterns going on in the data, autocorrelation will point to each of the underlying patterns in the data.
The Falcon puzzle that I mentioned at the start of this blog began looking like this…
You can see I have normalized the first line to 1. There are peaks between 60 and 70 and around 130 which tell us about the underlying information. More in next week’s exciting episode!
P.S. Did you see how I managed to explain autocorrelation without any mathematical formulae? This is because there are different ways to compute this which give slightly different answers and I don’t want to get stuck in the mud of discrete vs continuous functions, and how to deal with repetition of the patterns. Thinking about comb overlap is a perfect analogy for the way we use this function to explore Flight Data Recorders.