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 in a land of built-in multipliers
Started by ●October 13, 2016
Reply by ●October 14, 20162016-10-14
Reply by ●October 14, 20162016-10-14
On 10/13/2016 11:51 PM, 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.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. -- Rick C
Reply by ●October 14, 20162016-10-14
On Friday, October 14, 2016 at 4:37:39 AM UTC+3, rickman wrote:> On 10/13/2016 9: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. > > 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 > seriesIf you properly chose your ranges then power series will converge many times faster than CORDIC. For example, you want sin(x) for x in range [0..pi/2]. You don't apply power 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. Then, 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-entry 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.> and requires no multiplications. Do I have it now? Using fewer > gates is a bit of an understatement. > > -- > > Rick C
Reply by ●October 14, 20162016-10-14
On Friday, October 14, 2016 at 6:35:12 AM UTC+3, Rafael Deliano wrote:> > 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, > > It was used in (HP-)pocket calculators then and got well known > that way. > Later on floating point coprocessors. 8087,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.> 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.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.> > 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
Reply by ●October 14, 20162016-10-14
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
Reply by ●October 14, 20162016-10-14
On 14/10/2016 06:35, Rafael Deliano wrote: (snip)> 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. Evgeny
Reply by ●October 14, 20162016-10-14
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.
Reply by ●October 14, 20162016-10-14
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 Wescott Wescott Design Services http://www.wescottdesign.com I'm looking for work -- see my website!
Reply by ●October 14, 20162016-10-14
On 10/14/2016 7:40 AM, 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 >I've used a CORDIC to compute the magnitude of a complex signal. I found it easier than calculating the square root. Rob.
Reply by ●October 14, 20162016-10-14
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
