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

Chi Wan Sung; Kenneth W. Shum; Linyu Huang; Ho Yuet Kwan

doi:10.1109/TIT.2016.2536612

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

Chi Wan Sung
, Kenneth W. Shum
, Linyu Huang
, Ho Yuet Kwan

Research output: Contribution to journal › Article › peer-review

11 Citations (Scopus)

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.

Original language	English
Article number	7422800
Pages (from-to)	2493-2503
Number of pages	11
Journal	IEEE Transactions on Information Theory
Volume	62
Issue number	5
DOIs	https://doi.org/10.1109/TIT.2016.2536612
Publication status	Published - May 2016
Externally published	Yes

Keywords

Erasure broadcast channel
computational complexity
innovative encoding vector
sparse network code

Access to Document

10.1109/TIT.2016.2536612

Cite this

@article{2121f5c4c91446b5925052dcfb821306,

title = "Linear Network Coding for Erasure Broadcast Channel with Feedback: Complexity and Algorithms",

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.",

keywords = "Erasure broadcast channel, computational complexity, innovative encoding vector, sparse network code",

author = "Sung, \{Chi Wan\} and Shum, \{Kenneth W.\} and Linyu Huang and Kwan, \{Ho Yuet\}",

note = "Publisher Copyright: {\textcopyright} 2016 IEEE.",

year = "2016",

month = may,

doi = "10.1109/TIT.2016.2536612",

language = "English",

volume = "62",

pages = "2493--2503",

number = "5",

}

TY - JOUR

T1 - Linear Network Coding for Erasure Broadcast Channel with Feedback

T2 - Complexity and Algorithms

AU - Sung, Chi Wan

AU - Shum, Kenneth W.

AU - Huang, Linyu

AU - Kwan, Ho Yuet

PY - 2016/5

Y1 - 2016/5

N2 - 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.

AB - 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.

KW - Erasure broadcast channel

KW - computational complexity

KW - innovative encoding vector

KW - sparse network code

UR - https://www.scopus.com/pages/publications/84964812588

U2 - 10.1109/TIT.2016.2536612

DO - 10.1109/TIT.2016.2536612

M3 - Article

AN - SCOPUS:84964812588

SN - 0018-9448

VL - 62

SP - 2493

EP - 2503

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 5

M1 - 7422800

ER -

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this