  We apply linear network coding (LNC) to broadcast a block of data packets
from one sender to a set of receivers via lossy wireless channels, assuming
each receiver already possesses a subset of these packets and wants the rest.
We aim to characterize the average packet decoding delay (APDD), which reflects
how soon each individual data packet can be decoded by each receiver on
average, and to minimize it while achieving optimal throughput. To this end, we
first derive closed-form lower bounds on the expected APDD of all LNC
techniques under random packet erasures. We then prove that these bounds are
NP-hard to achieve and, thus, that APDD minimization is an NP-hard problem. We
then study the performance of some existing LNC techniques, including random
linear network coding (RLNC) and instantly decodable network coding (IDNC). We
proved that all throughput-optimal LNC techniques can approximate the minimum
expected APDD with a ratio between 4/3 and 2. In particular, the ratio of RLNC
is exactly 2. We then prove that all IDNC techniques are only heuristics in
terms of throughput optimization and {cannot guarantee an APDD approximation
ratio for at least a subset of the receivers}. Finally, we propose
hyper-graphic linear network coding (HLNC), a novel throughput-optimal and
APDD-approximating LNC technique based on a hypergraph model of receivers'
packet reception state. We implement it under different availability of
receiver feedback, and numerically compare its performance with RLNC and a
heuristic general IDNC technique. The results show that the APDD performance of
HLNC is better under all tested system settings, even if receiver feedback is
only collected intermittently.
