Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-09-17
2002-07-23
Gordon, Paul P. (Department: 2121)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S807000
Reexamination Certificate
active
06425106
ABSTRACT:
FIELD OF THE INVENTION
The present invention, relates to the provision of check quantities for digital data, particularly for data transmission.
DISCUSSION OF RELATED ART
The use of ECC (error detecting and/or correcting codes) for digital data is well established. ECC is used, where the data is to be stored or transmitted by some means which is liable to occasional error. The data has a check portion or field appended to it to form a packet when it is entered into the storage or transmission means. When the packet is retrieved, the check field is used to detect whether errors have occurred and, in some situations, to correct them. A new check field may for example be calculated from the data field of the packet and compared with the check field in the packet. It is convenient to distinguish the data and check portions of the packet, but the check field checks the entire packet, ie itself as well as the data field.
A variety of ECC techniques have been proposed. Obviously, ease of implementation is important; for practical utilization, there must be some easily implemented algorithm for calculating the check field from the data field. If the system is to be used for error correction, then there must also be an effective technique for calculating the required corrections to the data field from the (erroneous) packet. However, if only error detection is required, then there is no need for an efficient means of determining the precise nature of the error. Pure error detection, with no correction, is for examples commonplace in many message transmission networks, because if an error is detected, the message can be retransmitted.
A widely used group of ECCs is cyclic ECCs. These are generally known as CRCs (cyclic redundancy check codes), and can readily be used for checking fields of variable length. A CRC code generates a check field which is termed the CRC field and is normally appended to the end of the data being checked. The present invention finds its main application with CRCs, and will be described in terms of CRCs rather than ECCs generally.
For present purposes, a CRC can be regarded as involving the division of the data field (regarded as a binary value) by a fixed binary value termed a polynomial, using arithmetic over the Galois fields GF
2
(ie modulo
2
and without carries between different positions). The remainder is the CRC or check field. The classical technique for calculating a CRC involves using a shift register with a feedback circuit including XOR gates at the positions corresponding to the 1s (powers of x) in the polynomial. (Details of this can be found in Error Correcting Codes, 2nd edition, Peterson & Weldon, MIT 1972.)
Many digital systems, consist of a variety of physically distributed units, and require data to be passed between the various units. In some such systems, the connections may be relatively simple; eg there may be separate connections between each pair of units, or there may be a single master unit to which all other units are connected. In most large multi-unit systems, however, the connections between the units, together with the interfaces between the units and the connections, form a distinct subsystem.
Such a subsystem is termed a digital data transmission network. Such a network may consist of a switching network having a number of switching nodes interconnected with each other, or an area network such as a LAN (Local Area Network), or a combination of switching networks and area networks. (An area network has a common communication medium with, normally, a large number of units connected to it.)
The present invention is mainly, though not exclusively, concerned with such digital data transmission networks.
With such networks, it is the responsibility of the network to achieve the proper carriage of data between the end units connected to the network. This typically involves determining suitable routing for the data (eg through a suitable sequence of switching nodes). The routing information required for this is a function of the network, independent of the end units. The switching network therefore normally has to add a header including routing information to the data as received from the source (originating) end unit. This header is either stripped off just before the message is delivered to the destination (receiving) end unit, or is ignored by that unit.
This complicates the application of ECC.
The original data, as generated by the originating end unit, will often be generated with its own CRC, and for various reasons, it is often highly desirable for the data to retain this CRC throughout its journey to the receiving end unit. The transmission network must therefore treat this combination of data plus its CRC as a unit (which we will term a packet). The transmission network adds a header to this packet (we will term this combination of header plus packet a message). (It will be realized that terms such as packet and message are used here with specific senses which may not be identical with their usual meanings in the context of message transmission networks.)
Just as for the data generally, it is often desirable for the header to be checkable; ie for ECC to be applied. But the precise manner in which ECC (which means, in practice, CRC) is applied to the message involves various considerations and is not entirely straightforward.
One option is not to use a CRC for the header, in the expectation that an error in the header will result in the message failing to reach an end unit or, if it reached the wrong end unit, that end unit rejecting it; the sending end until will then not receive an acknowledgement of its receipt, and will in due course resend it. This may not be acceptable.
A second option is to generate a header CRC for the header, so that the message consists of the header with its CRC, plus the packet (the data with its CRC).
A third option is for the packet to be encapsulated, with the header being added to the front of the packet and a combined CRC for the header plus packet being calculated and added at the end of the message.
A factor which has to be taken into consideration in selecting an option is whether the transmission network protocol is predetermined. If it is not, then any option may be chosen. But if it is, then the choice of option may be forced. The standard protocols require that the message should have a CRC at the end which checks the entire message, which forces the adoption of the third option.
SUMMARY OF THE INVENTION
The main object of the present invention is to provide an improved technique for providing error detection for messages in message networks.
The crux of the present invention lies in including, in the header of a message, a check correction field (CCF) which is chosen such that the CRC of the packet is also a valid CRC for the entire message. This means that the message will automatically conform to the usual message network protocol. (It will be realized that the nature of the contents of the header is not relevant, although we have described the header as containing routing information for use in a message network.)
The main advantage of this is that the CRC of the message forms a check for both the data of the original packet and the header, so a single CRC check verifies the accuracy of both the message as a whole and the data alone. This is in contrast to the known techniques discussed above. In the first of those, the header is not checked, and in the second, it is obvious that the header and the data are checked independently. In the third, the packet encapsulation technique, it is possible for an error to occur in the packet as the CRC for the message (packet plus header) is being calculated; so a CRC check on the entire message using the CRC of the message, therefore verified only the message header, and a second CRC check is therefore required on the packet extracted from the message to verify the integrity of the data.
The construction of the CCF will normally be performed in the interfacing between the originating end unit and the message network. Although the general f
Berent Anthony Neil
Higginson Peter Leslie
Enterasys Networks Inc.
Gordon Paul P.
Wolf Greenfield & Sacks P.C.
LandOfFree
Extended ECC system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Extended ECC system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Extended ECC system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2830774