don@allegra.UUCP (D. Mitchell) (03/29/84)
Subject: error detecting codes Here are the results of an experiment to test the quality of various error detecting codes. Numbers below are failures to detect errors out of 131072 tests on 128-bit messages. All error codes are 16 bit except the PUP which is 32. Number of Bits Incorrect Protocol 1 2 3 5 8 13 26 Method X.25 0 0 0 0 5 0 3 CRC 16 TCP/IP 0 3699 337 94 19 6 5 1's comp. sum PUP-I 0 2925 256 62 17 0 0 sum and rotate Brand X 0 7327 0 0 100 0 5 16 parities uucp 7687 3353 913 141 40 4 3 Ad Hoc (hash) 0 0 9 2 2 0 0 modulo 65521 (crypto) 4 1 3 4 1 3 2 DES CBC Comments: A good error code means more than a good hashing algorithm. DES is a nearly perfect hash, but fails to detect 1-bit errors. CRC, in addition to being a good hash, detects ALL small-number-of-bits errors. UUCP is terrible! Its error code was tested as a hashing function, but not as an error code, from what I have heard. TCP and PUP error codes are fast to computer. Mod 65521 and DES are too expensive to really use. CRC can be done faster than many people realize. Note that mod 65521 is mathematically related to CRC, and is almost as good.
gwyn@brl-vgr.ARPA (Doug Gwyn ) (03/31/84)
That was very interesting. You mean people really implement important communication protocols with such lousy ECCs? I thought everyone in that corner of the business had at least read Hamming's book on the subject. Tsk, tsk. Richard Lary told a funny story about the Chinese mathematician DEC kept around and let out of the closet just long enough to design an ECC for them whenever they needed one. The Digital Storage Architecture is supposed to have a phenomenally good ECC as a result.