Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-06-30
2003-10-07
Moise, Emmanuel L. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S715000, C714S758000, C714S786000, C714S788000
Reexamination Certificate
active
06631488
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to error control coding, and more specifically, to a configurable error control coding (ECC) engine that has a specialized instruction set tailored for ECC tasks.
BACKGROUND OF THE INVENTION
General Error Correction
In digital electronic systems, information is represented in a binary format (i.e., as a series of 0's and 1's). When information in a binary format is transported from a first point to a second point or stored on a magnetic media, there is the possibility of an error occurring during the transmission and reception process. For example, a “1” can be interpreted as a “0”, or a “0” can be interpreted as a “1”. There may be any number of reasons for the error. For example, media defects, electronic noise, component failures, poor connections, deterioration of data due to age, multi-path fading, other factors, or a combination thereof, can cause these errors. When a bit of information is mistakenly interpreted, a bit error has occurred.
To address the problem of bit errors, error correction schemes have been developed. Error correction is simply the use of techniques to detect bit errors and to correct them. Information can be conveyed as a group of bits. Typically, error correction schemes add “redundant” bits (i.e., extra bits) to the information. The extra bits add a particular structure to the information. Consequently, if the structure is altered by errors, the changes can be detected and corrected.
Some have used the following analogy to the English language to describe error correction schemes. The English language is based on the English alphabet and words that are formed by utilizing the letters in that alphabet. It is obvious that not all possible combinations of the English alphabet form “meaningful words” where “meaningful words” are defined as those words listed in a dictionary of the English language. Errors that occur when transmitting or storing English words can be detected by determining if the received word is defined by the dictionary. If the received word does not correspond with any word in the dictionary, errors in the word may be corrected by finding a meaningful word that is closest to the received word. Conceptually, error correction systems perform in a similar fashion to this analogy described above.
Error Correction for Wireless Systems
We live in a communication intensive society where the accurate transfer of information is important. Data communication via a wired system using cables or telephone lines is generally more reliable in the sense that there are fewer transmission errors than in a wireless communication system. One common example of wireless communications is the use of cellular telephones for voice communication, and increasingly, for data transfer.
In general, when designing a wireless system, the transmission errors in the communication channel need to be addressed. One situation that creates transmission errors in a wireless system is the existence of noise that can be man-made (e.g., radio frequency (RF) sources, electromagnetic field generated by electric sources, etc.), that can result from natural phenomenon (e.g., lightening, atmospheric conditions, etc.) or that can stem from the intrinsic thermal noise of the receiver. The noise can corrupt data that is being transferred. For example, in the cell phone example, the noise can manifest itself as static or as a loss of the voice data. The loss of voice data can be the loss of a spoken word, phrase, or entire sentence. If the noise is severe, the connection between the cellular telephone and the base station can be terminated. Accordingly, one goal of wireless system design is to provide a mechanism for addressing the transmission errors in the channel.
A second problem associated with a wireless system is that the communication channel is lossy (i.e., a signal may be at a high amplitude at the transmitting antenna, but of low amplitude a few miles away). Since the rate of transmission errors (i.e., the error rate) decreases with a higher signal-to-noise ratio, the error rate can be decreased by increasing the power transmitted by the cellular telephone, for example. Unfortunately, using higher power for transmission decreases the battery life of the cellular telephone that inconveniences users of such phones. Accordingly, it is desirable for a mechanism to correct transmission errors.
In this regard, in order too address the lossy and noisy traits of a wireless communication channel, designers commonly employ error correction systems. Error correction systems add additional bits to the data transmission, which are referred to as error correction bits, to detect and correct bit errors. There are many different types of error correction algorithms that can be effectively employed to detect and correct for bit errors in wireless systems, thereby increasing the accuracy of data communications and decreasing the number of errors encountered.
One approach to implementing the error correction algorithms is to utilize processors with a general arithmetic logic unit (ALU) or general floating point unit (FPU). Unfortunately, this approach does not provide (1) adequate performance and (2) the appropriate level of abstraction for error correction and detection tasks.
First, these general ALUs or FPUs provide only tolerable performance for error control coding (ECC) since the general processor must be able to perform many different tasks, only one of which is error correction related tasks. Consequently, the general ALU or FPU is not optimized for ECC tasks.
Second, a programmer who is writing code to implement a particular error detection and correction algorithm is required to program at an inappropriate level of abstraction. For example, the programmer is forced to write many lines of code in a development language, such as “C” programming language, just to implement a single error detection or error correction task. in a typical error detection and correction system, there is an encoder block and a decoder block with several functional blocks within each. The encoder block, for example, may include a convolutional encoder and interleaver that each would require one or more pages of program code in “C” to implement. Similarly, the decoder block, which may include a convolutional decoder and a de-interleaver, each would require one or more pages of code to implement. When the number of lines of required code increases, the development costs of a project generally increases proportionally. Furthermore, more lines of code leads to longer time to debug and to verify the proper operation of the code.
Consequently, it would be desirable for there to be an engine that can easily and simply implement a particular error correction task (e.g., convolutional encoder) without many lines of code. By simplifying and reducing the number of instructions that a developer has to write to implement an error detection or correction task, the attendant complexities and difficulties in developing code at an unnecessarily low level of abstraction can be decreased.
Programming at an unnecessarily low level of abstraction also adversely affects performance. For example, a single error control coding algorithm often involves many lines of instructions in a loop, where each execution of the loop requires multiple clock cycles to generate a single bit of output. In this regard, it is desirable for a mechanism for allowing a designer to specify an algorithm with a single instruction and for reducing the number of clock cycles needed to generate the output bits of error control coding algorithms.
Another approach to implementing the error correction and detection algorithms is to utilize specialized application specific integrated circuits (ASICs) that are hard-wired to perform a particular error-coding algorithm. This approach offers very fast execution and improves the performance when compared with the first approach. Unfortunately, new wireless communication protocols that specify different error correction algorithms are always be
Seacrist Kevin
Stambaugh Mark A
Agilent Technologie,s Inc.
Moise Emmanuel L.
LandOfFree
Configurable error detection and correction engine that has... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Configurable error detection and correction engine that has..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Configurable error detection and correction engine that has... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3167744