On decoding of DVR-based linear network codes. (English) Zbl 1343.94091
Summary: 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 received submodule. An existing 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, 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.
MSC:
| 94B05 | Linear codes (general theory) |
| 13F30 | Valuation rings |
| 68M10 | Network design and communication in computer systems |
| 94A15 | Information theory (general) |
Keywords:
linear network coding; discrete valuation ring; cyclic networks; decoding delay; time-variant decodingReferences:
| [1] | Brown, W.C.: Matrices Over Commutative Rings. Marcel Dekker, New York (1986) |
| [2] | Dummit, D.S., Foote, R.M.: Abstract Algebra, 3rd edn. Wiley, New York (2004) · Zbl 1037.00003 |
| [3] | Erez, E., Feder, M.: Convolutional network codes. In: Proceedings of the IEEE International Symposium Information Theory (ISIT), Chicago, USA (2004) |
| [4] | Erez, E., Feder, M.: Efficient network codes for cyclic networks. IEEE Trans. Inf. Theory 56(8), 3862-3878 (2010) · Zbl 1366.94626 · doi:10.1109/TIT.2010.2050934 |
| [5] | Guo, W., Cai, N.: The minimum decoding delay of convolutional network coding. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E 93A(8), 1518-1523 (2010) · doi:10.1587/transfun.E93.A.1518 |
| [6] | Guo, W., Cai, N., Sun, Q.T.: Time-variant decoding of convolutional network codes. IEEE Commun. Lett. 16(10), 1656-1659 (2012) · doi:10.1109/LCOMM.2012.080312.120789 |
| [7] | Koetter, R., Mdard, M.: An algebraic approach to network coding. IEEE/ACM Trans. Netw. 11(5), 782-795 (2003) · doi:10.1109/TNET.2003.818197 |
| [8] | Li, S.-Y.R., Yeung, R.W., Cai, N.: Linear network coding. IEEE Trans. Inf. Theory 49(2), 371-381 (2003) · Zbl 1063.94004 · doi:10.1109/TIT.2002.807285 |
| [9] | Li, S.-Y.R., Yeung, R.W.: On convolutional network coding. In: Proceedings of the IEEE International Symposium Information Theory (ISIT), Seattle, USA, pp. 1743-1747 (2006) · Zbl 1366.94249 |
| [10] | Li, S.-Y.R., Sun, Q.T.: Network coding theory via commutative algebra. IEEE Trans. Inf. Theory 56(1), 403-415 (2011) · Zbl 1366.94249 · doi:10.1109/TIT.2010.2090227 |
| [11] | Li, S.-Y.R., Sun, Q.T., Shao, Z.: Linear network coding: theory and algorithms. Proc. IEEE 99(3), 372-387 (2011) · doi:10.1109/JPROC.2010.2093851 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
