Codificación de redes triangulares

En teoría de la codificación , la codificación de red triangular ( TNC ) es un esquema de codificación de paquetes basado en codificación de red no lineal introducido por Qureshi, Foh y Cai (2012) . ^{[ 1 ]} Anteriormente, la codificación de paquetes para la codificación de red se realizaba utilizando codificación de red lineal (LNC). El inconveniente de LNC sobre un campo finito grande es que resultaba en una alta complejidad computacional de codificación y decodificación . Si bien la codificación y decodificación lineal sobre GF(2) alivia la preocupación de la alta complejidad computacional, la codificación sobre GF(2) conlleva el costo de degradar el rendimiento de la transmisión.

La principal contribución de la codificación de red triangular es reducir la complejidad computacional de decodificación en el peor de los casos.${\displaystyle O(n^{3})}$a${\displaystyle O(n^{2})}$(donde n es el número total de paquetes de datos que se codifican en un paquete codificado) sin degradar el rendimiento de transmisión, con una tasa de codificación comparable a la de los esquemas de codificación óptimos.

También se ha propuesto el código triangular como código Fountain ^{[ 2 ]} para lograr un rendimiento casi óptimo con una complejidad computacional de codificación y decodificación de${\displaystyle O(n\log n)}$. Se ha demostrado además que el código de fuente triangular puede incluso superar al código de transformación de Luby optimizado . ^{[ 2 ]}

En TNC, la codificación se realiza en dos etapas. Primero, se agregan bits "0" redundantes al principio y al final de cada paquete, de manera que todos los paquetes tengan una longitud de bits uniforme. Luego, los paquetes se codifican mediante XOR , bit a bit. Los bits "0" se agregan de tal manera que estos bits "0" redundantes agregados a cada paquete generan un patrón triangular .

En esencia, el proceso de decodificación TNC, al igual que el proceso de decodificación LNC, implica la eliminación gaussiana . Sin embargo, dado que los paquetes en TNC se han codificado de tal manera que los paquetes codificados resultantes tienen un patrón triangular, el proceso computacional de triangularización, ^{[ 3 ]} con una complejidad de${\displaystyle O(n^{3})}$, dónde${\displaystyle n}$es el número de paquetes, se puede omitir. El receptor ahora solo necesita realizar una sustitución inversa, ^{[ 3 ]} con una complejidad en el peor de los casos dada por${\displaystyle O(n^{2})}$para cada ubicación de bit.