¿Qué técnicas puedes usar para codificar datos en un canal unidireccional con pérdida?

Question

Imagine que tiene un canal de comunicación que es inherentemente con pérdida y unidireccional. Es decir, hay un ruido inherente que es imposible de eliminar que provoca, por ejemplo, que se activen bits aleatorios. También imagine que es de una manera: no puede solicitar la retransmisión.

Pero debe enviar datos a través de ellos independientemente. ¿Qué técnicas puedes usar para enviar números y texto por ese canal?

1. ¿Es posible codificar números para que, incluso con un giro aleatorio de bits, se puedan interpretar como valores cercanos al original (transmisión con pérdida )?

2. ¿Hay alguna manera de enviar una cadena de caracteres (ASCII, por ejemplo) de una manera sin pérdidas ?

Esto es solo por diversión. Sé que puede usar el código Morse o cualquier comunicación binaria de muy baja frecuencia. Sé sobre bits de paridad y sumas de comprobación para detectar errores y volver a intentarlo. Sé que también podrías usar una señal analógica. Tengo curiosidad por saber si hay técnicas interesantes de informática para enviar este material a través de un canal con pérdida.

Answer 1

Dependiendo de algunos detalles que no proporcione sobre su canal con pérdida, recomendaría, primero usar un Código gris para garantizar que los errores de un solo bit provoquen pequeñas diferencias (para cubrir su deseo de mitigar la pérdida en la transmisión con pérdida) y, posiblemente, también codificar la secuencia resultante con algo de "sin pérdida". (== intenta ser una codificación sin pérdidas ;-).

Reed-Solomon y sus variantes son particularmente buenas si su Los episodios de ruido son propensos a ocurrir en pequeñas ráfagas (varios errores de bits dentro de, por ejemplo, un solo byte), que deben interactuar bien con la codificación Gray (ya que los errores de varios bits son los asesinos para el aspecto de `` mitigación de pérdidas '' de Gray, diseñado degradarse con gracia para errores de un solo bit en el cable). Esto se debe a que R-S es intrínsecamente un esquema de bloques, y múltiples errores dentro de un bloque son básicamente lo mismo que un solo error en él, desde el punto de vista de R-S ;-).

RS es particularmente impresionante si muchos de los errores son borrados , por decirlo simplemente , un borrado es un símbolo que probablemente ha sido destrozado en la transmisión, PERO por lo que SI sabe el hecho crucial de que ha sido destrozado. La capa física, dependiendo de cómo esté diseñada, a menudo puede tener pistas sobre ese hecho, y si hay una manera de informar a las capas superiores, puede ser de gran ayuda. Déjame explicarte un poco las borraduras ...:

Digamos para un ejemplo simplificado que un 0 se envía como un nivel de -1 volt y un 1 se envía como un nivel de +1 volt (wrt alguna onda de referencia), pero hay ruido (el ruido físico a menudo puede ser bueno- modelado, pregunte a cualquier ingeniero de comunicación competente ;-); Dependiendo del modelo de ruido, la decodificación puede ser que cualquier cosa -0.7 V y abajo se considera un bit 0, cualquier cosa +0.7 V y arriba se considera un bit, cualquier cosa intermedia se considera un borrado, es decir, se le dice a la capa superior que el bit en cuestión probablemente fue destrozado en la transmisión y, por lo tanto, debe ser ignorado (A veces doy esto como un ejemplo de mi tesis de que a veces las abstracciones DEBERÍAN '' filtrarse '' de manera controlada y arquitectónica: el corolario de Martelli a Ley de abstracciones con fugas ! -).

Un código RS con cualquier relación de redundancia dada puede ser aproximadamente el doble de efectivo para corregir borrados (errores del que se informa al decodificador) que puede serlo para corregir errores que de otro modo serían desconocidos; también es posible mezclar ambos aspectos, corrigiendo ambos algunos borrados y algunos errores desconocidos.

Como punto culminante, los códigos RS personalizados se pueden diseñar (razonablemente fácilmente) y adaptar para reducir la probabilidad de errores no corregidos por debajo de cualquier umbral requerido ? dado un modelo preciso de las características del canal físico en términos de borrados y no detectados errores (incluyendo tanto la probabilidad como el estallido).

No llamaría a toda esta área una "informática". uno, en realidad: cuando me gradué (MSEE, hace 30 años), intentaba principalmente evitar "CS". cosas a favor del diseño de chips, diseño de sistemas, sistemas de radio avanzados, & amp; c; sin embargo, me enseñaron estas cosas (bueno, el subconjunto que ya estaba dentro del ámbito del uso práctico de ingeniería ;-) bastante bien.

Y, solo para confirmar que las cosas no han cambiado tanto en una generación: mi hija acaba de obtener su maestría en ingeniería de telecomunicaciones (centrándose estrictamente en sistemas de radio avanzados): no puede diseñar casi ningún programa serio , algoritmo o estructura de datos (aunque le fue bien en los cursos obligatorios sobre C y Java, hay w

Answer 2

Esta pregunta es el tema de teoría de codificación .

Answer 3

Probablemente uno de los métodos más conocidos es utilizar código de Hamming . Puede que no sea la mejor forma de corregir errores a gran escala, pero es increíblemente fácil de entender.

Answer 4

• Existe la codificación redundante utilizada en medios ópticos que puede recuperar la pérdida de bits
  • ECC también se usa en discos duros y RAM
• El TCP protocolo puede manejar bastante de pérdida de datos con retransmisiones.

Answer 5

O bien Códigos Turbo o Códigos de comprobación de paridad de baja densidad para datos generales, ya que estos se acercan más a acercarse al límite de Shannon - ver wikipedia.

Answer 6

Puede usar los códigos Reed-Solomon .

Answer 7

Consulte también el Protocolo de ventana deslizante (que es utilizado por TCP).

Aunque esto incluye tratar con los paquetes que se reordenan o se pierden por completo, lo que no era parte de la definición del problema.

Answer 8

Como dice Alex Martelli, hay mucha teoría de codificación en el mundo, pero los códigos Reed-Solomon son definitivamente un punto dulce. Si realmente quiere construir algo, Jim Plank ha escrito un buen tutorial sobre la codificación Reed-Solomon . Plank tiene un interés profesional en la codificación con mucha experiencia práctica para respaldarlo.

Answer 9

Iría por algunas de estas sugerencias, seguidas de múltiples envíos de los mismos datos. De esta forma, puede esperar que se introduzcan diferentes errores en diferentes puntos de la transmisión, y puede inferir el número deseado mucho más fácilmente.