High-speed syndrome calculation

Details High-speed syndrome calculation High-speed syndrome calculation

2000-02-18

2001-04-17

Decady, Albert (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S782000, C714S784000, C714S785000, C708S492000

Reexamination Certificate

active

06219815

ABSTRACT:

BACKGROUND OF THE INVENTION
A. Field of the Invention
The present invention relates to a method and device for calculating Reed Solomon syndromes using a programmable logic computer.
B. Description of the Related Art
Digital data transmission systems are used in a variety of different applications ranging from transferring financial numbers representing dollar amounts in bank accounts, to storing the music of our favorite performs on compact digital audio discs, to communicating telemetry data with aircraft and orbiting space satellites. To transmit this type of information, digital transmission systems deliver a sequence of binary information to a receiver across a transmission channel. Due to impairments in the transmission channel (i.e., the inability of the transmission channel to accurately deliver the transmitted bits), the binary information may become corrupted or changed as they traverse the transmission channel. If the errors are undetected, the amounts in our bank accounts would be wrong, our favorite singers would be out of tune, and aircraft could be lost.
To prevent these problems, error detection schemes are employed to detect differences between the originally transmitted bits and the received data bits. When a transmission error is detected, the error detection scheme signals the transmitter to re-send the corrupted information. More advanced error detection schemes, known as Forward-Error-Correction (“FEC”), can detect and correct corrupted information without requiring the transmitter re-send the information. FEC codes are essential in systems where the re-sending of information is not possible or practical. For example, in a compact audio disc there is not sufficient time to re-send the digital audio information without affecting the sound quality; with deep space probes re-sending the information may take a great deal of time.
A Galois finite field is a defined number system composed of a finite number of elements. A Galois finite field of q elements is usually denoted as GF(q). The q number of elements in a Galois field are of the form p
M
, where p is a prime integer and M is a positive integer.
Galois fields are particularly useful in FEC codes, such as Reed Solomon codes, for detecting and correcting errors in a transmitted sequence of binary information bits. For example, a sequence of binary information bits is first partitioned into a sequence of symbols, where each symbol is M-bits long. Each symbol is an element of a 2
M
element Galois field, denoted as GF(2
M
). The symbols are further partitioned into groups of K number of symbols represented by d
K−1
, d
K−2
, d
K−3
, . . . d
2
, d
1
, d
0
, where d
K−1
is first in the sequence (transmitted first in time) and d
0
last in the sequence (transmitted last). The sequence of transmitted symbols can thus be represented as a (K−1)
th
order polynomial:
D
(
X
)=
d
K−1
+d
K−2
X
K−2
+ . . . +d
2
X
2
+d
1
X+d
0
where X is a symbol delay operator and the d's are the coefficients of a Galois Field polynomial.
To implement a FEC using Galois field polynomials, redundant symbols are appended to the message stream, increasing the message length from K to N. The group of N number of symbols is called a codeword, and can be represented as a (N−1)
th
order polynomial C(X). The methods for determining these redundant symbols are known to those skilled in the art of error correction and described in “Error Control Coding: An Introduction,” by Peter Sweeney, Prentice Hall 1991 and “Theory and Practice of Error Control Codes,” by Richard E. Balhut, Addison-Wesley Publishing Company, Inc., 1983, which are hereby incorporated by reference.
The transmitter transmits the codeword, which is received at the receiver, but is possibly corrupted by the impairments of the transmission channel.
The receiver implements the FEC by decoding the received symbols using the coefficients of a Galois Field polynomial. The received symbols are represented as coefficients of a Galois Field polynomial and a set of syndromes, which holds the keys for locating errors in the input message stream, is calculated. I the syndromes calculated at the receiver are all zeros, the transmitted bit stream was received without any error. If the syndromes differ, an error exists in the received symbols. In a FEC code, the syndromes can also be used to determine the erroneous bits and correct them without requiring the message to be re-transmitted. The specifics of locating and correcting errors are known to those skilled in the art and described in the above texts.
Among the operations to be performed in FEC decoding are calculating a set of 2R symbols, called syndromes, for each received codeword. A common technique of calculating syndromes divides the C(X) polynomial by each of the 2R first order factors (X+a
i
) of the generator polynomial, where the value of i ranges from i=0 to i=(2R−1). Polynomial division is performed by long dividing the polynomial by the first order factors of the generator polynomial in a fashion similar to ordinary long division. To divide an (N−1)th order polynomial by a first order polynomial requires N−1 polynomial multiplications of the divisor polynomial (by the next digital in the quotient) to yield a product, and then N−1 subtractions of the product from the current remainder to yield a new remainder. The process repeats until the product can no longer be subtracted from the remainder. The division operation of the polynomial must be performed 2R times, that is, once for each of the first order factors of the generator polynomial G(X).
To implement the polynomial multiplication used in the polynomial division operation, a pre-computed multiplication table L
i
can be created for each of the first order polynomials factors of the generator polynomial (X+a
i
) and stored by the computer in memory. The multiplication look-up table L
i
is 2
M
elements long and contains the product of the input (index j) with the first order polynomial (X+a
i
):
L
i
(
j
)=
j*
(
X+a
i
)
In practice, for a small value of I, that is a small number of first order factors to evaluate the polynomial, typically I=2R, a set of I multiplication tables are created. The polynomial evaluation process can then perform multiplication by indexing and retrieving the result in the proper multiplication table stored in computer memory.
To calculate the set of syndromes for a codeword using a FEC code requires 2R division operations, each using (N−1) multiplications for a total of 2R*(N−1) multiplications required to calculate the set of syndromes. Using a look-up table, each multiplication requires a memory access to return the result of the multiplication. In computer processors having a long latency in performing memory accesses, this method of calculating polynomials may require a large amount of processor computation time. For example, a digital signal processor performing the multiplication by accessing the multiplication look-up table stored in memory may require a T number of memory clock cycles to return the result of the operation. The total processor time to calculate the syndromes is thus 2R(N−1)T clock cycles. For an application such as an Asymmetric Digital Subscriber Line (“ADSL”) as specified by the ANSI T1E1.413 standard, R=8 and N=254 which may be a prohibitive amount of time to calculate syndromes for each codeword. This amount of computational processing required may preclude a software implementation unless there is a method or system to simplify the calculations.
Accordingly, it would be desirable to reduce the amount of time necessary to perform the syndrome calculations.
SUMMARY OF THE INVENTION
The present invention addresses the problem of evaluating polynomial equations to determine syndromes used in FEC codes for detecting and correcting errors in transmitted data. In accordance with the present invention, the calculation of syndrome

Affiliated with

Also associated with

Rating

High-speed syndrome calculation does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with High-speed syndrome calculation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High-speed syndrome calculation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2473717