Siguiente: Códigos lineales Arriba: Códigos binarios Anterior: Distancia de Hamming

Códigos lineales: Códigos rectangulares y de Hamming

Definición 4.6   Un código $C\subset\mathbb{F}_2^n$ se dice ser lineal si posee al origen y es cerrado bajo la suma de $\mathbb{F}_2^n$.

En el caso de un código lineal, el peso de cualquier palabra $\mbox{\boldmath$\varepsilon$}\in C$ es $w\left(\mbox{\boldmath$\varepsilon$}\right) = d_n\left(\mbox{\boldmath$\varepsilon$},{\bf0}\right)$, y el peso mínimo del código es

$$w_m(C) = \min\left\{w\left(\mbox{\boldmath $\varepsilon$}\right)\vert\ \mbox{\boldmath $\varepsilon$}\in C-\{{\bf0}\}\right\}.$$

Observación 4.3   Para cualquier código lineal $C\subset\mathbb{F}_2^n$ se tiene

• $C$ reconoce $t$ errores si $w_m(C)>t$
• $C$ corrige $t$ errores si $w_m(C)>2t$

Ejemplo 4.4 (Códigos rectangulares)   Supongamos $n_1=m\,n$, con $m,n>1$. Entonces el producto cartesiano $[\![0,m-1]\!]\times[\![0,n-1]\!]$ se identifica con el intervalo de enteros $[\![0,n_1-1]\!]$ mediante la correspondencia $\nu:(i,j) \mapsto \nu(i,j) = in+j$. El código rectangular, con $(m-1)(n-1)$ bits de información y $m+n-1$ bits de revisión, es

$$\begin{eqnarray*} C &=& \left\lbrace \mbox{\boldmath$\varepsilon$}\in \mathbb{F}... ...epsilon_{\nu(i,j)}\right) \mbox{\rm mod }2 \right] \right\rbrace \end{eqnarray*}$$

La razón de información de este código es $\frac{m-1}{m}\frac{n-1}{n}$.

Puede verse que $C$ es un código lineal, pues contiene al origen y es cerrado bajo la suma. Si un elemento $\varepsilon_{\nu(i,j)}$ toma el valor $1$, entonces debe aparecer un $1$ en otra posición en la misma columna y un $1$ también en otra posición en el mismo renglón, y debe haber un $1$ en la esquina opuesta a $(i,j)$. En consecuencia, el peso mínimo de $C$ es $4$ y por tanto es capaz de detectar hasta 3 errores.

Se tiene que un vector $\mbox{\boldmath$\varepsilon$}\in \mathbb{F}_2^{n_1}$ estará en el código si y sólo si se satisfacen las $m+n$ ecuaciones

$$\sum_{j=0}^{n-1}\varepsilon_{\nu(i,j)} = 0,\ i\in[\![0,m-1]\!... ...\ \sum_{i=0}^{m-1}\varepsilon_{\nu(i,j)}=0,\ j\in[\![0,n-1]\!].$$

Todo código lineal es un subespacio lineal de $\mathbb{F}_2^n$ y por tanto ha de poseer una base. Cualquier palabra podrá ser escrita como una combinación lineal de los elementos en la base y por tanto las palabras en el código han de satisfacer un conjunto de ecuaciones lineales tal como en el caso de los códigos rectangulares.

En efecto, si un código lineal $C$ es de dimensión $k$ en $\mathbb{F}_2^n$, sea $\left(\mbox{\boldmath$\varepsilon$}_j\right)_{0\leq j\leq k} \subset \mathbb{F}_2^{n}$ una base de $C$. La matriz $H =\left[\mbox{\boldmath$\varepsilon$}_j\right]_{0\leq j\leq k}\in \mathbb{F}_2^{n\times k}$ que posee como columnas a los vectores básicos, llamada generatriz de $C$, es de orden $(n\times k)$ y determina un isomorfismo $\mathbb{F}_2^{k}\to C$, $\mbox{\boldmath$\delta$}\mapsto H\mbox{\boldmath$\delta$}$. Existe entonces una matriz $H^{\perp}\in \mathbb{F}_2^{(n-k)\times n}$ tal que $H^{\perp}H=0\in \mathbb{F}_2^{(n-k)\times k}$. Así se ha de tener la equivalencia: $\left[\mbox{\boldmath$\varepsilon$}\in C\ \Leftrightarrow\ H^{\perp}\mbox{\boldmath$\varepsilon$}={\bf0}\right]$. La matriz $H^{\perp}$ se dice ser una revisora de paridad del código $C$.

Proposición 4.1   Un código $C$ corrige errores de un bit si y sólo si cualquier matriz revisora de paridad suya posee columnas no-nulas y distintas a pares.

Sea ${\bf e}_j=\left[\delta_{ij}\right] _{i=0}^{n-1}$ el $j$-ésimo vector de la base canónica, $j=0,\ldots,n-1$. Denotemos también por $\mbox{\boldmath$\varepsilon$}_{ij}$ al vector que coincide con ${\bf0}$ salvo que en sus dos entradas $i$ y $j$ posee el valor 1, $\mbox{\boldmath$\varepsilon$}_{ij}={\bf e}_i+{\bf e}_j$.

La proposición se sigue de que las siguientes aseveraciones son equivalentes a pares:

• $C$ corrige errores de un bit.
• El peso mínimo de $C$ es al menos 3.
• Ninguno de los vectores ${\bf e}_j$, $\mbox{\boldmath$\varepsilon$}_{ij}$ puede estar en $C$.
• Para cada $H^{\perp}$ revisora de paridad, los productos $H^{\perp}{\bf e}_j$, $H^{\perp}\mbox{\boldmath$\varepsilon$}_{ij}$ no pueden ser nulos.
• Para cada $H^{\perp}$ revisora de paridad, las columnas de $H^{\perp}$ son no-nulas y distintas a pares.

Definición 4.7   Para cada $m$, sea $H_m^{\perp}=\left[\mbox{\boldmath$\varepsilon$}\right]_{\mbox{\scriptsize\boldm... ...n\mathbb{F}_2^{m}-\{\mbox{\bf\scriptsize0}\}} \in\mathbb{F}_2^{m\times (2^m-1)}$ la matriz cuyas columnas son los vectores no-nulos en $\mathbb{F}_2^{m}-\{{\bf0}\}$. Todo código que posea a $H_m^{\perp}$ como matriz revisora de paridad se dice ser de Hamming¹.

Así todo código de Hamming posee $\left(2^m-1\right)-m$ bits de información y $m$ bits de revisión, y su razón de información es $\frac{2^m-1-m}{2^m-1}=1-\frac{m}{2^m-1}$.

La matriz $H_m^{\perp}$ queda determinada de manera única salvo el orden en el que se enumere a los elementos de $\mathbb{F}_2^{m}-\{{\bf0}\}$. Sea $\kappa_m:[\![1,2^m-1]\!]\to[\![1,2^m-1]\!]$ la permutación que ordena a los índices de acuerdo con el peso de Hamming y en orden lexicográfico cuando haya coincidencia de pesos. Por ejemplo:

$m=3$.

$\kappa_3 = \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 2 & 4 & 3 & 5 & 6 & 7 %\\ \end{array} \right)$

$m=4$.

$\kappa_4 = \left(\begin{array}{ccccccccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 ... ...& 8 & 3 & 5 & 6 & 9 & 10 & 12 & 7 & 11 & 13 & 14 & 15 %\\ \end{array} \right)$

Si a los índices se les ordena de acuerdo con $\kappa_m$, entonces se podrá escribir $H_m^{\perp} = \left[I_m\ G_m\right]$ donde $I_m$ es la matriz identidad de orden $(m\times m)$ y $G_m$ es una matriz de orden $m\times (2^m-1-m)$. Así pues, se tendrá que una palabra $\mbox{\boldmath$\varepsilon$}=\left(\varepsilon_j\right)_{j=1}^{2^m-1}$ está en el código de Hamming si y sólo si $\left[I_m\ G_m\right]\,\kappa_m(\mbox{\boldmath$\varepsilon$}) = {\bf0}$, donde $\kappa_m(\mbox{\boldmath$\varepsilon$})=\left(\varepsilon_{\kappa_m(j)}\right)_{j=1}^{2^m-1}$, lo cual equivale a que

$$I_m\mbox{\boldmath$\varepsilon$}_0 = G_m\mbox{\boldmath$\var... ...1 = \left(\varepsilon_{\kappa_m(j)}\right)_{j=m+1}^{2^m-1}$}.$$ (7)

El conjunto de índices $I_0=\left\lbrace\kappa_m(j)\right\rbrace_{j=1}^{m}$ corresponde a los bits de revisión y el conjunto $I_1=\left\lbrace\kappa_m(j)\right\rbrace_{j=m+1}^{2^m-1}$ a los de información.

Sea $H_m=\left[\begin{array}{c} G_m \\ I_{2^m-1-m}\end{array}\right]\in\mathbb{F}_2^{\left(2^m-1\right)\times\left(2^m-1-m\right)}$. Entonces, $H_m^{\perp}H_m = {\bf0}\in\mathbb{F}_2^{m\times\left(2^m-1-m\right)}$ y por tanto las columnas de $H_m$ forman una base del código de Hamming. La dimensión del código es el número de bits de información, a saber, $2^m-1-m$.

Para codificar una palabra ${\bf\delta}=\left[\delta_j\right]_{j=1}^{2^m-1-m}\in\mathbb{F}_2^{2^m-1-m}$ se construye $\mbox{\boldmath$\varepsilon$}=\left(\varepsilon_j\right)_{j=1}^{2^m-1}$ haciendo $\varepsilon_{\kappa_m(j)}=\delta_{j-m}$ para $j\in[\![m+1,2^m-1]\!]$ y, para $j\in[\![1,m]\!]$, los valores $\varepsilon_{\kappa_m(j)}$ quedan determinados por la ec. (7).

Para decodificar un $\mbox{\boldmath$\varepsilon$}=\left(\varepsilon_j\right)_{j=1}^{2^m-1}$, se revisa si éste está en el código. El vector $H_m^{\perp}\mbox{\boldmath$\varepsilon$}$ se dice ser el síndrome de $\mbox{\boldmath$\varepsilon$}$. Si el síndrome fuese nulo no se hace ninguna corrección y se recupera ${\bf\delta}\in\mathbb{F}_2^{2^m-1-m}$ mediante los bits de información: $\delta_{j}=\varepsilon_{\kappa_m(j+m)}$, para $j\in[\![1,2^m-1-m]\!]$. En otro caso, deben existir $\mbox{\boldmath$\varepsilon$}'$ en el código de Hamming y un índice $i\in[\![1,2^m-1]\!]$ tales que $\mbox{\boldmath$\varepsilon$}=\mbox{\boldmath$\varepsilon$}'+{\bf e}_i$. Por tanto, ha de tenerse $H_m^{\perp}\mbox{\boldmath$\varepsilon$}'={\bf0}$ y

$$H_m^{\perp}\mbox{\boldmath $\varepsilon$} = H_m^{\perp}\left(... ... e}_i = \left( \mbox{$i$-\'esima columna de }H_m^{\perp}\right)$$

y la $i$-ésima columna de $H_m^{\perp}$ no es otra que la representación en base 2 del índice $i$. Así pues, el síndrome indica cuál es el índice que ha de conmutarse para corregir el error.

Observación 4.4   Los códigos de Hamming poseen peso mínimo $3$.

En efecto, si la matriz revisora de paridad se escribe como las representaciones en base 2 de los números en $[\![1,2^m-1]\!]$, entonces las tres primeras columnas, correspondientes a 1, 2 y 3 forman una submatriz $m\times 3$ con un bloque inicial de $(m-2)\times 3$ ceros y los dos últimos renglones son $\begin{array}{ccc} 0 & 1 & 1 \\ 1 & 0 & 1 \end{array}$. De aquí se ve que la palabra $1110^{(2^m-4)}$ está en el código. Por tanto $w_{m}(H_m)\leq 3$. Por otro lado, como el código corrige un bit, por la observación 4.1, se tiene que $w_{m}(H_m)\geq 3$. $\Box$

Observación 4.5   Los códigos de Hamming son perfectos en el sentido de que cualquier palabra en el espacio que contiene a las palabras de código, es bien una palabra de código o bien dista en $1$ de una palabra de código.

Definición 4.8   Supongamos que $C\subset\mathbb{F}_2^n$ es un código lineal con palabras de código de longitud $n$, y que un canal binario simétrico, con probabilidad $p$ de alterar el valor de cada bit, transmite una palabra de código $\mbox{\boldmath$\varepsilon$}$. Si $\mbox{\boldmath$\varepsilon$}'$ es la palabra recibida tras la transmisión, el error es $\mbox{\boldmath$\eta$} =\mbox{\boldmath$\varepsilon$}-\mbox{\boldmath$\varepsilon$}'$. El error quedará indetectado siempre que $\mbox{\boldmath$\eta$}\in C$.

Para cada $i\in[\![1,2^m-1]\!]$, sea $c_i$ el número de palabras con peso de Hamming $i$ en el código $C$. Entonces, la probabilidad de que un error quede indetectado será

$$\,\mbox{\rm Prob}\,(\mbox{error indetectado}) = P_x = \sum_{i=1}^{n} c_i p^i(1-p)^{n-i} = \sum_{i=d}^{n} c_i p^i(1-p)^{n-i}$$

donde $d$ es el peso mínimo de $C$ (si $i<d$ entonces $c_i=0$).

Definición 4.9   El polinomio $P_C(X) = \sum_{i=0}^{n} c_i X^i$, donde $c_i$ es el número de palabras con peso $i$ en $C$, se dice ser el enumerador de pesos del código $C$.

De acuerdo con lo anterior, se tiene

$$P_x = (1-p)^n \left[C\left(\frac{p}{1-p}\right)-1\right].$$

Por ejemplo, para los primeros códigos de Hamming se tiene:

$m=3$.

La dimensión del código es $2^m-1-m = 8-1-3 = 4$, por tanto el código posee $2^4=16$ palabras, que clasificadas según sus pesos de Hamming producen las siguientes cuentas:

$$\begin{array}{\vert\vert c\vert\vert c\vert c\vert c\vert c\v... ...& 7 \\ \hline c_i & 1 & 7 & 7 & 1 \\ \hline \hline \end{array}$$

El enumerador de pesos es pues

$$P_C(X) = 1 + 7 X^3 + 7 X^4 + X^7.$$

$m=4$.

La dimensión del código es $2^m-1-m = 16-1-4 = 11$, por tanto el código posee $2^{11}=2048$ palabras, que clasificadas según sus pesos de Hamming producen las siguientes cuentas:

$$\begin{array}{\vert\vert c\vert\vert c\vert c\vert c\vert c\v... ...5 & 435 & 280 & 168 & 105 & 35 & 1 \\ \hline \hline \end{array}$$

El enumerador de pesos es pues

$$P_C(X) = 1 + 35 X^3 + 105 X^4 + 168 X^5 + 280 X^6 + 435 X^7 + 435 X^8 + 280 X^9 + 168 X^{10} + 105 X^{11} + 35 X^{10} + X^{15}.$$

$m=5$.

La dimensión del código es $2^m-1-m = 32-1-5 = 26$, por tanto el código posee $2^{26}=67\,108\,864$ palabras, que clasificadas según sus pesos de Hamming producen las siguientes cuentas:

$$\begin{array}{cc} \begin{array}{\vert\vert r\vert r\vert\vert... ...\ \hline 16 & 9398115 \\ \hline \hline \end{array}\end{array}$$

Si se conoce el polinomio enumerador de pesos en un código-$(n,k)$ $C$ se puede calcular procedimentalmente el polinomio enumerador de pesos de su dual $C^{\perp}$. Denotemos por $P_C(X)$ al enumerador de pesos de $C$, según la definición 4.9. Definamos al polinomio de dos variables

$$Q_C(X,Y) = Y^n\,P_C\left(\frac{X}{Y}\right) = \sum_{i=0}^n c_i X^i Y^{n-i}.$$

Teorema 4.1 (MacWilliams)   Para el código dual $C^{\perp}$ de $C$ se tiene

$$P_{C^{\perp}}(X) = 2^{-k} (1+X)^n\ P_C\left(\frac{1-X}{1+X}\right)$$

o equivalentemente

$$Q_{C^{\perp}}(X,Y) = 2^{-k} \ Q_C\left(Y-X,Y+X\right).$$ (8)

Observamos primero

$$2^{-k} \sum_{{\bf v}\in C} (-1)^{\langle{\bf u}\vert{\bf v}\... ... \mbox{ si }{\bf u}\not\in C^{\perp} %\\ \end{array} \right.$$ (9)

En efecto, por un lado $\mbox{\rm card}\,C = 2^k$. Por otro, si ${\bf u}\in C^{\perp}$ entonces $\langle{\bf u}\vert{\bf v}\rangle=0$. En otro caso, existe ${\bf v}_0\in C$ tal que $\langle{\bf u}\vert{\bf v}_0\rangle\not=0$, es decir, $\langle{\bf u}\vert{\bf v}_0\rangle=1$. Se puede ver que $\left(V\cap{\bf u}^{\perp}\right)$ y ${\bf v}_0 + \left(V\cap{\bf u}^{\perp}\right)$ forman una partición de $V$ y ambas tienen una misma cardinalidad. De aquí se sigue (9).

Observamos luego que, para cualquier código, se tiene

$$Q_C(X,Y) = \sum_{{\bf v}\in C} X^{\vert{\bf v}\vert} Y^{n-\vert{\bf v}\vert}.$$

Pues bien, por un lado se tiene

$$\begin{eqnarray*} Q_{C^{\perp}}(X,Y) &=& \sum_{{\bf u}\in {C^{\perp}}} X^{\vert{... ...um_{{\bf v}\in C} \prod_{j=0}^{n-1} \left(Y+(-1)^{v_j}X\right). \end{eqnarray*}$$

Por otro lado,

$$\begin{eqnarray*} Q_C(Y-X,Y+X) &=& \sum_{{\bf v}\in C} (Y-X)^{\vert{\bf v}\vert}... ...sum_{{\bf v}\in C} \prod_{j=0}^{n-1} \left(Y+(-1)^{v_j}X\right) \end{eqnarray*}$$

Por tanto se cumple (8). $\Box$

Siguiente: Códigos lineales Arriba: Códigos binarios Anterior: Distancia de Hamming