Open AccessThe case for structured random codes in network capacity theorems
Author(s) -
Nazer Bobak,
Gastpar Michael
Publication year - 2008
Publication title -
european transactions on telecommunications
Language(s) - English
Resource type - Journals
eISSN - 1541-8251
pISSN - 1124-318X
DOI - 10.1002/ett.1284
Subject(s) - linear network coding , mathematical proof , computer science , coding (social sciences) , theoretical computer science , channel capacity , gaussian , random access , discrete mathematics , random variable , mathematics , finite field , channel (broadcasting) , computer network , statistics , physics , geometry , quantum mechanics , network packet
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ö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. Copyright © 2008 John Wiley & Sons, Ltd.