Automatic detection of logic levels in a signal?

[Artlav]

Short version: Given an unbalanced signal (in a form of ADC samples) with some noise floor, how do you determine logic levels in it, automatically?

Long version:
Imagine a light telegraph.
An LED is lit for 1, and not lit for 0.
The receiver detects these signals, giving higher voltage when it's lit and lower when it's not.
It also sees the ambient light, that can vary from place to place.
The LED can also be far away or nearby, giving larger or lower voltage changes.

The microcontroller only sees the numbers from it's ADC.

It can be 5-15 without a signal and 100 for 1, or it can be 90-100 for ambient and 120 for 1.
Even worse, the signal can do things like 111111110, or 0000000001.

Question is, how do you determine the logic levels under such conditions?

First thing that comes to mind is a filter like:
amb = amb * 0.98 + in * 0.02;
if (in > amb) return 1;

But this either gets lost on 000000001s if too fast, or consumes first bytes if too slow.

So, how can i do this reliably?

[miguelvp]

Same way as MCUs can distinguish 0s from 1s.
Digital Signal Voltage Levels.

You have a low defined, also a high and in between is undetermined. The levels must have enough buffer to account for noise.

So if your analog signal from the light gives you an output from 0 to 5V then check what TTL does.

If you want to transmit through more noise then you use two signals for doing differential signalling that is less susceptible to noise, because when noise is present it affects both signals so the information can be retrieved in the other side.

[free_electron]

you need to track average light over time.
you will need to use a run length limited code to prevent the average from being pushed to far off due to consecutive ones or zeroes.

[Artlav]

Same way as MCUs can distinguish 0s from 1s.
Digital Signal Voltage Levels.
...
So if your analog signal from the light gives you an output from 0 to 5V then check what TTL does.

The problem is that these levels can be whatever.
Only pattern is that a 1 is higher voltage than a nearby 0.

you will need to use a run length limited code to prevent the average from being pushed to far off due to consecutive ones or zeroes.

Yeah, that's one option - to "DC balance" the code.
However, i wonder if it's possible with an arbitrary one.

[macboy]

Keeping a running average of the kind you proposed in the first post is a good start. You have essentially two signal levels: ambient (which varies over time), and ambient plus signal. You just need to get that "plus signal" part. You will need to be smarter than "if signal>ambient"; you will need some threshold... how much greater than? otherwise noise will ruin you.

Also consider that when sending a data stream, you need some concept of framing. If you just send "00000001", and "0" means LED off, then how do you know where the first "0" bit is? UART takes care of this by always sending a start bit followed by (usually) 8 data bits, followed by a stop bit. In UART (TTL level, not RS232 level), the idle condition is high, a start bit is low, data is 0=low, 1=high, and the stop bit is a high. Each byte is then 10 bits (baud) long, and there can be any amount of time between bytes since the start of each byte is demarked by a framing bit at the start.

Another way to avoid the framing problem is to ensure that both 0 and 1 bits use both on and off states of the link. So a "0" bit might be 1 usec LED on followed by 3 usec off, and a "1" bit is 3 usec LED on followed by 1 usec off. Then, all on the Rx side, you need to detect the edge (when off -> on), wait exactly 2 usec, then sample the signal... it will be off for a 0 bit and on for a 1 bit. Then you wait for "off", and wait for the next off->on transition for the start of the next bit. repeat. Using this, the start of each bit is individually demarked by a off->on transistion, so you have some leeway in timing. For UART, you must by no more than 2% off of nominal or the signal may become errored (total error must be less than 5%, since this accumulates to 50% error in the timing of the 10th bit, meaning that the 10th bit may be sampled at the wrong instant... so each Rx and Tx must be <2.5% error).

Sometimes we want to send a serial stream over noisy links like simple ASK RF (those cheap $1 433 MHz modules on ebay etc.). These modules use a automatic gain on the Rx, so when the link is idle, the signal is boosted until the noise creates signal transitions. So the Rx side UART is always getting noise. For this reason, the microcontroller must be smart. First, the UART will probably throw lots of framing errors, but even when it does receive a byte of data, it is discarded unless it matches some kind of start-of-packet byte or byte sequence. This is transmitted prior to the data in order to "train" the receiver AGC to the signal level (remember it has AGC and is responding to noise until now) and to notify the micro that data is coming. So you might transmit a series of five 0xF0 bytes, with some time in between. The first one or two will maybe be botched by the Rx RF module as it tunes its AGC. Then the next three or so will make it through and the microcontroller will recognize that this is a start of packet (discarding these). Then the real data starts... hopefully followed by a checksum or CRC for validation. This might sound complicated but it is just about the absolute minimum that must be done on a noisy link.

You may need to do something similar, but if you choose your threshold wisely, you won't need to deal with noise/garbage data in the idle condition. You should still consider some kind of start-of-packet and a checksum.

[jeremy]

Assuming you have enough transitions and the signal/nose is fairly consistent during a transmission, you should have a bimodal distribution of voltage samples across some range. So maybe just some sort of peak search on the relative frequency of the ADC samples would solve it.

In other words, take all your ADC samples and draw a histogram.

[pyrohaz]

Is there any way that you could modulate the sender? If you could encode data as two seperate pulse widths, you could high pass the sampled data to get rid of ambient light changes then look for the on vs off time to determine whether the data was a zero or a one.

[hamster_nz]

The classic solution to this problem is to use 8b/10b coding on your data stream. Because a 8b/10b datastream has an equal number of ones and zeros you can then use an AGC on the signal to correct the long-term average level of the signal. You can then compare the data stream against the long-term average level to recover the bits (and the data clock).

[tggzzz]

The classic solution to this problem is to use 8b/10b coding on your data stream.

Or, much more simply, Manchester encoding.

[tggzzz]

Since both the dark/noise level and the peak level are unknown, they cannot be distinguished from the "DC" ambient light. Your signal will therefore have to be "AC", with a lowest frequency that is significantly higher than the maximum rate of change of the ambient light.

This can be achieved either by mechanically chopping the signal source, modulating it in one way or another (e.g. FSK), or by Manchester encoding the data source.

Depending on the range of the ambient light level, you may or may not find it advantangeous to operate the light detector in a logarithmic mode rather than a linear mode.

[Marco]

How about you pick a decision boundary, assign each measured voltage to a logic level, determine the mean for each logic level, whichever decision boundary minimizes the RMS error between the means and the series of measured voltages associated with those means is the likely correct one ignoring pathological cases.

The optimization problem seems simple enough that there might be a closed form solution, but you can always some heuristic method.

[T3sl4co1l]

Do what remote control receivers do: use a narrow band modulation, and detect that.  This excludes the bandwidth of most ambient sources (removing DC and line-frequency components most importantly), and raises SNR enough to work with.

The amplitude of the modulation is also weak, so AGC will be necessary.  Once the signal is reasonably clean and of a predictable amplitude, you can leave the analog domain (or the DSP domain if you prefer) and decode/demodulate the individual bits.

AM, FM, Manchester (a variation of PM as I recall, which is also directly related to FM), 8b/10b, and many other types of modulations and encodings are commonly used, often in combination.  Combined with error correcting codes and spectrum spreading (convolving the signal state with a pseudorandom number sequence), the theoretical bandwidth of a link can be maximized: these are the kinds of things they do for deep space communication, which achieves near dial-up speeds while transmitting a mere 10W or so across the solar system!

Tim

[Artlav]

Ironically, i was using an $1 433MHz module as a reference for encoding.
A start byte, size, address, message, CRC.
Without that, you can't pick the data from the noise.

I tried framing the bytes in 1 start and 0 at end, but that just barely helps to detect half the byte misses.
It did let me add a sync symbol to recover the bytes.

Eventually, i tried 8b/10b encoding that hamster_nz suggested, and that allows to add sync (comma) symbols without interfering with the data.
It also made a nice, DC balanced stream, so a simple average allows logic detection.

What i do is keep two values - maximum and minimum, both smoothed.
The value between them is the threshold.
Each message is prefaced with 3 comma symbols, to let the average adjust, and it seem to work nicely from there.
I guess that can be described as an AGC of some sort.

And it works nicely.
So, thanks all in there...

That, however, concludes the "works nicely" part.
Now, the current problem.
How do you sync up the bits?
That is, sample exactly in the middle of a bit, and not somewhere in between?

I sample at 6 times the clock rate.
Sometimes the bits will align nicely:

Code: [Select]

000000 0
000011 0
111111 1
111111 1
111111 1
111111 1
111100 1
000000 0
000011 0
1111** 1
000000 0
000011 0 ?
111111 1
111111 1
11111 1
111111 1
111110 1
000000 0
00000* 0 -sync-
11111* 1
*00000 0
0000*1 0
111111 1
111111 1
111111 1
111111 1
1111*0 1
000000 0
000000 0 -sync-
0000*1 0
111111 1
111111 1
1111** 1
000000 0
0000*1 0
111111 1
111100 1
0000*1 0
111111 1 ?
1111*0 1
000000 0
000011 0
111111 1
1111*0 1
0000*1 0
111111 1
111111 1
111110 1
000001 0 !
111111 1
111110 1
000001 0
111110 1
000000 0
000001 0
11111* 1
000001 0
111111 1
111111 1 ?

Sometimes, they won't.
And, there is also some drift, since the clocks are not precisely matched.
End result is, the symbols get misaligned, and off-by-oned.

Code: [Select]

000000 0
001111 1
111111 1
111111 1
111111 1
111111 1
110000 0
000000 0
001111 1
110000 0
000000 0
00*111 1
111111 1 ?
111111 1
111111 1
111111 1
110000 0
000000 0 -sync-
00*111 1
11*000 0
000000 0
001111 1
111111 1
111111 1
111111 1
111111 1
110000 0
000000 0 -sync-
000000 0
001111 1
111111 1
111111 1
110000 0
000000 0
001111 1
111111 1
110000 0
001111 1 ?
111111 1
110000 0
000000 0
001111 1
111111 1
110000 0
00*111 1
111111 1
111111 1
11*000 0 !
000111 0

I tried counting the bits in one packet, and if there is more than 2 of the different ones, to nudge the clock a couple bits.
However, that still produce glitches.

Any classic solutions to this problem?

[dannyf]

The answer is quite simple: you just need to think about how you would have approached the problem.

If you were given a series of numbers (say voltage measurements) representing the signal you want to detect ***without anything else***, how would you figure out which one is '1' and which one is '0'?

If you can figure out a way, you can implement. If you cannot, well, you cannot.

[macboy]

I see dannyf replies which I was writing. Read his post first and do the mental exercise he asked. The/an answer should come to you. Otherwise:

The trick to aligning the rx side sampling to the tx side is to wait for a transition and go from there. This is why UART has a "start" bit. The Rx sits and waits for the idle->start transition and syncs up on it. The start bit is not part of the data stream, but part of the necessary framing of the data. If your idle state is equal to a 0, then you need to wait for the 0->1 transition. You could do something like this (assuming 6x oversampling as you mentioned):
1. (Idle) wait for 0-1 transition
2. discard one sample
3. take 3 samples, majority rules (e.g. 1,0,1 gives a 1 bit; the 0 is considered to be noise)
4. discard 3 samples (they are at the end of this bit/start of next one; you want to look at the middle of bits not the transitions)
5. need more bits?, goto 3.
6. process the byte then return to idle (goto 1).

With the above, each bit lasts 6 Rx samples; errors in clock accuracy accumulate with more bits, but it will at least re-sync the Rx on each byte as you wait for the start bit which is always 1 (hint hint). In the "process the byte" part, you will discard the first bit which is always a 1 used for framing.

If bits are not guaranteed to have a transition in them (i.e. a run of 0s or 1s gives no transitions), then the clocks must be very well matched in frequency. See above about why even basic UART needs better than 2% accuracy. If each bit is guaranteed to have a transition at a known place (start/middle), then you can resync the Rx on each bit, and clock accuracy is much less of a concern (e.g. IR remote controls, often timed with ceramic or RC oscillator).  You might also consider leaving a small gap between bytes to ensure that the Rx will re-sync rather than continue to accumulate timing or framing errors.

[Artlav]

Sure, i thought about it and i can implement it.
So far the best result was to scale down to 4 samples per bit, and write the clock change rules for each case there.
Also, a significant improvement came from nudging by a half-bit, not a whole bit.
That way it syncs up within a few bits once the initial commas start to come in, and keeps the occasional misalign fixed without a glitch.

I just wondered if perhaps i'm reinventing the bicycle here, and working on the curve the road should take to fit the square wheel, while there is a classic solution akin to using a round wheel out there already.

[dannyf]

i can implement it.

OK, here is a series:

Code: [Select]

100.8
 113.8
 139.6
 117.2
 130.2
 119.7
 86.6
 100.7
 81.0
 107.4
 117.7
 133.4
 117.5
 140.5
 133.4
 117.9
 88.0
 102.1
 79.7
 89.8
 122.4
 131.5
 119.1
 120.3
 113.4
 120.7
 108.8
 100.3
 100.1
 109.0
 121.2
 132.6
 119.7
 140.4
 109.3
 102.3
 107.0
 102.5
 78.9
 86.7
 100.7

I will even give you the answer - it is generated by this series of logic values:

Code: [Select]

0
0
1
0
1
1
0
1
0
1
1
1
0
1
1
1
0
1
0
0
1
1
0
0
0
1
1
1
1
1
1
1
0
1
0
0
1
1
0
0
0

Can your approach reproduce the logic values?

[rob77]

i can implement it.

OK, here is a series:

Code: [Select]

100.8
 113.8
 139.6
 117.2
 130.2
 119.7
 86.6
 100.7
 81.0
 107.4
 117.7
 133.4
 117.5
 140.5
 133.4
 117.9
 88.0
 102.1
 79.7
 89.8
 122.4
 131.5
 119.1
 120.3
 113.4
 120.7
 108.8
 100.3
 100.1
 109.0
 121.2
 132.6
 119.7
 140.4
 109.3
 102.3
 107.0
 102.5
 78.9
 86.7
 100.7

I will even give you the answer - it is generated by this series of logic values:

Code: [Select]

0
0
1
0
1
1
0
1
0
1
1
1
0
1
1
1
0
1
0
0
1
1
0
0
0
1
1
1
1
1
1
1
0
1
0
0
1
1
0
0
0

Can your approach reproduce the logic values?

i would think of redesigning the hardware which produced that - it's drifting more than a herd of drunken sailors but apart from that i think it's possible to reproduce by tracking a "short-term average" (constantly kept updated) made of few samples only.

[tggzzz]

i would think of redesigning the hardware which produced that - it's drifting more than a herd of drunken sailors but apart from that i think it's possible to reproduce by tracking a "short-term average" (constantly kept updated) made of few samples only.

You are making presumptions about the "noise" with the "signal", which may or may not be valid. Consider 1/f noise, thermal noise, impulsive interference, powerline noise, 100Hz illumination, tempco, etc etc.

You are making presumptions about the signal characteristics, e.g. RZ/NRZ, continuous/intermittent etc.

This is not an easy problem to solve without some form of modulation - because you can base a receiver on being able to lock on to a continuous modulated signal and then detect changes in the modulation.

[nctnico]

Keeping a running average of the kind you proposed in the first post is a good start. You have essentially two signal levels: ambient (which varies over time), and ambient plus signal. You just need to get that "plus signal" part. You will need to be smarter than "if signal>ambient"; you will need some threshold... how much greater than? otherwise noise will ruin you.

I agree. I solve these problems by having a fast filter and a slow filter. The slow filter gives a baseline and the fast filter gets rid of noise. Usually moving average filters do just fine.

[rob77]

i would think of redesigning the hardware which produced that - it's drifting more than a herd of drunken sailors but apart from that i think it's possible to reproduce by tracking a "short-term average" (constantly kept updated) made of few samples only.

You are making presumptions about the "noise" with the "signal", which may or may not be valid. Consider 1/f noise, thermal noise, impulsive interference, powerline noise, 100Hz illumination, tempco, etc etc.

You are making presumptions about the signal characteristics, e.g. RZ/NRZ, continuous/intermittent etc.

This is not an easy problem to solve without some form of modulation - because you can base a receiver on being able to lock on to a continuous modulated signal and then detect changes in the modulation.

i know it's not easy but you must admit that the SNR of that example must be pretty bad (at least my Brain DSP says that ) => redesign of the hardware is needed (e.g. use modulation ) to make it reliable.

[C]

Changing the sample rate costs you some in history.
Think you need to use that sample history to solve the problems.

Add time value to each sample.
Think you have a known start-up sequence and a range for transmitter data rate.
Compute back in time a bunch of time tables for when the start-up sequence bits change based on the range created by transmitter rate.
You now have an back in time array(A).
X axis is the bit pattern of the start-up sequence.
Y axis is the range of transmitter rates.
for each row of Y
if X for that column is 1, Add the values of the samples that happen during the time and count the samples added.
if X for that column is 0, Subtract the values of the samples that happen during the time and count the samples subtracted.
put the four values computed in each row in a 3-d array(B).
X= the four values
Y= same as above array(A)
Z= time based on sample rate.
Add one additional value in the X axis, the difference of 1 - 0 values.
As you add new samples and recompute I think you will see the 1 - 0 difference increase for the actual transmitted rate and then decrease as new samples are added.
With that max difference as start-up sink, you shift to some or all data transmitted is unknown.
Recompute the times in the array based on sync up.
compute forward in time when the next bit should change in time for the Y axis adding a column to array(A).
Now instead of making major changes and just using values from array(B) to decide if a bit is a 0 or a 1, I think I would change the rules above a bit

Change the rules a bit for array(A) so you could have an Unknown value for a bit time.
Then based what data you have, you could add to the X axis of array(A) what you know should happen and leaving the unknown to be computed based on the results of array(C)
add an array(C)
The best guess computing as if the data is a 0 
The best guess computing as if the data is a 1
and also
Idea needs to be cleaned up a bit, hope I got the idea across

C