Patent ID: 8832523

Claim:
An apparatus for correcting errors in a sequence of k n-state data symbols and a plurality of n-state check symbols, an n-state symbol being represented by a signal, with n>2, and k greater than 2, comprising: a memory enabled to store instructions; a processor that retrieves and executes instructions from the memory to perform the steps of: receiving on an input the sequence of k n-state symbols and the plurality of n-state check symbols being a plurality of codewords with at least two codewords having no n-state data symbols in common, wherein the n-state check symbols in the plurality of n-state check symbols are determined by a first arrangement of the k n-state data symbols in an at least two-dimensional matrix, wherein for each instance of the at least two-dimensional matrix at least a first and a second n-state check symbol are determined during a coding, by evaluating a first n-state expression to generate the first n-state check symbol and evaluating a second n-state expression to generate the second n-state check symbol, each n-state expression having all the n-state data symbols in an instance for which the n-state check symbols are determined as variables of a degree 1; arranging the received sequence of k n-state symbols in the first arrangement of the at least two-dimensional matrix, recalculating the first and second n-state check symbols for each instance of the at least two-dimensional matrix and comparing the received and recalculated check symbols to determine instances of the first and second dimensions of the at least two-dimensional matrix that are in error; determining at least two n-state syndrome equations of degree 1 for one dimension of the at least two-dimensional matrix from a comparison of received and recalculated n-state check symbols, wherein each variable in the at least two n-state syndrome equations has a degree 1 and a first unknown represents an error magnitude of a common n-state symbol in a first instance in error in the first dimension that is common with a first instance in error in the second dimension of the at least two-dimensional matrix; determining the error magnitude of the common n-state symbol by directly solving the at least two n-state syndrome equations of degree 1 for the first unknown; and generating a correct state of the common n-state symbol by combining the error magnitude with the common n-state symbol by applying an n-state logic function.