DEMO: Succesive Aproximation Normalization (SAN) Filter
Beau Schwabe
Posts: 6,575
This is just a cool little code snip-it I wanted to pass along. Although written for the Propeller, it could easily be adapted to a Basic Stamp.
Purpose:
Take a data value where you know the upper and lower limits and
"normalize" the data so that it proportionally scales to a binary
weighted value.
For instance, say you have a potentiometer that reads 204 on one extreme
and 8453 on the other extreme. ...And the current value is 2834.
You want to scale that to a 12-Bit number? Simply load the Data,
BitResolution, RefLOW, RefHIGH variables and call the function. The
returned value will contain the result. 1306 in this case.
Yes, you could apply the formula ...
Data = [(Data-RefLOW)/(RefHIGH-RefLOW)]*(2^BitResolution)
... but the SAN filter avoids any floating point, and gets the job done
using only shift and adds.
enjoy!
OBEX:
http://obex.parallax.com/snippet/699
Purpose:
Take a data value where you know the upper and lower limits and
"normalize" the data so that it proportionally scales to a binary
weighted value.
For instance, say you have a potentiometer that reads 204 on one extreme
and 8453 on the other extreme. ...And the current value is 2834.
You want to scale that to a 12-Bit number? Simply load the Data,
BitResolution, RefLOW, RefHIGH variables and call the function. The
returned value will contain the result. 1306 in this case.
Yes, you could apply the formula ...
Data = [(Data-RefLOW)/(RefHIGH-RefLOW)]*(2^BitResolution)
... but the SAN filter avoids any floating point, and gets the job done
using only shift and adds.
enjoy!
OBEX:
http://obex.parallax.com/snippet/699
Comments
PUB SAN(_Data,_BitResolution,_RefLOW,_RefHIGH):Temp|RefMID repeat _BitResolution RefMID := (_RefHIGH + _RefLOW) >> 1 Temp += Temp - (_Data > RefMID) if Temp & 1 _RefLOW := RefMID else _RefHIGH := RefMIDOf course this will still be slower than the equation form, but to use that you need to reorder so you do the multiplication (via SHL), then the division, and of course make sure the intermediate values don't overflow. A PASM version of this function would be a clear winner.thanks,
Jonathan
Thanks... I added and Assembly option to the OBEX file ... version 1.1
'------------------------------------------ Allocate Variables in SPIN VAR long Data,BitResolution,RefLOW,RefHIGH '------------------------------------------ Call Assembly routine from some PUB PUB DEMO cognew(@PASM,@Data) '------------------------------------------ '------------------------------------------ Main Assembly program '------------------------------------------ DAT org '------------------------------------------ Get Variables PASM mov pTemp,par rdlong pData,pTemp add pTemp,#4 rdlong pResolution,pTemp add pTemp,#4 rdlong pRefLOW,pTemp add pTemp,#4 rdlong pRefHIGH,pTemp add pTemp,#4 mov pTemp,#0 '------------------------------------------ Apply Filter Loop mov pRefMID, pRefHIGH add pRefMID, pRefLOW shr pRefMID, #1 sub pRefMID, pData wc,nr if_c mov pRefLOW, pRefMID 'If pData > pRefMID ; RefLOW = pRefMID if_nc mov pRefHIGH, pRefMID 'If pData =< pRefMID ; RefHIGH = pRefMID rcl pTemp,#1 djnz pResolution, #Loop wrlong pTemp,par '------------------------------------------ Exit COG cogid pTemp cogstop pTemp pData long 0 pResolution long 0 pRefLOW long 0 pRefHIGH long 0 pRefMID long 0 pTemp long 0-Phil
You realize the algorithm is just a classic game of "Pick a number between 1 and 10 in the fewest number of guesses"? ; the only feedback you get is if your guessed number is higher or lower than the actual number. What most people don't realize is that this classic game produces a binary equivalent of the actual number that you are trying to guess if you were to keep track of the HIGH and LOW results when guessing.
Here is a writeup I did back in March for our local Hacker space:
Thanks Beau, nice and neat. I normally do this with scaled integers but here is your method tested in my Tachyon Forth.
Just copy and paste all of this to load and run.
[FONT=courier new]\ Succesive Aproximation Normalization Filter v1.1 - Beau Schwabe \ Modified for Tachyon Forth \ REGISTER METHOD - uses temp registers for variables \ offsets: 0 = high 4 = low 8 = data \ Code size = 40 bytes \ Execution time = 246us DECIMAL HERE \ use decimal mode and mark code space fo pub SAN ( res data low high -- result ) 0 REG ! 4 REG ! 8 REG ! 0 SWAP FOR ( temp ) 2* 0 REG @ 4 REG @ + 2/ ( temp mid ) DUP 8 REG @ < IF 4 REG ! 1+ ELSE 0 REG ! THEN NEXT ; \ Report code size HERE SWAP - CR . ." bytes " \ Run demo and also report execution time 12 2834 204 8453 NEWCNT SAN .LAP CR ." Result = " . ( 1306 ) [/FONT]This is the result:
BTW, this is the normal named variables method in place of the temporary "registers"
[FONT=courier new]\ VARIABLES METHOD - 288us 40 bytes LONG data,low,high DECIMAL HERE pub SAN ( res data low high -- result ) high ! low ! data ! 0 SWAP FOR ( temp ) 2* high @ low @ + 2/ ( temp mid ) DUP data @ < IF low ! 1+ ELSE high ! THEN NEXT ; HERE SWAP - CR . ." bytes " 12 2834 204 8453 NEWCNT SAN .LAP SPACE . ( 1306 ) [/FONT]and wondered about the real timings of the different versions of to solve this problem
so I made some experiments, first in Tachyon then in SPIN.
For the Tachyon code see this post in the Tachyon thread.
What is still missing is a straight forward SPIN implementation using the FLOAT library
which I expect to be really slow.
Maybe someone can provide the numbers.
this is the problem we want to solve:
1) Data = [(Data-RefLOW)/(RefHIGH-RefLOW)]*(2^BitResolution)
if we rearrange it a little we get rid of the requirement for float immediately
2) Data = (Data-RefLOW) * (2^BitResolution) / (RefHIGH-RefLOW)
and then replace the * 2^n with shift left
3) Data = ((Data-RefLOW) SHL BitResolution) / (RefHIGH-RefLOW)
I get the following timings: @80MHz
Beau's filter in PASM 26 us
Beau's filter in SPIN 579 us ( Peter writes around 1300us in his EXTEND.fth, I don't know how he measured it)
EQ3 in SPIN 34 us
from Tachyon
Beau's filter in TForth 205 us
EQ2 in a lazy impl. in TF 208 us
EQ2 fast impl. in TF 28 us
EQ3 fast TF impl. 24 us
SPIN FLOAT-LIB ?? the horrible example of NOT to do it ;-)
PASM impl. of EQ3 ?? would be a great reference
VAR '-------------------------------------------------------- ' Variables must remain in this order for both optons long Data,BitResolution,RefLOW,RefHIGH,Data2,ResSpin,ResMJB,Resasm,Ressimple,Tasm,Tspin,Tsimple '-------------------------------------------------------- PUB DEMO PST.Start(230400{<- Baud}) BitResolution := 12 RefLOW := 204 RefHIGH := 8453 Data := 2834 'Assembly Version Tasm := cnt Filter.Asm(@Data) Tasm := (cnt - Tasm) / 80 ' us Data2 := 2834 Tspin := cnt ResSpin := Filter.Spin(Data2,BitResolution,RefLOW,RefHIGH) 'Spin Version Tspin := (cnt - Tspin) / 80 ' us Tsimple := cnt ' ResMJB := SARMJB(Data2,BitResolution,RefLOW,RefHIGH) ResMJB := ((Data2 - RefLOW) << BitResolution ) / (RefHIGH - RefLOW) ' direct SPIN version Tsimple := (cnt - Tsimple) / 80 repeat PST.dec(Data) ' from PASM PST.Char(9) PST.dec(Tasm) PST.Char(9) PST.dec(ResSpin) PST.Char(9) PST.dec(Tspin) PST.Char(9) PST.dec(ResMJB) PST.Char(9) PST.dec(Tsimple) PST.Char(13) ' PST.Char(10) DAT { result is value time in us Filter.Asm(@Data) 1306 26 Filter.Spin 1306 579 direct SPIN 1305 34 }