Saltar al contenido principal
LibreTexts Español

8.3: Códigos lineales

  • Page ID
    111139
  • \( \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}}\)

    \( \newcommand{\vectorA}[1]{\vec{#1}}      % arrow\)

    \( \newcommand{\vectorAt}[1]{\vec{\text{#1}}}      % arrow\)

    \( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vectorC}[1]{\textbf{#1}} \)

    \( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)

    \( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)

    \( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)

    \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

    \(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)

    Para obtener más conocimiento de un código en particular y desarrollar técnicas más eficientes de codificación, decodificación y detección de errores, necesitamos agregar estructura adicional a nuestros códigos. Una forma de lograr esto es exigir que el código también sea un grupo. Un código de grupo es un código que también es un subgrupo de\({\mathbb Z}_2^n\text{.}\)

    Para verificar que un código sea un código de grupo, solo necesitamos verificar una cosa. Si agregamos dos elementos cualesquiera en el código, el resultado debe ser una\(n\) -tuple que vuelva a estar en el código. No es necesario verificar que la inversa de la\(n\) -tupla esté en el código, ya que cada palabra clave es su propia inversa, ni es necesario verificar que\({\mathbf 0}\) sea una palabra clave. Por ejemplo,

    \[ (11000101) + (11000101) = (00000000)\text{.} \nonumber \]
    Ejemplo\(8.16\)

    Supongamos que tenemos un código que consta de las siguientes 7-tuplas:

    \ begin {alinear*} & (0000000) & & (0001111) & & (0010101) & (0011010)\\ & (0100110) & (0101001) & (0110011) & (0110011) & (0111100)\ & (1000011) & (1001100) & (1010110) & (1011001)\ & (1100101) & & (1101010) & ( 1110000) & & (1111111)\ text {.} \ end {alinear*}

    Solución

    Es una tarea sencilla aunque tediosa verificar que este código es también un subgrupo\({\mathbb Z}_2^7\) y, por lo tanto, un código de grupo. Este código es un único código de detección de errores y único de corrección de errores, pero es un proceso largo y tedioso para calcular todas las distancias entre pares de palabras clave para determinar que\(d_{\min} = 3\text{.}\) es mucho más fácil ver que el peso mínimo de todas las palabras de código distintas de cero es\(3\text{.}\) Como veremos pronto, esto no es una coincidencia. Sin embargo, la relación entre pesos y distancias en un código particular depende en gran medida del hecho de que el código sea un grupo.

    Lema\(8.17\)

    Dejar\({\mathbf x}\) y\({\mathbf y}\) ser binarios\(n\) -tuplas. Entonces\(w({\mathbf x} + {\mathbf y}) = d({\mathbf x}, {\mathbf y})\text{.}\)

    Prueba

    Supongamos que\({\mathbf x}\) y\({\mathbf y}\) son\(n\) -tuplas binarias. Entonces la distancia entre\({\mathbf x}\) y\({\mathbf y}\) es exactamente el número de lugares en los que\({\mathbf x}\) y\({\mathbf y}\) difieren. Pero\({\mathbf x}\) y\({\mathbf y}\) difieren en una coordenada particular exactamente cuando la suma en la coordenada es\(1\text{,}\) desde

    \ begin {alinear*} 1 + 1 & = 0\\ 0 + 0 & = 0\\ 1 + 0 & = 1\\ 0 + 1 & = 1\ text {.} \ end {alinear*}

    En consecuencia, el peso de la suma debe ser la distancia entre las dos palabras clave.

    Teorema\(8.18\)

    Let\(d_{\min}\) be the minimum distance for a group code\(C\text{.}\) then\(d_{\min}\) is the minimum weight of all the nonzero codewords in\(C\text{.}\) There is,

    \[ d_{\min} = \min\{ w({\mathbf x}) : { {\mathbf x} \neq {\mathbf 0} } \}\text{.} \nonumber \]
    Prueba

    Observe que

    \ begin {align*} d_ {\ min} & =\ min\ {d ({\ mathbf x}, {\ mathbf y}): {\ mathbf x}\ neq {\ mathbf y}\}\\ &=\ min\ {d ({\ mathbf x}, {\ mathbf y}): {\ mathbf x} + {\ mathbf y}\ neq\ mathbf 0}\}\\ &=\ min\ {w ({\ mathbf x} + {\ mathbf y}): {\ mathbf x} + {\ mathbf y}\ neq {\ mathbf 0}\}\\ & =\ min\ {w ({\ mathbf z}): { \ mathbf z}\ neq {\ mathbf 0}\}\ texto {.} \ end {alinear*}

    Códigos Lineales

    A partir de Ejemplo\(8.16\), ahora es fácil verificar que el peso mínimo distinto de cero es\(3\text{;}\) por lo tanto, el código efectivamente detecta y corrige todos los errores individuales. Ahora hemos reducido el problema de encontrar códigos “buenos” al de generar códigos de grupo. Una manera fácil de generar códigos de grupo es emplear un poco de teoría matricial.

    Definir el producto interno de dos\(n\) -tuplas binarias para ser

    \[ {\mathbf x} \cdot {\mathbf y} = x_1 y_1 + \cdots + x_n y_n\text{,} \nonumber \]

    donde\({\mathbf x} = (x_1, x_2, \ldots, x_n)^\transpose\) y\({\mathbf y} = (y_1, y_2, \ldots, y_n)^\transpose\) son vectores de columna. 5 Por ejemplo, si\({\mathbf x} = (011001)^\transpose\) y\({\mathbf y} = (110101)^\transpose\text{,}\) entonces también\({\mathbf x} \cdot {\mathbf y} = 0\text{.}\) podemos mirar un producto interno como el producto de una matriz de filas con una matriz de columnas; es decir,

    \ begin {align*} {\ mathbf x}\ cdot {\ mathbf y} & = {\ mathbf x} ^\ transpone {\ mathbf y}\\ & =\ begin {pmatrix} x_1 & x_2 &\ cdots & x_n\ end {pmatrix}\ begin {pmatrix} y_1\ y_2\\\ vdots\\ y_n\ end {pmatrix} matriz}\\ & = x_ {1} y_ {1} + x_ {2} y_ {2} +\ cdots + x_ {n} y_ {n}\ texto {.} \ end {alinear*}
    Ya que estaremos trabajando con matrices, escribiremos\(n\) -tuplas binarias como vectores de columna para el resto de este capítulo.
    Ejemplo\(8.19\)

    Supongamos que las palabras a codificar constan de todas las\(3\) -tuplas binarias y que nuestro esquema de codificación es paridad.

    Solución

    Para codificar una\(3\) -tupla arbitraria, agregamos un cuarto bit para obtener un número par de\(1\) s. Observe que una\(n\) -tupla arbitraria\({\mathbf x} = (x_1, x_2, \ldots, x_n)^\transpose\) tiene un número par de\(1\) s exactamente cuando,\(x_1 + x_2 + \cdots + x_n = 0\text{;}\) por lo tanto, una\(4\) -tupla\({\mathbf x} = (x_1, x_2, x_3, x_4)^\transpose\) tiene un número par de\(1\) s si\(x_1+ x_2+ x_3+ x_4 = 0\text{,}\) o

    \[ {\mathbf x} \cdot {\mathbf 1} = {\mathbf x}^\transpose {\mathbf 1} = \begin{pmatrix} x_1 & x_2 & x_3 & x_4 \end{pmatrix} \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix} = 0\text{.} \nonumber \]

    Este ejemplo nos lleva a esperar que exista una conexión entre las matrices y la teoría de la codificación.

    Dejar\({\mathbb M}_{m \times n}({\mathbb Z}_2)\) denotar el conjunto de todas las\(m \times n\) matrices con entradas en\({\mathbb Z}_2\text{.}\) Hacemos operaciones matriciales como de costumbre excepto que todas nuestras operaciones de suma y multiplicación ocurren en\({\mathbb Z}_2\text{.}\) Definir el espacio nulo de una matriz\(H \in {\mathbb M}_{m \times n}({\mathbb Z}_2)\) para que sea el conjunto de todos los binarios\(n\) - tuplas\({\mathbf x}\) tales que\(H{\mathbf x} = {\mathbf 0}\text{.}\) denotamos el espacio nulo de una matriz\(H\) por\(\Null(H)\text{.}\)

    Ejemplo\(8.20\)

    Supongamos que

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

    Para\({\mathbf x} = (x_1, x_2, x_3, x_4, x_5)^\transpose\) que una\(5\) -tupla esté en el espacio nulo de\(H\text{,}\)\(H{\mathbf x} = {\mathbf 0}\text{.}\) Equivalentemente, se debe cumplir el siguiente sistema de ecuaciones:

    \ begin {alinear*} x_2 + x_4 & = 0\\ x_1 + x_2 + x_3 + x_4 & = 0\\ x_3 + x_4 + x_5 & = 0\ texto {.} \ end {alinear*}

    Solución

    El conjunto de\(5\) -tuplas binarias que satisfacen estas ecuaciones es

    \[ (00000) \qquad (11110) \qquad (10101) \qquad (01011)\text{.} \nonumber \]

    Este código se determina fácilmente como un código de grupo.

    Teorema\(8.21\)

    Let\(H\) be in\({\mathbb M}_{m \times n}({\mathbb Z}_2)\text{.}\) Entonces el espacio nulo de\(H\) es un código de grupo.

    Prueba

    Dado que cada elemento de\({\mathbb Z}_2^n\) es su propio inverso, lo único que realmente hay que verificar aquí es el cierre. Vamos\({\mathbf x}, {\mathbf y} \in \Null(H)\) por alguna matriz\(H\) en\({\mathbb M}_{m \times n}({\mathbb Z}_2)\text{.}\) Entonces\(H{\mathbf x} = {\mathbf 0}\) y\(H{\mathbf y} = {\mathbf 0}\text{.}\) Así

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

    De ahí\({\mathbf x} + {\mathbf y}\) que esté en el espacio nulo de\(H\) y por lo tanto debe ser una palabra clave.

    Un código es un código lineal si está determinado por el espacio nulo de alguna matriz\(H \in {\mathbb M}_{m \times n}({\mathbb Z}_2)\text{.}\)

    Ejemplo\(8.22\)

    Dejar\(C\) ser el código dado por la matriz

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

    Solución

    Supongamos que\({\mathbf x} = (010011)^\transpose\) se recibe la\(6\) -tuple. Es una simple cuestión de multiplicación matricial determinar si\({\mathbf x}\) es o no una palabra clave. Desde

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

    la palabra recibida no es una palabra clave. Debemos o bien intentar corregir la palabra o solicitar que se vuelva a transmitir.


    This page titled 8.3: Códigos lineales 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.