The conventional theory of linear network coding (LNC) is only over acyclic networks. Convolutional network coding (CNC) applies to all networks. It is also a form of LNC, but the linearity is w.r.t. the ring of rational power series rather than the
field of data symbols. CNC has been generalized to LNC w.r.t. any discrete valuation ring (DVR) in order for flexibility in applications. For a causal DVR-based code, all possible source-generated messages form a free module, while incoming coding vectors to a receiver span the emph{received submodule}. An existing emph{time-invariant decoding} algorithm is at a delay equal to the largest valuation among all invariant factors of the received submodule. This intrinsic algebraic attribute is herein proved to be the optimal decoding delay. Meanwhile, emph{time-variant decoding} is formulated. The meaning of time-invariant decoding delay gets a new interpretation through being a special case of the time-variant counterpart. The optimal delay turns out to be the same for time-variant decoding, but the decoding algorithm is more flexible in terms of decodability check and decoding matrix design. All results apply, in particular, to CNC.
We consider network coding for networks experiencing worst-case bit-flip errors, and argue that this is a reasonable model for highly dynamic wireless network transmissions. We demonstrate that in this setup prior network error-correcting schemes can
be arbitrarily far from achieving the optimal network throughput. We propose a new metric for errors under this model. Using this metric, we prove a new Hamming-type upper bound on the network capacity. We also show a commensurate lower bound based on GV-type codes that can be used for error-correction. The codes used to attain the lower bound are non-coherent (do not require prior knowledge of network topology). The end-to-end nature of our design enables our codes to be overlaid on classical distributed random linear network codes. Further, we free internal nodes from having to implement potentially computationally intensive link-by-link error-correction.
