19.1: Introducción
- Page ID
- 114337
\( \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}\)Cuando se transmite información, puede quedar confusa en el camino. Los códigos de corrección de errores pueden hacer posible que el destinatario de un mensaje confuso averigüe qué pretendía decir el remitente.
Asunción\(\PageIndex{1}\)
Por definitividad, asumimos que el mensaje a enviar es una cadena (o “palabra”) de bits (\(0\)s y\(1\) s). (La información almacenada en una computadora siempre se convierte en una cadena de este tipo, por lo que esta no es una limitación seria).
Ejemplo\(\PageIndex{1}\)
Quizás la palabra\(0110\) le dice a una fábrica automatizada que cierre las\(3^{\text{rd}}\) válvulas\(2^{\text{nd}}\) y. Si enviamos ese mensaje a través de una red inalámbrica, la interferencia (o algún otro problema) podría cambiar uno de los bits, por lo que la fábrica recibe el mensaje\(0010\). Como resultado, la fábrica cierra solo la\(3^{\text{rd}}\) válvula y la\(2^{\text{nd}}\) deja abierta. Esto podría tener consecuencias desastrosas, por lo que nos gustaría hacer algo para evitar este tipo de problemas.
Ejemplo\(\PageIndex{2}\)
Una solución simple es agregar un bit de verificación al final del mensaje. Para ello, establecemos tres reglas:
- Requerimos que todos los mensajes tengan cierta longitud. (Por ejemplo, digamos que todos los mensajes deben tener exactamente\(5\) bits).
- Requerimos que todos los mensajes tengan un número par de\(1\) s.
- Estamos de acuerdo en que el bit final del mensaje (llamado “bit de comprobación de paridad”) no transmitirá ninguna información, sino que se utilizará únicamente para garantizar que Regla\(2\) sea obedecida. (Así, cada mensaje que enviemos tendrá\(4\) bits de información, más el bit de verificación).
En particular, si deseamos enviar el mensaje\(0110\) (que ya tiene un número par de\(1\) s), entonces agregamos\(0\) al final, y enviamos el mensaje\(01100\). Si, digamos, el\(2^{\text{nd}}\) bit se cambia en la transmisión, entonces la fábrica recibe el mensaje\(00100\), entonces el control informático de la fábrica puede ver que este no puede ser posiblemente el mensaje deseado, porque tiene un número impar de\(1\) s. Así que la fábrica puede devolver un mensaje de error, pidiéndonos que enviemos nuestro instrucciones de nuevo.
Nota
Como ejemplo de la vida real, los escáneres de código de barras utilizados por los cajeros emplean el principio anterior: si el bit de verificación no es correcto, entonces el escáner no emite un pitido, por lo que el cajero sabe que es necesario volver a examinar el artículo.
Ejercicio\(\PageIndex{1}\)
Bajo las reglas del Ejemplo 19.1.2, ¿cuál de las siguientes cadenas se permite enviar como mensaje?
\(00110, 10101, 00000, 11011\).
A veces no es factible tener un mensaje reenviado (por ejemplo, si pasa mucho tiempo en tránsito), por lo que sería mucho mejor tener un sistema que permita al destinatario corregir errores de transmisión, no solo detectarlos.
Ejemplo\(\PageIndex{3}\): (Triple-Repetition Code)
Podríamos estar de acuerdo en enviar cada bit de nuestros\(3\) tiempos de mensaje. Por ejemplo, si queremos enviar el mensaje\(0110\), entonces lo transformaríamos (o “codificaríamos”) como\(000111111000\). Si, digamos, el\(2^{\text{nd}}\) bit se vuelve confuso, entonces la fábrica recibe\(010111111000\), entonces sabe que hubo un problema en la transmisión de los primeros\(3\) bits, porque no todos son iguales. Además, dado que la mayoría de estos bits son\(0\), la fábrica puede averiguar que probablemente pretendíamos decir\(000\), y decodificar correctamente todo el mensaje como\(0110\).
El código de triple repetición funciona, pero es muy ineficiente, porque solo un tercio de los bits que enviamos están transportando información — la mayoría de los bits son bits de comprobación que se agregaron para corregir los posibles errores. Después de desarrollar alguna teoría, veremos algunos códigos que son capaces de corregir cada error de un solo bit, pero usan muchos menos bits de verificación.
Ejercicio\(\PageIndex{2}\)
Dejar\(\mathbb{T}^n\) ser el conjunto de todas las secuencias ternarias de longitud\(n\) (así cada entrada es\(0\),\(1\), o\(2\)). Escribir una relación de recurrencia para\(c_n\), el número de palabras de código de\(\mathbb{T}^n\) que no tienen ceros\(2\) consecutivos. Utilice funciones generadoras para resolver su relación de recurrencia, derivando una fórmula explícita para\(c_n\).