Just read the principles of CORDIC. A few basic questions: 1) Don't all processors nowadays have multiplication ability? So unless implementation in FPGA to save gates or chip area it's useless? 2) The actual iteration of the algo still requires multiplication. Specifically, the following equations still require the multiplication of (2^-L) with either the in phase or quadrature component. Doesn't this defeat the purpose of the algo? Ic' = Ic - K�Qc = Ic - (2^-L)�Qc Qc' = Qc + K�Ic = Qc + (2^-L)�Ic Regards, Peter
CORDIC
Started by ●June 8, 2004
Reply by ●June 8, 20042004-06-08
1) Yes, processors have multiplies, but they don't all have sine, for example! You're correct that CORDIC sees a lot of use in FPGAs. 2) Multiplying by a power of two can be done by a simple binary shift. Easy in hardware. You should've paid attention in those logic lectures! ;-) Cheers, Syms. "Peter Choi" <choi@mecca.ca> wrote in message news:f7808324.0406080934.65d79bef@posting.google.com...> Just read the principles of CORDIC. A few basic questions: > 1) Don't all processors nowadays have multiplication ability? So > unless implementation in FPGA to save gates or chip area it's useless? > 2) The actual iteration of the algo still requires multiplication. > Specifically, the following equations still require the multiplication > of (2^-L) with either the in phase or quadrature component. Doesn't > this defeat the purpose of the algo? > Ic' = Ic - K�Qc = Ic - (2^-L)�Qc > Qc' = Qc + K�Ic = Qc + (2^-L)�Ic
Reply by ●June 8, 20042004-06-08
Peter Choi wrote:> Just read the principles of CORDIC. A few basic questions: > 1) Don't all processors nowadays have multiplication ability? So > unless implementation in FPGA to save gates or chip area it's useless?For implementation on general purpose CPU's polynomial approximations are usually used.> 2) The actual iteration of the algo still requires multiplication. > Specifically, the following equations still require the multiplication > of (2^-L) with either the in phase or quadrature component. Doesn't > this defeat the purpose of the algo? > Ic' = Ic - K�Qc = Ic - (2^-L)�Qc > Qc' = Qc + K�Ic = Qc + (2^-L)�IcFor binary CORDIC, as well as I remember only one multiply is needed after (or before) the CORDIC loop. I am not so sure about decimal CORDIC, as implemented in most hand calculators. (All calculators that I know of do BCD arithmetic, and CORDIC can be done that way, also.) See: http://www.andraka.com/cordic.htm -- glen
Reply by ●June 8, 20042004-06-08
CORDIC is not typically used for microprocessors, rather it is a hardware implementation that eliminates multiplications as well as large trig tables. For microprocessors, it generally makes more sense to use one of the polynomial approximations. For hardware, the multiplications that remain in the algorithm are multiplies by powers of 2, which is accomplished with a simple shift. In the unrolled version, the shifts are just wires. You might take a look at my CORDIC paper available at no cost from my website (http://www.andraka.com) Peter Choi wrote:> Just read the principles of CORDIC. A few basic questions: > 1) Don't all processors nowadays have multiplication ability? So > unless implementation in FPGA to save gates or chip area it's useless? > 2) The actual iteration of the algo still requires multiplication. > Specifically, the following equations still require the multiplication > of (2^-L) with either the in phase or quadrature component. Doesn't > this defeat the purpose of the algo? > Ic' = Ic - K�Qc = Ic - (2^-L)�Qc > Qc' = Qc + K�Ic = Qc + (2^-L)�Ic > > Regards, > Peter-- --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
Reply by ●June 26, 20042004-06-26
In article <40C60AA3.52B5499E@andraka.com>, Ray Andraka <ray@andraka.com> wrote:> CORDIC is not typically used for microprocessors, rather it is a hardware > implementation that eliminates multiplications as well as large trig > tables. For microprocessors, it generally makes more sense to use one of > the polynomial approximations.It all depends on the microprocessor you are using. On many of the microprocessor used for hand-held devices (e.g. Palm), there is no floating-point, so polynomials are problematic. I recently wrote some graphics code for one of these devices, and CORDIC was the obvious choice for trigonometry. The most basic form of CORDIC is most useful for - generating sine and cosine simultaneously - polar to rectangular conversion - arctangent (arctan2, to be exact) - vector magnitude - rectangular to polar conversion I have a clear description of the use of CORDIC for the circular trigonometric functions, as well as source code, at: http://www.worldserver.com/turk/computergraphics/papers.html
Reply by ●June 26, 20042004-06-26
Ken Turkowski wrote:> In article <40C60AA3.52B5499E@andraka.com>, > Ray Andraka <ray@andraka.com> wrote: > > >>CORDIC is not typically used for microprocessors, rather it is a hardware >>implementation that eliminates multiplications as well as large trig >>tables. For microprocessors, it generally makes more sense to use one of >>the polynomial approximations. > > > It all depends on the microprocessor you are using. On many of the > microprocessor used for hand-held devices (e.g. Palm), there is no > floating-point, so polynomials are problematic. > > I recently wrote some graphics code for one of these devices, and CORDIC > was the obvious choice for trigonometry. > > The most basic form of CORDIC is most useful for > - generating sine and cosine simultaneously > - polar to rectangular conversion > - arctangent (arctan2, to be exact) > - vector magnitude > - rectangular to polar conversion > > I have a clear description of the use of CORDIC for the circular > trigonometric functions, as well as source code, at: > > http://www.worldserver.com/turk/computergraphics/papers.htmlThe hp 35 (and probably also 45) calculators do floating-point arithmetic and use CORDIC to do trig. Instead of using a fixed number of iterations and a constant scale correction, they compute sine and cosine simultaneously, divide to get tangent, and use trig identities to convert that to the required function. The designers must have had good reason to be so indirect. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●July 10, 20042004-07-10
Jerry Avins wrote: (snip of CORDIC question)> The hp 35 (and probably also 45) calculators do floating-point > arithmetic and use CORDIC to do trig. Instead of using a fixed number of > iterations and a constant scale correction, they compute sine and cosine > simultaneously, divide to get tangent, and use trig identities to > convert that to the required function. The designers must have had good > reason to be so indirect.Well, they don't have floating point hardware in the sense that it is meant today. Nothing so complicated as the Intel 8087 chip in those calculators. When floating point is done in software it makes a big enough difference. Though if you consider machines such as the 360/30, with an 8 bit ALU and microprograms to do floating point. It uses polynomials like other real computers. -- glen
Reply by ●July 16, 20042004-07-16
It doesn't make much sense to do CORDIC with floating point. CORDIC is an add-shift algorithm, which means the values have to be denormalized at each iteration in order to perform the add. Doing it with floating point just gets you truncation problems and a whole lot of shifting for no reason. If you have floating point, normalize the IQ pair at the input so that the larger of the pair has no repeated sign bits, then do a fixed point CORDIC on just the mantissas. Pass the exponent around the cordic, then at the completion you can apply the exponent and renormalize. If you think about what CORDIC is doing, it is simply a phase angle rotator. In rotation mode, it rotates the input vector by the designated angle. In vector mode, it rotates the input vector to the I axis recording the angle traversed. The scale of the individual I and Q components may change, but if one gets smaller, the other gets bigger. The magnitude of the vector is not changed (well, not exactly: it is multiplied by the cordic scale constant=~1.65). Since each iteration of the CORDIC adds the I and Q components (once with the I right shifted, once with Q right shifted each by the number of bits equal to the iteration), and since addition requires both addends to have the same exponent, floating point essentially gets converted to a fixed point before each iteration. Many of the early scientific calculators used CORDIC for the 'scientific' functions. Part of this was because most of those calculators also used bit serial arithmetic and iterated in order to keep the hardware complexity to an absolute minimum. Remember, at the time integrated circuits were still pretty new, and typically had complexities of under 1000 gates. With that small gate count, you don't have the luxury of large look-up tables or lots of logic dedicated to a single purpose. glen herrmannsfeldt wrote:> Jerry Avins wrote: > > (snip of CORDIC question) > > > The hp 35 (and probably also 45) calculators do floating-point > > arithmetic and use CORDIC to do trig. Instead of using a fixed number of > > iterations and a constant scale correction, they compute sine and cosine > > simultaneously, divide to get tangent, and use trig identities to > > convert that to the required function. The designers must have had good > > reason to be so indirect. > > Well, they don't have floating point hardware in the sense > that it is meant today. Nothing so complicated as the > Intel 8087 chip in those calculators. > > When floating point is done in software it makes a big > enough difference. > > Though if you consider machines such as the 360/30, with an > 8 bit ALU and microprograms to do floating point. > It uses polynomials like other real computers. > > -- glen-- --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
Reply by ●July 17, 20042004-07-17
Ray Andraka wrote: (snip)> Many of the early scientific calculators used CORDIC for the 'scientific' > functions. Part of this was because most of those calculators also used bit > serial arithmetic and iterated in order to keep the hardware complexity to an > absolute minimum. Remember, at the time integrated circuits were still pretty > new, and typically had complexities of under 1000 gates. With that small gate > count, you don't have the luxury of large look-up tables or lots of logic > dedicated to a single purpose.As far as I know, the early, as well as more current, scientific calculators use decimal digit serial arithmetic. Also, I believe that there are ways to do decimal CORDIC, though I don't completely understand them yet. A polynomial approximation in floating point on the 360/30 is probably about as fast as CORDIC on a scientific calculator. -- glen
Reply by ●July 18, 20042004-07-18
glen herrmannsfeldt wrote:> Also, I believe that there are ways to do decimal CORDIC, though I > don't completely understand them yet.Could you not simply replace your binary shifts with decimal adds, and make any adjustments necessary to avoid right shifts? Or are you talking about a technique of decimating the problem in each iteration rather than halving it?
