Efficient CRC remainder coefficient generation and checking devi

Details Efficient CRC remainder coefficient generation and checking devi Efficient CRC remainder coefficient generation and checking devi

1995-10-11

1997-04-08

Baker, Stephen M.

Excavating

371 376, H03M 1300

Patent

active

056195168

ABSTRACT:
A parallel CRC remainder coefficient generator (100) and method (1100) are described for providing efficient error detection in a digital data communication system. This method calculates a K-bit CRC remainder m data bits at a time, where m can be less than, equal to, or greater than K, and where the processing of each of the m bits requires a total of j, K-bit table look-ups into a total of j tables of 2.sup.b entries each, where m=jb. It also requires one m-bit exclusive-or operation, a total of (j-1) K-bit exclusive-or operations, and one (K-m)-bit exclusive-or operation if m<K. An implementation of a 16-bit CRC using the new method (700) in a 16-bit DSP processor with m=16, j=2 and b=8 reduces processor loading by 43% relative to the fastest prior art method which uses m=8, j=1, and b=8. An implementation of a 32-bit CRC using the novel method (600) in a 16-bit DSP processor with m=6, j=2, and b=8 reduces the processor loading by 41% relative to the fastest prior art method which uses m=8, j=1, and b=8. Hardware implementation of the new method provides similar benefits with respect to throughput and area.

REFERENCES:
patent: 4473902 (1984-09-01), Chen
patent: 5325372 (1994-06-01), Ish-Shalom
Weissberger, A., "Control Chip Handles Error Checking and Character-Based Protocols Easily", Electronics, Mar. 27, 1980, pp. 151-155.
Tong-Bi Pei and Charles Zukowski, "High-Speed Parallel CRC Circuits in VLSI," IEEE Transactions on Communications, vol. 40, No. 4, Apr. 1992.
Dilip V. Sarwate, "Computation of Cyclic Redundancy Checks Via Table Look-Up," Communications of the ACM, vol. 31, No. 8, Aug. 1988.
Georgia Griffiths and G. Carlyle Stones, "The Tea-Leaf Reader Algorithm: An Efficient Implementation of CRC-16 and CRC-32," Communications of the ACM, vol. 30, No. 7, Jul. 1987.
Yoseph Linde, "A Fast Algorithm for Calculating Cyclic Redundancy Checks," Correlations, Fall 1979.
Guido Albertengo and Riccardo Sisto, "Parallel CRC Generation," IEEE Micro, Oct. 1990.
D. Bertsekas and R. Gallager, Data Link Control and Communication Channels p. 548.
Karl M. Helness, "Implementation of a Parallel Cyclic Redundancy Check Generator," Computer Design, Mar. 1974.
Aram Perez, "Byte-wise CRC Calculations," IEEE Micro, Jun. 1983.
Tenkasi V. Ramabadran and Sunil S. Gaitonde, "A Tutorial on CRC Computations," IEEE Micro, Aug. 1988.

Affiliated with

Also associated with

Rating

Efficient CRC remainder coefficient generation and checking devi does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Efficient CRC remainder coefficient generation and checking devi, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient CRC remainder coefficient generation and checking devi will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2401846