General AL-FEC documents

Rapid access to...


Introduction
Introduce AL-FEC codes, why is it used, explain coding principles, and implementation rules.
Terminology
This is a list of all definitions that you need with AL-FEC codes.

Quick introduction to AL-FEC  ↑


AL-FEC in short

AL-FEC (A.K.A. UL-FEC) codes are critical to many applications. Their goal is to recover from symbol erasures (rather than errors): a symbol either arrives without any error or is altogether lost. This is why we say they work on a symbol erasure channel. Depending on the target use-case, a symbol can either be:

  • a bit (as with physical layer codes)
  • a byte (e.g. in the DVB MPE-FEC/MPE-IFEC MAC layer),
  • a packet payload that is several hundreds of byte long (e.g. a UDP datagram payload),
  • or a file chunk (e.g. with distributed storage applications).

The coding principles remain the same, even if codes are not used exactly in the same way.

Being implemented in higher layers (compared to physical layer codes), they benefit from many simplifications:

  • they are usually implemented in software codecs, using the host memory for symbol storage;
  • they often integrate the application constraints and the codes can often be produced dynamically, just on time, with the exact encoding block size and redundancy amount needed. Adding a large amount of redundant data is even meaningful with some use-cases.
An example (among many others...)

Here is a simple example where the use of AL-FEC encoding (in that case LDPC-stairce codes) adds some redundancy to the transmitted flow which enables the mobile receiver to reconstruct the missing information, even in harsh environments, and play the content of the digital library. The content is sent in a file-distribution mode (rather than streaming mode), within a carousel.

alfec for mobile

Open this image

Terminology  ↑


Some useful words & expressions...
3GPP/MBMS the MBMS (Multimedia Broadcast Multicast Service) service is an extension to cellular 3G telephony systems that has been developed by 3GPP. Its goal is to enable scalable content delivery services to mobiles.
AL-FEC the Application-Level FEC denotes an FEC code that operates within the transport or application layer. The channel model used in that case is the “packet erasure channel”.
CDP Content Delivery Protocols and applications (e.g. the FLUTE/ALC protocol used in the 3GPP/MBMS and DVB-H/IP Datacasting services).
Encoding symbol an encoded symbol is a symbol produced by the FEC code. Since most of the FEC codes considered in this project are "systematic", encoded symbols consist of source symbols and parity symbols. There are n encoding symbols.
FEC Forward Erasure Correction (FEC) codes, thanks to the addition of redundancy in the data flow, are capable of recovering from transmission erasures (e.g., packets lost by a congested router). FEC techniques are opposed to repeat request techniques whereby a receiver asks for the retransmission of lost symbols. Note that the "E" of the acronym can also mean "error" in which case the FEC decoder is capable of correcting erroneous bits. In the context of AL-FEC codes, the target is only erasures recovery.
Large block codes large block codes have (almost) no limitation on the block size. LDPC and Raptor codes have this property.
LDPC codes LDPC (Low Density Parity Check) codes form a very rich family of FEC codes. LDPC-staircase codes [rfc5170] belong to this category of codes.
MDS codes Maximum Distance Separable (MDS) codes are ideal codes, in the sense that decoding is possible as soon as any k symbols (among n possible symbols) are available, where k and n denote respectively the number of source and encoding symbols. LDPC and Raptor codes are NOT MDS codes, even if they can approach ideal MDS codes.
ML decoding Maximum Likelihood (ML) decoding consists in finding the most likely “codeword” (i.e., the n encoding symbols) given the received sequence of symbols. For erasure channels, this is the same as resolving the linear system given by the parity check matrix of the code.
Object an object is an ordered sequence of bytes to be transferred. Some objects are of finite, known in advance, size (e.g. a file) while others can be produced in real-time (e.g. a live audio/video stream).
Repair symbol a repair symbol is a symbol containing information generated by the FEC code which can be used to recover erased (lost) source symbols. There are n-k repair symbols.
Source block a (source) block is a subset of the object that is composed of k source symbols that are processed together by the FEC code. An object can consist of several blocks, because the object size exceeds the maximum block size accepted by a given FEC codec.
Source symbol a source symbol is a symbol containing information from the original object. There are k symbols per block.
Small-rate/rateless codes small-rate codes refers to codes capable of producing a large number of repair symbols for a given source block (said differently their code rate is small). LDPC codes can be used as small-rate codes. As an extreme case, the code rate tends to zero, meaning that the number of repair symbols can be infinite. The Raptor(Q) codes, as well as RLC (Random Linear Codes) codes have this property.
Symbol a symbol is the unit of data processed by the FEC code. With erasure channels, the target of this proposal, a symbol is either completely received without error, or completely lost.