Confusion-Free Codes

Copyright ©2003 by Paul Niquette. All rights reserved.
Modern train control systems provide speed commands from the wayside to the lead vehicle by digital codes electronically delivered via the running rails.  "Cab signaling," it's called. 

The track is divided into blocks.  As the train travels along each block, it receives its speed command for that block as a repeating bit pattern. Various factors determine the speed limit that must be enforced on the train when it enters any given block, including curves in the track and switch settings, station-stops and the presence of traffic ahead. 

Cab signaling must address several technical challenges...

  • Iron rails constitute a poor medium for communications, imposing exceptionally slow data rates: often fewer than 20 bits per second.
  • At high speeds, the train can move a considerable distance during the time required to receive and interpret a new speed code.
  • An inoperative or stuck signal must be detectable by logic in the cab so that the train can be put into its "safe state" -- stopped. 
  • By its own location, the train selects the next block for reading the speed code, unsynchronized with the signaling pattern in the rails.
  • All codes must be chosen to assure that the concatenation of bits in successive repetitions will not be interpretable as a counterfeit code.
That last requirement mandates the application of what we shall call "Confusion-Free Codes" and offers us an opportunity for a puzzle.

Suppose that the following messages are to be communicated to the train:

  • High Speed
  • Medium Speed
  • Slow Speed
  • Zero Speed
  • Stuck Bits Detection
Design a "confusion-free code" for the delivery of those five messages.

GO TO SOLUTION  PAGE