Triangular network coding

<h2 id="coding-and-decoding">Coding and decoding</h2>

In TNC, coding is performed in two stages. First redundant "0" bits are added at the head and tail of each packet such that all packets are of uniform bit length. Then the packets are <a href="/facts/Exclusive_or/FHyr7hGQ">XOR coded</a>, bit-by-bit. The "0" bits are added in such a way that these redundant "0" bits added to each packet generate a <a href="/facts/Triangular_matrix/qjXSFMM3">triangular pattern</a>.
In essence, the TNC decoding process, like the LNC decoding process involves <a href="/facts/Gaussian_elimination/23Rvf4ht">Gaussian elimination</a>. However, since the packets in TNC have been coded in such a manner that the resulting coded packets are in triangular pattern, the computational process of triangularization,<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> with complexity of 
 
 
 
 O
 (
 
 n
 
 3
 
 
 )
 
 
 {\displaystyle O(n^{3})}
 
, where 
 
 
 
 n
 
 
 {\displaystyle n}
 
 is the number of packets, can be bypassed. The receiver now only needs to perform back-substitution,<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> with worst-case complexity given as 
 
 
 
 O
 (
 
 n
 
 2
 
 
 )
 
 
 {\displaystyle O(n^{2})}
 
 for each bit location.

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Qureshi, Jalaluddin; Foh, Chuan Heng; Cai, Jianfei (2012). "Optimal solution for the index coding problem using network coding over GF(2)". 2012 9th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON). pp. 134–142. arXiv:1209.6539. Bibcode:2012arXiv1209.6539Q. doi:10.1109/SECON.2012.6275780. ISBN 978-1-4673-1905-8. S2CID 8977891.. <a href="978-1-4673-1905-8" target="_blank">978-1-4673-1905-8</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Qureshi, Jalaluddin; Foh, Chuan Heng (August 2023). "Triangular code: Near-optimal linear time fountain code". Digital Communications and Networks. 9 (4): 869–878. doi:10.1016/j.dcan.2022.12.006. <a href="https://doi.org/10.1016%2Fj.dcan.2022.12.006" target="_blank">https://doi.org/10.1016%2Fj.dcan.2022.12.006</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Qureshi, Jalaluddin; Foh, Chuan Heng (August 2023). "Triangular code: Near-optimal linear time fountain code". Digital Communications and Networks. 9 (4): 869–878. doi:10.1016/j.dcan.2022.12.006. <a href="https://doi.org/10.1016%2Fj.dcan.2022.12.006" target="_blank">https://doi.org/10.1016%2Fj.dcan.2022.12.006</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">J. B. Fraleigh, and R. A. Beauregard, Linear Algebra. Chapter 10, Addison-Wesley Publishing Company, 1995. <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">J. B. Fraleigh, and R. A. Beauregard, Linear Algebra. Chapter 10, Addison-Wesley Publishing Company, 1995. <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
</ol>

Triangular network coding open-in-new

Triangular network coding