¿Cuál es el porcentaje de error de descodificación del código Hamming (7,4)?

Question

El error de descodificación se produce cuando hay más de 1 bits invertidos. Por lo tanto, si la probabilidad de que un bit sea volteado es $10\%$ entonces el porcentaje de error de decodificación no debería ser $1-0.1\cdot0.9^6\cdot7-0.9^7 = 0.149$ ? Por qué mi libro de texto (de MacKay) afirma que es $7\%$ ?

Answer 1

Dejemos que $E$ denota el caso de que la salida del descodificador sea una codificación que no es la misma que la codificación transmitida, y que $E_i$ denota el evento que el $i$ -en datos bit en el codeword de salida difiere del $i$ -ésimo bit de datos de la palabra clave transmitida. Es evidente que tenemos que $$E = E_1 \cup E_2 \cup \cdots \cup E_k.\tag{1}$$ ya que si ninguno de la $E_i$ entonces los bits de datos de la palabra clave de salida son todos correctos y por lo tanto el codeword de salida debe ser el mismo que el codeword transmitido.

Ahora, en general, los eventos $E_i$ son ni eventos independientes ni equiprobables. El Tasa de error de bits (BER) para los bits de datos decodificados, denotados por $P_b$ aquí, se define como la media aritmética de los $k$ $P(E_i)$ valores. Por lo general, determinar los valores de la $P(E_i)$ o su media $P_b$ excepto para los códigos de longitudes de bloque muy cortas, mientras que $P(E)$ la probabilidad de que la salida del decodificador no sea la misma que la palabra de código transmitida, es más fácil de determinar (o de sobrepasar para decodificadores de distancia limitada que son propensos a fallo del decodificador). Es sencillo demostrar que $$\frac 1k P(E) \leq P_b \leq P(E)\tag{2}$$ que en el caso que desconcierta al OP nos dice que la BER debe estar entre $3.725\%$ y $14.9\%$ . Se puede decir más en esta caso particular, sin embargo, las palabras clave de un $[7,4]$ Código Hamming están muy relacionados con lo que se llama un conjunto de señales biortogonales en la literatura de las comunicaciones (las palabras clave del $[8,4]$ código Hamming ampliado son exactamente un conjunto de señales biortogonales). Para un conjunto de señales biortonales, la BER es casi $\frac 12P(E)$ y, por lo tanto, el $7\%$ La BER que se afirma en el texto de Mackay puede explicarse como coherente con este resultado, con algunas diferencias porque el $[7,4]$ El código Hamming no es del todo un conjunto de señales biortogonales, y porque $P_b$ es no exactamente $\frac 12 P(E)$ para un conjunto de señales biortogonales.

Los masoquistas que realmente quieran profundizar en los detalles pueden encontrar información sobre los conjuntos de señales ortogonales y biortogonales y su relación con los códigos Reed-Muller de primer orden (de cuya clase el $[8,4]$ código Hamming ampliado es un ejemplo) puede encontrar alguna información básica en las páginas 161-180 de esta antigua nota de lectura mía .