Siguiente: Códigos de Reed-Muller Arriba: Introducción a la Teoría Anterior: Programas

Modificaciones de códigos

Sea $\mathbb{K}$ un campo finito y sea $C<\mathbb{K}^n$ un código lineal-$(n,k)$. Sea $C_e<\mathbb{K}^{n+1}$ definido como sigue:

$$\forall ({\bf x},x_n)\in\mathbb{K}^n\times\mathbb{K}:\ \left[... ...ightarrow\ {\bf x}\in C\ \&\ x_n = \sum_{j=0}^{n-1} x_j\right].$$

Naturalmente, $C_e$ es un código lineal-$(n+1,k)$. Si $B\in\mathbb{K}^{(n-k)\times n}$ es una matriz revisora de paridad de $C$ entonces una matriz revisora de paridad de $C_e$ es

$$B_e = \left[\begin{array}{cc} B & 0_{n-k,1} \\ 1_{1n} & 1 \end{array}\right]$$

donde $0_{n-k,1}\in\mathbb{K}^{(n-k)\times 1}$ es el vector columna consistente de $n-k$ ceros y $1_{1n}\in\mathbb{K}^{1\times n}$ es el vector renglón consistente de $n$ unos. $C_e$ se dice ser el código extendido de $C$.

Observación 6.1   Si $\mathbb{K}=\mathbb{F}_2$ y $C<\mathbb{K}^n$ es un código lineal-$(n,k)$ con peso mínimo $w_C$ impar, entonces el peso mínimo de $C_e$ es $w_{C_e}=w_C+1$.

En efecto, si ${\bf e}$ es de peso mínimo en $C$ entonces el correspondiente vector $({\bf e},e_n)$ en $C_e$ ha de ser tal que $e_n=1$. Por tanto $w({\bf e},e_n) =w({\bf e}) +1$. $\Box$

Observación 6.2   Para los códigos de Hamming $H_m$, de acuerdo con la observación 4.4, sus extendidos $H_{me}$ son de peso mínimo $4$, y una matriz revisora de paridad de ellos es de la forma

$$H^{\perp}_{me} = \left[\begin{array}{cc} H^{\perp}_m & 0_{m1} \\ 1_{1,2^m-1} & 1 \end{array}\right]$$

Sea $C_r<\mathbb{K}^{n-1}$ definido como sigue:

$$\forall {\bf x}\in\mathbb{K}^{n-1}:\ \left[ {\bf x}\in C_r\ \... ...tarrow\ \exists x_n\in\mathbb{K}:\, ({\bf x},x_n)\in C\right] .$$

Si se escribe a una matriz revisora de paridad de $C$ como

$$B = \left[\begin{array}{cc} B_{00} & {\bf b}_{01} \\ {\bf b}_{10}^T & b_{11} \end{array}\right]$$

entonces una matriz revisora de paridad de $C_r$ ha de ser $B_r = \left(\frac{1}{b_{11}} {\bf b}_{10}^T {\bf b}_{01} - B_{00} \right)$. El código $C_r$ se dice ser recortado de $C$.

Observación 6.3   Un código es el recortado de su extendido y es también equivalente al extendido de su recortado.

Ahora, sea $C_a=C\oplus\left(1_n+C\right)$ el espacio generado por $C$ y la clase lateral $1_n+C$, donde $1_n$ es el vector en $\mathbb{K}^n$ constante 1:

$$\forall {\bf x}\in\mathbb{K}^n:\ \left[ {\bf x}\in C_a\ \Long... ... {\bf y}\in C, x\in\mathbb{K}:\ {\bf x}={\bf y}+x\,1_n\right] .$$

El código $C_a$ se dice ser aumentado de $C$.

Proposición 6.1   Sea $\mathbb{K}=\mathbb{F}_2$. En todo código lineal ocurre que bien todas sus palabras poseen peso par, o bien el número de las palabras con peso par coincide con el número de las palabras con peso impar.

En efecto, supóngase que hubiese una palabra de código ${\bf y}\in C$ de peso impar. Por un lado, como $C$ es un grupo abeliano con la suma, se tiene que la traslación ${\bf x}\mapsto{\bf y}+{\bf x}$ es una biyección. Por otro lado, para cualquier palabra de código ${\bf x}$ vale que el peso de ${\bf x}$ es par si y sólo si el peso de ${\bf y}+{\bf x}$ es impar. Por tanto, la mitad de los elementos de $C$ posee pesos pares. $\Box$

Supondremos en lo sucesivo que $\mathbb{K}=\mathbb{F}_2$.

Sea $C<\mathbb{F}_2^n$ un código lineal. Sea $C_x=\{{\bf y}\in C\vert w({\bf y})\equiv 0 \,\mbox{\rm mod}\,2\}$ el conjunto de palabras de código con peso par. Entonces $C_x$ es un código lineal, llamado expurgado de $C$. Por la proposición anterior, resulta que bien $C_x$ coincide con $C$ o bien posee la mitad de elementos de $C$.

Definición 6.1   Se dice que un código lineal $C<\mathbb{F}_2^n$ corrige $t$ errores y detecta $s$ errores simultáneamente si

$$\forall {\bf y}\in C\,\forall {\bf w}\in\mathbb{F}_2^n:\ \le... ...ll {\bf z}\in C-\{{\bf y}\}:\, d_n({\bf w},{\bf z})>t\right].$$ (12)

Con un tal código se puede decodificar según el siguiente:

Procedimiento de decodificación.

Supóngase que al transmitir una palabra ${\bf y}\in C$ se recibe la palabra ${\bf w}\in\mathbb{F}_2^n$. Calcúlese la palabra de código ${\bf z}\in C$ más cercana a ${\bf w}$. Si $d_n({\bf z},{\bf w})\leq t$ entonces dése a ${\bf z}$ como la palabra ${\bf y}$. En otro caso, anúnciese que al menos $s$ símbolos han cambiado.

Proposición 6.2   Un código lineal $C<\mathbb{F}_2^n$ corrige $t$ errores y detecta $s$ errores simultáneamente si y sólo si su distancia mínima $w_m(C)$ satisface

$$w_m(C)\geq t + s + 1.$$ (13)

Supongamos primero que vale la desigualdad (13). Sean ${\bf y}\in C$ y ${\bf w}\in\mathbb{F}_2^n$ tales que $d_n({\bf y},{\bf w}) \leq s$. Para cualquier otra palabra ${\bf z}\in C-\{{\bf y}\}$ se tiene $d_n({\bf z},{\bf y})\geq w_m(C)\geq t + s + 1$. Por la desigualdad del triángulo se sigue: $d_n({\bf z},{\bf w}) + d_n({\bf w},{\bf y})\geq t + s + 1$; y por tanto

$$d_n({\bf z},{\bf w}) \geq t + s + 1 - d_n({\bf w},{\bf y})\geq t+1,$$

con lo que queda demostrada la relación (12).

Recíprocamente, supongamos que la desigualdad (13) no se cumpliera. Entonces $w_m(C) < t + s + 1$ y habría ${\bf y},{\bf z}\in C$ tales que $d_n({\bf y},{\bf z}) = w_m(C) \leq t+s$. Elijamos $s$ posiciones donde las entradas de ${\bf y}$ y ${\bf z}$ difieran y sea ${\bf w}\in\mathbb{F}_2^n$ tal que coincida con ${\bf y}$ salvo en las $s$ posiciones seleccionadas, donde ha de tomar los valores de ${\bf z}$. Entonces $d_n({\bf y},{\bf w}) = s$ y $d_n({\bf z},{\bf y}) = d_n({\bf z},{\bf w})+d_n({\bf y},{\bf w})$. Por tanto,

$$d_n({\bf z},{\bf w}) = d_n({\bf z},{\bf y})-d_n({\bf y},{\bf w}) \leq (t+s)-s = t$$

lo cual evidencia que la relación (12) tampoco puede cumplirse. $\Box$

De la observación 6.2 se tiene que el extendido del código de Hamming posee un peso mínimo $w_m(H_{me})=4\geq 2+1+1$, por tanto $H_{me}$ puede corregir un error y detectar dos errores simultáneamente. Se puede pues decodificar como sigue:

Procedimiento de decodificación.

Supóngase que al transmitir una palabra $({\bf y},y_{2^m})\in H_{me}$ se recibe la palabra $({\bf w},w_{2^m})\in\mathbb{F}_2^{2^m}$. Calcúlese el síndrome ${\bf s}=H_m^{\perp}{\bf w}$. Si ${\bf s}={\bf0}$ entonces acéptese ${\bf w}$ como ${\bf y}$ y acaso corríjase $w_{2^m}$ si fuera necesario; en otro caso, si $w_{2^m}=0$ declárese que hubo al menos dos errores y si $w_{2^m}=1$ entonces cámbiese el valor $w_i$ donde $i$ está dado en binario por el síndrome ${\bf s}$.

Siguiente: Códigos de Reed-Muller Arriba: Introducción a la Teoría Anterior: Programas