Rabbit Hole

      This morning, Tam was looking at a Mars-lander parachute with a message encoded in the panels.  Over her shoulder, I thought it was a Russian Soyuz parachute, which have patterns used to check orientation and spin.

     That led me to look up Gray code, which is a binary code that only flips one bit per increment.  Unclear?  Look at it this way: real binary numbers, the way a guy with two fingers counts, run like this:
0000
0001
0010
0011
0100
0101
0110
0111
     The step from 0 to 1 and from 10 to 11 (or 2 to 3, as you and I count) only flip one bit; but going from 1 to 10 and from 11 to 100, two bits change state.

     Who cares, right? That's just how robots count anyway.  But if they count wrong, it makes trouble for us, and if the robot is counting how far we're turning a knob (or a steering wheel!), the encoder is a physical device, maybe a light source and a disc with digital numbers encoded as clear or opaque spots read by a phototransistor array -- and no matter how carefully the blame thing was made, the bits aren't going to change at the exact same time: the robot might miscount on the steps from 1 to 10, 11 to 100, and every one of them (a lot, as the count continues) that flips more than one bit at once. 

     We're smarter than robots; let's help 'em out -- and that's what Frank Gray did, putting the numbers in a different order:
0000
0001
0011
0010
0110
0111
0101
     Now only one bit changes for each step; the robot can't be confused when the count increments.  It's only got to track the single change.

     If you chart this Gray code order on a conventional-order number line, it turns into a funny set of hops of greater and smaller distances (see the Wikipedia page) -- and looking at it, I was struck by how closely it resembled one representation of output from the high-speed data encoding behind digital television.  Scrolling down, I discovered that's not a coincidence: because it results in more robust data transmission under noisy conditions, Gray coding works with forward error correction in digital modulation schemes, of which U.S. 8-VSB digital TV is one (albeit something of an ugly stepchild; the next-generation ATSC 3.0 uses a better method, called OFDM).

     And that's this morning's rabbit hole.  Frank Gray, who died in 1969, worked for Bell Labs, where he made many contributions to early television.  He's the father of the flying-spot scanner, which is the backwards of a TV camera: scan the thing you want to televise with a single bright dot of light, picking up up the reflected intensity with a single cheap photocell: the output is the same as the raw output of a TV camera tube. Slide scanners once used this, with a tiny TV picture tube as the moving light source, much cheaper than a video camera tube.  Gray was a graduate of Indiana's own Purdue University, with a degree in physics.

     (If you'd like to sink even deeper into the geekery, try Trellis encoded modulation, the trick that lets us push the Shannon limit for communications speeds over a noisy link -- and it turns out they're all noisy in the real world.  Digital TV uses Trellis encoding, too -- look, that's a whole lot of bits to pack into not very much space on the dial, static and all, and if they didn't mash it down very compactly, all the basketballs and footballs and hockey pucks would be jerkily-moving little squares, and the numbers on the players would barely be readable.  Oh, Claude Shannon?  That's a whole other bundle of brilliance, father of modern digital telecommunications and a first-rate juggler, too.  If you haven't seen The Bit Player, perhaps you should.)