19.4: Uso de la matriz de comprobación de paridad para la decodificación
- Page ID
- 114346
\( \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}\)Notación
Un código lineal binario es de tipo\((n, k)\) (o decimos que\(\mathcal{C}\) es un \((n, k)\)código) si su matriz generadora\(G = \left[ \begin{array}{ll} I_k \\ A \end{array} \right]\) es una\(n \times k\) matriz. En otras palabras,\(G\) codifica mensajes de longitud\(k\) como palabras de código de longitud\(n\), lo que significa que el número de bits de verificación es\(n−k\). Usualmente usamos\(r\) para denotar el número de bits de verificación, entonces\(r = n − k\). Entonces\(A\) es una\(r \times k\) matriz.
Ejercicio\(\PageIndex{1}\)
¿Cuántas palabras clave hay en un código lineal binario de tipo\((n, k)\)?
Definición: Matriz de comprobación de paridad
Si\(G = \left[ \begin{array}{ll} I_k \\ A \end{array} \right]\) es la matriz generadora de un código lineal binario\(\mathcal{C}\), y\(A\) es una\(r \times k\) matriz (así\(\mathcal{C}\) es de tipo\((k + r, k)\)), entonces la matriz de comprobación de paridad de\(\mathcal{C}\) es
\[P = [A \;\; I_r].\]
Ejemplo\(\PageIndex{1}\)
1) Para el código\(\mathcal{C}\) del Ejemplo 19.3.2, la matriz\(A\) es\(2 \times 3\), así\(r = 2\). Por lo tanto, la matriz de comprobación de paridad de\(\mathcal{C}\) es
\(P = [A \;\; I_r] = [A\;\; I_2] = \left[ \begin{array}{ll} 1\;\;0\;\;1\;\;1\;\;0 \\ 0\;\;1\;\;1\;\;0\;\;1 \end{array} \right]\).
2) Para un solo check-bit de paridad, como en el Ejemplo 19.3.1, tenemos\(A = [1\;\; 1\;\; 1]\). Esto es una\(1 \times 3\) matriz, entonces\(r = 1\). Por lo tanto, la matriz de comprobación de paridad del código es
\(P = [A\;\;I_r] = [A\;\; I_1] = [1\;\; 1\;\; 1\;\; 1]\)
(ya que\(I_1 = [1]\)).
Ejercicio\(\PageIndex{2}\)
Supongamos que la matriz generadora del código lineal binario\(\mathcal{C}\) es
\(\left[ \begin{array}{ll} 1\;\;0\;\;0\;\;0 \\ 0\;\;1\;\;0\;\;0 \\ 0\;\;0\;\;1\;\;0 \\ 0\;\;0\;\;0\;\;1 \\ 1\;\;0\;\;1\;\;1 \\ 1\;\;0\;\;0\;\;1 \\ 0\;\;1\;\;1\;\;1 \end{array} \right]\)
¿Cuál es la matriz de comprobación de paridad de este código?
La matriz de verificación de paridad se puede usar para verificar si un mensaje que recibimos es una palabra de código válida:
Proposición\(\PageIndex{1}\)
Un vector de columna x es una palabra clave si y solo si\(Px = 0\).
- Prueba
-
\((⇒)\)Ya que\(x\) es una palabra clave, tenemos\(x = Gm\) para algún mensaje (\(k\)-bit)\(m\). Esto significa que
\[x = Gm = \left[ \begin{array}{ll} I_k \\ A \end{array} \right] m = \left[ \begin{array}{ll} m \\ Am \end{array} \right]\]
Entonces
\[Px = [A \;\; I_r] \left[ \begin{array}{ll} m \\ Am \end{array} \right] = [Am + Am] = [2Am] ≡ 0 (\text{mod } 2). \]
\((⇐)\)Supongamos\(Px = 0\). Escribir\(x = \left[ \begin{array}{ll} m \\ y \end{array} \right]\), donde
- \(m\)es las primeras\(k\) filas de\(x\), y
- \(y\)es el resto de\(r = n − k\) filas de\(x\).
Entonces
\[0 = Px = [A \;\;I_r] \left[ \begin{array}{ll} m \\ y \end{array} \right] = [Am + y]. \]
Esto significa\(y = −Am = Am (\text{mod } 2)\), entonces
\[x = \left[ \begin{array}{ll} m \\ y \end{array} \right] = \left[ \begin{array}{ll} m \\ Am \end{array} \right] = \left[ \begin{array}{ll} I-k \\ A \end{array} \right] m = Gm \]
así\(x ∈ \mathcal{C}\).
Ejemplo\(\PageIndex{3}\)
Aquí hay una ilustración simple de la Proposición 19.4.1. Para el código en el que se requiere que cada palabra clave tenga un número par de\(1\) s, el Ejemplo 19.4.1 (2) nos dice que la matriz de comprobación de paridad es\(P = [1\;\; 1\;\; 1\;\; 1]\). Por lo tanto, para cualquier cadena\(4\) -bit\(x_1x_2x_3x_4\), tenemos
\(Px = [1\;\;1\;\;1\;\;1] \left[ \begin{array}{ll} x_1 \\ x_2 \\ x_3 \\ x_4 \end{array} \right] = [x_1 + x_2 + x_3 + x_4]. \)
Esto es\(0 (\text{mod } 2)\) si y sólo si hay un número par de\(1\) s en\(x\), que es lo que significa decir que\(x\) es una palabra clave.
Ejemplo\(\PageIndex{4}\)
Utilice la matriz de comprobación de paridad para determinar si cada una de estas palabras está en el código\(\mathcal{C}\) del Ejemplo 19.3.2:
\(11111, 10101, 00000, 11010.\)
Solución
Del Ejemplo 19.4.1 (1), sabemos que la matriz de comprobación de paridad de este código es
\(P = \left[ \begin{array}{ll} 1\;\;0\;\;1\;\;1\;\;0 \\ 0\;\;1\;\;1\;\;0\;\;1 \end{array} \right].\)
Contamos con:
- \(P = \left[ \begin{array}{ll} 1\\1\\1\\1\\1 \end{array} \right] = \left[ \begin{array}{ll} 1 · 1 + 0 · 1 + 1 · 1 + 1 · 1 + 0 · 1 \\ 0 · 1 + 1 · 1 + 1 · 1 + 0 · 1 + 1 · 1 \end{array} \right] = \left[ \begin{array}{ll} 1\\1 \end{array} \right] \neq \left[ \begin{array}{ll} 0\\0 \end{array} \right] \), entonces no\(11111\) es una palabra clave.
- \(P = \left[ \begin{array}{ll} 1\\0\\1\\0\\1 \end{array} \right] = \left[ \begin{array}{ll} 1 · 1 + 0 · 0 + 1 · 1 + 1 · 0 + 0 · 1 \\ 0 · 1 + 1 · 0 + 1 · 1 + 0 · 0 + 1 · 1 \end{array} \right] = \left[ \begin{array}{ll} 0\\0 \end{array} \right] \), así\(10101\) es una palabra clave.
- \(P = \left[ \begin{array}{ll} 0\\0\\0\\0\\0 \end{array} \right] = \left[ \begin{array}{ll} 1 · 0 + 0 · 0 + 1 · 0 + 1 · 0 + 0 · 0 \\ 0 · 0 + 1 · 0 + 1 · 0 + 0 · 0 + 1 · 0 \end{array} \right] = \left[ \begin{array}{ll} 0\\0 \end{array} \right] \), así\(00000\) es una palabra clave.
- \(P = \left[ \begin{array}{ll} 1\\1\\0\\1\\0 \end{array} \right] = \left[ \begin{array}{ll} 1 · 1 + 0 · 1 + 1 · 0 + 1 · 1 + 0 · 0 \\ 0 · 1 + 1 · 1 + 1 · 0 + 0 · 1 + 1 · 0 \end{array} \right] = \left[ \begin{array}{ll} 0\\1 \end{array} \right] \neq \left[ \begin{array}{ll} 0\\0 \end{array} \right] \), entonces no\(11010\) es una palabra clave.
(Estas respuestas se pueden verificar mirando la lista los elementos de\ mathcal {C} en la solución del Ejemplo 19.3.2.)
Es evidente a partir de la matriz de comprobación de paridad si un código corrige cada error de un solo bit:
Teorema\(\PageIndex{1}\)
Un código lineal binario\(\mathcal{C}\) puede corregir cada error de un solo bit si y solo si las columnas de su matriz de verificación de paridad son todas distintas y distintas de cero.
- Prueba
-
Supongamos que\(x\) se transmite una palabra clave, pero el bit i-ésimo se cambia, por lo que\(y\) se recibe una cadena diferente. Que ei sea la cadena que es todo\(0\) s, excepto que el\(i^{\text{th}}\) bit es\(1\), entonces\(y = x+e_i\). Entonces
\[P_y = P(x + e_i) = P_x + Pe_i = 0 + Pe_i = P_ei\]
es la\(i^{\text{th}}\) columna de\(P\).
Por lo tanto, si todas las columnas de\(P\) son distintas de cero, entonces\(P_y\) es distinta de cero, por lo que el receptor puede detectar que hubo un error. Si, además, todas las columnas de\(P\) son distintas, entonces\(P_y\) es igual a la\(i^{\text{th}}\) columna de\(P\), y no igual a ninguna otra columna, por lo que el receptor puede concluir que el error está en el bit i-ésimo. Al cambiar este bit se corrige el error.
Por el contrario, si o bien la\(i^{\text{th}}\) columna de\(P\) es cero, o la\(i^{\text{th}}\) columna es igual a la\(j^{\text{th}}\) columna, entonces cualquiera\(Pe_i = 0\) o\(Pe_i = Pe_j\). Por lo tanto, cuando\(00 . . . 0\) se envía la palabra clave, y un error cambia el\(i^{\text{th}}\) bit, dando como resultado que\(e_i\) se reciba el mensaje, ya sea\(Pe_i = 0\), por lo que el receptor no detecta el error (y erróneamente concluye que el mensaje\(e_i\) es lo que se envió), o no puede decir si el el error está en el\(i^{\text{th}}\) bit (y\(0\) se envió el mensaje) o el error está en el\(j^{\text{th}}\) bit (y\(e_i + e_j\) se envió el mensaje). En cualquier caso, se trata de un error de un solo bit que no se puede corregir.
Ejercicio\(\PageIndex{3}\)
La matriz de comprobación de paridad del código lineal binario\(\mathcal{C}\) es
\(P = \left[ \begin{array}{ll} 0\;\;1\;\;1\;\;1\;\;0 \\ 1\;\;0\;\;1\;\;0\;\;1 \end{array} \right].\)
¿Puede\(\mathcal{C}\) corregir todos los errores de un solo bit?
La prueba del Teorema 19.4.1 muestra cómo corregir cualquier error de un solo bit (cuando sea posible):
Método General.
Supongamos que la palabra\(y\) ha sido recibida. Calcular\(P_y\).
- Si\(P_y = 0\), entonces\(y\) es una palabra clave. Supongamos que no hubo errores, así\(y\) es la palabra clave que se envió.
- Ahora supongamos\(P_y \neq 0\).
- Si\(P_y\) es igual a la\(i^{\text{th}}\) columna de\(P\), entonces vamos\(x = y+e_i\). (En otras palabras, crear\(x\) cambiando el\(i^{\text{th}}\) bit de\(y\) de\(0\) a\(1\) o viceversa.) Entonces\(x\) es una palabra clave. Supongamos que es la palabra clave que se envió.
- Si no\(P_y\) es igual a ninguna de las columnas de\(P\), entonces al menos dos de los bits de\(y\) están equivocados. No intentes corregir el error.
Ejemplo\(\PageIndex{5}\)
Supongamos que la matriz de comprobación de paridad de un código lineal binario es
\(P = \left[ \begin{array}{ll} 1\;\;1\;\;1\;\;1\;\;0\;0 \\ 1\;\;0\;\;1\;\;0\;\;1\;0 \\ 1\;\;1\;\;0\;\;0\;\;0\;\;1 \end{array} \right].\)
Decodificar cada una de las siguientes palabras recibidas:
\(111000, 101001, 001101.\)
Solución
Dejar\(P\) ser la matriz de comprobación de paridad dada. Entonces:
\(P = \left[ \begin{array}{ll} 1\\1\\1\\0\\0\\0 \end{array} \right] = \left[ \begin{array}{ll} 1\\0\\0 \end{array} \right]\). Esta es la\(4^{\text{th}}\) columna de\(P\), por lo que cambiar el\(4^{\text{th}}\) bit corrige el error. Esto quiere decir que la palabra recibida\(111000\) decodifica como\(111\underline{1}00\).
\(P = \left[ \begin{array}{ll} 1\\0\\1\\0\\0\\1 \end{array} \right] = \left[ \begin{array}{ll} 0\\0\\0 \end{array} \right]\). Esto es\(0\), por lo que no hay error. Esto quiere decir que la palabra recibida\(101001\) decodifica como\(101001\).
\(P = \left[ \begin{array}{ll} 0\\0\\1\\1\\0\\1 \end{array} \right] = \left[ \begin{array}{ll} 0\\1\\1 \end{array} \right]\). Esta no es ninguna de las columnas de\(P\), por lo que hay al menos dos errores. Por lo tanto, no podemos decodificar la palabra recibida\(001101\).
Ejercicio\(\PageIndex{4}\)
1) La matriz de comprobación de paridad de un cierto código lineal binario es
\(P = \left[ \begin{array}{ll} 1\;\;0\;\;1\;\;0\;\;1\;\;0\;\;0\;\;0 \\ 1\;\;0\;\;0\;\;1\;\;0\;\;1\;\;0\;\;0 \\ 0\;\;1\;\;0\;\;1\;\;0\;\;0\;\;1\;\;0 \\ 0\;\;1\;\;1\;\;1\;\;0\;\;0\;\;0\;\;1 \end{array} \right].\)
a) Decodificar cada una de las siguientes palabras recibidas:\(10001111\),\(11110000\),\(01111101\).
(b) Encontrar la matriz generadora del código.
2) La matriz de comprobación de paridad de un cierto código lineal binario es
\(P = \left[ \begin{array}{ll} 1\;\;1\;\;0\;\;1\;\;0\;0 \\ 0\;\;1\;\;1\;\;0\;\;1\;0 \\ 1\;\;0\;\;1\;\;0\;\;0\;\;1 \end{array} \right].\)
(a) ¿Puede el código corregir todos los errores de un solo bit?
b) Decodificar cada una de las siguientes palabras recibidas:\(001001\),\(110011\),\(000110\)
Ejemplo\(\PageIndex{6}\)
Let
\(P = \left[ \begin{array}{ll} 1\;\; 1\;\; 1\;\; 1\;\; 1\;\; 1\;\; 1\;\; 0\;\; 0\;\; 0\;\; 0 \\ 1\;\; 1\;\; 1\;\; 1\;\; 0\;\; 0\;\; 0\;\; 1 \;\;1\;\; 1\;\; 0 \\ 1\;\; 1 \;\;0\;\; 0 \;\;1 \;\;1 \;\;0 \;\;1\;\;1\;\; 0\;\; 1\\ 1 \;\;0 \;\;1 \;\;0\;\; 1\;\; 0 \;\;1 \;\;1\;\; 0\;\; 1\;\; 1 \end{array} \right].\)
Esta es una\(4 \times 11\) matriz cuyas columnas enumeran todos los vectores binarios de longitud\(4\) que tienen al menos dos\(1\) s. La matriz de\(4 \times 15\) verificación de paridad correspondiente\(P = [A\;\;I_4]\) enumera todos los vectores binarios\(2^4 − 1 = 15\) distintos de cero de longitud\(4\) (sin repetición), por lo que el lineal binario resultante puede corregir todos los errores de un solo bit.
La matriz generadora correspondiente\(G = \left[ \begin{array}{ll} I_{11} \\ A \end{array} \right].\) es una\(15 \times 11\) matriz, por lo que toma un mensaje\(11\) -bit, y agrega solo bits de\(15 − 11 = 4\) verificación. Esto es mucho más eficiente que el código de triplerepetición del Ejemplo 19.1.3, que tendría que agregar bits de\(22\) verificación para detectar cada error de un solo bit en un mensaje de\(11\) -bit.
Nota
Generalizando Ejemplo 19.4.6, un código lineal binario se denomina código Hamming si las columnas de su matriz de comprobación de paridad\(P = [A\;\; I_r]\) son una lista de todos los vectores binarios\(2^r − 1\) distintos de cero de longitud\(r\) (en algún orden, y sin repetición). Cada código Hamming puede corregir todos los errores de un solo bit. Debido a su alta eficiencia, los códigos de Hamming se utilizan a menudo en aplicaciones del mundo real. Pero solo corrigen errores de un solo bit, por lo que otros códigos lineales binarios (que no discutiremos) necesitan ser utilizados en situaciones en las que es probable que más de un bit esté equivocado.
Ejercicio\(\PageIndex{5}\)
1) Explicar cómo hacer un código lineal binario de tipo\((29, 24)\) que corrija todos los errores de un solo bit.
2) Explique por qué es imposible encontrar un código lineal binario de tipo\((29, 25)\) que corrija todos los errores de un solo bit.
3) Para cada uno\(k ≤ 20\), encuentre el menor número posible\(r\) de bits de verificación en un código lineal binario que le permitirá enviar mensajes de\(k\) bits y corregir todos los errores de un solo bit. (Es decir, para cada uno\(k\), queremos un código de tipo\((n, k)\) que corrija todos los errores de un solo bit, y\(r = n − k\) queremos que sea lo más pequeño posible).
4) ¿Cuál es el menor número posible\(r\) de bits de verificación en un código lineal binario que le permitirá enviar mensajes de\(100\) bits y corregir todos los errores de un solo bit?