Publication

New model for rigorous analysis of LT-codes

Mohammad Amin Shokrollahi
2006
Conference Papers

Abstract

We present a new model for LT codes which simplifies the analysis of the error probability of decoding by belief propagation. For any given degree distribution, we provide the first rigorous expression for the limiting bit-error probability as the length of the code goes to infinity via recent results in random hypergraphs by Darling and Norris, Ann. Appl. Probab., 2005. For a code of finite length, we provide an algorithm for computing the probability of block-error of the decoder. This algorithm improves by a linear factor the algorithm of Karp, Luby, and Shokrollahi, Proc. of ISIT, 2004.

Official source

https://infoscience.epfl.ch/entities/publication/5ae3d2c8-e6cc-41ff-a994-9314e61321cc

About this result

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.

Mohammad Amin Shokrollahi
2006
Conference Papers

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/5ae3d2c8-e6cc-41ff-a994-9314e61321cc

About this result

Related concepts (32)

Error correction code

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.

Probability

Probability is the branch of mathematics concerning numerical descriptions of how likely an event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and 1, where, roughly speaking, 0 indicates impossibility of the event and 1 indicates certainty. The higher the probability of an event, the more likely it is that the event will occur. A simple example is the tossing of a fair (unbiased) coin.

Fountain code

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.

Related publications (31)

Technosignatures Longevity and Lindy's Law

Claudio Grimaldi

The probability of detecting technosignatures (i.e., evidence of technological activity beyond Earth) increases with their longevity, or the time interval over which they manifest. Therefore, the assumed distribution of longevities has some bearing on the ...

Iop Publishing Ltd2024

Mean value theorems for collections of lattices with a prescribed group of symmetries

Nihar Prakash Gargava

Euclidean lattices are mathematical objects of increasing interest in the fields of cryptography and error-correcting codes. This doctoral thesis is a study on high-dimensional lattices with the motivation to understand how efficient they are in terms of b ...

EPFL2024

A Generalized Adjusted Min-Sum Decoder for 5G LDPC Codes: Algorithm and Implementation

Andreas Peter Burg, Alexios Konstantinos Balatsoukas Stimming, Yifei Shen, Yuqing Ren, Hassan Harb

5G New Radio (NR) has stringent demands on both performance and complexity for the design of low-density parity-check (LDPC) decoding algorithms and corresponding VLSI implementations. Furthermore, decoders must fully support the wide range of all 5G NR bl ...

Ieee-Inst Electrical Electronics Engineers Inc2024