Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1997-10-15
2001-02-13
Tu, Christine Trinh L. (Department: 2784)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S781000
Reexamination Certificate
active
06189124
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to error code calculation for data integrity checking in high speed telecommunications networks. The invention can be applied to Asynchronous Transfer Mode (ATM) networks in which high speeds require a fast process for data integrity checking.
BACKGROUND OF THE INVENTION
When digital messages are transmitted over telecommunication networks some errors can be expected and to insure data integrity, the serialized data is protected with Error Detection Codes. In high speed networks the lines have a low error rate and the security of data only requires a end to end process. The data integrity process is carried out at both the sending and the receiving station; the sending station calculates a code corresponding to the data and the transmitting station checks the integrity of the data and code. ATM uses a Frame Check Sequence (FCS) field derived from Cyclic Redundancy Check (CRC) Error Detection codes for error checking. The CRC codes are often used for checking integrity of data because they are easy to implement and they detect a large class of errors. The access nodes of an ATM network have the responsibility of data integrity. The originating node calculates the redundancy bits constituting the Frame Check Sequence, (FCS) which is appended by the originating system to the bit stream to be checked before sending it over the network. At the destination node, the bit stream plus its initial FCS are checked using similar CRC computation. There is no error in transmission if the computed FCS at the destination node yields a constant value depending on the type of CRC used. It is noted that in an ATM network the FCS calculation and checking are performed in the ATM adapter cards of ATM access nodes (et the entry of the network), in ATM-connected user end stations, and also in ATM nodes providing internetworking functions such as ATM-Frame Relay.
CRC codes are generated by a generator polynomial characterizing the type of CRC; the CRC code corresponding to the polynomial representation of a bit stream to be encoded is the remainder of the polynomial division of the polynomial representation of the bit stream by the polynomial generator. CRC calculations are described, for instance, in ‘Téléinformatique I’ of Henri Nussbaumer, 1987, Presses informatiques romandes CH-1015 Lausanne. The FCS code has been standardized for data integrity checking as described in the ANSI X3.139-1987 document pages 28 and 29 and in Appendix B thereto. All the CRC codes constitute a finite Galois Field. If the polynomial generator is of degree d, the Galois Field of the CRC codes has 2
d
-1 elements. The simple implementation of codes based on CRC is due to the simple characteristics of calculations in the finite Galois Fields.
In ATM networks different types of connections may be established depending on the quality of service required. Some ATM standards organizations (ITU-T The International Telecommunication Union—Telecommunication and ETSI The European Telecommunication Standardization Institute ) have standardized different ATM Adaptation Layers (AALs) to provide generalized interworking across the ATM network. In the case of data, this AAL function takes frames (blocks) of data delivered to the ATM network, breaks them up into cells and adds necessary header information to allow rebuilding of the original block at the receiver. The AAL function includes checking for errors. The AAL function is implemented in the ATM end point which connects to the ATM network over the User Network Interface (UNI). As ATM switches usually contain endpoint functions as well as switch functions, AAL function is also implemented in ATM switches. Different AALs correspond to different traffic types. For instance, AAL1 is used for the service class A, circuit emulation, while AAL3/4 provides an end-to-end transport for both connection oriented (class C) and connectionless data (class D). AAL5 is designed to operate significantly more efficiently than AAL3/4 and has become the 1.364 ITU-T standard. The implementation of the AAL5 function is characterized by its low cost, compared to the other AAL implementations, in terms of overhead in the network nodes.
The ATM cell headers have their own error checking based on FCS calculation. The payload of 384 bits (48 bytes) of some ATM cells also uses FCS redundancy bits for error checking. The last 32 bits of cell payload of the last cell of a message conveyed through an AAL5 type connection represents the FCS code calculated on the message. The FCS code used for AAL5 cells is based on the CRC-32 codes calculations. We can represent bit streams as polynomials having coefficients values of 0 or 1, each power of X representing the weight of the bit in the stream. The addition of such polynomials correspond to logical addition (XORs) on their coefficients. The CRC-32 codes belong to the Galois Field generated by the following generator polynomial of degree 32:
G
(
X
)=
X
32
+X
26
+X
23
+X
22
+X
16
+X
12
+X
11
+X
10
+X
8
+X
7
+X
5
+X
4
+X
2
+X+
1
This generator polynomial of degree 32 was chosen as a standard for error checking in Ethernet and then chosen by the ATM standard for AAL5 error checking. The standard used for FCS calculation based on the polynomial generator of degree 32 is described in the publication ‘American National Standard for information systems, fiber distributed data interface (FDDI)—token ring media access control (MAC)’ ANSI X3.139-1987 of American National Standards Institute, inc.
If P(X) is the polynomial representation of a bit stream for which the 32 bit stream FCS is to be calculated:
FCS
(
P
(
X
))=
L
(
X
)+
Rem
G
(
X
32
P
(
X
)+
X
k
L
(
X
)) (Expression 1)
with
k−1=degree of P(X)
L(X)=X
31
+X
30
+ . . . +X
2
+X+1.
Similarly, for FCS checking at the other side of a network when receiving a bit stream F′(X) including the appended FCS which has been calculated before sending, the checking is positive only if:
Rem
G
(
X
32
(
F
′(
X
)+
X
k′
L
(
X
)))=
C
(
X
) (Expression 2)
with
C(X)=X
31
+X
30
+X
26
+X
25
+X
24
+X
18
+X
15
+X
14
+X
12
+X
11
+X
10
+X
8
+X
6
+X
5
+X
4
+X
3
+X+1;
k′−1=degree of F(X); and
L(X)=X
31
+X
30
+ . . . +X
2
+X+1
The FCS bottleneck in FCS computation and checking is the Rem
G
operation. The result is a CRC code belonging to the set of residue classes modulo G(X) of the polynomials of coefficients equal to 1 or 0 which is a ring, a linear algebra and which is a Galois Field having a multiplicative cyclic group because G(X), the generator polynomial of degree 32, is an irreducible polynomial.
The standard circuitry for computing the FCS of a bit stream message is a Linear Feedback Shift Register (LFSR) which carries out a bit by bit multiplication in the corresponding Galois Field. Each bit of the message is pushed in the LFSR, Most Significant Bit (MSB) first. The division is performed by the feedbacks. At the end of the process, the FCS (remainder of the division) is within the shift register. This method and type of circuitry is described, for instance in ‘Error Checking Codes’ by Peterson and Weldon, the MIT Press, 2nd edition, 1972. Although simple the method has obvious drawbacks. For example, since only one bit is processed at each shift, as many shifts as the number of bits is the message are needed in the LFSR. As the 32 bit CRC is used, a 32 bit register is needed. In this LFSR the remainder is calculated on a message shifted left by 32 bit places according to Expression 1 and Expression 2 for FCS calculation and checking. Still in order to be in accordance with Expression 1 and Expression 2, the polynomial addition of X
k
L(X) is realized by presetting the Shift register to all ones. Computing the CRC takes as many clock pulses as there are bits in
Abraham Esaw
International Business Machines - Corporation
McConnell Daniel E.
Tu Christine Trinh L.
LandOfFree
Method and apparatus for a two-step calculation of CRC-32 does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for a two-step calculation of CRC-32, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for a two-step calculation of CRC-32 will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2574977