The Case for Structured Random Codes in Network Capacity Theorems

B. Nazer and M. Gastpar

European Transactions on Telecommunications, Special Issue on New Directions in Information Theory, vol.19, no.4, pp.455-474, June 2008.

Download | Abstract | Notes | Links | Reference | BibTeX

Download

Adobe Portable Document Format - [PDF]

Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract

Random 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\"{o}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.

Notes

Reference

B. Nazer and M. Gastpar, The Case for Structured Random Codes in Network Capacity Theorems, European Transactions on Telecommunications, Special Issue on New Directions in Information Theory, vol.19, no.4, pp.455-474, June 2008.

BibTeX

@ARTICLE(bn_mg_ett07,
   AUTHOR = "B.~Nazer and M.~Gastpar",
   TITLE = "The Case for Structured Random Codes in Network Capacity Theorems",
   JOURNAL = "European Transactions on Telecommunications, Special Issue on New Directions in Information Theory",
   VOLUME = "19",
   NUMBER = "4",
   PAGES = "455-474",
   MONTH = "June",
   YEAR = "2008",
   )