Fast software implementation of error detection codes

1 December 1995

journal article
Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking

Vol. 3 (6) , 640-651
https://doi.org/10.1109/90.477710

Abstract

Software implementations of error detection codes are considered to be slow compared to other parts of the communication system. This is especially true for powerful error detection codes such as CRC. However, we have found that powerful error detection codes can run surprisingly fast in software. We discuss techniques for, and measure the performance of, fast software implementation of the cyclic redundancy check (CRC), weighted sum codes (WSC), one's-complement checksum, Fletcher (1982) checksum, CXOR checksum, and block parity code. Instruction count alone does not determine the fastest error detection code. Our results show the computer memory hierarchy also affects performance. Although our experiments were performed on a Sun SPARCstation LX, many of the techniques and conclusions will apply to other processors and error detection codes. Given the performance of various error detection codes, a protocol designer can choose a code with the desired speed and error detection power that is appropriate for his network and application.

Keywords

This publication has 11 references indexed in Scilit:

Weighted sum codes for error detection and their comparison with existing codes
IEEE/ACM Transactions on Networking, 1994
Improving the efficiency of the OSI checksum calculation
ACM SIGCOMM Computer Communication Review, 1989
Computing the Internet checksum
Published by RFC Editor ,1988
Computation of cyclic redundancy checks via table look-up
Communications of the ACM, 1988
A tutorial on CRC computations
IEEE Micro, 1988
Efficient implementation of the OSI transport protocol checksum algorithm using 8/16-bit arithmetic
ACM SIGCOMM Computer Communication Review, 1987
The tea-leaf reader algorithm: an efficient implementation of CRC-16 and CRC-32
Communications of the ACM, 1987
Byte-Wise CRC Calculations
IEEE Micro, 1983
An Arithmetic Checksum for Serial Transmissions
IEEE Transactions on Communications, 1982
Cyclic Codes for Error Detection
Proceedings of the IRE, 1961