**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.

Concept# Fountain code

Summary

In coding theory, fountain codes (also known as rateless erasure codes) are a class of erasure codes with the property that a potentially limitless sequence of encoding symbols can be generated from a given set of source symbols such that the original source symbols can ideally be recovered from any subset of the encoding symbols of size equal to or only slightly larger than the number of source symbols. The term fountain or rateless refers to the fact that these codes do not exhibit a fixed code rate.
A fountain code is optimal if the original k source symbols can be recovered from any k successfully received encoding symbols (i.e., excluding those that were erased). Fountain codes are known that have efficient encoding and decoding algorithms and that allow the recovery of the original k source symbols from any k’ of the encoding symbols with high probability, where k’ is just slightly larger than k.
LT codes were the first practical realization of fountain codes. Raptor codes and online codes were subsequently introduced, and achieve linear time encoding and decoding complexity through a pre-coding stage of the input symbols.
Fountain codes are flexibly applicable at a fixed code rate, or where a fixed code rate cannot be determined a priori, and where efficient encoding and decoding of large amounts of data is required.
One example is that of a data carousel, where some large file is continuously broadcast to a set of receivers. Using a fixed-rate erasure code, a receiver missing a source symbol (due to a transmission error) faces the coupon collector's problem: it must successfully receive an encoding symbol which it does not already have. This problem becomes much more apparent when using a traditional short-length erasure code, as the file must be split into several blocks, each being separately encoded: the receiver must now collect the required number of missing encoding symbols for each block. Using a fountain code, it suffices for a receiver to retrieve any subset of encoding symbols of size slightly larger than the set of source symbols.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related courses (5)

Related publications (122)

Related people (32)

Related concepts (5)

COM-102: Advanced information, computation, communication II

Text, sound, and images are examples of information sources stored in our computers and/or communicated over the Internet. How do we measure, compress, and protect the informatin they contain?

EE-543: Advanced wireless receivers

Students extend their knowledge on wireless communication systems to spread-spectrum communication and to multi-antenna systems. They also learn about the basic information theoretic concepts, about c

CS-308: Introduction to quantum computation

The course introduces the paradigm of quantum computation in an axiomatic way. We introduce the notion of quantum bit, gates, circuits and we treat the most important quantum algorithms. We also touch

Related lectures (32)

Related units (6)

In coding theory, an erasure code is a forward error correction (FEC) code under the assumption of bit erasures (rather than bit errors), which transforms a message of k symbols into a longer message (code word) with n symbols such that the original message can be recovered from a subset of the n symbols. The fraction r = k/n is called the code rate. The fraction k’/k, where k’ denotes the number of symbols required for recovery, is called reception efficiency.

In computing, telecommunication, information theory, and coding theory, forward error correction (FEC) or channel coding is a technique used for controlling errors in data transmission over unreliable or noisy communication channels. The central idea is that the sender encodes the message in a redundant way, most often by using an error correction code or error correcting code (ECC). The redundancy allows the receiver not only to detect errors that may occur anywhere in the message, but often to correct a limited number of errors.

In information theory, a low-density parity-check (LDPC) code is a linear error correcting code, a method of transmitting a message over a noisy transmission channel. An LDPC code is constructed using a sparse Tanner graph (subclass of the bipartite graph). LDPC codes are , which means that practical constructions exist that allow the noise threshold to be set very close to the theoretical maximum (the Shannon limit) for a symmetric memoryless channel.

Linear Codes: Systematic vs Non-Systematic

Explores the creation of systematic linear codes and the transformation of non-systematic codes, showcasing their equivalence and importance in simplifying encoding and decoding processes.

Linear Block Codes: Basics

Covers the basics of linear block codes and systematic codes over a field F.

Data Compression and Shannon's Theorem: Definitions

Explains binary codes, prefix-free codes, and representing letters with codes.

Ontological neighbourhood

:

Pascal Fua, Mathieu Salzmann, Benoît Alain René Guillard, Ren Li, Luca De Luigi

Recent approaches to drape garments quickly over arbitrary human bodies leverage self-supervision to eliminate the need for large training sets. However, they are designed to train one network per clothing item, which severely limits their generalization a ...

2023Olivier Sauter, Federico Alberto Alfredo Felici, Cassandre Ekta Contré, Simon Van Mulders, Hartmut Zohm

Rapid inter-discharge simulation and optimization using the RAPTOR code have allowed the development of a reliable and reproducible early heating strategy for an advanced tokamak (AT) scenario on ASDEX Upgrade. Solving for electron heat and current diffusi ...

Olivier Sauter, Federico Alberto Alfredo Felici, Cassandre Ekta Contré, Anna Teplukhina, Simon Van Mulders, Bernhard Sieglin

We discuss how the combination of experimental observations and rapid modeling has enabled to improve understanding of the tokamak ramp-down phase in ASDEX Upgrade. A series of dedicated experiments has been performed, to disentangle the effect of individu ...