Dear DDJ,
Per John Kodis's "Fletcher's Checksum" in the May 1992 DDJ, I ran Fletcher's algorithm through an ancient error-simulator program of mine, DATAERRS. DATAERRS tests various checksums and CRCs by finding whether or not they miss errors put into data packets. DATAERRS puts the errors into the packets in a fashion similar to that of a bad phone line, i.e., errors are weighted toward small data changes. Table 1 tells how many bad-data packets per 100,000 are missed by each of several methods.
Packet size and type
37-byte 233-byte
Method ASCII 3.25~
-----------------------------------------
Parity bit 4500 4400
8-bit XOR-sum 1300 1350
8-bit checksum 900 900
16-bit checksum 600 700
Fletcher's 70 50
super-cs 20 20
16-bit CRC 1 1
32-bit CRC 0 0
Doubled 16-bit CRC 0 0
Whether the "super_cs" checksum's performance is only good under DATAERRS or not, I don't know. Its grace is that on CPUs with parity flag bits (e.g. Intel 8008 through 486s), it is extremely easy to implement. By the way, slight changes to it ruin its efficacy.
DATAERRS has never detected any missed errors (over a few hundred million packets) when two different 16-bit CRCs (CCITT and CRC-16) are used in combination. It has also never missed errors using 32-bit CRCs. Furthermore, as the code in Example 1 suggests, DATAERRS has found the same "perfect" level of error detection from a single type of 16-bit CRC done twice: first on the data, then on the data shuffled (as you would shuffle a deck of cards). This result may have implications with regard to digital signatures. Creating or modifying a block of data to force a particular, known CRC should not be hard. But creating one that, after shuffling, has a particular, other, known CRC seems a bit more difficult--especially if the procedure is iterated a few times.
#define SWORD unsigned short
#define BYTE unsigned char
#define WORD unsigned int
/*** Do a Fletcher Checksum on a block of memory. ***/
SWORD mem_fletcher_cs(BYTE *mem, WORD how_many)
{
BYTE s1, s2;
s2 = s1 = 0;
while (how_many-) {
s1 += *mem++;
if (s1 == 255) s1 = 0;
s2 += s1;
if (s2 == 255) s2 = 0;
}
s2 += s1;
if (s2 == 255) s2 = 0:
s2 = 255 - s2;
s1 += s2;
if (s1 == 255) s1 = 0;
s1 = 255 - s1;
return(s1 * 256 + s2);
}
/*** Do a 16-bit checksum that DATAERRS says is very effective. ***/
SWORD super_cs (BYTE *xm, WORD how_many, SWORD cs)
{
while (how_many-){
cs += *xm;
cs = _rotl(cs, 1) + odd_parity(*xm++);
}
return(cs);
B. Alex Robinson
Maple Valley, Washington
John responds: It's interesting to compare the results listed by Mr. Robinson for the 16-bit checksum, Fletcher's checksum, the super_cs algorithm, and the 16-bit CRC. While these algorithms all have about a 1 in 65,000 chance of missing an error when fed random data, the number of errors reported under testing by the DATAERRS program varies by a factor of 700. The error-detection ability of any of these algorithms' type depends on the types of errors which occur most frequently in practice. Mr. Robinson's results dramatically show the extent to which this is the case.
Dear DDJ,
Statistics and data analysis require careful thought. Unfortunately, Roy Kimbrell's "Finding Significance in Noisy Data" (June 1992) repeats some common myths, fallacies, and pitfalls usually dealt with in beginning statistics courses.
First, he states, "It won't hurt to assume a normal distribution for the errors." The so-called "normal" distribution referred to here is the Gaussian distribution with density proportional to exp(-((x-m)/s * * 2), where m and s are the mean and standard deviation. Falsely assuming this distribution matters a great deal when we test individual values and cannot appeal to the central-limit theorem. Measurements with a minimum of 0 and an effective maximum at least several times the typical value are often badly skewed. Taking square roots of counts often give data with a distribution closer to Gaussian. Concentrations are often improved by logarithms, as with pH values.
Second, the article mislabels column 1 of Table 1 as the "probability that the value is significant." Each entry in this column is actually the probability (expressed as a percent) that a nonsignificant random value from a standard normal distribution will fall within the interval defined by the value in the second column. A probability of significance for individual values requires specification of both the fraction and distribution of values affected by the putative nonrandom cause.
Third, it ignores the effect of multiple tests. If the residuals ("errors") are independent, then random variation will result in an average of 8.4 days (365 *.023) falsely declared significant when 365 days are tested against two standard deviations. Serial correlation changes all probabilities in a difficult-to-calculate manner. Standard time-series analysis uses lagged correlations to model the data and give independent residuals.
Fourth, it blindly applies the proposed method to the flight data and fails to examine the predictions for sensibility. The operation of lattice filtering is opaque even after looking at the results in Roy's Figure 2. The predictions are sometimes more jagged than the raw data instead of smoother, as from December 2 to December 10. December 2 is predicted to be lower than any day previous. December 3 (a Sunday, I believe) is called significant for being medium instead of high, but a better prediction is that it should be relatively low, as are December 10, 17, 24, and 31. There is no attempt to show that these predictions are any better, in any sense, than the raw data for this series.
Fifth, Roy pretends that an after-the-fact search for causes of "significant" events has much of any meaning. One can almost always find something, which is why astrology and the like are still alive. To properly investigate the relationship between weather and plane flights, one must first code the weather for each day by either formula or a human who is ignorant of the flight data.
In summary, the contention that these adaptive filters "select significant events with precision" is highly questionable. The dependence of "significance" on the number of history days itself makes this clear. The reader should be wary before using this method as presented.
Terry J. Reedy
Newark, Delaware
Roy responds: Terry's first point is that we should take care when assuming a normal distribution. I do agree. However, he might have noticed that the results of the experiment depend only on the mean and standard deviation--which are distribution independent. The normal distribution was only used as an example illustrating the idea of significance. Though I neglected to say so in the article, I had done some checking. The differences between the expected and the actual counts of aircraft flights did seem to fit a normal distribution. (It is common for differences in values to fit a normal distribution even though the values come from some other distribution.) Formal tests of goodness of fit were unnecessary because the results of the experiment didn't depend on the data fitting a normal distribution.
I also agree with the second point--that the table labeled "confidence values from the normal distribution" could have been better labeled. But then, it was only an example showing how the standard deviation is related to significance.
And to the third and fourth points: Terry is, understandably, approaching adaptive filtering from a statistician's viewpoint. The process is amenable to statistical analysis, but it must be approached in a different way. The point of the adaptive filter discussed in the article is that large differences between the expected and actual counts are correlated with changes in the weekly pattern of high and low counts--not with the actual values of the counts. Another point is that these changes in the weekly pattern are often difficult to find using simple statistics.
Terry also suggests that I should have tried to rigorously prove that the technique works as advertised. I'm afraid that would have been flogging a dead horse. Adaptive filters have been in active use for at least ten years (in speech processing, communications filtering, and the like). I was only reporting on one of their applications.
Terry is correct in pointing out that after-the-fact searches for "significance" can prove that virtually any technique works. But there is a difference between searches for significance and a search for the reasons a technique is showing certain results. I looked at the weather and other events trying to find reasons for the technique's indications of significance. To do this, I read the Omaha World-Herald for the 365 days corresponding to the data. Where there were events that should have affected aircraft operations, I checked for indications of significance. Where there were indications of significance, I looked for events. (Though I didn't report them in the article, there were weak correlations with problems United Airlines was having with their aircraft during the spring of that year. Unfortunately, it's hard to quantify such events so they can be analyzed statistically.) The look at the weather and other events that might have affected aircraft operations was casually reported because it was a matter of curiosity only. I said as much in the article, though I suppose I should have been clearer.
I guess if this was to be a careful study of the application of a newly invented technique, I'd want to perform the kind of study you suggest. But because it would be boring to read about and would prove little, I am sure Dr. Dobb's would hesitate to publish such a report. The idea is to bring new techniques and tools to programmers. In this we've succeeded. Because of the article, the technique is being investigated at the Center for Disease Control in Atlanta to signal outbreaks of diseases, and at Texas A&I University to help project carrying capacities of range land for early stock adjustments.
Dear DDJ,
You printed a letter in the May issue titled, "A Little History" from Denys Tull. I am skeptical of several of Denys's conclusions, but take exception to one in particular.
If C compilers are recompiling every object module by using the #include statement, we had better tell the NSI committee and the compiler manufacturers! This will take them by surprise. I do not know of any compilers that recompile object libraries during each compilation. The existence of such compilers is doubtful.
Clearly, Denys should find out what C compilers are all about--especially the uses of the #include statement.
Gregory L. Filter
Battle Creek, Michigan
Dear DDJ,
Regarding the running discussion of the ideal swap macro for C, we have been debating this issue in the C User's Group (U.K.) journal recently. The storage-free swap method using XORs, as described by Bill Wilder in the July 1992 issue, is given in Glassner's excellent Graphics Gems (Academic Press, 1990). However, the author erroneously states that the macro works for any data type.
This is true in theory, but unfortunately ANSI C as it stands doesn't allow you to XOR noninteger data types, so the macro will work with char, int, and long, for example, but not with float or double.
Graham Mudd
Beckenham, England
Copyright © 1992, Dr. Dobb's Journal