In computer networking, linear network coding is a program in which intermediate nodes transmit data from source nodes to sink nodes by means of linear combinations.
Linear network coding may be used to improve a network's throughput, efficiency, and scalability, as well as reducing attacks and eavesdropping. The nodes of a network take several packets and combine for transmission. This process may be used to attain the maximum possible informationflow in a network.
It has been proven that, theoretically, linear coding is enough to achieve the upper bound in multicast problems with one source.[1] However linear coding is not sufficient in general; even for more general versions of linearity such as convolutional coding and filter-bank coding.[2] Finding optimal coding solutions for general network problems with arbitrary demands is a hard problem, which can be NP-hard[3][4]
and even undecidable.[5][6]
^S. Li, R. Yeung, and N. Cai, "Linear Network Coding"(PDF), in IEEE Transactions on Information Theory, Vol 49, No. 2, pp. 371–381, 2003
^R. Dougherty, C. Freiling, and K. Zeger, "Insufficiency of Linear Coding in Network Information Flow" (PDF), in IEEE Transactions on Information Theory, Vol. 51, No. 8, pp. 2745-2759, August 2005 ( erratum)
^Rasala Lehman, A.; Lehman, E. (2004). Complexity classification of network information flow problems. 15th ACM-SIAM SODA. pp. 142–150.
^Li, C. T. (2023). "Undecidability of Network Coding, Conditional Information Inequalities, and Conditional Independence Implication". IEEE Transactions on Information Theory. 69 (6): 1. arXiv:2205.11461. doi:10.1109/TIT.2023.3247570. S2CID248986512.