三角ネットワークコーディング

符号理論において、三角ネットワーク符号化（TNC ）は、Qureshi、Foh、Cai（2012）によって導入された非線形ネットワーク符号化ベースのパケット符号化方式である。 ^{[1]以前は、ネットワーク符号化のパケット符号化は線形ネットワーク符号化（LNC）を使用して行われていた。大きな}有限体 上のLNCの欠点は、符号化と復号化の計算量が高くなることである。GF (2)上の線形符号化と復号化は計算量が高いという懸念を軽減するが、GF(2)上の符号化はスループット性能を低下させるというトレードオフを伴います。

三角ネットワーク コーディングの主な貢献は、スループット パフォーマンスを低下させることなく、最悪の場合のデコード計算の複雑さを に削減することです(ここで、nはコード化されたパケットでエンコードされるデータ パケットの合計数です)。コード レートは最適なコーディング スキームと同等です。 ${\displaystyle O(n^{3})}$${\displaystyle O(n^{2})}$

三角符号は、符号化と復号化の計算複雑度が で、ほぼ最適なパフォーマンスを実現するFountain 符号^[2]としても提案されています。さらに、三角ベースの Fountain 符号は、最適化されたLuby 変換符号​​よりも優れたパフォーマンスを発揮できることが示されています^[2]。${\displaystyle O(n\log n)}$

TNC では、コーディングは 2 段階で実行されます。最初に、すべてのパケットのビット長が均一になるように、各パケットの先頭と末尾に冗長な「0」ビットが追加されます。次に、パケットはビットごとにXOR コーディングされます。各パケットに追加された冗長な「0」ビットが三角形のパターンを生成するように、「0」ビットが追加されます。

本質的には、TNC 復号化プロセスは、LNC 復号化プロセスと同様に、ガウス消去法を伴います。ただし、TNC のパケットは、結果として得られる符号化パケットが三角形のパターンになるように符号化されているため、複雑度 （パケット数）の三角形化 [3] の計算プロセスをバイパスでき^ます。受信機は、各ビット位置について最悪の場合の複雑度が として与えられるバック置換^[3]を実行するだけで済みます。 ${\displaystyle O(n^{3})}$${\displaystyle n}$${\displaystyle O(n^{2})}$