  This paper investigates the construction of linear network codes for
broadcasting a set of data packets to a number of users. The links from the
source to the users are modeled as independent erasure channels. Users are
allowed to inform the source node whether a packet is received correctly via
feedback channels. In order to minimize the number of packet transmissions
until all users have received all packets successfully, it is necessary that a
data packet, if successfully received by a user, can increase the dimension of
the vector space spanned by the encoding vectors he or she has received by one.
Such an encoding vector is called innovative. We prove that innovative linear
network code is uniformly optimal in minimizing user download delay. When the
finite field size is strictly smaller than the number of users, the problem of
determining the existence of innovative vectors is proven to be NP-complete.
When the field size is larger than or equal to the number of users, innovative
vectors always exist and random linear network code (RLNC) is able to find an
innovative vector with high probability. While RLNC is optimal in terms of
completion time, it has high decoding complexity due to the need of solving a
system of linear equations. To reduce decoding time, we propose the use of
sparse linear network code, since the sparsity property of encoding vectors can
be exploited when solving systems of linear equations. Generating a sparsest
encoding vector with large finite field size, however, is shown to be NP-hard.
An approximation algorithm that guarantee the Hamming weight of a generated
encoding vector to be smaller than a certain factor of the optimal value is
constructed. Our simulation results show that our proposed methods have
excellent performance in completion time and outperforms RLNC in terms of
decoding time.
