CORDIC in a land of built-in multipliers

Being bad because I'm cross-posting. Being bad because I'm cross-posting a reply to _my own post_.

Oh well -- I'm thinking that maybe some of the folks on comp.dsp who aren't also on comp.arch.fpga will have some thoughts.

I've considered it many times, but never used it. Then again it's not like I use the DSP blocks for CORDIC sorts of things anyhow; I just throw a RAM lookup table at the problem.

That was the other thing that I should have mentioned.

I've heard a lot of talk about CORDIC, but it seems to be one of those things that was Really Critically Important back when an Intel 4004 cost (reputedly) $5 in then-dollars, but maybe isn't so important now, when it seems like the package costs more than the silicon inside it.

There are still FPGAs at the lower end that don't include multipliers. I have an older design in a small FPGA I am still shipping that does the iterative adding thing. It has been a while since I considered using the CORDIC algorithm. What exactly is the advantage of the CORDIC algorithm again?

It uses less gates. Which is why I'm asking my question -- gates seem to be a lot cheaper these days, so do people still use CORDIC?

Can you explain that briefly? Why is it less gates than an adder? Adders are pretty durn simple. I thought the CORDIC algorithm used an ADD.

Opps, I see the CORDIC doesn't replace a multiplication... it replaces a sine calculation. I told you it had been a while since I looked at it.

Yes, I recall now the CORDIC typically converges faster than a power series and requires no multiplications. Do I have it now? Using fewer gates is a bit of an understatement.

My understanding (kind of limited) is that CORDIC is used for trig and exponential calculations, more than just multiplication. I have never used a CORDIC implementation in an FPGA or an ASIC. I tend to do more control path and communications implementations than DSP/data path stuff though.

BobH

It was used in (HP-)pocket calculators then and got well known that way. Later on floating point coprocessors. 8087, probably up to MC68882. Guess Cyrix were the first there to implement a big float multiplier and do it differently. In the 70ies and 80ies on (rad-hard) RCA1802 CPUs in AMSAT satellites. It calculates not only sin, cos, but also atan, atanh, sinh, cosh ... For navigation, robotics on small memory it may be still usefull.

But who knows after all these years what it is and how to implement it ? Same for Logarithmic Number Systems ( LNS ). There may be niche applications that benefit, but industry will not offer it, because customers will not know & buy.

MfG JRD

Cordic is used for items like sine, cosine, tangent, square root,etc with involves multiplication and some division, but the Cordic Algorithms eliminate multiply and divide so it simplifies the logic by quite a bit. It's mainly used with devices that do not have multiply and divide capability even then Cordic could be faster.

It can be faster at trig functions than multiplying (assuming the multiply was not with a parallel multiplier), but it is not faster than a multiplier at multiplying, even a shift and add multiplier. The CORDIC function converges at 1 bit per iteration. That's the same as a sequential multiplier doing a shift and add which is very similar to the CORDIC method.

The CORDIC function can always be pipelined to get higher throughput, but it is not likely to outrun a dedicated multiplier in an FPGA. Taylor series gets very high precisions very quickly.

ho

not

se

w,

. I

to

ADD.

If you properly chose your ranges then power series will converge many time s faster than CORDIC.

For example, you want sin(x) for x in range [0..pi/2]. You don't apply powe r series to a full range. Instead, you calculated it as sin(x_tab)*cos(x-x_tab)+cos(x)*sin(x-x_tab) Where, sin(x_tab)/cos(x_tab) are taken from small table, e.g. 64 entries. T hen, you only apply power series to x-x_tab, which is a small number. Such power series converges very quickly, in specific case of sin() and of 64-en try table, ~13 bits per iteration.

Please, don't take what is written above as an actual algorithm. It's just a guideline. An algorithm, that wants to produces a result with max. error of < 1 ULP, would have to be a little more careful about details.

Did 8087 use CORDIC for multiplication and division or only for trigonometric instructions, and, possibly, for BCD-binary conversions? I googled for an answer several months ago, but found nothing.

Unlikely. Nowadays, even small ARM Cortex-M4 has fast multiplier and is typically coupled with at least 128 KB of on-chip NOR flash. And robotics tend to use bigger CPUs than Cortex M4.

I've been designing DSP ASIC's since the 1980's and have never chosen to use Cordic. I can envision where Cordic might make sense -- where the precision requirements are not really known or are very high, Cordic will win over LUT-based designs but most typically the LUT-based designs are a simpler way to meet the requirement.

It's also possible that in some PLD-based designs Cordic might be the way to go.

Steve

(snip)

Why, logarithmic number systems are commonly used e.g. in the log-APP algorithm, as a part of turbo-decoders.

Evgeny

Yes, well, some turbo decoders and nearly all Viterbi decoders operate using log-likelyhood ratios (metrics) to represent the probability and measure values needed within the decoder. But not all, and it is instructive to implement these decoders using measures instead of metrics. Sometimes, in application the best implementation uses measures.

The idea that turbo (or LDPC) decoders are welded at the hip to log domain representations is a narrow point of view .. IMO

S.

Please forgive me for cutting this short:

Tim: "do you use CORDIC?"

Rick: "No"

Tim: "thank you"

If you want more information about how it's used, please don't ask me -- I'm asking YOU!!

I've used a CORDIC to compute the magnitude of a complex signal.

I found it easier than calculating the square root.

Rob.

Tim, that is a very strange reply. It has been a long time since I've looked at the CORDIC and I couldn't remember the details of the math involved. I didn't say *anything* about how it is used.

Your questions were:

"how commonly is CORDIC used?"

"Is it still a necessary go-to for anyone contemplating doing DSP in an FPGA, or is it starting to ease onto the off-ramp of history?"

Nowhere did you ask how it is used...

Rob Gaddi wrote, "I've considered it many times, but never used it." and you didn't feel the need to criticize him.

You made a statement that I don't think can be supported. When I asked about that you give me a hard time...

Did you get up on the wrong side of bed or something?