“Triangular network coding”的意思、由来-开放百科全书

In coding theory, triangular network coding (TNC) is a network coding based packet coding scheme introduced by {{harvtxt|Qureshi|Foh|Cai|2012}}.^[1]

Previously, packet coding for network coding was done using linear network coding (LNC). The drawback of LNC over large finite field is that it resulted in high encoding and decoding computational complexity. While linear encoding and decoding over GF(2) alleviates the concern of high computational complexity, coding over GF(2) comes at the tradeoff cost of degrading throughput performance.

Triangular network coding therefore essentially addresses the high encoding and decoding computational complexity without degrading the throughput performance, with code rate comparable to that of linear network coding.

Coding and decoding

In TNC, coding is performed in two stages. First redundant "0" bits are selectively added at the head and tail of each packet such that all packets are of uniform bit length. Then the packets are XOR coded, 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.

In essence, the TNC decoding process, like the LNC decoding process involves 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,^[2] with complexity of

, where

is the number of packets, can be bypassed. The receiver now only needs to perform back-substitution,^[3] with complexity given as

for each bit location.

References

1. ^{{citation | last1 = Qureshi | first1 = Jalaluddin | last2 = Foh | first2 = Chuan Heng | last3 = Cai | first3 = Jianfei | doi = 10.1109/SECON.2012.6275780 | mr = | issue = | journal = IEEE SECON | pages = 134–142 | title = Optimal Solution for the Index Coding Problem Using Network Coding over GF(2) | volume = | year = 2012| arxiv = 1209.6539}}.
2. ^J. B. Fraleigh, and R. A. Beauregard, Linear Algebra. Chapter 10, Addison-Wesley Publishing Company, 1995.
3. ^J. B. Fraleigh, and R. A. Beauregard, Linear Algebra. Chapter 10, Addison-Wesley Publishing Company, 1995.