[skip-to-content]
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \renewcommand{\gcd}{\operatorname{mcd}} \renewcommand{\lcm}{\operatorname{mcm}} \renewcommand{\deg}{\operatorname{gr}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Sección8.4Decodificación Eficiente

Estamos ahora en el punto donde somos capaces de generar códigos lineales que detecten y corrijan errores con relativa facilidad, pero aún es un proceso lento el de decodificar una \(n\)-tupla recibida y determinar cuál es la palabra del código más cercana, pues la \(n\)-tupla recibida debe ser comparada con todas las posibles palabras del código para determinar la decodificación apropiada. Este puede ser un impedimento serio si el código es muy grande.

Ejemplo8.35

Dada la matriz binaria

\begin{equation*} H = \begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \end{pmatrix} \end{equation*}

y las 5-tuplas \({\mathbf x} = (11011)^{\rm t}\) and \({\mathbf y} = (01011)^{\rm t}\text{,}\) podemos calcular

\begin{equation*} H{\mathbf x} = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix} \qquad \text{and} \qquad H{\mathbf y} = \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix}. \end{equation*}

Luego, \({\mathbf x}\) es una palabra del código e \({\mathbf y}\) no lo es, pues \({\mathbf x}\) está en el espacio nulo e \({\mathbf y}\) no lo está. Notemos que \(H{\mathbf y}\) es idéntica a la primera columna de \(H\text{.}\) De hecho, es ahí donde ocurrió el error. Si cambiamos el primer bit en \({\mathbf y}\) de 0 a 1, obtenemos \({\mathbf x}\text{.}\)

Si \(H\) es una matriz de \(m \times n\) y \({\mathbf x} \in {\mathbb Z}_2^n\text{,}\) entonces decimos que el síndrome de \({\mathbf x}\) es \(H{\mathbf x}\text{.}\) La siguiente proposición permite la detección y corrección rápida de errores.

La demostración sigue del hecho que

\begin{equation*} H{\mathbf x} = H({\mathbf c} +{\mathbf e}) = H{\mathbf c} + H{\mathbf e} = {\mathbf 0} + H{\mathbf e} = H{\mathbf e}. \end{equation*}

Esta proposición nos dice que el síndrome de una palabra recibida depende solamente del error y no de la palabra trasmitida. La demostración del siguiente teorema sigue inmediatamente de la Proposición 8.36 y del hecho que \(H{\mathbf e}\) es la \(i\)-ésima columna de la matriz \(H\text{.}\)

Ejemplo8.38

Consideremos la matriz

\begin{equation*} H = \begin{pmatrix} 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 \end{pmatrix} \end{equation*}

y supongamos que las 6-tuples \({\mathbf x} = (111110)^{\rm t}\text{,}\) \({\mathbf y} = (111111)^{\rm t}\text{,}\) y \({\mathbf z} = (010111)^{\rm t}\) fueron recibidas. Entonces

\begin{equation*} H{\mathbf x} = \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix}, H{\mathbf y} = \begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix}, H{\mathbf z} = \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}. \end{equation*}

Luego, \({\mathbf x}\) tiene un error en el tercer bit y \({\mathbf z}\) tiene un error en el cuarto bit. Las palabras trasmitidas para \({\mathbf x}\) y \({\mathbf z}\) deben haber sido \((110110)\) y \((010011)\text{,}\) respectivamente. El síndrome de \({\mathbf y}\) no aparece en ninguna de las columnas de \(H\text{,}\) de manera que más de un error debe haber ocurrido para producir \({\mathbf y}\text{.}\)

SubsecciónDecodificación por Clases Laterales

Podemos usar teoría de grupos para obtener otro método de decodificación. Un código lineal \(C\) es un subgrupo de \({\mathbb Z}_2^n\text{.}\) Decodificación por Clases Laterales o decodificación estándar usa las clases laterales de \(C\) en \({\mathbb Z}_2^n\) para implementar la decodificación de probabilidad máxima. Supongamos que \(C\) un código lineal \((n,m)\text{.}\) Una clase lateral de \(C\) en \({\mathbb Z}_2^n\) se escribe en la forma \({\mathbf x} + C\text{,}\) donde \({\mathbf x} \in {\mathbb Z}_2^n\text{.}\) Por el Teorema de Lagrange (Teorema 6.10), hay \(2^{n-m}\) clases laterales de \(C\) en \({\mathbb Z}_2^n\text{.}\)

Ejemplo8.39

Sea \(C\) el código lineal \((5,3)\) dado por la matriz verificadora

\begin{equation*} H = \begin{pmatrix} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{pmatrix}. \end{equation*}

El código consiste de las palabras

\begin{equation*} (00000) \quad (01101) \quad (10011) \quad (11110). \end{equation*}

Hay \(2^{5-2} = 2^3\) clases laterales de \(C\) en \({\mathbb Z}_2^5\text{,}\) cada una de orden \(2^2 =4\text{.}\) Estas clases laterales aparecen en la Tabla 8.40.

Representante Clase lateral
de la clase
\(C\) (00000) (01101) (10011) (11110)
\((10000) + C\) (10000) (11101) (00011) (01110)
\((01000) + C\) (01000) (00101) (11011) (10110)
\((00100) + C\) (00100) (01001) (10111) (11010)
\((00010) + C\) (00010) (01111) (10001) (11100)
\((00001) + C\) (00001) (01100) (10010) (11111)
\((10100) + C\) (00111) (01010) (10100) (11001)
\((00110) + C\) (00110) (01011) (10101) (11000)
Cuadro8.40Clases laterales de \(C\)

Nuestra tarea es descubrir cómo conocer las clases laterales nos puede ayudar a decodificar un mensaje. Supongamos que \({\mathbf x}\) era la palabra trasmitida y que \({\mathbf r}\) es la \(n\)-tupla recibida. Si \({\mathbf e}\) es el error de trasmisión, entonces \({\mathbf r} = {\mathbf e} + {\mathbf x}\) o, equivalentemente, \({\mathbf x} = {\mathbf e} + {\mathbf r}\text{.}\) Pero, esto es exactamente equivalente a decir que \({\mathbf r}\) es un elemento de la clase \({\mathbf e} + C\text{.}\) En la decodificación de máxima probabilidad esperamos que \({\mathbf e}\) sea lo más pequeño que se pueda; es decir, \({\mathbf e}\) tendrá el menor peso. Una \(n\)-tupla de peso mínimo en una clase se denomina líder de clase. Una vez que hemos determinado un líder para cada clase, el proceso de decodificación se transforma en el de calcular \({\mathbf r} + {\mathbf e}\) para obtener \({\mathbf x}\text{.}\)

Ejemplo8.41

En la Tabla 8.40, note que hemos elegido un representante de peso mínimo para cada clase. Estos representantes son líderes de clase. Ahora supongamos que recibimos la palabra \({\mathbf r} = (01111)\text{.}\) Para decodificar \({\mathbf r}\text{,}\) lo encontramos en la clase \((00010) + C\text{;}\) luego, la palabra del código originalmente trasmitida debe haber sido \((01101) = (01111) + (00010)\text{.}\)

Un problema potencial con este método de decodificación es que tengamos que examinar cada clase en busca de la palabra recibida. La siguiente proposición entrega un método para la implementación de la decodificación por clases laterales. Establece que podemos asociar un síndrome con cada clase; luego, podemos hacer una tabla que asigna un líder de clase a cada síndrome. Tal lista se denomina tabla de decodificación.

Síndromes Líder de clase
(000) (00000)
(001) (00001)
(010) (00010)
(011) (10000)
(100) (00100)
(101) (01000)
(110) (00110)
(111) (10100)
Cuadro8.42Síndromes para cada clase

Dos \(n\)-tuplas \({\mathbf x}\) e \({\mathbf y}\) están en la misma clase lateral de \(C\) precisamente cuando \({\mathbf x} - {\mathbf y} \in C\text{;}\) pero, esto es equivalente a que \(H({\mathbf x} - {\mathbf y}) = 0\) o \(H {\mathbf x} = H{\mathbf y}\text{.}\)

Ejemplo8.44

La Tabla 8.42 es una tabla de decodificación para el código \(C\) dado en el Ejemplo 8.39. Si se recibe \({\mathbf x} = (01111)\text{,}\) entonces su síndrome se calcula como

\begin{equation*} H {\mathbf x} = \begin{pmatrix} 0 \\ 1 \\ 1 \end{pmatrix}. \end{equation*}

Examinando la tabla de decodificación, determinamos que el líder de clase es \((00010)\text{.}\) Es fácil ahora decodificar la palabra recibida.

Dado un código de bloque \((n,k)\text{,}\) surge la pregunta si la decodificación por clases laterales es un sistema manejable o no. Una tabla de decodificación requiere una lista de líderes de clases laterales y síndromes uno para cada una de las \(2^{n - k}\) clases laterales de \(C\text{.}\) Supongamos que tenemos un código de bloque \((32, 24)\text{.}\) Tenemos una enorme cantidad de palabras en el código, \(2^{24}\text{,}\) pero hay solamente \(2^{32 - 24} = 2^{8} = 256\) clases laterales.