19.2: Códigos de corrección de errores
- Page ID
- 114353
\( \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 poder corregir errores en la transmisión, aceptamos enviar solo cadenas que estén en un determinado conjunto\(\mathcal{C}\) de palabras clave. (Entonces, la información que deseamos enviar deberá ser “codificada” como una de las palabras clave). En nuestros ejemplos anteriores,\(\mathcal{C}\) fue
- el conjunto de todas las palabras de longitud\(5\) que tengan un número par de\(1\) s, o
- el conjunto de palabras de longitud\(12\) que constan de cuatro cadenas de tres bits iguales.
El conjunto\(\mathcal{C}\) se llama código. Elegir el código inteligentemente nos permitirá corregir correctamente los errores de transmisión.
Cuando se recibe una transmisión, el destinatario asumirá que el remitente transmitió la palabra clave que está “más cercana” a la cadena que se recibió. Por ejemplo, si\(\mathcal{C}\) fuera el conjunto de palabras\(5\) -letras en el idioma inglés, y se recibiera la cadena “fruiz”, entonces el destinatario asumiría (presumiblemente correctamente), que el remitente transmitió la palabra “fruta”, porque eso sólo está apagado por una letra. (Así es como normalmente tratamos los errores tipográficos que encontramos.)
Por la palabra de código “más cercana”, nos referimos a la palabra clave a la distancia más pequeña, en el siguiente sentido:
Definición: Distancia Hamming
Supongamos\(x\) y\(y\) son cadenas de dos bits de la misma longitud. La distancia de Hamming de\(x\) a\(y\) (denotada\(d(x, y)\)) es el número de bits en los que difieren.
Ejemplo\(\PageIndex{1}\)
Para mayor claridad, subrayamos los bits en la segunda cadena que difieren del bit correspondiente en la primera cadena:
- \(d(11111, 11101) = 1\)
- \(d(11100, 01001) = 3\)
- \(d(10101, 01010) = 5\)
- \(d(10101, 10101) = 0\)
Nota
Cuando dos bits son “transpuestos” (o “conmutados”), lo que significa que una cadena\(01\) se cambia a\(10\) (o viceversa), esto cuenta como que dos bits son diferentes porque a\(0\) se cambia a a\(1\) y a\(1\) se cambia a a\(0\), aunque se pueda pensar en el switch como sólo una sola operación.
Ejercicio\(\PageIndex{1}\)
Calcular la distancia Hamming entre los siguientes pares de palabras:\(\{110, 011\}\),\(\{000, 010\}\),\(\{\text{brats }, \text{ grass}\}\),\(\{11101, 00111\}\).
Ejercicio\(\PageIndex{2}\)
Encuentra cada uno de los siguientes:
1) una palabra inglesa cuya distancia Hamming de “math” es\(0\);
2) una palabra inglesa cuya distancia Hamming de “math” es\(1\);
3) una palabra inglesa cuya distancia Hamming de “math” es\(2\);
4) una palabra inglesa cuya distancia Hamming de “math” es\(3\).
5) ¿Puedes encontrar más de uno de cada uno?
La distancia Hamming satisface los axiomas de una función “métrica” o “distancia”:
Ejercicio\(\PageIndex{3}\)
Demostrar que la función Hamming satisface cada una de las siguientes propiedades, las cuales definen una métrica.
Dejar\(x\),\(y\), y\(z\) ser palabras de la misma longitud. Entonces:
1)\(d(x, y) ≥ 0\).
2)\(d(x, y) = 0 \Longleftrightarrow x = y\).
3)\(d(x, y) = d(y, x)\).
4)\(d(x, z) ≤ d(x, y) + d(y, z)\).
Nota
La parte (4) del Ejercicio 19.2.3 se llama la desigualdad triangular porque dice que la longitud de un lado de un triángulo es siempre menor que (o igual a) la suma de las longitudes de los otros dos lados.
Definición: Distancia mínima
La distancia mínima de un código\(\mathcal{C}\) (denotado\(d(\mathcal{C})\)) es la distancia Hamming más pequeña entre dos elementos distintos de\(\mathcal{C}\).
Ejemplo\(\PageIndex{2}\)
- \(d (\{10, 010, 011\}) = 1\)(porque\(d(010, 011) = 1\)).
- \(d (\{000, 011, 101, 110\}) = 2\).
- \(d (\{10001, 11111\}) = 3\).
Ejercicio\(\PageIndex{4}\)
¿Cuál es la distancia mínima de cada uno de los siguientes códigos?
1)\(\{\text{tell}, \text{ tale},\text{ sale}, \text{ date}\}\)
2)\(\{\text{mon }, \text{ tue}, \text{ wed}, \text{ thu}, \text{ fri}, \text{ sat}, \text{ sun}\}\)
3)\(\{00000, 01011, 10101, 10110, 10011\}\)
Hacer que la distancia mínima de un código sea\(\mathcal{C}\) grande es la clave para garantizar que pueda detectar (o corregir) errores grandes. Vamos a hacer esta idea muy explícita en nuestros próximos dos resultados.
Teorema\(\PageIndex{1}\)
Un código\(\mathcal{C}\) puede detectar todos los errores posibles que afectan a la mayoría de los\(k\) bits si y solo\(d(C) > k\).
- Prueba
-
Demostraremos lo contrapositivo:
\(d(C) ≤ k \Longleftrightarrow \)existe un error que no se puede detectar y afecta solo\(k\) (o menos) bits.
\((⇐)\)Supongamos que hay una situación en la que:
- se envía una\(x\) palabra clave,
- se recibe\(y\) un mensaje,
- con solo bits\(k\) incorrectos, y
- el receptor no se da cuenta de que hubo errores.
Dado que el receptor no se dio cuenta de que había ningún error, el mensaje que se recibió debe ser una palabra clave. En otras palabras,\(y ∈ C\). Ya que hay\(k\) errores en el mensaje recibido, también lo sabemos\(d(x, y) = k\). Ya que\(x\),\(y ∈ C\), esto implica\(d(C) ≤ k\).
\((⇒)\)Por suposición, existen\(x\),\(y ∈ C\) con\(x \neq y\), pero\(d(x, y) ≤ k\). Ahora, supongamos que\(x\) se envía la palabra de código. Ya que\(d(x, y) ≤ k\), cambiar\(k\) (o menos) bits puede cambiar\(x\) a\(y\), así\(y\) puede ser el mensaje que se recibe, incluso si los errores en la transmisión afectan solo a los\(k\) bits. Ya que\(y ∈ C\), el destinatario no se da cuenta de que se cometió un error, y asume que ese\(y\) era el mensaje pretendido. Por lo que no se detectaron los\(k\) (o menos) errores.
Si bien una distancia mínima de nos\(k\) permite detectar errores que afectan como máximo a los\(k\) bits, no es suficiente para permitirnos corregir todos esos errores. A los efectos de corregir errores, requerimos que la distancia mínima sea el doble de esta grande.
Teorema\(\PageIndex{2}\)
Un código\(\mathcal{C}\) puede corregir todos los errores posibles que afectan a la mayoría de los\(k\) bits si y solo\(d(\mathcal{C}) > 2k\).
- Prueba
-
Demostraremos lo contrapositivo:
\(d(\mathcal{C}) ≤ 2k \Longleftrightarrow \text{ there exists an error that is not properly corrected, and affects only \(2k\)(o menos) bits.}\)
\((⇐)\)Supongamos que hay una situación en la que:
- se envía una\(x\) palabra clave,
- se recibe\(y\) un mensaje,
- con solo bits\(2k\) incorrectos, y
- el receptor decodifica el mensaje incorrectamente, como alguna palabra clave\(z \neq x\).
Debe darse el caso que\(z\) sea la palabra clave más cercana a\(y\) (o, al menos, se empata por ser la más cercana), entonces\(d(z, y) ≤ d(x, y) = k\). Luego, usando el Ejercicio 19.2.3, tenemos
\[d(x, z) ≤ d(x, y) + d(y, z) = d(x, y) + d(z, y) ≤ k + k = 2k.\]
Entonces\(d(C) ≤ 2k\) (porque\(x\),\(z ∈ C\)).
\((⇒)\)Por suposición, existen\(x\),\(y ∈ C\) con\(x \neq y\), pero\(d(x, y) ≤ 2k\). Vamos\(r = \lceil \dfrac{d(x, y)}{2e} \rceil ≤ \lceil \dfrac{2k}{2e} \rceil = k\). (En otras palabras,\(r\) se obtiene redondeando\(\dfrac{d(x, y)}{2}\) hasta el entero más cercano.)
Ahora supongamos que\(x\) se envía la palabra de código. Ya que\(d(x, y) ≤ 2k\), el mensaje\(y\) podría ser recibido, con no más que bits\(2k\) incorrectos. Construir\(z\) a partir de\(x\) cambiando solo\(r\) de los\(d(x, y)\) bits que son incorrectos en\(y\), entonces
\[d(x, z) = r \text{ and } d(z, y) = d(x, y) − r.\]
Por la definición de\(r\), tenemos\(r ≤ d(x, y) ≤ 2r\), entonces
\[d(z, y) = d(x, y) − r ≤ 2r − r = r ≤ d(x, y).\]
Por lo tanto\(z\) es al menos lo más cerca que\(x\) está, por lo que el destinatario no tiene forma de saber que\(x\) es el mensaje que se envió.\(y\) Por lo que no fue posible corregir los\(2k\) (o menos) errores.
Ejercicio\(\PageIndex{5}\)
1) Supongamos que un código\(C\) tiene una distancia mínima de\(7\).
a) ¿Cuántos errores puede detectar?
b) ¿Cuántos errores puede corregir?
2) Supongamos que un código\(C\) tiene una distancia mínima de\(6\).
a) ¿Cuántos errores puede detectar?
b) ¿Cuántos errores puede corregir?
Ejercicio\(\PageIndex{6}\)
Let\(\mathbb{B}^n\) representar el conjunto de cadenas binarias de longitud\(n\). Demostrar que un código de\(\mathbb{B}^{10}\) eso tiene más que\(2\) palabras, no puede corregir\(3\) errores. Hipótesis de una generalización de este resultado a códigos\(\mathbb{B}^n\) con más que\(2\) palabras.