Olin Lathrop wrote: > Note that this is not a moving window filter at all, but implements > exactly the filter I described with FP = 1/256. When I wrote my reply, I THOUGHT "they're the same filter" in response to the original poster's question as to how mine differed from yours... But I guess I didn't actually type it. It IS a moving-window, though; it produces a new output after each new input, and as you pointed out, each input's effect on the output disappears after 256 samples (the window width). > You can call FILTER256 several times per input sample to > effectively increase FP as Andy suggested, or change the code to do > a real shift of something less than 8 bits. Each approach will produce identical results. Because FILTER256 takes only 7 cycles to execute, though, calling it several times is faster unless "several" is really large... And it also allows you easily and quickly to use values of FP that aren't exact powers of 2. > Unfortunately Andy didn't explain his code Yeah, good point. Here's the explanation; be careful what you wish for: Think about how you'd do a straight averaging filter with a 256-sample sliding window... You'd keep the last 256 samples in a circular buffer, then every time you got a new sample, you'd throw out the oldest sample in the buffer and put the new one in. To calculate the output, you'd then sum all the samples and divide by 256: At time t: s1 + s2 + s3 + .... + s254 + s255 + s256 AVERAGE = ---------------------------------------- 256 At time t+1: s2 + s3 + s4 + .... + s255 + s256 + s257 AVERAGE = ---------------------------------------- 256 Note that I've taken slight liberties with the names of the samples. To be completely accurate, I should have called the first 3 samples s(256-t+1), s(256-t+2), and s(256-t+3)... But I figure s1, s2, and s3 are easier to read and won't cause any confusion. Anyway... Because adding up 256 values each time through the loop is slow, we can save a LOT of time by noting that most of the numbers don't change from t to t+1, so we can shortcut the process by subtracting s1/256 from AVERAGE and adding s257/256. In other words, oldest sample newest sample AVERAGE = AVERAGE - ------------- + ------------- 256 256 This is pretty straightforward, but the only way to do it exactly is to store 256 samples in memory. We don't often have that much free RAM, so let's find another way to do this (or do something close, anyway). Step through the process from time t to time t + 256. After each sample, we add that sample/256 to AVERAGE and subtract the oldest sample/256, right? Ok, what are those "oldest samples/256"? They're s1/256, s2/256, s3/256, s4/256... In fact, by the time we get to time t+256, we'll have subtracted exactly what AVERAGE was at time t. Since it'll take us 256 samples to subtract that AVERAGE, we can approximate the process by subtracting AVERAGE/256 at each sample. In other words, we can do THIS at every sample: AVERAGE newest sample AVERAGE = AVERAGE - ------- + ------------- 256 256 If that doesn't make sense, you can try looking at it this way: "On average," each sample is equal to AVERAGE, so subtracting AVERAGE/256 at each sample is, "on average," equivalent to subtracting one of our samples/256. However you look at it, though, a miraculous thing occurs when we do it this way: We no longer need to store those 256 old samples, since once a sample's been added into our average, we never need it again. To see how my code works, first rewrite the equation above: newest sample AVERAGE AVERAGE = AVERAGE + ------------- - ------- 256 256 newest sample - AVERAGE = AVERAGE + ----------------------- 256 Here are the equates: AVEHI EQU [ANY FILE REGISTER] ;Holds the average [0-255]. AVELO EQU [ANY FILE REGISTER] ;Holds the fractional part ;of the average. NEW EQU [ANY FILE REGISTER] ;Holds the new sample. We're storing AVERAGE in two parts, an integer part and a fractional part. The fractional part's denominator is 256; if our AVERAGE were equal to, for instance, 100.5 decimal, AVEHI would hold 100 and AVELO would hold 128. The code again: FILTER256: MOVF AVEHI,W SUBWF NEW,W SKPC DECF AVEHI ADDWF AVELO SKPNC INCF AVEHI ------------------------- Line-by-line explanation: ------------------------- MOVF AVEHI,W SUBWF NEW,W These two lines put (newest sample - AVERAGE) in W. If a borrow was necessary (i.e., if AVERAGE was greater than NEW), the carry flag will be clear. SKPC DECF AVEHI ADDWF AVELO These three lines do a lot: They divide the value of W by 256 and add it to AVERAGE, while also handling the borrow from the two lines above. To see what's going on, it may be helpful to imagine how this would work if the fractional part were in units of 1/100 rather than 1/256... That'll make it easier to step through it on paper or in your head. Imagine that AVERAGE is 100.5, W holds 40, and we want to add W/100 to AVERAGE: AVEHI = 100 AVELO = 50 W = 40 W/100 is 0.4, so the result should be AVERAGE = 100.5 + 0.4 = 100.9, or: AVEHI = 100 AVELO = 90 It's easy to see how to get there, right? We just add W (40) to AVELO (50). By adding W to the fractional part of the average, we IMPLY the division by 100 without actually having to spend any time doing it. Of course, there's that possible borrow from the very first two lines to take care of. We handle that by first checking for it via the SKPC, then -- if the carry is clear, indicating a borrow -- decrementing AVEHI. SKPNC INCF AVEHI Adding W to AVELO in the three lines above may produce a result larger than can be stored in AVELO (i.e., there may be a carry). If that happens, we handle it in these final two lines; if the carry flag is set, we increment AVEHI. -------------------------------------------- A full, step-by-step example (using units of 1/100 to make it easier to follow along): -------------------------------------------- AVERAGE = 90.9 and NEW = 10. We want AVERAGE = AVERAGE + (NEW - AVERAGE)/100, or AVERAGE = 90.9 + (10-90.9)/100 = 90.9 - 80.9/100 = 90.9 - 0.8 = 90.1 Step through the code: NEW = 10 AVEHI = 90 AVELO = 90 First, subtract AVEHI from NEW and store the result in W: W = NEW-AVEHI = 10-90 = -80, or 20 with a -100 borrow Since there's a borrow, the SKPC isn't taken and we decrement AVEHI: AVEHI = AVEHI-1 = 90-1 = 89 Add W to AVELO: AVELO = AVELO+W = 90 + 20 = 110, or 10 with a +100 carry Since there's a carry, the SKPNC isn't taken and we increment AVEHI: AVEHI = AVEHI+1 = 89+1 = 90 So after those 7 instructions: AVEHI = 90 AVELO = 10 Which means AVERAGE = 90.1, which is what we wanted. -Andy === Andrew Warren -- aiw@cypress.com === Principal Design Engineer === Cypress Semiconductor Corporation === === Opinions expressed above do not === necessarily represent those of === Cypress Semiconductor Corporation -- http://www.piclist.com hint: To leave the PICList mailto:piclist-unsubscribe-request@mitvma.mit.edu