Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1997-03-14
2001-01-09
Moise, Emmanuel L. (Department: 2784)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S759000, C714S784000, C714S792000, C714S800000
Reexamination Certificate
active
06173429
ABSTRACT:
TECHNICAL FIELD
The present invention is generally directed to a digital data transfer system and is particularly directed to a digital television transmission system in which errors in digital data are detected and corrected.
BACKGROUND OF THE INVENTION
Various systems, such as data communication systems and data processing systems, transfer digital data. Examples of data transfers include a transmission of data from a source location to a remote location within a communication system, and a storage/retrieval cycle of data within a processing system. Various influences can cause corruption of the data. For example, communication systems often transmit data across great distances through the atmosphere. Atmospheric conditions, such as lightning, can disrupt the data signal.
Various techniques have been developed for increasing the probability of error free data transfer. One example technique is based upon the inclusion of error correction data with the information (i.e., the original) data to provide error correction code words. Correction of erroneous information data at the destination (e.g., upon receipt or retrieval) is possible by mathematically reconstituting correct code words. To construct a code word, error correction data, often referred to as parity, is derived from the original data. The parity, in essence, mathematically characterizes the pattern of the original data. Upon receipt or retrieval, a decoder, using the parity, examines and manipulates the data in a fashion to detect, locate, and correct errors which have occurred therein.
A particular error detecting and correcting technique is directed to algebraic block codes wherein binary numbers are utilized to represent elements in a finite or Galois Field. A Galois Field (2
M
) has 2
M
elements, in which each element is M bits in length. The Galois Field elements may be considered as binary vectors representing data words or “symbols”. Typically, such Galois Field elements are multiplied in processes used to encode and decode messages for error correction purposes. Galois Field multiplication is fundamental in algebraic code techniques, but usually involves complicated operations. Some known Galois Field multipliers are decidedly too complex or too specialized, and thus of limited capability.
Modern data systems transfer a relatively large amount of data in a relatively short period of time. The modern systems have large data throughput, and thus have high error correction requirements. For example, television transmission systems which operate within the advanced television system standard (hereinafter referred to as “ATSS”) require a Reed-Solomon encoder utilizing Galois Field type error correction. The typical Reed-Solomon encoder operating within the ATSS must accept 187 eight-bit bytes of information data and generate 20 eight-bit bytes of error correction data (i.e., parity). To accomplish this requires a lengthy polynomial multiplication sequence as well as significant growth in signal data rate. Some known Galois Field multipliers are relatively slow and, as a result, may be unable to operate at the speed necessary to support the required data rates.
SUMMARY OF THE INVENTION
The present invention provides an apparatus for providing error correction data in a digital data transfer system. In accordance with one aspect of the present invention, the apparatus includes means for receiving a clock signal and means for providing a first signal using the clock signal. The apparatus includes means for receiving information data and a means for providing a second signal using the information data. The apparatus includes memory means for holding values. The memory means has a plurality of addressable memory locations and each memory location contains a value. Means address the memory means using the first signal to provide a first address component and using the second signal to provide a second address component. Mathematics means of the apparatus perform mathematics utilizing a value from the memory means to generate error correction data.
In accordance with another aspect of the present invention, the apparatus includes means for receiving information data. The information data is received in groups which each have a first predetermined number of elements. Means generate error correction data in response to the information data. The error correction data is in groups each having a second predetermined number of elements. Memory means of the apparatus are accessible by a portion of the system other than the apparatus and hold the information data elements and the error correction data elements. The accessible memory means includes memory array means having a plurality of array locations, each array location for holding an element. The number of array locations is equal to an integer multiple of the sum of the first and second predetermined numbers.
In accordance with a further aspect of the present invention, the apparatus includes means for receiving a clock signal and means for providing control signals using the clock signal. The apparatus includes means for receiving information data elements in first groups. Means generate error correction data elements using the information data elements and a control signal from the means for providing control signals. The error correction data elements being in second groups. Memory means of the apparatus include memory array means having a plurality of array locations for holding the information data and the error correction data elements. Means send information data elements and error correction data elements to the accessible memory means in third groups. Means control the means for sending in response to a control signal from the means for providing control signals to cause a first array location of the memory means to always receive a first element of one of the third groups of the information data and the error correction data.
REFERENCES:
patent: 3975712 (1976-08-01), Hepworth et al.
patent: 4471480 (1984-09-01), Haussmann et al.
patent: 4564945 (1986-01-01), Glover et al.
patent: 4637022 (1987-01-01), Burke et al.
patent: 4642808 (1987-02-01), Baggen
patent: 4716567 (1987-12-01), Ito et al.
patent: 4748626 (1988-05-01), Wong
patent: 4866719 (1989-09-01), Morgan et al.
patent: 4980897 (1990-12-01), Decker et al.
patent: 5068856 (1991-11-01), Nagasawa et al.
patent: 5195093 (1993-03-01), Tarrab et al.
patent: 5212695 (1993-05-01), Shikakura et al.
patent: 5222077 (1993-06-01), Krishnan
patent: 5377207 (1994-12-01), Perlman
patent: 5497404 (1996-03-01), Grover et al.
patent: 5586128 (1996-12-01), Chen
patent: 5627844 (1997-05-01), Cho
patent: 5805854 (1998-09-01), Shigeeda
patent: 5825807 (1998-10-01), Kumar
patent: 5901159 (1999-05-01), Ichikawa
patent: 5910960 (1999-06-01), Claydon et al.
patent: 6032284 (2000-02-01), Bliss
Mizwicki Paul
Seccia Joseph Lee
Twitchell Edwin Ray
Harris Corporation
Lamarre Guy
Moise Emmanuel L.
Tarolli, Sundheim, Covell Tummino & Szabo L.L.P.
LandOfFree
Apparatus for providing error correction data in a digital... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus for providing error correction data in a digital..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus for providing error correction data in a digital... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2439417