8.10: Salvia

Última actualización
Guardar como PDF

Page ID: 111127

\( \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}}\)

Sage tiene un conjunto completo de códigos lineales y una variedad de métodos que pueden usarse para investigarlos.

Construcción de códigos lineales

El objeto codes se puede utilizar para obtener una lista concisa de los códigos implementados disponibles. Códigos de tipo. y presiona la tecla Tab y la mayoría de las interfaces a Sage te darán una lista. Luego puede usar un signo de interrogación al final de un nombre de método para conocer los diversos parámetros.

Utilizaremos el clásico\((7,4)\) código binario de Hamming como ilustración. “Binario” significa que tenemos vectores con solo 0's y 1's, the\(7\) es la longitud y significa que los vectores tienen\(7\) coordenadas, y el\(4\) es la dimensión, lo que significa que este código tiene\(2^4=16\) vectores que comprenden el código. La documentación supone que sabemos algunas cosas de más adelante en el curso. Usamos GF (2) para especificar que nuestro código es binario, esto tendrá más sentido al final del curso. Un segundo parámetro es r y podemos ver a partir de las fórmulas en la documenación que establecer r=3 dará longitud\(7\text{.}\)

Propiedades de los Códigos Lineales

Podemos examinar el código Hamming que acabamos de construir. Primero la dimensión.

El código es lo suficientemente pequeño como para que podamos enumerar todas las palabras clave.

La distancia mínima es quizás una de las propiedades más importantes. Los códigos Hamming siempre tienen distancia mínima\(d=3\text{,}\) por lo que siempre son únicos correctores de errores.

Sabemos que la matriz de comprobación de paridad y la matriz generadora son útiles para la construcción, descripción y análisis de códigos lineales. Los nombres del método Sage son solo un poco crípticos. Sage cuenta con extensas rutinas para analizar matrices con elementos de diferentes campos, por lo que realizamos gran parte del análisis posterior de estas matrices dentro de Sage.

La matriz generadora aquí en el texto tiene columnas que son palabras de código, y las combinaciones lineales de las columnas (el espacio de columna de la matriz) son palabras de código. En Sage la matriz generadora tiene filas que son palabras de código y el espacio de filas de la matriz es el código. Entonces aquí hay otro lugar donde necesitamos traducir mentalmente entre una elección hecha en el texto y una elección hecha por los desarrolladores de Sage.

Aquí una prueba parcial de que estas dos matrices son correctas, ejerciendo Lemma\(8.27\). Observe que necesitamos usar la transposición de la matriz generadora, por las razones descritas anteriormente.

Tenga en cuenta que la comprobación de paridad puede no ser canónica y la matriz generadora puede no ser estándar. Sage puede producir una matriz generadora que tiene un conjunto de columnas que forma una matriz de identidad, aunque no se garantiza que estas columnas sean las primeras columnas. (Columnas, no filas.) Se dice que dicha matriz es sistemática, y el método Sage es .systematic_generator_matrix ().

Decodificación con un código lineal

Podemos decodificar los mensajes recibidos que se originan a partir de un código lineal. Supongamos que recibimos el vector\(7\) binario de longitud r.

Podemos reconocer que se han producido uno o más errores, ya que r no está en el código, ya que el siguiente cálculo no arroja el vector cero.

Un código lineal tiene un método.decode. Puede elegir entre varios algoritmos diferentes, mientras que los códigos de Hamming tienen su propio algoritmo personalizado. El algoritmo por defecto es la decodificación de síndrome.

Entonces, si estamos dispuestos a asumir que solo ocurrió un error (que podríamos, si la probabilidad de que una entrada indivual del vector esté en error es muy baja), entonces vemos que ocurrió un error en la tercera posición.

Recuerda que podría suceder que hubiera más de un solo error. Por ejemplo, supongamos que el mensaje era el mismo que antes y los errores ocurrieron en las ubicaciones tercera, quinta y sexta.

Entonces parece que hemos recibido una palabra clave, por lo que asumimos que no hay errores en absoluto, y decodificamos incorrectamente.