Códigos Correctores Perfectos y con Descodificación Unica

Juan Tena Ayuso

Departamento de Algebra, Geometría y Topología. Universidad de Valladolid. ^{∗}

1 Introducción

El propósito de este artículo es la exposición de algunos nuevos resultados relativos a Códigos Correctores de Errores con la propiedad de Descodificación Unica.

La teoría de Códigos se inscribe en el marco conceptual de la Teoría de la Información, disciplina que tiene su origen en un artículo de C.E. Shannon (Bell Telephone), [4] y que estudia, desde un punto de vista matemático, la transmisión de información a través de un canal. Tal proceso de transmisión puede esquematizarse en la forma siguiente:

[figure: emisor; canal; receptor]

En la situación anterior el emisor desea enviar una información (o mensaje) a un receptor a través del canal. Para nuestro propósito presente podemos suponer (aunque Shannon estudia también canales continuos gaussianos) el canal discreto y sin memoria (se emite una señal por unidad de tiempo, cada señal no tiene efecto sobre las siguientes y a cada señal emitida corresponde una recibida).

Consecuentemente los mensajes transmitidos serán palabras o elementos del monoide A^{∗}, donde A representa un Alfabeto o conjunto finito de símbolos (castellano, binario, etc.).

∗E–mail: tena@cpd.uva.es

Habitualmente la forma en que la información está escrita originalmente no es adecuada para su transmisión. Se codifica entonces para adaptarla a las características del canal y a nuestras necesidades (comprimir la información, detectar y corregir errores, garantizar la privacidad de la información frente a terceros, etc). Tal codificación viene dada por una aplicación codificación del conjunto de mensajes en el monoide B^{∗} (donde B es un segundo alfabeto)

c : M ⟶^{inyect.} B^{∗}

Se denomina Código a la imagen de c : C = Im(c)

Cada una de las necesidades antes mencionadas da origen a un tipo diferente de código: códigos compresores, códigos correctores o códigos secretos, ver [3].

En la práctica, los canales no transmiten fielmente la información, ya que sufren alteraciones o perturbaciones (lo que en la jerga se llama ruido) que hacen que el mensaje recibido difiera del original. En particular, un símbolo o letra del mensaje puede ser alterado, recibiéndose una letra diferente. Llamaremos error a esta situación y supondremos que tales errores se producen de forma aleatoria (con una cierta probabilidad dependiente del canal particular).

Los Códigos Correctores de Errores preservan la información transmitida de alteraciones producidas por el ruido del canal, detectando y corrigiendo los errores producidos.

Un código C se dice Código en bloque de longitud n, si todas sus palabras son de la misma longitud n. Los códigos correctores son generalmente códigos en bloque y así lo supondremos en lo que sigue.

Para conseguir tal objetivo de detección y corrección los códigos correctores utilizan como herramienta la adición al mensaje de símbolos adicionales (Redundantes o de control).

Ejemplo 1.1 Sean A = B = {0, 1}, M = A y consideremos la codificación

c : A ⟶^{inyect.} A^{3}

0 ⟶ 000, 1 ⟶ 111 (código de triple repetición). Tal código permite corregir un error simple: si uno de los tres dígitos iguales transmitidos es alterado un proceso de descodificación por mayoría permite recuperar el mensaje original.

La característica fundamental que permite, en el ejemplo del código de repetición anterior, la corrección de errores, es que sus (dos) palabras son lo más ‘diferentes’ posibles, con lo que resulta ‘improbable’ que las alteraciones del canal transformen una en otra. Esta idea de tomar las palabras lo más diferentes posible es, de hecho, la base de todos los códigos correctores de errores.

La forma lógica de medir la separación entre palabras es la llamada distancia de Hamming, que definimos a continuación.

Definición 1.2 Si x, y ∈ B^{n}, x = (x_{1}, ⋯, x_{n}), y = (y_{1}, ⋯, y_{n}), llamaremos distancia de Hamming entre x e y a

d(x, y) = #{i | 1 ≤ i ≤ n, x_{i} ≠ y_{i}}.

Definición 1.3 Llamaremos distancia mínima del código C a

d = d(C) = min{d(x, y) | x, y ∈ C, x ≠ y}.

Emitida una palabra c ∈ C, se recibirá una n-upla y. Para descodificar y seguiremos el Principio de Distancia Mínima, lo que significa simplemente que descodificaremos y por la palabra de C más ‘parecida’ a y (siempre según la distancia de Hamming). Al actuar así, asumimos implícitamente que el error producido durante la trasmisión no ha sido muy grande.

Este método proporciona el siguiente algoritmo

Algoritmo 1.4 Recibido y,

1. Evaluar la distancia de y a todas las palabras de C;
2. Descodificar y por la más cercana (si es única).

El algoritmo falla cuando la palabra más cercana no es única. En cualquier otro caso proporciona una (no necesariamente correcta) descodificación de y.

Definición 1.5 C se llama Código de Descodificación Unica (o CDU) si, para todo y, existe una sola palabra de C más próxima a y, es decir si el algoritmo anterior permite siempre descodificar y.

La propiedad CDU es obviamente deseable en un código. En lo que sigue trataremos de caracterizar tales códigos.

El parámetro que permite medir la capacidad de corrección de errores de un código es la distancia mínima. Se tiene en efecto, (ver [2], [3]).

Proposición 1.6 Sea C un código en bloque de longitud n y distancia mínima d. El algoritmo aplicado a una n-upla recibida permite corregir cualquier configuración de e errores siempre que 2e < d. e = ⌊\frac{d−1}{2}⌋ se denomina la capacidad correctora de C.

Los procesos de codificación y descodificación de los códigos en bloque son computacionalmente costosos y exigen almacenar en memoria todas las palabras del código. El intento de superar estas dificultades obligó muy pronto a buscar códigos con una estructura algebraica añadida.

Sea F_{q} el (único) cuerpo finito con q elementos.

Definición 1.7 Un código lineal de longitud n sobre F_{q} es un subespacio vectorial de F_{q}^{n}.

Todo código lineal C de longitud n, es también un código en bloque de longitud n. Además, como espacio vectorial, C posee una dimensión, k, luego su cardinal es siempre una potencia de q, q^{k}. Estos números, n, k y la distancia mínima d, son llamados parámetros fundamentales de C. Para abreviar, de un código cuyos parámetros sean n, k y d, se dice que es de tipo [n, k, d].

Definición 1.8 Llamaremos matriz generatriz de C a la matriz de una aplicación lineal inyectiva f : F_{q}^{k} ⟶ C ⊂ F_{q}^{n}, es decir, a una matriz k × n cuyas filas son una base de C.

Un subespacio vectorial de F_{q}^{n} puede describirse no solo mediante un sistema de generadores (lo que da lugar al concepto de matriz generatriz), sino también mediante unas ecuaciones implícitas. Esta forma de caracterización origina la siguiente definición.

Definición 1.9 Diremos que una matriz H es una matriz de control del código C si, para todo vector x ∈ F_{q}^{n}, se verifica que x ∈ C si y solo si Hx^{t} = 0.

Ejemplo 1.10 Sea r un entero positivo, r ≥ 2. Llamaremos código de Hamming binario H_{2}(r), al código cuya matriz de control tiene por columnas a los vectores no nulos de F_{2}^{r}. H_{2}(r) tiene longitud n = #F_{2}^{r} − 1 = 2^{r} − 1, dimensión k = n − r = 2^{r} − r − 1 y distancia 3. Por motivos prácticos es usual ordenar las columnas de la matriz de control en orden creciente como representación binaria de los enteros 1, 2, ⋯, 2^{r} − 1. Así H_{2}(3) tendrá parámetros [7,4,3] y matriz de control

H = ( \begin{matrix}0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{matrix} ) .

2 Códigos Perfectos

Los parámetros n, k y d, de un código no son independientes ya que están relacionados por diferentes relaciones combinatorias o cotas. En particular se tiene (ver [2], [3]):

Teorema 2.1 (Cota de Hamming) Si C es un código (lineal o no) de longitud n sobre F_{q}, que corrige e errores, se verifica:

MV_{q}(n, e) ≤ q^{n}

donde M es el número de palabras de C y V_{q}(n, e) el número de elementos de una bola de radio e y centro en cualquier palabra del código.

Definición 2.2 Los códigos para los que se alcanza la igualdad en la cota de Hamming son llamados Perfectos.

\underline{Nota}: Los códigos perfectos son de Descodificación Unica: Para todo elemento x ∈ F_{q}^{n} existe un elemento único c ∈ C a mínima distancia de x (el centro de la única bola de radio e a la que pertenece).

Ejemplo 2.3 (Ver [2], [3])

1. Códigos Perfectos triviales: 0, F_{q}^{n} y binarios de repetición con longitud impar.

2. Los códigos de Hamming sobre F_{q}, (n = \frac{q^{m}−1}{q−1}, k = n − m, d = 3). Capacidad correctora e = 1

3. Código binario de Golay, G_{23}, (n = 23, k = 12, d = 7). Capacidad correctora e = 3.

4. Código ternario de Golay G_{11}, (n = 11, k = 6, d = 5). Capacidad correctora e = 2.

Los ejemplos anteriores son esencialmente los únicos:

Teorema 2.4 Todo código perfecto no trivial sobre F_{q} tiene los mismos parámetros que un código de Hamming o de Golay. Además en el caso lineal son de hecho equivalentes a estos.

La herramienta combinatoria para el estudio de los códigos perfectos es el t-diseño

Definición 2.5 Sea X = (P_{1}, P_{2}, …, P_{v}) un v-conjunto. Un t − (v, k, λ) diseño sobre X es una colección de k-subconjuntos de X, (Bloques), tal que todo t-subconjunto de X está contenido en λ bloques.

Si λ=1, el diseño se denomina sistema de Steiner S(t, k, v).

Ejemplo 2.6 • El plano afín sobre F_{2} es un 2 − (4, 2, 1) diseño, es decir un S(2, 2, 4)

sistema de Steiner, con bloques las rectas.

• El plano proyectivo sobre F_{2} es un 2−(7, 3, 1) diseño, es decir un S(2, 3, 7) sistema de Steiner.

Existe una estrecha relación entre diseños y códigos (lineales o no), [2]. En particular:

Teorema 2.7 (Assmus-Mattson).- C código lineal de longitud n y distancia d es perfecto si y solamente si los bloques correspondientes a las palabras minimales forman un (e+1)−(n, d, (q−1)^{e}) diseño (en el caso binario un S(e+1, d, n) sistema de Steiner).

Ejemplo 2.8 El código H_{2}(F_{5}) con matriz de control

H = ( \begin{matrix}0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 2 & 3 & 4 \end{matrix} ) .

posee 80 vectores minimales, es decir 20 rectas vectoriales (bloques). e + 1 = 2 posiciones están siempre en el soporte de (q − 1)^{e} = 4 bloques. Por ejemplo las dos primeras coordenadas están en el soporte de las 4 líneas:

λ(1, 4, 0, 0, 0, 1), λ(1, 2, 0, 0, 3, 0), λ(1, 3, 0, 2, 0, 0), λ(1, 1, 4, 0, 0, 0)

3 Códigos Lineales de Descodificación Unica

Los códigos perfectos son CDU. Es inmediato comprobar que también lo son los códigos suma directa de códigos perfectos (Ver [2] o [3] para la construcción del código suma directa).

\underline{Conjetura}, [1]: No existen otros códigos lineales CDU.

Con vistas a intentar demostrar la conjetura anterior supongamos C ⊂ F_{q}^{n} código lineal CDU. Sea V el conjunto de sus palabras minimales y d = 2e + 1 (necesariamente impar) el peso de tales palabras.

Definición 3.1 v, w ∈ V, se denominan adjuntos si verifican una de las condiciones:

1. v = λw, λ ∈ F_{q}^{∗}.

2. |Sop(v) ∩ Sop(w)| = e y los valores de las e coordenadas comunes son iguales.

En V se tiene la siguiente relación de equivalencia:

Definición 3.2 a ∼ b si y solamente si existe una cadena: a = v_{1}, v_{2}, …, v_{s} = b, con v_{i}, v_{i+1} adjuntos.

Si M es una clase de equivalencia en V y D =< M > se tiene:

Teorema 3.3 D es perfecto.

Demostración: En virtud de 2.7 basta probar que e + 1 coordenadas de M=Sup(D) están contenidas en el soporte de (q − 1)^{e+1} vectores de M (= (q − 1)^{e} líneas). Ver [1] para más detalles.

Corolario 3.4 C contiene una suma de códigos perfectos D_{i}^{e}, con capacidad correctora e.

Sería ahora necesario probar que la intersección de dos tales códigos D_{i}^{e} se reduce a 0. Lamentablemente solo podemos demostrar (ver [1]) el resultado parcial:

Proposición 3.5

∀ i ≠ j |Sup(D_{i}^{e}) ∩ Sup(D_{j}^{e})| < e.

Si C = ∑ D_{i}^{e}, el proceso termina. Caso contrario consideremos C − ∑ D_{i}^{e} y sea 2f +1 (f > e), el peso de los vectores minimales de la diferencia. Repitiendo de nuevo la construcción anterior se obtienen códigos perfectos D_{i}^{f} los cuales, como en 3.5, verifican:

∀ i, j |Sup(D_{i}^{f}) ∩ Sup(D_{j}^{f})| < f.

Además para e < f se verifica:

Proposición 3.6

∀ i, j |Sup(D_{i}^{e}) ∩ Sup(D_{j}^{f})| ≤ e.

Continuando la construcción, si necesario, se obtiene una descomposición:

C = D_{1}^{e_{1}} + D_{2}^{e_{2}} + ⋯ + D_{r}^{e_{r}}

e_{1} < e_{2} ⋯ < e_{r} y

D_{i}^{e_{i}} = D_{i1} + D_{i2} + ⋯ + D_{ir_{i}}

D_{ij} perfectos con distancia mínima 2e_{i} + 1.

Es fácil mostrar también el siguiente resultado de unicidad:

Teorema 3.7 La descomposición anterior es esencialmente única. Dada otra:

C = C_{1}^{f_{1}} + C_{2}^{f_{2}} + ⋯ + C_{s}^{f_{s}}
C_{i}^{f_{i}} = C_{i1} + C_{i2} + ⋯ + C_{is_{i}}

C_{ij} perfectos con mínima distancia 2f_{i} + 1:

r = s, e_{i} = f_{i}, C_{i}^{e_{i}} = D_{i}^{e_{i}}

y existe σ_{i} ∈ S_{r_{i}}; C_{ij} = D_{iσ_{i}(j)}.

\underline{Conclusión}: Un código CDU puede expresarse como suma de códigos perfectos D_{i}^{e_{i}} y esencialmente en forma única. Con vistas a la demostración de la conjetura planteada (un código CDU es suma directa de perfectos) restaría pues por probar la nulidad de las intersecciones de los D_{i}^{e_{i}}.

References

[1] G. Cohen, J. Rif, J. Tena, G. Zemor. On the Characterization of Linear Uniquely Decodable Codes, preprint.

[2] F.J. MacWilliams, N.J. Sloane. The Theory of Error–Correcting Codes. North Holland Publishing Co. 1977.

[3] C. Munuera, J. Tena Codificación de la Información. Universidad de Valladolid, 1997.

[4] C.E. Shannon A Mathematical Theory of Communication. Bell System Technical Journal 28, 1948, pp. 623-656.