On the Sparsity of a Linear Network Code for Broadcast Systems with Feedback
Chi Wan Sung, Kenneth W. Shum, Ho Yuet Kwan · 2011
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.