Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-05-05
2004-09-21
Ton, David (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S781000
Reexamination Certificate
active
06795946
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to the checking of digital signals which include a frame check sequence, particularly Ethernet data packets, which are transmitted over a transmission medium in serial form at high data rates. The general object of the invention is to speed up the rate of checking preferably to enable a frame or packet to be checked at a speed commensurate with the data rate of the signal.
BACKGROUND OF THE INVENTION
In order to detect whether a data packet or other framed data signal has been corrupted in transmission or processing, it is customary to compute a frame check sequence by performing, in Galois field arithmetic a division of the number represented by the packet data by a selected multiple bit number, normally in the form of an appropriate polynomial of which the order corresponds to the number of bits in the sequence. The frame check sequence represents the ‘remainder’ of the frame data when that or a conventionally modified form of it is divided by the polynomial. The ‘remainder’ is added at the end of the packet data when the packet is transmitted. The packet including the frame check sequence may be checked after transmission to determine whether there is any corruption of the packet data (or the frame check sequence).
In some systems, the addition of the frame check sequence at the end of the frame which has been subject to the polynomial division will produce a result which, when divided by the same polynomial, produces all zeros for the remainder. This follows obviously from modular and more particularly Galois field arithmetic. In the particular case of Ethernet packets and others conforming to IEEE Standard 802.3 Section 3.2.8, the polynomial division is preceded by some conventional steps, including complementing the first 4 bytes of the packet not including, the preamble and start of frame delimiter and multiplying by x
32
, and succeeded by other conventional steps such as complementing the result of the division. Moreover the frame check sequence is transmitted with its most significant bit first instead of its least significant bit first. Thus the remainder that is produced when an uncorrupted frame including the frame check sum is divided by the same polynomial as is used for computing, the frame check sum is a non-zero constant (Hex c704dd7b) instead of all zeros. In what follows it will be assumed that the framed data on which the frame check sequence is to be computed is an Ethernet data packet consisting of (or intended to consist of) an integral number of bytes transmitted so as to produce if not corrupted a predetermined non-zero remainder as a result of an FCS check on the received paclet, but the invention is applicable to other framed messages consisting of an integral multiplicity of bytes.
Frame check sequence generators and checkers are well known in themselves. A typical checker is for example the 74F401 checker made by Fairchild Semiconductor Corporation. That checker specifically provides for the generation of a 16-bit frame check sequence and the detection of an appropriate 16-bit remainder when an incoming data stream consisting of the data and check bits is coupled serially into the checker. In itself, frame check sequence checking is not difficult for binary signals. In physical terms, the checker is a register comprising a chain of D-type bistables associated with exclusive-OR gates. The generator (or checker) divides an input binary digital signal by a general polynomial G(x) which may be, for example:
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
Where x is the relevant bit of the digital signal.
The main difficulty in high speed FCS checking (and generation) is that the storage devices (e.g. flip-flops) required for the checker cannot conveniently be operated at the same rate as the incoming data rate. More particularly the ‘set-up’ and ‘hold’ times for storage elements are of the same magnitude as or greater than a cycle at the incoming data rate. Although it is known to make a FCS check one byte at a time on incoming data which is one byte wide, if the data rate is, for example, 10 gigabits per second, the time required to calculate the running FCS for each byte is only 0.8 nanoseconds.
SUMMARY OF THE INVENTION
The process of FCS checking can be made more rapid if the input data (which may be in serial form or byte-wide form) is converted into parallel segments each consisting of a multiplicity of bytes, for example 16 bytes ( 128 bits). Each of the segments may be de-multiplexed into a buffer register, meaning generally a store in which the bits are stored in parallel, and then shifted to a second register to enable CRC checking to be performed on that segment while the next segment is being de-multiplexed into the first register.
However, a difficulty with such a scheme is that although all valid packets are based on octet (i.e. byte) boundaries, the number of bytes in a packet need not be a fixed multiple of the number of bytes in a segment. More generally, if the first register holds a segment of N bytes and M is the number of bytes in the packet, then M is not necessarily an integral multiple of N. It should be remarked at this stage that if a packet happens to contain odd bits in addition to the last full byte, it is normally ignored in the FCS checking and is handled by ‘dribble’ circuitry in a media access control device (MAC).
However, because the FCS check is a polynomial division carried out on the data in the packet, the result of the check, if the FCS of the packet is included, will always be a constant for an uncorrupted packet. If therefore a packet is augmented by data which is constant, a frame check sequence calculation performed on the augmented data packet will result in another constant. Furthermore, if the buffer register is incompletely filled by the packet data but is padded with constant data, so that the portion of the register not occupied by packet data of given length is always occupied by the same pad data, it is possible to carry out the frame check sequence checking by performing the check on the packet augmented by the pad data and checking whether the resultant remainder matches any of a limited number of pre-determinable constants, corresponding in number to the number of bytes which the first register can hold.
In numerical terms, if a register can hold 16 bytes ( 128 bits) at a time, the last segment of the packet or frame will consist of between 1 and 16 bytes inclusive. If for example the pad data consists of all ‘1’s, the FCS check which includes tile last segment should yield one of only 16 remainders, each uniquely associated with the different possible number of bytes contained in the last segment of the packet or frame. A similar result is obtained even though the pad data is not all 1's but is, for example an alternating sequence of 0s and 1s, provided that the pad data remains constant. If the pad data should be changed, it would be necessary to recalculate the various possible valid remainders.
Accordingly, the present invention is based on not only the demultiplexing or deserialising of the input data as may be necessary into parallel segments consisting of an integral number bytes, but also the padding of the last segment with constant data and a determination whether the FCS check matches any predetermined FCS values corresponding in number to the number of bytes in a segment.
The pad data may conveniently be provided by pre-loading a register into which each segment is written so that so far as a segment consists of bytes from the packet or frame the pre-loaded pad data is overwritten. Thus for all but the last segment of a packet the segment will consist of packet bytes whereas the last segment will comprise X bytes of packet data, wherein X may be from 1 to N, and Y bytes of pad data, wherein Y equals (N−X).
REFERENCES:
patent: 5121396 (1992-06-01), Irvin et al.
patent: 5424971 (1995-06-01), Yang et al.
patent: 5539
Aszkenasy Ruben
Drummond-Murray Justin A
3Com Corporation
Chaudry Mujtaba
Ton David
LandOfFree
Fast frame error checker for multiple byte digital data 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 Fast frame error checker for multiple byte digital data frames, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast frame error checker for multiple byte digital data frames will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3264036