coding theory Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and computer data storage, data sto ...

, triangular network coding (TNC) is a non-linear

network coding In computer networking, linear network coding is a program in which intermediate nodes transmit data from source nodes to sink nodes by means of linear combinations. Linear network coding may be used to improve a network's throughput, efficiency, ...

based packet coding scheme introduced by .. Previously, packet coding for network coding was done using linear network coding (LNC). The drawback of LNC over large

finite field In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field (mathematics), field that contains a finite number of Element (mathematics), elements. As with any field, a finite field is a Set (mathematics), s ...

is that it resulted in high encoding and decoding

computational complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations ...

. While linear encoding and decoding over

GF(2) (also denoted \mathbb F_2, or \mathbb Z/2\mathbb Z) is the finite field with two elements. is the Field (mathematics), field with the smallest possible number of elements, and is unique if the additive identity and the multiplicative identity ...

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)

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 In telecommunication and information theory, the code rate (or information rateHuffman, W. Cary, and Pless, Vera, ''Fundamentals of Error-Correcting Codes'', Cambridge, 2003.) of a forward error correction code is the proportion of the data-stre ...

comparable to that of optimal coding schemes. Triangular code has also been proposed as Fountain code to achieve near-optimal performance with encoding and decoding computational complexity of

O(n\log n)

. It has been further shown that triangular based fountain code can even outperform optimized Luby transform code.

Coding and decoding

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, 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 In mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of row-wise operations performed on the corresponding matrix of coefficients. This method can 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,''J. B. Fraleigh, and R. A. Beauregard, Linear Algebra. Chapter 10, Addison-Wesley Publishing Company, 1995. with complexity of

O(n^3)

, where

n

is the number of packets, can be bypassed. The receiver now only needs to perform ''back-substitution,'' with worst-case complexity given as

O(n^2)

for each bit location.

References

Coding theory Finite fields Information theory {{telecommunications-stub