Cualquier código de corrección de error en tal situación?

Question

Estoy buscando un tipo de código de corrección de error o una solución que se puede corregir mi palabra en este caso:

Mi mensaje tiene k bits, y 2*k bits de la palabra (el precio es de 1/2) es producida por el generador de la matriz, por ejemplo, k=5, por lo que los rendimientos de 10 bits de la palabra 1001100111. Si la palabra es borrado por alguna razón y se convierte en 1xx1x00xx1 (similar a la palabra transmitida a través de los Binarios de Borrado de Canal, y x es desconocido, '0' o '1'), aún así puedo corregir todas las "x bits" en tal situación, como la tasa de error de bit es de 1/2?

He leído acerca de algunas código de corrección de error, tales como el bloque de código, código convolucional y LDPC y tengo las siguientes preguntas:

1. Todos estos ECC tienen aplicación práctica en la comunicación, por lo que todavía funcionan cuando el BER es cerca de 1/2 (creo que BER es imposible, así que alta)?

2. ¿Hay alguna solución viable para mi caso? De hecho, mi mensaje es de 30 bits y puedo presentar a otro de 30 bits de redundancia como bits de paridad. Aún así puedo corregir mi palabra incluso si la mitad de los bits están dañados?

Ninguna de las guías o sugerencias se agradece!

Answer 1

No, eso no es posible.

Supongamos, por el contrario, que tenemos como código. Porque podemos borrar el $k$ últimos bits de un código de palabras, por el principio del palomar todas las $2^k$ posibles combinaciones de la primera $k$ bits debe ser utilizado por exactamente una palabra clave. Sin pérdida de generalidad podemos asumir que el primer $k$ bits en cada palabra son la misma mensaje de bits. También podemos suponer que el mensaje de $0^k$ tiene la palabra $0^{2k}$. (Si no, lo podemos hacer así por el uniforme de la negación de ciertas posiciones de bits en todos los codewords).

¿Cuál es la segunda mitad de la palabra de mensaje de $0^{k-1}\,1$? Si borramos el 1 en la primera mitad y todo pero un único bit en la última mitad de la palabra, debe haber al menos 1 a la izquierda; de lo contrario no podríamos distinguirlo de mensaje de $0^k$. Pero eso sólo puede ser el bit que no se borre en la segunda mitad, y este razonamiento tiene, sin importar la posición de la broca, por lo $0^{k-1}\,1^{k+1}$ es una palabra en clave.

Por bastante similar razonamiento, $1\,0^{k-1}\,1^k$ debe ser una palabra clave.

Pero $0^{k-1}\,1^{k+1}$ $1\,0^{k-1}\,1^k$ parecen iguales cuando borramos la primera $k$ bits. Esta es una contradicción.

Answer 2

Como otros lo han explicado, no se puede hacer esto con absoluta certeza, porque entonces se le golpeas tu cabeza contra la pared de la distancia de Hamming. Sin embargo, `rateless códigos puede hacer esto con una probabilidad muy alta con la tasa efectiva de un epsilon más de 1/2, y más bloques de datos. En otras palabras, la bola de nieve comentario es una buena.

En cierto sentido, la filosofía (que en cierta medida fue un cambio de paradigma para la ECC diseñadores) es que el enfoque basado en la optimización de la distancia de Hamming es que de jugar el juego en contra de un ser inteligente, el mal, el adversario, el que borra (o alterna), precisamente, los bits que va a dar problemas. En la comunicación natural, el verdadero rival es el más benigno de ruido aleatorio que ocurre en la naturaleza.

Buscar la fuente de los códigos de y (para una mejora) Raptor Códigos para las definiciones y los papeles con los análisis probabilistas (si se puede soportar el regodeo de una persona, que insiste en llamar operación XOR bit a bit como una transformación nombrado después de él mismo).

Answer 3

La manera de describir lo que usted está usando un bloque de código, la búsqueda libre de errores de decodificación y por lo tanto puede comprobar el Hamming obligado. $$ A_2(n,d) = \frac{2^n}{\sum_{j=0}^{\lfloor(d-1)/2\rfloor}\binom{n}{j}} $$

Aquí tenéis $n=10$ y desea que cada par de codewords a ser distinguible incluso si 5 bits se perderá, por lo que es necesario un mínimo de la distancia de Hamming $d=6$, que delimita el número de los distintos codewords a los 18 años, por lo que no será capaz de codificar todos los 5 bits de los mensajes.

Con un largo bloque de mensaje es aún peor, $A_2(30,16)<2^{14}$.

Para $k<4$ el obligado no es tan apretado, pero como @HenningMakholm ya demostró no ser capaz de construir un código al $k>1$.

Para $k=1$ el código $\{01,10\}$ le permite corregir cualquier un poco borrado, técnicamente permite decodificar correctamente cuando la "tasa de error de bit es de 1/2" en el mensaje recibido.