This is a followup blog post to an earlier post on error resilience mechanisms for video. As mentioned in the previous blog post, there are multiple error resilience mechanisms that can be used to resolve issues with lost media packets. In this blog post, we will cover Forward Error Correction, which sends repair packets to automatically recover the lost packet.
The simplest FEC is an eXclusive OR (XOR) parity scheme. The scheme is as follows:
- The sender determines the group of source packets (fixed size) that are protected by a repair packet.
- The sender generates the repair packets by performing the XOR operation on those group of packets.
- The sender sends the source packets and the repair packets to the receiver
- At the receiver, if a packet is lost, it attempts to recover the packet.
There are several types of parity FEC schemes:
- Single Dimensional: a packet can only be used in one group of source packet. For example, row (non-interleaved) and column (interleaved).
- Multiple Dimensional: a packet can be used in several groups of source packets. E.g., staircase pattern, etc.
Let’s go through single and multiple dimensional FEC schemes with animations.
Single Dimensional Parity FEC
The packets are arranged in rectangular or square pattern, and repair packets are generated by XORing the rows or columns. The row FEC is good for a single uncorrelated packet loss, because more than one consecutive packet loss (burst) would not be recoverable using a simple parity FEC. Figure 1 animates what kind packet losses row FEC can and cannot recover.
Figure 1: Recoverable and Unrecoverable loss pattern for row FEC
The column FEC is more capable of handling continuous or burst packet loss, if the burst size is smaller than the number of groups. For example, in our example the group size is three packets and a burst of four or more would be unrecoverable. The main reason for this is that the lost packet can only be recovered after the associated recovery packets have been received, and if more than one packet is lost in a group, a single repair packet will not be sufficient. Figure 2 animates what kind packet losses column FEC can and cannot recover.
Figure 2: Recoverable and Unrecoverable loss pattern for column FEC
Figure 3 shows the recoverable and unrecoverable loss pattern for column and row FEC used in Figures 1 and 2. In the case of row FEC, we assume that the row FEC protects a single the packet in a row. Similarly, for column FEC a single lost packet in a column is recovered. Packets marked with “X” are lost and unrecoverable.
Figure 3: Recoverable and Unrecoverable loss pattern for column and row FEC.
Multi Dimensional Parity FEC
To overcome the limitation of the single dimensional FEC, protecting a single packet with multiple repair packets increases the robustness. However, it also increases the overhead. Figure 4 shows that by combining both the row and column FEC packets, it can repair the unrecoverable loss patterns in Figure 3.
Figure 4: Recoverable loss pattern for a full block of FEC repair.
Applicability to Multimedia
FEC in real-time media can be used in several ways:
- To protect packets within a single media stream
- To protect packets across multiple media streams
In the case of audio, where several audio samples are packetized into a single packet (20-60ms), the FEC blocks are smaller. The reason is to not delay playback waiting for the repair packet to arrive. Opus for example sends an FEC repair packet for every two packets.
In the case of video, a compressed video frame is packetized into several Real-Time Transport Protocol (RTP) packets, and typically, the FEC repair packet arrives before the next video frame.
There are several RTP payload formats to carry FEC data: RFC 5109, RFC 2733 and SMPTE 2022-1. However, these versions have had scalability issues, which led to the work on FLEXIBLE FEC. FLEXIBLE FEC supports the flexibility of 1-dimensional and 2-dimensional FEC, and it can protect a single stream and/or multiple streams. Apart from parity FEC, there are several other block-based FEC codes, such as: Low-density parity-check (LDPC), Reed-Solomon, etc.
If you are interested to learn FEC in more detail, have a look at our papers on Error Resilience and Adaptive FEC for WebRTC congestion control. Another good introductory paper to FEC is Stefan Holmer’s Handling Packet loss in WebRTC.
To pick your brain, here is a FEC themed puzzle. Packets 3, R1, 4, 5, 6, are lost in a burst because of a bad wifi implementation. By applying the 2-dimensional parity scheme presented above, in which order would the white/outlined packets be recovered? Note that the outlined packets are lost.
Three first correct answers sent to growth[at]callstats.io will get a callstats.io T-shirt.
If you get excited about solving puzzles like this, have a look at our jobs page and send an application. We are looking for developers and tech savvy sales professionals.