1
\$\begingroup\$

In this book both Table Based methods and Cordic iterations are explained. computationally speaking i suppose the Table based is usually faster, even though it probably requires more resource, while Cordic is probably slower, but probably less resource consuming (if my understanding is correct, it should be a specific instance of shift and adds algorithm). But are there other benefits/drawback in both approach? I suppose also the CORDIC doesn't suffer of the table maker dilemma, even though it in general requires a LUT.

\$\endgroup\$

2 Answers 2

1
\$\begingroup\$

By reconfiguring the adders between registers slightly, the basic CORDIC hardware can compute rotations, inverse rotations, reciprocals, and a whole bunch of others. As there are few coefficients, the algorithm can be laid out from multiple iterations using serial registers (very slow and very small) to multiple ranks of wide registers in a pipeline (one result per system clock cycle, big and fast) and all tradeoffs in between.

Throwing a few more bits on for extra accuracy is straightforward, it takes another cycle per bit, and a linear increase in coefficient and working storage. Doing the same with a table based approach could require a polynomial increase in the size of the tables.

These days when most FPGAs have dedicated multipliers, the decision which to employ might often be taken by what mix of resource you have left nearing the end of the design. If there are some spare multipliers, then use Taylor series or similar because more people know about that and it's easy to synthesise. If none then implement CORDIC in the fabric.

\$\endgroup\$
2
  • \$\begingroup\$ But for given accuracy and area, because I assume one could implement the cordic using radix different than 2, would the speed of both implementation be comparable? Or would be one much slower than the other? I understand the best way to understand this would be to implement it, however I'm still struggling a bit on how the cordic works. \$\endgroup\$ Jul 6, 2016 at 13:19
  • \$\begingroup\$ As you increase the radix a CORDIC uses, you lose the simplicity of the base 2 implementation. However a higher radix will speed it up. As you make a table method have sub-tables, with a set of tables for the top 4 bits, then the next 4, then the next 4, done in multiple passes, you blur and even lose the distinction between that and a radix 16 CORDIC. Neither are significantly slower, they both get used, and if one was very inferior, it would not be used. Try this for a [CORDIC 101] (forums.parallax.com/discussion/127241/cordic-for-dummies) \$\endgroup\$
    – Neil_UK
    Jul 6, 2016 at 13:36
1
\$\begingroup\$

Maybe you are missing the advantage of CORDIC vs. look up table which is the fact that the effort grows only logarithmically with accuracy with CORDIC (runtime) vs. linearly with lookup tables (size).

I.e. if you want increase accuracy from \$n\$ bits to \$n+1\$ bits

  • with CORDIC you just have to do another step vs.
  • with lookup table you need a table that has twice the size.
\$\endgroup\$
6
  • \$\begingroup\$ How about the speed? \$\endgroup\$ Jul 6, 2016 at 13:26
  • \$\begingroup\$ With steps I mean time steps (and time is inversely proportional to speed). But the important fact is logarithmic vs. linear. I.e. if you increase accuracy more and more there will come the point where CORDIC is better because the lookup table you needed would be huge. \$\endgroup\$
    – Curd
    Jul 6, 2016 at 14:01
  • \$\begingroup\$ Also the lookup table needs time (access time which would be ~log(n)) \$\endgroup\$
    – Curd
    Jul 6, 2016 at 14:02
  • \$\begingroup\$ @Groo: yes, since \$n\$ is the number of bits (which is already \$log(size)\$; so access times for both methods are \$O(n)\$ and one CORDIC step costs probably more time than one look-up table (binary search) step. So, yes: only size matters (not access time). \$\endgroup\$
    – Curd
    Feb 28, 2019 at 9:13
  • \$\begingroup\$ @Curd: I meant to say access time for the lookup table is O(1), i.e. constant: calculate the index and read it from the table (i = x / table_size; value = lut[i];). There is only a single "expensive" operation, which is division, which CORDIC doesn't use, but doubling the lookup table to get better precision doesn't cost anything except storage space. \$\endgroup\$
    – Groo
    Feb 28, 2019 at 10:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.