From msuinfo!netnews.upenn.edu!newsserver.jvnc.net!darwin.sura.net!paladin.american.edu!europa.asd.contel.com!NewsWatcher!user Tue Feb 2 20:43:59 1993 Path: msuinfo!netnews.upenn.edu!newsserver.jvnc.net!darwin.sura.net!paladin.american.edu!europa.asd.contel.com!NewsWatcher!user From: levesque@rocky.ndhm.gtegsc.com (Allen Levesque) Newsgroups: sci.crypt Subject: CRC Encoding & Decoding Message-ID: Date: 25 Jan 93 20:00:32 GMT Sender: news@europa.asd.contel.com (News) Followup-To: CRC-16 Inquiry from Paul Rolland Organization: GTE Government Systems Lines: 116 Nntp-Posting-Host: rocky.ndhm.gtegsc.com THIS IS POSTED IN RESPONSE TO AN INQUIRY FROM PAUL ROLLAND (rol@grasp1.univ-lyon.fr) RE ALGORITHMS FOR CRC CODES. PERHAPS THIS MAY QUALIFY FOR INCLUSION IN A LIST OF FAQ'S. Subject: Encoding and Decoding CRC Codes Date: January 25, 1993 From: levesque@rocky.ndhm.gtegsc.com ENCODING AND DECODING CYCLIC REDUNDANCY CHECK (CRC) CODES A CRC-coded "message" consists of a specific number of data bits and a set of check bits, sometimes called the Frame Check Sequence (in HDLC parlance). If we let n be the total number of bits in the coded message, and k the number of data bits, then n-k equals the number of check bits (e. g., n-k = 16 bits when CRC-16 is used, and so forth). The coded message is constructed from two polynomials, the first an algebraic representation of the data sequence and the second the CRC generator polynomial. It is conventional to denote the data polynomial as G(X) and the code generator polynomial as P(X). Thus the k-bit data sequence is represented as G(X) = X^(k-1) + X^(k-2) + ... + X + 1, where X^0 = 1. As an example, the data sequence 10011 is represented as X^4 + + X + 1. Similarly, we arrange the CRC generator polynomial with highest power at the left, such as P(X) = X^16 + X^15 + X^2 + 1 (CRC-16). Stated simply, given a data polynomial G(X) and a CRC generator polynomial P(X), the encoding procedure is to construct a coded message polynomial F(X) that is evenly divisible by P(X). To accomplish this, we first multiply the data polynomial G(X) by X^(n-k), which has the effect of "shifting the data sequence to the left", leaving n-k open bit positions at the right-hand end; we then fill those positions with the remainder after dividing the shifted version of G(X) by the CRC generator polynomial. The steps are as follows: 1. Multiply the data sequence G(X) by X^(n-k), where n-k is the degree of the CRC generator polynomial. 2. Divide the resulting product [X^n-k][G(X)] by the generator polynomial P(X), producing a quotient and a remainder, which we call C(X). 3. Discard the quotient and add the remainder C(X) to the product, thereby producing the coded message polynomial F(X) = [X^n-k][G(X)] + C(X). The division is modulo-2 polynomial division, that is, in binary with no carries or borrows. Note that the bit length of the remainder C(X) is one less than the bit length of the CRC polynomial. This is always the case since, for example, any remainder after division by a degree-16 polynomial cannot have degree greater than 15. It is a simple matter to show that F(X) = [X^n-k][G(X)] + C(X) is evenly divisible by the CRC generator polynomial. The remainder of F(X) is the sum of the remainders of the two terms in F(X). The remainder of the first term is of course C(X). The remainder of the second term is simply the second term C(X) itself. Summing the two remainders modulo-2 produces zero, QED. EXAMPLE: (example adapted from McNamara, ref. 5) 1. Given: Data polynomial G(X) = 110011 = X^5 + X^4 + X + 1 Generator polynomial P(X) = 11001 = X^4 + X^3 + 1 G(X) contains 6 data bits; P(X) contains 5 bits, thus there are 4 check-bit positions, and n-k =4, so that n=10. 2. Multiplying the data sequence G(X) by X^4 yields the product: X^9 + X^8 + X^5 + X^4 (binary is 1100110000, ten bits long). 3. Dividing the product by P(X) gives a quotient of 100001 and a remainder C(X) = 1001. 4. The quotient is discarded and the remainder C(X) is added to the product to produce the coded message F(X) = 1100111001. The coded message is transmitted over a channel, and at the receive end, the decoder divides the received message by the CRC generator polynomial. If no errors occurred in transit, the division will produce the all-zeros remainder, and the data bits are accepted as error-free. A non-zero remainder indicates detected errors. Much of the literature describes CRC encoding and decoding using shift-register long-division algorithms. However, software algorithms (mainly table drive) have also been documented. Some references are provided below. REFERENCES: 1. Boudreau and Steen, "Cyclic Redundancy Checking by Program," AFIPS Proceedings, Vol. 39, 1971. 2. Higginson and Kirstein, "On the Computation of Cyclic Redundancy Checks by Program," The Computer Journal (British), VJol 16, No. 1, Feb 1973. 3. Marton and Frambs, "A Cyclic Redundancy Checking (CRC) Algorithm," Honeywell Computer Journal, Vol. 5, No. 3, 1971. 4. Wecker, S., "A Table-Lookup Algorithm for Software Computation of Cyclic Redundancy Check (CRC)," Digital Equipment Corporation memorandum, 1974. [Reference cited in McNamara, ref. below.] 5. McNamara, J. E., "Technical Aspects of Data Communication," 2nd edition, Digital Press, Bedford, Massachusetts, 1982. 6. Davies and Barber, "Computer Networks and Their Protocols," J. Wiley & Sons, 1979. END ALLEN LEVESQUE, GTE GOVERNMENT SYSTEMS CORP., WALTHAM, MASS. USA, TEL: (617)466-3729, FAX: (617)466-3720, e-mail: Levesque@rocky.ndhm.gtegsc.com