  In this paper, the problem of designing network codes that are both
communicationally and computationally efficient over packet line networks with
worst-case schedules is considered. In this context, random linear network
codes (dense codes) are asymptotically capacity-achieving, but require highly
complex coding operations. To reduce the coding complexity, Maymounkov et al.
proposed chunked codes (CC). Chunked codes operate by splitting the message
into non-overlapping chunks and send a randomly chosen chunk at each
transmission time by a dense code. The complexity, that is linear in the chunk
size, is thus reduced compared to dense codes. In this paper, the existing
analysis of CC is revised, and tighter bounds on the performance of CC are
derived. As a result, we prove that (i) CC with sufficiently large chunks are
asymptotically capacity-achieving, but with a slower speed of convergence
compared to dense codes; and (ii) CC with relatively smaller chunks approach
the capacity with an arbitrarily small but non-zero constant gap. To improve
the speed of convergence of CC, while maintaining their advantage in reducing
the computational complexity, we propose and analyze a new CC scheme with
overlapping chunks, referred to as overlapped chunked codes (OCC). We prove
that for smaller chunks, which are advantageous due to lower computational
complexity, OCC with larger overlaps provide a better tradeoff between the
speed of convergence and the message or packet error rate. This implies that
for smaller chunks, and with the same computational complexity, OCC outperform
CC in terms of the speed of approaching the capacity for sufficiently small
target error rate. In fact, we design linear-time OCC with very small chunks
(constant in the message size) that are both computationally and
communicationally efficient, and that outperform linear-time CC.
