You are here

Techniques

 

The ideas behind error-correcting codes are not really difficult, they just take a few pages to explain. The explanation is entirely verbal and symbolic, and does not require conventional mathematics. Suppose the following phrase is to be protected from errors that might occur when it is later mechanically read:

 

joy of a misty dawn

 

Careful application of redundancy is one of the keys to protection. For example, the

phrase could simply be replicated three times. When the copies were later mechanically

read, if any two of them matched, one of the two matching copies could be taken as correct. That would be a form of “majority rule.” If none of the three matched, there would be no majority and an error would be reported.

 

The problem with such a simple approach is not just that it wastes space, but that the method itself is prone to systematic error. A mechanical reader that misinterpreted one

copy could easily misinterpret the other copies in exactly the same way. For example, if the mechanical reader frequently misinterpreted the symbols j and i, then all three copies could match and be incorrect at the same time.

 

More useful is what Otto Schmitt (1913–1998) called “non-replicate redundancy.” More

than one copy is kept, but each in a different guise. In this case, full copies are not needed

at all; compressed copies that are functionally related to the full copy will suffice.

 

Error detection

 

The phrase to be protected can be compressed by repeatedly mapping pairs of adjacent

symbols into a single symbol. Suppose for illustration that the only symbols of interest are the lower-case letters of the English alphabet, plus a null symbol representing blank space. Arrange the symbols in alphabetic order, with the blank first, so that each symbol has a successor. Thus a is the successor of blank, b is the successor of a, c of b, and forth. The last symbol of the alphabet, z, also has a successor; it merely wraps around to the beginning, making the successor of z be blank.

 

Now the line can be compressed to generate simple non-replicate redundancy in the following way. A blank space followed by any symbol is compressed to that symbol. An a followed by any symbol is compressed to the successor of that symbol. A b followed by any symbol is compressed to the second successor of that symbol (the successor of the successor). A c followed by any symbol is compressed to the third successor. And so forth. The entire set of compressions become the following 27 ×27 table with a regular structure:

(Below, the symbol represents a blank space.)

 

 

Now the process of compression begins by replacing the first pair of adjacent symbols with the corresponding value from the table. The first pair of symbols is jo. In row j and column o of the table is the symbol y. Therefore, the line

 

joy_of_a_misty_dawn

 

is rewritten as

 

yy_of_a_misty_dawn

 

Now the process repeats in the same way, replacing yy with the corresponding value from row y, column y of the table, which is w, giving

 

w_of_a_misty_dawn

As the table shows, any symbol followed by a blank space () is replaced by that symbol, so the line becomes

 

wof_a_misty_dawn

 

The process repeats until only a single symbol remains:

 

kf_a_misty_dawn

q_a_misty_dawn

qa_misty_dawn

r_misty_dawn

rmisty_dawn

disty_dawn

msty_dawn

ety_dawn

yy_dawn

w_dawn

wdawn

_awn

awn

xn

k

 

The final symbol in this sequence is a guard symbol representing the entire line, in this case k. Now the line can be written with that guard symbol in front, like this:

 

k joy of a misty dawn