Código sistemático

[gL.edu] Este artículo recoge contribuciones de Daniel Gracia Garallar, elaboradas en el contexto de la Clarificación conceptual en torno a la "teoría de la información", bajo la supervisión de José María Díaz Nafría.

En el contexto de teoría de la información, se denomina código sistemático al código de bloque que mantiene los símbolos de entrada inalterados y, además, añade información de paridad ya sea al principio o al final, con el objeto de detectar y corregir errores.

Propiedades

Suponiendo el código de bloque lineal ${\mathcal {C}}[n,k]$, definido en el subespacio vectorial ${\mathcal {L}}_{n}$ de dimensión $k$ y matriz generadora $G$

$G_{k\times n}={\begin{pmatrix}g_{1}\\g_{2}\\\cdots \\g_{k}\end{pmatrix}}={\begin{pmatrix}g_{1,1}&g_{1,2}&\cdots &g_{1,n}\\g_{2,1}&g_{2,2}&\cdots &g_{2,n}\\\cdots &\cdots &\ddots &\vdots \\g_{k,1}&g_{k,2}&\cdots &g_{k,n}\end{pmatrix}}$

con vectores $g_{i}$ linealmente independientes, aplicando reducción por filas (método de Gauss-Jordan) y reordenando las columnas, siempre podemos encontrar una matriz $G'=F\cdot G\cdot P$ (donde $F$ es no singular y $P$ es una matriz de permutación) tal que:

$G'_{k\times n}={\begin{pmatrix}I_{k}&|&A_{k\times (n-k)}\end{pmatrix}}={\begin{pmatrix}1&0&\cdots &0&a_{1,1}&\cdots &a_{1,n-k}\\0&1&\cdots &0&a_{2,1}&\cdots &a_{2,n-k}\\\cdots &\cdots &\cdots &\cdots &\cdots &\ddots &\vdots \\0&0&\cdots &1&a_{k,1}&\cdots &a_{k,n-k}\end{pmatrix}}$

La matriz $G'$, distinguida por la submatriz identidad $I_{k}$ y la submatriz $A_{k\times (n-k)}$ o de paridad, se denomina matriz sistemática, y el código caracterizado por esta, es un código sistemático. Obsérvese que de acuerdo a esta definición las palabras o bloques de código contiene al principio los mensajes a los que sigue un conjunto de valores de paridad de dimensión $r=n-k$.

Las matrices $G$ y $G'$ no definen, necesariamente, la misma función de codificación, pero sí el mismo espacio vectorial. Entonces, modelando la fuente de mensajes como una variable aleatoria independiente e idénticamente distribuida, la distribución de probabilidad del nuevo código será igual a la de la distribución original. Se dice así que las matrices generadoras $G$ y $G'$ son equivalentes ya que los códigos que resultan de su aplicación mantienen idénticas propiedades estadísticas relativas —en cuanto a la frecuencia de aparición de cada código—, aunque sean diferentes en su composición simbólica.

Todo código lineal tiene un código lineal sistemático equivalente. Por ende, cualquier código lineal con matriz generadora $G$ puede ser expresado como un código sistemático $G'$.

Paridad al principio del bloque

Si bien lo indicado supone que el código contiene al principio los datos (o mensajes) y a éstos les sigue la paridad, es evidente se puede extender al caso en el que la paridad se coloca al principio y los datos al final. En dicho caso:

$G''_{k\times n}={\begin{pmatrix}A_{k\times (n-k)}&|&I_{k}\end{pmatrix}}$

Aplicación

Los códigos sistemáticos resultan muy convenientes en su aplicación práctica, ya que el mensaje (o datos) queda directamente accesible en la palabra del código –ya sea al principio o al final–, bien diferenciados de la información redundante (ver código anejo).

Cabe mencionarse entre los códigos de boque de uso frecuente las versiones sistemáticas de los códigos Hamming, códigos BCH, y códigos Reed-Solomon.

Código

A continuación, se presenta un ejemplo de código de MATLAB que permite obtener una matriz generadora sistemática $G'$ a partir de una matriz generadora lineal $G$. Además, calcula la tabla de códigos asociados a ambas matrices en un cuerpo de Galois $\mathrm {GF(2)}$ —i. e., código binario—, habida la convención de referir al término neutro como $0$ (el código no debe utilizarse para cuerpos finitos de cardinal $q\neq 2$).

% Definimos una matriz generadora G arbitraria de vectores linealmente 
% independientes, que puede cambiarse por cualquier otra.
G = [1 0 1 0;
     0 1 1 0;
     1 0 1 1];

% Determinamos las dimensiones de la matriz generadora
[filas, columnas] = size(G);

% Reducimos G por Gauss-Jordan
[R, pivotes] = rref(G);

% Generamos un vector con las posiciones ordinales del subespacio.
% Tomamos las posiciones de columnas pivote en el orden calculado y
% anejamos las columnas que no se hayan pivotado.
vect_cols = linspace(1, columnas, columnas);
cols_ordenadas = [pivotes setdiff(vect_cols, pivotes)];

% Ordenamos la forma reducida según el orden de los pivotes, anejando
% las columnas sin pivote.
G_prima = R(:, cols_ordenadas);

% Podemos codificar los mensajes codificados por las matrices generadoras
% multiplicando ambos. P. ej., podemos tomar el código correspondiente
% al mensaje [0 1 1] como:
u = [0 1 1];
x = u*G_prima;

% Nótese que, para obtener un resultado coherente, debemos considerar
% el espacio GF(2) en el que definimos la operación. En nuestro caso
% concreto, suponiendo lógica binaria, debemos ajustar los resultados 
% obtenidos en función de los posibles desbordamientos por suma.
x = mod(x,2);

% Y mostramos el resultado.
disp(["Mensaje: " num2str(u) "Codificación" num2str(x)]);

% Genera la tabla de símbolos de G y G_prima
msg = dec2bin(linspace(0, 2^filas-1, 2^filas)) - '0';
cod_orig = mod(msg*G, 2);
cod_sist = mod(msg*G_prima, 2);
Mensaje = char(msg + '0');
CodigoOriginal = char(cod_orig + '0');
CodigoSistematico = char(cod_sist + '0');
tabla_cod = table(Mensaje, CodigoOriginal, CodigoSistematico);
disp(tabla_cod);

El código anterior genera la salida:

     "Mensaje: "    "0  1  1"    "Codificación"    "0  1  1  1"
 
     Mensaje    CodigoOriginal    CodigoSistematico
     _______    ______________    _________________
 
       000           0000               0000       
       001           1011               0010       
       010           0110               0101       
       011           1101               0111       
       100           1010               1001       
       101           0001               1011       
       110           1100               1100       
       111           0111               1110