Path: csiph.com!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: rickman Newsgroups: comp.lang.forth Subject: Re: embedded forth Date: Sun, 12 Feb 2017 19:37:12 -0500 Organization: A noiseless patient Spider Lines: 88 Message-ID: References: <49b3566a-3842-4f9f-a47f-a66590625fef@googlegroups.com> <92d07db1-18b7-410e-a77c-d7ab4f6606d8@googlegroups.com> <87lgtu20wb.fsf@nightsong.com> <6415800d-9ed0-4eef-afcf-6291de9a1ef3@googlegroups.com> <78a6cb97-3479-42ea-ade2-03c22b4d69d4@googlegroups.com> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Mon, 13 Feb 2017 00:35:27 -0000 (UTC) Injection-Info: mx02.eternal-september.org; posting-host="aa8b9ac927b6be8ad54db2c77eabed3e"; logging-data="25344"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+0+3xbTJ7oL5WvKgazTn6F" User-Agent: Mozilla/5.0 (Windows NT 6.2; WOW64; rv:45.0) Gecko/20100101 Thunderbird/45.7.1 In-Reply-To: <78a6cb97-3479-42ea-ade2-03c22b4d69d4@googlegroups.com> Cancel-Lock: sha1:zJxLII6CbFynbTVU0ldwX5P5zzI= Xref: csiph.com comp.lang.forth:54820 On 2/12/2017 1:21 PM, Ilya Tarasov wrote: >> I did a little digging and found why there seemed to be something >> about CORDIC that didn't quite sit. The algorithm for CORDIC >> iterates calculations on the sine and cosine of an angle by >> rotating the vector, adding and subtracting from the angle until >> the angle is zero... or approximately zero. The way the math >> works, the sine and cosine will always be *exact*, that is true. >> But it will just be for the wrong angle! > > I don't think 'wrong' is applicable here. Every kind of iterative > approaching algorithms has a built-in error, which decreased by every > iteration. The real power of iterarive approach is an ability to > decrease this error. The point is that the answer is not an exact answer to the question because while the calculation of the answer *is* exact, it is answering the wrong question even if only by a small amount. So in the end the CORDIC is no more exact than other methods and is ill suited in most cases because of the large resource usage. >> Yep, the angle is adjusted by adding and subtracting table values >> until it is close to zero. But each table value has a built in >> error of up to ±0.5 lsbs. For a 32 bit value there will be at >> least 32 iterations which means the errors can combine to as much >> as ±16 counts in the lsb of the phase angle. This is on top of the >> potential ±1 lsb due to the angle not resolving fully. This has a >> quirk where in the next to last iteration the angle can have >> resolved perfectly and the final step throws it off by 1. >> >> Of course the rounding errors are likely uncorrelated so the >> typical error will be 0.5*sqrt(32) or around 2.8 plus the >> resolution error. The analysis I've done with the trig approach >> indicates maximum errors in the range of ±1.5 lsbs and a lower >> typical and average. >> >> Is this wrong? > > This number looks real anough. Of course, performing math operations > with numbers with errors will lead to error propagation, and more > iterations means more error. Every approach has its own range of > optimal characteristics by time, area, memory size etc. If you reach > 1.5 LSBS tolerance, but need more, you can add two iterations and > that 1.5 LSBS will related to 34 bits, not 32. Of course, any method can be done in extended precision and the result rounded. >> BTW, the small b "approximation" is not a source of significant >> error. This simply determines where you divide the angle into the >> (a) bits and (b) bits. Choose (a) to be large enough and cos(b) is >> as close to 1 as you like. > > In average, approaches sequence usually looks like 'tables -> > approximation/series -> iterations'. Table size typically growing by > 2^N law (with some tricks maybe), approximation typically has a kind > of saturation (can you provide 64 bits?). I don't need 64 bits . I still haven't heard the use case for 32 bits. Why do you need 32 bits of accuracy? BTW, a 32 bit address lookup table is not really a bit issue. That is just 4 giga-entries. Or it can be broken down to a pair of tables using the same trig algorithm but this time with a full two multiplies as the cos(b)=b identity won't be true. Still, that's a total of three multiplies which is the same complexity as the CORDIC. The difference is it doesn't implement it all using FPGA fabric. Don't think that CORDIC doesn't have issues with word size. It is order N^2 complexity. So a 64 bit calculation would be rather huge in an FPGA using some 14,000 LUTs if I recall your earlier numbers correctly. That's actually more than four times larger than the FPGA I am generating sines from to do testing on interface boards. > More important another question you still didn't answer. For 32-bit > angle and 32-bit datawidth, what is more important to keep at their > level? Here we have time and (typically) voltage from ADC - that > value has better precision? Sorry, I don't understand the question. "Their level" and "that value has better precision" don't make sense to me. Who is "they" and what is "that"? -- Rick C