Error correcting codes [QuietCasting]

[pavlos]

Hello all

I have been following this (great) community for a while. I am very much interested in low power, long range communication which is how I came across the Moteino in the first place.  3 young kids and a demanding job don't allow for much tinkering time so for now I am enjoying tinkering by proxy via  the various projects and posts happening in this community.  Some of the stuff I have been thinking about relating to  long range low power communications may be of interest to the moteino community so I gathered some material here:

   https://github.com/pavlos-christoforou/quietcasting

In particular I think a good but simple error correcting code will provide a great enhancement to the robustness of the communication layer of the Moteino. I believe the design detailed under lib/ecc.py offers a good performance/resource usage compromise and it is probably efficient enough to run well on the Moteino. Unfortunately I have only coded python versions for now.

Keep well and have fun with Moteino!

Cheers

Pavlos

[Felix]

Pavlos, thanks for sharing this. What's your take on the default hardware CRC mechanism?

[pavlos]

The default CRC mechanism is excellent. It will point out whether the received  message was corrupted or not (with some probability p) and being calculated on hardware it is very efficient. If, for some particular use, only a CRC is needed then my suggestions are not relevant. However if an application requires not only error detection but also error correction then one needs more powerful codes.  I expect the most common use case would be applications that require increased range. Here is an example:

Say for instance one has 2 Moteinos separated by say 2 floors and at that range one gets 1 corrupted packet per 100.   That's easily handled by the current ACK mechanism. Now suppose we move the Moteinos further apart (say 4 floors) and we are now getting 60-70 corrupted packets per 100. No ACK mechanism will help in such situation as each retransmission has again a high probability of being corrupted (not to mention that the ACK requests themselves are highly likely to be corrupted too).  Also if one has a number of Moteinos attempting to communicate at such range the number of ACK requests will flood the whole network and make it unusable. A state of the art error correcting code (like the ones used in cell phones) would have no trouble handling such errors rates and an application of such a code will probably result in 100% correct packet reception without any ACKs required. Such state of the art codes are however beyond the Moteino's computational capabilities (I think so at least; I am only an amateur in this field so I may very well be wrong). I did a some searches on the web a few months back looking for error correcting codes that run on such CPUs as the Moteino's but all I found was someone who has implemented the Viterbi error correcting code on a more powerful AVR CPU. I also expect/hope sooner or later most RF module manufacturers will include such error correcting codes in hardware.

In short I would like to see whether I can get 2 Moteinos to communicate over a few Km line of sight (without specialized antennae etc).

Cheers

[Felix]

Thanks for explaining, that makes more sense now. I am interested to see what you can come up with.
Others were able to achieve much longer ranges by tweaking the bitrate and bandwidth of the transceiver and also using higher performance antennas. There are a few posts in the forum related to this, just search for "range" or "bitrate", here's a few:

http://lowpowerlab.com/forum/index.php/topic,222.msg955.html
http://lowpowerlab.com/forum/index.php/topic,181.msg700.html
http://lowpowerlab.com/forum/index.php/topic,114.msg613.html
http://lowpowerlab.com/forum/index.php/topic,157.msg578.html
http://lowpowerlab.com/forum/index.php/topic,142.msg504.html
http://lowpowerlab.com/forum/index.php/topic,112.msg288.html

[pavlos]

Thanks Felix for collecting and providing these links. Yes improving the RF layer (antena, receiver sensitivity, modulation etc) is the other dimension one can work with towards improving range and I note that there are a few very capable individuals (and in possession of appropriate instrumentation!)  already exploring this direction, Will keep you updated once I get a chance to actually try some of these methods.

Cheers 

[jbeale]

It's an interesting problem from an algorithms point of view, I'll look forward to see what is possible. It may be more useful for cases of interference rather than simply low signal level, as with the Moteino I think the dropoff from 95% or more packets getting through to nearly no packets getting through, is pretty quick in terms of the signal level, at least in my testing. Although the dropoff may be more gradual with longer packet length; I was looking at very short packets.

[Felix]

jbeale is right - I have seen the same behavior in general. Once the signal drops it drops almost 100% as far as I can tell, even with longer packets. I believe it's more worth investing in a mesh capability which will add far greater redundancy. I was able to verify this in my own mesh experiments. Plus, the cost of a middle man Moteino is almost negligent when you're looking to get 2X the range at the cost of a few dozen milliseconds forwarding/ACKing overhead. And also at the expense of more complexity.

[pavlos]

Thanks Felix and jbeale. Given what you have observed the likely scenario is that an error correcting code will make little or no difference or (the unlikely one) a huge difference. I expect no middle ground.
Agreed on the advantages of a  mesh or at least a few repeater moteinos and the associated cost is very low so all is good.

[Felix]

Didn't mean my comments to sound discouraging or anything like that. I think algorithms have their advantage and place in RF applications. It would be interesting to see if an algorithm like the one you proposed would bring a significant advantage. I would imagine you'd have to tweak the library to disable CRC at the very least so all received packages would be passed through.

[WhiteHare]

Thanks Felix for collecting and providing these links. Yes improving the RF layer (antena, receiver sensitivity, modulation etc) is the other dimension one can work with towards improving range and I note that there are a few very capable individuals (and in possession of appropriate instrumentation!)  already exploring this direction, Will keep you updated once I get a chance to actually try some of these methods.

Cheers

Any updates?