Error-detection codes: algorithms and fast implementation
Author:
- 17 January 2005
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 54 (1) , 1-11
Abstract
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.Keywords
This publication has 10 references indexed in Scilit:
- Performance of checksums and CRCs over real dataIEEE/ACM Transactions on Networking, 1998
- Fast software implementation of error detection codesIEEE/ACM Transactions on Networking, 1995
- Comments on "Weighted sum codes for error detection and their comparison with existing codes"IEEE/ACM Transactions on Networking, 1995
- Error Detecting Codes1995
- Weighted sum codes for error detection and their comparison with existing codesIEEE/ACM Transactions on Networking, 1994
- Computation of cyclic redundancy checks via table look-upCommunications of the ACM, 1988
- A tutorial on CRC computationsIEEE Micro, 1988
- Byte-Wise CRC CalculationsIEEE Micro, 1983
- An Arithmetic Checksum for Serial TransmissionsIEEE Transactions on Communications, 1982
- The Theory of Error-Correcting Codes1977