Saltar al contenido principal
LibreTexts Español

8.5: Decodificación eficiente

  • Page ID
    111132
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Ahora estamos en la etapa en la que somos capaces de generar códigos lineales que detectan y corrigen errores con bastante facilidad, pero sigue siendo un proceso que lleva mucho tiempo decodificar una\(n\) -tuple recibida y determinar cuál es la palabra clave más cercana, porque la\(n\) -tuple recibida debe compararse con cada posible palabra de código para determinar la decodificación adecuada. Esto puede ser un impedimento grave si el código es muy grande.

    Ejemplo\(8.35\)

    Dada la matriz binaria

    \[ H = \begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \end{pmatrix} \nonumber \]

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

    Solución

    podemos computar

    \[ H{\mathbf x} = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix} \qquad \text{and} \qquad H{\mathbf y} = \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix}\text{.} \nonumber \]

    De ahí,\({\mathbf x}\) es una palabra clave y no lo\({\mathbf y}\) es, ya que\({\mathbf x}\) está en el espacio nulo y no lo\({\mathbf y}\) es. Observe que\(H{\mathbf y}\) es idéntico a la primera columna de\(H\text{.}\) De hecho, aquí es donde ocurrió el error. Si volteamos el primer bit\({\mathbf y}\) de\(0\) a\(1\text{,}\) entonces obtenemos\({\mathbf x}\text{.}\)

    Si\(H\) es una\(m \times n\) matriz 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 rápida detección y corrección de errores.

    Proposición\(8.36\)

    Deje que la matriz\(m \times n\) binaria\(H\) determine un código lineal y deje que\({\mathbf x}\) sea la\(n\) -tuple recibida. Escribe\({\mathbf x}\) como\({\mathbf x} = {\mathbf c} +{\mathbf e}\text{,}\) donde\({\mathbf c}\) está la palabra de código transmitida y\({\mathbf e}\) es el error de transmisión. Entonces el síndrome\(H{\mathbf x}\) de la palabra clave recibida\({\mathbf x}\) es también el síndrome del error\({\mathbf e}\text{.}\)

    Prueba

    La prueba se desprende del hecho de que

    \[ H{\mathbf x} = H({\mathbf c} +{\mathbf e}) = H{\mathbf c} + H{\mathbf e} = {\mathbf 0} + H{\mathbf e} = H{\mathbf e}\text{.} \nonumber \]

    Esta proposición nos dice que el síndrome de una palabra recibida depende únicamente del error y no de la palabra clave transmitida. La prueba del siguiente teorema se desprende inmediatamente de la Proposición\(8.36\) y del hecho de que\(H{\mathbf e}\) es la columna\(i\) th de la matriz\(H\text{.}\)

    Teorema\(8.37\)

    Vamos\(H \in {\mathbb M}_{ m \times n} ( {\mathbb Z}_2)\) y supongamos que el código lineal correspondiente a\(H\) es un solo error de corrección. Dejar\({\mathbf r}\) ser una\(n\) -tuple recibida que se transmitió con como mucho un error. Si el síndrome de\({\mathbf r}\) es\({\mathbf 0}\text{,}\) entonces no se ha producido ningún error; de lo contrario, si el síndrome de\({\mathbf r}\) es igual a alguna columna de\(H\text{,}\) digamos la columna\(i\) th, entonces el error ha ocurrido en el \(i\)bit th

    Ejemplo\(8.38\)

    Considerar la matriz

    \[ H = \begin{pmatrix} 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 \end{pmatrix} \nonumber \]

    y supongamos que las\(6\)\({\mathbf x} = (111110)^{t}\text{,}\)\({\mathbf y} = (111111)^{t}\text{,}\) -tuplas\({\mathbf z} = (010111)^{t}\) ya han sido recibidas.

    Solución

    Entonces

    \[ 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}\text{.} \nonumber \]

    De ahí\({\mathbf x}\) que tenga un error en el tercer bit y\({\mathbf z}\) tenga un error en el cuarto bit. Las palabras clave transmitidas para\({\mathbf x}\) y\({\mathbf z}\) deben haber sido\((110110)\) y\((010011)\text{,}\) respectivamente. El síndrome de\({\mathbf y}\) no ocurre en ninguna de las columnas de la matriz\(H\text{,}\) por lo que deben haber ocurrido múltiples errores para producir\({\mathbf y}\text{.}\)

    Decodificación Coset

    Podemos usar la teoría de grupos para obtener otra forma de decodificar mensajes. Un código lineal\(C\) es un subgrupo de\({\mathbb Z}_2^n\text{.}\) Coset o decodificación estándar utiliza los coconjuntos de\(C\) in\({\mathbb Z}_2^n\) para implementar la decodificación de máxima verosimilitud. Supongamos que\(C\) es un código\((n,m)\) -lineal. Un coset de\(C\) in\({\mathbb Z}_2^n\) está escrito en la forma\({\mathbf x} + C\text{,}\) donde\({\mathbf x} \in {\mathbb Z}_2^n\text{.}\) Por Teorema de Lagrange (Teorema\(6.10\)), hay\(2^{n-m}\) distintos cosets de\(C\) in\({\mathbb Z}_2^n\text{.}\)

    Ejemplo\(8.39\)

    Dejar\(C\) ser el código\((5,3)\) -lineal dado por la matriz de comprobación de paridad

    \[ H = \begin{pmatrix} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{pmatrix}\text{.} \nonumber \]

    Solución

    El código consta de las palabras clave

    \[ (00000) \quad (01101) \quad (10011) \quad (11110)\text{.} \nonumber \]

    Hay\(2^{5-2} = 2^3\) cosets de\(C\) en\({\mathbb Z}_2^5\text{,}\) cada uno con orden\(2^2 =4\text{.}\) Estos cosets se enumeran en Tabla\(8.40\).

    \(Table \text { } 8.40.\)Cosets de\(C\)

    Coset Coset
    Representante
    \(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)\)

    Nuestra tarea es averiguar cómo conocer los cosets podría ayudarnos a decodificar un mensaje. Supongamos que esa\({\mathbf x}\) era la palabra de código original enviada y esa\({\mathbf r}\) es la\(n\) -tuple recibida. Si\({\mathbf e}\) es el error de transmisión, entonces\({\mathbf r} = {\mathbf e} + {\mathbf x}\) o, equivalentemente,\({\mathbf x} = {\mathbf e} + {\mathbf r}\text{.}\) Sin embargo, esta es exactamente la afirmación que\({\mathbf r}\) es un elemento en el coset\({\mathbf e} + C\text{.}\) En la decodificación de máxima verosimilitud esperamos\({\mathbf e}\) que el error sea lo más pequeño posible; es decir,\({\mathbf e}\) tendrá el menor peso. Una\(n\) -tupla de menor peso en un coset se llama líder de coset. Una vez que hemos determinado un líder de coset para cada coset, el proceso de decodificación se convierte en una tarea de cálculo\({\mathbf r} + {\mathbf e}\) para obtener\({\mathbf x}\text{.}\)

    Ejemplo\(8.41\)

    En la Tabla 8.40, observe que hemos elegido un representante del menor peso posible para cada coconjunto.

    Solución

    Estos representantes son líderes coset. Ahora supongamos que esa\({\mathbf r} = (01111)\) es la palabra recibida. Para decodificar\({\mathbf r}\text{,}\) encontramos que está en el coset\((00010) + C\text{;}\) por lo tanto, la palabra clave originalmente transmitida debe haber sido\((01101) = (01111) + (00010)\text{.}\)

    Un problema potencial con este método de decodificación es que podríamos tener que examinar cada coset para la palabra de código recibida. La siguiente proposición da un método para implementar la decodificación de coset. Afirma que podemos asociar un síndrome con cada coset; de ahí que podamos hacer una tabla que designe a un coset líder correspondiente a cada síndrome. Dicha lista se llama tabla de decodificación.

    \(Table \text { } 8.42\). Síndromes para cada coconjunto

    Síndrome Líder de Coset
    \((000)\) \((00000)\)
    \((001)\) \((00001)\)
    \((010)\) \((00010)\)
    \((011)\) \((10000)\)
    \((100)\) \((00100)\)
    \((101)\) \((01000)\)
    \((110)\) \((00110)\)
    \((111)\) \((10100)\)
    Proposición\(8.43\)

    Dejar\(C\) ser un código\((n,k)\) -lineal dado por la matriz\(H\) y supongamos que\({\mathbf x}\) y\({\mathbf y}\) están en\({\mathbb Z}_2^n\text{.}\) Entonces\({\mathbf x}\) y\({\mathbf y}\) están en el mismo coconjunto de\(C\) si y solo si Es\(H{\mathbf x} = H{\mathbf y}\text{.}\) decir, dos\(n\) -tuplas están en el mismo coset si y solo si sus síndromes son los mismos.

    Prueba

    Dos\(n\) -tuplas\({\mathbf x}\) y\({\mathbf y}\) están en el mismo coset de\(C\) exactamente cuando\({\mathbf x} - {\mathbf y} \in C\text{;}\) sin embargo, esto es equivalente a\(H({\mathbf x} - {\mathbf y}) = 0\) o\(H {\mathbf x} = H{\mathbf y}\text{.}\)

    Ejemplo\(8.44\)

    Tabla\(8.42\) es una tabla de decodificación para el código\(C\) dado en Ejemplo\(8.39\). Si\({\mathbf x} = (01111)\) se recibe,

    Solución

    entonces su síndrome se puede computar para ser

    \[ H {\mathbf x} = \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}\text{.} \nonumber \]

    Al examinar la tabla de decodificación, determinamos que el líder de coset\((00010)\text{.}\) es Ahora es fácil decodificar la palabra de código recibida.

    Dado un código\((n,k)\) -block, surge la pregunta de si la decodificación de coset es o no un esquema manejable. Una tabla de decodificación requiere una lista de coconjuntos y síndromes, uno para cada uno de los\(2^{n - k}\) coconjuntos de\(C\text{.}\) Supongamos que tenemos un código\((32, 24)\) -block. Tenemos una gran cantidad de palabras clave,\(2^{24}\text{,}\) sin embargo solo hay\(2^{32 - 24} = 2^{8} = 256\) cosets.


    This page titled 8.5: Decodificación eficiente is shared under a GNU Free Documentation License 1.3 license and was authored, remixed, and/or curated by Thomas W. Judson (Abstract Algebra: Theory and Applications) via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.