Confusion-Free Codes -- Solution

Confusion-Free Codes

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