Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-12-15
2002-05-07
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06385751
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
The technical field of this invention is electronic circuits for communications error correction.
BACKGROUND OF THE INVENTION
Digital communication systems have developed to a high degree of sophistication in the past two or three decades. Features that, not long ago, could be built into these systems only at enormous expense, can now be deployed in a wide range of applications including consumer electronics. Specifically, error detection and correction (EDAC) techniques, which have long been understood mathematically, were often not practical because of hardware costs. Only simple Hamming Code EDAC's with single bit correction were practical in low-cost applications. A Reed-Solomon EDAC, on the other hand, uses a powerful encoder/decoder technique that has excellent capability to correct multiple bit errors resulting from high-noise interference environments such as critical space communication, yet are producible at reasonable cost allowing for widespread usage even in moderate-cost products.
Recent advances in electronics have now made high-speed digital data communications prevalent in many types of applications and uses. Digital communication techniques are now used for communication of audio signals for telephony, with video telephony now becoming available in some locations. Digital communication among computers is also prevalent, particularly with the advent of the Internet. Computer-to-computer networking by way of dedicated connections (e.g., local-area networks) and also by way of dial-up connections has also become prevalent in recent years.
The quality of communications carried out in these ways depends upon the accuracy with which the received signals match the transmitted signals. Some types of communications, such as audio communications, can withstand bit loss to a relatively large degree. However, the communication of digital data, especially of executable programs, requires exact fidelity in order to be at all useful. Accordingly, various techniques for the detection and correction of errors in communicated digital bit streams have been developed. Indeed, error correction techniques have effectively enabled digital communications to be carried out over available communication facilities, such as existing telephone lines, despite the error rates inherent in high-frequency communication over these facilities.
Error correction may also be used in applications other than the communication of data and other signals over networks. For example, the retrieval of stored data by a computer from its own magnetic storage devices also typically utilizes error correction techniques to ensure exact fidelity of the retrieved data; such fidelity is essential in the reliable operation of the computer system from executable program code stored in its mass storage devices. Digital entertainment equipment, such as compact disc players, digital audio tape recorders and players, and the like also now typically utilize error correction techniques to provide high fidelity output.
An important class of error detection and error correction techniques is referred to as Reed-Solomon coding, and was originally described: by the Reed-Solomon article entitled: “Polynomial Codes over Certain Finite Fields” (see reference 1) Reed-Solomon coding uses Galois Field arithmetic, to map blocks of a communication into larger blocks. In effect, each coded block corresponds to an over-specified polynomial based upon the input block.
Reed-Solomon code based EDACs are used now in many communication systems such as satellites, modems, audio compact discs, and wireless phones. Each one of these systems is defined by a standard. The standard will define the parameters for the Reed-Solomon encoder/decoder. The encoder/decoder. implies an encoder plus a companion decoder. Table 1 below lists a few of those Reed-Solomon parameters for several communication standards. Each communication standard has different values for the parameters which define an Reed-Solomon code.
TABLE 1
Galois
Standard
Field
n
k
t
p(x)
IEEE 802.14-A
256
204
188
8
p1 (x)
IEEE 802.14-B
128
128
122
3
p2 (x)
CAP
256
5 to 255
1 to 251
2
p1 (x)
DMT
256
3 to 255
1 to 253
1 to 8
p1 (x)
W-CDMA
256
36
32
2
p3 (x)
The parameters “Galois Field”, “n”, “k”, “t”, and “p(x)” will now be described.
Reed-Solomon encoders/decoders use Finite Field arithmetic which is sometimes called Galois Field arithmetic and includes addition, multiplication, division, and exponentiation, in many data processing steps. The rules for such arithmetic operations are completely different from normal binary arithmetic. The primitive polynomial p(x) is used to define the result. The designation GF(X) refers to the number of possible bit combinations of a symbol in a given standard. Thus GF(256) refers to an eight-bit symbol and GF(8) refers to a 3-bit symbol.
Reed-Solomon codes are block codes, meaning that a message at the source is divided into “k” blocks of symbols having a designated number of bits “m”. For a given system as defined by one of the standards in the table above, for example, two other parameters are used: “n” is the number of symbols in a channel codeword, and “t” is the number of symbol blocks which can be corrected per each message of k blocks. Thus a particular Reed-Solomon code choice would be represented by: RS(n,k,t). The source codeword, k blocks of symbols, is designated by i(x), and the channel codeword of n blocks of symbols is designated by c(x). The (n−k) excess symbols, called parity symbols, are added to the source word to constitute the codeword, and the number of symbol errors which this system can correct is t=(n−k)/2.
Reed-Solomon encoder/decoders provide forward error correction (FEC) by adding redundancy to the source information. Forward error correction refers to the concept that the receiver does not have an opportunity to communicate with the source. One example of this is the transmitter on a distant planet which cannot interactively communicate with the receiver on earth and make adjustments based on received data (for example, retransmit a new copy of the data which was received and found to be corrupted). The data is transmitted through a non-perfect channel which could introduce errors and is received at the receiver. The Reed-Solomon decoder decodes and corrects the data.
An overall Reed-Solomon encoder/decoder system is shown in
FIG. 1. A
Reed-Solomon encoder receives and encodes source codeword i(x) including n symbols. The channel codeword c(x) is transmitted by a non-perfect communications channel. The non-perfect channel introduces errors, designated in
FIG. 1
by e(x) . The received codeword r(x) has the potential of symbols corruption. Thus the received codeword r(x) may not equal the channel codeword c(x) . The Reed-Solomon decoder does the reverse operation of the Reed-Solomon encoder plus an EDAC function. If there were no errors, the decoded codeword i′(x) would be restored to the same codeword as the source codeword i(x) without need for error correction. Thus:
i
′(
x
)=
i
(
x
).
Additionally, if there are symbol errors less than or equal to t in received codeword r(x), then the decoded keyword i′(x) would be also be restored to the same codeword as the source codeword i(x) after error correction. Thus:
i
′(
x
)=
i
(
x
).
The Reed-Solomon encoder uses the generator polynomial &ggr;(x) in the following equation to generate the channel codeword c(x). The equation of the channel codeword is in systematic form.
C
(
x
)
=
x
n
-
k
u
(
x
)
+
REM
[
x
n
-
k
u
(
x
)
γ
(
x
)
]
&ggr;(x) is defined as:
γ
(
x
)
=
∏
i
=
0
2
t
-
1
(
x
-
α
i
+
j
0
)
j
0
is an integer and is used to vary the result of &ggr;(x)
The error polynomial is labeled as e(x) and:
r
(
x
)=
c
(
x
)+
e
(
x
)
The purpose of the Reed-Solomon decoder is to solve for e(x) and calculate i′(x) . If the number of errors added to the block is less than
Baker Stephen M.
Brady III W. James
Marshall, Jr. Robert D.
Telecky , Jr. Frederick J.
Texas Instruments Incorporated
LandOfFree
Programmable, reconfigurable DSP implementation of a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Programmable, reconfigurable DSP implementation of a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Programmable, reconfigurable DSP implementation of a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2845239