Re: Vector Rotation

Greg Berchin wrote:

Looking for an algorithm to accomplish the following in FPGA/ASIC.
Accuracy needs to be very high; errors less than 1 part per million.
Speed, of course, is also crucial, but given the implementation context
I can pipeline to my heart's content:

I have two, two-dimensional vectors of arbitrary length and direction;
call them A and B. I need to find vector A' that is the same length as
A but in the direction of B. Of course, I could simply compute
A' = (|A|/|B|)*B
but that requires a square root and a divide. I thought about using
some variant of CORDIC to rotate A onto B, but I wonder if there's a
better way.

Thanks,
Greg Berchin

A method that I originally saw in the ADSP-2101 literature, but should port well to an FPGA, is to just do a polynomial expansion, i.e.

y = a_0 + a_1 x + a_2 x^2 + ... + a_n x^n.

This reduces to keeping a running result for x^n and doing a MAC for the a_n * x^n; with two multipliers you should be able to do it in not too much more than n+1 clock cycles, and n shouldn't have to be too big (I'm guessing 10 or so). You could save a multiplier by doubling the time, of course, or use 2n multipliers and do it in one computation/clock, if you had to.

The cool thing about the way they did it was that they did _not_ try to do a Taylor's series. Instead, they just started with the recognition that the series was going to be truncated, and they found the least-squares fit for the coefficients (this is easy to do on just about any math package -- you can even coerce Excel to do it).

This should work well for both square roots and for 1/|B|.

In your case I would start by finding a rough root (inverse) by shifting. For the square root find N such that x_r * 2^N = x and 0.25 < x_r <= 1; for the inverse find N such that x_r * 2^N = x and 0.5 < x_r <= 1. Then sqrt(x) = 2^N sqrt(r) and 1/x = 2^-N/x_r. This means that you can restrict the number of x_r^n terms you need to find, while still maintaining accuracy. Depending on your speed/area requirements you can find N in between 1 and N clock cycles.

--

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

Posting from Google? See http://cfaj.freeshell.org/google/
.