TY - GEN
T1 - Relaying a fountain code across multiple nodes
AU - Gummadi, Ramakrishna
AU - Sreenivas, R. S.
PY - 2008
Y1 - 2008
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=51849086816&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=51849086816&partnerID=8YFLogxK
U2 - 10.1109/ITW.2008.4578640
DO - 10.1109/ITW.2008.4578640
M3 - Conference contribution
AN - SCOPUS:51849086816
SN - 9781424422708
T3 - 2008 IEEE Information Theory Workshop, ITW
SP - 149
EP - 153
BT - 2008 IEEE Information Theory Workshop, ITW
T2 - 2008 IEEE Information Theory Workshop, ITW
Y2 - 5 May 2008 through 9 May 2008
ER -