Universal Reed-Solomon coder/encoder

Claim 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.

Claim 9

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.

Claim 10

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.

Claim 11

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 α n 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.

Claim 12

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 α n 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.

Claim 13

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 α n 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.

Claim 14

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 α n 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.

Claim 17

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.

Claim 18

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.

Claim 19

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.

Claim 20

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.