Hi all, I have to convert 16 bit numbers to their scaled logaritm in base 2, basically 256*log2(). I am trying look-up-table approach. The constraint is that the error should be less then 0.01dB. Can anyone suggest how to construct a (smallest size) look-up-table and how to calculate the logarithm? Thanks, Sumeer.
Fixed point logarithm to base 2
Started by ●June 2, 2004
Reply by ●June 2, 20042004-06-02
Sumeer wrote:> Hi all, > > I have to convert 16 bit numbers to their scaled logaritm in base 2, > basically 256*log2(). I am trying look-up-table approach. The > constraint is that the error should be less then 0.01dB. Can anyone > suggest how to construct a (smallest size) look-up-table and how to > calculate the logarithm? > > Thanks, > Sumeer.I would suggest shifting the number to normalize it (unless it's already scaled between 0 and 1?), then doing an n-power interpolation. If you _really_ want to minimize the "table" then figure out what power you need and do a least-squares fit to a logarithm in your normalized range, i.e. find the coefficients such that y = sum(x^n * a_n) is a good enough fit. If you're writing assembly the ADSP 21xx is a _really_ good processor for this because you can fit the MAC _and_ the x^n inside of a hardware loop. A larger table could be had for less mathematically intensive coding if you just use linear interpolation -- but I'll leave it to you to find the right table size. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com
Reply by ●June 3, 20042004-06-03
See my quick and dirty log post in DSP guru.. Basically, normalize the input value. The number of shifts to normalize is the integer portion of the log2 of the input. The normalized value is the residue of the input (between 1 and 2), which can be used to address a table for the fractional part of the log. Use only then number of MSBs needed for the precision you want. 4 bits excluding the always '1' MSB gets you to about a half dB using only a 16 entry table. The log is the sum of the integer portion and the table value. Other log bases can be had by multiplying by 1/log2(base). Sumeer wrote:> Hi all, > > I have to convert 16 bit numbers to their scaled logaritm in base 2, > basically 256*log2(). I am trying look-up-table approach. The > constraint is that the error should be less then 0.01dB. Can anyone > suggest how to construct a (smallest size) look-up-table and how to > calculate the logarithm? > > Thanks, > Sumeer.-- --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 4, 20042004-06-04
Ray Andraka wrote:> See my quick and dirty log post in DSP guru.. Basically, normalize the > input value. The number of shifts to normalize is the integer portion > of the log2 of the input. The normalized value is the residue of the > input (between 1 and 2), which can be used to address a table for the > fractional part of the log. Use only then number of MSBs needed for the > precision you want. 4 bits excluding the always '1' MSB gets you to > about a half dB using only a 16 entry table. The log is the sum of the > integer portion and the table value. Other log bases can be had by > multiplying by 1/log2(base). > > Sumeer wrote: > > >>Hi all, >> >>I have to convert 16 bit numbers to their scaled logaritm in base 2, >>basically 256*log2(). I am trying look-up-table approach. The >>constraint is that the error should be less then 0.01dB. Can anyone >>suggest how to construct a (smallest size) look-up-table and how to >>calculate the logarithm? >> >>Thanks, >>Sumeer. > > > -- > --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 >My slide rule says that .01 dB is about 1 part in 870, so it looks as it 10 bits will meet the spec, but 9 might be good enough is the spec is a bit tighter than need be. Quadratic interpolation would allow a much smaller table. (See http://users.erols.com/jyavins/typek.htm for an example.) Some years ago, R.B-J. posted some coefficients for an efficient polynomial approximation. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●June 4, 20042004-06-04
Regarding "smallest size look-up-table", you can trade off table size for calculation complexity. At one extreme, you just use the closest point in your table directly. This is the simplest computationally but requires the largest table for a given accuracy. The next step is linear interpolation between table points. After that, more complex interpolation schemes can be used (e.g. quadratic as Jerry mentioned, cubic, or even higher order). At the other extreme is a complex calculation (e.g. high-order polynomial) that uses just a few points or doesn't need a table at all! For your particular application, I'm guessing the "sweet spot" will be linear interpolation. This is assuming you have already normalized the value to limit the range the table portion needs to work at to between 1 and 2 as Ray describes below. In the limited range of 1-2, the log function is quite smooth so some simple interpolation should go a long way. "Ray Andraka" <ray@andraka.com> wrote in message news:40BFCE95.38852D79@andraka.com...> See my quick and dirty log post in DSP guru.. Basically, normalize the > input value. The number of shifts to normalize is the integer portion > of the log2 of the input. The normalized value is the residue of the > input (between 1 and 2), which can be used to address a table for the > fractional part of the log. Use only then number of MSBs needed for the > precision you want. 4 bits excluding the always '1' MSB gets you to > about a half dB using only a 16 entry table. The log is the sum of the > integer portion and the table value. Other log bases can be had by > multiplying by 1/log2(base). > > Sumeer wrote: > > > Hi all, > > > > I have to convert 16 bit numbers to their scaled logaritm in base 2, > > basically 256*log2(). I am trying look-up-table approach. The > > constraint is that the error should be less then 0.01dB. Can anyone > > suggest how to construct a (smallest size) look-up-table and how to > > calculate the logarithm? > > > > Thanks, > > Sumeer. > > -- > --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 4, 20042004-06-04
Jon Harris wrote:> Regarding "smallest size look-up-table", you can trade off table size for > calculation complexity. At one extreme, you just use the closest point in your > table directly. This is the simplest computationally but requires the largest > table for a given accuracy. The next step is linear interpolation between table > points. After that, more complex interpolation schemes can be used (e.g. > quadratic as Jerry mentioned, cubic, or even higher order). At the other > extreme is a complex calculation (e.g. high-order polynomial) that uses just a > few points or doesn't need a table at all! > > For your particular application, I'm guessing the "sweet spot" will be linear > interpolation. This is assuming you have already normalized the value to limit > the range the table portion needs to work at to between 1 and 2 as Ray describes > below. In the limited range of 1-2, the log function is quite smooth so some > simple interpolation should go a long way. > > "Ray Andraka" <ray@andraka.com> wrote in message > news:40BFCE95.38852D79@andraka.com... > >>See my quick and dirty log post in DSP guru.. Basically, normalize the >>input value. The number of shifts to normalize is the integer portion >>of the log2 of the input. The normalized value is the residue of the >>input (between 1 and 2), which can be used to address a table for the >>fractional part of the log. Use only then number of MSBs needed for the >>precision you want. 4 bits excluding the always '1' MSB gets you to >>about a half dB using only a 16 entry table. The log is the sum of the >>integer portion and the table value. Other log bases can be had by >>multiplying by 1/log2(base). >> >>Sumeer wrote: >> >> >>>Hi all, >>> >>>I have to convert 16 bit numbers to their scaled logaritm in base 2, >>>basically 256*log2(). I am trying look-up-table approach. The >>>constraint is that the error should be less then 0.01dB. Can anyone >>>suggest how to construct a (smallest size) look-up-table and how to >>>calculate the logarithm? >>> >>>Thanks, >>>Sumeer. >> >>-- >>--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 >>Direct calculation may be worth looking at. A quadratic to approximate log2(1+x) is (1-a)*x -a*x^2. It is exact at the end points and the error doesn't exceed .01 for values of a between .335 and .359. The largest error is .00764 when n is .3465. Exactness at the end points ensures continuity when the integer portion of the log changes. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●June 4, 20042004-06-04
Jerry Avins wrote:> Jon Harris wrote: > >> Regarding "smallest size look-up-table", you can trade off table size for >> calculation complexity. At one extreme, you just use the closest >> point in your >> table directly. This is the simplest computationally but requires the >> largest >> table for a given accuracy. The next step is linear interpolation >> between table >> points. After that, more complex interpolation schemes can be used (e.g. >> quadratic as Jerry mentioned, cubic, or even higher order). At the other >> extreme is a complex calculation (e.g. high-order polynomial) that >> uses just a >> few points or doesn't need a table at all! >> >> For your particular application, I'm guessing the "sweet spot" will be >> linear >> interpolation. This is assuming you have already normalized the value >> to limit >> the range the table portion needs to work at to between 1 and 2 as Ray >> describes >> below. In the limited range of 1-2, the log function is quite smooth >> so some >> simple interpolation should go a long way. >> >> "Ray Andraka" <ray@andraka.com> wrote in message >> news:40BFCE95.38852D79@andraka.com... >> >>> See my quick and dirty log post in DSP guru.. Basically, normalize the >>> input value. The number of shifts to normalize is the integer portion >>> of the log2 of the input. The normalized value is the residue of the >>> input (between 1 and 2), which can be used to address a table for the >>> fractional part of the log. Use only then number of MSBs needed for the >>> precision you want. 4 bits excluding the always '1' MSB gets you to >>> about a half dB using only a 16 entry table. The log is the sum of the >>> integer portion and the table value. Other log bases can be had by >>> multiplying by 1/log2(base). >>> >>> Sumeer wrote: >>> >>> >>>> Hi all, >>>> >>>> I have to convert 16 bit numbers to their scaled logaritm in base 2, >>>> basically 256*log2(). I am trying look-up-table approach. The >>>> constraint is that the error should be less then 0.01dB. Can anyone >>>> suggest how to construct a (smallest size) look-up-table and how to >>>> calculate the logarithm? >>>> >>>> Thanks, >>>> Sumeer. >>> >>> >>> -- >>> --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 >>> > > Direct calculation may be worth looking at. A quadratic to approximate > log2(1+x) is (1-a)*x -a*x^2. It is exact at the end points and the error > doesn't exceed .01 for values of a between .335 and .359. The largest > error is .00764 when n is .3465. Exactness at the end points ensures > continuity when the integer portion of the log changes. > > JerryAnd if you're coding in assembly a polynomial may be way faster than a table look-up -- I know that the ADSP-21xx series allows a taylors-series-like polynomial expansion for sin(x) that's just phenomenal. It works best if you _don't_ use a 'real' taylors series but rather calculate the least-squares fit of the coefficients to the ideal. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com
Reply by ●June 4, 20042004-06-04
Tim Wescott wrote:> Jerry Avins wrote: > >> Jon Harris wrote: >> >>> Regarding "smallest size look-up-table", you can trade off table size >>> for >>> calculation complexity. At one extreme, you just use the closest >>> point in your >>> table directly. This is the simplest computationally but requires >>> the largest >>> table for a given accuracy. The next step is linear interpolation >>> between table >>> points. After that, more complex interpolation schemes can be used >>> (e.g. >>> quadratic as Jerry mentioned, cubic, or even higher order). At the >>> other >>> extreme is a complex calculation (e.g. high-order polynomial) that >>> uses just a >>> few points or doesn't need a table at all! >>> >>> For your particular application, I'm guessing the "sweet spot" will >>> be linear >>> interpolation. This is assuming you have already normalized the >>> value to limit >>> the range the table portion needs to work at to between 1 and 2 as >>> Ray describes >>> below. In the limited range of 1-2, the log function is quite smooth >>> so some >>> simple interpolation should go a long way. >>> >>> "Ray Andraka" <ray@andraka.com> wrote in message >>> news:40BFCE95.38852D79@andraka.com... >>> >>>> See my quick and dirty log post in DSP guru.. Basically, normalize the >>>> input value. The number of shifts to normalize is the integer portion >>>> of the log2 of the input. The normalized value is the residue of the >>>> input (between 1 and 2), which can be used to address a table for the >>>> fractional part of the log. Use only then number of MSBs needed for >>>> the >>>> precision you want. 4 bits excluding the always '1' MSB gets you to >>>> about a half dB using only a 16 entry table. The log is the sum of the >>>> integer portion and the table value. Other log bases can be had by >>>> multiplying by 1/log2(base). >>>> >>>> Sumeer wrote: >>>> >>>> >>>>> Hi all, >>>>> >>>>> I have to convert 16 bit numbers to their scaled logaritm in base 2, >>>>> basically 256*log2(). I am trying look-up-table approach. The >>>>> constraint is that the error should be less then 0.01dB. Can anyone >>>>> suggest how to construct a (smallest size) look-up-table and how to >>>>> calculate the logarithm? >>>>> >>>>> Thanks, >>>>> Sumeer. >>>> >>>> >>>> >>>> -- >>>> --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 >>>> >> >> Direct calculation may be worth looking at. A quadratic to approximate >> log2(1+x) is (1-a)*x -a*x^2. It is exact at the end points and the error >> doesn't exceed .01 for values of a between .335 and .359. The largest >> error is .00764 when n is .3465. Exactness at the end points ensures >> continuity when the integer portion of the log changes. >> >> Jerry > > > And if you're coding in assembly a polynomial may be way faster than a > table look-up -- I know that the ADSP-21xx series allows a > taylors-series-like polynomial expansion for sin(x) that's just > phenomenal. It works best if you _don't_ use a 'real' taylors series > but rather calculate the least-squares fit of the coefficients to the > ideal. >OK, I couldn't resist. For 0.5 <= x < 1, log_2(x) can be approximated by summing x^n * a_n from n = 0 to 4, where a_n = -3.5072144 8.1146325 -8.443007 5.137437 -1.302050. In floating point the error stays less than 1.6e-4. Writing up the algorithm for a fixed point machine is left as an exercise for the reader. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com
