From: junk@junk.net (Anton Erasmus) Newsgroups: comp.arch.fpga Subject: Doing Trig Functions in FPGA, EPLD Date: Fri, 07 Jun 2002 18:39:37 GMT Organization: The South African Internet Exchange Lines: 15 Message-ID: <3d00fc71.1352331@news.saix.net> Reply-To: antera@intekom.co.za NNTP-Posting-Host: bnb53-01-p143.nt.saix.net X-Trace: ctb-nnrp1.saix.net 1023474898 29529 155.239.180.143 (7 Jun 2002 18:34:58 GMT) X-Complaints-To: abuse@saix.net NNTP-Posting-Date: 7 Jun 2002 18:34:58 GMT X-Newsreader: Forte Free Agent 1.11/32.235 Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!newsfeed.icl.net!news.maxwell.syr.edu!newsfeed.cwix.com!ctb-nntp1.saix.net!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:18159 Hi, I have done simple EPLDs with device like Altera EPM7064 and 10K Flex series. So far I have used AHDL. How difficult is it to do math functions such as axis transformations in an EPLD ? I am trying to find out whether it would be possible to use a smallish EPLD / FPGA such as a FLEX 10K10 or 10K20 to provide meaningfull acceleration of axis transformation done with an 8 bit processor. The calculations are done in floating point, and the slowest functions are the sin, cos functions. I would be greatfull for any input regarding this. Regards Anton Erasmus ###### From: "Kevin Neilson" Newsgroups: comp.arch.fpga References: <3d00fc71.1352331@news.saix.net> Subject: Re: Doing Trig Functions in FPGA, EPLD Lines: 37 X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 6.00.2600.0000 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000 Message-ID: NNTP-Posting-Host: 12.253.117.91 X-Complaints-To: abuse@attbi.com X-Trace: sccrnsc01 1023485084 12.253.117.91 (Fri, 07 Jun 2002 21:24:44 GMT) NNTP-Posting-Date: Fri, 07 Jun 2002 21:24:44 GMT Organization: AT&T Broadband Date: Fri, 07 Jun 2002 21:24:44 GMT Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!wn1feed!wn4feed!worldnet.att.net!204.127.198.203!attbi_feed3!attbi.com!sccrnsc01.POSTED!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:18223 Trig functions aren't easy in a PLD, but they can be very fast. I'd recommend staying with fixed-point math, however. The barrel-shifting, etc. required for floating point eats up gates quickly and gets complicated. If you have some blockRAMs, you can use them for sin/cos lookup tables, and if not you can use pipelined Taylor expansions. Each of these takes a lot of gates for multipliers, though. If you can use a small VirtexII you can get embedded blockRAMs and multipliers. For the smallest implementation in cheaper chips go with Ray's CORDIC stuff, but I hope you have better luck figuring out how that works because I haven't yet. You might be able to split up the tasks between the processor and FPGA. I had to have an FPGA rotate a vector to compensate for distortion in a quad modulator. However, the angle of rotation was constant, so I could have the processor calculate the secant and tangent one time and that left the FPGA with only a couple of multiplies and sums to perform on each vector. -Kevin "Anton Erasmus" wrote in message news:3d00fc71.1352331@news.saix.net... > Hi, > > I have done simple EPLDs with device like Altera EPM7064 and 10K Flex > series. So far I have used AHDL. > How difficult is it to do math functions such as axis transformations > in an EPLD ? I am trying to find out whether it would be possible to > use a smallish EPLD / FPGA such as a FLEX 10K10 or 10K20 to > provide meaningfull acceleration of axis transformation done with > an 8 bit processor. The calculations are done in floating point, and > the slowest functions are the sin, cos functions. > I would be greatfull for any input regarding this. > > Regards > Anton Erasmus > ###### Message-ID: <3D0158D2.66DE87CE@andraka.com> From: Ray Andraka Organization: Andraka Consulting Group, Inc X-Mailer: Mozilla 4.77 [en] (WinNT; U) X-Accept-Language: en MIME-Version: 1.0 Newsgroups: comp.arch.fpga Subject: Re: Doing Trig Functions in FPGA, EPLD References: <3d00fc71.1352331@news.saix.net> Content-Type: multipart/alternative; boundary="------------048D58B233F58C1DA6DB1309" Lines: 226 Date: Sat, 08 Jun 2002 01:04:26 GMT NNTP-Posting-Host: 68.15.41.165 X-Complaints-To: abuse@cox.net X-Trace: news1.east.cox.net 1023498266 68.15.41.165 (Fri, 07 Jun 2002 21:04:26 EDT) NNTP-Posting-Date: Fri, 07 Jun 2002 21:04:26 EDT Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!cyclone.bc.net!news-hog.berkeley.edu!ucberkeley!nntp-relay.ihug.net!ihug.co.nz!cox.net!news1.east.cox.net.POSTED!53ab2750!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:18222 --------------048D58B233F58C1DA6DB1309 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Kevin, The hardware complexity of CORDIC is roughly equivalent of one to two multipliers depending on the FPGA, so in most cases if you are rotating a vector, CORDIC is the way to go. The exceptions are if you have only one or two fixed angles to rotate by, or if your precision requirements are low (8 bits or less generally). CORDIC isn't all that difficult to understand. Basically it is performing the rotation as a series of fixed angle rotations such that the sum of the rotations is equal to the desired total rotation. The angles are specifically chosen so that their tangents are powers of two. which leads to a shift-add operation. Starting with the rotation of a vector in a plane (a Givens rotation) straight from any trig book: x' = x cos a - y sin a y' = x sin a + y cos a divide out the cosines: x' = cos a * (x - y tan a) y' = cos a * (y +x tan a) Now, ignoring the cosine for a moment, if each elemental rotation is such that it's tangent is a power of 2 (45,26.5,14 etc degrees) the term inside the parenthesis is a shift and add/subtract x' = cos a * (x - y * 2^-i) y' = cos a * (y + x* 2^-i) where tan a = 2^-i OK, so what about that cosine? Well, if at each iteration we always rotate by either atan(2^-i) or -atan(2^-i), which is to say we always rotate by that elemental angle but we pick the rotation direction that best improves the result toward our goal. By limiting the rotation angle to +/- a, the cosine term becomes a constant since cos(a) = cos(-a). So for each iteration or elemental angle the rotation is: x[i+1] = Ki * (x[i] - y[i] * 2^-i) y[i+1] = Ki * (y[i] + x[i]*2^-i) So for a single iteration we one direction or the other by atan(2^-i) degrees. To rotate through a desired angle then, we increment i and rotate the result from the previous iteration through the new angle. The decision on the angle direction each time is made so that the rotation always rotates the vector toward the target. The sequence of the direction decisions uniquely identifies an angle in an arctangent base. A third chain of add/subtracts can be used to convert that arctangent base into any convenient angle system. Now that you hopefully understand how the rotations are done, pick up the paper to get a deeper understanding of the operation and more importantly of all the different modes and a flavor of the applications. It isn't magic, just a really neat application of algebra and trig. Kevin Neilson wrote: > Trig functions aren't easy in a PLD, but they can be very fast. I'd > recommend staying with fixed-point math, however. The barrel-shifting, etc. > required for floating point eats up gates quickly and gets complicated. If > you have some blockRAMs, you can use them for sin/cos lookup tables, and if > not you can use pipelined Taylor expansions. Each of these takes a lot of > gates for multipliers, though. If you can use a small VirtexII you can get > embedded blockRAMs and multipliers. For the smallest implementation in > cheaper chips go with Ray's CORDIC stuff, but I hope you have better luck > figuring out how that works because I haven't yet. > > You might be able to split up the tasks between the processor and FPGA. I > had to have an FPGA rotate a vector to compensate for distortion in a quad > modulator. However, the angle of rotation was constant, so I could have the > processor calculate the secant and tangent one time and that left the FPGA > with only a couple of multiplies and sums to perform on each vector. > > -Kevin > > "Anton Erasmus" wrote in message > news:3d00fc71.1352331@news.saix.net... > > Hi, > > > > I have done simple EPLDs with device like Altera EPM7064 and 10K Flex > > series. So far I have used AHDL. > > How difficult is it to do math functions such as axis transformations > > in an EPLD ? I am trying to find out whether it would be possible to > > use a smallish EPLD / FPGA such as a FLEX 10K10 or 10K20 to > > provide meaningfull acceleration of axis transformation done with > > an 8 bit processor. The calculations are done in floating point, and > > the slowest functions are the sin, cos functions. > > I would be greatfull for any input regarding this. > > > > Regards > > Anton Erasmus > > -- --Ray Andraka, P.E. President, the Andraka Consulting Group, Inc. 401/884-7930 Fax 401/884-7950 email ray@andraka.com http://www.andraka.com "They that give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety." -Benjamin Franklin, 1759 --------------048D58B233F58C1DA6DB1309 Content-Type: text/html; charset=us-ascii Content-Transfer-Encoding: 7bit Kevin,

The hardware complexity of CORDIC is roughly equivalent of one to two multipliers depending on the FPGA, so in most cases if you are rotating a vector, CORDIC is the way to go.  The exceptions are if you have only one or two fixed angles to rotate by, or if your precision requirements are low (8 bits or less generally).  CORDIC isn't all that difficult to understand.  Basically it is performing the rotation as a series of fixed angle rotations such that the sum of the rotations is equal to the desired total rotation.  The angles are specifically chosen so that their tangents are powers of two. which leads to a shift-add operation.

Starting with the rotation of a vector in a plane (a Givens rotation) straight from any trig book:

    x' = x cos a  - y sin a
    y' = x sin a + y cos a

divide out the cosines:
    x' = cos a * (x - y tan a)
    y' = cos a * (y +x tan a)

Now, ignoring the cosine for a moment, if each elemental rotation is such that it's tangent is a power of 2 (45,26.5,14 etc degrees) the term inside the parenthesis is a shift and add/subtract

    x' = cos a * (x - y * 2^-i)
    y' = cos a * (y + x* 2^-i)
    where tan a = 2^-i

OK, so what about that cosine?  Well, if at each iteration we always rotate by either atan(2^-i) or -atan(2^-i), which is to say we always rotate by that elemental angle but we pick the rotation direction that best improves the result toward our goal.  By limiting the rotation angle to +/- a, the cosine term becomes a constant since cos(a) = cos(-a).  So for each iteration or elemental angle the rotation is:

    x[i+1] = Ki * (x[i] - y[i] * 2^-i)
    y[i+1] = Ki * (y[i] + x[i]*2^-i)

So for a single iteration we one direction or the other by atan(2^-i) degrees.  To rotate through a desired angle then, we increment i and rotate the result from the previous iteration through the new angle.

The decision on the angle direction each time is made so that the rotation always rotates the vector toward the target.  The sequence of the direction decisions uniquely identifies an angle in an arctangent base.  A third chain of add/subtracts can be used to convert that arctangent base into any convenient angle system.

Now that you hopefully understand how the rotations are done, pick up the paper to get a deeper understanding of the operation and more importantly of all the different modes and a flavor of the applications.  It isn't magic, just a really neat application of algebra and trig.
 
 

Kevin Neilson wrote:

Trig functions aren't easy in a PLD, but they can be very fast.  I'd
recommend staying with fixed-point math, however.  The barrel-shifting, etc.
required for floating point eats up gates quickly and gets complicated.  If
you have some blockRAMs, you can use them for sin/cos lookup tables, and if
not you can use pipelined Taylor expansions.  Each of these takes a lot of
gates for multipliers, though.  If you can use a small VirtexII you can get
embedded blockRAMs and multipliers.  For the smallest implementation in
cheaper chips go with Ray's CORDIC stuff, but I hope you have better luck
figuring out how that works because I haven't yet.

You might be able to split up the tasks between the processor and FPGA.  I
had to have an FPGA rotate a vector to compensate for distortion in a quad
modulator.  However, the angle of rotation was constant, so I could have the
processor calculate the secant and tangent one time and that left the FPGA
with only a couple of multiplies and sums to perform on each vector.

-Kevin

"Anton Erasmus" <junk@junk.net> wrote in message
news:3d00fc71.1352331@news.saix.net...
> Hi,
>
> I have done simple EPLDs with device like Altera EPM7064 and 10K Flex
> series. So far I have used AHDL.
> How difficult is it to do math functions such as axis transformations
> in an EPLD ? I am trying to find out whether it would be possible to
> use a smallish EPLD / FPGA such as a FLEX 10K10 or 10K20 to
> provide meaningfull acceleration of axis transformation done with
> an 8 bit processor. The calculations are done in floating point, and
> the slowest functions are the sin, cos functions.
> I would be greatfull for any input regarding this.
>
> Regards
>    Anton Erasmus
>

--
--Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
401/884-7930     Fax 401/884-7950
email ray@andraka.com
http://www.andraka.com

 "They that give up essential liberty to obtain a little
  temporary safety deserve neither liberty nor safety."
                                          -Benjamin Franklin, 1759
  --------------048D58B233F58C1DA6DB1309--