Searching \ for '[PIC]: Fast Log algorithm' in subject line. ()
Make payments with PayPal - it's fast, free and secure! Help us get a faster server
FAQ page: www.piclist.com/techref/microchip/devices.htm?key=pic
Search entire site for: 'Fast Log algorithm'.

Exact match. Not showing close matches.
PICList Thread
'[PIC]: Fast Log algorithm'
2004\09\06@061108 by hael Rigby-Jones

picon face
I need to implement an logarithm function on an 18F part that executes as
quickly as possible.  Essentialy I need to convert power in nW to dBm with
an resolution of 0.01dBm. i.e. 1E6nW (1mW) would return a value of 100
(1dBm).  Both input and output of the function are 24bit integers.

An interpolated table (like Scott Dattalos example) is the obvious choice,
but I wondered if there was an alternative?

Calculating the integer portion of a number in LOG base 2 is trival, it's
simply the bit position of the most singificant bit which is set.  Can this
be extended to the the lower bits to get more accuracy?  If so my equation
boild down to LOG2(nW) * 301.03 - 6000, obviously the constants will have to
be scaled to suit the fixed point output of the LOG2 function.

Thanks for any assistance with this.

Regards

Mike Rigby-Jones

=======================================================================
This e-mail is intended for the person it is addressed to only. The
information contained in it may be confidential and/or protected by
law. If you are not the intended recipient of this message, you must
not make any use of this information, or copy or show it to any
person. Please contact us immediately to tell us that you have
received this e-mail, and return the original to us. Any use,
forwarding, printing or copying of this message is strictly prohibited.
No part of this message can be considered a request for goods or
services.
=======================================================================
_______________________________________________
http://www.piclist.com
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

2004\09\06@114158 by Scott Dattalo

face
flavicon
face
On Mon, 6 Sep 2004, Michael Rigby-Jones wrote:

> I need to implement an logarithm function on an 18F part that executes as
> quickly as possible.  Essentialy I need to convert power in nW to dBm with
> an resolution of 0.01dBm. i.e. 1E6nW (1mW) would return a value of 100
> (1dBm).  Both input and output of the function are 24bit integers.

How quick is 'quickly as possible'? Also, I thought 1mW was 0 dBm.

If you only want to compute dbm to the nearest 0.01 units, do you really
need to work with 24 integers? If the input power is in nW, then 2^24 nW
is only 16.777 mW which is only 1.22 dBm. Powers below roughly 1.023
(10^0.01) mW cannot be resolved to finer than 0.01 dBm. So this means your
input power ranges from 1.02 to 16.777mW and must be resolve to 0.01 to
1.22 dBm.

I suspect either I'm misunderstanding you or there's a typo in your
description and that you really need a higher resolution than I state.
Increasing the lookup table and linear interpolation to 9 or 10 bits is
straight forward. However, beyond that you may wish to consider an all
iterative technique (see method 3(a).vii
http://www.dattalo.com/technical/theory/logs.html for example).

Scott
_______________________________________________
http://www.piclist.com
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

2004\09\06@123211 by hael Rigby-Jones

picon face


{Quote hidden}

Yep, you spotted the deliberate mistake ;)  I really need to do this in less
than 1000 cycles as I am fast running out of steam on the PIC.

{Quote hidden}

The 24bit integers are a given, can't change that as it's part of an
existing interface spec.  The regsiters do not represent the actual accuracy
and resolution requirements which are limited by the hardware.  In practice
I suspect we won't be getting much better than ~250nW resolution.

The 24bit register for dBm measurement is vast overkill I agree.  A typical
range would be something like +5 to -30 dBm, (+500 to -3000 in the register)
which easily fits into 12bits.  The choice of using a power of ten unit
(0.01dBm) instead of using a simple fixed point format is also somewhat odd.
I suspect the spec was written by someone with little experience in embedded
programming (the device receiving this data is also microcontroller based).

>
>I suspect either I'm misunderstanding you or there's a typo in your
>description and that you really need a higher resolution than I state.

Nope, just me not giving enough information!

>Increasing the lookup table and linear interpolation to 9 or
>10 bits is
>straight forward. However, beyond that you may wish to consider an all
>iterative technique (see method 3(a).vii
>http://www.dattalo.com/technical/theory/logs.html for example).


Thanks, I'll take a look.  I think the table approach should be OK, I have a
good chunk of program memory to play with (18F8620, 64kwords which is
currently about 55% used).

I asked because calculating INT(LOG2(x)) is just so darn simple, and I was
hoping there was a way of calculating the fractional bits as easily.

Regards

Mike

=======================================================================
This e-mail is intended for the person it is addressed to only. The
information contained in it may be confidential and/or protected by
law. If you are not the intended recipient of this message, you must
not make any use of this information, or copy or show it to any
person. Please contact us immediately to tell us that you have
received this e-mail, and return the original to us. Any use,
forwarding, printing or copying of this message is strictly prohibited.
No part of this message can be considered a request for goods or
services.
=======================================================================
_______________________________________________
http://www.piclist.com
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

2004\09\06@140115 by Spehro Pefhany

picon face
At 05:35 PM 9/6/2004 +0100, you wrote:

>Thanks, I'll take a look.  I think the table approach should be OK, I have a
>good chunk of program memory to play with (18F8620, 64kwords which is
>currently about 55% used).

You could also create a table in terms of the output variable and search
within
the table for the input, which would take 12 accesses. That's only a 10.5K
byte
table, with no interpolation required.

Best regards,

Spehro Pefhany --"it's the network..."            "The Journey is the reward"
speffspamKILLspaminterlog.com             Info for manufacturers: http://www.trexon.com
Embedded software/hardware/analog  Info for designers:  http://www.speff.com




_______________________________________________
http://www.piclist.com
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

2004\09\07@131114 by hilip Stortz

picon face
so i assume you have a simple detector supplying an output voltage? analog devices (i think that's right) and others produce log converters
that produce a linear output voltage over a 6 decade range of
voltage/power input.  i don't think they are even that expensive. probably the way to go rather than software, and it also lets you keep
the pic's noise pysically/electrically farther from this very sensitive
voltage measurement.  if you are dealing with microwatts, i'd think
noise pickup from the pic and any other digital circuitry would be a
real problem.

Michael Rigby-Jones wrote:
--------
> Yep, you spotted the deliberate mistake ;)  I really need to do this in less
> than 1000 cycles as I am fast running out of steam on the PIC.
---------

-- Philip Stortz--"In Germany they came first for the Communists, and I
didn't speak up because I wasn't a Communist. Then they came for the Jews, and I didn't speak up because I wasn't a
Jew. Then they came for the trade unionists, and I didn't speak up because I
wasn't a trade unionist. Then they came for the Catholics, and I didn't speak up because I was a
Protestant. Then they came for me, and by that time no one was left to speak up."
-- Martin Niemöller, 1892-1984 (German Lutheran Pastor), on the Nazi
Holocaust, Congressional Record 14th October 1968 p31636.

_______________________________________________
http://www.piclist.com
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

2004\09\07@133753 by hael Rigby-Jones

picon face
>Michael Rigby-Jones wrote:
>--------
>> Yep, you spotted the deliberate mistake ;)  I really need to do this
>> in less than 1000 cycles as I am fast running out of steam
>on the PIC.
>---------

>{Original Message removed}

2004\09\07@143347 by Scott Dattalo

face
flavicon
face
On Mon, 6 Sep 2004, Michael Rigby-Jones wrote:

<snip>

> I asked because calculating INT(LOG2(x)) is just so darn simple, and I was
> hoping there was a way of calculating the fractional bits as easily.

Michael,

Here's an observation about logarithms that may be of some assistance. The
series expansion for natural logarithms can be written:

  ln(1+x) = x - x^2/2 + x^3/3 -+ ...

Now, suppose you normalize your binary input such that the MSB is a 1 (and
by normalizing, you already know the integer portion for lg(), the base 2
logarithm). Split this normalized number into two parts, called the high
and low:

  n = normalized(input)

  n = H*a + L

Where 'a' is chosen to be larger than L (e.g. 2^8 if we're dealing
with 16-bit integers). This splits the normalized integer into a High
and Low part where L is less than 'a'. Now consider:

  ln(n) = ln(H*a + L)
        = ln(H*a * (1 + L/(H*a)))
        = ln(H*a) + ln(1 + L/H/a)
        = ln(a) + ln(H) + ln(1 + L/H/a)

The first term, ln(a), is a constant (at least for now). The second term,
ln(H), is the logarithm of the high order bits. The last term can be
expanded by the series exapnsion. Of particular interest, note that L/H/a
is way smaller than 1. The reason is that H is greater than 1 (because of
the normalization) and 'a' is greater than L. This means that the series
converges rapidly.

Substitute the series expansion:

   ln(n) = ln(a) + ln(H) + L/H/a - 0.5 * (L/H/a)^2 + O( (L/H/a)^3)
         ~= ln(a) + ln(H) + L/H/a

This approximation is accurate to within (L/H/a)^2. This expression
provides a guide on how you can trade off a lookup table size with the
interpolation.

Let's take an example. Suppose 'n' is a 16-bit integer and 'a' is 2^8.
This means that H and L are 8-bit integers. Furthermore, H is greater than
127 since the normalization operation will leave a '1' in the most
significant bit of 'n'. Use a look up table to comput ln(H) and use
fraction division to compute L/H/256.

There are many other ways to utilize the series expansion. Perhaps with
the help of the 18F's hardware multiplier you may be able to compute the
higher order terms.

Scott
_______________________________________________
http://www.piclist.com
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

More... (looser matching)
- Last day of these posts
- In 2004 , 2005 only
- Today
- New search...