Linear Network Coding for Erasure Broadcast Channel with Feedback : Complexity and Algorithms

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

10 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)2493-2503
Journal / PublicationIEEE Transactions on Information Theory
Volume62
Issue number5
Online published1 Mar 2016
Publication statusPublished - May 2016

Abstract

This paper investigates the linear network coding problem for erasure broadcast channel with user feedback. An innovative linear network code is shown to be uniformly optimal for the system. In general, determining the existence of innovative packets is proved to be NP-complete. When the finite field size is larger than the number of users, innovative packets always exist and the problem of finding an innovative encoding vector with smallest Hamming weight is considered. The corresponding decision problem is shown to be NP-complete. Optimal and approximate network coding algorithms for maximizing the sparsity of encoding vectors are designed.

Research Area(s)

  • computational complexity, Erasure broadcast channel, innovative encoding vector, sparse network code

Citation Format(s)

Linear Network Coding for Erasure Broadcast Channel with Feedback : Complexity and Algorithms. / Sung, Chi Wan; Shum, Kenneth W.; Huang, Linyu et al.

In: IEEE Transactions on Information Theory, Vol. 62, No. 5, 05.2016, p. 2493-2503.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review