Relaying a fountain code across multiple nodes

Ramakrishna Gummadi, R. S. Sreenivas

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Fountain codes are designed for erasure channels, and are particularly well suited for broadcast applications from a single source to its one hop receivers. In this context, the problem of designing a rateless code in the network case for on-the-fly recoding is very important, as relaying the data over multiple nodes is fundamentally useful in a network. Clearly, fountain codes are unsuited for on-line recoding (and simply forwarding over subsequent hops is provably suboptimal). Random linear codes are throughput optimal, but they do not enjoy the low complexity that is a prime feature of fountain codes. Can we get the low complexity of say, LT codes, while maintaining on-the-fly recoding and being throughput optimal? This paper proposes a novel solution to the above question. We consider packet level coding on a line network of discrete memoryless erasure channels (with potentially unlimited nodes), and exhibhit a coding scheme with (1) Ratelessness (2) Logarithmic per-symbol coding complexity (3) Throughput optimality (achieves rates equal the min cut capacity) and (4) avoids the delay of having to decode and then re-encode entire block lengths at intermediate nodes.

Original languageEnglish (US)
Title of host publication2008 IEEE Information Theory Workshop, ITW
Number of pages5
StatePublished - 2008
Event2008 IEEE Information Theory Workshop, ITW - Porto, Portugal
Duration: May 5 2008May 9 2008

Publication series

Name2008 IEEE Information Theory Workshop, ITW


Other2008 IEEE Information Theory Workshop, ITW

ASJC Scopus subject areas

  • Information Systems
  • Electrical and Electronic Engineering


Dive into the research topics of 'Relaying a fountain code across multiple nodes'. Together they form a unique fingerprint.

Cite this