Cyclic redundancy check for partitioned frames

Details Cyclic redundancy check for partitioned frames Cyclic redundancy check for partitioned frames

1999-09-24

2004-01-20

Decady, Albert (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

Reexamination Certificate

active

06681364

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates in general to managing communications networks, and in particular, to a method and system for providing increased flexibility in processing data packets. More particularly, the present invention relates to a method and system for computing a frame check sequence (FCS) for a partitioned data packet. Still more particularly, the present invention relates to implementing Cyclic Redundancy Checks (CRCs) utilizing the inherent flexibility of modulo-2 arithmetic with no carries to provide a Cyclic Redundancy Check (CRC) that is adaptable with existing data processing structures and methods.
2. Description of the Related Art
CRC is a well known method for determining the presence of errors in digital transmissions in which discrete units of data, known as packets are delivered. The fundamental principle upon which CRC is based can be expressed equivalently in one of three ways. First, CRC can be described in terms of division of binary numbers. Second, as described by Boudreau et al. in U.S. Pat. No. 3,872,430, CRC may be performed utilizing a division of polynomials. Third, the utility in implementing CRCs is often realized by designing special check circuits in which Exclusive Or (XOR) and other elementary binomial operands generate frame check numbers for use during CRC.
Several types of packet-oriented data transmission systems are currently available. Token Ring, Ethernet, Asynchronous Transfer Mode (ATM), and Synchronous Optical Network (SONET) are examples of such systems which employ error detection and correction techniques such as CRC. When an information packet (sometimes referred to as a “frame” or “cell”) is delivered from a source node to a destination node the receiver will utilize CRC to verify integrity of the transmission. To verify an accurate and successful transmission of an n-bit data packet, M, in accordance with conventional CRC methodologies requires two fundamental steps. First, a divisor P having n+1 bits is selected. For example, and with reference to Spragins p. 279, the divisor utilized in accordance with the IEEE 802 standard is the 33-bit number known as “CRC-32”, as follows (the dot “.” is for visual convenience only):
10000010.01100000.10001110.11011011.1.
The next step is to append n 0-bits to the end of the data sequence M. This is equivalent to multiplying M (regarding M as a binary number) by 2
n
. Data sequence M is then divided by P utilizing modulo-2 arithmetic with, no carries and the remainder, R, is the Frame Check Sequence (FCS) of M. This FCS is then appended to the end (right) of M without the added 0-bits to produce the frame to be transmitted T. If T is correctly transmitted and then divided by P, the remainder is the n-bit number having all zero entries.
Various methods for employing CRC and computing a FCS are well known to those skilled in the art and for a further explanation of conventional CRC methods, reference is made herein to Boudreau et al. U.S. Pat. No. 3,872,430 Stallings, pp. 164-171, and Spragins, Hammond, Pawlikowski, p.279. These references provide a more detailed explanation of CRC calculations and are incorporated herein by reference.
Computation of a FCS for a lengthy data string is cumbersome and hardware intensive. It is therefore often desirable to divide the computation of a FCS for a data packet into several subcomputations which are faster and which impose a lesser degree of hardware overhead. Several techniques are known for performing such CRC computations on subdivided portions of the original data packet. U.S. Pat. No. 5,410,546 (Boyer et al.) and U.S. Pat. No. 5,325,372 (Ish-Shalom), describe one such approach in which partial CRC remainders (adjustment codes) are stored in a table. In this manner, the complete CRC check sequence (sometimes referred to as “check sum”) may be reconstructed utilizing a software implementation that constructs a FCS from the partial CRC remainders. Such methods may result in lower computation time but do not necessarily reduce hardware and software overhead. In addition, these “table lookup” methods do not support multiple interleaved data streams and are therefore insufficient when utilized with asynchronous systems such as Asynchronous Transfer Mode (ATM).
It can therefore be appreciated that a need exists for an improved CRC computation methodology that capitalizes on existing logic structures to calculate and subsequently combine partial CRCs to form a packet CRC. Such a method and system, if implemented would reduce the overhead required for generating check sequences that provides the flexibility inherent in utilizing partial CRCs.
SUMMARY OF THE INVENTION
It is therefore an object of the invention to provide an improved method and system for managing data communications.
It is another object of the invention to provide a method and system for providing increased flexibility in processing data packets.
It is still another object of the invention provide a method and system for computing a frame check sequence (FCS) for a partitioned data packet.
It is a further object of the invention to provide a method and system for implementing Cyclic Redundancy Checks (CRCs) utilizing the inherent flexibility of modulo-2 arithmetic to provide a CRC that is adaptable with existing data processing structures and methods.
The above and other objects are achieved as is now described. An improved method and system for generating a frame check sequence are disclosed. In the preferred implementation, a multiple-bit data string, M, is received in which M is of the form:
a
n
b
n
c
n
d
n
a
n−1
c
n−1
d
n−1
. . . a
2
b
2
c
2
d
2
a
1
b
1
c
1
d
1
.
M is thereafter parsed into multiple subframes of the form:
a
n
a
n−1
a
n−2
. . . a
2
a
1
;
b
n
b
n−1
b
n−2
. . . b
2
b
1
;
c
n
c
n−1
c
N−2
. . . c
2
c
1
;
and
d
n
d
n−1
d
n−2
. . . d
2
d
1
.
The subframes are padded with zeros resulting in subframes of the form:
a
n
000a
n−1
000a
n−2
000 . . . a
2
000a
1
000;
0b
n
000b
n−1
000b
n−2
00 . . . 0b
2
000b
1
00;
 00c
n
000c
n−1
000c
n−2
0 . . . 00c
2
000c
1
0;
and
000d
n
000d
n−1
000d
n−2
. . . 000d
2
000d
1
.
A partial check sum is then generated for each of the multiple subframes. Finally, each of the partial check sums are added together such that a frame check sequence for M is obtained. In this manner, the sum of the partial check sums is guaranteed to be the same as the check sum for the original complete data packet.


REFERENCES:
patent: 3872430 (1975-03-01), Boudreau et al.
patent: 4238852 (1980-12-01), Iga et al.
patent: 4593393 (1986-06-01), Mead et al.
patent: 4623920 (1986-11-01), Dufresne et al.
patent: 4712215 (1987-12-01), Joshi et al.
patent: 4723243 (1988-02-01), Joshi et al.
patent: 5008879 (1991-04-01), Fischer et al.
patent: 5122875 (1992-06-01), Raychaudhuri et al.
patent: 5168356 (1992-12-01), Acampora et al.
patent: 5251215 (1993-10-01), Dravida et al.
patent: 5280476 (1994-01-01), Kojima et al.
patent: 5282215 (1994-01-01), Hyodo et al.
patent: 5313454 (1994-05-01), Bustini et al.
patent: 5325372 (1994-06-01), Ish-Shalom
patent: 5351243 (1994-09-01), Kalkunte et al.
patent: 5361266 (1994-11-01), Kodama et al.
patent: 5379297 (1995-01-01), Glover et al.
patent: 5410546 (1995-04-01), Boyer et al.
patent: 5450399 (1995-09-01), Sugita
patent: 5452330 (1995-09-01), Goldstein
patent: 5778013 (1998-07-01), Jedwab
patent: 5790842 (1998-08-01), Charles et al.
patent: 5793427 (1998-08-01), Mills et al.
patent: 5951707 (1999-09-01), Christensen et al.
patent: 2001/0000221 (2001-04-01), Chen et al.
Sharp, D.W. et al. (Detection of variable message lengths for NATO Improved Link Eleven using CRC codes; IEEE, On page(s): 910-914 vol. 3; Nov. 4-7, 1991).*
Glaise, R.J. et al. (Fast CRC calculation; IEEE, On page(s): 602-605; Oct. 3-6, 1993).*
Shuaib, K. et al. (A cell loss padding technique for the transport of MPEG-2 transport stream over ATM/AAL; IEEE, On page(s): 450-454; Dec. 8-10, 1997).*

Affiliated with

Also associated with

Rating

Cyclic redundancy check for partitioned frames does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Cyclic redundancy check for partitioned frames, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cyclic redundancy check for partitioned frames will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3200117