Error detection/correction and fault detection/recovery – Pulse or data error handling – Error/fault detection technique
Reexamination Certificate
1999-02-12
2001-05-29
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Error/fault detection technique
Reexamination Certificate
active
06240540
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to computer instructions, and, more particularly to a computer system using instructions for effecting a cyclic redundancy check.
BACKGROUND OF THE INVENTION
It is known to carry out cyclic redundancy checks on data in many communication protocols and data storage formats. They increase the reliability of data transmission and storage by defining a check sum which may be appended to data when it is written or sent. A receiver or reader of the data can recompute the check sum to confirm the integrity of the data.
It is an object of the present invention to provide an improved method and improved apparatus for carrying out a cyclic redundancy check in a computer system.
SUMMARY OF THE INVENTION
The invention is particularly, but not exclusively, applicable for use in data transmission and storage in accordance with MPEG protocol used for video signals. It is also particularly useful in digital audio signal compression techniques.
The present invention provides a method of executing a computer instruction to generate a cyclic redundancy check on data in a computer system, which instruction operates (a) to locate a digital word comprising, in a sequence of bit locations at one end of the word, a first cyclic redundancy check value and a data value adjacent the check value, the data value comprising a plurality of bit groups each having the same bit length, (b) to locate a generator value of the same bit length as the check value, (c) shifting all bits of the digital word a predetermined number of bit locations towards the one end of the word, (d) selectively forming an exclusive OR combination of bits of the generator value with respective corresponding bits in the sequence of bit locations, the selective formation providing a result dependent on detecting a particular value for any bit displaced from the sequence of bit locations on shifting the bits of the digital word towards the one end of the word, and using the results to replace digital values in the corresponding bit locations of the sequence of bit locations, (e) repeating the shifting of step (c) and selective formation of an exclusive OR combination of step (d) for each bit in one the group of bits of the data value, and (f) holding a resultant digital word comprising a revised cyclic redundancy check value together with any bit group representing a data value not yet shifted into the sequence of bit locations.
In one embodiment the predetermined number of bit locations in the shifting step (c) is one.
In one embodiment a single bit is displaced out of the sequence of bit locations on shifting the bit of the digital word towards the one end of the word, and no result is provided for each exclusive OR combination of step (d) if the last the single bit displaced has a predetermined one of two alternative values.
Conveniently the data value comprises a plurality of bytes, each the bit group comprising one byte.
Preferably the sequence of bit locations has a bit length equal to the bit length of the data value.
Preferably the generator value has a bit length equal to the bit length of the sequence of bit locations.
In one embodiment the one end of the digital word is the end of most significance.
The invention may include repeatedly executing a cyclic redundancy check instruction as mentioned above whereby a cyclic redundancy check value is generated for each data bit group sequentially, successive executions of the cyclic redundancy check instruction being effected without relocation of the bit groups of the data value in the digital word following each execution of the cyclic redundancy check instruction.
The invention also provides a computer system comprising an instruction store and execution circuitry responsive to instructions in the store including a cyclic redundancy check instruction, the execution circuitry including (a) first bit location circuitry to locate a digital word comprising in a sequence of bit locations at one end of the word a first cyclic redundancy check value and a data value adjacent the check value, the data value comprising a plurality of bit locations each having the same bit length, (b) second bit location circuitry to locate a generator value of the same bit length as the check value, (c) bit shifting circuitry for shifting all bits of the digital word a predetermined number of bit locations towards the one end of the word, (d) exclusive OR circuitry for selectively forming an exclusive OR combination of bits of the generator value with respective corresponding bits in the sequence of bit locations, the selective formation providing a result dependent on detecting a particular value for any bit displaced from the said sequence of bit locations on shifting the bits of the digital word towards the one end of the word, and using the results to replace the digital values in the corresponding bit locations of the sequence of bit locations, (e) sequence circuitry for repeating for each bit in one the group of bits of the data value the shifting step of bits in the digital word and the selective formation of exclusive OR combinations, and (f) result holding circuitry for holding a resultant digital word comprising a revised cyclic redundancy check value together with any bit group representing a data value not yet shifted into the sequence of bit locations.
In one embodiment the bit shifting circuitry is arranged to shift all bits of the digital word by a one bit displacement for each shifting operation.
Preferably in which enabling circuitry is connected to the exclusive OR circuitry the enabling circuitry being connected to the first bit location circuitry and arranged to control the exclusive OR circuitry in dependence on the particular value of bits displaced from the sequence of bit locations on shifting the bits of the digital word towards the one end.
Preferably the first bit location circuitry provides a plurality of bytes for the data value of the digital word.
Preferably the first bit location circuitry provides the same number of byte locations for the first cyclic redundancy check value as the number of byte locations for the data value.
Preferably the second bit location circuitry provides the same bit length for the generator value as the first bit location circuitry provides for the first cyclic redundancy check value.
The invention includes a computer system comprising processor circuitry memory and instruction holding circuitry the instruction holding circuitry holding a cyclic redundancy check instruction operable to carry out the method aforesaid.
REFERENCES:
patent: 4467444 (1984-08-01), Harmon, Jr. et al.
patent: 4723243 (1988-02-01), Joshi et al.
patent: 5539756 (1996-07-01), Glaise et al.
patent: 5844923 (1998-12-01), Condon
patent: 5931967 (1999-08-01), Shimizu et al.
patent: 5935268 (1999-08-01), Weaver
patent: 5953240 (1999-09-01), Prabhu et al.
patent: 0 608 848 A2 (1994-01-01), None
Linde, “A Fast Algorithm for Calculating Cyclic Redundancy Checks”, Correlations, Fall 1979, pp. 20-23, Dec. 1979.*
Perez et al., “Byte-wise CRC Calculations”, IEEE Micro, Jun. 1983, pp. 41-50.*
Sarwate, “Computation of Cyclic Redundancy Checks via Table Look-Up”, Communications of the ACM, Aug. 1988, vol. 31, No. 8, pp. 1008-1013.*
Crenshaw, “Implementing CRCs”, Embedded Systems Programming, Jan. 1992, pp. 18-43.
Homewood Mark Owen
Jones Andrew Michael
Allen Dyer Doppelt Milbrath & Gilchrist, P.A.
Baker Stephen M.
Galanthay Theodore E.
STMicroelectronics Limited
LandOfFree
Cyclic redundancy check in a computer 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 Cyclic redundancy check in a computer system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cyclic redundancy check in a computer system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2571036