Number Sort Algorithm

[aratti]

Had you made any other changes?

Yes, a second one, but more for cleaning the code, since it didn't effect functionality:

RawData(CounterA+1+0) = RawData(CounterA) ^ RawData(CounterA+1)

Has been cleaned with:

RawData(CounterA+1) = RawData(CounterA) ^ RawData(CounterA+1)

Well, I wouldn't think it's a problem.
Right after the IF block that statement is in, Melanie put a ...

CounterA=CounterA+1

So if CounterA = 1, subtracting 2 makes it 255, then adding 1 makes it 0 again

But the above make sense, I do better check the whole system again.

Thank you Darrel.

Al.

[boroko]

WOW, must be a good day!
I remembered Melanie had a comment on sorting out changing inputs, but I couldn't find my bookmark for it. I went to the main forum page and there it was on the right column!
Whew! someone must be looking out for me....

My situation involves reading WORD sized data every 30ms (with quite a few spurious readings) and controlling a PWM output with somewhere near a 2-3 second response to drive some mechanicals that require slow reaction. I have been trying to mold Darrel's DT_Average16 routine to make it work, but with little success in this application.

Can someone elaborate a bit on feeding fresh data into this sort and trimming the top and bottom readings? I don't understand how to run this with a continuous data stream without blowing up the sort.

Thanks
Bo

[boroko]

Here is what I have come up with so far.....
it is getting closer.
Derived from Malanie's suggestion about parsing data and DT's averaging scheme * PIC18F2525 @ 8 MHz

ByteData var byte                                                                                                      
CounterA    var word             ' sort counter
CounterB    var byte
CounterC    var byte
DataA       var word             ' storage for sorted values
DatSort     var byte             ' pointer to middle 8 values
DatAvg      var word             ' averaged value of sorted data
RawData     var word[16]         ' storage for raw data
Clear
AvgCount	CON  8		         ' = Number of samples to average
FAspread	CON  1000	         ' = Fast Average threshold +/-
INCLUDE "AllDigital.pbp"
DEFINE OSC 8
OSCCON = %01110000
DEFINE HSER_RCSTA 90h ' Enable serial port & continuous receive
DEFINE HSER_TXSTA 24h ' Enable transmit, BRGH = 1
DEFINE HSER_CLROERR 1 ' Clear overflow automatically
DEFINE HSER_SPBRG 34  ' 57600 Baud @ 8MHz, -0.79%
SPBRGH = 0
BAUDCON.3 = 1         ' Enable 16 bit baudrate generator

hserout["SortAverage",10,13]
pause 500
goto Start

'Sort Array SUB ** collects 16 readings, sorts, and averages middle 8 ******
SortArray:
    CounterA=0
SortLoop:                          ' sorts 16 readings of RawData in order
    If RawData(CounterA+1) < RawData(CounterA) then
        DataA=RawData(CounterA)
        RawData(CounterA)=RawData(CounterA+1)
        RawData(CounterA+1+0)=DataA
        If CounterA > 0 then CounterA=CounterA-2
        endif
    CounterA=CounterA+1
    If CounterA < 15 then goto SortLoop
'    for CounterC = 0 to 15        ' These three lines O/P the sort results
'    hserout["Ordered[",dec CounterC,"]= ", dec RawData[CounterC],10,13] 
'    next CounterC
'**** Trim and Average ***************************************************
   for DatSort = 4 to 11                    ' pick out middle 8 readings
    IF ABS (DatAvg - RawData[DatSort]) > FAspread Then CatchUp
    IF ABS (DatAvg - RawData[DatSort]) < AvgCount Then RealClose
    DatAvg = DatAvg - (DatAvg/AvgCount)
    DatAvg = DatAvg + (RawData[DatSort]/AvgCount)
    GoTo AVGok
  CatchUp:
    DatAvg = DatAvg + (RawData[DatSort]/8)  ' catch-up by 1/8 value of reading
    GoTo AVGok
  RealClose:
    DatAvg = DatAvg - (RawData[DatSort]/(AvgCount/4))
    DatAvg = DatAvg + (DatAvg/(AvgCount/4))
  AVGok:
' hserout["Middle[",dec datsort,"] = ",dec RawData[DatSort],10,13] 'SHOW mid 8
   next DatSort
    Return  
'** END SUB************************
Start:
      FOR CounterB=0 to 15
     HSERIN [RawData[CounterB]]
      NEXT CounterB      
      FOR CounterB=0 to 15
      HSEROUT["RawData[",DEC counterB,"] = ",DEC rawdata[CounterB],10,13]
      NEXT CounterB
      CALL SortArray
      HSEROUT ["Sorted Averaged result ",dec DatAvg,10,13]
     GOTO start

[aratti]

for DatSort = 4 to 11                    ' pick out middle 8 readings
 DatAvg = DatAvg + RawData[DatSort]
NEXT DatSort

DatAvg = DatAvg >>3
Return

You can short and semplify your averaging routine with the above example. DatAvg sums up the 8 central values then you devide by 8 for the average.

Al.

[boroko]

Hi Al. Thanks for looking at it.

I like the way you simplified, but my concern was that since I will be working with WORD data, the result of the addition could get big enough that I would have to use LONGs if I didn't use DT's running average scheme.

So far, I have only tested it with byte data, and it does seem to settle slowly on something close to average. I need to try WORD data and see how that works.

Bo

[aratti]

... but my concern was that since I will be working with WORD data, the result of the addition could get big enough that I would have to use LONGs...

Using a 10 bits adc, the maximun number you can obtain is 1023. Now summing up 8 readings of 1023 each, you will end up with your word variable at 8184 (overflow will occur at 65K)

Since you are using adc , you have to remove

INCLUDE "AllDigital.pbp"

from your code.

Al.

[boroko]

Hi Al,
Thanks for engaging in this thread. Sometimes when one posts and gets no response, you begin to worry if your question is so off the wall that no one is interested.

The values that I'm working with are actually timer values that are WORD sized. The ultimate result is measuring ultrasonic pulse return to calculate distance. In the real program, I'm using a comparator interrupt to grab of the values. That one uses the analog, but here I'm just trying to sort out the averaging scheme.
The response needs to be smoothed considerably due to the high instance of random response of the ultrasonics. The values go on to determine the PWM output that drive a servo valve that controls some heavy hydraulics that can't tolerate quick movement. The response time needs to be in the 2-3 second range with smooth changes to work well. Since the values are 0-65535, and readings every 30mS, I'm trying to use Melanie's suggestions to dump the extremes, and DT's averaging to get away from LONGs and 32 bit math.

Current testing is with a second PIC generating the return pulse timing to separate the circuit from the program so that I can find the weakness. I'm trying to send a serial in to simulate the echo numbers. The next step is to convert the RX bytes into WORDS and see if the program works correctly.

Back to Burn and Turn
Bo