De detección de errores y códigos correctores de errores

De detección de errores y códigos correctores de errores

Texto de Referencia: Sección 4.6, p. 265

En este conjunto de ejercicios, un método para detectar y corregir errores en la transmisión de

mensajes codificados se construye. Resultará que los espacios vectoriales abstractos y los conceptos de

espacio nulo, rango y dimensión se necesitan para esta construcción.

Cuando se transmite un mensaje, que tiene el potencial para ser revueltos por el ruido. Esto es cierto

de mensajes de voz, y también es cierto de los mensajes digitales que se envían desde y hacia computadoras.

Ahora, incluso el sonido y el vídeo se está transmitiendo de esta manera. Un mensaje digital es una secuencia

de 0 y de 1 de que codifica un mensaje dado. Se añadirán más datos para un mensaje binario dado

que le ayudará a detectar si un error se ha hecho en la transmisión del mensaje; añadiendo tales

de datos se denomina un código de detección de errores. Más datos también se pueden añadir al mensaje original, de modo

que errores en la transmisión se pueden detectar, y también para averiguar cuál es el mensaje original

fue a partir del mensaje posiblemente corrupto que fue recibido. Este tipo de código es un error-corrección

código.

Un tipo común de código de detección de errores se llama una comprobación de paridad. Por ejemplo, considere el mensaje

1101. Añadir un 0 o 1 hasta el final de este mensaje para que el mensaje resultante tiene un incluso

número de 1 de. El mensaje 1.101 por lo tanto se codifica como 11011. Si el mensaje original eran

1001, sería codificado como 10 010, ya que el mensaje original ya contaba con un número par de

1 de. Consideremos ahora la recepción del mensaje 10101. Dado que el número de 1 de en este mensaje es impar,

un error se ha hecho en la transmisión. Sin embargo, no se sabe cuántos errores ocurridos en

dígito (s) de transporte o que se efectuaron. Así, un esquema de comprobación de paridad detecta errores, pero hace

No ubicarlos para su corrección.

Ejemplo: El Servicio Postal de los Estados Unidos utiliza un código de expresar el código postal en una carta como

serie de barras largas y cortas. Los dígitos están codificados de la siguiente manera:

Los códigos postales se codifican y se colocan en el sobre. Una larga barra comienza y termina cada código. Un

comprobación de paridad dígito adicional está codificada. Este dígito, cuando se añade a los que están en el código postal de cinco dígitos,

produce un número que es un múltiplo de diez. Si los seis dígitos codificados no se suman a un múltiplo

de diez, a continuación, debe haber ocurrido un error en la transmisión. Así, el 29.733 códigos postales y 28.209

hacerse

Desde el 2 + 9 + 7 + 3 + 3 = 24, y 24 + 6 = 30, un 6 esta en el código 29733; asimismo, un 9

fue introducido en el código 28209, ya que 8 + 2 + 2 + 0 + 9 + 9 = 30.

Con el fin de discutir los códigos de corrección de errores, la atención se limita a secuencias digitales: mensajes

de 0 de 1 y de. El conjunto Z2 que es el conjunto {0, 1}. Será primero ser útil para realizar operaciones aritméticas en Z2.

La suma y la multiplicación por 0 y 1 se dan en las siguientes tablas:

Uno puede comprobar que estas operaciones tienen las propiedades familiares de la suma y la multiplicación de

numeros reales. Una particularidad es el hecho de que desde el 1 + 1 = 0, 1 = -1. Es decir, 1 es su propio aditivo

inversas, y por lo tanto la sustracción es exactamente la misma que la adición en Z2.

Los mensajes ahora pueden ser expresados como vectores columna de elementos de Z2. Los mensajes 1001 y

1101 se expresaría como

Supongamos que cada mensaje es n dígitos de longitud; el conjunto de todos los posibles mensajes de longitud n dígitos Zn

2.

En otras palabras, Zn

2 es el conjunto de todos los vectores con n elementos tomados de Z2. El conjunto Z4

2 contiene el

tras dieciséis vectores:

Estos vectores se pueden añadir al igual que en Rn; estos vectores también se pueden multiplicar por escalares tomadas

de Z2.

Ejemplos:

De hecho, si Z2 son los escalares, y las operaciones de adición y multiplicación escalar de vectores como se indica

en los últimos ejemplos se utilizan, a continuación, Zn

2 es un espacio vectorial: dejar claro que Z2 son los escalares, Zn

2

se llama un espacio vectorial sobre Z2. El material en las Secciones 4.2 a 4.6 en matrices de números reales

también se aplica a matrices cuyas entradas se toman de Z2, excepto que toda la aritmética se realiza en Z2.

Ejemplo: Para encontrar una base para el espacio de la columna, una base para el espacio nulo, y el rango de

primera fila reducir A usando aritmética Z2 (recuerde que 1 + 1 = 0):

Una base para Col A es las columnas pivote de A:

Así rango A = 2. Para encontrar una base para Nul A, resolver Ax = 0 y obtener las ecuaciones

x1 = -1x3 - 1x4 y x2 = -1x3 - 1x4.

Desde -1 = 1,

x1 = 1x3 + 1x4 y x2 = 1x3 + 1x4,

por lo que una base para Nul A sería

1

1

1

0

,

1

1

0

1

Observe que estos resultados difieren de los que se calcula si A fueron tratados como una matriz

de números reales; usted puede confirmar que en ese rango caso A = 3.

Éstos son todos los miembros de Nul A:

...