CORDIC in a land of built-in multipliers

[rickman]

On 10/14/2016 1:37 PM, Tim Wescott wrote:

On Thu, 13 Oct 2016 21:33:49 -0400, rickman wrote:

On 10/13/2016 6:16 PM, Tim Wescott wrote:
On Thu, 13 Oct 2016 18:14:58 -0400, rickman wrote:

On 10/13/2016 5:10 PM, Tim Wescott wrote:
On Thu, 13 Oct 2016 20:59:49 +0000, Rob Gaddi wrote:

Tim Wescott wrote:

On Thu, 13 Oct 2016 13:46:18 -0500, Tim Wescott wrote:

Now that FPGAs have built-in DSP blocks, 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?

And, putting FPGA use aside -- how common is it is ASICs?

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.

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!!

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?

--

Rick C

 

[Steve Pope]

Tim Wescott <tim@seemywebsite.really> wrote:

On Fri, 14 Oct 2016 14:40:02 +0000, Steve Pope wrote:

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.

Are the ASICs you're using based on LUTs, or are they a sea-of-gates
where you define the interconnect?

Interesting question.

In the early era (80's through early 90's) if a LUT was needed in an ASIC
it was a layout-based disign consisting of a mask-programmed ROM.

Certain other logic functions (notably, ALU's and parallel multipliers)
would also be layout-based). More random logic would be based on
routing together standard cells.

(At the time, a "gate array" or "sea of gates" approach suggested the
cells were very small, on the order of a gate or two as opposed to cells
for D-flops, adder sections, etc.; and typically that only a few
metal layers were customized.)

In the modern era, lookup tables are usually synthesized from gate
logic along with the rest of the random logic and physically, the
only large blocks in the digital part of the design are RAM's.
Of course the converters and other analog blocks are separate blocks.

The exception is large CPU chips where the ALU's, memory switches,
and so forth are still layout-based designs.

If one has a photomicrograph of a chip you can usually see what
they are doing and how they've paritioned it.

Steve

 

[Tim Wescott]

On Fri, 14 Oct 2016 14:40:02 +0000, Steve Pope wrote:

Cecil Bayona <cbayona@cbayona.com> wrote:

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.

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

Are the ASICs you're using based on LUTs, or are they a sea-of-gates
where you define the interconnect?

--
www.wescottdesign.com

 

[Allan Herriman]

On Thu, 13 Oct 2016 13:46:18 -0500, Tim Wescott wrote:

Now that FPGAs have built-in DSP blocks, 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?

And, putting FPGA use aside -- how common is it is ASICs?

Ray Andraka used to be a frequent comp.arch.fpga poster. On his website
he lists several FPGA projects that use CORDIC, however I notice that
these all seem to have older dates, e.g. from the Xilinx Virtex-E era.

http://www.andraka.com/cordic.php

Allan

 

[rickman]

On 10/15/2016 3:35 AM, Allan Herriman wrote:

On Thu, 13 Oct 2016 13:46:18 -0500, Tim Wescott wrote:

Now that FPGAs have built-in DSP blocks, 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?

And, putting FPGA use aside -- how common is it is ASICs?

Ray Andraka used to be a frequent comp.arch.fpga poster. On his website
he lists several FPGA projects that use CORDIC, however I notice that
these all seem to have older dates, e.g. from the Xilinx Virtex-E era.

http://www.andraka.com/cordic.php

He was very old school having developed libraries of hierarchical
schematics for all manner of complex functions with full specification
of placement of each logic function. So he was not happy with the idea
of changing over to HDL which Xilinx told him would be the only entry
means supported eventually. Once he gave it a serious try and
discovered he could do the exact same thing with structural code, he was
happily convinced HDL was the way to go. I expect he has a full HDL
library of CORDIC functions.

--

Rick C

 

[Evgeny Filatov]

On 14.10.2016 19:27, Steve Pope wrote:

Evgeny Filatov <filatov.ev@mipt.ru> wrote:

On 14/10/2016 06:35, Rafael Deliano wrote:

But who knows after all these years what it is and
how to implement it ?
Same for Logarithmic Number Systems ( LNS ).

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

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.

Alright. By the way, Steve, do you follow polar codes? Looks like they
have comparable performance to LDPC now:

http://sci-hub.cc/10.1109/JSAC.2015.2504299

Gene

 

On Thursday, October 13, 2016 at 10:51:13 PM UTC-5, Cecil Bayona wrote:

On 10/13/2016 8:33 PM, rickman wrote:
On 10/13/2016 6:16 PM, Tim Wescott wrote:
On Thu, 13 Oct 2016 18:14:58 -0400, rickman wrote:

On 10/13/2016 5:10 PM, Tim Wescott wrote:
On Thu, 13 Oct 2016 20:59:49 +0000, Rob Gaddi wrote:

Tim Wescott wrote:

On Thu, 13 Oct 2016 13:46:18 -0500, Tim Wescott wrote:

Now that FPGAs have built-in DSP blocks, 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?

And, putting FPGA use aside -- how common is it is ASICs?

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.

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.

--
Cecil - k5nwa

]> Cordic is used for items like sine, cosine, tangent, square root,etc

Used it for pixel-rate polar to rectangular (needed both angle & radius).
Vendor's CORDIC IP worked fine. It used a ~12 stage pipeline.

 

[Kevin Neilson]

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.

--
Rob Gaddi, Highland Technology -- www.highlandtechnology.com

Same here. CORDIC is something that is cool, but does not seem useful any longer. It takes too many cycles and is only useful if you don't care about throughput, but in those applications, you are probably using a processor, not an FPGA. You keep the latency but increase throughput by pipelining, but then it's bigger than an alternative solution. If you can, you use a blockRAM lookup table for trig functions. Otherwise you'd probably use embedded multipliers and a Taylor series (with Horner's Rule). Or a hybrid, such as a Farrow function, which can be as simple as interpolating between lookup elements. The Farrow idea works really well in sine lookups since the derivative of sine is a shifted sine, so you can use the same lookup table. That's what I've used.

For arctan(y/x), which is needed in phase recovery, I've used 2-dimensional lookup tables, where the input is a concatenated {x,y}. You don't need a lot of precision. There are also good approximations for things like sqrt(x^2+y^2).

A lot of ideas persist for a long time in textbooks and practice when they are no longer useful. I do error correction now and all the textbooks still show, for example, how to build a Reed-Solomon encoder that does 1 symbol per cycle. If I wanted to do something that slowly, I'd probably do it in software. Sure a lot easier. FPGAs are only useful if you are doing things really fast.

 

[Kevin Neilson]

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

I found it easier than calculating the square root.

Rob.

True, but there are probably simpler ways. You can use a 2D lookup in a blockRAM. And an approximation that can be reasonably precise is

mag = A*max(I,Q) + B*min(I,Q)

where A,B are constants. (You can find suggestions for these on the web.)