I've started work on a prototype USB RF Transceiver dongle using the MRF49XA and an Atmel AT90USB series micro controller. Along with the change in hardware, I've made a change in the packet format as well. The old packet format was based on the MRF49XA sample code from Microchip, ported to the AVR.
[caption id="attachment_1502" align="aligncenter" width="540"]!(http://alternet.us.com/wp- content/uploads/2011/11/DSC_0147.jpg) Prototype build using AT90USBKey[/caption]
The source code (still early) is available on GitHub. For now, it's designed for use with the Atmel AT90USBKey (user's guide). The schematic I used for connecting the USBKey to the transceiver is essentially a direct mapping of the attached schematic (below). The only real difference is that the Atmel chip is slightly different. Notice in the above image that almost all of the interface wires go to port B on the AVR. This proved rather convenient as it was easy to construct the wiring harness using rainbow ribbon cable, which I highly recommend. A little heat shrink tubing helped keep the wires from wiggling and breaking. There are complaints about the pin spacing used for these ports, because you can't install standard .1″ headers. That is a bit of a disappointment, but it does work quite well with direct soldered wire. The only "stray" wire is for the interrupt request, which is installed on the wrong port in the image. On the schematic, it's connected to pin C7, but for the USBKey it should be on pin E4.
It cannot be said how nice it is to ditch the dedicated programmer for the built-in AT90USB boot loader. Whenever you need to rev your code, just reset the controller while holding down the HWB button. You don't even need to unplug the USB connector. The USB system will "re-enumerate" the device as a "DFU Programmer," and you can simply download the program. Hit the reset button again and you're back up & running!
As I often do, I've hacked together a simple frame to keep the prototype from self-destructing while I develop it on the couch. I just took a scrap piece of acrylic and drilled some holes for the mounting holes on the USBKey. To mount the transceiver I used velcro adhesive tape.
A bizarre, but kinda cool, feature of the USBKey is that it comes shipped with firmware that allows it to be a USB device and host. If you plug it into your computer it will appear as a USB flash drive, containing all the documentation and software, and a mouse using the little joystick. If you power it using the 9v battery clip it behaves like a computer; you can plug in a mouse and make the LEDs blink by moving it around. It also includes a few extra sensors that you can use for playing around with USB, such as a thermometer.
The software part of the project centers around the LUFA USB Framework written by Dean Camera (see the excellent tutorial by Christoph Redecker). LUFA is licensed using the relatively permissive MIT license. I've licensed my code under the GPL version 2, which I think I can do given the licensing of LUFA.
I had great aspirations of adding forward error correction to the transceiver. When I used it before, I had significant bit errors in the communication path. I had hoped that I could eliminate these while not increasing the transmit power. I started with Phil Karn's encode_rs_8 and decode_rs_8 functions. These functions are great, and really easy to use. The problem, though, is that they use a lot of RAM. The functions are what's called a fixed-length (255, 223) Reed-Solomon code. What this means is that the whole "code word" is 255 bytes (or symbols), and 255-223=32 bytes of it are parity. You can use them with less than the full code word size, by filling unused data with zeros, but the math still requires several arrays that are 255 bytes long. This was a non- starter on the AT90USB162, which has 512 bytes of ram total. Therefore, I had to abandon dreams of FEC; at least using these functions. I decided that the best course of action was to define as basic a packet format as possible that would allow any form of data as its payload.
Protocol and Packet format
I think the best way to start with the packet format is to think about the minimum amount of data, allowing for extended fields later. To this end, the vital fields are length and type. The type field can be used to index into an array of packet sub-types, allowing for specialization later. The length field contains the length of the payload data in bytes. I settled on 64 byte payloads due to a limitation of the RAM size on AVRs.
Offset Length Description 0 1 Payload Length 1 1 Packet type (basic byte array is 0xBD) 2 64 Payload data (may be truncated)
It seems to me that you can count on at least 512 byte memories, therefore to ensure that it's applicable on a wide range of devices we should assume this value. I experimented with 96 byte packets, but even though the compiler claimed that only 90% of the memory was used it didn't include the heap or the stack. I didn't use any dynamic memory allocation, so the heap should be empty, but you should never assume that the stack is a trivial amount of memory. Just in case you don't know what these things are, there are basically 3 types of RAM used in a C program. The first is the memory that is defined by the compiler (I'm simplifying a little). This is every time you have a static variable or global. The second is the stack. This memory grows every time you call a function. All those variables that you use (other than static ones) in the called functions exist on the stack. Finally, the heap is where all your memory that you "malloc" lives. In general, the stack and heap are on opposite "sides" of the available memory. They tend to grow toward the center. When you're out of memory they can overwrite each other. This is extremely unlikely to happen in a computer (especially with 64 bit computers, where it may never happen) but on a micro controller, it's a constant problem. Bringing it back to the issue at hand, on a 512 byte AVR, it's not possible to use 96 byte packets the way I've implemented it.
Forward Error Correction
As Forward Error Correction (the ability to recover from errors in the communication channel without retransmission) is a valuable feature in radio communication, especially when used for telemetry, I spent some time evaluating the options. I've produced a table of a few coding schemes from the major classes and their pros and cons in an embedded environment. Additional information about turbo codes is available in an IEEE Spectrum article, and they produced a lovely graphic of the encoder/decoder. Also, if you're using the AT90USBKey, there is enough RAM for an implementation of the Reed Solomon code by Phil Karn. His code (use encode_rs_8.c and encode_rs_8.h) is written in C in a portable way, so that it compiles and successfully runs on the AVR.
Type Pros Cons Hamming Code Simple to code and decode, Low performance relative very low memory requirements to more recent and advanced codes Convolution code More complex than hamming, Decoding process more but space and code efficient. compute intensive Better performance than hamming Reed-solomon code Very good code, especially when Very memory intensive. used with a convolution code. At least a few kB of RAM Used in the voyager missions for a 255 byte code and harddrives. Turbo codes State of the art code, very While encoding using turbo nearly "perfect" according to codes appears to be shannon information theory. relatively simple, decoding is RAM and cpu intensive.
In this application, there is some hope for hamming code forward error correction. The most common hamming code that you'll see if you search for "hamming codes" is the 7,4 variant, which is 4 data bits and 3 parity bits. While it would fit into an 8 bit word, there is a wasted bit in every code word. The 7,4 code is able to correct single bit errors and detect double bit errors, but I don't think its able to distinguish between double bit errors and single bit errors. It will happily, and incorrectly, interpret a double bit error as a single bit error. This will likely flip an otherwise correct bit, making a new tripple-bit error! There is a 8,4 code, which is nice because it simply doubles the size of the data, and doesn't waste any bits. Also, the 8,4 code is able to detect double bit errors as distinct from single bit errors. You can use this information to mark "erasures," bytes that you aren't sure what they're supposed to be. Sometimes it can be useful to know what you don't know.
The structure of wireless channel errors has been widely studied in the literature. It can be useful to think of bit errors occurring within a symbol in terms of their local frequency. By this I mean: how clustered are bit- errors? It is common for errors to occur in bursts, with relatively few errors between them. Therefore, if there is a simple way to interleave many symbols within the bit stream, it may be possible to recover from more bit errors. Effectively, you would be increasing the number of code words that have an error, but reducing the number of errors in a codeword on average.
[caption id="attachment_1536" align="aligncenter" width="540"]!(http://alternet.us.com/wp- content/uploads/2011/11/interleave.png) Different strategies for interleaving codewords[/caption]
I haven't decided which strategy for interleaving codewords in the transceiver. The simplest, in my opinion, is to split each codeword in two and place the second piece of each, in order, at the end of the packet. Each half of the code word will be at the maximum distance from its pair. Another idea is to interleave them bit-by-bit.
From the perspective of someone who has to implement this, I'm leaning toward the simple method of splitting code words and sticking them on either end of the packet. All you have to do is make the packet twice as large (or the data half as large), and when a byte comes in convert it to a codeword (using a lookup table) and place its 4 bit half-words at indexes i and i+length (assuming half bit type in the array, it 's a little more complicated with an 8-bit data type). Or, you could do it all at once, just before the packet is transmitted. I think it's even possible to do it "on the fly" without using any additional memory needs (for transmit only). I'm not likely to go that route, but it's an option.
The bit-wise interleaving is much more robust against burst errors, but I don't really want to code it up, honestly. We'll see what I get around to over break.
Hamming Code implementation
I decided to just go ahead and implement a simple FEC scheme using Hamming codes. I'm not even splitting the codewords into separate sections of the packet yet. The funny thing about hamming codes is that the best way to implement them is using a lookup table. In this case, the reason is because there are relatively few codewords. In this case there are 16. An array (use PROGMEM!) of 16 elements is all that's needed to encode your data. Use the higher-order nibble, generate a code word, then use the lower-order nibble and generate another.
Decoding is a little more complicated, but only because you have to think about every possible erroneous codeword. In this case, because codewords are 8 bits, there are 256 of them. Another PROGMEM array converts from (possibly error-containing) words into useable data. There are many received words that don't map to a specific codeword. Normally, these would be treated as "erasures," which means that the character is deleted from the data stream. However, we don't really have a way of marking these erasures, so I just guess. That seems crazy, but it's an educated guess. For example, in the case of a received word that we can't directly decode, there will be a few near-by codewords. By near-by, I mean they have the same, and small, hamming distance. I choose one of these codewords. I choose them biased toward the information part (as opposed to the check part) of the codeword. It's not a perfect strategy, but it's better than nothing (maybe).
I wrote a simple program for the PC (in general terms, it will compile on anything) that generates these arrays, just specify the generator and check matrices that you want (I have a good one in there already) and start it from the command line. It'll spit the lookup tables out to the console. It's checked into the Git repository along with the other transceiver code.
USB interface format
On the USB port, I've decided to simply copy the bytes over USB exactly as they were received over the air. This choice was made because I imagine that later computer software may want to write its own packet formats, and would need to change the value of the length and type fields directly. This is also true for data arriving from USB destined for RF. If the incoming data provides an invalid length it is ignored. There is some possibility of the host and transceiver becoming out of sync. In attempt to correct this, I've implemented a function that clears the buffer state (and transmits whatever's in it) when a "break" is sent over the USB serial port.
The hardware is little more than a basic AT90USB-series Atmel AVR and my now standard (at least to me) MRF49XA transceiver. I've attached the devices using the standard SPI pins on the AVR, though I'm not necessarily using the hardware SPI hardware. Because the MRF49XA uses a 16-bit interface, and the AVR SPI uses 8-bit transfers, you can't use the hardware SS pin, even if you use the hardware SPI logic.
[caption id="attachment_1506" align="aligncenter" width="540"]!(http://alternet.us.com/wp- content/uploads/2011/11/DSC_0151.jpg) Debugging the transceiver interface[/caption]
Because the AT90USB162 doesn't include an ADC, I've not connected the RSSI pin to anything, so there's no analog signal strength measurement. Though it's not necessary to connect to the RCLKOUT and DATA pins (they're used when you're not using the transceiver FIFO), I've attached them in case some wants to try using them.
[caption id="attachment_1503" align="aligncenter" width="544"]!(http://alternet.us.com/wp-content/uploads/2011/11/mrf49xa- small-v2.jpg) Full transceiver schematic (click for PDF)[/caption]
That's it for now. I've got plans to release a all-in-one PCB that implements this project. Thanks for reading!
Note that the AT90USBKey was provided by Element 14 in exchange for writing this post.