Tareas

138

7.12.

C´digos de Hamming o

Los c´digos de Hamming, introducidos por Golay en 1949, permiten reo ducir el tiempo y el espacio de decodificaci´n. Para su definici´n, se precisa o o introducir el concepto de tasa de informaci´n de un c´digo lineal C(n, k). o o Se llama as´ al cociente R = k/n. Representa el n´mero de bits de informaı u ci´n por s´ o ımbolo que porta cada palabra-c´digo.Obviamente, a igualdad de o capacidad correctora, interesa m´s el c´digo con tasa m´s pr´xima a 1. a o a o Recordemos que la redundancia de un c´digo lineal viene dada por r = o n − k, donde k es la dimensi´n, y que r es el n´mero de filas de una matriz o u de control.

Definici´n 7.12.1. Fijado r, se llama c´digo de Hamming de redundancia r o o al c´digo lineal con la mayor tasa posible entretodos los que son 1-correctores. o Al tratarse de c´digos lineales 1-correctores, se sigue que la matriz de o control no puede tener menos de 3 columnas linealmente dependientes. En efecto, de ser la capacidad correctora 1, se sigue que d ≥ 3, y recordemos que el n´mero m´ u ınimo de columna linealmente dependientes en la matriz de control coincide con el valor de d. Como r = n − k, la tasa deinformaci´n o k n−r r viene dada por R = n = n = 1 − n . Por tanto, al aumentar n aumenta la tasa R, lo que nos dice que n debe ser lo m´s grande que sea posible. a No es dif´ construir este tipo de c´digos. Una matriz de control s´lo ıcil o o puede contener conjuntos de 3 o m´s columnas linealmente dependientes. En a consecuencia, debe cumplir: (a) Todas la columnas deben ser diferentes. (b) Ningunacolumna es nula. (c) Ninguna columna puede ser un m´ltiplo de otra. u (d) Las columnas son de r (= n − k) coordenadas de A.

139 (e) La matriz de control debe tener el mayor n´mero posible de columnas, u para que la tasa de informaci´n sea lo m´s pr´xima a 1 que sea posible. o a o q r − 1 es el n´mero de columnas no nulas diferentes con r coordenadas. Si u m es el n´mero total de columnas queverifican las condiciones anteriores, u cada una de ellas, al multiplicarlas por uno de los q − 1 escalares no nulos, r −1 da otras q − 1 columnas diferentes. Por tanto, m(q − 1) = q r − 1 ⇒ m = qq−1 es el n´mero m´ximo de columnas que podr´ u a ıamos poner en la matriz H. Por tanto, el valor de los par´metros de un c´digo de Hamming (n, k) viene dado a o por:   n = qr −1 , q−1  k =n−r =
q r−1 q−1

− r.

Se deduce que no existen c´digos de Hamming para cualesquiera (n, k) ya o que la construcci´n depende de r = n − k. o

7.13.

Correcci´n con un c´digo de Hamming o o

Vamos a ver que no se necesita mantener en memoria la tabla de s´ ındromes, sino s´lo la matriz de control. Supongamos que se transmite la pao labra-c´digo x y se recibe y, donde y = x + e, siendo e el errorque se ha o producido. Si e es una palabra de peso 1 (porque el c´digo de Hamming es o 1–corrector), se tiene Hy t = H(xt + et ) = Het , pues Hxt = 0. Si el error e = 0, obviamente Het = 0 ⇒ Hy t = 0 y corregimos aceptando y como correcta. Pero si, como hemos dicho antes, e es de peso 1, entonces e = α · ei (α = 0), donde ei denota la cadena con todas sus componentes nulas salvo la que ocupa ellugar i–´simo que es igual a α, e t entonces He = αhi , donde hi es la columna i–´sima de H. e Esta observaci´n permite idear un m´todo de correcci´n simple . o e o – Al recibir y se calcula Hy t .

140 – Si Hy t = 0, se acepta y como el mensaje enviado. – Si Hy t = st = 0 se compara st con las columnas de H. Si existe i, tal que st = αhi , entonces e es una cadena de longitud n con α en laposici´n o i-´sima y cero en las otras. Se ha producido un error y corregimos y e como y − e. – Si Hy t = st no es un m´ltiplo de alguna columna de H es que ha habido u m´s de un error. a En el caso de c´digos binarios de Hamming, a´n podemos mejorar este o u m´todo. e Las columnas de H son vectores de r = n − k componentes pertenecientes a 0, 1 = Z2 . Las ordenamos de modo que la columna i sea la...