Universal Reed-Solomon coder/encoder

• US 5,771,244 A
• Filed: 03/09/1994
• Issued: 06/23/1998
• Est. Priority Date: 03/09/1994
• Status: Expired due to Fees

• Current Assignee: University of Southern California
• Original Assignee: University of Southern California
• Inventors: Truong, T. K., Reed, Irving S., Hsu, Chin Chi
• Primary Examiner(s): Elmore, Reba I.
• Assistant Examiner(s): BROWN, THOMAS
• Application Number:
  US08/208,269
• Time in Patent Office: 1,567 Days
• Field of Search: 371/37.1, 371/38.1, 371/39.1, 371/40.1, 371/37.01, 371/37.5, 371/37.8, 371/37.9, 371/37.07, 371/37.08, 371/37.09, 371/37.11, 371/37.12
• US Class Current: 714/752
• CPC Class Codes: H03M 13/151 using error location or error correction polynomials
• CPC Class Codes: H04L 1/0043 Realisations of complexity reduction techniques, e.g. use of look-up tables
• CPC Class Codes: H04L 1/0052 Realisations of complexity reduction techniques, e.g. pipelining or use of look-up tables
• CPC Class Codes: H04L 1/0057 Block codes H04L1/0061, H04L1/0064 take precedence
• CPC Class Codes: H04L 1/0065 Serial concatenated codes

Abstract

A Reed-Solomon encoding and decoding system is described which uses the decoder as an encoder. The input bit is formed into a codeword having all parity symbols marked as erasures. The decoder decodes this codeword by inputting the proper parity information. Various techniques of operating a preferred Reed-Solomon coder over the Galois Field GF(257) are also described. Special calculation load reduction techniques over GF(257) and GF(256) are also described.

Claims

1. A half-duplex system using a single Reed-Solomon decoding device, comprising the steps of:

means for determining if a communication is to be decoded or encoded;

a single Reed-Solomon decoder, for both said encoding and said decoding;

a parity marking device, receiving a message to be encoded and forming an extended and corrupted codeword in which all parity symbols thereof have been marked as erasures;

a signal switching device responsive to said determining means, switching paths to couple a signal which is determined as one to be encoded to said parity marking device, and coupling said codeword including erasure-marked parity symbols to said single Reed-Solomon decoder, and to couple a signal to be decoded, directly, without making parities as erasures to said Reed-Solomon decoder, wherein said parity marking device includes;

means for obtaining a message polynomial m(x) to be encoded, and

means for forming the message polynomial m(x) into a codeword of the form m(x) xd-1+P(x)c, where P(x)c represents a deliberately-corrupted and marked parity portion, and

means for feeding said deliberately-corrupted and marked message to said signal switching device.

2. A Reed-Solomon coding and/or decoding system comprising

means for receiving an input sequence to be coded;

means for calculating values necessary to translate the input sequence into an output sequence, and

providing the output sequence based on said values,

said calculating means including;

two look-up tables, a NUM2POWER table having an input value of α

ⁿ and an output value of n, and a POWER2NUM table having an input value of k, and an output value of α

^k, where α

is the primitive element of the calculation step; and

means for carrying out a multiplication operation

c=a×

b mod Q by looking up;

POWER2NUM (NUM2POWER a!+NUM2POWER b!) mod (Q-1)! in said two look-up tables, such that all calculations can be carried out without any multiplications or divisions.

4. A system as in claim 2, wherein said calculating means is a reduced instruction set type microprocessor.

3. A Reed-Solomon coding and/or decoding system comprising:

means for receiving an input sequence;

means for calculating values necessary to translate the input sequence into an output sequence, and

providing the output sequence based on said values,

said calculating means including;

two look-up tables, a NUM2POWER table having an input value of α

ⁿ and an output value of n, and a POWER2NUM table having an input value of k, and an output value of α

^k, where α

is the primitive element of the calculation step; and

means for carrying out a division operation c=a/b mod Q by looking up POWER2NUM (NUM2POWER a!-NUM2POWER b!) mod (Q-1)! such that all calculations can be carried out without any multiplications or divisions.

5. A system as in claim 3, wherein said calculating means is a reduced instruction set type microprocessor.

6. A method of operating a half-duplex system using a single Reed-Solomon decoding device, comprising the steps of:

determining if a communication is to be decoded or encoded;

providing a single Reed-Solomon decoder for both said encoding and said decoding;

if said signal is determined as one to be encoded, forming an erasure-marked codeword in which all parity symbols thereof have been intentionally marked as erasures, and coupling said codeword including erasure-marked parity symbols to said Reed-Solomon decoder;

if said signal is to be decoded, coupling said signal directly, without marking, to said Reed-Solomon decoder;

wherein said corrupting and erasure-marking step includes the steps of;

obtaining a message polynomial m(x) to be encoded;

forming the message polynomial m(x) into a codeword of the form m(x) x^d-1 +P(x)c, where P(x)c represents a deliberately-corrupted and erasure-marded parity portion, and

feeding said deliberately-corrupted and erasure-marked message to said Reed-Solomon decoder system.

7. A method of Reed-Solomon coding and/or decoding an input sequence into an output sequence, comprising the steps of:

receiving the input sequence;

calculating values necessary to translate the input sequence into an output sequence; and

providing the output sequence based on said values,

wherein said calculating values step includes the steps of;

storing in advance two look-up tables, a NUM2POWER table having an input value of α

ⁿ and an output value of n, and a POWER2NUM table having an input value of k, and an output value of α

^k, where α

is the primitive element of the calculating step; and

carrying out a multiplication operation c=a×

b mod Q by looking up;

POWER2NUM (NUM2POWER a!+NUM2POWER b!) mod (Q-1)! in said two look-up tables, such that all calculations can be carried out without any multiplications or divisions.

9. A method as in claim 7 wherein said operation is carried out by a reduced-instruction-set type microprocessor.

8. A method of Reed-Solomon coding and/or decoding an input sequence into an output sequence, comprising the steps of:

receiving the input sequence;

calculating values necessary to translate the input sequence into an output sequence; and

providing the output sequence based on said values,

wherein said calculating values step includes the steps of;

storing in advance two look-up tables, a NUM2POWER table having an input value of α

ⁿ and an output value of n, and a POWER2NUM table having an input value of k, and an output value of α

^k, where α

is the primitive element of the calculating step; and

carrying out a division operation c=a/b mod Q by looking up POWER2NUM (NUM2POWER a!-NUM2POWER b!) mod (Q-1)! such that all calculations can be carried out without any multiplications or divisions.

10. A method as in claim 8 wherein said operation is carried out by a reduced-instruction-set type microprocessor.

11. A method of operating to create Reed-Solomon values, comprising the steps of:

obtaining a Reed-Solomon message to be decoded;

computing syndromes from the data by using a forward transform defined by ##EQU68## in the Galois field of a prime number;

calculating only d-1 coefficients of the desired syndromes, where d=the number of errata, according to the equation ##EQU69## calculating a decimation in time FFT-like calculation using multiple stages and creating Reed-Solomon values based thereon.

12. A method of using a Reed-Solomon decoder to encode a message, comprising the steps of:

providing a Reed-Solomon decoder;

forming an erasure-marked codeword, including a message portion and a parity portion, and including areas of said parity portion which are intentionally marked as erasures;

feeding said erasure-marked codeword to the Reed-Solomon decoder; and

using said Reed-Solomon decoder to decode the erasure-marked codeword into a valid codeword, which includes an intact message portion and a valid parity portion, and which hence represents an encoded message;

wherein said step of forming a deliberately-corrupted and erasure-marked codeword includes the steps of;

obtaining a message polynomial m(x) to be encoded;

forming the message polynomial m(x) into a codeword of the form m(x) x^d-1 +P(x)c, where P(x)c represents a codeword with a corrupted and erasure-marked parity portion, all portions of which are marked as erasures, and

feeding the message polynomial with the corrupted and erasure-marked parity portion to said Reed-Solomon decoder system.