DocumentCode
2681602
Title
On the Sparsity of a Linear Network Code for Broadcast Systems with Feedback
Author
Sung, Chi Wan ; Shum, Kenneth W. ; Kwan, Ho Yuet
Author_Institution
Dept. of Electron. Eng., City Univ. of Hong Kong, Hong Kong, China
fYear
2011
fDate
25-27 July 2011
Firstpage
1
Lastpage
4
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.
Keywords
broadcasting; computational complexity; network coding; radio networks; NP hard problem; decoding complexity; feedback; finite field; innovative encoding vector; linear network code; minimal Hamming weight; wireless broadcast systems; Complexity theory; Decoding; Delay; Encoding; Hamming weight; Network coding; Vectors;
fLanguage
English
Publisher
ieee
Conference_Titel
Network Coding (NetCod), 2011 International Symposium on
Conference_Location
Beijing
Print_ISBN
978-1-61284-138-0
Type
conf
DOI
10.1109/ISNETCOD.2011.5979090
Filename
5979090
Link To Document