Multiple-access network information-flow and correction codes

Theodoros K. Dikaliotis, Tracey Ho, Sidharth Jaggi, Svitlana Vyetrenko, Hongyi Yao, Michelle Effros, Jrg Kliewer, Elona Erez

Research output: Contribution to journalArticlepeer-review

15 Scopus citations

Abstract

This work considers the multiple-access multicast error-correction scenario over a packetized network with z malicious edge adversaries. The network has min-cut m and packets of length ℓ , and each sink demands all information from the set of sources S. The capacity region is characterized for both a side-channel model (where sources and sinks share some random bits that are secret from the adversary) and an omniscient adversarial model (where no limitations on the adversary's knowledge are assumed). In the side-channel adversarial model, the use of a secret channel allows higher rates to be achieved compared to the omniscient adversarial model, and a polynomial-complexity capacity-achieving code is provided. For the omniscient adversarial model, two capacity-achieving constructions are given: the first is based on random subspace code design and has complexity exponential in ℓ m while the second uses a novel multiple-field-extension technique and has Oℓ mS complexity, which is polynomial in the network size. Our code constructions are end-to-end in that all nodes except the sources and sinks are oblivious to the adversaries and may simply implement predesigned linear network codes (random or otherwise). Also, the sources act independently without knowledge of the data from other sources.

Original languageEnglish (US)
Article number5695099
Pages (from-to)1067-1079
Number of pages13
JournalIEEE Transactions on Information Theory
Volume57
Issue number2
DOIs
StatePublished - Feb 2011
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Keywords

  • Double extended field
  • Gabidulin codes
  • network error-correction
  • random linear network coding
  • subspace codes

Fingerprint Dive into the research topics of 'Multiple-access network information-flow and correction codes'. Together they form a unique fingerprint.

Cite this