Fast software signal filtering

[Psi]

Hey guys,

Can anyone think of a good approach to convert the yellow ADC input waveform into the green signal using software on an AVR.
(The green signal will then be converted to a digital stream of bits)
I've tried a running average but i'd prefer something a bit more advanced that's able to keep the edges as sharp as possible.



It's important that the top part of the waveform is used to create the new signal because the signal can also look like this.

[IanB]

I'm not clear about your requirements. Is the AVR sampling the data and you want to process it in real time--and the oscilloscope pictures are just for illustration?

Assuming the above to be true, you can write any software you like to do the job. Is it the algorithm you are asking for suggestions about?

If you are asking about the algorithm, that could be easy or hard depending on the details. How many possible levels can the green trace have? Assuming it is a small number like 16 I would write code that detects the height of each peak in the yellow signal and then maps this to the nearest valid level of the green signal. However, your first and second illustrations are contradictory. If the upper trace were processed according to the parameters of the lower trace, then your step signal would become a staircase signal.

With this kind of question the answers are all in the details, and the details are complex.

[Psi]

I'm not clear about your requirements. Is the AVR sampling the data and you want to process it in real time--and the oscilloscope pictures are just for illustration?

Sorry, yes, the adc is sampling the yellow data on the scope and i want to process it in real time on the AVR.

Is it the algorithm you are asking for suggestions about?

Yes

If you are asking about the algorithm, that could be easy or hard depending on the details. How many possible levels can the green trace have? Assuming it is a small number like 16 I would write code that detects the height of each peak in the yellow signal and then maps this to the nearest valid level of the green signal. However, your first and second illustrations are contradictory. If the upper trace were processed according to the parameters of the lower trace, then your step signal would become a staircase signal.

The green will eventually be turned into straight digital, i was just trying to break down the steps needed and focus on cleaning up the signal first.

With this kind of question the answers are all in the details, and the details are complex.

Yeah, i'm not after example code. Just ideas.

Since posting i've had the idea of a running average that then averages the answer with the center value of the average range.
This would make it quicker to respond to changes on the edges each pulses. but i've not tried it yet.

[Zad]

Use the maximum value of the last (n) samples? Very fast to do and only needs a small circular buffer.

[Psi]

Use the maximum value of the last (n) samples? Very fast to do and only needs a small circular buffer.

That's so simple there has to be some reason i didn't think of it 
But i can't think of one 

I will try that asap
Thanks

EDIT:  Ok, i think i see why that might not be the best plan.
It's fine for when the buffer first encounters a pulse. (it responds instantly with the new max value)
But when it exist the end of a pulse its going to use the max value until the buffer clears.
So the pulses are all going to end up longer than they should be by the length of the buffer.

[IanB]

The green will eventually be turned into straight digital, i was just trying to break down the steps needed and focus on cleaning up the signal first.

Does digital mean binary high/low?

Yeah, i'm not after example code. Just ideas.

I didn't mean that kind of complex, just the complexity of the specification and requirements.

Judging by your time base, this is a very slow signal (7 ms pulse duration?). So you should have plenty of time to process the data for each sample point and pulse I think?

If your output is binary high/low, you can just apply some measure of the signal and switch the output depending on whether it is above or below your threshold.

You will need to specify whether the output basis is absolute or relative I think. If the signal basis is absolute you can set the output directly based on whether your measured value is above or below your threshold. If relative, you will need to switch the state of the output according to whether the upward or downward swings of the signal are greater than some relative threshold.

Some of my puzzlement comes from your pictured green traces. They don't seem to be binary, and they don't seem consistent in levels between examples.

[Psi]

Does digital mean binary high/low?

Correct, just a bitstream

Judging by your time base, this is a very slow signal (7 ms pulse duration?). So you should have plenty of time to process the data for each sample point and pulse I think?

Yep, its very slow compared to the 8MHz micro clock.

If your output is binary high/low, you can just apply some measure of the signal and switch the output depending on whether it is above or below your threshold.

Ideally yes, but the signal does have some DC offset which changes a little. So it has to be a little more intelligent and find the center itself. But i'm ok with that part, i've already got that to work.

You will need to specify whether the output basis is absolute or relative I think. If the signal basis is absolute you can set the output directly based on whether your measured value is above or below your threshold. If relative, you will need to switch the state of the output according to whether the upward or downward swings of the signal are greater than some relative threshold.

Yeah

Some of my puzzlement comes from your pictured green traces. They don't seem to be binary, and they don't seem consistent in levels between examples.

That's not a trace, i just drew it on the picture to show the kind of output i was looking for.
Sorry for the confusion.
I figured the first step was to tidy up the signal and get something resembling a square wave.
Then the next step would be to convert that to a digital bitstream.

[IanB]

That's not a trace, i just drew it on the picture to show the kind of output i was looking for.

I understood that, but you drew the green signal with varying levels so it wasn't clear how many possible levels it could have. If the green signal can only have two levels the problem is greatly simplified.

[Psi]

That's not a trace, i just drew it on the picture to show the kind of output i was looking for.

I understood that, but you drew the green signal with varying levels so it wasn't clear how many possible levels it could have. If the green signal can only have two levels the problem is greatly simplified.

Well i had planed to keep it as a 10bit analog signal during the cleanup process.
One i had a clean 10bit square wave i was going to convert that to digital.

It's definitely possible to do it all at once but i find it easier to do things separately at first.
Just because its easier to understand each step. When i have it working i may merge the code and convert straight from 10bit raw signal to digital.

[Mechatrommer]

my suggestion from what i understand so far, the variation will depend on your signal threshold (hi vs lo). pseudo code follows:

registers
lowAdc ;define the threshold between hi and lo
curAdc ;current adc value
prevAdc ;previous adc value
peakAdc ;latest peak adc value

main:
    user defines lowAdc value
    user make necessary initial setup here

    curAdc = getAvrAdcPin
    filterFunc
goto main:

filterFunc:
    prevAdc = curAdc
    getPeakAdc

    if peakAdc > lowAdc then
         setIoPin = HIGH
    else
         setIoPin = LOW
    endif
goto filterFunc

getPeakAdc:
    ;when signal is rising during entry/call, detect peak adc and wait until the next rise
    ;when signal is falling during entry/call, return whatever current adc value and wait until the next rise

    curAdc = getAvrAdcPin
    if curAdc < prevAdc then ;signal moving down
        peakAdc = prevAdc
        waitUntilRising
    else ;signal moving up
        prevAdc = curAdc
        goto getPeakAdc
    endif
return

waitUntilRising:
    prevAdc = curAdc
    curAdc = getAvrAdcPin
    if curAdc <= prevAdc then goto waitUntilRising ;loop if signal still falling
return ;signal is moving up, quit loop/wait

getAvrAdcPin
    ;delay function if necessary to reduce sampling rate or error due to ripple/noise
    refer to datasheet on how to read avr adc
return

basically the logic/idea is... for each pulse, the program will detect its peak, if its above threshold, IO = HIGH, else IO = LOW, thats it. maybe some logic error there, but you may harness and/or modify the logic. for eg, the above logic will only change IO state LO<->HI after each valley in a pulse. so there's some delay there. YMMV, hope it helps.

[sub]

If Wikipedia is to be believed, the optimal (in terms of SNR) linear filter would be that given by correlating it with a single pulse:

http://en.wikipedia.org/wiki/Matched_filter

Are you limited in terms of the delay that you can tolerate?

[Zad]

Keeping the envelope can be done, but it will have to have a latency equivalent to the duration of one pulse. For example, you show the green line dropping on the trailing edge of one pulse. If you as a human could not see whether the following pulse were high or low, you could not tell whether the envelope was falling. Therefore you need to know what the next pulse will be.

[Rerouter]

question, why cant you make your carrier signal so that it equally divides into your data signal? e.g. slightly lower frequency so you get 5 pulses per bit, and with that measure the middle 3 sample peaks of each bit, and do what filtering you wish with that,

[ejeffrey]

A matched filter is good in the case where you know the impulse response of your channel and it is subject to additive white noise (I think).  This does not appear to be the case here: the "noise" is strongly correlated with the signal.  This is more of a demodulation problem than a noise filtering problem.  If you can get or generate a local oscillator of the carrier wave, it is easy to demodulate, and will do an excellent job of filtering out-of-band noise.  Failing that, I would use a peak-detection heuristic with automatically adjusted hysteresis.

[Psi]

<code>

basically the logic/idea is... for each pulse, the program will detect its peak, if its above threshold, IO = HIGH, else IO = LOW, thats it. maybe some logic error there, but you may harness and/or modify the logic. for eg, the above logic will only change IO state LO<->HI after each valley in a pulse. so there's some delay there. YMMV, hope it helps.

Thanks for that, every bit helps

If you as a human could not see whether the following pulse were high or low, you could not tell whether the envelope was falling. Therefore you need to know what the next pulse will be.

Yeah, that issue had been annoying me for days.
Ya can't tell if a pulse is over until enough time has passed without another pulse occurring. And by then its too late and ya have to backtrack and correct the pulse ending position.
Luckily i think the new approach of syncing to the carrier and sampling at the top of each waveform should bypass that issue.

question, why cant you make your carrier signal so that it equally divides into your data signal? e.g. slightly lower frequency so you get 5 pulses per bit, and with that measure the middle 3 sample peaks of each bit, and do what filtering you wish with that,

i don't have control of the carrier.  If i could i would remove it entirely.

This is more of a demodulation problem than a noise filtering problem.  If you can get or generate a local oscillator of the carrier wave, it is easy to demodulate, and will do an excellent job of filtering out-of-band noise.  Failing that, I would use a peak-detection heuristic with automatically adjusted hysteresis.

Yeah, that's the approach im trying at present. 
I've not got it working yet but if i can figure out the period of the carrier in real time then start a timer at the falling edge i can read the waveform at the top of each cycle and the carrier should completely disappear.

[AntiProtonBoy]

Apply a low pass filter on the incoming signal, something like a Gaussian smoothing function. Then take the double derivative of resulting signal. The inflection points will denote the rise and fall  thresholds for  the smoothed curve.

Also, obviously the window size of the Gaussian function will determine the sensitivity of your threshold detector. Smaller windows will be less computationally expensive, and respond to crisper transitions at the expense of more false triggering (if you have a noisy signal). Bigger windows are more robust, and more expensive.

[sub]

Actually, thinking about it again, could one not just demodulate directly by undersampling?  Sample twice at the modulation frequency, with every other sample going into a second buffer, and then find the magnitude by interpreting them as the real and imaginary parts of a complex signal.  Some example Octave code to illustrate:

Code: [Select]

f = @(t) t.^2 .* sin(2*pi*t+0.1)

I = f(0:1:4);
Q = f(0.25:1:4.25);

plot(0.25:1:4.25,sqrt(I.^2 + Q.^2),'bo');
hold on;
plot(0:0.1:5,(0:0.1:5).^2, 'r');
hold off;
legend('Demodulated', 'Transmitted');

The catch I suppose is that you would need to lock to the modulating carrier so that you don't get a beat frequency.  Other than the need for a (software) PLL or somesuch, does anyone see a problem here other than the complexity of the frequency locking?  Obviously you could get better noise performance by sampling again at the other two quadrants.

[AntiProtonBoy]

Personally, I'd do as much signal conditioning in hardware as possible before doing processing in software.

What about using an envelope detector at the input? I'd imagine that would simplify your software requirements a great deal.

[Psi]

Actually, thinking about it again, could one not just demodulate directly by undersampling?  Sample twice at the modulation frequency, with every other sample going into a second buffer, and then find the magnitude by interpreting them as the real and imaginary parts of a complex signal.  Some example Octave code to illustrate:

Code: [Select]

f = @(t) t.^2 .* sin(2*pi*t+0.1)

I = f(0:1:4);
Q = f(0.25:1:4.25);

plot(0.25:1:4.25,sqrt(I.^2 + Q.^2),'bo');
hold on;
plot(0:0.1:5,(0:0.1:5).^2, 'r');
hold off;
legend('Demodulated', 'Transmitted');

The catch I suppose is that you would need to lock to the modulating carrier so that you don't get a beat frequency.  Other than the need for a (software) PLL or somesuch, does anyone see a problem here other than the complexity of the frequency locking?  Obviously you could get better noise performance by sampling again at the other two quadrants.

Yeah, locking to the carrier is proving to be quite cpu intensive.
Thanks for the code though, its give me a few more ideas

Personally, I'd do as much signal conditioning in hardware as possible before doing processing in software.

What about using an envelope detector at the input? I'd imagine that would simplify your software requirements a great deal.

wow, that looks like exactly what i want.
I just wired it up and it makes a HUGE difference over a typical RC filter.

I can only do a very limited hardware based filter on the signal before the MCU in terms of cost and pcb footprint.
All the RC filters i tried didn't work very well which is what made me look at a software based filter.
but that envelope filter seems to work much better.

Thanks!
I will have a play with that tomorrow but i think its going to be the best solution.

Today has been all coding and trying to sync to the high frequency in software and then cancel it out. It did work but it's taking up so much cpu time that there's not much left for other things.

[Lesolee]

I noticed on the first post that your desired waveform is not physically possible. You are trying to PREDICT that the waveform will not rise again! The best you can possibly do is lock onto the frequency of the waveform and when the edge does not occur at the expected time, change state. If the frequency of the pulses is constant then an analog detector will not be too bad. (I am trying to distinguish between the pulses within the group compared to the size of the "packet" containing the pulses.)

I think for this case a digital filter is always going to be faster and more adaptive than its analog counterpart. 

[IanB]

I noticed on the first post that your desired waveform is not physically possible.

Yes, I noted that too. The green line rises to its final level in the first picture long before the amplitude of the yellow trace has got there. It would be impossible to achieve the green line in real time, although if some kind of look ahead and processing delay between input and output were allowed it might be possible.

Which brings up a general observation about problem solving: it is important to develop a clear high level description and specification and understanding of the expected outcome before delving into filters and programs and circuit designs.

As far as I can tell this thread has never contained an adequately precise statement of the problem, consisting of a thorough description of the properties of the input signal, its range, its variations and its characteristics; an exact description of the output signal; and a statement of how the output signal needs to relate to the input signal in the time and frequency domains.

Without such a problem statement, designing a solution is going to be a somewhat ad-hoc process and the result buggy.

(Sad to say, this situation also crops up far too much in the software world and computer programs are accordingly full of bugs.)

[Mechatrommer]

The green line rises to its final level long before the amplitude of the yellow trace has got there

my imagination tells me by using comparator, it might be possible. but not a comparator alone, i think there will be "adjustable voltage divider" to define hi volt value, and then a hysterisis or delay/low pass circuit etc etc. but it could get messy after that, let alone the detection for hi->lo pulse.

[IanB]

my imagination tells me by using comparator, it might be possible. but not a comparator alone, i think there will be "adjustable voltage divider" to define hi volt value, and then a hysterisis or delay/low pass circuit etc etc. but it could get messy after that, let alone the detection for hi->lo pulse.

Yes, if you bring in more information about the yellow signal than we have been given it might be possible. For example if you know ahead of time that the yellow signal is amplitude modulated and it has only two states, "low" and "high", and you know the amplitude ranges that low and high correspond to, and you know the shortest possible duration of a low and high state before it can change again--then if you are currently in the low state and you detect an upward trend in amplitude that exceeds the noise threshold of uncertainty and which occurs after the minimum low time has passed, then you can switch to the high state.

But if you can't nail down the description of the input signal that tightly, you will be subject to false detection and errors on output. Most likely a real system would include a digital error correction code (ECC) to guard against the inevitable bit errors that occasionally will occur no matter how good the decoding circuit is.

[ejeffrey]

The green line rises to its final level long before the amplitude of the yellow trace has got there

my imagination tells me by using comparator, it might be possible. but not a comparator alone, i think there will be "adjustable voltage divider" to define hi volt value, and then a hysterisis or delay/low pass circuit etc etc. but it could get messy after that, let alone the detection for hi->lo pulse.

The real issue is that the yellow curve contains essentially no information in the troughs.  A rising edge of the green curve anywhere between one falling edge and the next rising edge will give rise to the same signal, therefore it is not possible to distinguish the possibilities.  If you have some external clock and you know that the green curve can only change state at certain times, then you can reconstruct the signal nearly exactly.  Otherwise you will always have an uncertainty window of approximately half the carrier period in the timing of the rising and falling edges.

[Psi]

Thanks guys,

Yeah, i probably should have given more information at the start but i don't like to get too bogged down in specifications limits when trying to solve a specific problem.
I've been burnt before when the specification were set so tight that the solution ended up being more complicated than it really needed to be.

Sometimes it's good to throw the specs out the window and just look at ideas, even if they probably wont work, because they prompt other ideas that may turn out to be better.

The signal is from a photodiode with pulldown which is pointing at a computer screen. An application is flashing binary data on the screen in black and white.
The higher frequency is the LCD backlight pwm and the low frequency is the actual flashing of data.

The pictures i gave are from 40% and 0% brightness on the lcd.

What i want to do is recover the binary data in code.
I've already put a hardware envelope filter on the input as AntiProtonBoy recommended and it looks much better but the filtered pulses are still quite chaotic under 30% brightness. Currently i'm trying to improve my adc sampling code to filter and recover the data.
I'm using Manchester code to encode the data and that is all working fine.


My current technique is to do a 32 sample running average and then trigger a timer when a crossover is detected (average moves between halfway point).
The timer is set to skip any subpulse (Manchester polarity correction) and then start looking for the next data pulse.  Being Manchester code,  the rising or falling edge give the high or low bit state.