Error detection and correction in digital communication systems
First Claim
1. An error detection and correction system for locating and correcting double errors in a received data block word digitally encoded in a Reed-Solomon code (n,K) as coefficient terms of an n-order codeword polynomial in the form ##EQU20## where i is an integer and the coefficients are powers of the primitive a of a Galois field, which codeword is divisible by a code generator polynomial in the form of a product of a plurality of different factors in the form (x+ai), where ai is a power of said primitive a, said system comprising:
- syndrome generation means responsive to signals representing a received data block word for deriving four syndrome signals each corresponding to a respective first order syndrome equal to the remainder upon dividing in said Galois field said received data block word by a respective said factor;
error locator means for locating the terms in said received data block word containing respective said errors, said error locator means comprising means operating in said Galois field and responsive to said four syndrome signals for deriving a reference signal corresponding to the position of a reference term in said received data block word equally spaced relative to said terms containing said errors, means operating in said Galois field and responsive to said four syndrome signals for deriving a relative position signal corresponding to the number of terms by which the terms containing said errors are spaced from said reference term, and means for combining said reference signal and said relative position signal to form combined error location signals corresponding to the positions of the terms containing the respective errors;
error solution means responsive to said four syndrome signals for producing first and second error solution signals corresponding to the differences between the respective received terms containing said errors and the corresponding terms as encoded; and
error correction means responsive to said error location signals and said error solution signals for correcting said signals representing a received data block word.
4 Assignments
0 Petitions
Accused Products
Abstract
An error detection and correction system locates and corrects double errors in a received data block word digitally encoded in a Reed-Solomon code (n,K) as coefficient terms of an n-order codeword polynomial in the form ##EQU1## where the coefficients are powers of the primitive a of a Galois field, which codeword is divisible by a code generator polynomial in the form of a product of a plurality of different factors in the form (x+ai). Four syndrome signals are derived, each corresponding to a respective first order syndrome equal to the remainder upon dividing a received data block word by a respective factor. An error locator responsive to the four syndrome signals derives a reference signal corresponding to the position h of a reference term in the received data block word equally spaced relative to the two terms containing errors, and a relative position signal k corresponding to the number of terms by which the terms containing the errors are spaced from the reference term. An error solution circuit responsive to the four syndrome signals produces first and second error solution signals corresponding to the differences between the respective received terms containing the errors and the corresponding terms as encoded. An error correction circuit adds the error solution signals to the received data block at the proper places to reproduce the encoded codeword. A fifth syndrome signal may be used to determine if there are more than two errors. Two syndromes may be used to correct single errors.
77 Citations
20 Claims
-
1. An error detection and correction system for locating and correcting double errors in a received data block word digitally encoded in a Reed-Solomon code (n,K) as coefficient terms of an n-order codeword polynomial in the form ##EQU20## where i is an integer and the coefficients are powers of the primitive a of a Galois field, which codeword is divisible by a code generator polynomial in the form of a product of a plurality of different factors in the form (x+ai), where ai is a power of said primitive a, said system comprising:
-
syndrome generation means responsive to signals representing a received data block word for deriving four syndrome signals each corresponding to a respective first order syndrome equal to the remainder upon dividing in said Galois field said received data block word by a respective said factor; error locator means for locating the terms in said received data block word containing respective said errors, said error locator means comprising means operating in said Galois field and responsive to said four syndrome signals for deriving a reference signal corresponding to the position of a reference term in said received data block word equally spaced relative to said terms containing said errors, means operating in said Galois field and responsive to said four syndrome signals for deriving a relative position signal corresponding to the number of terms by which the terms containing said errors are spaced from said reference term, and means for combining said reference signal and said relative position signal to form combined error location signals corresponding to the positions of the terms containing the respective errors; error solution means responsive to said four syndrome signals for producing first and second error solution signals corresponding to the differences between the respective received terms containing said errors and the corresponding terms as encoded; and error correction means responsive to said error location signals and said error solution signals for correcting said signals representing a received data block word. - View Dependent Claims (2, 3, 4, 5)
-
-
6. A method for locating and correcting double errors in a received data block word digitally encoded in a Reed-Solomon code (n,K) as coefficient terms of an n-order codeword polynomial in the form ##EQU21## where i is an integer and the coefficients are powers of the primitive a of a Galois field, which codeword is divisible by a code generator polynomial in the form of a product of a plurality of different factors in the form (x+ai), where ai is a power of said primitive a, said method comprising:
-
responsive to signals representing a received data block word, deriving four syndrome signals each corresponding to a respective first order syndrome equal to the remainder upon dividing in said Galois field said received data block word by a respective said factor; locating the terms in said received data block word containing respective said errors by operating in said Galois field in response to said four syndrome signals to derive a reference signal corresponding to the position of a reference term in said received data block word equally spaced relative to said terms containing said errors, operating in said Galois field in response to said four syndrome signals to derive a relative position signal corresponding to the number of terms by which the terms containing said errors are spaced from said reference term, and combining said reference signal and said relative position signal to form combined error location signals corresponding to the positions of the terms containing the respective errors; responsive to said four syndrome signals, producing first and second error solution signals corresponding to the differences between the respective received terms containing said errors and the corresponding terms as encoded; and responsive to said error location signals and said error solution signals, correcting said signals representing a received data block word. - View Dependent Claims (7, 8, 9, 10)
-
-
11. A decoder for error correcting a received digital data block R(x) encoded as a codeword C(x) having a plurality of data bytes and a plurality of check bytes, said codeword being encoded in a Reed-Solomon code such that division of the received data block by the generator polynomial will produce a plurality of syndromes Si which contain information about the errors contained in the received code words, said decoder comprising:
-
means for generating a plurality of syndromes from a received code word, input register means for storing the generated syndromes when they become available from said syndrome generator, an arithmetic/logic unit (ALU) for performing arithmetic or logical operations on one or two operands input to a first channel or to a second channel of said unit in accordance with a control word and for outputting the results of the operation to an accumulator, output register means for storing the locations of the errors and the values of the errors in said received data block R(x), internal register means for the temporary storage of the output of said accumulator, a first data path connecting the output of said input register means and the output of said internal register means to one of said first and second channels of said ALU, a second data path connecting the output of said accumulator to the input of said output register means, the input of said internal register means, and the other of said first and second channels of said ALU, and processor means for controlling the transfer of data over said first and second data paths and for generating a control word which selects an operation for the (ALU). - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20)
-
Specification