Siguiente: Arreglos estándares Arriba: Códigos lineales Anterior: Matrices generatrices, de paridad

Pesos mínimos

Definición 5.6   El peso de Hamming de una palabra ${\bf y}\in\mathbb{K}^n$ es $w({\bf y}) = \mbox{\rm card}\{j\in[\![0,n-1]\!]\vert\, y_j\not=0\}$. Para un código lineal-$(n,k)$ $C<\mathbb{K}^n$, su peso mínimo es $w_m(C)=\min\{w({\bf y})\vert\ {\bf y}\in C-\{{\bf0}\}\}$.

Observación 5.1 (Cota de Singleton)   El peso mínimo $w_m(C)$ de un código lineal-$(n,k)$ $C$ queda acotado como sigue:

$$w_m(C)\leq n-k+1.$$ (10)

En efecto, por un lado como los símbolos de información pueden asumir cualesquiera valores, transformando a una generatriz sistemática se ve que la palabra ${\bf y} = 1\ 0^{k-1}\ y_{k+1}\cdots y_{n-1}$ es una palabra en el código de peso a lo sumo $n-(k-1)$, por tanto $w_m(C)\leq n-k+1$. $\Box$

Como es convencional, si $d=w_m(C)$, entonces se dice que $C$ es un código lineal-$(n,k,d)$.

Un código lineal-$(n,k,d)$ $C$ que alcance la cota de Singleton, es decir, en el que vale la igualdad en la relación (10), se dice ser separable con la distancia máxima (en inglés, Maximum Distance Separable (MDS)). Primeramente:

Observación 5.2   Un código lineal-$(n,k)$ $C$ es MDS cuando y sólo cuando las palabras en $C$ no-nulas de peso mínimo tienen peso $n-(k-1)$.

Otra caracterización es la siguiente:

Observación 5.3   Un código lineal-$(n,k)$ $C$ es MDS cuando y sólo cuando cualesquiera $n-k$ columnas de una matriz revisora de paridad de $C$ son linealmente independientes.

Y considerando códigos duales, una caracterización más es:

Observación 5.4   Sea $C$ un código lineal-$(n,k)$. Entonces las siguientes relaciones son equivalentes a pares:

1. $C$ es MDS.
2. El código dual $C^{\perp}$ es MDS.
3. Cualesquiera $k$ columnas de una matriz generatriz de $C$ son linealmente independientes.
4. Si $\left[\begin{array}{c} I_{k} \\ A_r\end{array}\right]$, con $A_r\in\mathbb{K}^{(n-k)\times k}$, es una matriz sistemática de $C$ entonces cualquier submatriz cuadrada de $A_r$ es no-singular.

Por otro lado:

Observación 5.5   Sea $B\in\mathbb{K}^{(n-k)\times n}$ una matriz revisora de paridad del código lineal-$(n,k,d)$ $C$. Entonces cualesquiera $d-1$ columnas de $B$ son linealmente independientes.

En efecto supongamos que hubiese $m$ columnas de $B$ linealmente dependientes, con $m\leq d-1$.

Sea $M\subset[\![0,n-1]\!]$ el conjunto de índices correspondiente a esas columnas. Entonces sin pérdida de generalidad podemos suponer que la suma de esas columnas es el vector cero, $\sum_{j\in M}{\bf b}_j={\bf0}\in\mathbb{K}^{n-k}$.

Sea ${\bf x}=\sum_{j\in M}{\bf e}_j\in\mathbb{K}^n$. Entonces ${\bf x}$ tiene peso $m$ y su síndrome es $B{\bf x}=\sum_{j\in M}{\bf b}_j$, o sea es el vector cero. Por tanto ${\bf x}$ ha de estar en el código $C$, pero esto no es posible ya que el peso mínimo de $C$ es $d$ y éste es mayor que $m$. $\Box$

Una reformulación de la observación 5.5 es la siguiente:

Observación 5.6   Sea $B\in\mathbb{K}^{(n-k)\times n}$ una matriz revisora de paridad del código lineal-$(n,k,d)$ $C$. Entonces $d$ coincide con el entero mínimo $m$ para el cual hay $m$ columnas linealmente dependientes en $B$.

Consideremos ahora $\mathbb{K}=\mathbb{F}_2$. Sea $b(n,r)=\sum_{j=0}^r{n\choose j}$ la cardinalidad de una bola de radio $r$ centrada en un punto del hipercubo $\mathbb{F}_2^n$.

Observación 5.7 (Cota de Hamming)   Sea $C$ un código lineal-$(n,k,d)$. Entonces

$$\log_2 b\left(n,\left\lfloor\frac{d-1}{2}\right\rfloor\right)\leq n-k.$$ (11)

En efecto, sea $r=\left\lfloor\frac{d-1}{2}\right\rfloor$. Para cualesquiera dos palabras de código ${\bf x}_0,{\bf x}_1\in C$, al ser éste de peso mínimo $d$, se tiene $\left[{\bf x}_0\not={\bf x}_1\ \Rightarrow\ B({\bf x}_0,r)\cap B({\bf x}_1,r) = \emptyset\right]$, es decir, cualesquiera dos bolas de radio $r$ con centros en palabras de código distintas han de ser ajenas. Por tanto,

$$2^n\geq \mbox{card}\left(\bigcup_{{\bf x}\in C}B({\bf x},r)\r... ...^k\cdot b\left(n,\left\lfloor\frac{d-1}{2}\right\rfloor\right),$$

de donde se sigue (11). $\Box$

Un código lineal-$(n,k,d)$ $C$ que alcance la cota de Hamming, es decir, en el que vale la igualdad en la relación (11), se dice ser perfecto. En un tal código, se tiene que $\left\{B\left({\bf x},\left\lfloor\frac{d-1}{2}\right\rfloor\right)\right\}_{{\bf x}\in C}$ es una partición del hipercubo $\mathbb{F}_2^n$. Los códigos de Hamming son perfectos. Naturalmente, la noción de perfección introducida aquí generaliza a la de la observación 4.5.

Siguiente: Arreglos estándares Arriba: Códigos lineales Anterior: Matrices generatrices, de paridad