Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
The tea-leaf reader algorithm: an efficient implementation of CRC-16 and CRC-32
Griffiths G., Stones G. Communications of the ACM30 (7):617-620,1987.Type:Article
Date Reviewed: Apr 1 1988

The Cyclical Redundancy Check (CRC) is an effective error-detecting checksum technique for data packages. The CRC relies on forming logical relationships between the bits of a message by shifting the message in a register. It is usually described and performed in a bitwise manner.

This paper shows a method for drastically saving execution time. For a fixed length word, the relationships can be precomputed and stored in tables. This allows the encoding to be done by table-lookup at the byte level rather than by calculation at the bit level. Savings of at least an order of magnitude are reported.

The paper is economical in presentation. The information provided allows a programmer to implement the tea-leaf reader algorithm if he or she is already conversant with CRCs. The reader not conversant with CRCs needs to refer to the references. The strategy for reducing run-time is a general one and makes the technique an interesting case study even for those who are not directly interested in CRCs. Unfortunately the authors limit their discussion of strategy inspiration to the point that there is not an adequate justification of the algorithm name “tea-leaf reader.” Having read and understood the paper, I can guess, I think.

Reviewer:  M. Whitelaw Review #: CR112156
Bookmark and Share
 
Error-Checking (B.4.5 ... )
 
 
Coding And Information Theory (E.4 )
 
Would you recommend this review?
yes
no
Other reviews under "Error-Checking": Date
Error detecting decimal digits
Putter P., Wagner N. Communications of the ACM 32(1): 106-110, 1989. Type: Article
Feb 1 1990
Weighted sum codes for error detection and their comparison with existing codes
McAuley A. IEEE/ACM Transactions on Networking 2(1): 16-22, 1994. Type: Article
Jan 1 1995

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy