Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
End-to-End Error-Correcting Codes on Networks With Worst-Case Bit Errors
KTH, School of Electrical Engineering and Computer Science (EECS), Information Science and Engineering.ORCID iD: 0000-0001-9471-1409
Department of Information Engineering, Chinese University of Hong Kong, Hong Kong.
2018 (English)In: IEEE Transactions on Information Theory, ISSN 0018-9448, E-ISSN 1557-9654, Vol. 64, no 6, p. 4467-4479Article in journal (Refereed) Published
Abstract [en]

In highly dynamic wireless networks, communications face several challenges. In the first place, noise levels between nodes might be difficult to predict a priori. Besides, a Byzantine attacker hidden in the network, with knowledge of the network topology and observation of all transmissions, can choose arbitrary locations to inject corrupted packets. Considering that transmissions are usually in bits and hardware in wireless networks usually use modulation schemes with the size of modulation alphabet being powers of two, e.g. BPSK, QPSK, 16-QAM, 64-QAM, and so on, to address the above problem, we study coding for networks experiencing worst case bit errors, and with network codes over binary extension fields. We demonstrate that in this setup prior network error-correcting schemes can be arbitrarily far from achieving the optimal network throughput. A new transform metric for errors under the considered model is proposed. Using this metric, we replicate many of the classical results from coding theory. Specifically, new Hamming-type, Plotkin-type, and Elias-Bassalygo-type upper bounds on the network capacity are derived. A commensurate lower bound is shown based on Gilbert-Varshamov (GV)-type codes for error-correction. The GV codes used to attain the lower bound can be non-coherent, that is, they require neither prior knowledge of the network topology nor network coding kernels. We also propose a computationally efficient concatenation scheme. The rate achieved by our concatenated codes is characterized by a Zyablov-type lower bound. We provide a generalized minimum-distance decoding algorithm which decodes up to half the minimum distance of the concatenated codes. The end-to-end nature of our design enables our codes to be overlaid on the classical distributed random linear network codes. The other advantage of the end-to-end strategy over the link-by-link error-correction is that it reduces the computational cost at the internal nodes for performing error-correction.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE), 2018. Vol. 64, no 6, p. 4467-4479
Keywords [en]
Network error-correcting, worst-case errors, upper and lower bounds
National Category
Telecommunications
Identifiers
URN: urn:nbn:se:kth:diva-230416DOI: 10.1109/TIT.2018.2817801ISI: 000432983500032Scopus ID: 2-s2.0-85044335364OAI: oai:DiVA.org:kth-230416DiVA, id: diva2:1220956
Note

QC 20180619

Available from: 2018-06-19 Created: 2018-06-19 Last updated: 2018-06-20Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

Wang, Qiwen

Search in DiVA

By author/editor
Wang, Qiwen
By organisation
Information Science and Engineering
In the same journal
IEEE Transactions on Information Theory
Telecommunications

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf