Analysis of checksums, extended-precision checksums, and cyclic redundancy checks

摘要

The effectiveness of extended-precision checksums is thoroughly analyzed. It is demonstrated that the extended-precision checksums most effectively exploit natural redundancy occurring in program codes. Honeywell checksums and cyclic redundancy checks are compared to extended-precision checksums. Two's complement, unsigned, and one's complement arithmetic checksums are treated in a unified manner. Results are also extended to any general radix-p arithmetic checksum. Asymptotic and closed-form formulas of aliasing probabilities for the various error models are derived.