19.5: Códigos de diseños
- Page ID
- 114355
\( \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}}} \)
Un código de corrección de errores se puede construir a partir de cualquier diseño BIBD\((v, k, λ)\) para el cual\(λ = 1\). Es decir, a partir de cada bloque del diseño, crear una cadena binaria de longitud\(v\), colocando a\(1\) en cada una de las posiciones que corresponden a puntos en el diseño, y\(0\) s en todas partes. (Sin embargo, esto no suele tener una matriz generadora, por lo que no es un código lineal binario).
Ejemplo\(\PageIndex{1}\)
Para el BIBD\((7, 3, 1)\) que ha surgido en ejemplos anteriores, con bloques
\(\{1, 2, 3\}, \{1, 4, 5\}, \{1, 6, 7\}, \{2, 4, 6\}, \{2, 5, 7\}, \{3, 4, 7\}, \{3, 5, 6\},\)
el código correspondiente es
\(C = \{1110000, 1001100, 1000011, 0101010, 0100101, 0011001, 0010110\}.\)
Proposición\(\PageIndex{1}\)
Un BIBD se\((v, k, 1)\) puede utilizar para producir un código que pueda corregir hasta\(k − 2\) errores.
- Prueba
-
Dejar\(B\) y\(B'\) ser bloques del diseño, y let\(b\),\(b'\) ser las cadenas binarias correspondientes de longitud\(k\) como se describe al inicio de esta sección. Si los bloques no tienen puntos en común, entonces\(d(b, b') = 2k\). Si los bloques tienen\(1\) entrada en común, entonces
\(d(b, b') = 2(k − 1)\)
(las cadenas difieren en las\(k − 1\) posiciones correspondientes a los puntos que están en\(B\) pero no en\(B'\), y en las\(k − 1\) posiciones correspondientes a los puntos que están en\(B'\) pero no en\(B\)). Ya que\(λ = 1\), los bloques no pueden tener más de un punto en común. Entonces, en cualquier caso,
\(d(b, b') ≥ 2(k − 1).\)
Dado que\(b\) y\(b'\) eran palabras de salida arbitrarias del código (porque\(B\) y\(B'\) eran bloques arbitrarios), esto significa que\(d(C) ≥ 2(k − 1)\). Esto es mayor que\(2(k − 2)\), por lo que el Teorema 19.2.2 nos dice que el código puede corregir cualquier\(k − 2\) error.
Ejercicio\(\PageIndex{1}\)
- Si usa un BIBD para crear un código cuyas palabras tengan longitud\(10\), eso es\(4\) -corrección de errores. ¿Cuántas palabras tendrá tu código?
- ¿Cuántos errores se pueden corregir con un código que proviene de un BIBD\((21, 4, 1)\)?
- Recordemos el\(2\) -\((8, 4, 3)\) diseño dado en el Ejercicio 17.2.1 (2). Es posible demostrar que esto también es un\(3\) -\((8, 4, 1)\) diseño; para los efectos de este problema, se puede suponer que esto es cierto. Si convertimos estos bloques en cadenas binarias para formar palabras de código para un código, ¿cuántos errores puede corregir este código?