Construcción de código Hamming - norman-ipn/Errores GitHub Wiki

Construcción del código Hamming

El procedimiento de construcción del código se explica en relación con las sucesivas columnas de la tabla representada en la página siguiente. • Sea una palabra inicial de 12 bits: b11 b10 b9 b8 b7 b6 b5 b4 b3 b2 b1 b0. • Se trata de construir una palabra ampliada por un conjunto de paridades parciales, que se entremezclan con los bits de la palabra inicial; para ello, es necesario numerar en binario los bits de la palabra ampliada [columna (1)]. Para facilitar la descripción se utiliza la denominación |número| para indicar el que numera los bits de la palabra ampliada.
Habida cuenta de que las paridades parciales se refieren a las posiciones de los «unos» en el |número| de cada bit, en la columna (2) se han sustituido los «ceros» por – y los «unos» por símbolos diversos según su posición ( @ , * , ∆ , # , & ) a los que denominaremos grafismos. [Esta representación gráfica es absolutamente superflua una vez comprendido el método.] • El primer bit de la palabra ampliada (numerado con 00…) se reserva para la paridad global y es el último que se calcula. Los bits de la palabra ampliada que solamente tienen un «uno» en su |número| (es decir, los que tienen un solo grafismo) se reservan para las paridades parciales [columna (3)].
• En el resto de los bits se colocan ordenadamente los dígitos de la palabra inicial (de menor a mayor valor significativo, tal como están ordenados sus |números|) [columnas (4) y (5)]. Si es preciso se continúa la numeración de bits, hasta que quepan todos los de la palabra inicial, reservando siempre los bits cuyo |número| contiene un solo «uno» para paridades parciales. • Cada paridad parcial corresponde a un |número| con un solo «uno» y se calcula sobre los bits cuyo |número| contiene un «uno» en la misma posición; es decir, estarán reservados para paridad parcial los bits con un solo grafismo y para calcular una de ellas tomaremos los bits señalados con el mismo grafismo y hallaremos la paridad del conjunto de ellos.
La paridad parcial P1 es la de los bits cuyo |número| acaba por «uno», es decir, aquellos cuyo grafismo es &: b11 b10 b8 b6 b4 b3 b1 b0. La paridad parcial P2 es la de los bits cuyo |número| tiene un «uno» en penúltima posición, o sea cuyo grafismo es : b10 b9 b6 b5 b3 b2 b0. La paridad P3 corresponde a un «uno» en antepenúltima posición y su grafismo es ∆: b10 b9 b8 b7 b3 b2 b1; P4 se refiere al grafismo *:
b10 b9 b8 b7 b6 b5 b4 y P5 a @: b11.

• Una vez calculadas y puestas en su lugar las paridades parciales, se calcula la paridad global de la palabra y se coloca en el bit menos significativo (|número| = 0). De esta forma, se tiene la palabra ampliada completa en código Hamming de distancia mínima 4; bien entendido que, conforme a la numeración de los bits, las columnas están ordenadas del bit menos significativo (el primero de arriba) al más significativo (el último de abajo).

hamming

Es fácil comprobar la distancia mínima entre dos palabras de este código; consideremos dos palabras iniciales diferentes (cuya distancia sea menor de 3):

  • si se diferencian en un solo bit, diferirán también en, al menos, dos bits de paridad parcial (ya que el número de orden del bit modificado tendrá, por lo menos, dos unos),
  • si tienen dos bits diferentes, lo será también, al menos, uno de los bits de paridad (ya que los números de orden de los bits modificados diferirán, cuando menos, en un uno), o sea que la distancia entre dos palabras ampliadas no puede ser inferior a 3; además, como el código incluye la paridad global, su distancia será siempre múltiplo de 2, es decir, entre dos palabras ampliadas habrá una distancia mínima de 4.