The Case for Structured Random Codes in Network Capacity Theorems

Simple item page
dc.creatorNazer, Bobak
dc.creatorGastpar, Michael
dc.date2008-02-04
dc.date.accessioned2026-07-07T09:18:32Z
dc.date.available2026-07-07T09:18:32Z
dc.descriptionRandom coding arguments are the backbone of most channel capacity achievability proofs. In this paper, we show that in their standard form, such arguments are insufficient for proving some network capacity theorems: structured coding arguments, such as random linear or lattice codes, attain higher rates. Historically, structured codes have been studied as a stepping stone to practical constructions. However, Körner and Marton demonstrated their usefulness for capacity theorems through the derivation of the optimal rate region of a distributed functional source coding problem. Here, we use multicasting over finite field and Gaussian multiple-access networks as canonical examples to demonstrate that even if we want to send bits over a network, structured codes succeed where simple random codes fail. Beyond network coding, we also consider distributed computation over noisy channels and a special relay-type problem.
dc.description23 pages, 7 figures, To appear in European Transactions on Telecommunication: Special Issue on New Directions in Information Theory
dc.identifierhttps://arxiv.org/abs/0802.0342
dc.identifierhttp://arxiv.org/abs/0802.0342
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/154057
dc.subjectInformation Theory
dc.titleThe Case for Structured Random Codes in Network Capacity Theorems
dc.typetext

Files

Collections

arXiv