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: <levesque-250193145752@192.147.5.16>
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