Method and apparatus for a simple calculation of CRC-10

• US 6,014,767 A
• Filed: 04/01/1997
• Issued: 01/11/2000
• Est. Priority Date: 09/04/1996
• Status: Expired due to Term

• Current Assignee: Cisco Systems, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Glaise, Rene
• Primary Examiner(s): MOISE, EMMANUEL LIONEL
• Application Number:
  US08/834,678
• Time in Patent Office: 1,015 Days
• Field of Search: 371/37.01, 371/37.02, 371/32, 371/34, 371/53, 371/28, 714/752, 714/776, 714/748, 714/750, 714/807, 714/745, 714/781, 714/758, 708/492
• US Class Current: 714/776
• CPC Class Codes: H03M 13/091 Parallel or block-wise CRC computation

Abstract

A process and an apparatus to calculate the FCS (Frame Check Sequence) error checking code of packets payload sent over a fixed size packet networks in a network equipment sending said packets and to check said FCS in the network equipment receiving said packet; this invention applies to calculations of FCS based on CRC (Cyclic Redundancy Checking) codes generated by the polynomial generator of degree 10, G(X)=X¹⁰ +X⁹ +X⁵ +X⁴ +X+1. Particularly, this invention is for use in the ATM layer of ATM nodes processing OA&M and AAL3/4 ATM cells. The solution consists in using the calculation of the FCS based on the CRC code generated by the polynomial generator of degree 9, X⁹ +X⁴ +1 and simple operations. The calculation and the checking of the FCS is simple and thus the performance are improved authorizing the support of higher speed network lines.

Claims

1. A method for generating a packet, the integrity of which may be checked upon receipt at a destination node to which the packet is sent through a packet network, said method comprising the steps of:

calculating a FCS (Frame Check Sequence) value based on CRC (Cylical Redundancy Check) code generated by the polynomial generator of degree 10, G10(X)=X¹⁰ +X⁹ +X⁵ +X⁴ +X+1, of a packet payload by

calculating (520) CRC code generated by the polynomial generator of degree 9, G9(d)=X⁹ +X⁴ +1, of the packet payload and storing the resulting 9-bit stream FCS in 9-bit storage means,

calculating (510) the parity of said payload,

setting (580) the most significant bit of a 10-bit storage to zero,

if the payload parity is odd (590), adding (597) the 9-bit stream FCS to a bit stream representation of the generator polynomial of degree 9, G9(X)and storing the 10-bit stream resulting from the addition of the previous step in the 10-bit storage means, this stored 10-bit stream representing the payload FCS,

if the payload parity is even, storing (595) the 9-bit stream FCS in the least significant bits of the 10-bit storage means, the 10-bit stream of the 10-bit storage means representing the payload FCS;

retrieving the packet for which the foregoing calculations were performed and the 10-bit stream representing the payload FCS; and

generating a packet suitable for transmission by adding the retrieved payload FCS to the payload of the retrieving packet.

3. The method of claim 1 where the packet payload bit stream is a sequence of n-bits data bytes and the step for calculating the CRC code generated by the polynomial generator of degree 9 , G9(X)=X⁹ +X⁴ +1, of the packet payload consists in successive n-bit byte cycle processing, said method comprising the steps of:

a--sequentially receiving said sequence of data bytes in the 9-bit storage means (220);

b--pushing each byte of said data byte sequence into said 9-bit storage means, until said 9-bit storage means is full;

c--multiplying (210) the contents of said 9-bit storage means by the bit stream corresponding to α

ⁿ, an element of Galois Field generated by the generator polynomial G9(X), α

being an irreducible polynomial, root of said Galois Field,

d--updating the content of said 9-bit storage means by loading the result of said multiplying step into said 9-bit storage means,

e--repeating steps c, d, e until all data bytes have been pushed into said 9-bit storage means.

2. A method for checking the integrity of a packet in a packet network, having an extended payload field comprising an n-bits data bytes payload extended with a 10-bit stream FCS (Frame Check Sequence) calculated on the payload, said 10-bit FCS being based on CRC (Cyclic Redundancy Check) code generated by the polynomial generator of degree 10, G¹⁰ (X)=X¹⁰ +X⁹ +X⁵ +X⁴ +X+1, said method comprising the steps of:

calculating (520) the CRC code generated by the polynomial generator of degree 9, G9(X)=X⁹ +X⁴ +1, of the extended payload and storing the resulting 9-bit stream FCS in 9-bit storage means by

a) sequentially receiving a sequence of data bytes in the 9-bit storage means (220),

b) pushing each byte of said data byte sequence into said 9-bit storage means until said 9-bit storage means is full,

c) multiplying (210) the contents of said 9-bit storage means by the bit stream corresponding to α

ⁿ, an element of Galois Field generated by the generator polynomial G9 (X), α

being an irreducible polynomial, root of said Galois Field,

d) updating the content of said 9-bit storage means by loading the result of said multiplying step into said 9-bit storage means, and

e) repeating steps c, d, e until all data bytes have been pushed into said 9-bit storage means;

testing (540) if all the bits of the resulting 9-bit stream are equal to zero, the result of packet integrity checking being negative (560) if all said bits are not equal to zero;

if all the bits of the resulting 9-bit stream are equal to zero, testing the 1-bit parity of said extended payload, the result of packet integrity checking being negative (560) if said 1-bit parity is not equal to zero, the result of packet integrity checking being positive (570) if said 1-bit parity is equal to zero.

4. An apparatus to calculate the FCS (Frame Check Sequence) based on CRC (Cyclic Redundancy Check) code generated by the polynomial generator of degree 10, G10(X)=X¹⁰ +X⁹ +X⁵ +X⁴ +X+1, of a packet payload in a packet network to be sent onto a network line, said apparatus comprising the following means:

means (200, 210,

     220) for calculating the CRC code generated by the polynomial generator of degree 9, G9(X)=X⁹ +X⁴ +1, of the fixed length packet payload and storing the resulting 9 bit stream FCS in 9-bits storage means;

means for calculating the parity of said payload and storing it in a 1-bit storage means (247);

means for setting 10-bit storage means to zero;

means (240) for adding to each of the 9-bit stream read from the 9-bit stream storage means the 1 bit storage means and to the resuting 9-bit stream, the 10-bit stream representing the to the polynomial generator of degree 9, G9(X)=X⁹ +X⁴ +1;

means (250) for storing the 10-bit stream resulting of the addition of the previous step in the 10-bit storage means, this stored 10-bit stream representing the payload FCS that was to be calculated.

6. The apparatus of claim 4 or 5 where the packet payload bit stream is a sequence of n-bits data bytes, wherein the data bytes are sequentially received and a computation operation on said data bytes is made in successive cycles in order to generate said FCS, said apparatus comprising:

storage means having a number of bit positions equal to the number of the FCS bits, into which each byte of said data bytes is pushed until said storage means is full;

Galois Field multiplier means activated at each cycle to multiply the contents of said storage means by an element of the Galois Field;

gating means to load said storage means with the result of said Galois Field multiplication;

means for pushing a new byte of said data bytes into said storage means at each cycle, whereby said storage means contains at each cycle the current FCS.

5. An apparatus for checking in a network node, the integrity of a packet in a packet network, having a payload field comprising an extended field with the 10-bit stream FCS (Frame Check Sequence) calculated on the payload before extension, said 10-bits FCS being based on CRC (Cyclic Redundancy Check) code generated by the polynomial generator of degree 10, G10(X)=X¹⁰ +X⁹ +X⁵ +X⁴ +X+1, said appparatus comprising the following means:

means (200, 210,

     220) for calculating the CRC code generated by the polynomial generator of degree 9, G9(X)=X⁹ +X⁴ +1, of the fixed length extended payload and means for storing the resulting 9-bit stream FCS in 9-bit storage means;

means for testing the resulting 9-bit stream, if all the bits are not equal to zero, the result of packet integrity checking is negative;

means for calculating, if all the bits of the resulting 9-bit stream are equal to zero, the 1-bit parity of said extended payload, the result of packet integrity checking being negative if the 1-bit parity is not zero and positive if the 1-bit parity is zero.