Computing, read from an encoder's source

Co-authored by Claude · Version 1.0.0, changed in rev 123

In the late 1940s Richard Hamming worked at Bell Labs on the Model V, a computer built from electromechanical relays. During the week the machine stopped and signalled an operator when it detected a relay error. At weekends and after hours nobody was there, so it moved on to the next job, and Hamming had to restart his programs from the beginning. In a taped interview he put the question that became a code: if the machine can detect an error, why can't it locate the position of the error and correct it? He published his answer in 1950. It is still in use, in the memory of computers, and it is one of a family of ideas about what can be said reliably through a channel that is not.

The computing library for DKE, the Deterministic Knowledge Engine, writes down some of the family in DKE Python, and this essay teaches the subject by reading it. You record one kind of fact. A binary code is written as its words, each a string of 0 and 1, and the library's rules conclude the Kraft sum of the code, whether any word begins another, and whether the code is therefore prefix-free, so that a received string can be read without separators. The answer names the pair of words that breaks it, and correcting a word withdraws the answers it supported. The second half of the library calculates: the CRC-32 and Adler-32 checksums, the Luhn and ISBN-13 check digits, numbers in any base from 2 to 36, the Hamming code with its single-error correction, Shannon's entropy, Huffman code lengths, binary search and Dijkstra's shortest paths. Every program below runs as shown once the library's source file has been compiled into a store, and every output is copied from a run.

1. A code that can be read without gaps

Samuel Morse first meant to send only numerals, from a codebook. In 1840 Alfred Vail extended the code to letters, and he chose the lengths by counting: he estimated the frequency of English letters from the movable type in the type cases of a newspaper in Morristown, New Jersey, and gave the commonest letters the shortest sequences. E, the commonest, is a single dit. The cost is that the code is not a prefix code. E is the beginning of I, which is two dits, so a receiver that hears two dits cannot say whether it is one I or two Es, and the operator needs a pause: a dit is one unit of time, a dah three, the gap inside a letter one, the gap between letters three dits and the gap between words seven.

A code in which no word is the beginning of another needs no pause. The reader walks down the received string until a word is complete, and that word is the next one. The library writes a code as a word for each string and a pair for each two words, and its rule is a statement about the pairs:

@rule
def prefix_free():
    for c in Code:
        if none(p in Pair: p.code == c and p.prefix == True):
            c.prefix_free = True

There is also a number that bears on whether such a code can exist. Each word of length n takes up 2 to the minus n of the space of all strings, and the Kraft sum is the total. Kraft showed in his master's thesis of 1949 at MIT that lengths with a sum of at most 1 are exactly the lengths a prefix code can have, and McMillan proved in 1956 that the same bound holds for every uniquely decodable code, not only prefix ones. Here are three codes. The first is a prefix code. The second has the same Kraft sum and is not one. The third has the trouble of E and I in Morse's alphabet, since 0 begins 00, and a sum above 1:

import computing

computing.code("good", ["0", "10", "110", "111"])
computing.code("bad", ["0", "01", "11"])
computing.code("gappy", ["0", "1", "00"])
print(computing.prefix_free_codes(), computing.kraft_sum("good"), computing.kraft_sum("bad"), computing.kraft_sum("gappy"))
print(computing.breaking_pairs("bad"), computing.breaking_pairs("good"), computing.breaking_pairs("gappy"))
o = current(computing.Code.gappy.oversubscribed)
print(o.value)
reason = why_not(computing.Code.bad.prefix_free)
print(reason)

['good'] 1.0 1.0 1.25
['0 01'] [] ['0 00']
True
rule `computing.prefix_free` needs computing.Code[bad].prefix_free__none1 to be absent, and it is present

The first code is prefix-free, with a Kraft sum of exactly 1: it is complete, and no string of bits is left over. The second also has a Kraft sum of 1, and it is not prefix-free, because 0 begins 01. The lesson is the one the second line makes: a sum of 1 is necessary and not sufficient, and the pair that makes the difference is named. The third has a sum of 1.25. No uniquely decodable code has words of lengths 1, 1 and 2, so the library marks it oversubscribed and no choice of bits would help. The last line is the answer to why the second code is not prefix-free: a rule needs a thing to be absent, and it is present, and the row of the pair is the thing.

2. Checksums

A checksum is a short number computed from a longer message, sent beside it, so that the receiver can compute it again and compare. W. Wesley Peterson proposed cyclic codes for detecting errors in networks in 1961, in a paper with D. T. Brown, and the cyclic redundancy check takes its name from them. A CRC of n bits detects any single burst of damage no longer than n bits, which suits channels where errors come in runs. CRC-32 is in Ethernet, gzip, zip and PNG. The catalogue of CRC algorithms gives the check value for the nine characters "123456789" under the one the library calls CRC-32 as 0xcbf43926, which is 3421780262. The library computes it bit by bit. Mark Adler made a faster and less reliable checksum in 1995, which the zlib compression library uses: two sums, A starting at 1 and B at 0, both modulo 65521, the largest prime below 65536. Its value for "Wikipedia" is 0x11E60398. Neither is cryptographic, since an attacker can recompute either after editing a message.

import computing

print(computing.crc32("123456789"), computing.to_base(computing.crc32("123456789"), 16))
print(computing.crc32("hello"), computing.crc32("hellp"), computing.crc32(""))
print(computing.adler32("Wikipedia"), computing.to_base(computing.adler32("Wikipedia"), 16))
print(computing.adler32("hello"), computing.adler32("hellp"))

3421780262 cbf43926
907060870 3138956147 0
300286872 11e60398
103547413 103612950

The check value of the catalogue is reproduced, and so is the value for "Wikipedia". Changing one letter of "hello" changes the CRC beyond recognition and the Adler sum by 65,537, which is the weakness of the second on short messages: its A sum has not yet wrapped. The empty message has the CRC 0. The numbers in other bases come from to_base(), which writes a number in any base from 2 to 36 with the digits 0 to 9 and a to z, and from_base() reads them back:

import computing

print(computing.to_base(255, 2), computing.to_base(255, 16), computing.to_base(123456789, 36), computing.from_base("21i3v9", 36), computing.from_base("ff", 16))

11111111 ff 21i3v9 123456789 255

3. Check digits

Hans Peter Luhn of IBM devised a check digit that is still on credit cards, and was granted a US patent in 1960, for a hand-held mechanical device that computes it. Double every second digit from the right, subtract 9 from any result above 9, and the sum of the digits should be a multiple of 10. It is used in IMEI numbers, the numbers of credit cards, Canadian social insurance numbers and many more. It is designed to protect against accidental errors, not malicious ones: it catches every single-digit error and almost all swaps of neighbouring digits, and misses 09 for 90. The International Standard Book Number came from the Standard Book Number devised in 1966 for the bookseller W. H. Smith by Gordon Foster, a professor of statistics, and became ISO 2108 in 1970. Since 1 January 2007 books carry thirteen digits, with the prefix 978 that is compatible with the barcodes of shop goods, and the check weighs the digits 1 and 3 alternately. The page that gives the standard's example, 978-0-306-40615-7, also names its blind spot: it misses a swap of neighbouring digits that differ by 5.

import computing

print(computing.luhn_valid("17893729974"), computing.luhn_valid("17893729970"), computing.luhn_valid("17893729947"))
print(computing.isbn13_valid("9780306406157"), computing.isbn13_valid("9780306406158"), computing.isbn13_valid("9780306401657"))

True False False
True False True

The number 17893729974 is the worked example in the usual account of the algorithm. Changing its last digit is caught, and so is swapping its last two. The ISBN 9780306406157 is valid and its last digit changed is not. But the third ISBN is the first with its 6 and 1 swapped, and the check accepts it, as the blind spot predicts.

4. A code that corrects

Hamming's answer to his own question was to arrange the check bits so that each covers a different overlapping set of the data bits, and a pattern of failed checks points at the place of the error. Hamming(7,4) puts three parity bits among four data bits, a word of seven, with a rate of 4/7. The code has a distance of 3: any two valid words differ in at least three bits, so a word with one bit flipped is nearer to its original than to any other word, and the decoder can put it right. With an extra parity bit the code is the ECC memory of computers. The library encodes four bits to seven and decodes seven to four after correcting one flip:

import computing

print(computing.hamming_encode(11), computing.to_base(computing.hamming_encode(11), 2), computing.hamming_decode(51))
w = computing.hamming_encode(11)
bad = w ^ 4
print(w, bad, computing.hamming_decode(bad), computing.hamming_distance(w, bad))
worse = w ^ 4 ^ 1
print(computing.hamming_decode(worse), computing.hamming_distance(w, worse))
ok = 0
for d in range(16):
    c = computing.hamming_encode(d)
    for k in range(7):
        if computing.hamming_decode(c ^ (1 << k)) == d:
            ok = ok + 1
print(ok, 16 * 7)

51 110011 11
51 55 11 1
14 2
112 112

Eleven is encoded as 51, which is 110011 in binary and which decodes back to 11. A word with one bit flipped, 55, still decodes to 11, one bit away. A word with two bits flipped decodes to 14, wrongly and without notice: the code cannot tell, and the distance of 2 is more than it can repair. The last line tries every one of the sixteen words with every one of the seven single flips, and all 112 come back right.

5. Information and the shortest code

Claude Shannon published "A Mathematical Theory of Communication" in the Bell System Technical Journal in July and October 1948, and among its ideas is the bit as a unit of information. The entropy of a source, the sum over its symbols of minus p log₂ p, is the average number of bits each symbol needs at best. A source of two equally likely symbols has an entropy of 1 and one of four has 2.

David Huffman was a student at MIT in 1951, in a class of Robert Fano, who offered the class a term paper or a final examination. The paper was to find the most efficient binary code. Huffman could not prove that any code was the best, and then came up with a tree built from the least frequent symbols up, which was optimal, and he published it in 1952, in "A Method for the Construction of Minimum-Redundancy Codes". Fano had worked with Shannon on a similar code, which builds its tree from the top and does not guarantee the best. Prefix codes of the Huffman family are in DEFLATE, JPEG and MP3, though most of those use fixed tables and not codes built from the data. The library finds the lengths by merging the two lightest groups at each step, and the program compares the cost of the code with the entropy. The frequencies, in percent of a message of six letters, are invented:

import computing

print(computing.entropy([1, 1]), computing.entropy([1, 1, 1, 1]), computing.entropy([5, 2, 1, 1]), computing.entropy([1, 0]))
freqs = [45, 13, 12, 16, 9, 5]
lengths = computing.huffman_lengths(freqs)
print(lengths, computing.huffman_lengths([5, 2, 1, 1]))
cost = 0
for i in range(len(freqs)):
    cost = cost + freqs[i] * lengths[i]
print(cost / 100, computing.entropy(freqs))

1.0 2.0 1.6577427265048887 0.0
[1, 3, 3, 3, 4, 4] [1, 2, 3, 3]
2.24 2.219879978107314

The commonest letter gets a word of 1 bit and the two rarest 4. The average is 2.24 bits a letter, against an entropy of 2.22, so the code gives up 0.02 bits on the best any code could do. No code can average fewer bits a symbol than the entropy, and Huffman's comes within one bit of it, the best that a code giving each symbol its own word can do. A source with one symbol has an entropy of 0, as the last value of the first line shows.

6. Finding, and the shortest path

John Mauchly first mentioned binary search in 1946, in the Moore School Lectures. Before Derrick Henry Lehmer published a version for lists of any length in 1960, the published versions handled only lists one shorter than a power of two. Jon Bentley assigned it to professional programmers and found that ninety percent of them failed to write a correct one after several hours, and the binary search of the Java library had an overflow bug that stayed undetected for more than nine years. A search of a sorted list halves the range at each probe, so a list of 1,000 needs at most 10 probes and a list of 1,000,000 needs 20. The library counts the probes for the indexes 0 to n − 1:

import computing

print(computing.binary_search_steps(1000, 499), computing.binary_search_steps(1000, 0), computing.binary_search_steps(1000000, 999999), computing.binary_search_steps(1000000, 0))
print(computing.binary_search([2, 3, 5, 7, 11, 13], 7), computing.binary_search([2, 3, 5, 7, 11, 13], 8))

1 9 20 19
3 -1

The middle of a thousand takes one probe, the first index of a thousand takes nine and the last of a million takes twenty. In the list of the first six primes, 7 is at index 3, and 8 is not there. The library's search is written as a loop of at most 64 halvings, since the language has no while: no list an int can index needs more.

Edsger Dijkstra conceived his shortest-path algorithm in 1956, as he said in an interview of 2001, in about twenty minutes while shopping in Amsterdam with his fiancée, sitting at a café terrace, and designed it without pencil and paper. He was at the Mathematical Center and wanted a problem that people outside his field could follow, so he chose the shortest trip from Rotterdam to Groningen, and ran it on the ARMAC computer on a simplified map of 64 Dutch cities. He published it in 1959. It gives the shortest distances from one node to all the rest, for edges with non-negative weights, and with negative weights it can return wrong answers. It is the basis of the network routing protocols OSPF and IS-IS and of the routing of maps. Here is a graph of five nodes, with directed edges of the form from, to and length, and the distances from two nodes:

import computing

edges = [[0, 1, 10], [0, 3, 5], [1, 2, 1], [1, 3, 2], [2, 4, 4], [3, 1, 3], [3, 2, 9], [3, 4, 2], [4, 0, 7], [4, 2, 6]]
print(computing.dijkstra(5, edges, 0), computing.dijkstra(5, edges, 2))

[0, 8, 9, 5, 7] [11, 19, 0, 16, 4]

From node 0 the nearest is node 3 at 5, then node 4 at 7, node 1 at 8 by way of node 3, and node 2 at 9. The direct edge from 0 to 1 of length 10 loses to the way through 3. A node that cannot be reached keeps the distance 1,000,000, so a path must be shorter than that.

7. What the library leaves out

A code's pairs grow as the square of its words, so a code is for a few dozen words. Hash functions beyond the two checksums, and any string that is not made of characters with codes 0 to 255, are not here, since an int has 64 bits and a 64-bit hash that wraps would be refused. The language has no while, so every loop is bounded and the bound is stated in each script's comment, and a list holds one type, so Huffman's merging keeps its weights and its members in lists of their own. Dijkstra's graph is a list of edges and a handful of nodes. A real system uses a tested library for a checksum, and what this one gives is the written reason and the same digits on every machine.

Closing

Much of computing is the care taken over a message that must arrive as it was sent, and the care has a short history. Vail counted type, Peterson and Hamming arranged check bits, Shannon measured what a message is worth in bits and Huffman built the shortest code for it, Luhn and the booksellers protected numbers that people copy by hand, and Dijkstra found the way from Rotterdam to Groningen in a cafe. The library keeps their procedures where a reader can run them and ask about them. It names the pair of words that makes a code ambiguous, gives the checksum that every system agrees on, and shows by the same arithmetic where a code stops working. And because each conclusion names the words it rests on, one corrected word corrects what depended on it.