AVR Manchester Encoding

Hi everyone! I've been gone for an unusually long time and apologize for it. I still have a lot of topics to write about and especially want to talk about my much improved code for the last "Developing a digital synthesizer in C++" topic I posted, about creating waveforms. That will have to be done in the next few weeks, though. I got my first internship at the Institute for Networked and Embedded Systems at the University of Klagenfurt where I'll be working on Non-Intrusive Load Monitoring with Raspberry Pis this July. To prepare for the internship, I'm currently building weather nodes and sending the data over RF to the Raspberry Pi where I want to process and log it and display it on a website locally. The RF is Manchester encoded, which I want to write about in this post as well as post all my code because http://i.lvme.me/t2mt669.jpg, besides wanting to spare you all the trouble I had with it.

I will first talk about and explain Manchester Encoding as well as tell you exactly why you need to Manchester Encode your RF signals. You can skip this part and head straight to the code if you want, or read about Manchester Encoding from my sources:

This really interesting article from Atmel. It gives nice descriptions of common encoding techniques other than ME as well various very nice and efficient decoding techniques for Manchester Encoding. I could make no use of the code examples, though: http://www.nesweb.ch/downloads/doc9164.pdf

This article you should also read that explains the process a bit better: http://www.erg.abdn.ac.uk/~gorry/eg3567/phy-pages/man.html

What is Manchester Encoding?

Manchester Encoding is, to be concise, a very clever and efficient way of encoding an RF signal, especially in noisy environments or with cheap links like the 433 Mhz ones I'm using. To understand why Manchester Encoding is so useful, it might be beneficial to first become familiar with a few other encoding schemes.

The most straightforward and conventional way of encoding a signal is basically sending a HIGH signal for a HIGH bit of your data and a LOW signal for any LOW bit of your data, also known as Non Return to Zero Encoding or WYSIWYG Encoding, as I would call it.

Take the number 91 in decimal, or 01011011 in binary, or 5D in hexadecimal, or 133 in octal or OK enough. Non Return to Zero states quite simply that the signal sent is identical to the data, so 01011011 would be sent like this:
                        ______                         ___________                          ____________
________|                 |________|                               |________|                                |
        0                     1                0                    1            1                     0                   1             1

As you can see, the signal matches the data. So why is this encoding scheme a bad idea? First of all, the data rate may pose an obstacle. For Non Return To Zero encoding the data rate must be known and maintained stably throughout the entire signal, otherwise certain edges might not be recorded. More importantly however, Non Return To Zero makes a signal like this possible:

_____________________________________________________
       0                0                0                0                0                0                0                0

What? A straight line? Where did my data go? What you have here, in fact, is this byte: 0b00000000. There is no way possible to determine where any bit starts or ends and more importantly, many cheap RF links will just loose the signal or receive enough noise to annihilate your data completely and absolutely.

Manchester Encoding addresses and solves these problems. It states that for any bit there will be transition at the mid-bit. A HIGH data bit is signalized by a transition from LOW to HIGH (01) and a LOW data bit is indicated by a transition from HIGH to LOW (10) at the mid-bit.

HIGH data bit:
            ____
____|

LOW data bit:
____
           |____

This ensures that the signal will never be a constant like I demonstrated above and therefore the receiver can keep its gain adjusted to the signal. It takes bit more effort to decode the signal but you are also more sure to receive valid data. Plus, Manchester Encoding makes syncing very easy due to the mid-bit transition.

The data I showed you above, encoded with Non Return To Zero Encoding, looks like this with Manchester Encoding (01011011):

____                        ______                        ___              ______                         ___              ___
          |________|               |________|        |____|                |________|        |____|        |
         0         ^         1        ^      0        ^         1        ^          1       ^       0          ^         1             ^     1       ^    
                Edge            Edge          Edge             Edge            Edge            Edge                Edge         End    

Decoding techniques

There are a few different ways to decode such a Manchester Signal which are all very well described in the Atmel article I supplied above. They can be narrowed down to two different methods. The first uses timing where you basically record the time between each transition and process the input accordingly. The second is more the DSP approach where one oversamples and captures/stores the data stream and processes it after. Having worked and still working with sampling extensively for my digital synthesizer in C++ project, I chose the sampling technique. I therefore cannot tell you too much about the timing technique, though the Arduino Manchester Library uses Timing based Manchester Decoding. Check out the library here: https://github.com/mchr3k/arduino-libs-manchester

To the code and beyond: Basic considerations

First, we need to determine a good data rate. I chose 2.5 Khz, as it's not too fast for the RF links I'm using but also not too slow that the links would loose the connection or receive too much noise in between the pulses. So, 2500 Hz gives 1/2500 = 0.0004 seconds or times 10^6, 400 µs. Therefore, each data pulse, either 10 or 01, will have a duration of 400 microseconds and the mid bit transition will be around about at 200µs.

Next we need to determine a sampling rate or more conveniently we'll just look for a good number of samples to take for each bit. At first, I had eight samples per data pulse, so I would just set or clear a bit of a "sampling-byte" for every sample and then interpret this sampling-byte after. However, eight bits turned out to allow too little tolerance for the signal.

Due to the cheap RF links and the fact that there is no such thing as an ideal signal, a little tolerance has to be given to the signal as long as it's constant, meaning that even if the signal isn't always 400µs but 405µs for the one period and 395µs for the next or something similar to that, it won't shift the period dramatically over time. If the signal is really 395µs for every pulse, you have a problem, since the next time the signal will end at 790µs instead of at 800µs and then at  1.185µs instead of 1200µs. After a while the period will have shifted enough to create a bit error and ruin your signal.

So, to leave more room for tolerance, I then reduced the sampling to four samples per bit. This currently works great. If one doesn't worry too much about noise one could even go down to 2 samples per bit but because 4 work for me as of now, I kept the extra resolution. The great thing about 4 samples per data pulse is that now instead of using a sampling-byte, I'm using a 32-bit number to store my samples. This means that every time this 32-bit number is filled, I have sampled an entire data byte and can interpret and store it right away. Four samples for every 400µs-lasting data bit means that the duration between samples is 100µs.

It's important to note that you will want to offset your sampling by about one half the duration between samples. For example, instead of taking a sample at 0µs, 100µs, 200µs, and 300µs, which would mean that you're sampling right at the bit edges, you'll want to sample at 50µ, 150µs, 250µs and 350µs. With the mid-bit transition being ca. around 200µs of every period, this leaves a nice cushion of 50µs before a sampling-error occurs.

Next up, I want to mention the two things you'll want to transmit besides your data for every transmission: a preamble and a checksum.

A preamble is basically a pre-fixed data stream that lets you know when the actual data starts.  For me, this preamble consists of 6 low manchester-encoded signals, so 6 transitions from HIGH to LOW, and 2 high signals, from LOW to HIGH, to signalise the start of the data.

A checksum is a small piece of data that represents some sort of encoded or compressed form of the data you send and that is attached to the actual data stream. To ensure that the received data is correct, one would use the same algorithm to compute the checksum for the data on the RX side and see if it matches the checksum sent at the end of the transmission. A simpler error-detection technique than a checksum is the so-called parity bit, which is a single bit attached to the data which is SET if the number of bytes transmitted is odd and CLEARED if the number of bits sent is even. You can invent your own checksum algorithm as you please, like adding all the bytes of the data together and appending the modulus of the sum with a pre-defined value to the data or something like that. However, there are a few more complex and more widely-used checksum algorithms. The most popular one's I came across were Adler's checksum, some form of Hamming code and Fletcher's checksum. I'm using the latter, this part of the Wikipedia article convinced me.

The last consideration you might want to make is the connection time. What if your receiver is locked in the syncing loop and waits for the preamble, but never gets it. Will you let your micro controller fall victim to an endless loop? No! No of course we won't! Freedom to the CPUs! Freedom to the CPUs! Therefore, what we need is a sort of watchdog timer that times out the connection pipeline after a certain time, say 10 seconds.

To the code and beyond: the code and actually not that much beyond

I think I'll just go ahead and direct you to the repository I created on GitHub: https://github.com/goldsborough/mavrchester 

There's not much use explaining the whole code, it's well commented and I try to use variable names that make sense when you read the code. I'm using two Attiny85s @8Mhz so you'll probably want to change around stuff for you if you don't have the same setup. At the moment the code sends "Hello World!" and lights an LED on the RX side if it was received and the checksum is correct.

A few things I want to mention, though:

• The code is not perfect, the preamble seems to take very long for me to work, which is why you'll see the code sending 75 bytes of only 10s (240 milliseconds...) but I don't know whether that's hardware or software related. The transmission works pretty well, I get an error like 5% of the time but again that might be hardware-related. In any case if it doesn't work well for you, take what you can from the code or the architecture of it and try to change things. I am not publishing this code as a library, it's my own rough code that I'm sharing. 

• Notice that the Transmission uses Timers to delay the half-bit-time. This is absolutely vital! I tried way too long to find a good delay to use with the delays from <util/delay.h> but this way, it doesn't matter at all how much time you spend outside of the sendByte() function because TCNT0 goes on anyway. However, make sure you keep that last while loop in the sendData() function or else the last bit won't send properly (as commented).

• For the receiving end, make sure that you don't use the Clear Timer on Compare Match feature. It might seem sense to let the much more precise hardware reset the timer every time the sampling ISR is called, however, it is not the ISR that has to be called regularly, but the sampling! That's why the TCNT0 is reset after the sample-taking. 

Have fun and comment if you have problems or anything.