¿Qué algoritmo para errores extremadamente altos sin ráfaga?

Question

Tengo una secuencia binaria que tiene una tasa de error muy alta. La tasa de error es del 50%, lo que significa que cada bit tiene una probabilidad del 50% de ser volteado. El error no se produce en ráfagas y es completamente aleatorio, por lo que los códigos Reed & # 8211; Solomon no funcionarían bien.

¿Qué esquema o algoritmo debo aplicar a la secuencia? No me importan los gastos generales en absoluto.

Todo esto es teórico, por lo que no tiene sentido preguntar si podría reducir el error de la transmisión.

EDIT

No digas que no es posible, la primera respuesta te dice que es posible con canal ruidoso teorema de codificación.

Answer 1

El teorema de codificación de canal ruidoso dice que en realidad se puede lograr la capacidad de Shannon para el canal. ¡ no dice que el canal tiene una capacidad distinta de cero!

Si aleatoriza el 100% de los bits en el canal, el 50% de ellos no se modificarán, por lo que solo voltea un 50% aleatorio de los bits. Debería ser obvio que no puede enviar ningún dato a través de dicho canal: su capacidad de Shannon es cero.

Answer 2

Si la tasa de error es del 50%, entonces eso es básicamente ruido aleatorio, ¿no? Quiero decir, considera tratar de transmitir un solo bit. Si envía una secuencia infinita del bit correcto, con una tasa de error del 50% obtendrá medio 1s y medio 0s si el bit correcto es 1 o 0.

Si en realidad es inferior al 50% (por ejemplo, el 50% de los bits serán '' aleatorios '' en lugar de '' invertidos ''), entonces puede repetir los datos: transmita cada bit 128 veces y descubra que obtiene más de por cada 100 bits recibidos. Esa es la solución simple de codificar, enormemente ineficiente, no matemática en absoluto :)

Answer 3

Bueno, el objetivo de la corrección de errores de Reed-Solomon es que la mayoría de los errores del mundo real se producen en ráfagas, por lo que se intercalan y desentrelazan los datos. Si sus errores son completamente aleatorios, es decir, distribuidos por Poisson, entonces simplemente agregar redundancia a la secuencia de una manera directa y matemáticamente eficiente funcionará. Una cosa que podría ver es algún tipo de modelo oculto de Markov, como código trellis. Esto es básicamente una forma matemáticamente eficiente de agregar redundancia.

Además, eche un vistazo al teorema de codificación de canales ruidosos. Estrictamente hablando, no lo hace no se aplique a datos digitales, pero si su fuente de estos bits es algún proceso analógico, o si pudiera modelar sus bits como si fueran el resultado de algún proceso analógico, podría darle una idea en lo que podría ser lo mejor que podría hacer. Esto evitaría que pierdas el tiempo tratando de hacerlo mejor de lo que es matemáticamente posible.

Answer 4

Cuando el canal se acerca al 50% de la tasa de ruido real, ya no es posible transmitir ninguna información. A la respuesta de Jon Skeet, si la tasa de error es inferior al 50% de ruido, puede obtener datos haciendo ráfagas más largas de los datos previstos de forma redundante y estadísticamente observando el resultado con cierto nivel de confianza en el valor original. La longitud de ráfaga necesaria y los niveles de confianza para una longitud dada se derivarían en función de una caracterización del ruido. Sin embargo, comprenda que lo que está haciendo aquí es reducir efectivamente la velocidad de datos para mejorar la relación señal / ruido neta de la transmisión transmitida.

En su pregunta, es posible que haya descartado esto como una opción, pero un mejor esquema de codificación podría basarse en la existencia (o no) relativa del flujo de datos en sí. En otras palabras, para transmitir uno binario ... envíe una secuencia alterna de 1/0. Para enviar un cero, no envíe nada o quizás envíe un nivel constante. La idea es que enviar (y recibir) cualquier cosa representa un estado y enviar (y recibir) nada representa el otro estado. Esto se parecería efectivamente a un tipo de codificación bipolar de los datos.

Answer 5

Si su tasa de error es del 50%, la secuencia de bits ES aleatoria y NO CORRELA la secuencia de bits original. Es como si estuvieras haciendo XOR a la secuencia con una secuencia de bits completamente aleatoria, y el resultado es completamente aleatorio. Y no hay nada que puedas hacer al respecto.

La tasa de cambio debe ser inferior al 50% para que cualquier esquema funcione. Por supuesto, podría estar POR ENCIMA del 50%, pero luego puede invertir la transmisión y luego procesarla como si la tasa de error fuera inferior al 50%.

Si los errores son completamente aleatorios y muy frecuentes (por ejemplo, el 25% de los bits se voltean), es muy difícil encontrar un esquema robusto de detección de errores. Debe agregar una cantidad significativa de redundancia.

Answer 6

¿Has buscado códigos turbo?

- MarkusQ

Doh! Leí mal eso como 50% aleatorizado, no 50% invertido.

Answer 7

Si exactamente el 50% de los bits se voltea en cualquier transmisión dada, en lugar de que cada bit se voltee con un 50% de probabilidad, puede enviar un bit de información enviando una transmisión de dos bits: - envíe un 0 como 00 y un 1 como 01. Si el primer bit de la palabra de código recibida es 1, el otro bit se desbloquea.