Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1998-08-07
2001-12-04
Hua, Ly V. (Department: 2131)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S018000, C714S751000, C714S776000
Reexamination Certificate
active
06327688
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to the field of data busses, and particularly to schemes for verifying the integrity of data conveyed on a data bus.
2. Description of the Related Art
Data busses, found in virtually all computers and computer-based products, are used to convey data between devices connected to the bus. When data is conveyed from an originating device to a receiving device, there exists the possibility that the data will become corrupted en route.
Various schemes have been developed to alleviate this problem. For example, various handshaking protocols exist which require a device to which a message is sent to acknowledge the message's receipt by sending an acknowledgment message back to the message originating device. Though effective for verifying that some kind of data was received, this technique does nothing to insure that the data was received correctly; i.e., it does not verify the integrity of the data conveyed between the devices.
Schemes that do verify the integrity of conveyed data typically involve the use of some type of “check sequence”, i.e., one or more data bits that have a value based on the data conveyed. For example, a “parity bit” may be allotted a slot in a message, which is set high or low depending on the number of “1's” or “0's” in the message. When the message is received, the receiving device counts the message's “1's” or “0's” as appropriate, determines what the parity bit should be, and compares it with the bit received to determine the integrity of the message.
An extension of the parity bit approach requires the appending of a multi-bit check sequence to a message being sent. The value of the check sequence is calculated in a known manner based on the bits of the message. When the message is received, the same calculation is applied to the bits of the received message to determine what the check sequence should be. This predicted check sequence is compared to the received check sequence to determine message integrity.
Several methods are used to verify the integrity of conveyed data when a check sequence is employed. For example, when the check sequence calculated by the receiving device does not match that sent by the message originating device, the receiving device can send a message back to the originating device indicating that the message was not properly received. Such a message typically includes a “header”, i.e., one or more bytes of overhead data that precede the actual message, and requires the receiving device to arbitrate for the bus. Alternatively, the originating device can send a message to the receiving device asking that the received data be read back, or that a message status byte—with accompanying header—be sent. In either case, the originating device is unable to actively verify that a message is received correctly without a subsequent bus operation; i.e., data verification requires a minimum of two bus operations.
Because the above-described data integrity verification methods require multiple bus operations, message headers, and/or bus arbitration, they occupy the bus for a considerable amount of time, resulting in a bandwidth requirement that may be unacceptably high—particularly for busses intended for use in battery-powered products such as cellular phones or handheld computers for which low-cost bus devices are preferred.
A need exists for a data bus system that provides data integrity verification without requiring excessive bandwidth and which is compatible with low-cost bus devices.
SUMMARY OF THE INVENTION
A data bus system with data integrity verification and a verification method are presented which meet the needs stated above. The system and method provide a high degree of data integrity, use less bandwidth than prior art schemes, and operate effectively with low-cost bus devices.
The data bus system is arranged so that a bus device receiving a message always responds by sending a check sequence back to the message originating device; i.e., a check sequence is automatically returned to a message originating device as part of every bus transaction. The originating device then reads the check sequence and uses it to verify the integrity of the data transferred between the two devices.
The check sequences that are automatically sent by receiving devices on the bus can be, for example, a cyclical redundancy code (CRC), a checksum, a longitudinal redundancy check (LRC), or a parity bit. The check sequence can be created by the receiving device based on the data received or requested, or the receiving device can simply echo back a check sequence that is appended to the incoming data.
The returned check sequence is made an integral part of each bus transaction, eliminating the need to perform two bus operations to insure data integrity and thereby lessening the bus bandwidth required by prior art schemes. Also, the integrity verification is performed by the originating device, so that receiving devices need not include verification or error correction capabilities—enabling the system's use with low-cost bus devices.
The data bus system with automatic data integrity verification is effectively employed with various broadcast-type bus configurations, with single or multi-wire busses, and even with topologies such as a token ring network, and is equally applicable to fixed block or variable length message protocols.
Further features and advantages of the invention will be apparent to those skilled in the art from the following detailed description, taken together with the accompanying drawings.
REFERENCES:
patent: 5335233 (1994-08-01), Nagy
patent: 5428766 (1995-06-01), Seaman
patent: 5664105 (1997-09-01), Keisling et al.
patent: 5745502 (1998-04-01), Khayrallah et al.
patent: 5754754 (1998-05-01), Dudley et al.
patent: 6014767 (2000-01-01), Glaise
Dunstan Robert A.
Stolitzka Dale
Analog Devices Inc.
Hua Ly V.
Koppel & Jacobs
LandOfFree
Data bus with automatic data integrity verification and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data bus with automatic data integrity verification and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data bus with automatic data integrity verification and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2587002