Computer Science – Information Theory
Scientific paper
2008-02-04
Computer Science
Information Theory
23 pages, 7 figures, To appear in European Transactions on Telecommunication: Special Issue on New Directions in Information T
Scientific paper
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.
Gastpar Michael
Nazer Bobak
No associations
LandOfFree
The Case for Structured Random Codes in Network Capacity Theorems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Case for Structured Random Codes in Network Capacity Theorems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Case for Structured Random Codes in Network Capacity Theorems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-236780