To reduce the processing amount of a field multiplication. A matrix application apparatus computes a vector b by multiplying a vector a and a matrix A, provided that a denotes a k-th order vector having elements a.sub.0, . . . , a.sub.k1 (a.sub.0, . . . , a.sub.k1GF(x.sup.q)), b denotes an m-th order vector having elements b.sub.0, . . . , b.sub.m1 (b.sub.0, . . . , b.sub.m1GF(x.sup.q)), and A denotes a m-by-k Vandennonde matrix. A polynomial multiplication part computes a value b.sub.i. An order reduction part designates g.sub.ih.sub.if as the value b.sub.i by using a polynomial h.sub.i obtained by dividing a part of the value b.sub.i having an order equal to or higher than q by X.sup.q and a polynomial g.sub.i formed by a part of the value b.sub.i having an order lower than q.

An integrated circuit (IC) includes an encoder circuit. The encoder circuit includes an encoding input configured to receive an input message including one or more data symbols. Each data symbol has N bits and N is a positive integer. The encoder circuit includes an encoding unit configured to perform Reed-Solomon encoding to the one or more data symbols to generate one or more coding symbols. The Reed-Solomon encoding uses a Galois field having an order that is less than 2.sup.N. A coded message that includes the one or more data symbols and the one or more coding symbols is provided at an encoding output of the encoder circuit.

A syndrome calculation circuit receives input data r(x) including data and a parity bit and having a code length n of (2.sup.m1) bits at maximum which is represented by a Galois field GF(2.sup.m), and performs syndrome calculation so as to meet
s.sup.i+.sup.j
z(.sup.i+).sup.1+.sup.1+(.sup.j+).sup.1+.sup.1(A)
thereby calculating syndromes s and z. An error position polynomial coefficient calculation circuit calculates the coefficient of an error position polynomial to obtain sz by multiplying s and z by one multiplier. After that, 2-bit error data positions i and j are specified. Errors at the error data positions i and j of the input data are corrected.

A coding circuit includes an encoder circuit configured to generate an input codeword by concatenating an input data and a parity generated by processing the input data using an odd parity generator matrix; and a decoder circuit configured to correct a double error from an output codeword, and to detect a triple error using a syndrome generated by processing the output codeword using the odd parity generator matrix, wherein each column of the odd parity generator matrix has a respective odd number of 1's.

Embodiments relate to the emulation of the effect of Forward Error Correction (FEC) codes, e.g., GF.sup.10 Reed Solomon (RS) FEC codes, on the bit error ratio (BER) of received Pseudo-Random Binary Sequences (PRBS) patterns. In particular, embodiments group errors into RS-FEC symbols and codewords in order to determine if the errors are correctable. By emulating the error correction capabilities of FEC codes in order to determine which errors are correctable by the code, embodiments afford a more accurate representation of the post-FEC BER of RS FEC codes from links carrying PRBS patterns. This FEC code emulation provides error correction statistics, for stand-alone use or for error correction in connection with Bit Error Rate Testers (BERTs).

A system for hardware error-correcting code (ECC) detection or correction of a received codeword from an original codeword includes an error-detecting circuit configured to process a selection of symbols of the received codeword using a set of factors, the original codeword being recomputable from a corresponding said selection of symbols of the original codeword using the set of factors. The error-detecting circuit includes a hardware multiplier and accumulator configured to use the set of factors and the selection of symbols of the received codeword to recompute remaining symbols of the original codeword, and a hardware comparator configured to compare the recomputed remaining symbols of the original codeword with corresponding said remaining symbols of the received codeword and to output first results of this comparison.

Examples disclosed herein relate to very large-scale integration (VLSI) circuit implementations of list decode circuits. In accordance with some examples disclosed herein, a device may include a first and second polynomial evaluation circuit, a field division circuit, a discrepancy filter, and an enhanced error locator polynomial (ELP) circuit. The first and second polynomial evaluation circuits may respectively evaluate a first and second polynomial output from a Berlekamp-Massey algorithm over a plurality of values in a finite field. The field division circuit may divide the outputs from the evaluations to generate a plurality of speculative discrepancy values for an additional iteration of the Berlekamp-Massey algorithm. The discrepancy filter circuit may filter the speculative discrepancy values down to a list of potentially valid discrepancy values that may be used by the enhanced ELP circuit to generate an enhanced ELP.

A system for software error-correcting code (ECC) protection or compression of original data using ECC data in a first memory is provided. The system includes a processing core for executing computer instructions and accessing data from a main memory, and a non-volatile storage medium for storing the computer instructions. The software ECC protection or compression includes: a data matrix for holding the original data in the first memory; a check matrix for holding the ECC data in the first memory; an encoding matrix for holding first factors in the main memory, the first factors being for encoding the original data into the ECC data; and a thread for executing on the processing core. The thread includes a Galois Field multiplier for multiplying entries of the data matrix by an entry of the encoding matrix, and a sequencer for ordering operations using the Galois Field multiplier to generate the ECC data.

An error correction code (ECC) decoder includes a finite state machine (FSM) controller and a shared logic circuit. The FSM controller generates a first control signal and a second control signal each corresponding to a certain state. The shared logic circuit includes a plurality of shared Galois field (GF) multipliers, a plurality of shared XOR arithmetic elements, and a plurality of shared multiplexers (MUXs), which are used for an operation selected between a syndrome operation, an error location polynomial operation, an error location operation and an error correction operation, in response to the first and second control signals.

Provided is a BCH decoder in which a folded multiplier is equipped. The BCH decoder may include a key equation solver including a plurality of multipliers. The multiplier includes a plurality of calculation blocks configured to perform a calculation operation. Each of the calculation blocks repeatedly performs a calculation operation of a calculation stage for a plurality of calculation stages, outputs one output value on the basis of at least one input value in each calculation stage, and is connected to at least one another calculation block to transfer an output value of a current calculation stage as an input value of the at least one another calculation block in a next calculation stage.