Siguiente: Códigos de ráfagas Arriba: Códigos cíclicos Anterior: Codificación y decodificación

Códigos de Golay

Definición 8.3   Sea $\mathbb{K}$ un campo finito. Un código-$(n,k)$ $C$ se dice perfecto para $t$ errores si para cualquier palabra de longitud $n$ existe una única palabra de código que diste de ella en a lo sumo $t$. Es decir,

$$\forall {\bf w}\in\mathbb{K}^n\ \exists {\bf v}\in C:\ d_n({\... ..._n({\bf u},{\bf w})\leq t\ \Rightarrow\ {\bf u}={\bf v}\right).$$

Por tanto todo código-$(n,k)$ $C$ perfecto para $t$ errores ha de corregir $t$ errores y en consecuencia su peso mínimo ha de ser $2t+1$.

Observación 8.3   Si existe un código-$(n,k)$ $C<\mathbb{F}_2^n$ perfecto para $t$ errores entonces necesariamente

$$2^{n-k} = \sum_{j=0}^t {n \choose j}.$$ (25)

En efecto, $2^{n-k}$ es el número de clases laterales módulo $C$ en tanto que $\sum_{j=0}^t {n \choose j}$ es el número de representantes principales de clases con pesos a lo sumo $t$. $\Box$

A manera de recíproco, se tiene:

Observación 8.4   Si $C<\mathbb{F}_2^n$ es un código-$(n,k)$ que corrige $t$ errores y $2^{n-k} = \sum_{j=0}^t {n \choose j}$ entonces es perfecto.

En la tabla 4 presentamos una lista de tercetas de enteros $(n,t,k)$ tales que se cumple (25).

Recuadro 4: Tercetas de enteros $(n,t,k)$ tales que $2^{n-k} = \sum_{j=0}^t {n \choose j}$, con $n\leq 100$.

En la tercera columna, tercer rengón de ella aparece la terceta $(n,t,k)=(23,3,12)$ por lo cual ha de existir un código-$(23,12)$ $C$ perfecto para $t$ errores.

Proposición 8.1 (Golay, 1949)   El código cíclico de longitud $23$ con polinomio generador

$$g(X) = 1 + X^{2} + X^{4} + X^{5} + X^{6} + X^{10} + X^{11}$$

y por consiguiente con polinomio revisor de paridad

$$h(X) = \frac{X^{23}+1}{g(X)} = 1 + X^2 + X^5 + X^8 + X^9 + X^{10} + X^{11} + X^{12}$$

es perfecto para $3$ errores. Se le llama código de Golay.

Siguiente: Códigos de ráfagas Arriba: Códigos cíclicos Anterior: Codificación y decodificación