Multiply and accumulate feedback
A method and apparatus may be used to evaluate a polynomial by initializing a multiply and accumulate feedback apparatus ( 260 ) comprising a multiplier stage ( 264 ) having an output coupled to an input of an accumulator stage ( 267 ) having an accumulator feedback output ( 269 ) selectively coupled to an input of the multiplier stage over a plurality of clock cycles; iteratively calculating a final working loop variable z over an additional plurality of clock cycles; multiplying the final working loop variable z and a complex input vector x to compute a final multiplier value; and adding a least significant complex polynomial coefficient to the final multiplier value using the multiplier stage of the multiply and accumulate feedback apparatus to yield a result of the polynomial evaluation.
1. A method for evaluating a polynomial in an electronic system, comprising:
initializing a multiply and accumulate feedback apparatus comprising a multiplier stage having an output coupled to an input of an accumulator stage, the accumulator stage having an accumulator feedback output selectively coupled to an input of the multiplier stage over a plurality of clock cycles to generate a plurality of initial working loop variables (z 0 0, z 0 1, . . . z 0 N) at the accumulator feedback output;
calculating a final working loop variable z from the plurality of initial working loop variables using a plurality of iterative passes of the multiply and accumulate feedback apparatus to generate a plurality of final working loop values (z0, z1, . . . zN) over an additional plurality of clock cycles;
multiplying the final working loop variable z and a complex input vector x to compute a final multiplier value using the multiplier stage of the multiply and accumulate feedback apparatus; and
adding a least significant complex polynomial coefficient to the final multiplier value using the multiplier stage of the multiply and accumulate feedback apparatus to yield a result of the polynomial evaluation.
2. The method of claim 1 , where the method for evaluating the polynomial is used to perform digital pre-distortion in the electronic system.
3. The method of claim 1 , where initializing the multiply and accumulate feedback apparatus comprises providing the multiply and accumulate feedback apparatus with first and second complex polynomial coefficients and a plurality of input values (|x 0 |, |x 1 |, . . . |x N |) from a real input vector |x| which are sequentially input over a plurality of clock cycles, thereby generating the plurality of initial working loop variables (z 0 0, z 0 1, . . . z 0 N) at the accumulator feedback output.
4. The method of claim 3 , where initializing the multiply and accumulate feedback apparatus comprises multiplexing the first complex polynomial coefficient and the accumulator feedback output at a multiplex selection circuit by applying a first control signal to output the first complex polynomial coefficient during the plurality of clock cycles.
5. The method of claim 3 , where calculating the final working loop variable z comprises providing the multiply and accumulate feedback apparatus, at each iterative pass, with a replacement complex polynomial coefficient, the feedback output, and the plurality of input values (|x 0 |, |x 1 |, . . . |x N |) which are sequentially input over an additional plurality of clock cycles, thereby generating a plurality of final working loop values (z0, z1, . . . zN) to form the final working loop variable z.
6. The method of claim 1 , where initializing the multiply and accumulate feedback apparatus comprises:
storing a first complex polynomial coefficient a p at a first storage device coupled to a first input of the multiplier stage for the plurality of clock cycles;
sequentially storing the plurality of input values (|x 0 |, |x 1 |, . . . |x N |) at a second storage device coupled to a second input of the multiplier stage during the plurality of clock cycles;
storing at each clock cycle the output of the multiplier stage at a third storage device coupled to a first input of the accumulator stage;
storing at each clock cycle of the plurality of clock cycles a second complex polynomial coefficient a p−1 at a fourth storage device coupled to a second input of the accumulator stage; and
storing at each clock cycle the accumulator feedback output at a fifth storage device coupled to an input of the first storage device.
7. The method of claim 6 , where calculating the final working loop variable z comprises:
storing the accumulator feedback output from the fifth storage device at the first storage device during the additional plurality of clock cycles;
sequentially storing the plurality of input values (|x 0 |, |x 1 |, . . . |x N |) at the second storage device during the additional plurality of clock cycles;
storing at each clock cycle the output of the multiplier stage at the third storage device;
storing at each clock cycle of the additional plurality of clock cycles a complex polynomial coefficient a n at the fourth storage device; and
storing at each clock cycle the accumulator feedback output at the fifth storage device.
8. The method of claim 7 , where multiplying the final working loop variable z and the complex input vector x comprises:
storing the final working loop variable z in the first storage device;
storing the complex input vector x at the second storage device; and
storing the output of the multiplier stage as the final multiplier value in the third storage device.
9. The method of claim 8 , where adding the least significant complex polynomial coefficient to the final multiplier value comprises:
storing the final multiplier value at the third storage device;
storing the least significant complex polynomial coefficient in the fourth storage device; and
storing the output of the accumulator stage as the result of the polynomial evaluation at the fifth storage device.
10. A device for evaluating a polynomial expression of order P, comprising:
a multiplier hardware stage coupled to receive first and second multiplier operands from first and second clocked latch circuits, where the multiplier hardware stage generates a product of the first and second multiplier operands at a multiplier hardware stage output over a plurality of clock cycles;
an accumulator stage coupled to receive first and second addition operands from third and fourth clocked latch circuits, where the accumulator stage generates a sum of the first and second addition operands at an accumulator stage output over the plurality of clock cycles, where the accumulator stage is coupled to receive the second addition operand from the multiplier hardware stage output, and where the accumulator stage output is selectively coupled in feedback to provide the second multiplier operand to the multiplier hardware stage.
11. The device of claim 10 , further comprising a multiplex selection circuit coupled to receive a first complex polynomial coefficient a p at a first input and to receive the accumulator stage output at a second input, where the multiplex selection circuit is controlled to output the first complex polynomial coefficient a p only during a plurality of initiation clock cycles.
12. The device of claim 10 , where the first clocked latch circuit comprises a flip-flop storage device for sequentially storing a plurality of input values (|x 0 |, |x 1 |, . . . |x N |) from a real input vector |x| which are sequentially input as the first multiplier operand over a plurality of clock cycles.
13. The device of claim 10 , where the second clocked latch circuit comprises a flip-flop storage device for storing a first complex polynomial coefficient a p during a plurality of initiation clock cycles, and for storing a plurality of final working loop values (z0, z1, . . . zN) generated and fed back by the accumulator stage over an additional plurality of clock cycles.
14. The device of claim 10 , where the third clocked latch circuit comprises a flip-flop storage device for sequentially storing a plurality of complex polynomial coefficients (a p−1 , a p−2 , . . . a 0 ), each of which is sequentially input as the first addition operand over N clock cycles.
15. The device of claim 10 , where the fourth clocked latch circuit comprises a flip-flop storage device for sequentially storing the product of the first and second multiplier operands generated at the multiplier hardware stage output over a plurality of clock cycles.
16. The device of claim 10 , further comprising a fifth clocked latch circuit comprising a flip-flop storage device for sequentially storing the sum of the first and second addition operands generated at the accumulator stage output over a plurality of clock cycles.
17. The device of claim 10 , where the clocked latch circuits are clocked so that the multiplier hardware stage and accumulator stage carry out Horner's rule on the polynomial expression of order P by performing complex multiply and addition operations in each clock cycle to process different values from a complex input vector x=(x 0 , x 1 , . . . x N ).
18. A multiply and accumulate feedback circuit for evaluating a polynomial of order P different values from a complex input vector x=(x 0 , x 1 , . . . x N ), comprising:
a multiplier circuit for computing a product of first and second multiplier operands input to the multiplier circuit, where the product is output at a multiplier stage output at each clock cycle;
an accumulator circuit coupled to the multiplier stage output for computing a sum of first and second addition operands input to the accumulator circuit, where the sum is output at an accumulator stage output at each clock cycle;
a feedback storage device coupled to the accumulator stage output for storing the sum for feedback as in input to the multiplier circuit;
an input multiplexer circuit coupled to the feedback storage device for multiplexing a first complex polynomial coefficient a p and the accumulator stage output by applying a first control signal to output the first complex polynomial coefficient a p during a plurality of initiation clock cycles and to output the accumulator stage output during a plurality of additional clock cycles;
first and second clocked storage devices for providing the first and second multiplier operands to the multiplier circuit; and
third and fourth clocked storage devices for providing the first and second addition operands to the accumulator circuit,
where the clocked storage devices are clocked so that the multiplier circuit and accumulator circuit carry out Horner's rule on the polynomial of order P by performing complex multiply and addition operations in each clock cycle to process different values from the complex input vector x=(x 0 , x 1 , . . . x N ).
19. The multiply and accumulate feedback circuit of claim 18 , where the first clocked storage device sequentially provides a plurality of input values (|x 0 |, |x 1 |, . . . |x N |) from the real input vector |x| as the first multiplier operand over the initiation clock cycles and the plurality of additional clock cycles, and where the second clocked storage device provides the output from the input multiplexer circuit over the initiation clock cycles and the plurality of additional clock cycles.
20. The multiply and accumulate feedback circuit of claim 18 , where the third clocked storage device provides a plurality of complex polynomial coefficients (a p−1 , a p−2 , . . . a 0 ), each of which is sequentially input as the first addition operand over N clock cycles, and where the fourth clocked storage device provides the multiplier stage output over the initiation clock cycles and the plurality of additional clock cycles.