Error detection/correction and fault detection/recovery – Pulse or data error handling – Error/fault detection technique
Reexamination Certificate
1997-09-12
2001-01-30
Moise, Emmanuel L. (Department: 2784)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Error/fault detection technique
C714S006130, C365S218000
Reexamination Certificate
active
06182266
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to the detection of invalid data elements stored in an array. More specifically, this invention pertains to a self-auditing protection method for a sorted array in which corrupt and/or duplicate data elements are detected and deleted during traversal of the sorted array.
In order to maximize efficiency and minimize delays associated with information retrieval, data elements within an array are typically “sorted” or arranged in numerical or alphabetical order. Many computer applications and operating systems include a built-in sorting program such as Quicksort, published in 1962 by C.A.R. Hoare, or computer sorting routines such as: (1) bubble sort; (2) insertion sort; (3) merge sort; (4) selection sort; and (5) shell sort. However, if the sorting process is prematurely terminated, before each data element has been moved to its appropriate array position, data elements may be duplicated or corrupted.
There are two existing techniques in the prior art which attempt to solve the above-identified problem. The first technique uses cyclic redundancy (check) code (“CRC”) in conjunction with data elements in an array. In short, CRC auditing involves the calculation of a CRC value based upon a formula which uses the data contained in each array element as variables. The result of that calculation, the CRC value, is then appended onto the end of each data element. Various calculation methods can be used to generate the CRC value; however, the CRC calculation method is generally chosen to optimize error detection capability. In order to check for an error in the data element, the calculation is performed again and compared with the stored answer, the CRC value. If the two calculations are different, an error is detected.
For large data elements, generating the CRC value is time consuming and for small data elements, the CRC algorithm is susceptible to erroneous detection of duplicates. Further, either of these problems can be aggravated depending on the selected CRC algorithm.
Another technique involves the use of doubly-linked lists. Doubly-linked lists provide a way to manage data that is not stored sequentially in a computer. In essence, a doubly-linked list contains three parts, the data itself, a first number (ie. pointer) which identifies the location of the previous item on the list, and a second number (i.e. pointer)which identifies the location of the next item on the list. However, the use of linked lists requires a relatively complex resource allocation scheme and a complex auditing mechanism. In addition, the recovery of broken linkages (i.e. when the pointer does not properly identify the location of the next or previous item on the list) is time-consuming and requires complex data analysis to recover all possible breakages and resource losses. Furthermore, the process which is traversing the doubly-linked list cannot proceed if errors are encountered.
In many data intensive applications sorting techniques requiring the use of CRCs or doubly-linked lists are unacceptable. A new system for detecting corrupt data elements stored in a computer as an array of data elements is necessary.
SUMMARY OF THE INVENTION
An object of the present invention is to provide a method and system of detecting and deleting invalid data elements contained within an array, including data elements that are duplicates as well as those that are corrupt, in which each traversal of the sorted array detects and discards the invalid data elements.
The invention takes the form of an error detection system for an array of data elements in which each data element has a first error detection field and a second error detection field. The first and second error detection fields are both assigned the same number which is unique and different from the numbers assigned to the error detection fields of the remaining data elements. The array of data elements is stored in a storing mechanism such as memory. As the error detection system traverses the array of data elements, a detecting mechanism sequentially compares the first error detection field with the second error detection field for each data element in order to determine whether the data element is corrupt. If the contents of the first error detection field does not equal the contents of the second error detection field, the data element is corrupt, otherwise, the data element is valid. A detecting mechanism also compares the first error detection field of one of the data elements with the first error detection field of another of the data elements. If the first error fi detection field of said one of the data elements equals the first error detection field of said another of the data elements, said another of the data elements is a duplicate of said one of the data elements. In any event, if a corrupt or duplicate data element is detected, a removing mechanism then removes or deletes the invalid element from the array.
These as well as other novel advantages, details, embodiments, features and objects of the present invention will be apparent to those skilled in the art from the following detailed description of the invention, the attached claims and accompanying drawings, listed hereinbelow, which are useful in explaining the invention.
REFERENCES:
patent: 3756404 (1973-09-01), King et al.
patent: 4448526 (1984-05-01), Miyazawa
patent: 5235585 (1993-08-01), Bish et al.
patent: 5319627 (1994-06-01), Shinno et al.
patent: 5577194 (1996-11-01), Wells et al.
Clutter Sherwin J.
Simak David F.
Lucent Technologies - Inc.
Moise Emmanuel L.
LandOfFree
Self-auditing protection method for sorted arrays does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Self-auditing protection method for sorted arrays, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Self-auditing protection method for sorted arrays will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2443118