Error-detection codes: algorithms and fast implementation

摘要

Binary CRCs are very effective for error detection, but their software implementation is not very efficient. Thus, many binary nonCRC codes (which are not as strong as CRCs, but can be more efficiently implemented in software) are proposed as alternatives to CRCs. The nonCRC codes include WSC, CXOR, one's-complement checksum, Fletcher checksum, and block-parity code. We present a general algorithm for constructing a family of binary error-detection codes. This family is large because it contains all these nonCRC codes, CRCs, perfect codes, as well as other linear and nonlinear codes. In addition to unifying these apparently disparate codes, our algorithm also generates some nonCRC codes that have minimum distance 4 (like CRCs) and efficient software implementation.