Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-08-27
2002-03-19
Chung, Phung M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S759000, C375S342000
Reexamination Certificate
active
06360348
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to coding and decoding and, in particular, to a method and apparatus for Reed-Solomon coding and decoding.
BACKGROUND OF THE INVENTION
Reed-Solomon coding is known in the art. As was first described in “Polynomial codes over certain finite fields,” Reed I. S. and Solomon G.,
Journal of Society of Industrial Application Mathematics
8, 300-304 (1960), Reed-Solomon Codes can be utilized during the transmission of data to eliminate errors in the received data. The encoders rely on the mathematics of Galois fields, which are disclosed is U.S. Pat. No. 4,142,174 and 4,567,594, the disclosures of which are incorporated by reference herein. In summary, Reed-Solomon codes are defined with code symbols from a Galois Field of numbers represented as GF(Q), where Q=2
b
is a positive integer power of 2. A Galois Field has a finite number of elements. GF(Q) has Q elements, that can be represented by 0 and Q−1 consecutive powers, (&agr;
0
, &agr;
1
, . . . , &agr;
Q−1
) of a special element (&agr;).
Many different methods of using Reed-Solomon encoders and decoders are known in the art. One such method for using Reed-Solomon codes in error correction is to append a set of parity symbols to the transmitted data, where the word “symbol” is used to represent b bits that form an element of GF(Q) field. The parity symbols are used to detect and correct errors in the transmitted data. More particularly, an encoder treats the message bits as blocks of symbols that form a message polynomial on GF(Q) and derives the parity symbols by dividing the message polynomial (X) by a code generating polynomial (G). The parity symbols are identified as the coefficients of the remainder polynomial (C). The parity symbols are appended to the message symbols to form the coefficients of a codeword polynomial. The code generating polynomial is selected to impart desired properties to the codeword so that the codeword will belong to a particular class of error-correcting group codes. During transmission, the codeword is transmitted by appending the parity symbols to the message data as tail bits which are utilized by the receiver to correct errors in the received message polynomial (R).
FIG. 1
shows a prior-art Reed-Solomon encoder, implemented as a shift-register polynomial division circuitry. As shown, the shift register is initialized with zeros in the delay elements (D). During each iteration, the mth data symbol X
m
is multiplied with the content of the right most delay element to form the symbol Y
m
. The content of each delay element is then updated by summing the content of the delay element to its left and the product of the symbol Y
m
and G
m.
, where G
m
's are the coefficients of the code generating polynomial, i.e., G(z)=G
0
+G
1
z+. . . +G
K−1
z
K−1
+Z
K
. (An exception is the left most delay element, which is updated with the product G
0
Y
m
.)
The parity symbols are generated by continuing to update the shift register until the end of the message block. Upon completing the iteration for the last symbol of the message block, the content of the shift register becomes the parity symbols, where the right most delay element contains the first parity symbol to be appended to the message data by the transmitter.
To date the division processing is typically carried out by dedicated hardware (e.g., multipliers
101
, delay circuitry
102
, and adders
103
), however, with the advancement of “soft” modems, the processing has been increasingly accomplished via a microprocessor/software combination.
Although soft modems have the capability to perform Reed-Solomon encoding/decoding, a problem exists in that the prior art implementation requires a lot of processing power. In the encoder described in
FIG. 1
, for each message symbol, K multiplications and additions are required. Although Galois Field addition is logical XOR operation that is typically supported in microprocessor instruction set, Galois field multiplication is rarely supported and takes multiple instruction cycles to complete. For high speed modems (e.g., ADSL modems or cable modems), the Reed-Solomon encoder needs to process on the order of million of message symbols per second. The total processing power or MIPS required would be a significant percentage of if not exceeding the total processing power of a typical microprocessor. As result, the entire modem function may be difficult to accomplish via a microprocessor. Even if the microprocessor were able to accomplish modem functions, for host processing or software modems, processing power used by the modem would not be available for other applications. Therefore a need exists for a method and apparatus for encoding/decoding that can be implemented in soft modems, yet does not utilize the MIPS required by prior-art soft modems.
REFERENCES:
patent: 3668632 (1972-06-01), Oldham, III
patent: 4958349 (1990-09-01), Tanner et al.
patent: 5329618 (1994-07-01), Moati et al.
patent: 5627843 (1997-05-01), Deng et al.
patent: 5701314 (1997-12-01), Armstrong et al.
patent: 5926647 (1999-07-01), Adams et al.
patent: 5942005 (1999-08-01), Hassner et al.
patent: 5948117 (1999-09-01), Weng et al.
patent: 6075812 (2000-06-01), Cafarella et al.
patent: 6131178 (2000-10-01), Fujita et al.
patent: 6138133 (2000-10-01), Oh
patent: 6167559 (2000-12-01), Furtek et al.
patent: 6173429 (2001-01-01), Twitchell et al.
patent: 6226334 (2001-05-01), Olafsson
Chi (A new fast Reed-Solomon decoding algorithm without Chien search; IEEE, Oct. 14, 1993).*
Clarke et al. (Implementation of dynamic look-up tables; IEEE, Nov. 1994).*
Nasiopulos, et al. (Adaptive compression coding; IEEE, Aug. 1991).*
Nasiopoulos et al., “Adaptive Compression Coding,” IEEE Transactions on Communications, vol. 39, No. 8, pp. 1245-1254 (Aug. 1991).
Chi, “A New Fast Reed-Solomon Decoding Algorithm Without Chien Search,” IEEE/IEE Electronic Library, Military Communications Conference, vol. 3, pp. 948-952 (Oct. 1993).
Clarke et al., “Implementation of Dynamic Look-Up Tables,” IEEE/IEE Electronic Library, Computers and Digital Techniques, vol. 141, pp. 391-397 (Nov. 1994).
PCT International Search Report, PCT/US00/22631, International file date Aug. 17, 2000, ( 3 pgs).
Chung Phung M.
Lamarre Guy
Motorola Inc.
LandOfFree
Method and apparatus for coding and decoding data does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for coding and decoding data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for coding and decoding data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2883805