How to calculate logarithm of a signal in FPGA?
in [DSP]
|
From: rickman on 2 Feb 2010 00:16 On Feb 1, 5:11 pm, Clay <c...(a)claysturner.com> wrote: > On Feb 1, 10:23 am, "abhijitk" <mailabh...(a)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
From: Clay on 2 Feb 2010 11:05 On Feb 2, 12:16 am, rickman <gnu...(a)gmail.com> wrote: > On Feb 1, 5:11 pm, Clay <c...(a)claysturner.com> wrote: > > > > > > > On Feb 1, 10:23 am, "abhijitk" <mailabh...(a)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; }
From: Manny on 2 Feb 2010 12:06 On Feb 2, 4:05 pm, Clay <c...(a)claysturner.com> wrote: > On Feb 2, 12:16 am, rickman <gnu...(a)gmail.com> wrote: > > > > > On Feb 1, 5:11 pm, Clay <c...(a)claysturner.com> wrote: > > > > On Feb 1, 10:23 am, "abhijitk" <mailabh...(a)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 :).
From: Greg Berchin on 2 Feb 2010 12:44 On Mon, 1 Feb 2010 14:11:04 -0800 (PST), Clay <clay(a)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
From: Clay on 2 Feb 2010 12:44 On Feb 2, 12:06 pm, Manny <mlou...(a)hotmail.com> wrote: > On Feb 2, 4:05 pm, Clay <c...(a)claysturner.com> wrote: > > > > > > > On Feb 2, 12:16 am, rickman <gnu...(a)gmail.com> wrote: > > > > On Feb 1, 5:11 pm, Clay <c...(a)claysturner.com> wrote: > > > > > On Feb 1, 10:23 am, "abhijitk" <mailabh...(a)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
First
|
Prev
|
Next
|
Last
Pages: 1 2 3 4 5 Prev: Kaiser window vs Kaiser-Bessel window Next: G726 codec support with .wav files |