Codificación de red

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 22 de octubre de 2016; las comprobaciones requieren 2 ediciones .

La codificación de redes  es una rama de la teoría de la información que estudia la cuestión de optimizar la transmisión de datos a través de una red utilizando técnicas para cambiar los paquetes de datos en los nodos intermedios.

Fundamentos de la codificación de redes

Para explicar los principios de la codificación de redes, utilice el ejemplo de una red mariposa, propuesto en el primer trabajo sobre codificación de redes "Flujo de información de red" [1] . Considere la red que se muestra en la figura, en la que hay una o dos fuentes que generan los paquetes A y B, que llegan a la entrada de la red mariposa. Los primeros nodos encargados de transmitir información transmiten un paquete cada uno (A a la izquierda y B a la derecha) en la entrada a los nodos finales de los destinatarios. También pasan estos paquetes a un nodo intermedio que, en lugar de enviar dos paquetes a la vez (y perder tiempo), combina estos paquetes, por ejemplo, utilizando la operación XOR y transmite más.

Los nodos de destino tienen la capacidad de recuperar los paquetes originales a partir de información sobre un solo paquete recibido y una combinación de ellos. Como resultado, aumenta el rendimiento de la red: se pueden transmitir dos paquetes a dos destinatarios simultáneamente (para cada ciclo), aunque la sección mínima de la red contiene solo tres canales de transmisión de datos.

Codificación de red aleatoria

A diferencia de la codificación de red estática, cuando el destinatario conoce todas las manipulaciones realizadas con el paquete, también se considera el problema de la codificación de red aleatoria cuando esta información es desconocida. La autoría de los primeros trabajos sobre este tema pertenece a Kötter, Krzyszang y Silva [2] . Este enfoque también se denomina codificación de red con coeficientes aleatorios: cuando los coeficientes bajo los cuales los paquetes iniciales transmitidos por la fuente se incluirán en los paquetes resultantes recibidos por el destinatario, con coeficientes desconocidos que pueden depender de la estructura de red actual e incluso de la distribución aleatoria. decisiones tomadas en los nodos intermedios.

El método principal es la inclusión en el paquete transmitido de información adicional que identifica el paquete dentro de una determinada sesión (se cree que los paquetes que pertenecen a una sola sesión pueden combinarse). Por ejemplo, podría ser un simple campo de bits. Para la red mariposa discutida anteriormente, este campo de bits puede constar de dos bits para cada paquete:

Paquete campo de bits
diez
0 1
once

El primer destinatario recibirá dos paquetes con campos de bits "1 0" y "1 1", el segundo destinatario recibirá "0 1" y "1 1". Utilizando este campo como información sobre los coeficientes de la ecuación lineal de los paquetes, el receptor puede recuperar los paquetes originales si se transmitieron sin errores.

Protección de la información contra la distorsión

Para la codificación de red no aleatoria, se pueden utilizar técnicas estándar antiinterferencias y antialiasing utilizadas para la transmisión simple de información a través de una red. Sin embargo, como se señala en el artículo “Esquemas de codificación LDPC para error” [3] , los paquetes recuperados de combinaciones lineales tienen una mayor probabilidad de ser recibidos con error, ya que se ven afectados como probabilidad de error en dos paquetes utilizados para la recuperación de información en una vez.

Considerando la red "mariposa", se puede demostrar que para el primer destinatario la probabilidad de recibir un paquete sin errores es mayor que para el paquete , incluso si asumimos las mismas probabilidades de error, pero distintas de cero, en los paquetes recibidos y .

Para reducir este efecto, los autores proponen modificar el método de decodificación iterativa de los paquetes A y B (por ejemplo, utilizando la codificación LDPC ), cuando las iteraciones de decodificación de paquetes se realizan simultáneamente y los decodificadores intercambian información sobre las probabilidades de error en un paquete específico. pedacitos Para deshacerse por completo de este efecto, los autores también proponen dividir los paquetes fuente en varias partes y transferirlos de varias maneras. Como mostró el experimento numérico, esto realmente iguala las probabilidades de decodificación de paquetes.

Los métodos utilizados para la decodificación en la codificación de red aleatoria consideran todos los paquetes recibidos como un solo objeto (a menudo una matriz) construido a partir de los paquetes de fila recibidos. Si la primera parte del paquete es un campo de bits, entonces las operaciones con la matriz se reducen, primero, a llevar su lado izquierdo a una forma diagonal (usando el método de Gauss ), y luego a corregir errores en el lado derecho de la matriz. . Para corregir errores, se pueden usar códigos de rango , que pueden corregir no solo errores en las columnas de la matriz (debido a bits de datos recibidos incorrectamente), sino también errores en las filas de la matriz (debido a errores de transmisión en el campo de bits) .

Notas

  1. ↑ Ahlswede, R.; Ning Cai; Li, S.-YR; Yeung, RW, " Flujo de información de red ", Teoría de la información, IEEE Transactions on, vol.46, no.4, pp.1204-1216, julio de 2000
  2. ↑ Artículos
    • Koetter R., Kschischang FR Codificación de errores y borrados en la codificación de red aleatoria// Simposio internacional IEEE sobre teoría de la información. Proc.ISIT-07.-2007.- P. 791-795.
    • Silva D., Kschischang FR Uso de códigos métricos de rango para la corrección de errores en la codificación de redes aleatorias // Simposio internacional IEEE sobre teoría de la información. proc. ISIT-07. — 2007.
    • Koetter R., Kschischang FR Codificación de errores y borrados en la codificación de red aleatoria // IEEE Transactions on Information Theory. - 2008 - V.IT-54, N.8. - Pág. 3579-3591.
    • Silva D., Kschischang FR, Koetter R. A Rank-Metric Approach to Error Control in Random Network Coding // IEEE Transactions on Information Theory.- 2008- V. IT-54, N. 9.- P.3951-3967.
  3. ↑ Kang J., Zhou B., Ding Z., Lin S. Esquemas de codificación LDPC para el control de errores en una red de multidifusión

Véase también