Polynomial expander for generating coefficients of a polynomial from roots of the polynomial

A polynomial expander circuit comprising:

• a plurality of coefficient storage registers operable to store polynomial coefficients;
• a temporary coefficient register coupled to an output terminal of the coefficient storage registers;
• a root register;
• a multiplier coupled to the root register and the output terminal of the coefficient storage registers, the multiplier operable to multiply a root value stored in the root register with a value stored in the coefficient storage registers;
• and
• an adder coupled to the multiplier and to an output terminal of the temporary coefficient register, the adder operable to sum the multiplier product with a value stored in the temporary coefficient register, the adder further coupled to input terminals of the coefficient storage registers and operable to provide the sum to the coefficient storage registers;
• and
• a multiplexer having an output terminal coupled to the input terminal of the temporary coefficient resister, a first input terminal coupled to the output terminal of the coefficient storage registers, and a second input terminal coupled to an initial value source.

A polynomial expander circuit comprising;

• a plurality of coefficient storage registers operable to store polynomial coefficients;
• a temporary coefficient register coupled to an output terminal of the coefficient storage registers;
• a root register;
• a multiplier coupled to the mot register and the output terminal of the coefficient storage registers, the multiplier operable to multiply a root value stored in the root register with a value stored in the coefficient storage resisters;
• an adder coupled to the multiplier and to an output terminal of the temporary coefficient register, the adder operable to sum the multiplier product with a value stored in the temporary coefficient register, the adder further coupled to input terminals of the coefficient storage registers and operable to provide the sum to the coefficient storage registers;
• a root multiplexer;
• and
• a root buffer register operable to store a root value while another root value is being processed,
• the root multiplexer having an output terminal coupled to the input terminal of the root register, a first input terminal coupled to a first source of root values, and a second input terminal coupled to an output terminal of the root buffer register, the root multiplexer operable to select between the first source of root values and the root buffer register as the source of the root value for the root register.

A computer-readable medium on which is stored computer instructions for creating in a programmable logic device a polynomial expander circuit comprising:

• a plurality of coefficient storage registers operable to store polynomial coefficients;
• a temporary coefficient register coupled to an output terminal of the coefficient storage registers;
• a root register;
• a multiplier coupled to the root register and the output terminal of the coefficient storage registers, the multiplier operable to multiply a root value stored in the root register with a value stored in the coefficient storage registers;
• an an adder coupled to the multiplier and to an output terminal of the temporary coefficient register, the adder operable to sum the multiplier product with a value stored in the temporary coefficient register, the adder further coupled to input terminals of the coefficient storage registers and operable to provide the sum to the coefficient storage registers;
• and
• a multiplexer having an output terminal coupled to the input terminal of the temporary coefficient register, a first input terminal coupled to the output terminal of the coefficient storage registers, and a second input terminal coupled to an initial value source.

A method for generating in a circuit coefficients of an expanded polynomial of a variable, X, from a predetermined number, n, of the roots of the polynomial, comprising:

• generating a respective coefficient for each of a X(j-1)term of the polynomial, with j being an integer from 1 to (n+1), with each respective coefficient being generated at a respective one of a first place at a right most place to a (n+1) place at a left most place;
• storing as a temporary coefficient the respective coefficient that was at said first place in a prior clock cycle;
• initializing the respective coefficient at the first place to a unitary value and any other respective coefficient not at the first place to a null value, and initializing the temporary coefficient to a null value;
• wherein said predetermined number, n, of the roots of the polynomial are provided serially from a first order to an nth order;
• generate an ith order multiplier output by multiplying an ith order root with the respective coefficient at the first place, and generating an ith order adder output by adding the temporary coefficient to said ith order multiplier output;
• shifting respective coefficients at and to the right of an (i+1) place toward the right with the respective coefficient at the first place being shifted to become the temporary coefficient, and shifting in said ith order adder output to be the respective coefficient at said (i+1) place;
• performing, generation of said ith order multiplier output and said ith order adder output and shifting of respective coefficients at and to the right of said (i+1) place, an (i+1) times for said ith order root with (i+1) clock cycles;
• and
• performing, said (i+1) times of generating said it order multiplier output and said ith order adder output and shifting of respective coefficients at and to the right of said (i+1) place for said ith order root, for each of said n-roots, for i=1 to n, to generate the respective coefficient for the X(j-1) term of the polynomial at a j-th place with (n+1)n/2 clock cycles, with j being an integer from 1 to (n+1).

In a polynomial expander circuit, a method of generating coefficients for a polynomial having a plurality of roots, the method comprising:

• providing a plurality of coefficient storage registers;
• providing a temporary coefficient register coupled to an output terminal of the coefficient storage registers;
• providing a root register;
• multiplying a root value stored in the root register with a value stored in the coefficient storage registers to generate a multiplier output;
• adding the multiplier output with a value stored in the temporary coefficient register to generate an adder output;
• shifting said adder output into the coefficient storage registers;
• and
• shifting, concurrently with the shifting of said adder output into the coefficient storage registers, the value stored in the coefficient storage registers into the temporary register as a next value in the temporary register.

In a polynomial expander circuit, a method of generating coefficients for a polynomial having a plurality of roots, the method comprising:

• providing a plurality of coefficient storage registers;
• providing a temporary coefficient register coupled to an output terminal of the coefficient storage registers;
• providing a root register;
• multiplying a root value stored in the root register with a value stored in the coefficient storage registers to generate a multiplier output;
• adding the multiplier output with a value stored in the temporary coefficient register to generate an adder output;
• shifting said adder output into the coefficient storage resisters;
• and
• selecting by a respective multiplexer the input to each coefficient storage register as one of said adder output or the output of a preceding coefficient storage register with said coefficient storage registers coupled in series.

In a polynomial expander circuit, a method of generating coefficients for a polynomial having a plurality of roots, the method comprising:

• providing a plurality of coefficient storage registers;
• providing a temporary coefficient register coupled to an output terminal of the coefficient storage registers;
• providing a root register;
• multiplying a root value stored in the root resister with a value stored in the coefficient storage registers to generate a multiplier output;
• adding the multiplier output with a value stored in the temporary coefficient register to generate an adder output;
• shifting said adder output into the coefficient storage registers;
• and
• storing, in a root buffer register, a root value generated by a root source while another root value is being processed through said coefficient storage registers.