Código binario para los errores esperados de 1 bit

Question

Considere un código $C$ que asigna de forma única cada número binario de k dígitos $P=p_1 p_2 \cdots p_k$ a algún número binario de k dígitos $Q=q_1 q_2 \cdots q_k$ . Es decir, el código es $C(P) = Q$ y $C^{-1}(Q) = P$ .

Hay $2^k!$ tales códigos.

Ahora considere que las palabras de código se transmiten a través de un canal ruidoso que volteará exactamente 1 bit en cada palabra de código Q, dando lugar a otra palabra de código Q'. Esta se decodificará en $C^{-1}(Q')= P' \neq P$ .

Me interesa el código que minimiza $|P' - P|$ para todos $P$ . ¿Cómo puedo construirlo? Agradezco cualquier sugerencia.

(Mi intuición es que la identidad que mapea cada $P$ sobre sí mismo, es decir, $\forall P: C(P)=P$ es óptimo, pero no sé cómo demostrarlo. Espero que mi pregunta sea clara, no soy matemático. Estaré encantado de explicarlo. Para aclarar de antemano: No quiero corregir el error ni detectar qué bit se ha volteado, sólo minimizar el error).

Answer 1

Si está midiendo |P-P'| como un entero, entonces algo como un código gris puede ser mejor que la función de identidad.

Por ejemplo:

La codificación gris de David:

P Q    P'             relative
       with one error errors
0 0000 {1, 2, 3, 4}   {+1, +2, +3, +4}
1 0001 {0, 5, 6, 7}   {-1, +4, +5, +6}
2 0010 {0, 7, 8, 9}   {-2, +5, +6, +7}
3 0100 {0, 6, 9, a}   {-3, +3, +6, +7}
4 1000 {0, 5, 8, a}   {-4, +1, +4, +6}
5 1001 {1, 4, b, c}   {-4, -1, +6, +7}
6 0101 {1, 3, b, d}   {-5, -3, +5, +7}
7 0011 {1, 2, c, d}   {-6, -5, +5, +6}
8 1010 {2, 4, c, e}   {-6, -4, +4, +6}
9 0110 {2, 3, d, e}   {-7, -6, +4, +5}
a 1100 {3, 4, b, e}   {-7, -6, +1, +4}
b 1101 {5, 6, a, f}   {-6, -5, -1, +4}
c 1011 {5, 7, 8, f}   {-7, -5, -4, +3}
d 0111 {6, 7, 9, f}   {-7, -6, -4, +2}
e 1110 {8, 9, a, f}   {-6, -5, -4, +1}
f 1111 {b, c, d, e}   {-4, -3, -2, -1}
worst errors:          -7, +7

codificación de la identidad:

P Q    P'             relative
       with one error errors
0 0000 {1, 2, 4, 8}   {+1, +2, +4, +8}
1 0001 {0, 3, 5, 9}   {-1, +2, +4, +8}
2 0010 {3, 0, 6, a}   {+1, -2, +4, +8}
3 0011 {2, 1, 7, b}   {-1, -2, +4, +8}
...
worst errors:          -8, +8
median absolute error: 3.

Como puede ver, el peor caso de |P-P'| para la codificación de tipo gris es 7, que es mejor que el peor caso de |P-P'| de 8 para el mapeo de identidad.

Por lo tanto, C(P)=P no es óptimo para k=4 (y, sospecho, para todos los k más altos).

Si está más interesado en el media o el mediana error |P-P'| sobre cada código y sobre cada posible error de un solo bit -- o, como Jyrki Lahtonen insinúa, el "error circular" (|P-P'| mod 2^k) -- entonces quizás un código gris estándar "reflejado" puede ser mejor.

No estoy seguro de por qué no quieres hacer que Q sea unos pocos bits más largo que P -- entonces puedes aplicar códigos Hamming y corregir cualquier error de un solo bit, dando error cero.