On the sparsity of a linear network code for broadcast systems with feedback

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

doi:10.1109/ISNETCOD.2011.5979090

On the sparsity of a linear network code for broadcast systems with feedback

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

11 Citations (Scopus)

Abstract

One method for reducing the decoding complexity of network coding in wireless broadcast systems is to generate sparse encoding vectors. The problem of finding the minimal Hamming weight of innovative encoding vectors over large finite field is formulated. By reducing the problem of hitting set to it, we show that the problem is NP-hard. However when the number of users is fixed, the problem can then be solved in polynomial time. A systematic method for solving the problem is provided.

Original language	English
Title of host publication	2011 International Symposium on Network Coding, NETCOD 2011 - Proceedings
DOIs	https://doi.org/10.1109/ISNETCOD.2011.5979090
Publication status	Published - 2011
Externally published	Yes
Event	2011 International Symposium on Network Coding, NETCOD 2011 - Beijing, China Duration: 25 Jul 2011 → 27 Jul 2011

Publication series

Name	2011 International Symposium on Network Coding, NETCOD 2011 - Proceedings

Conference

Conference	2011 International Symposium on Network Coding, NETCOD 2011
Country/Territory	China
City	Beijing
Period	25/07/11 → 27/07/11

Access to Document

10.1109/ISNETCOD.2011.5979090

Cite this

@inproceedings{4b8b161dbe3e4d72b314daceaaaaef26,

title = "On the sparsity of a linear network code for broadcast systems with feedback",

abstract = "One method for reducing the decoding complexity of network coding in wireless broadcast systems is to generate sparse encoding vectors. The problem of finding the minimal Hamming weight of innovative encoding vectors over large finite field is formulated. By reducing the problem of hitting set to it, we show that the problem is NP-hard. However when the number of users is fixed, the problem can then be solved in polynomial time. A systematic method for solving the problem is provided.",

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

year = "2011",

doi = "10.1109/ISNETCOD.2011.5979090",

language = "English",

isbn = "9781612841403",

series = "2011 International Symposium on Network Coding, NETCOD 2011 - Proceedings",

booktitle = "2011 International Symposium on Network Coding, NETCOD 2011 - Proceedings",

note = "2011 International Symposium on Network Coding, NETCOD 2011 ; Conference date: 25-07-2011 Through 27-07-2011",

}

Sung, CW, Shum, KW & Kwan, HY 2011, On the sparsity of a linear network code for broadcast systems with feedback. in 2011 International Symposium on Network Coding, NETCOD 2011 - Proceedings., 5979090, 2011 International Symposium on Network Coding, NETCOD 2011 - Proceedings, 2011 International Symposium on Network Coding, NETCOD 2011, Beijing, China, 25/07/11. https://doi.org/10.1109/ISNETCOD.2011.5979090

On the sparsity of a linear network code for broadcast systems with feedback. / Sung, Chi Wan; Shum, Kenneth W.; Kwan, Ho Yuet.
2011 International Symposium on Network Coding, NETCOD 2011 - Proceedings. 2011. 5979090 (2011 International Symposium on Network Coding, NETCOD 2011 - Proceedings).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - On the sparsity of a linear network code for broadcast systems with feedback

AU - Sung, Chi Wan

AU - Shum, Kenneth W.

AU - Kwan, Ho Yuet

PY - 2011

Y1 - 2011

N2 - One method for reducing the decoding complexity of network coding in wireless broadcast systems is to generate sparse encoding vectors. The problem of finding the minimal Hamming weight of innovative encoding vectors over large finite field is formulated. By reducing the problem of hitting set to it, we show that the problem is NP-hard. However when the number of users is fixed, the problem can then be solved in polynomial time. A systematic method for solving the problem is provided.

AB - One method for reducing the decoding complexity of network coding in wireless broadcast systems is to generate sparse encoding vectors. The problem of finding the minimal Hamming weight of innovative encoding vectors over large finite field is formulated. By reducing the problem of hitting set to it, we show that the problem is NP-hard. However when the number of users is fixed, the problem can then be solved in polynomial time. A systematic method for solving the problem is provided.

UR - http://www.scopus.com/inward/record.url?scp=80053012464&partnerID=8YFLogxK

U2 - 10.1109/ISNETCOD.2011.5979090

DO - 10.1109/ISNETCOD.2011.5979090

M3 - Conference contribution

AN - SCOPUS:80053012464

SN - 9781612841403

T3 - 2011 International Symposium on Network Coding, NETCOD 2011 - Proceedings

BT - 2011 International Symposium on Network Coding, NETCOD 2011 - Proceedings

T2 - 2011 International Symposium on Network Coding, NETCOD 2011

Y2 - 25 July 2011 through 27 July 2011

ER -

On the sparsity of a linear network code for broadcast systems with feedback

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this