Hello everyone.. How to calculate Logarithm of a signal in FPGA? Is there any hardware efficient method for it? Can CORDIC core be used to calculate log function? Regards Abhijit
How to calculate logarithm of a signal in FPGA?
Started by ●February 1, 2010
Reply by ●February 1, 20102010-02-01
"abhijitk" <mailabhi.k@gmail.com> writes:> Hello everyone.. > > How to calculate Logarithm of a signal in FPGA? Is there any hardware > efficient method for it? Can CORDIC core be used to calculate log > function? > > Regards > AbhijitThe most hardware efficient method is a diode and an op amp! It's somewhat ironic that you could spend $50 worth of FPGA gates (and possibly nontrivial amounts of engineering effort) simulating this :-) But seriously, it's all about the input and output data formats, and the required precision. Is it fixed-point? How many bits? Could you use somthing as simple as a leading ones detector, a lookup table and interpolation? - Kenn
Reply by ●February 1, 20102010-02-01
On Feb 1, 9:34�am, Kenn Heinrich <kwhei...@uwaterloo.ca> wrote:> "abhijitk" <mailabh...@gmail.com> writes: > > How to calculate Logarithm of a signal in FPGA? > > Could you use > something as simple as a leading ones detector, a lookup table and > interpolation?I've done that - worked reasonably well (a few % error), didn't use up a whole slew of gates. Eric
Reply by ●February 1, 20102010-02-01
abhijitk wrote:> Hello everyone.. > > How to calculate Logarithm of a signal in FPGA? Is there any hardware > efficient method for it? Can CORDIC core be used to calculate log > function?Here is very efficient method: ln(x) ~ x - 1 How about that? VLV
Reply by ●February 1, 20102010-02-01
On Feb 1, 10:23�am, "abhijitk" <mailabh...@gmail.com> wrote:> Hello everyone.. > > How to calculate Logarithm of a signal in FPGA? Is there any hardware > efficient method for it? Can CORDIC core be used to calculate log > function? > > Regards > AbhijitA way that is pretty simple in binary (gives the log to base 2): 1) start with number x so that 2 > x >= 1 and init mantissa 0. 2) let x = x*x (square x) 3) if x>=2, then augment "1" and let x=x/2 else augment "0". The augmenting of the "1" or "0" is done to the right side of the manitssa. 4) go back to step 2. This will let you compute the radix 2 logarithm to an precise number of bits. IHTH, Clay p.s. if your original number is outside of the range [1,2) simply multiply/divide by two keeping count of the number of times and subtracting/adding the count from/to the resulting manitissa. Final result may be multiplied by a scaling factor to change radix of log.
Reply by ●February 2, 20102010-02-02
On Feb 1, 5:11�pm, Clay <c...@claysturner.com> wrote:> On Feb 1, 10:23�am, "abhijitk" <mailabh...@gmail.com> wrote: > > > Hello everyone.. > > > How to calculate Logarithm of a signal in FPGA? Is there any hardware > > efficient method for it? Can CORDIC core be used to calculate log > > function? > > > Regards > > Abhijit > > A way that is pretty simple in binary (gives the log to base 2): > > 1) start with number x so that � �2 > x >= 1 and init mantissa 0. > > 2) let x = x*x �(square x) > > 3) if x>=2, then augment "1" �and let x=x/2 else augment "0". The > augmenting of the "1" or "0" is done to the right side of the > manitssa. > > 4) go back to step 2. > > This will let you compute the radix 2 logarithm to an precise number > of bits. > > IHTH, > > Clay > > p.s. if your original number is outside of the range [1,2) simply > multiply/divide by two keeping count of the number of times and > subtracting/adding the count from/to the resulting manitissa. Final > result may be multiplied by a scaling factor to change radix of log.What does "augment 1" and "augment 0" mean??? Rick
Reply by ●February 2, 20102010-02-02
On Feb 2, 12:16�am, rickman <gnu...@gmail.com> wrote:> On Feb 1, 5:11�pm, Clay <c...@claysturner.com> wrote: > > > > > > > On Feb 1, 10:23�am, "abhijitk" <mailabh...@gmail.com> wrote: > > > > Hello everyone.. > > > > How to calculate Logarithm of a signal in FPGA? Is there any hardware > > > efficient method for it? Can CORDIC core be used to calculate log > > > function? > > > > Regards > > > Abhijit > > > A way that is pretty simple in binary (gives the log to base 2): > > > 1) start with number x so that � �2 > x >= 1 and init mantissa 0. > > > 2) let x = x*x �(square x) > > > 3) if x>=2, then augment "1" �and let x=x/2 else augment "0". The > > augmenting of the "1" or "0" is done to the right side of the > > manitssa. > > > 4) go back to step 2. > > > This will let you compute the radix 2 logarithm to an precise number > > of bits. > > > IHTH, > > > Clay > > > p.s. if your original number is outside of the range [1,2) simply > > multiply/divide by two keeping count of the number of times and > > subtracting/adding the count from/to the resulting manitissa. Final > > result may be multiplied by a scaling factor to change radix of log. > > What does "augment 1" and "augment 0" mean??? > > Rick- Hide quoted text - > > - Show quoted text -Rick, Sorry I didn't describe it very clearly. Maybe I should had said append instead of augment. The following "c" code shows a simple implementation of the algo. I do in this version use a mix of integer and floating point, but I think it will be clear that this can be all done in integer arithmetic very cleanly. Which when I needed this in assembler, is what I did. This version is really to just illustrate the algo. // Simple binary logarithm routine by Clay S. Turner // Calculates binary logarithm of x assuming 1<= x < 2 // Algo is designed to operate efficiently with binary integers although // this version also uses floating point for illustarting the algo. #define PRECISION 10 // # of bits the log will be calculated to double BinLog(double x) { int p=0,q=1,i; for (i=0;i<PRECISION;i++) { p<<=1; q<<=1; x=x*x; if (x>=2.0) { x/=2.0; p|=1; } } return (double)p / q; }
Reply by ●February 2, 20102010-02-02
On Feb 2, 4:05�pm, Clay <c...@claysturner.com> wrote:> On Feb 2, 12:16�am, rickman <gnu...@gmail.com> wrote: > > > > > On Feb 1, 5:11�pm, Clay <c...@claysturner.com> wrote: > > > > On Feb 1, 10:23�am, "abhijitk" <mailabh...@gmail.com> wrote: > > > > > Hello everyone.. > > > > > How to calculate Logarithm of a signal in FPGA? Is there any hardware > > > > efficient method for it? Can CORDIC core be used to calculate log > > > > function? > > > > > Regards > > > > Abhijit > > > > A way that is pretty simple in binary (gives the log to base 2): > > > > 1) start with number x so that � �2 > x >= 1 and init mantissa 0. > > > > 2) let x = x*x �(square x) > > > > 3) if x>=2, then augment "1" �and let x=x/2 else augment "0". The > > > augmenting of the "1" or "0" is done to the right side of the > > > manitssa. > > > > 4) go back to step 2. > > > > This will let you compute the radix 2 logarithm to an precise number > > > of bits. > > > > IHTH, > > > > Clay > > > > p.s. if your original number is outside of the range [1,2) simply > > > multiply/divide by two keeping count of the number of times and > > > subtracting/adding the count from/to the resulting manitissa. Final > > > result may be multiplied by a scaling factor to change radix of log. > > > What does "augment 1" and "augment 0" mean??? > > > Rick- Hide quoted text - > > > - Show quoted text - > > Rick, > > Sorry I didn't describe it very clearly. Maybe I should had said > append instead of augment. The following "c" code shows a simple > implementation of the algo. I do in this version use a mix of integer > and floating point, but I think it will be clear that this can be all > done in integer arithmetic very cleanly. Which when I needed this in > assembler, is what I did. This version is really to just illustrate > the algo. > > // Simple binary logarithm routine by Clay S. Turner > > // Calculates binary logarithm of x assuming 1<= x < 2 > // Algo is designed to operate efficiently with binary integers > although > // this version also uses floating point for illustarting the algo. > > #define PRECISION 10 � �// # of bits the log will be calculated to > > double BinLog(double x) > { > int p=0,q=1,i; > > for (i=0;i<PRECISION;i++) { > � � � � p<<=1; > � � � � q<<=1; > � � � � x=x*x; > � � � � if (x>=2.0) { > � � � � � � � � x/=2.0; > � � � � � � � � p|=1; > � � � � � � � � } > � � � � } > return (double)p / q; > > }Neat! All is left now for you to do is instantiate a constant fractional multiplier (left justify) to move to base e. You may need to do an addition first. Homework done :).
Reply by ●February 2, 20102010-02-02
On Feb 2, 12:06�pm, Manny <mlou...@hotmail.com> wrote:> On Feb 2, 4:05�pm, Clay <c...@claysturner.com> wrote: > > > > > > > On Feb 2, 12:16�am, rickman <gnu...@gmail.com> wrote: > > > > On Feb 1, 5:11�pm, Clay <c...@claysturner.com> wrote: > > > > > On Feb 1, 10:23�am, "abhijitk" <mailabh...@gmail.com> wrote: > > > > > > Hello everyone.. > > > > > > How to calculate Logarithm of a signal in FPGA? Is there any hardware > > > > > efficient method for it? Can CORDIC core be used to calculate log > > > > > function? > > > > > > Regards > > > > > Abhijit > > > > > A way that is pretty simple in binary (gives the log to base 2): > > > > > 1) start with number x so that � �2 > x >= 1 and init mantissa 0. > > > > > 2) let x = x*x �(square x) > > > > > 3) if x>=2, then augment "1" �and let x=x/2 else augment "0". The > > > > augmenting of the "1" or "0" is done to the right side of the > > > > manitssa. > > > > > 4) go back to step 2. > > > > > This will let you compute the radix 2 logarithm to an precise number > > > > of bits. > > > > > IHTH, > > > > > Clay > > > > > p.s. if your original number is outside of the range [1,2) simply > > > > multiply/divide by two keeping count of the number of times and > > > > subtracting/adding the count from/to the resulting manitissa. Final > > > > result may be multiplied by a scaling factor to change radix of log. > > > > What does "augment 1" and "augment 0" mean??? > > > > Rick- Hide quoted text - > > > > - Show quoted text - > > > Rick, > > > Sorry I didn't describe it very clearly. Maybe I should had said > > append instead of augment. The following "c" code shows a simple > > implementation of the algo. I do in this version use a mix of integer > > and floating point, but I think it will be clear that this can be all > > done in integer arithmetic very cleanly. Which when I needed this in > > assembler, is what I did. This version is really to just illustrate > > the algo. > > > // Simple binary logarithm routine by Clay S. Turner > > > // Calculates binary logarithm of x assuming 1<= x < 2 > > // Algo is designed to operate efficiently with binary integers > > although > > // this version also uses floating point for illustarting the algo. > > > #define PRECISION 10 � �// # of bits the log will be calculated to > > > double BinLog(double x) > > { > > int p=0,q=1,i; > > > for (i=0;i<PRECISION;i++) { > > � � � � p<<=1; > > � � � � q<<=1; > > � � � � x=x*x; > > � � � � if (x>=2.0) { > > � � � � � � � � x/=2.0; > > � � � � � � � � p|=1; > > � � � � � � � � } > > � � � � } > > return (double)p / q; > > > } > > Neat! All is left now for you to do is instantiate a constant > fractional multiplier (left justify) to move to base e. You may need > to do an addition first. Homework done :).- Hide quoted text - > > - Show quoted text -I have always thought it was a pretty cool algo. I came up with it 35 years ago. I doubt I'm the 1st in the world to come up with this. My Dad gave me a paper on public key cryptography where the authors included an algo for exponentiation by repeated squaring and multiplying. It didn't take me too long to figure out how to calculate base 2 log(x) by a similar process except we now have repeated squaring and dividing. Doing it in base two makes that 2nd part trivial. If someone knows of a reference to logs by this method, I'd love to know it. Clay
Reply by ●February 2, 20102010-02-02
On Mon, 1 Feb 2010 14:11:04 -0800 (PST), Clay <clay@claysturner.com> wrote:>This will let you compute the radix 2 logarithm to an precise number >of bits.I have been using a similar, exact iterative algorithm for decades, except mine uses two lookup tables, each with as many entries as the required number bits of precision. Lookup tables aren't nearly as elegant as squaring-and-comparing, but the same tables can also be used to compute the inverse logarithm. I'm not sure, but I suspect that your square-and-compare method might turn into a square-root-and-compare for the inverse log. Greg
