Confusion-Free Codes

Copyright ©2003 by Paul Niquette. All rights reserved.

Five different messages in the puzzle...
  • High Speed
  • Medium Speed
  • Slow Speed
  • Zero Speed
  • Stuck Bits Detection
...means that we need more than two bits for each code.  Three bits will give us eight combinations to work with, but that last requirement -- to detect stuck bits -- will take away two of them: 000 and 111. 

The remaining six combinations would seem to be enough.  We might, for example, let...

  • 110 = High Speed
  • 101 = Medium Speed
  • 100 = Low Speed
  • 011 = Zero Speed
However, the sophisticted solver will want to consider how, as repeating patterns, each will appear to the train...
110110110... 
101101101...
100100100...
011011011...
Now, depending on exactly when the train happens to "sync up" on the incoming signal at the beginning of each block along the right-of-way, it is clear that some codes can be confused with others.  Thus a Zero Speed command 011 can be confused with a High Speed command 110 -- hey, throughout the block.  Can't have that.

A little foozling will reveal that at least one more bit-per-code is required to assure synchronization.  For example, we might require that each of those codes begin with a 1...

  • 1110 = High Speed
  • 1101 = Medium Speed
  • 1100 = Low Speed
  • 1011 = Zero Speed
...oh, but that won't work either, because the patterns are repeating, now the Zero Speed command can be confused with the Medium Speed command despite that "sync" bit there.  With four bits we have 16 combinations, so surely that should be enough to do the job.  But how?

The solution is to assign more than one pattern of bits to each command such that no matter when the train begins reading them, the interpretation will be the same.  Here, then, is one such solution.
 
Command
Confusion-Free
Codes
  • High Speed
  • Medium Speed
  • Slow Speed
  • Zero Speed
  • Stuck Bits
  • 0001, 0010, 0100, 1000
    0011, 0110, 1100, 1001
    0111, 1011, 1101, 1110
    0101, 1010
    0000, 1111

    Multiple bit-patterns like these have also been called "comma-free codes," but there are many differences here from the scheme to which the conventional use of that expression applies, as you will see in the solution to Conservation of Bits, wherein the objectives are...

    • to compress not to expand representations,
    • to use one code per symbol, not repetitions,
    • to decode variable-length not fixed-length patterns, 
    • to synchronize once and for all at the beginning of a data string, and
    • to support one channel of data not to select from successive blocks.
    ...hence the coinage adopted here, Confusion-Free Codes.


    Epilog:BART (Bay Area Rapid Transit)

    The inspiration for this puzzle comes from the renowned automatic train control system at BART.  A total of eight speed codes are delivered from the wayside to trains as repeating 6-bit codes...

    • 100000 = 0 mph
    • 100001 = 6 mph
    • 101001 = 18 mph
    • 100101 = 27 mph
    • 100011 = 36 mph
    • 101011 = 50 mph
    • 100111 = 70 mph
    • 101111 = 80 mph
    Actually, six 6-bit combinations are assigned to each speed code.  For example,...

    100000 = 010000 = 001000 = 000100 = 000010 = 000001 = 0 mph

    Thus, repeated transmissions from the wayside can be received by the train, beginning at any bit-time after it enters a track block, and after receiving a total of six bits, the train will be able to recognize the intended speed code without confusion.  You will note that out of 64 combinations of 6-bits, 28 are not assigned for signaling but instead serve to detect faults in the communications system, including Stuck Bits 000000 and 111111.


     


    Home Page
    Puzzle Page
    Reasoning Meets the Rails
    The Puzzle as a Literary Genre