  In the application of linear network coding to wireless broadcasting with
feedback, we prove that the problem of determining the existence of an
innovative encoding vector is NP-complete when the finite field size is two.
When the finite field size is larger than or equal to the number of users, it
is shown that we can always find an encoding vector which is both innovative
and sparse. The sparsity can be utilized in speeding up the decoding process.
An efficient algorithm to generate innovative and sparse encoding vectors is
developed. Simulations show that the delay performance of our scheme with
binary finite field outperforms a number of existing schemes in terms of
average and worst-case delay.
