Efficient hardware implementation of chien search polynomial reduction in reed-solomon decoding

A programmable logic device, comprising:

• control circuitry, for receiving program instructions and for generating control signals responsive thereto;
• a data bus;
• and
• a Chien search execution unit coupled to the data bus, for executing a Chien search instruction under the control of the control circuitry, and comprising:
• a plurality of finite field multipliers, each for performing finite field multiplication upon a symbol value and a coefficient to produce a product;
• finite field addition circuitry, for performing finite field addition of the products from the plurality of finite field multipliers to produce a final sum, said finite field addition circuitry comprising;
• a first finite field adder stage, for performing finite field addition of products from the plurality of finite field multipliers to produce a plurality of partial sums, and
• a final stage finite field adder, for performing finite field addition of the plurality of partial sums from the first finite field adder stage, to produce the final sum;
• zero detection circuitry, coupled to an output of the finite field addition circuitry, for generating a root detection signal responsive to the final sum equaling zero;
• and
• error magnitude and position circuitry, coupled to receive the root detection signal, for storing error magnitude and position values in selected registers responsive to receiving the root detection signal.

A method of operating a programmable logic device to execute a Chien search operation comprising the steps of:

• loading coefficient values into a coefficient register;
• in a first pass, performing the steps of:
• performing finite field multiplication of a plurality of pairs of coefficient values and paired powers of zero order symbol values to produce a first plurality of finite field products;
• storing the first plurality of finite field products into the coefficient register;
• summing the first plurality of finite field products to produce a first final sum;
• responsive to the first final sum indicating that the zero order symbol value generated a root, storing corresponding magnitude and position values into magnitude and position registers;
• and
• loading a plurality of symbol value powers into a symbol value register;
• and
• then, for each of a subsequent plurality of passes, performing the steps of:
• performing finite field multiplication of a plurality of pairs of coefficient values and symbol value powers to produce a subsequent plurality of finite field products;
• storing the subsequent plurality of finite field products into the coefficient register;
• summing the subsequent plurality of finite field products to produce a subsequent final sum;
• and
• responsive to the subsequent final sum indicating generation of a root, storing corresponding magnitude and position values into magnitude and position registers.

An electronic system, comprising:

• an interface for receiving signals, in the form of encoded digital data;
• and
• a programmable logic device, comprising:
• control circuitry, for receiving program instructions and for generating control signals responsive thereto;
• a data bus;
• a Chien search execution unit coupled to the data bus, for executing a Chien search instruction under the control of the control circuitry, and comprising:
• a plurality of finite field multipliers, each for performing finite field multiplication upon a symbol value and a coefficient to produce a product;
• finite field addition circuitry, for performing finite field addition of the products from the plurality of finite field multipliers to produce a final sum;
• zero detection circuitry, coupled to an output of the finite field addition circuitry, for generating a root detection signal responsive to the final sum equaling zero;
• error magnitude and position circuitry, coupled to receive the root detection signal, for storing error magnitude and position values in selected registers responsive to receiving the root detection signal;
• a symbol register, having outputs coupled to the plurality of finite field multipliers, for storing the symbol values;
• a coefficient register, having outputs coupled to the plurality of finite field multipliers, and having inputs coupled to outputs of the plurality of finite field multipliers, for storing the coefficients applied to the plurality of finite field multipliers, and for storing the products from the plurality of finite field multipliers.

An electronic system, comprising:

• an interface for receiving signals, in the form of encoded digital data;
• and
• a programmable logic device, comprising:
• control circuitry, for receiving program instructions and for generating control signals responsive thereto;
• a data bus;
• a Chien search execution unit coupled to the data bus, for executing a Chien search instruction under the control of the control circuitry, and comprising:
• a plurality of finite field multipliers, each for performing finite field multiplication upon a symbol value and a coefficient to produce a product;
• finite field addition circuitry, for performing finite field addition of the products from the plurality of finite field multipliers to produce a final sum, said finite field addition circuitry comprising:
• a first finite field adder stage, for performing finite field addition of products from the plurality of finite field multipliers to produce a plurality of partial sums, and
• a final stage finite field adder, for performing finite field addition of the plurality of partial sums from the first finite field adder stage, to produce the final sum;
• zero detection circuitry, coupled to an output of the finite field addition circuitry, for generating a root detection signal responsive to the final sum equaling zero;
• and
• error magnitude and position circuitry, coupled to receive the root detection signal, for storing error magnitude and position values in selected registers responsive to receiving the root detection signal.