Implement error detection / correction

rmeister commented 8 years ago

This would be great for increased transmission quality, especially for the browser-to-browser use case.

https://en.wikipedia.org/wiki/Error_detection_and_correction For both, detection and correction, it always needs sending addtional bits. The question is where to place the redundant bits. Currently, SoftModem sends data like UART but without parity bit: one frame is one byte.

Some possible options:

Split bytes up into multiple frames, with added redundancy information in every frame. E.g. 5 bits for data, 3 bits for correction (numbers are arbitrary).
Append data for detection/correction after the actual data. This also requires some data length encoding or other methods to mark the end of actual data and the begin of correction codes.

Resource for CRC hashes on the Arduino: http://excamera.com/sphinx/article-crc.html

Another good article about error detection and correction: https://hackaday.com/2016/02/10/error-detection-and-correction-reed-solomon-convolution-and-trellis-diagrams/#more-189519

Detection vs. Correction: I'd say in this case correction is the better option, as detection would require resending, which is not provided by librarys like Firmata.

dwblair commented 8 years ago

Big fan of WebJack! Been playing with it a lot, so many interesting projects to be done with it!

One basic use-case I have is simply receiving sensor data in the browser from an Arduino. I've been playing around with that, and it seems that (with my shaky circuit setup, which can be improved), I often find a lot of '3's sent by the Arduino are parsed as '7's by Webjack.

One very simple (not so efficient) form of error correction I just came upon is a type of Forward Error Correction (FEC), in which one simply transmits each bit 3 times, and then the receiver does a 'majority vote' on the bits received. I'm thinking of implementing this in a really crude way in WebJack, but I'd be curious as to how you think it might be best implemented? The nice thing about this (for my application at least) is that I don't need to worry about two-way communication, and it seems quite simple conceptually.

In searching for error correction techniques with modems, I happened across this project, which looks like it has implemented some acknowlege / receive stuff, and perhaps some error correction ... maybe an inspiration?

https://cho45.stfuawsc.com/WebAudio-Modem/FSK/modem.html https://github.com/cho45/WebAudio-Modem/tree/master/FSK

Anyway, thanks for all your great work!

Cheers, Don

jywarren commented 8 years ago

Don - found this library, not sure if it's done, and we'd want to add some tests of some kind: https://github.com/sergiopantoja/Hamming.js/

Explanation of Hamming codes which seems pretty cool: https://en.wikipedia.org/wiki/Hamming_code

It doesn't look complete, though -- it returns an object which has a .generate(input) method, but no .parse(input) or equivalent, and there's a missing .check() method that's only been stubbed out.

jywarren commented 8 years ago

Other implementations of Hamming and something called Manchester encoding: https://gist.github.com/joeladdison/9717310

Also a very short example here: https://gist.github.com/ivanpepelko/b4c290f4645865f8fec581016a96420e

But Hamming[7,4] codes seem to self-correct 1-bit errors, which is cool: https://en.wikipedia.org/wiki/Hamming(7,4)

jywarren commented 8 years ago

My thought on the webjack integration would be:

Webjack accepts a constructor option in the passed profile object, such as:

var profile = WebJack.Profiles.SoftModem;
profile.sendFilter = function(output) {
  return output; // this is the default -- no error correction on send
}
profile.receiveFilter = function(input) {
  return input; // this is the default -- only raw data expected
}
profile.sendFilter = function(input) {
  return hamming.generate(input); // or, override it like this
}
var connection = new WebJack.Connection(profile);

dwblair commented 8 years ago

Cool! Yes, seems that Hamming not only detects, but can correct errors!

The downside of Hamming (if I'm reading things right) is that it would, in fact, require interventions at the "bit" level of communication -- e.g. Hamming 7,4 requires adding 3 additional "parity" bits for every 4 bits you send. I think this would require a rewrite of how SoftModem and WebJack work.

jywarren commented 8 years ago

But couldn't we transmit the bits as strings or something? Just jump a level of abstraction? Or perhaps there are binary encoders we could use to send specific bit sequences more efficiently.

On Sep 25, 2016 6:20 PM, "dwblair" notifications@github.com wrote:

Cool! Yes, seems that Hamming not only detects, but can correct errors!

The downside of Hamming (if I'm reading things right) is that it would, in fact, require interventions at the "bit" level of communication -- e.g. Hamming 7,4 requires adding 3 additional "parity" bits for every 4 bits you send. I think this would require a rewrite of how SoftModem and WebJack work.

— You are receiving this because you commented.

Reply to this email directly, view it on GitHub https://github.com/publiclab/webjack/issues/32#issuecomment-249450350, or mute the thread https://github.com/notifications/unsubscribe-auth/AABfJw3jIE-UhBVs4ompV_hVcYuPqV55ks5qtvOagaJpZM4JuJw7 .

dwblair commented 8 years ago

I think we could do that -- e.g., for Hamming 7,4 (which requires 3 additional 'parity' bits for every 4 bits of data you want to send), if you want to send an ascii "8", you first break it down into bits: (in this case, "00111000") then break it down into groups of 4 bits (e.g. "0011", "1000"), and determine the proper additional 3 parity bits to send along with each of those 4 bits ...

so then, instead of sending "8", or just its binary representation "00111000", you send the Hamming 7,4 representation "0011abc1000def" (where a,b,c,d,e,f are the appropriate Hamming parity bits (each of them a "0" or a "1")), and then reconstruct on the other side using the appropriate inverse Hamming method, yeah?

I think the downside of abstracting things at this level might be (if I'm doing the arithmetic right) that for every character you want to send across the line (e.g. "8"), you now would need to send 14 characters ("00110101000101", or whatever Hamming 7,4 would generate). Currently, I'm able to send data to WebJack about every 200 ms -- so something like 5 values per second, which is fairly snappy; shorter delays than 200 ms, and I start to see a lot of errors. Naively, I think this high-level Hamming (HLH?) approach would bring that delay up to about 14*200 ms -- i.e., or once every 3 seconds (maybe a little faster b/c of the error-correction due to Hamming, but not much -- if I understand Hamming 7,4 right, I think if more than 2 out of every 7 bits are flipped, Hamming 7,4 is no longer effective.) The upside would be that we'd be fairly sure we got every data point; once every 3 seconds is certainly fast enough for some applications.

For the sorts of things I'm thinking of doing, though -- playing 'live' with thermistors and loadcells and photocells and watching their response in the browser -- maybe even sending chat messages from browser to browser -- 1 character per 3 seconds a bit too sluggish. If I were going to implement Hamming, I think we'd want to do it at the bit level, to make it faster than this. Which might be a good project to take up! It would certainly make SoftModem and WebJack more robust to have error-correction at the bit level.

At this point, for a quick-and-dirty (and, apparently, commonly employed) solution, I'm headed down the route of using CRC codes, which are widely used in radio and in internet protocols. They're relatively simple, and they only add a fixed length checksum to the transmission of any arbitrary-length string -- in the case of CRC8, a single byte. It's only an "error detection", not an "error correction", code, but I was anyway finding that the error rates were fairly low; and for most of the things I'm interested in, a few dropped data points don't matter too much; I'd rather have a snappy response time.

Also: if there's two-way communication, and one wants to make sure not to lose any packets, the typical thing that's done is to just ask for a re-send if the checksum doesn't match. That's quite with the current WebJack setup, I think.

I hunted / fiddled around a bunch this morning, and now have compatible javascript and arduino functions ( "CRC8()") for generating a CRC8 checksum, which is simply a single byte.:

https://github.com/dwblair/crc8-avr-js

So, my plan at this point is: on the arduino side, use CRC8() to generate a checksum for a given message, and use SoftModem to send something like "message;checksum" to the browser ...

... then, on the browser side, read in "message%checksum", leverage the "%" character (or whatever would make for a good separating character) to split message and checksum apart; use CRC8() on the browser side to generate the checksum for message independently, and compare that checksum to the one you received from the Arduino. If they differ, then you ask for a re-send (or, if you don't care too much about every data point, you just don't keep that message ... but maybe you tally up an "error counter" so you have a sense for how bad the connection is) ...

dwblair commented 8 years ago

Implemented CRC8!

https://youtu.be/7RDXzkhKuZY

Sorry the video is blurry ... but basically it shows:

data is being sent from the arduino in the format "message%checksum"
it is received and parsed into "message" and "checksum_arduino"
the browser calculates its own "checksum_browser" based on "message"
browser then compares checksum_arduino and checksum_browser
if they are the same, it's a match
if they're not the same, there's some noise in the system

you can see a "noise" event detected at https://youtu.be/7RDXzkhKuZY?t=22

i'll clean up the code and see if i can find a way to do a PR that doesn't break things now

i used it for graphing thermistor data, and it was super smooth -- no glitches!

I tried hard resetting my repo as before to get rid of merge conflicts, but there still seems to be a conflict with the README even after I do that ... so still learning :)

Meanwhile, for what it's worth -- the code is still messy, but i pulled out the new example folders into a separate repo here: https://github.com/dwblair/webjack-crc8

I'll be refactoring in the next day or so and trying to figure out how to do a nice PR against the main repo ...

jywarren commented 8 years ago

Hi, Don -- fantastic! You can follow these steps:

git checkout -b backup -- just make a backup first
git checkout master -- go back to master
git pull https://github.com/publiclab/webjack.git master -- get the latest master from publiclab repo
git reset --hard d21fcd0 -- rewind to d21fcd0 -- the checksum/id of the current publiclab master
git checkout backup -- go back to your backup branch
git checkout -b crc8 -- copy it into a new feature branch just for the error correction stuff
git diff d21fcd0 HEAD -- see all your changes compared to latest publiclab master
git checkout d21fcd0 path/to/file -- use this to remove files that are not specific to your crc8 feature (they're saved in the 'backup' branch, so no worries)
git commit -m "selected only error correction stuff" -- I think this extra commit is needed but not 100% sure
git rebase -i master -- (optional) this opens a file where you can mark your commits with an "s" to squash them into one commit, or "f" to do the same without saving each commit message, then write the file
git push origin crc8 -- push up the new, single-commit feature branch to your own remote feature branch
go to https://github.com/publiclab/webjack and see "open Pull Request" in yellow notice, open it
close other PRs that aren't needed
repeat this all for your gauge and dial changes (you could submit those together in one PR) -- based on the saved copy in your "backup" branch

Does this make sense? I hope I didn't forget anything!

jywarren commented 8 years ago

Ah -- the README conflict is because I merged in a change to the README from Richard -- so you need to resolve that conflict before switching back to master, in step 2 (or maybe 1). He fixed the spacing in one of the tables.

dwblair commented 8 years ago

Wow, thank you for outlining all these steps! I'm going to dig in and see if I can get my process back on track ... cool!

On Mon, Sep 26, 2016 at 9:35 AM, Jeffrey Warren notifications@github.com wrote:

Hi, Don -- fantastic! You can follow these steps:

git checkout -b backup -- just make a backup first

git checkout master -- go back to master

git pull https://github.com/publiclab/webjack.git master -- get the latest master from publiclab repo

git reset --hard d21fcd0 -- rewind to d21fcd0 https://github.com/publiclab/webjack/commit/d21fcd0c544b8fb2e804d18e3b99682fe387e35a -- the checksum/id of the current publiclab master

git checkout backup -- go back to your backup branch

git checkout -b crc8 -- copy it into a new feature branch just for the error correction stuff

git diff d21fcd0 HEAD -- see all your changes compared to latest publiclab master

git checkout d21fcd0 path/to/file -- use this to remove files that are not specific to your crc8 feature (they're saved in the 'backup' branch, so no worries)

git commit -m "selected only error correction stuff" -- I think this extra commit is needed but not 100% sure

git rebase -i master -- (optional) this opens a file where you can mark your commits with an "s" to squash them into one commit, or "f" to do the same without saving each commit message, then write the file

git push origin crc8 -- push up the new, single-commit feature branch to your own remote feature branch

go to https://github.com/publiclab/webjack and see "open Pull Request" in yellow notice, open it

close other PRs that aren't needed

repeat this all for your gauge and dial changes (you could submit those together in one PR) -- based on the saved copy in your "backup" branch

Does this make sense? I hope I didn't forget anything!

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/publiclab/webjack/issues/32#issuecomment-249571082, or mute the thread https://github.com/notifications/unsubscribe-auth/AAnDEAmy0lupMuZqgnHEilHyikkNtvwBks5qt8o9gaJpZM4JuJw7 .

publiclab / webjack

Implement error detection / correction #32