Shop Learn
Compute Mult, such that Signal ** Mult == Target, using a binary search. — Parallax Forums

Compute Mult, such that Signal ** Mult == Target, using a binary search.

Phil Pilgrim (PhiPi)Phil Pilgrim (PhiPi) Posts: 22,999
edited 2021-04-22 05:09 in BASIC Stamp

A typical problem in signal processing is calibration, wherein you take a raw signal and multiply it by a scaling factor to get a calibrated value. Whether it's wind speed, air pressure, temperature, or a white-balanced color coordinate, the process is the same. The tricky part is computing the scaling factor from a a known signal reading.

In working with the ColorPAL, for example, doing a white balance is critical to getting the RGB figures the same when presented with a white target. In the past, I've taken the raw readings from a white target and divided them into $FF80 to get a correction factor:

sred = $FF80 / red
sgrn = $FF80 / grn
sblu = $FF80 / blu

Then, when I want a white-balanced reading, I do this:

red = red */ sred
grn = grn */ sgrn
blu = blu */ sblu

This works fine when you're normalizing white to be $FF (255) across all the RGB coordinates. But it's not fine if you want a larger range. In that case you want to use:

red = red ** sred
grn = grn ** sgrn
blu = blu ** sblu

But how to find the s--- values, when the target white value is, say, white? On a calculator they would be, for example:

sred = white * 65536 / red

But you can't do that computation directly on a BASIC Stamp.

Tracy Allen has solved this by writing a long division routine, which he describes here:

http://emesystems.com/OLDSITE/BS2math2.htm

I decided to go at it from a slightly different direction, using a binary search. Here's a program that implements that search and tests it:

'   {$STAMP BS2PE}
'   {$PBASIC 2.5}

mult         VAR  Word
signal       VAR  Word
targ         VAR  Word
x            VAR  Word
seed         VAR  Word
sumiter      VAR  Word
i            VAR  Nib
j            VAR  Byte

targ = 1000
seed = 6789

DEBUG "  X     M   X**M Iter", CR
DEBUG "----- ----- ----  --", CR

FOR j = 1 TO 50
  RANDOM seed
  signal = seed ** 30000 + targ
  GOSUB FindMultiplier
  DEBUG DEC5 signal, " ", DEC5 mult, " ", DEC4 signal ** mult, "  ", DEC2 15 - i, CR
  sumiter = sumiter + 15 - i
NEXT
sumiter = sumiter / 5
DEBUG CR, "Average iterations: ", DEC sumiter / 10, ".", DEC sumiter // 10, CR
END

FindMultiplier:

  mult = $8000                 'Set multiplier to a middle value
  FOR i = 14 TO 0              'Do 15 iterations.
    x = mult ** signal         'Compute a trial value.
    IF (x > targ) THEN         'If it's too big, subtract half the remaining distance from the multiplier.
      mult = mult - (1 << i)
    ELSEIF (x < targ) THEN     'If it's too small, add half the remaining distance to the multiplier.
      mult = mult + (1 << i)
    ELSE                       'If it's spot on, quit.
      EXIT
    ENDIF
  NEXT
  RETURN

Here's the output:

  X     M   X**M Iter
----- ----- ----  --
12184 05384 1000  13
23626 02776 1000  13
18308 03580 1000  14
10746 06104 1000  13
02405 27264 1000  09
25099 02612 1000  14
21013 03120 1000  12
25208 02600 1000  13
26628 02462 1000  15
12598 05204 1000  14
10629 06168 1000  13
27791 02360 1000  13
29316 02236 1000  14
25131 02608 1000  12
09879 06640 1000  12
09242 07096 1000  13
25501 02572 1000  14
17490 03748 1000  14
04885 13424 1000  12
27407 02392 1000  13
14758 04444 1000  14
03763 17424 1000  12
02249 29152 1000  11
26403 02484 1000  14
24089 02722 1000  15
23559 02784 1000  11
20092 03264 1000  10
23457 02796 1000  14
15143 04328 1000  13
12090 05424 1000  12
22654 02894 1000  15
06156 10656 1000  11
07473 08776 1000  13
23697 02768 1000  12
19062 03440 1000  12
23883 02746 1000  15
09717 06748 1000  14
11618 05644 1000  14
01529 42880 1000  09
22311 02940 1000  14
02136 30688 1000  11
15891 04128 1000  11
05866 11176 1000  13
04504 14560 1000  11
20440 03208 1000  13
08093 08104 1000  13
15524 04224 1000  09
01570 41760 1000  11
09490 06912 1000  08
03519 18624 1000  10

Average iterations: 12.5

It seems to work, and I will be using it henceforth in a certain ColorPAL application that I've written for a customer.

-Phil

Comments

  • This is extremely clever and I may be trying it soon in the 32-bit space of Propeller projects.

Sign In or Register to comment.