Forward error correction for wifibroadcast
This post introduces a new feature to wifibroadcast: Forward error correction. This helps lowering the data rate and/or increasing the reliability of the transmission.
Early after I published wifibroadcast there were suggestions on improving the forward error correction (FEC) mechanism. While I agreed on these suggestions, my primary goal was to first create something that is usable to see if the idea behind wifibroadcast is worth following. After some months of testing and dozens of other people having also great experiences with wifibroadcast I was confident enough to start to “improve” things.
Initially I implemented a simple retransmission. Each packet got sent several times, increasing the chance that at least one packet got through. This worked sufficiently well but had some issues:
- Bandwidth: The only parameter to increase the reliability was the retransmission rate. And this rate basically multiplied the net bandwidth. This is quite obvious: If you transmit each packet three times, you need three times the bandwidth.
- Relieability: Although it seems unlikely that all N retransmissions of the same packet are lost that phenomenon existed. The explanation is quite simple: If you roll a dice often enough, the likelihood of some strange combinations happening needs to be considered. For example, if you roll a million times, you could expect to see the sequence “1”-“2”-“3”-“4” nearly a thousandth times. The same is true for wifibroadcast. We are sending a lot of packets so unlikely things can easily happen.
Some commentators suggested to take a look at udpcast, a tool that is able to transfer data over a lossy unidirectional link. And well, that is exactly what wifibroadcast does! The FEC code there was well written and easy to adopt for my use case. In addition, the code is fast enough to run on a Raspberry PI A+. In the code Vandermonde matrices are used to perform the FEC.
The idea behind the code is very simple. Your data has to be divided into packets and a fixed number of them are grouped together to form a block. Lets assume we have a block size of 8 packets. The FEC code now allows you to calculate an arbitrary number of FEC packets (that have the same size as the DATA packets). Lets assume we use 4 FEC packets. If now a DATA packet gets lost, it can be replaced by any of the 4 FEC packets. So we might be able to repair up to 4 DATA packets, regardless which ones of the 8 are affected. This leads to two important advantages:
- Bandwidth: Since we used in the example above 4 FEC packets per 8 DATA packets, the bandwidth requirements are +50%. This could not have been archived with retransmission. There the “smallest” bandwidth with redundancy would be +100%
- Reliability: Since any DATA packet can be repair with any FEC packet, the chances of corruptions drop significantly. It is no more important which packets are corrupted, only how many.
The new FEC feature has been merged into the default branch of wifibroadcast (together with the new fifo interface introduced here)
To update (both on tx and rx!):
hg pull hg update make clean && make
The basic usage of wifibroadcast has not changed. Only some parameters have now a different meaning:
- -b This parameter describes the number of DATA packets per block. So this parameter has more or less the same meaning as with the retransmission version
- -r This parameter has changed from number of retransmissions to number of FEC packets. Each block will be appended with -r FEC packets.
- -f Packet size. This parameter is identical to the retransmission version in that it defines the size of a packet. The only difference is that packets now cannot be smaller than -f.
- Changing the coding rate while keeping block size constant: Increasing the number of FEC packets increases the reliability of the link at the expense of higher bandwidth. A FEC ratio of 50% is roughly(!) comparable (in terms of reliability) to a retransmission rate of 2. If your block size is 8 DATA packets then this would result in 4 FEC packets.
- Changing the block lengths while keeping the coding rate constant: An increased block length can increase the reliability of a link without increasing the bandwidth. However, this increases the latency since it needs to be waited until a full block of data has been received before the transmission can begin. Why does this increase reliability? Very often, blocks are only mildly corrupted so that not all FEC packets will be needed. However, these unused FEC packets are useless for the following block. By increasing the block size you are also increasing the “range” where the FECs can be applied.
It is also important to note that both tx and rx need to agree on -b, -r and -f. Otherwise the transmission does not work anymore.
How to set the parameters
The values of the parameters depend on your application. There are two things to consider: The coding rate and the block length. The coding rate is defined by the ratio between DATA and FEC packets. The block length is simply given by the -b parameter.
Since with this new FEC feature the bandwidth requirements of wifibroadcast can be lowered quite significantly, new WIFI modulations are now usable. I’ve added a new patched firmware under patches/AR9271/firmware/htc_9271.fw.mcs1 that if being copied to /lib/firmware/htc_9271.fw (on tx) enables the MCS1 modulation. This gives you 13mbit/s air data rate of which roughly net 10mbit/s are usable. So this modulation would be perfect to use if you have a h264 data rate of 6mbit/s with a 8/4 coding rate (resulting in a 9mbit/s bandwidth requirement).
The lower modulation rate should give you a better range if you are flying at high distance or with massive occlusions.