https://www.nature.com/research-intelligence/nri-topic-summaries/network-coding-in-wireless-communication-systems-micro-22183
https://www.microsoft.com/en-us/research/wp-content/uploads/2007/07/tr-2007-90.pdf
Network Coding:
- Transformative Technique in Wireless Communications
- Enable intermediate nodes to combine data packets before they relay or transmit further towards destination.
- Traditionally it is just store and forward, but with Network Coding, utilizing various techniques like linear combinations of packets over finite fields, there are various benefits:
- Mitigates packet loss, interference etc.
- Performance: Increases throughput and spectral efficiency.
Generalization of Routing
Information delivery in today’s wireless networks is performed by routing which is intermediate nodes (routers) store and forward data. Now, network coding is the recent generalization of routing in which nodes can generate output data which is produced from encoding or applying certain functions on the previously received input data.
https://www.microsoft.com/en-us/research/wp-content/uploads/2007/07/tr-2007-90.pdf
Network coding as a fundamental generalization of traditional “store-and-forward” routing.
- Routing: Intermediate nodes receive packets and simply forward copies of them.
- Network Coding: Intermediate nodes can “mix” information by generating new output packets that are mathematical functions (e.g., linear combinations) of the packets they have received.
Technical Terms
- Network Coding:
Network coding allows intermediate nodes (routers/relays) to mathematically combine packets rather than just forwarding them. The classic example is the XOR operation (A⊕B). If a relay receives packet A and packet B, it transmits a single packet C=A⊕B. This reduces the number of transmissions needed, saving bandwidth and energy. - Randome Linear Network Coding (RLNC):
Instead of simple XOR, RLNC creates packets using linear algebra equations. If a node has original packets $p_1,p_2,…,p_n$, it creates a coded packet C by:
$C=\alpha_1p_1+\alpha_2 p_2+⋯+\alpha_n p_n$
Here, the coefficients ($\alpha$) are chosen randomly from a Galois Field. The receiver views this as a system of linear equations: $Ax=b$. Once the receiver collects n linearly independent coded packets, they can invert the matrix and recover the original data. - Galois Field (Finite Field):
A Galois Field, denoted GF($q$) or GF($2^n$), is a set of numbers with defined rules for addition and multiplication where the result always stays within the set. - Decoding Delay:
In RLNC, the receiver usually needs to collect a “full rank” matrix before it can solve the system of equations. If the original file was broken into N packets (generations), the receiver must successfully receive N coded packets before it can recover even a single bit of the original file.
References:
[1] R. Dilanchian, A. Bohlooli, and K. Jamshidi, “Adjustable random linear network coding (ARLNC): A solution for data transmission in dynamic IoT computational environments,” Digital Communications and Networks, vol. 11, no. 2, pp. 574–586, Apr. 2025, doi: 10.1016/j.dcan.2024.04.003.
[2] O. Lajam and S. Mohammed, “Optimizing efficiency of P2P content distribution with network coding: Principles, challenges, and future directions,” Journal of Network and Computer Applications, vol. 223, p. 103825, Mar. 2024, doi: 10.1016/j.jnca.2024.103825.
[3] B. Pu, “Network coding construction for a special class of three unicast sessions,” Sci Rep, vol. 13, no. 1, p. 20248, Nov. 2023, doi: 10.1038/s41598-023-47203-8.