Error-Detection Codes: Algorithms and Fast Implementation

Abstract—Binary CRCs are very effective for error detection, but their software implementation is not very efficient. Thus, many binary non-CRC codes (which are not as strong as CRCs, but can be more efficiently implemented in software) are proposed as alternatives to CRCs. The non-CRC codes include WSC, CXOR, one’s-complement checksum, Fletcher checksum, and block-parity code. In this paper, we present a general algorithm for constructing a family of binary error-detection codes. This family is large because it contains all these non-CRC 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 non-CRC codes that have minimum distance 4 (like CRCs) and efficient software implementation. Index Terms—Fast error-detection code, Hamming code, CRC, checksum