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 journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
| Original language | English |
|---|---|
| Pages (from-to) | 2493-2503 |
| Journal / Publication | IEEE Transactions on Information Theory |
| Volume | 62 |
| Issue number | 5 |
| Online published | 1 Mar 2016 |
| Publication status | Published - May 2016 |
Link(s)
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 journal › peer-review
