Error Detection and Correction: Reed-Solomon, Convolution and Trellis Diagrams

Transferring data without error when there is a lot of background noise is a challenge. Dr. Claude E. Shannon in 1948 provided guidance with his theory addressing the capacity of a communications channel in the presence of noise. His work quickly spread beyond communications into other fields. Even other aspects of computer use were impacted. An example is the transfer of data from a storage medium, like a hard drive or CD-ROM. These media and their sensors are not 100% reliable so errors occur. Just as Shannon’s work defines communication channel capacity it defines the transfer rate from a media surface to the read head.

Shannon told us how much could be passed through a channel but didn’t say how. Since 1948 a lot of research effort went into accurately detecting errors and correcting them. Error correction codes (ECC) add extra bits to messages, but their cost pays off in their ability to work around errors. For instance, without ECC the two Voyager spacecraft, now leaving our solar system, would be unable to phone home with the information they’ve gathered because noise would overwhelm their signals. Typically in hardware, like memory, error correction is referred to as ECC. In communications, the term forward error correction (FEC) is used.

Robust communication, or data transfer, is a combination of fancy software and tricky signal processing. I’m going to focus on the software side in this article. You may find some of these techniques useful in communicating data among your devices. While I’ll be using the term communications keep in mind this is applicable to transferring data in general.

Continue reading “Error Detection and Correction: Reed-Solomon, Convolution and Trellis Diagrams”

Turning A Teensy Into A U2F Key

Last month, GitHub users were able to buy a special edition Universal 2nd Factor (U2F) security key for just five bucks. [Yohanes] bought two, but wondered if he could bring U2F to other microcontrolled devices. he ended up building a U2F key with a Teensy LC, and in the process brought U2F to the unwashed masses.

Universal 2nd Factor is exactly what it says on the tin: it doesn’t replace your password, but it does provide a little bit of extra verification to prove that the person logging into an account is indeed the person that should. Currently, Google (through Gmail and Google Drive), Github, Dropbox, and even WordPress (through a plugin) support U2F devices, so a tiny USB key that’s able to provide U2F is a very useful device.

After digging into the U2F specification [Yohanes] found the Teensy LC would be a perfect platform for experimentation. A U2F device is just a USB HID device, which the Teensy handles in spades. A handy library takes on ECC for both AVR and ARM platforms and [Yohanes’] finished U2F implementation is able to turn the Teensy LC into something GitHub was selling for $5.

It should be noted that doing anything related to security by yourself, with your own code is dumb and should not be considered secure. Additionally, [Yohanes] didn’t want to solder a button to his Teensy LC, so he implemented everything without a button press, which is also insecure. The ‘key handle’ is just XOR encryption with a fixed key, which is also insecure. Despite this, it’s still an interesting project and we’re happy [Yohanes] shared it with us.

Wiimote finger tracking music controller

The Evolution Control Committee has been doing live mashup performances for many years and recently upgraded their hardware. Inspired by [Johnny Lee]’s Wiimote whiteboard, they built a rear projection display they could use during performances. It displays a dense collection of samples in Ableton Live. On each of the performer’s hands is an IR LED mounted to a thimble. By touching the thumb to the forefinger, the LED turns on. Two Wiimotes watch for these IR flashes to trigger mouse clicks. [TradeMark G] found the Ableton display too complex to navigate quickly and accurately with a mouse; this new display make things much easier and enjoyable.

[via Laughing Squid]

PS3 ECC algorithm reversed

The ECC is the protection that keeps the PS3 from booting with a custom flashed rom. These folks managed to reverse the code. This means that they can now generate custom ones to allow the rom to boot.  They haven’t gotten very far with that side of it yet, but they did manage to rescue a broken PS3 with it.  They had one that had a bad flash, they were able to re write the code in it and it booted right up.

[thanks, vorgravy]