Siguiente: Segundas listas Arriba: Códigos lineales Anterior: Pesos mínimos

Arreglos estándares

Sea $\mathbb{K}$ un campo finito y sea $C$ un código lineal-$(n,k,d)$. Al ser $C$ un subespacio, el cociente $\mathbb{K}^n/C=\{{\bf y}+C\vert\,{\bf y}\in\mathbb{K}^n\}$ es a su vez un espacio vectorial sobre $\mathbb{K}$. Naturalmente, dos palabras cualesquiera ${\bf y},{\bf z}\in\mathbb{K}^n$ en una misma clase del cociente $\mathbb{K}^n/C$, es decir, tales que ${\bf z}-{\bf y}\in C$, han de poseer el mismo síndrome: $B{\bf z}=B{\bf y}$ donde $B\in\mathbb{K}^{(n-k)\times n}$ es la matriz revisora de paridad de $C$.

También, si al transmitir una palabra en el código, digamos ${\bf y}\in C$, se recibiera la palabra ${\bf z}\in \mathbb{K}^n$ entonces para el error ${\bf e}={\bf z}-{\bf y}$ se habría de tener $B{\bf e}=B{\bf z}$. Así pues, el síndrome del error ha de coincidir con el síndrome de la palabra recibida, lo que, por lo anterior, equivale a que la palabra recibida ${\bf z}$ y el error cometido ${\bf e}$ necesariamente han de estar en una misma clase lateral de $\mathbb{K}^n/C$.

Definición 5.7   Para cada clase ${\bf z}+C\in\mathbb{K}^n/C$, un representante principal de ella es un vector ${\bf e}\in{\bf z}+C$ de peso de Hamming mínimo.

Por el Teorema Fundamental de Homomorfismos se tiene que $B:\mathbb{K}^n/C\to \mbox{Img}(B)$ es un isomorfismo. Así, para cada posible valor de síndrome ${\bf s}\in\mbox{Img}(B)<\mathbb{K}^{n-k}$ existe una única clase lateral ${\bf z}_s+C\in\mathbb{K}^n/C$ tal que $B({\bf z}_s+C)={\bf s}$. Sea ${\bf e}_s$ un representante principal de la clase ${\bf z}_s+C$. Resulta entonces un

Procedimiento de decodificación.

Supóngase que al transmitir una palabra ${\bf y}\in C$ se recibe la palabra ${\bf z}\in \mathbb{K}^n$ cometiéndose el error ${\bf e}={\bf z}-{\bf y}$. Entonces se calcula el síndrome ${\bf s} = B{\bf z}$ y, considerando el representante principal ${\bf e}_s$, se recupera la palabra transmitida tomando ${\bf z}-{\bf e}_s$.

Este procedimiento es, claramente, correcto toda vez que ${\bf e}={\bf e}_s$. Una manera de sistematizarlo es la siguiente:

Definición 5.8   El arreglo estándar del espacio $\mathbb{K}^n$, mediante el código $C$, es la matriz

$$K_n = \left[{\bf y}_{ij}\right]_{i\in[\![0,q^{n-k}-1]\!]}^{j\in[\![0,q^{k}-1]\!]}$$

tal que

• cada renglón es una clase, i.e. $\forall i\in[\![0,q^{n-k}-1]\!]$ $\exists {\bf y}_{i}\in\mathbb{K}^n$: $\left\{{\bf y}_{ij}\right\}_{j\in[\![0,q^{k}-1]\!]}={\bf y}_{i}+C$,
• el primer renglón consiste de las palabras de código, i.e. ${\bf y}_{0}={\bf0}$,
• la primera columna consta de representantes principales, i.e. ${\bf y}_{i0}$ es de peso mínimo en ${\bf y}_{i}+C$, y
• en cada entrada aparece la suma del representante principal de la clase con la correspondiente palabra de código, i.e. $\forall {i\in[\![0,q^{n-k}-1]\!]},{j\in[\![0,q^{k}-1]\!]}$: ${\bf y}_{ij}={\bf y}_{i0}+{\bf y}_{0j}$.

Utilizando el arreglo estándar se tiene el siguiente:

Procedimiento de decodificación.

Supóngase que al transmitir una palabra ${\bf y}\in C$ se recibe la palabra ${\bf z}\in \mathbb{K}^n$ cometiéndose el error ${\bf e}={\bf z}-{\bf y}$. Entonces se localiza en $K_n$ los índices $i,j$ tales que ${\bf z}={\bf y}_{ij}$, y se toma a ${\bf y}_{0j}\in C$ como la palabra original ${\bf y}$.

Este procedimiento es, claramente, correcto toda vez que el error ${\bf e}$ coincida con el representante principal ${\bf y}_{i0}$ de la clase ${\bf y}_{i}+C$ en la que apareció ${\bf z}$.

Siguiente: Segundas listas Arriba: Códigos lineales Anterior: Pesos mínimos