Extended symbol Galois field error correcting device

Details Extended symbol Galois field error correcting device Extended symbol Galois field error correcting device

1999-04-22

2002-01-22

Decady, Albert (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S800000

Reexamination Certificate

active

06341362

ABSTRACT:

TECHNICAL FIELD
This invention relates to the detection and correction of digital data, and more particularly, to systems and methods for detecting and correcting errors in digital data with singly-extended Reed-Solomon decoders.
BACKGROUND OF THE INVENTION
Recently, the need has increased for efficient and reliable digital data transmission and storage techniques. The fields of communications and computing have merged such that there exists a great demand for exchanging, processing and storing of digital information with large-scale, high-speed data networks. Even personal computers (PCS) have seen large increases in speed and complexity, and with a coupling to the Internet, have also developed an increased need for apparatus and methods for transferring digital information. A resulting primary concern is the control of errors during exchange, processing and storage of digital information so that data can be reliably reproduced.
As early as 1948, it was shown that error reduction could be realized from a noisy channel or storage medium by properly encoding information. Since this date, a significant amount of effort has been expended on devising ways of efficiently encoding and decoding information so that error is controlled, particularly in noisy environments. More recently, the use of high-speed digital systems has resulted in a need to realize reliable data transmission such that coding/decoding has become a significant factor in the design of modern communication systems and digital computers.
The intercommunication of computers, data processing systems and communications systems occurs via transmission of digital data comprising signals. Digital signals comprise a series of “ones” and “zeros”. Transfer of such signals oftentimes subjects the signals to errors resulting from the presence of noise, defects in storage media and defects in the transmission path or data channel extending between an information source and a destination device. Hence, there exists a need to correct for such errors in order that transmitted and stored information is not lost.
One system for detecting and correcting errors in digital information utilizes Reed-Solomon decoders. One relatively recent attempt is evidenced by U.S. Pat. No. 4,413,339 issued to Riggle, et al., wherein an error detecting and correcting system implements Reed-Solomon (1026,1006) code having codewords whose symbols are elements in the Galois field GF(2
10
) generated by either the primitive polynomial x
10
+x
3
+1 or x
10
+x
7
+1.
However, prior art solutions involving Reed-Solomon decoders generally utilize the following technique. The extended error value (e_) in the extended received-symbol (r_) is calculated by adding the syndrome (S
n−k+1
) of the received input codeword to the computed error values coming out of the RS decoder. That is,
e
_
=
s
n
-
k
+
1
+
∑
j
=
0
n
-
1
⁢
e
j
⁢
α
j
⁡
(
n
-
k
+
1
)
The disadvantage associated with the prior art techniques is that the syndrome value (S
n−k+1
) needs to be buffered until the error values are computed and ready. However, buffering causes the required overall latency and the number of logic elements used to increase.
For additional background information evidencing the state of the art, reference may be had to
Error Control Coding: Fundamentals and Applications
, Shu Lin and Daniel J. Costello, Jr., Prentice-Hall, Inc., Englewood Cliffs, N. J., 1983. Such reference is herein incorporated by reference as evidencing the present state of the art.
For yet additional background information pertaining to extended Reed-Solomon Codes, reference may be had to The Decoding of Extended Reed-Solomon Codes,
Discrete Mathematics
90 (1991), pp. 21-40, A. Dür, North-Holland. Such reference is herein incorporated by reference as evidencing the present state of the art.
Therefore, additional needs exist to reduce the overall latency and the number of logic elements needed when implementing a singly-extended Reed-Solomon decoder.
SUMMARY OF THE INVENTION
In accordance with the present invention, error correction of an extended symbol in a singly-extended Reed-Solomon decoder is implemented using existing error detection logic elements. The fundamental principles of this invention are that an encoded extended-symbol (c_) is generated by evaluating the encoded codeword, c(x), for &agr;
(n−k+1)
. The final encoded codeword, {tilde over (c)}=[c_c], is transmitted to a standard RS decoder which is used to correct the received input codeword, {tilde over (r)}=[r_r], excluding the extended symbol, r_. By computing the syndromes of the intermediate output codeword (c′
j
) of the standard RS decoder, it turns out that the corrected extended-symbol (c_) is in the (S
n−k+1
) output syndrome register and is latched on the (n−
1
)th (one before the last) clock cycle. During the (n)th (last) clock cycle, the corrected extended-symbol (c_) is multiplexed with the intermediate output codeword (c′
j
) to yield the final output codeword, {tilde over (c)}=[c_c].
The goal of this invention is to make use of existing error detection logic while minimizing latency and hardware requirements. For example, a 3 m 2×1 multiplexer can be used with 2 m registers to correct the received extended-symbol.
According to one aspect of the invention, an extended symbol Galois field error correcting device is provided. The device includes a singly-extended Reed-Solomon encoder configured to generate an encoded codeword, {tilde over (c)}(x). The device also includes a channel medium that is signal coupled with the singly-extended Reed-Solomon encoder. The channel medium is configured to receive the encoded codeword, {tilde over (c)}(x), and output a received input codeword, {tilde over (r)}(x). The channel medium is capable of introducing error, {tilde over (c)}(x), to the encoded codeword, {tilde over (c)}(x). The device further includes a singly-extended Reed-Solomon decoder that is coupled with the channel medium. The singly-extended Reed-Solomon decoder is configured to receive the received input codeword, {tilde over (r)}(x). The singly-extended Reed-Solomon decoder has error detection circuitry and extended symbol correction circuitry. The error detection circuitry is configured to detect presence of error, {tilde over (e)}(x), within the received input codeword, {tilde over (r)}(x). The extended symbol correction circuitry is configured to correct the received input codeword, {tilde over (r)}(x), by computing syndromes of an intermediate output codeword (c′
j
). A corrected extended parity symbol (c_) is provided such that the corrected extended symbol (c_) is multiplexed with the intermediate output codeword (c′
j
) to yield a final output codeword, {tilde over (c)}=[c_c′].
According to another aspect of the invention, a Reed-Solomon decoder is provided. The Reed-Solomon decoder includes error detection circuitry configured to receive an input codeword and operative to detect presence of error within the input codeword. The Reed-Solomon decoder also includes extended symbol correction circuitry that is coupled with the error detection circuitry and configured to correct the input codeword by computing syndromes of an intermediate output codeword. Furthermore, the Reed-Solomon decoder includes a multiplexer that is associated with the extended symbol correction circuitry. The extended symbol correction circuitry causes a corrected extended parity symbol to be provided in an output syndrome register associated with an (n−1)th clock cycle such that, during the (n)th clock cycle, the corrected extended parity symbol is multiplexed with the intermediate output codeword to yield a final output codeword.


REFERENCES:
patent: 4413339 (1983-11-01), Riggle et al.
patent: 4777635 (1988-10-01), Glover
patent: 5020060 (1991-05-01), Murai et al.
patent: 5130990 (1992-07-01), Hsu et al.
patent: 5323402 (1994-06-01), Vaccaro et al.

Affiliated with

Also associated with

Rating

Extended symbol Galois field error correcting device does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Extended symbol Galois field error correcting device, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Extended symbol Galois field error correcting device will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2871844