# Presentation: 805481

## Threshold Phenomena and Fountain Codes

- Amin Shokrollahi

- EPFL
- Joint work with M. Luby, R. Karp, O. Etesami

## Communication on Multiple Unknown Channels

## Example: Popular Download

## Example: Peer-to-Peer

## Example: Satellite

## The erasure probabilities are unknown.

- Want to come arbitrarily close to capacity on each of the erasure channels, with minimum amount of feedback.
- Traditional codes don’t work in this setting since their rate is fixed.
- Need codes that can adapt automatically to the erasure rate of the channel.

## What we Really Want

- Reconstruction time should depend only on size of content

**Notes:**
Want the encoded packets to be independently generated and unique

## Content

- Enc

- Digital buckets

## Applications: Multi-site downloads 

**Notes:**
With the new coding technology one would avoid the coupon collector problem

## Applications: Path Diversity 

- Applications: Path Diversity

**Notes:**
Avoid congested network areas

## Applications: Peer-2-Peer 

- Sender 1

- Applications: Peer-2-Peer

## Fountain Codes

- Sender sends a potentially limitless stream of encoded bits.
- Receivers collect bits until they are reasonably sure that they can recover the content from the received bits, and send STOP feedback to sender.
- Automatic adaptation: Receivers with larger loss rate need longer to receive the required information.
- Want that each receiver is able to recover from the minimum possible amount of received data, and do this efficiently.

## Fountain Codes

- Fix distribution      on      , where    is number of input symbols.
- For every output symbol sample independently from         and add input symbols corresponding to sampled subset.

## Fountain Codes

## Universality and Efficiency

- [Universality]
- Want sequences of Fountain Codes for which the overhead is arbitrarily small
- [Efficiency]
- Want per-symbol-encoding to run in close to constant time, and decoding to run in time linear in number of output symbols.

## LT-Codes

- Invented by Michael Luby in 1998.
- First class of universal and almost efficient Fountain Codes
- Output distribution has a very simple form
- Encoding and decoding are very simple

## LT-Codes

## The LT Coding Process

- Insert header,   and send

- XOR

- Choose 2
- Random original
- symbols

- Input symbols

## Decoding

## Decoding

## Decoding

## Decoding

## Decoding

## Decoding

## Decoding

## Decoding

## Decoding

## Slide 28

## Slide 29

## Slide 30

## So:

- Average degree constant means error probability constant
- How can we achieve constant workload per output symbol, and still guarantee vanishing error probability?
- Raptor codes achieve this!

## LT-light

- Traditional pre-code

- Raptor Codes

## Raptor Codes

- X

## Special Raptor Codes: LT-Codes

- LT-Codes are Raptor Codes with trivial pre-code: Need average degree

- LT-Codes compensate for the lack of the pre-code with a rather intricate output distribution.

## Progressive Giant Component Analysis

- A different method for the analysis of the decoder:

- Want enough nodes of degree 2 so there exists a giant component in the induced (random) graph on input symbols.

## Progressive Giant Component Analysis

- First giant component removes    -fraction of input symbols.
- Residual distribution:
- Fraction of residual nodes of degree 2:
- Average degree of new induced graph:
- Condition:
- “Ideal distribution:”

## Progressive Giant Component Analysis

- Analysis does not use “tree-assumption”, but only properties of induced graph.
- Analysis can be used to obtain error bounds for the decoding algorithm.
- It can also be used to obtain capacity-achieving distributions on the erasure channel.
- A modified version can be used to obtain       for capacity-achieving distributions for other symmetric channels.

## Nodes of Degree 2

## Nodes of Degree 2

- Information Loss!

## Fraction of Nodes of Degree 2

## The   -ary symmetric channel (large  )

- Double verification decoding (Luby-Mitzenmacher):

- If     and    are correct, then they verify   . Remove all of them from graph and continue.

- Can be shown that number of correct output symbols needs to be at least

- Times number of input symbols.

## The   -ary symmetric channel (large  )

- More sophisticated algorithms: induced graph!

- If two input symbols are connected by a correct output symbol, and each of them is connected to a correct output symbol of degree one, then the input symbols are verified. Remove from them from graph.

## The   -ary symmetric channel (large  )

- More sophisticated algorithms: induced graph!

- More generally: if there is a path consisting of correct edges, and the two terminal nodes are connected to correct output symbols of degree one, then the input symbols get verified. (More complex algorithms.)

## The   -ary symmetric channel (large  )

- Limiting case: Giant component consisting of correct edges, two correct output symbols of degree one “poke” the component. So, ideal distribution “achieves” capacity.

## Binary Memoryless Symmetric Channels 

- What is the fraction of nodes of degree 2 for capacity-achieving Raptor Codes?

- where, in general

- and    is the LLR of the channel.

## Slide 46

## General Symmetric Channels: Mimic Proof

- Proof is information theoretic: if fraction of nodes of degree 2 is larger by a constant, then :
- Expectation of the hyperbolic tangent of messages passed from input to output symbols at given round of BP is larger than a constant.
- This shows that
- So code cannot achieve capacity.

## General Symmetric Channels: Mimic Proof

- Fraction of nodes of degree one for capacity-achieving Raptor Codes:

## Sequences Designed for the BEC

- 0.067

- 0.135

- 0.194

- 0.267

- 0.331

- 0.391

- 0.459

- 0.522

- 0.584

- 0.650

- 0.000

- Normalized SNR
- Eb/N0

- Best designs
- (so far)

## Conclusions

- For LT- and Raptor codes, some decoding algorithms can be phrased directly in terms of subgraphs of graphs induced by output symbols of degree 2.
- This leads to a simpler analysis without the use the tree assumption.
- For the BEC, and for the q-ary symmetric channel (large q) we obtain essentially the same limiting capacity-achieving degree distribution, using the giant component analysis.
- An information theoretic analysis gives the optimal fraction of output nodes of degree 2 for general memoryless symmetric channels.
- A graph analysis reveals very good degree distributions, which perform very well experimentally.