# Triangular network coding

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Triangular_network_coding
> Markdown URL: https://mediated.wiki/source/Triangular_network_coding.md
> Source: https://en.wikipedia.org/wiki/Triangular_network_coding
> Source revision: 1306487474
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Concept in coding theory

In [coding theory](/source/Coding_theory), **triangular network coding** (**TNC**) is a non-linear [network coding](/source/Network_coding) based packet coding scheme introduced by [Qureshi, Foh & Cai (2012)](#CITEREFQureshiFohCai2012).[1] Previously, packet coding for network coding was done using linear network coding (LNC). The drawback of LNC over large [finite field](/source/Finite_field) is that it resulted in high encoding and decoding [computational complexity](/source/Big_O_notation). While linear encoding and decoding over [GF(2)](/source/GF(2)) alleviates the concern of high computational complexity, coding over GF(2) comes at the tradeoff cost of degrading throughput performance.

The main contribution of triangular network coding is to reduce the worst-case decoding computational complexity of O ( n 3 ) {\displaystyle O(n^{3})} to O ( n 2 ) {\displaystyle O(n^{2})} (where *n* is the total number of data packets being encoded in a coded packet) without degrading the throughput performance, with [code rate](/source/Code_rate) comparable to that of optimal coding schemes.

Triangular code has also been proposed as [Fountain code](/source/Fountain_code)[2] to achieve near-optimal performance with encoding and decoding computational complexity of O ( n log ⁡ n ) {\displaystyle O(n\log n)} . It has been further shown that triangular based fountain code can even outperform optimized [Luby transform code](/source/Luby_transform_code).[2]

## Coding and decoding

An example of coding four packets using TNC. Bit *b**i*,*k* ∈ {0,1} is the *i*th bit of the *k*th packet. Each packet has original length of *B* bits. The resulting coded packet has length *B* + 3 bits. Information about the number of redundant '0' bits added at the head of each packet is included in the coded packet's header.

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 [XOR coded](/source/Exclusive_or), bit-by-bit. The "0" bits are added in such a way that these redundant "0" bits added to each packet generate a [triangular pattern](/source/Triangular_matrix).

In essence, the TNC decoding process, like the LNC decoding process involves [Gaussian elimination](/source/Gaussian_elimination). 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,*[3] 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,*[3] with worst-case complexity given as O ( n 2 ) {\displaystyle O(n^{2})} for each bit location.

## References

1. **[^](#cite_ref-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](/source/ArXiv_(identifier)):[1209.6539](https://arxiv.org/abs/1209.6539). [Bibcode](/source/Bibcode_(identifier)):[2012arXiv1209.6539Q](https://ui.adsabs.harvard.edu/abs/2012arXiv1209.6539Q). [doi](/source/Doi_(identifier)):[10.1109/SECON.2012.6275780](https://doi.org/10.1109%2FSECON.2012.6275780). [ISBN](/source/ISBN_(identifier)) [978-1-4673-1905-8](https://en.wikipedia.org/wiki/Special:BookSources/978-1-4673-1905-8). [S2CID](/source/S2CID_(identifier)) [8977891](https://api.semanticscholar.org/CorpusID:8977891)..

1. ^ [***a***](#cite_ref-journal-article_2-0) [***b***](#cite_ref-journal-article_2-1) Qureshi, Jalaluddin; Foh, Chuan Heng (August 2023). ["Triangular code: Near-optimal linear time fountain code"](https://doi.org/10.1016%2Fj.dcan.2022.12.006). *Digital Communications and Networks*. **9** (4): 869–878. [doi](/source/Doi_(identifier)):[10.1016/j.dcan.2022.12.006](https://doi.org/10.1016%2Fj.dcan.2022.12.006).

1. ^ [***a***](#cite_ref-fraleigh95_3-0) [***b***](#cite_ref-fraleigh95_3-1) J. B. Fraleigh, and R. A. Beauregard, Linear Algebra. Chapter 10, Addison-Wesley Publishing Company, 1995.

This article related to telecommunications is a stub. You can help Wikipedia by adding missing information.

- [v](https://en.wikipedia.org/wiki/Template:Telecomm-stub)
- [t](/source/Template_talk%3ATelecomm-stub)
- [e](https://en.wikipedia.org/wiki/Special:EditPage/Template:Telecomm-stub)

---
Adapted from the Wikipedia article [Triangular network coding](https://en.wikipedia.org/wiki/Triangular_network_coding) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Triangular_network_coding?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.