Triangular network coding

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.

The main contribution of triangular network coding is to reduce the worst-case decoding computational complexity of

(where n is the total number of data packets being encoded in a coded packet) without degrading the throughput performance, with code rate comparable to that of optimal coding schemes.

Triangular code has also been proposed as Fountain code[2] to achieve near-optimal performance with encoding and decoding computational complexity of

First redundant "0" bits are added at the head and tail of each packet such that all packets are of uniform bit length.

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,[3] with complexity of

The receiver now only needs to perform back-substitution,[3] with worst-case complexity given as

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.