Efficient look-up table methods for Reed-Solomon decoding

Details Efficient look-up table methods for Reed-Solomon decoding Efficient look-up table methods for Reed-Solomon decoding

1998-11-25

2001-07-17

Moise, Emmanuel L. (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S759000, C714S785000

Reexamination Certificate

active

06263470

ABSTRACT:

STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
Not applicable.
BACKGROUND OF THE INVENTION
This invention is in the field of data communication, and is more specifically directed to error correction methods in the receipt of such communications.
Recent advances in the electronics field 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; of course, 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.
Of course, 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, of course, 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 in Reed and Solomon, “Polynomial Codes over Certain Finite Fields”,
J. Soc. for Industrial and Applied Mathematics,
Vol. 8 (SIAM, 1960), pp. 300-304. Reed-Solomon coding uses finite-field arithmetic, such as 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. Considering a message as made up of k m-bit elements, a polynomial of degree n−1 may be determined as having n coefficients; with n greater than k (i.e., the polynomial is overspecified), not all of the n coefficients need be valid in order to fully and accurately recover the message. According to Reed-Solomon coding, the number t of errors that may be corrected is determined by the relationship between n and k, according to
t
≤
n
-
k
2
.
Reed-Solomon encoding is used to generate the encoded message in such a manner that, upon decoding of the received encoded message, the number and location of any errors in the received message may be determined. Conventional Reed-Solomon encoder and decoder functions are generally implemented, in microprocessor-based architectures, as dedicated hardware units that are not in the datapath of the central processing unit (CPU) of the system, as CPU functionality has not heretofore been extended to include these functions.
In this regard,
FIG. 1
illustrates one example of an architecture for a conventional Reed-Solomon encoder, for the example where each symbol is eight bits, or one byte, in size (i.e., m=8), where Galois field arithmetic is used such that the size of the Galois field is 2
8
, and where the maximum codeword length is 2
8
−1, or 255 symbols. Of course, other architectures may be used to derive the encoded codeword for the same message and checksum parameters, or of course for other symbol sizes, checksum lengths, or maximum codeword lengths. In the example of
FIG. 1
, sixteen check symbols are generated for each codeword, and as such eight errors per codeword may be corrected. According to conventional Reed-Solomon encoding, the k message bytes in the codeword (M
k−1
, M
k−2
, . . . , M
0
) are used to generate the check symbols (C
15
, C
14
, . . . , C
0
). The check symbols C are the coefficients of a polynomial C(x)
C
(
x
)=
C
15
x
15
+C
14
x
14
+ . . . +C
0
which is the remainder of the division of a message polynomial M(x), having the message bytes as coefficients:
M
(
x
)=
M
k−1
x
K−1
+M
k−2
x
k−2
+ . . . +M
0
where the message polynomial M(x) is multiplied by the term x
2
t, and divided by a divisor referred to as generator polynomial G(x):
G
(
x
)=(
x−a
0
)(
x−a
1
)(
x−a
2
) . . . (
x−a
15
)=
x
16
+G
15
x
15
+G
14
x
14
+ . . . +G
0
where each value is a root of the binary primitive polynomial x
8+
x
4+
x
3+
x
2+
1. The exemplary architecture of
FIG. 1
includes sixteen eight-bit shift register latches
6
15
through
6
0
, which will contain the remainder values from the polynomial division, and thus will present the checksum coefficients C
15
through C
0
, respectively. An eight-bit exclusive-OR function
8
15
through
8
1
is provided between each pair of shift register latches
6
to effect Galois field addition, with XOR function
8
15
located between latches
6
15
and
6
14,
and so on. The feedback path produced by exclusive-OR function
2
, which receives both the input symbol and the output of the last latch
6
15,
presents the quotient for each division step. This quotient is broadcast to sixteen constant Galois field multipliers
4
15
through
4
0
, which multiply the quotient by respective ones of the coefficients G
15
through G
0
. In operation, the first k symbols contain the message itself, and are output directly as the leading portion of the codeword. Each of these message symbols enters the encoder architecture of
FIG. 1
on lines IN, and is applied to the division operation carried out by this encoder. Upon completion of the operations of the architecture of
FIG. 1
upon these message bytes, the remainder values retained in shift register latches
6
15
through
6
0
correspond to the checksum symbols C
15
through C
0
, and are appended to the encoded codeword after the k message symbols.
The encoded codewords are then communicated in a digital bitstream, after the appropriate formatting. For communications over telephone facilities, of course, the codewords may be communicated either digitally or converted to analog signals; digital network or intracomputer communications will, of course, maintain the codewords in their digital format. Regardless of the communications medium, errors may occur in the communicated signals, and will be reflected in the received bitstream as opposite binary states from those in the input bitstream, prior to the encoding process of FIG.
1
. These errors are sought to be corrected in the decoding process, as will now be described in a general manner relative to FIG.
2
.
An example of the decoding of Reed-Solomon encoded codewords, generated for example by the architecture of
FIG. 1
, is conventionally carried out in the manner now to be described relative to decoder
10
illustrated in FIG.
2
. Decoder
10
receives an input bitstream of codeword symbols, which is considered, for a single codeword, as received polynomial r(x) in FIG.
2
. Received polynomial r(x) is applied to syndrome accumulator
12
, which generates a syndrome polynomial s(x) of the form:
 
s
(
x
)=
s

Affiliated with

Also associated with

Rating

Efficient look-up table methods for Reed-Solomon decoding does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Efficient look-up table methods for Reed-Solomon decoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient look-up table methods for Reed-Solomon decoding will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2507262