Saltar al contenido principal

# 8.4: Matrices Generadoras y Comprobación de Paridad

$$\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}$$

Necesitamos encontrar una forma sistemática de generar códigos lineales así como métodos rápidos de decodificación. Al examinar las propiedades de una matriz$$H$$ y al elegir cuidadosamente$$H\text{,}$$ es posible desarrollar métodos muy eficientes de codificación y decodificación de mensajes. Para ello, se introducirán generadores estándar y matrices canónicas de comprobación de paridad.

Supongamos que$$H$$ es una$$m \times n$$ matriz con entradas en$${\mathbb Z}_2$$ y$$n \gt m\text{.}$$ Si las últimas$$m$$ columnas de la matriz forman la matriz de$$m \times m$$ identidad,$$I_m\text{,}$$ entonces la matriz es una matriz canónica de verificación de paridad. Más específicamente,$$H= (A \mid I_m)\text{,}$$ dónde$$A$$ está la$$m \times (n-m)$$ matriz

$\begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1,n-m} \\ a_{21} & a_{22} & \cdots & a_{2,n-m} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{m,n-m} \end{pmatrix} \nonumber$

y$$I_m$$ es la matriz$$m \times m$$ de identidad

$\begin{pmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{pmatrix}\text{.} \nonumber$

Con cada matriz canónica de comprobación de paridad podemos asociar una matriz generadora$$n \times (n-m)$$ estándar

$G = \left( \frac{I_{n-m}}{A} \right)\text{.} \nonumber$

Nuestro objetivo será mostrar que$$G {\mathbf x} = {\mathbf y}$$ existe un$$\mathbf x$$ satisfactorio si y solo si$$H{\mathbf y} = {\mathbf 0}\text{.}$$ Dado un bloque de mensaje$${\mathbf x}$$ a codificar, la matriz nos$$G$$ permitirá codificarlo rápidamente en una palabra clave lineal$${\mathbf y}\text{.}$$

## Ejemplo$$8.23$$

Supongamos que tenemos las siguientes ocho palabras para ser codificadas:

$(000), (001), (010), \ldots, (111)\text{.} \nonumber$

Para

$A = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix}\text{,} \nonumber$

el generador estándar asociado y las matrices de comprobación de paridad canónicas son

$G= \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix} \nonumber$

y

$H = \begin{pmatrix} 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 \end{pmatrix}\text{,} \nonumber$

respectivamente.

Solución

Observe que las filas en$$H$$ representan las comprobaciones de paridad en ciertas posiciones de bits en una$$6$$ -tupla. Las$$1$$ s en la matriz de identidad sirven como verificaciones de paridad para las$$1$$ s en la misma fila. Si$${\mathbf x} = (x_1, x_2, x_3, x_4, x_5, x_6)\text{,}$$ entonces

${\mathbf 0} = H{\mathbf x} = \begin{pmatrix} x_2 + x_3 + x_4 \\ x_1 + x_2 + x_5\\ x_1 + x_3 + x_6 \end{pmatrix}\text{,} \nonumber$

que produce un sistema de ecuaciones:

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

Aquí$$x_4$$ sirve como un bit de verificación para$$x_2$$ y$$x_3\text{;}$$$$x_5$$ es un bit de verificación para$$x_1$$ y$$x_2\text{;}$$ y$$x_6$$ es un bit de verificación para$$x_1$$ y$$x_3\text{.}$$ La matriz de identidad mantiene$$x_4\text{,}$$$$x_5\text{,}$$ y$$x_6$$ de tener que verificarse entre sí. De ahí,$$x_1\text{,}$$$$x_2\text{,}$$ y$$x_3$$ puede ser arbitrario pero$$x_4\text{,}$$$$x_5\text{,}$$ y$$x_6$$ debe elegirse para asegurar la paridad. El espacio nulo de$$H$$ se calcula fácilmente para ser

$\begin{array}{cccc} (000000) & (001101) & (010110) & (011011) \\ (100011) & (101110) & (110101) & (111000). \end{array} \nonumber$

Una forma aún más fácil de calcular el espacio nulo es con la matriz generadora$$G$$ (Tabla$$8.24$$).

$$Table \text { } 8.24$$. Un código generado por matriz

 Mensaje Palabra$$\mathbf x$$ Palabra de código$$G \mathbf x$$ $$000$$ $$000000$$ $$001$$ $$001101$$ $$010$$ $$010110$$ $$011$$ $$011011$$ $$100$$ $$100011$$ $$101$$ $$101110$$ $$110$$ $$110101$$ $$111$$ $$111000$$

## Teorema$$8.25$$

Si$$H \in {\mathbb M}_{m \times n}({\mathbb Z}_2)$$ es una matriz canónica de verificación de paridad, entonces$$\Null(H)$$ consiste en todos$${\mathbf x} \in {\mathbb Z}_2^n$$ cuyos primeros$$n-m$$ bits son arbitrarios pero cuyos últimos$$m$$ bits están determinados por$$H{\mathbf x} = {\mathbf 0}\text{.}$$ Cada uno de los últimos$$m$$ bits sirve como un bit de comprobación de paridad par para algunos de los primeros$$n-m$$ bits. De ahí,$$H$$ da lugar a un código$$(n, n-m)$$ -block.

Dejamos la prueba de este teorema como ejercicio. A la luz del teorema, los primeros$$n - m$$ bits en$${\mathbf x}$$ se denominan bits de información y los últimos$$m$$ bits se denominan bits de verificación. En el Ejemplo 8.23, los tres primeros bits son los bits de información y los tres últimos son los bits de verificación.

## Teorema$$8.26$$

Supongamos que$$G$$ es una matriz generadora$$n \times k$$ estándar. Entonces$$C = \left\{{\mathbf y} : G{\mathbf x} ={\mathbf y}\text{ for }{\mathbf x}\in {\mathbb Z}_2^k\right\}$$ es un código$$(n,k)$$ -block. Más específicamente,$$C$$ es un código de grupo.

Prueba

Dejar$$G {\mathbf x}_1 = {\mathbf y}_1$$ y$$G {\mathbf x}_2 ={\mathbf y}_2$$ ser dos palabras clave. Entonces$${\mathbf y}_1 + {\mathbf y}_2$$ está en$$C$$ desde

$G( {\mathbf x}_1 + {\mathbf x}_2) = G {\mathbf x}_1 + G {\mathbf x}_2 = {\mathbf y}_1 + {\mathbf y}_2\text{.} \nonumber$

También debemos mostrar que dos bloques de mensaje no pueden codificarse en la misma palabra de código. Es decir, debemos demostrar que si$$G {\mathbf x} = G {\mathbf y}\text{,}$$ entonces$${\mathbf x} = {\mathbf y}\text{.}$$ Supongamos que$$G {\mathbf x} = G {\mathbf y}\text{.}$$ Entonces

$G {\mathbf x} - G {\mathbf y} = G( {\mathbf x} - {\mathbf y}) = {\mathbf 0}\text{.} \nonumber$

Sin embargo, las primeras$$k$$ coordenadas en$$G( {\mathbf x} - {\mathbf y})$$ son exactamente$$x_1 -y_1, \ldots, x_k - y_k\text{,}$$ ya que están determinadas por la matriz de identidad,$$I_k\text{,}$$ parte de$$G\text{.}$$ Por lo tanto,$$G( {\mathbf x} - {\mathbf y}) = {\mathbf 0}$$ exactamente cuando$${\mathbf x} = {\mathbf y}\text{.}$$

Antes de que podamos probar la relación entre las matrices canónicas de comprobación de paridad y las matrices generadoras estándar, necesitamos probar un lema.

## Lema$$8.27$$

Dejar$$H = (A \mid I_m )$$ ser una matriz$$m \times n$$ canónica de comprobación de paridad y$$G = \left( \frac{I_{n-m} }{A} \right)$$ ser la matriz generadora$$n \times (n-m)$$ estándar correspondiente. Entonces$$HG = {\mathbf 0}\text{.}$$

Prueba

Let$$C = HG\text{.}$$ La entrada$$ij$$ th en$$C$$ es

\ begin {alinear*} c_ {ij} & =\ suma_ {k=1} ^n h_ {ik} g_ {kj}\\ & =\ sum_ {k=1} ^ {n-m} h_ {ik} g_ {kj} +\ sum_ {k=n-m+1} ^n h_ {ik} g_ {kj}\\ & =\ sum_ {k_ {=1} ^ {n-m} a_ {ik}\ delta_ {kj} +\ suma_ {k=n-m+1} ^n\ delta_ {i- (m-n), k} a_ {kj}\\ & = a_ {ij} + a_ {ij}\\ & = 0\ text {,}\ end {align*}

donde

$\delta_{ij} = \begin{cases} 1 & i = j \\ 0 & i \neq j \end{cases} \nonumber$

es el delta Kronecker.

## Teorema$$8.28$$

Dejar$$H = (A \mid I_m )$$ ser una matriz$$m \times n$$ canónica de comprobación de paridad y dejar$$G = \left( \frac{I_{n-m} }{A} \right)$$ ser la matriz generadora$$n \times (n-m)$$ estándar asociada con$$H\text{.}$$ Let$$C$$ be the code generated by$$G\text{.}$$ Entonces$${\mathbf y}$$ está en$$C$$ si y solo si$$H {\mathbf y} = {\mathbf 0}\text{.}$$ En particular,$$C$$ es un código lineal con matriz de verificación de paridad canónica$$H\text{.}$$

Prueba

Primero supongamos que$${\mathbf y} \in C\text{.}$$ Entonces$$G {\mathbf x} = {\mathbf y}$$ para algunos$${\mathbf x} \in {\mathbb Z}_2^m\text{.}$$ Por Lema 8.27,$$H {\mathbf y} = HG {\mathbf x} = {\mathbf 0}\text{.}$$

Por el contrario, supongamos que$${\mathbf y} = (y_1, \ldots, y_n)^\transpose$$ está en el espacio nulo de$$H\text{.}$$ Necesitamos encontrar una$${\mathbf x}$$ en$${\mathbb Z}_2^{n-m}$$ tal que$$G {\mathbf x}^\transpose = {\mathbf y}\text{.}$$ Dado que debe satisfacerse$$H {\mathbf y} = {\mathbf 0}\text{,}$$ el siguiente conjunto de ecuaciones:

\ begin {alinear*} a_ {11} y_1 + a_ {12} y_2 +\ cdots + a_ {1, n-m} y_ {n-m} + y_ {n-m+1} & = 0\\ a_ {21} y_1 + a_ {22} y_2 +\ cdots + a_ {2, n-m} y_ {n-m} + y_ {n-m+2} & = 0\\ &\ vdots\\ a_ {m1} y_1 + a_ {m2} y_2 +\ cdots + a_ {m, n-m} y_ {n-m} + y_ {n-m+m} & = 0\ text {.} \ end {alinear*}

Equivalentemente,$$y_{n-m+1}, \ldots, y_n$$ están determinados por$$y_1, \ldots, y_{n-m}\text{:}$$

\ begin {alinear*} y_ {n-m+1} & = a_ {11} y_1 + a_ {12} y_2 +\ cdots + a_ {1, n-m} y_ {n-m}\\ y_ {n-m+2} & = a_ {21} y_1 + a_ {22} y_2 +\ cdots + a_ {2, n-m} y_ {n-m}\\ &\ vdots\\ y_ {n} & = a_ {m1} y_1 + a_ {m2} y_2 +\ cdots + a_ {m, n-m} y_ {n-m}\ texto {.} \ end {alinear*}

En consecuencia, podemos dejar$$x_i = y_i$$$$i= 1, \ldots, n - m\text{.}$$

Sería útil si pudiéramos calcular la distancia mínima de un código lineal directamente desde su matriz$$H$$ para determinar las capacidades de detección y corrección de errores del código. Supongamos que

\ begin {alinear*} {\ mathbf e} _1 & = (100\ cdots 00) ^\ transpone\\ {\ mathbf e} _2 & = (010\ cdots 00) ^\ transpone\\ &\ vdots\\ {\ mathbf e} _n & = (000\ cdots 01) ^\ transpose\ end {align*}

son las$$n$$ -tuplas en$${\mathbb Z}_2^n$$ de peso$$1\text{.}$$ Para una matriz$$m \times n$$ binaria$$H\text{,}$$$$H{\mathbf e}_i$$ es exactamente la columna$$i$$ th de la matriz$$H\text{.}$$

## Ejemplo$$8.29$$

Observe que

$\begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix}\text{.} \nonumber$

Anotamos este resultado en la siguiente proposición y dejamos la prueba como ejercicio.

## Proposición$$8.30$$

$${\mathbf e}_i$$Sea la$$n$$ -tupla binaria con a$$1$$ en la coordenada$$i$$ th y$$0$$ 's en otra parte y supongamos que$$H \in {\mathbb M}_{m \times n}({\mathbb Z}_2)\text{.}$$ Entonces$$H{\mathbf e}_i$$ es la$$i$$ th columna de la matriz\ (H\ text { . }\

## Teorema$$8.31$$

Dejar$$H$$ ser una matriz$$m \times n$$ binaria. Entonces el espacio nulo de$$H$$ es un solo código de detección de errores si y solo si ninguna columna de$$H$$ consiste completamente en ceros.

Prueba

Supongamos que$$\Null(H)$$ es un único código de detección de errores. Entonces la distancia mínima del código debe ser al menos$$2\text{.}$$ Dado que el espacio nulo es un código de grupo, es suficiente requerir que el código no contenga palabras de código de menos de peso que no$$2$$ sean la palabra de código cero. Es decir, no$${\mathbf e}_i$$ debe ser una palabra clave para$$i = 1, \ldots, n\text{.}$$ Dado que$$H{\mathbf e}_i$$ es la$$i$$ ésima columna de$$H\text{,}$$ la única manera en que$${\mathbf e}_i$$ podría estar en el espacio nulo de$$H$$ sería si la columna$$i$$ th fueran todos ceros, lo cual es imposible; de ahí que el código debe tener la capacidad para detectar al menos errores individuales.

Por el contrario, supongamos que ninguna columna de$$H$$ es la columna cero. Por Proposición$$8.30$$,$$H{\mathbf e}_i \neq {\mathbf 0}\text{.}$$

## Ejemplo$$8.32$$

Si consideramos las matrices

$H_1 = \begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{pmatrix} \nonumber$

y

$H_2 = \begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{pmatrix}\text{,} \nonumber$

Solución

entonces el espacio nulo de$$H_1$$ es un solo código de detección de errores y el espacio nulo de no$$H_2$$ es.

Incluso podemos hacerlo mejor que el Teorema$$8.31$$. Este teorema nos da condiciones sobre una matriz$$H$$ que nos indican cuando el peso mínimo del código formado por el espacio nulo de$$H$$ es También$$2\text{.}$$ podemos determinar cuándo es la distancia mínima de un código lineal$$3$$ examinando la matriz correspondiente.

## Ejemplo$$8.33$$

Si dejamos

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

y quieren determinar si$$H$$ es o no la matriz canónica de comprobación de paridad para un código de corrección de errores,

Solución

es necesario cerciorarse de que$$\Null(H)$$ no contenga ninguna$$4$$ -tuplas de peso Es$$2\text{.}$$ decir,$$(1100)\text{,}$$$$(1010)\text{,}$$$$(1001)\text{,}$$$$(0110)\text{,}$$$$(0101)\text{,}$$ y no$$(0011)$$ debe estar en$$\Null(H)\text{.}$$ El siguiente teorema establece que efectivamente podemos determinar que el código generado por $$H$$es la corrección de errores al examinar las columnas de$$H\text{.}$$ Aviso en este ejemplo que no sólo no$$H$$ tiene columnas cero, sino que además no hay dos columnas iguales.

## Teorema$$8.34$$

Dejar$$H$$ ser una matriz binaria. El espacio nulo de$$H$$ es un solo código de corrección de errores si y solo si$$H$$ no contiene ninguna columna cero y no hay dos columnas de$$H$$ idénticas.

Prueba

La$$n$$ -tupla$${\mathbf e}_{i} +{\mathbf e}_{j}$$ tiene$$1$$ s en las entradas$$i$$ th y$$j$$ th y 0s en otros lugares, y$$w( {\mathbf e}_{i} +{\mathbf e}_{j}) = 2$$ para$$i \neq j\text{.}$$ Since

${\mathbf 0} = H({\mathbf e}_{i} +{\mathbf e}_{j}) = H{\mathbf e}_{i} + H{\mathbf e}_{j} \nonumber$

solo puede ocurrir si las columnas$$i$$ th y$$j$$ th son idénticas, el espacio nulo de$$H$$ es un solo código de corrección de errores.

Supongamos ahora que tenemos una matriz canónica de comprobación de paridad$$H$$ con tres filas. Entonces podríamos preguntar cuántas columnas más podemos agregar a la matriz y aún así tener un espacio nulo que es un solo código de detección de errores y un solo código de corrección de errores. Dado que cada columna tiene tres entradas, hay$$2^3 = 8$$ posibles columnas distintas. No podemos agregar las columnas

$\begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix}\text{.} \nonumber$

Entonces podemos agregar hasta cuatro columnas y aún así mantener una distancia mínima de$$3\text{.}$$

En general, si$$H$$ es una matriz$$m \times n$$ canónica de verificación de paridad, entonces hay posiciones de$$n-m$$ información en cada palabra clave. Cada columna tiene$$m$$ bits, por lo que hay$$2^m$$ posibles columnas distintas. Es necesario que las columnas$${\mathbf 0}, {\mathbf e}_1, \ldots, {\mathbf e}_m$$ sean excluidas, dejando columnas$$2^m - (1 + m)$$ restantes para información si todavía estamos para mantener la capacidad no sólo de detectar sino también de corregir errores individuales.

This page titled 8.4: Matrices Generadoras y Comprobación de Paridad 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.