Codificación

  • Pere Cruells

  • Germán Sáez

PID_00206068
Ninguna parte de esta publicación, incluido el diseño general y la cubierta, puede ser copiada, reproducida, almacenada o transmitida de ninguna forma, ni por ningún medio, sea éste eléctrico, químico, mecánico, óptico, grabación, fotocopia, o cualquier otro, sin la previa autorización escrita de los titulares del copyright.

1.Introducción a la codificación

1.1.Introducción

A lo largo de la historia, las personas han tenido necesidad de comunicarse, por lo que han intentado transmitir mensajes más allá de las posibilidades que puede dar su voz. En tiempos remotos, las comunicaciones a distancia podían ser a través de luces desde torreones o puestos de vigilancia, con señales de humo, con tambores, con banderas, etc.
1.1.1.Una primera forma de comunicación
Una de las formas de comunicación entre barcos se produce con banderas. Aunque actualmente la comunicación náutica se efectúa por radio, por teléfono o por otro tipo de telecomunicaciones más modernas, se conserva el código de banderas para casos de emergencia, así como para algunas indicaciones especiales. En la tabla siguiente relacionamos el abecedario con cada una de las banderas que se usan en náutica. En general, esta forma de comunicación se usa para algunas indicaciones muy concretas, no para transmitir mensajes de cualquier tipo.
m4e1_rec1.gif
1.1.2.El telégrafo y el código Morse
Estas formas de transmisión de información tienen grandes limitaciones, sobre todo la lentitud en la transmisión y, en algunos casos, limitaciones en la variedad de mensajes enviados. La necesidad de transmitir más información en un tiempo cada vez menor lleva al desarrollo de nuevos métodos para la transmisión de información. La comunicación electrónica se inició en 1834 con el telégrafo, que permitía transmitir información utilizando impulsos eléctricos. Para su uso era necesario utilizar un código que relacionara cada letra del alfabeto con una serie de impulsos eléctricos. Para conseguirlo, se utilizó el conocido código Morse. Samuel Morse (1791-1872) fue el inventor del código que lleva su nombre, y que representa los caracteres mediante puntos y líneas. A cada letra del alfabeto y a cada número entre 0 y 9 se le hace corresponder una serie de puntos y líneas. Éstos se traducen en impulsos eléctricos que producen una señal acústica o luminosa de una cierta duración. El tiempo de duración para un punto es de aproximadamente 1/25 segundos, y el tiempo para una línea es el equivalente en tiempo a tres puntos, es decir, 3/25 segundos. Los espacios entre las letras son de tres puntos, y cinco puntos entre palabras. Así, podríamos afirmar que el código Morse usa cuatro símbolos distintos:

  • punto,

  • línea,

  • espacio entre letras

  • y espacio entre palabras.

Este código nos permite transmitir cualquier texto a través de cable, a través de ondas de radio o, simplemente, con una linterna. El uso de nuevas tecnologías está dejando en desuso la transmisión de información por código Morse y, en consecuencia, el telégrafo.
m4e1_rec2.gif
m4e1_rec3.gif
Alfabeto en código Morse

A

· –

J

· – – –

R

· – ·

B

– · · ·

K

– · –

S

· · ·

C

– · – ·

L

· – · ·

T

–

D

– · ·

M

– –

U

· · –

E

·

N

– ·

V

· · · –

F

· · – ·

Ñ

– – · – –

W

· – –

G

– – ·

O

– – –

X

– · · –

H

· · · ·

P

· – – ·

Y

– · · – –

I

· ·

Q

– – · –

Z

– – · ·
Números en código Morse

1

· – – – –

2

· · – – –

3

· · · – –

4

· · · · –

5

· · · · ·

6

– · · · ·

7

– – · · ·

8

– – – · ·

9

– – – –

0

– – – – –
En la actualidad, la radio, el teléfono, la televisión y otros aparatos de telecomunicación son capaces de transmitir mucha información de forma mucho más rápida que el primitivo telégrafo. Para poder transmitir tal cantidad de información es necesario minimizar el tiempo de transmisión, asegurar la fiabilidad en las transmisiones, detectar errores producidos durante ésta y corregirlos. Precisamente, esta labor entra en el campo de la teoría de la codificación.
1.1.3.Los errores
m4e1_rec5.gif
En un proceso de transmisión de información se dan, de forma inevitable, interferencias y perturbaciones que pueden introducir errores en la información transmitida. Así, el problema que se plantea la teoría de la codificación es intentar detectar estos errores y, a ser posible, corregirlos. Para detectar errores en los mensajes transmitidos se debe incluir información redundante. La inclusión de información redundante es muy usual en el lenguaje hablado, por ejemplo, cuando repetimos una palabra para que el interlocutor la entienda bien, o cuando deletreamos una palabra usando otras: "M de Marruecos, E de Egipto, D de Dinamarca, I de Italia, A de Austria", estamos dando un mensaje muy largo cuando sólo tenemos intención de decir cinco letras: MEDIA. Esto nos permite corregir errores en caso de que, al transmitir la información, nuestro interlocutor perciba por ejemplo: "B de Dinamarca", ya que automáticamente entenderá: "D de Dinamarca". La información que añadimos es redundante, se trata de información que sirve para detectar y corregir posibles errores que se cometan en la transmisión del mensaje.
1.1.4.El almacenamiento
Para transmitir o almacenar información con un ordenador, con un disco magnético, un CD, etc., esta información se codifica con unos y ceros. Estos dos valores son los valores elementales que el ordenador es capaz de reconocer. Los ordenadores, junto con otros tipos de dispositivos periféricos y otras herramientas de almacenamiento de información, usan también tiras de ceros y unos para el tratamiento de la información. A partir de estas tiras de ceros y unos codificaremos los caracteres de nuestro alfabeto. Trabajar con estos dos dígitos nos conduce a hablar de sistema de dígito binario. Cada cero o uno se denomina bit, término derivado de BInary digiT ('dígito binario'). La combinación de ceros y unos permite componer caracteres a partir de unas reglas de codificación. Éstos se representan utilizando una tabla de conversión, lo que equivaldría a un diccionario entre tiras de bits y caracteres. La más común de estas tablas es el código ASCII (American Standard Code for Information Interchange, ASCII se pronuncia "asqui"), código que utiliza la mayoría de los ordenadores personales. Existen otras codificaciones usadas por grandes ordenadores. La codificación ASCII asocia cada carácter con una tira de ceros y unos, usando siempre tiras de ocho dígitos. La tabla siguiente refleja la conversión de los caracteres más usuales:
Decimal
ASCII
Binario
 
Decimal
ASCII
Binario

32

blanco

00100000

 

90

Z

01011010

33

!

00100001

 

91

[

01011011

34

"

00100010

 

92

/

01011100

35

#

00100011

 

93

]

01011101

36

$

00100100

 

94

^

01011110

37

%

00100101

 

95

_

01011111

38

&

00100110

 

96

'

01100000

40

(

00101000

 

97

a

01100001

41

)

00101001

 

98

b

01100010

42

*

00101010

 

99

c

01100011

44

,

00101100

 

100

d

01100100

45

-

00101101

 

101

e

01100101

46

.

00101110

 

102

f

01100110

65

A

01000001

 

103

g

01100111

66

B

01000010

 

104

h

01101000

67

C

01000011

 

105

i

01101001

68

D

01000100

 

106

j

01101010

69

E

01000101

 

107

k

01101011

70

F

01000110

 

108

l

01101100

71

G

01000111

 

109

m

01101101

72

II

01001000

 

110

n

01101110

73

I

01001001

 

111

o

01101111

74

J

01001010

 

112

p

01110000

75

K

01001011

 

113

q

01110001

76

L

01001100

 

114

r

01110010

77

M

01001101

 

115

s

01110011

78

N

01001110

 

116

t

01110100

79

O

01001111

 

117

u

01110101

80

P

01010000

 

118

v

01110110

81

Q

01010001

 

119

w

01110111

82

R

01010010

 

120

x

01111000

83

S

01010011

 

121

y

01111001

84

T

01010100

 

122

z

01111010

85

U

01010101

 

123

{

01111011

86

V

01010110

 

124

|

01111100

87

W

01010111

 

125

}

01111101

88

X

01011000

 

126

~

01111110

89

Y

01011001

 

 

 

 
Debemos destacar que en este módulo nos centraremos en cómo codificar información para su correcta transmisión, sin importarnos la seguridad en la transmisión. Es decir, no nos importa si los mensajes transmitidos pueden ser interceptados de forma que una tercera persona pueda leer nuestros mensajes o, incluso, modificarlos. El tema de la seguridad en la transmisión de información lo estudiaremos en los próximos módulos dedicados a la criptografía.
Sistema de numeración binario y sistema decimal
El sistema de numeración que normalmente utilizamos es el sistema de numeración posicional en base 10. Esto quiere decir, en primer lugar, que usamos diez símbolos diferentes: 0, 1, 2, 3, 4, 5, 6, 7, 8 y 9. La razón por la que usamos diez símbolos parece ser heredada por el número de dedos de nuestras manos. En segundo lugar, este sistema de numeración se llama posicional porque el valor de cada símbolo depende de la posición que ocupe en la representación del número. Así, es diferente el 171 que el 117, a pesar de representar los dos números con los mismos tres símbolos.
La posición nos indica si cada uno de estos símbolos es unidad, decena, centena, etc. Por ejemplo, el 117 es un número que tiene 7 unidades, 1 decena y 1 centena. Así, tendremos la igualdad:
117 = 100 + 10 + 7 = 1 · 102 + 1 · 101 + 7 · 100
El sistema binario es un sistema de numeración posicional pero en base 2. Este sistema sólo usa dos símbolos, el 0 y el 1. Por ejemplo, los primeros números naturales en base 2 son: 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111, 10000, etc.
Por ejemplo, el 87 en base 2 es el 1010111, ya que:
1010111 = 1 · 26 + 0 · 25 + 1 · 24 + 0 · 23 + 1 · 22 + 1 · 21 + 1 · 20 = 64 + 16 + 4 + 2 + 1 = 87
La tabla de caracteres ASCII que se ha dado anteriormente tiene una columna que expresa un número en sistema decimal, el equivalente en sistema binario y el carácter asociado del alfabeto. Observad la conversión y numeración del sistema binario y el sistema decimal.

1.2.Redundancia y dígitos de control

En el momento de transmitir una información, es conveniente añadir cierta redundancia para intentar detectar y corregir los posibles errores producidos durante la transmisión. Para detectar posibles errores se usan los dígitos de control. Hay varios dígitos de control que estamos acostumbrados a dar en la vida cotidiana sin casi darnos cuenta. Veamos algunos ejemplos.
1.2.1.NIF
El número de identificación fiscal (NIF) que tenemos cada uno de nosotros consta de ocho dígitos numéricos y una letra. Esta última letra es la redundancia que se añade a este número para detectar errores al transmitir el NIF a un impreso, formulario, etc. La relación que se establece entre los ocho dígitos numéricos y la letra es la siguiente: se debe realizar la división entera (sin cifras decimales) del número del NIF de ocho cifras entre 23. El resto de esta división será un número comprendido entre 0 y 22. Entonces se asocia una letra a cada una de estas 23 distintas posibilidades siguiendo la tabla:
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

T

R

W

A

G

M

Y

F

P

D

X

B

N

J

Z

S

Q

V

H

L

C

K

E
Calculemos cuál es la letra del NIF asociada al número: 35.059.123
m4e1_rec6.gif
Para ello, dividimos este número entre 23 y obtenemos:
m4e1_1.gif
Es decir, el resto de dividir 35.059.123 entre 23 es 16. Así, a este NIF le corresponde la letra Q.
Para realizar la división entera con una calculadora se debe proceder de la forma siguiente. Se divide 35.059.123 entre 23, con lo que obtendremos 1.524.309,6956521..., la parte entera de este número es el cociente de la división, es decir, 1.524.309. El resto de la división es la diferencia entre el dividendo y el producto del divisor por el cociente. Es decir, 35059123 – 23 × 1524309 = 16.
Con esta redundancia podemos detectar si un dígito de un NIF es incorrecto, pero no permite detectar cuál es. Esta regla para calcular la letra del NIF asigna, evidentemente, la misma letra a muchos números, pero es poco probable que se produzcan errores que no se detecten con esta redundancia. Se puede comprobar que es imposible cambiar un solo número del NIF y mantener la misma letra. Tampoco es posible permutar dos dígitos entre ellos y que se obtenga la misma letra. Justamente estos dos errores son de los más habituales que podemos producir al dar o escribir nuestro NIF. Lo que sí es posible es producir errores en dos dígitos y que no se detecte. Por ejemplo, los dos números 35.994.129 y 35.971.129 difieren en sólo dos dígitos, y su letra para el NIF es A. Por tanto, es posible que se produzca más de un error y no detectarlo. Sin embargo, realizar más de un error es poco probable, y cometer dos errores y conseguir que la letra del NIF se corresponda con este número erróneo es todavía más improbable.
1.2.2.EAN-13
Más frecuente que el uso del NIF es el uso que se hace en la vida cotidiana de los códigos de barras. Actualmente, casi todos los productos del mercado llevan una etiqueta con un código de barras. El código de barras más frecuente es el conocido como EAN-13. El número que encontramos debajo de estos códigos de barras contiene mucha información sobre el producto. Las dos primeras cifras indican el país de origen del producto, los cinco siguientes indican el productor y los cinco siguientes son un número identificativo del producto puesto por el mismo productor. En total, hay doce dígitos que contienen información sobre el producto. Sin embargo, los códigos de barras se componen de trece dígitos. El último dígito es un dígito de control; este último dígito contiene la redundancia suficiente para detectar si al leer el código de barras se ha producido un error. Veamos cómo se calcula. Supongamos que los trece dígitos son:
ABCDEFGHIJKLM
m4e1_rec7.gif
Entonces, el dígito M se calcula de la forma siguiente:
Realizamos la operación:
A + 3B + C + 3D + E + 3F + G + 3H + I + 3J + K + 3L
El dígito de control, M, será el resultado de la diferencia de 10 y la última cifra del número que se haya obtenido de la operación anterior. En caso de que el resultado de esta operación sea un múltiplo de 10, el dígito de control será un 0.
Ejemplo 1
Tenemos un producto con el siguiente código de barras:
2001234567893
Comprobemos que el dígito de control es correcto. Para ello, efectuaremos la operación:
2 + 3 · 0 + 0 + 3 · 1 + 2 + 3 · 3 + 4 + 3 · 5 + 6 + 3 · 7 + 8 + 3 · 9 = 97
La última cifra es un 7. La diferencia entre 10 y 7 es 3, y éste debe ser el dígito de control. Así, este código de barras es correcto.
Ejemplo 2
Calculemos el dígito de control del código siguiente:
028947564562__
Realizamos la operación:
0 + 3 · 2 + 8 + 3 · 9 + 4 + 3 · 7 + 5 + 3 · 6 + 4 + 3 · 5 + 6 + 3 · 2 = 120
Puesto que el resultado obtenido es múltiplo de 10, el dígito de control será un 0. Así, el número completo de este código de barras será 0289475645620.
Las lectoras ópticas para leer códigos de barras no leen los números que hay debajo de las barras en sistema decimal, sino que leen justamente las barras. Estas barras están formadas por columnas negras y blancas. Una barra negra corresponde a un 1, mientras que una barra blanca corresponde a un 0, obteniendo un número en sistema binario. El código EAN-13 empieza siempre con el número en binario 101, que indica inicio de lectura para la lectora óptica, y acaba con el mismo número para indicar final de lectura. En el centro de las barras se sitúa el número 01010, que indica el centro del código. El resto de las barras se corresponden con el número decimal de trece cifras que hemos explicado.
Existen varios tipos de códigos de barras. Como ya hemos indicado, el código que acabamos de explicar corresponde al código EAN-13, y es el código que encontramos en la mayoría de los productos en un supermercado. Otros tipos de códigos de barras son los llamados UPC, Codabar, JAN, etc. Los hay con más o menos dígitos, pero todos contienen un dígito de control que se calcula con una operación similar a la de EAN-13.
Aparte de estos ejemplos de dígitos de control, estamos familiarizados con muchos otros: las cuentas bancarias disponen de dos dígitos de control, los códigos ISBN de los libros tienen un dígito de control parecido al de los códigos de barras, etc.

2.Códigos lineales

2.1.Codificación

Tal como hemos visto en la introducción, existen varias formas de codificar un texto. En este módulo, básicamente estudiaremos una forma de codificación conocida como codificación lineal, en la que, incluyendo la redundancia, podremos detectar algunos errores y, en algunos casos, corregirlos. Para este tipo de codificación usaremos el sistema de numeración de base 2, con lo que sólo usaremos dos símbolos, el 0 y el 1, a los que llamaremos dígitos o bits. Estos dos símbolos formarán el alfabeto del código. De la concatenación de estos dígitos obtendremos las palabras que formarán el código. Cada una de las palabras del código tendrá el mismo número de dígitos, que será la longitud de las palabras del código.
Supongamos que queremos mandar una fotografía en blanco y negro muy simple, sin demasiada resolución. Disponemos de un canal que nos permite la transmisión de ceros y unos. Emisor y receptor convienen el significado de estos dos dígitos como 'Blanco' y 'Negro', así podremos interpretar el color, blanco o negro, de cada píxel de la fotografía para su transmisión. Para una fotografía en blanco y negro, deberemos mandar una cadena de ceros y unos bastante larga, pero para simplificar el ejemplo nos centraremos en tiras de ceros y unos muy cortas. Si queremos transmitir Blanco-Blanco-Negro-Negro-Blanco, mandaremos la secuencia: 00110. Haciéndolo de esta forma, si se produce algún error durante la transmisión será imposible detectarlo. Una posibilidad es incluir redundancia mandando la información dos veces: 00110 00110. Si ahora se produjera un solo error, podríamos detectarlo con la simple comparación de estas dos palabras, pero no podríamos corregirlo. Para corregirlo deberíamos mandar el mensaje una vez más. Si mandamos 00110 00110 00110 y si se produce un solo error durante la transmisión, por ejemplo, el receptor recibe: 00110 10110 00110, podrá detectar el error y corregirlo recuperando el mensaje original 00110. En caso de que se produjeran dos errores en una misma posición, no recuperaríamos el mensaje correcto. Claramente, esto se puede solucionar repitiendo el mensaje más veces. Es de suponer que los canales de transmisión que usamos producen errores con una probabilidad relativamente baja. El inconveniente de esta forma de codificación para detectar y corregir errores es que estamos transmitiendo mucha más información de la necesaria, gastando bastante tiempo y esfuerzo del sistema. Hay métodos de codificación que permiten la detección y corrección de errores sin alargar demasiado el mensaje.
2.1.1.El conjunto
Llamamos Z2n el conjunto de todas las palabras que podemos construir con el alfabeto 0 y 1 que tengan longitud n. Por ejemplo, todas las palabras de longitud 4 que podamos formar con 0 y 1 son:
Z24 = {0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111,
          1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111}
Vamos a identificar cada una de las 26 letras del abecedario (a, b, c, d, ...) con una tira de bits. Veamos cuál es la longitud mínima de las tiras de bits.
Calculemos cuántas palabras tiene cada uno de los conjuntos Z2n. Para ello debemos determinar un valor de n que genere un mínimo de 26 palabras.

  • Para n = 1 tenemos: Z21 = {0,1} únicamente dos palabras.

  • Para n = 2 tenemos: Z22 = {00,01,10,11}, únicamente cuatro palabras.

  • Para n = 3 tenemos: Z23 = {000,001,010,011,100,101,110,111}, que tiene ocho palabras.

  • Para n = 4 tenemos:

    Z24 = {0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001,
              1010, 1011, 1100, 1101, 1110, 1111} que tiene dieciséis palabras.

  • Y para n = 5, el conjunto

    Z25 = {00000,00001,00010,00011,00100,00101,00110,00111,01000,
              01001,01010,01011,01100,01101,01110,01111,10000,10001,10010,
              10011,10100,10101,10110,10111,11000,11001,11010,11011,11100,
             11101,11110,11111}

formado por treinta y dos palabras y, por tanto, podremos asignar el valor de los ventiséis caracteres del alfabeto a cada uno. Tendremos seis palabras sin significado.
Observad que el número de palabras de cada conjunto es 21, 22, 23, 24 y 25 respectivamente. En general, el conjunto Z2n tendrá 2n palabras. Así, si necesitamos un código para D caracteres o significados, necesitaremos que el número de dígitos mínimo de las palabras que usamos cumpla 2n ≥ D. Esto equivale a En este ejemplo podríamos haber resuelto directamente esta inecuación: y, por tanto, un número entero que cumple esta condición es n = 5.
Los logaritmos fueron introducidos a principios del siglo XVII por John Neper con el fin de facilitar operaciones de cálculo.
m3e2_rec2.gif
En esta época, los cálculos debían realizarse manualmente. Sumar es mucho más simple que multiplicar y, gracias a una de las propiedades básicas de los logaritmos, se convierte un producto en una suma utilizando tablas de logaritmos.
Un logaritmo se define de la siguiente forma: el logab (lo leeremos como "logaritmo en base a de b") es un número x tal que ax = b. En el caso de que la base del logaritmo no se especifique, supondremos que se trata de un logaritmo en base 10, es decir a = 10, y en el caso de que la base sea el número a = 2,718281828459..., lo llamaremos logaritmo neperiano (o natural) y lo denotaremos por "ln" en lugar de "log". El número 2,718281828459... se denomina número e; se trata de un número que, al igual que el número π, tiene una gran transcendencia en matemáticas.
Algunos ejemplos de logaritmo en base 10 son:

  • log 1 = 0, ya que 100 = 1

  • log 10 = 1, ya que 101 = 10

  • log 100 = 2, ya que 102 = 100

  • ln e = 1, ya que e1 = 1 e1 = e

  • loga (x · y) = logax + logay

  • logaxk = k · logax

y en base al número e:
Algunas propiedades básicas de la función logaritmo son las siguientes:
Ejercicio 1
Realizad los siguientes cálculos:
a) log 1013
b) ln e3
c) ln 1
Ejercicio 2
Resolved las siguientes ecuaciones:
a) 3x = 5
b) ln x2 = 4
c) 2x = 4x+1
2.1.2.Distancia de Hamming
Al formar palabras con nuestro alfabeto habitual (a, b, c, d, e, f, ...) no damos significado a todas las palabras posibles que se puedan formar con todas las letras; por ejemplo, "slleurc", "zeas", "segap", "cairrub", son palabras formadas con letras de nuestro abecedario que no tienen ningún significado. De igual forma, dentro del diccionario de palabras formadas con 0 y 1 de longitud n no tenemos porqué dar significado a cada una. Podemos escoger algunas y despreciar otras. Justamente este hecho es el que nos permitirá corregir errores. En lenguaje habitual, cuando en un texto leemos la palabra "multimwdia", consideramos que es un error al no encontrarse esta palabra en el diccionario. Para corregirla, sustituimos automáticamente por la palabra con significado más cercana, o parecida, a ésta. El significado de "más cercana" es fácil de entender en este caso: buscamos, entre todas las palabras de nuestro diccionario, aquella que tiene más letras en común con la palabra "multimwdia". La palabra "multimedia" se diferencia de "multimwdia" en sólo una letra. Éste es el fundamento que usan los correctores ortográficos de los procesadores de texto al señalar palabras que no se encuentran en su diccionario y al ofrecer palabras cercanas como posibles palabras correctas.
Para poder hablar sobre la cercanía entre palabras de Z2n, definiremos la "distancia entre dos palabras", conocida con el nombre de distancia de Hamming, como el número de dígitos en que se diferencian. Así, la distancia entre las palabras 1101 y 0101 será 1, y la distancia entre las palabras 1010 y 0111 será 3.
m4e2_rec1.gif
Un código estará formado por unas cuantas palabras dentro del conjunto Z2n de todas las palabras posibles de longitud n. Por ejemplo, una estación meteorológica, muy simple, manda una señal indicando la procedencia del viento. Para ello necesitamos codificar las cuatro palabras siguientes: "Norte", "Sur", "Este" y "Oeste". Para codificar estas cuatro direcciones, debemos usar Z22 como mínimo, pero también podemos usar cuatro palabras dentro de Z23, Z24, etc. Consideremos los códigos siguientes:
C1 = {00,01,10,11}, que coincide con Z22
C2 = {000,011,101,110}, que es un subconjunto de Z23
C3 = {000000,101010,010110,101101}, un subconjunto de Z26, y
C4 = {000000,010101,111000,101101}, otro subconjunto de Z26.
A cada una de las cuatro palabras de estos cuatro códigos les asignaremos las cuatro instrucciones que nos interesan. Así, tendremos:
Código
"Norte"
"Sur"
"Este"
"Oeste"

C1

00

01

10

11

C2

000

011

101

110

C3

000000

101010

010110

101101

C4

000000

010101

111000

101101
Con el código C1 sólo usamos dos dígitos, estamos usando todas las posibles palabras de dos dígitos para las cuatro instrucciones que queremos transmitir desde la estación meteorológica. Si se produce un error en la transmisión de esta información, no habrá forma de detectarlo, ya que cualquier palabra de dos dígitos con 0 y 1 tiene un significado posible para el receptor.
El código C2 permite transmitir las cuatro direcciones del viento de la misma forma. Si se produce un solo error en la transmisión, podremos detectarlo fácilmente gracias a la siguiente observación. Cada una de las cuatro palabras dentro del código C2 tiene dos unos o ninguno. Si hay un solo error al transmitir una de estas cuatro palabras, obtendremos una palabra con un uno o con tres unos. En este caso acabamos de detectar un error, por lo que el receptor deberá solicitar que se le vuelva a transmitir la información para saber cuál es la dirección del viento en ese momento. En caso de que el receptor no tenga posibilidad de solicitar la transmisión de nuevo, no podrá recuperar qué palabra se le había mandado. Observad que los dos primeros bits son los mismos que la palabra sin codificar. Mientras que el último bit de estas palabras código es 0, si el número de unos que tiene la palabra sin codificar es par, y es uno si el número de unos que tiene la palabra sin codificar es impar. Este último bit recibe el nombre de bit de paridad.
Los códigos C3 y C4, que utilizan más bits, tienen mucha más redundancia, por lo que, además de permitirnos detectar algunos errores, nos permitirá corregirlos.
Para cada uno de estos códigos, podemos calcular las distancias entre las palabras que los forman. Definiremos distancia mínima de un código la mínima de todas las distancias entre sus palabras, exceptuando la distancia de una palabra a sí misma, que siempre será 0. Así, por ejemplo, las distancias entre todas las palabras del código C1 son 1 ó 2, por lo que diremos que la distancia mínima del código C1 es 1.
Distancias entre las palabras del código C1

C1

00

01

10

11

00

0

 

 

 

01

1

0

 

 

10

1

2

0

 

11

2

1

1

0
La distancia entre dos palabras cualesquiera del código C2 es 2, y por tanto, la distancia mínima de este código es 2. Las distancias entre las palabras del código C3 son 3, 4 y 5. Así, la distancia mínima en C3 es 3.
Distancias entre las palabras del código C3

C3

000000

101010

010110

101101

000000

0

 

 

 

101010

3

0

 

 

010110

3

4

0

 

101101

4

3

5

0
Actividad
Calculad la distancia mínima del código C4 y acabad de rellenar la siguiente tabla:
Código
Distancias entre palabras
Distancia mínima

C1

0, 1, 2

1

C2

0, 2

2

C3

0, 3, 4, 5

3

C4

 

 
Observemos la relación entre el número de dígitos que nos permite detectar un código y su distancia mínima. La distancia mínima para C1 es 1, y hemos visto que se trata de un código que no nos permite detectar errores. La distancia mínima de C2 es 2, y sabemos que permite detectar un error. Para el código C3, tenemos que su distancia mínima es 3. Si se modifican uno o dos dígitos de cualquiera de sus palabras, no es posible obtener otra palabra del código. Para obtener otra palabra del código, deberemos modificar como mínimo tres dígitos. Esto nos indica que este código permite detectar hasta dos errores. Con estos ejemplos nos vamos acercando a la siguiente afirmación.
Si sólo pretendemos detectar errores, un código con una distancia mínima d permite detectar hasta d – 1 errores. Esto se debe a que si se produce un error que modifica un número menor que d dígitos a una de las palabras del código, obtendremos una palabra que estará fuera del código. Dicho de otra forma, para modificar una palabra del código y que se obtenga otra palabra del código se deberían modificar un mínimo de d dígitos.
La redundancia de estas palabras nos permitirá corregir algunos errores; la forma de hacerlo será buscando la palabra más cercana a la palabra que hayamos recibido con algún error. Un código permite corregir hasta e errores, siendo donde significa la parte entera.
Siguiendo los ejemplos anteriores, C1 no permite corregir errores, ya que tendríamos El código C2 tampoco permite corregir errores, por lo que tendremos: En cambio, el código C3 permite corregir error.

2.2.Aritmética módulo 2

Como hemos descrito anteriormente, reduciremos la transmisión de información en la transmisión de ceros y unos. La mayoría de los códigos correctores para la transmisión de información operan con las palabras formadas con ceros y unos, de forma que permite detectar y corregir errores gracias a operaciones con los números con que representamos estas palabras. La forma de operar con ceros y unos la describimos a continuación:
El cuerpo conmutativo Z2
Consideramos el conjunto formado por estos dos únicos elementos: 0 y 1, que denominaremos Z2. Así, tenemos Z2 = {0,1}. En este conjunto definiremos una forma de sumar y una de multiplicar estos números con las tablas:
Suma: +
0
1
Producto: ·
0
1

0

0

1

0

0

0

1

1

0

1

0

1
Quizá lo más sorprendente de estas operaciones sea que estamos considerando que 1 + 1 = 0.
Ahora veamos las propiedades de estas dos operaciones en el conjunto Z2.
La suma definida en Z2 verifica las propiedades:

  • asociativa: para cualesquiera x, y, z del conjunto Z2, tenemos que (x + y) + z = x + (y + z);

  • existencia de elemento neutro: existe el elemento neutro 0, que verifica que x + 0 = 0 + x = x para cualquier x perteneciente a Z2, es decir, tanto para x = 0 como para x = 1;

  • existencia de elemento opuesto: los dos elementos de Z2 tienen su elemento opuesto. El opuesto del 0 es el –0, y el elemento opuesto al 1 es el –1. Es decir, –0 = 0 y –1 = 1, ya que 0 + 0 = 0 y 1 + 1 = 0. El elemento opuesto también se denomina inverso respecto de la suma.

Por tanto, Z2 con la suma se trata de un grupo. Además, la suma tiene la propiedad conmutativa:

  • conmutativa: para cualesquiera x, y de Z2, tenemos que x + y = y + x.

Todas estas propiedades se resumen diciendo que Z2 con la suma es un grupo conmutativo.
Con el producto definido en Z2, tenemos las siguientes propiedades:

  • asociativa: para cualesquiera x, y, z del conjunto Z2, tenemos que (x · y) · z = x · (y · z);

  • existencia de elemento neutro: existe el elemento neutro 1, que verifica que x · 1 = 1 · x = x para cualquier x del conjunto Z2;

  • existencia de elemento inverso: al multiplicar 1 · 1 obtenemos 1. Así, podemos afirmar que el inverso de 1 es 1. El elemento 0 no tiene inverso, ya que no es posible multiplicarlo por ningún valor dentro de Z2 que dé como resultado 1.

  • conmutativa: para x, y elementos de Z2 tenemos que x · y = y · x.

Las dos operaciones conjuntamente verifican la propiedad:

  • distributiva: para x, y, z elementos de Z2, tenemos que x · (y + z) = x · y + x · z.

Para resumir las propiedades que verifica Z2 con la suma y el producto, se dice que Z2 es un cuerpo conmutativo. Todas estas propiedades que hemos enumerado pueden comprobarse mirando las tablas de las operaciones suma y producto.
El conjunto Z2n como espacio vectorial
El conjunto Z2n puede interpretarse como Z2 x Z2 x ... x Z2 = Z2n. Por ejemplo, para n = 3, los elementos de Z23 hemos dicho que son {000, 001, 010, 011, 100, 101, 110, 111}, y considerando
.
En el conjunto Z2n podemos considerar las siguientes operaciones:

  • suma: para sumar dos elementos de Z2n, sumamos dígito a dígito según la suma definida en Z2. Así, por ejemplo, en Z23 tenemos: ( 0 1 1 ) + ( 0 1 0 ) = ( 0 0 1 ).

  • producto externo: podemos multiplicar un elemento cualquiera de Z2n por un elemento de Z2 multiplicando cada uno de los dígitos por este elemento. Por ejemplo: 0 · ( 1 1 0 ) = ( 0 0 0 ) y 1 · ( 1 1 0 ) = ( 1 1 0 )

  • asociativa: para cualesquiera x, y, z del conjunto Z2n, tenemos que (x+y) +z = x+ (y+z);

  • existencia de elemento neutro: existe el elemento neutro , que verifica que x + 0 = 0 + x = x , para cualquier x perteneciente a Z2n;

  • existencia de elemento opuesto: para cualquier elemento x de Z2n existe un elemento opuesto, es decir, un elemento que al sumarlo a x nos da como resultado el elemento neutro. En este caso, análogamente a Z2n, el elemento opuesto de x es el propio x, debido a que x + x = 0. El elemento opuesto también se denomina elemento inverso respecto de la suma.

  • conmutativa: para cualesquiera x, y de Z2n, tenemos que x + y = y + x;

  • distributiva del producto respecto a la suma: para cualesquiera x, y de Z2n y cualquier a de Z2, tenemos que a (x + y) = ax + ay.

  • distributiva de la suma respecto al producto: para cualquier x de Z2n y cualesquiera a y b de Z2, tenemos que (a + b) x = ax + bx.

  • asociativa: para cualquier x de Z2n y cualesquiera a y b de Z2, se satisface que a (bx) = (ab) x.

  • elemento neutro: al multiplicar 1 de Z2 por cualquier elemento de Z2n, tenemos que 1 · x = x.

El conjunto Z2n con estas dos operaciones cumple las propiedades siguientes. Con la suma tenemos:
Por tanto, Z2n con la suma se trata de un grupo. Además, la suma tiene la propiedad conmutativa:
Todas estas propiedades se resumen diciendo que Z2n con la suma es un grupo conmutativo.
Con el producto externo definido en Z2n, tenemos las siguientes propiedades:
Con estas ocho propiedades de la suma y el producto externo de Z2n, podemos afirmar que Z2n es un espacio vectorial. De ahí que llamemos vectores a sus elementos. Observad que estamos haciendo un pequeño abuso del lenguaje al identificar tiras de bits (simples tiras de ceros y unos) con vectores de Z2n.
Ejercicio
En Z23, realizad los cálculos siguientes:
a) (1,1,1) + (1,0,1)
b) (1,0,1) + (0,1,1)
c) (1,1,0) - (0,1,1)
d) 1 · (1,0,1)
e) 0 · (1,0,1)
f) 1 · (0,1,1) + 0 · (1,0,0) + 1 · (1,0,0)

2.3.Producto de matrices

Definiremos una matriz de forma poco rigurosa, pero nos bastará para entender algunos ejemplos de codificación. Una matriz es una "caja de números" puestos en forma de cuadrícula, con un cierto número de filas y de columnas. Escribiremos esta caja de números entre paréntesis para delimitarla. Por ejemplo:
es una matriz de dos filas y tres columnas y por tanto, diremos que es una matriz 2 × 3. Mientras que
es una matriz de tres filas y cuatro columnas, es decir 3 × 4.
Definiremos dos operaciones con matrices: suma y producto. La suma de matrices es relativamente sencilla. Para poder sumar dos matrices, éstas deberán tener el mismo número de filas y el mismo número de columnas. El resultado de la suma será otra matriz, que se obtendrá sumando elemento a elemento. Por ejemplo:
Ahora vamos a definir el producto de matrices. Es posible multiplicar dos matrices A · B siempre que la matriz de la izquierda tenga tantas columnas como filas tenga la matriz de la derecha. Esto es lo que sucede en las dos matrices A y B que hemos dado como ejemplo al principio. Al multiplicar dos matrices, se obtiene otra matriz, que tendrá tantas filas como la matriz de la izquierda y tantas columnas como la matriz de la derecha. En el ejemplo anterior, al multiplicar A · B obtendremos una matriz de dos filas y cuatro columnas, es decir, una matriz 2 × 4.
Entonces, dadas dos matrices A y B, la matriz resultante del producto A · B se obtendrá de la forma siguiente. El elemento que ocupa la fila i y columna j se calcula sumando todos los productos resultantes de multiplicar los elementos de la fila i de la matriz A con los elementos de la columna j de la matriz B, elemento a elemento.
Hagamos el producto de estas dos matrices detalladamente:
Observad que, al multiplicar estas dos matrices, obtenemos una matriz de 4 columnas y 2 filas, tal como habíamos anunciado. Una matriz puede tener una sola fila o una sola columna. En el ejemplo anterior hemos operado con números enteros, pero también es posible trabajar con matrices de ceros y unos y operar tal como hacemos en Z2. Así, por ejemplo, podremos sumar dos matrices formadas por sólo una fila y varias columnas de la forma siguiente:
(0 0 1 1 1 0) + (0 1 0 1 0 1) = (0+0   0+1   1+0   1+1   1+0   0+1) = (0 1 1 0 1 1)
O bien, podremos realizar el siguiente producto:
m4e2_18.gif
(0·1 + 0·0 + 1·0   0·0 + 0·1 + 1·0   0·0 + 0·0 + 1·1   0·0 + 0·1 + 1·1   0·1 + 0·0 + 1·1   0·1 + 0·1 + 1·0) = (0 0 1 1 1 0)
Observad que la matriz de la izquierda tiene 1 fila y 3 columnas (1 × 3), mientras que la de la derecha tiene 3 filas y 6 columnas (3 × 6). Así, el resultado será una matriz de 1 fila y 6 columnas (1 × 6).
m4e2_19.gif
Otro ejemplo puede ser:
m4e2_20.gif
Observemos que las dimensiones de las matrices que hay que multiplicar son 3 × 6 y 6 × 1, y que el resultado es de 3 × 1.
En el caso de que una matriz tenga una sola fila (o una sola columna), acostumbraremos a llamarla vector fila (o vector columna, según sea el caso). Así, la matriz (0 0 1 1 1 0) será un vector fila con 6 componentes, mientras que la matriz es un vector columna con 3 componentes.

2.4.Códigos lineales

Tal como hemos comentado anteriormente, existen varias formas para crear códigos detectores y correctores de errores. En este módulo nos centraremos en los códigos lineales, por ser unos de los más simples y por ser la base de los códigos correctores más potentes usados actualmente.
2.4.1.Matriz generadora
En este apartado trabajaremos con tiras de bits de Z2n tal como hemos introducido anteriormente, pero escribiremos estas tiras de bits entre paréntesis y operaremos con ellas como vectores (o matrices de una sola fila o una sola columna).
Supongamos que necesitamos codificar m palabras. Para ello, identificaremos cada una de las palabras con una tira de n bits que, como hemos comentado anteriormente, deberá verificar . Para añadir redundancia al código que queremos crear, deberemos escoger que el número, k, de dígitos de nuestro código sea mayor que n; así, tendremos que n < k. Para crear el código, escogeremos una matriz, que llamaremos matriz generadora del código, con las siguientes características:

  • Será una matriz de n filas y k columnas: n × k.

  • No puede haber ninguna fila repetida.

  • No puede haber una fila que se obtenga como suma de dos o más filas restantes.

Una forma segura de conseguir estas dos últimas condiciones será escogiendo una matriz de la forma:
Es decir, las n primeras columnas se construyen con un solo 1 y el resto, 0; en la primera columna, el 1 está en la primera fila, en la segunda columna está en la segunda fila, y así sucesivamente. De este modo conseguimos que la diagonal principal de la matriz esté formada por 1, siendo el resto 0. Las restantes columnas de la matriz se rellenan con 0 y 1, dispuestos de cierta manera (que no trataremos en este material).
A partir de las palabras que hayamos escogido en Z2n, generamos el código multiplicando cada palabra por la matriz G, de la forma siguiente:
Con esta operación obtendremos un código en el que sus palabras serán todas distintas y nos permitirá codificar y decodificar y, en general, detectar y corregir errores de una forma relativamente simple.
Veamos un ejemplo. Tenemos situado un sensor que detecta el estado del tiempo y nos debe mandar una señal que puede ser: sol, nublado, lluvia, granizo, nieve, niebla o viento. Puesto que tenemos m = 7 palabras para codificar, necesitamos un código que tenga un mínimo de siete palabras. Escogeremos n = 3, así tendremos:
,
que tiene ocho elementos para la codificación. Acordamos hacer la asignación siguiente:

Sol

(0 0 0)

Nublado

(0 0 1)

Lluvia

(0 1 0)

Granizo

(0 1 1)

Nieve

(1 0 0)

Niebla

(1 0 1)

Viento

(1 1 0)
Estado del tiempo
Asignación en Z23
Palabra código

Sol

(0 0 0)

(0 0 0 0 0 0 0)

Nublado

(0 0 1)

(0 0 1 1 0 1 1)

Lluvia

(0 1 0)

(0 1 0 1 1 0 1)

Granizo

(0 1 1)

(0 1 1 0 1 1 0)

Nieve

(1 0 0)

(1 0 0 1 1 1 0)

Niebla

(1 0 1)

(1 0 1 0 1 0 1)

Viento

(1 1 0)

(1 1 0 0 0 1 1)
A partir de estas siete palabras de Z23 que hemos escogido, crearemos un código lineal de la siguiente forma. Consideraremos la matriz generadora :
Observad que esta matriz cumple las tres condiciones que hemos pedido para las matrices generadoras. Para obtener las palabras del código lineal multiplicaremos cada una de las palabras seleccionadas de Z23 por la matriz generadora:
m4e2_25.gif
m4e2_26.gif
m4e2_27.gif
m4e2_28.gif
m4e2_29.gif
m4e2_30.gif
m4e2_31.gif
Así, las palabras que formarán el código lineal son:
Cada una de las palabras escogidas en Z23 coincide con los tres primeros dígitos del código lineal. Esto es debido a la elección de la matriz G que hemos hecho, pero no siempre tiene que ser de este modo. Para la transmisión real de la información se debe transmitir la palabra código, ya que ésta es la que nos permitirá detectar si hay algún error añadido en la transmisión y, si es posible, corregirlo.
Si calculamos la distancia de Hamming entre las palabras de este código, veremos que la distancia entre dos palabras cualesquiera de este código es 4. Por tanto, la distancia mínima del código es d = 4.
En este ejemplo, todas las palabras, excepto la formada por ceros, tiene exactamente cuatro unos. En general, esto no tiene por qué ocurrir en los códigos lineales. Sin embargo, una propiedad que sí es general en los códigos lineales es la siguiente. Para calcular la distancia mínima de un código lineal, basta con contar cuántos unos tiene la palabra del código con menor número de unos, sin contar la palabra formada únicamente por ceros. Ésta es una de las grandes ventajas de los códigos lineales. Así, podemos calcular la distancia mínima del código de forma muy simple.
La distancia mínima de un código lineal se calcula contando cuántos unos tiene la palabra del código con menos unos, sin contar la palabra formada únicamente por ceros.
Sabiendo que d = 4, este código nos permitirá detectar hasta d – 1 = 3 errores y permitirá corregir e errores, siendo e tal que:
Por tanto, e = 1, es decir, podremos corregir un error.
2.4.2.Matriz de comprobación de paridad
Ahora sólo nos falta ver cómo podemos detectar y corregir errores con un código lineal. En primer lugar deberemos calcular una matriz, llamaremos matriz de comprobación de paridad y que nos servirá tanto para detectar como para corregir errores.
La matriz de comprobación de paridad, H, será una matriz de k – n filas y k columnas. Esta matriz se obtendrá a partir de la matriz generadora de la siguiente forma: poniendo cada una de las filas de la matriz G como un vector columna, buscamos una matriz H que no esté formada sólo por ceros, tal que al multiplicarla por cada uno de estos vectores columna obtengamos el vector 0. Es decir, buscamos una matriz H tal que si g1, g2, ..., gn son las filas de la matriz G, consideradas como columnas, entonces:
H·g1 = 0, H·g2 = 0, ..., H·gn = 0
Es posible encontrar más de una matriz que satisfaga estas condiciones. Deberemos escoger una cualquiera.
Entonces, cuando recibimos una palabra codificada y queremos comprobar si es del código o no, bastará con multiplicar la matriz H por esta palabra. En caso de ser una palabra del código, el resultado será el vector formado por ceros.
Siguiendo el ejemplo anterior, podemos considerar la siguiente matriz:
Si, por ejemplo, la estación meteorológica indica '"lluvia" y no se producen errores en la transmisión, el receptor leerá la palabra (0 1 0 1 1 0 1). Para comprobar si la palabra recibida es correcta, la pondremos en columna para multiplicarla por la matriz H de la siguiente forma (recordar que estas operaciones se deben hacer con aritmética de Z2):
m4e2_34.gif
Esto afirma que la palabra (0 1 0 1 1 0 1) pertenece al código y, por tanto, no se ha producido ningún error en la transmisión.
Veamos qué ocurre cuando recibimos una palabra que no es del código por tener un solo error. Ya hemos dicho antes que este código nos permitiría corregir un solo dígito erróneo. Supongamos que se transmite "nieve", y recibimos la palabra (1 0 0 1 1 1 0). Hagamos el producto con la matriz de comprobación de paridad:
m4e2_35.gif
El resultado no ha sido un vector formado por ceros, lo que nos indica que hemos recibido una palabra que no está en nuestro código. Acabamos de detectar que la palabra código recibida contiene algún error. Si suponemos que sólo hay un error en esta palabra, podremos corregirlo. Como ya hemos comentado, la matriz H nos indicará dónde se ha cometido este error. Para ello deberemos buscar qué columna de la matriz de comprobación de paridad coincide con el vector obtenido al realizar la comprobación. En este caso, vemos que el resultado de la comprobación coincide con la tercera columna de la matriz H y, por lo tanto, el error se ha producido en el tercer dígito. Así, el tercer dígito, que era 1, tiene que ser 0, y podemos asegurar que la palabra código correcta es: (1 0 0 1 1 1 0) y por tanto, al decodificarla obtendremos (1 0 0), que corresponde al estado meteorológico "nieve". Recordemos que, tal como hemos escogido la matriz generadora del código, para decodificar simplemente debemos leer los tres primeros dígitos de la palabra código. El resto de dígitos, llamados dígitos de paridad, nos han ayudado en la detección y corrección del error.
Actividad
Ejercicio 1
Usando la matriz de comprobación de paridad del ejemplo anterior, comprobad si las siguientes palabras pertenecen al código o no, y en caso de que haya algún error, corregidlo.
a) (1 0 0 1 1 0 0)
b) (0 1 0 1 1 0 1)
c) (1 0 1 0 1 1 1)
d) (1 1 1 0 1 1 0)
Ejercicio 2
Hemos comentado que este código permite detectar hasta tres errores. Comprobad que esto es cierto con dos palabras que tengan dos errores y dos palabras que tengan tres errores.
Ejercicio 3
Estudiad qué ocurre con la palabra código (1 1 1 1 0 0 0). ¿Es una palabra del código? ¿Si recibimos esta palabra, es detectada por la matriz de decodificación como una palabra errónea?
2.4.3.Códigos lineales y no lineales
Vamos a estudiar si los códigos introducidos anteriormente, que hemos llamado C1, C2, C3 y C4, son códigos lineales o no.
El código C1 es un código lineal, pero es un caso extremo dentro de la definición de códigos lineales. Su matriz generadora, que tiene n = 2 filas y k = 2 columnas, es la matriz Al multiplicar cada uno de los elementos de Z22 por esta matriz, obtenemos el mismo elemento. No añadimos redundancia al código y, por tanto, tal como habíamos comentado anteriormente, este código no permite detectar errores. La matriz de comprobación de paridad debería tener k – n = 2 – 2 = 0 filas y k = 2 columnas. Con esto vemos una vez más que no es posible detectar errores con este código.
El código C2 también es un código lineal. Creamos este código a partir de los elementos de Z22 y la matriz generadora Las palabras del código C2 son:
m4e2_38.gif
m4e2_39.gif
m4e2_40.gif
m4e2_41.gif
La matriz H de comprobación de paridad es H = (1 1 1). Recordemos que el último bit de estas palabras código corresponde a la paridad respecto al número de unos que contiene la palabra sin codificar.
Se puede comprobar que el código C3 no es un código lineal. Por lo tanto, no será posible encontrar una matriz generadora para este código y tampoco una matriz de comprobación de paridad.
Ejemplo
Recordemos el ejemplo de la transmisión de imágenes en blanco y negro. Queremos mandar información sobre el color de tres píxeles de una imagen. Al igual que hemos hecho anteriormente, asociamos 0 para "Blanco" y 1 para "Negro". Nos interesa mandar tres dígitos que asociamos a estos dos colores, cada uno de estos tres píxeles puede tomar cualquiera de los valores: 0 y 1. Es decir, vamos a mandar xyz, donde x, y y z pueden tomar los valores 0 y 1. En lugar de mandar sólo estos tres dígitos, añadiremos redundancia con tres dígitos más, que serán los dígitos de control de paridad. La palabra código que se enviará es xyzabc, con la relación a = y + z, b = x + z y c = x + y. El receptor recibirá el mensaje xyzabc y calculará en Z2 las operaciones realizadas por el emisor. En caso de no cumplirse alguna de las igualdades, el receptor habrá detectado algún error. Por ejemplo, queremos transmitir: Blanco-Blanco-Negro; para ello, el emisor tiene que mandar 001, y la redundancia que añadirá será: a = 0 + 1 = 1, b = 0 + 1 = 1 y c = 0 + 0 = 0, Por lo tanto, mandará: 001110. Cuando el receptor recibe el mensaje, comprobará que no hay ningún error realizando las mismas operaciones que el emisor antes de mandar el mensaje. Supongamos que el mensaje transmitido llega al receptor con un solo error, es decir, que reciba, por ejemplo: 101110. El receptor lo habrá detectado al realizar las siguientes comprobaciones:
0 + 1 = 1, 1 + 1 = 0 ≠ 1 y 1 + 0 = 1 ≠ 0.
Así, detecta que las dos operaciones que no se cumplen son la segunda y la tercera. Esto le indica que el error se encuentra en la primera cifra, ya que ésta es la que interviene en los cálculos de estas dos operaciones. Así, el mensaje enviado era Blanco-Blanco-Negro. Si el error se produjera en uno de los tres últimos dígitos, por ejemplo se recibiera 001111, el receptor detectaría que sólo falla una de las tres igualdades que debe comprobar:
0 + 1 = 1, 0 + 1 = 1 y 0 + 0 = 0 ≠ 1. Esto indica que el error se ha producido en el último dígito y, por tanto, el mensaje enviado era 001110, que corresponde a Blanco-Blanco-Negro.
Comprobad que esta forma de codificación es lineal. Para ello calculad la matriz generadora del código. Dad, también, una matriz de comprobación de paridad y comprovad qué pasa si el receptor recibe las palabras 101110 y 001111.
Actividad
Ejercicio 1
Comprobad que el código C4 sí es un código lineal. Para ello es suficiente con comprobar que su matriz generadora es Observad que aunque sus dos primeras columnas no estén formadas por 1 en la diagonal y 0 en el resto, esta matriz genera el código a partir de los cuatro elementos de Z22, de modo que se obtienen las cuatro palabras del código C4 descritas anteriormente. Comprobad que una matriz de comprobación de paridad para este código puede ser la siguiente:
Ejercicio 2
Comprobad que código definido por xyztuv con z=x, t=x+y, u=0, v=x+y corresponde a un código lineal siguiendo los pasos siguientes:
a) Dar la matriz generadora de este código.
b) Comprobar que la matriz es una matriz de comprobación de paridad para este código.
c) Comprobar que la matriz también es una matriz de comprobación de paridad para este código.
Ejercicio 3
Utilizad un método parecido para mandar mensajes de cuatro dígitos, del tipo xyzt, añadiendo redundancia de la forma xyztabcd, donde a = y + z + t, b = x + z + t, c = x + y + t y d = x + y + z. Proporcionad la matriz generadora de este código. ¿Qué podemos decir si recibimos los siguientes mensajes?
10101010
11111011
11100000

2.5.Otros tipos de códigos

Además de los códigos lineales, existen otras formas de codificar. La base matemática para muchos de éstos es más compleja y necesitaríamos un curso más extenso de matemáticas para su comprensión. Algunos de estos sistemas de codificación son el Sistema 3370 de IBM, Sistema fotodigital de Digital Cypress, el SINTAC (Système Intégré de Navigation, Trafic, Anticollision, Communication), el DAT (Digital Audio Tape), el usado por las naves Voyager para la transmisión de imágenes a la Tierra, los sistemas de codificación de los teléfonos-busca, etc.

2.6.Grabaciones en CD y DVD

La teoría de codificación se aplica, además de a la transmisión, a la grabación de información. Los actuales sistemas de grabación en CD y en DVD almacenan información usando códigos basados en el abecedario de ceros y unos de forma similar a la que hemos descrito en este módulo. No entraremos en detalles sobre qué tipo de codificación se usa para almacenar esta información en CD y en DVD. Simplemente daremos una idea sobre la forma de almacenar estas tiras de ceros y unos.
Estos dos métodos de almacenamiento de datos se han convertido en las formas estándares de almacenamiento de grandes cantidades de información. Esto es debido, esencialmente, al bajo coste de su producción y a la fiabilidad en su almacenamiento, aventajando en gran medida a las cintas y discos magnéticos.
El sistema de almacenamiento y reproducción del CD fue diseñado por Philips y Sony en junio de 1980. En un inicio, los CD se crearon para grabar sonido, efecto que se consiguió convirtiendo señales acústicas en señales digitales de ceros y unos. Para ello, la señal analógica que transmite el sonido se muestrea 44.100 veces por segundo, asignando un valor numérico a cada muestra entre 0 y 65535. Este número, escrito en sistema binario, tiene una longitud de 16 bits. Si el sonido es en estéreo, se debe almacenar el doble de información para cada señal, con lo que se obtienen tiras de 32 bits. La frecuencia del sonido que es capaz de reproducir un CD y la velocidad a que se transmite cada señal es aproximadamente igual a los límites del oído humano, logrando un efecto sonoro completamente continuo.
En un CD se almacenan datos usando, fundamentalmente, un tipo de codificación lineal llamada RS (Reed-Solomon), que utiliza palabras de 255 bits y con una distancia mínima d = 5.
En un solo CD podemos almacenar más de 780 Mb de información en un espacio realmente reducido: 12 cm de diámetro por 1,2 mm de grosor. Esto se debe a la forma de almacenar la información. Veamos cómo se almacena esta información.
La grabación de un CD se hace siguiendo una pista en forma de espiral. El grosor de esta pista es de 0,5 micras (una micra equivale a una millonésima parte de un metro) y la separación entre una vuelta y otra de esta espiral es de 1,6 micras. Estas medidas hacen que la longitud de esta espiral sea realmente muy larga. Si dispusiéramos esta espiral en línea recta, mediría aproximadamente 5 km.
m4e2_rec3.gif
Sobre esta pista espiral tenemos zonas planas y zonas hundidas. Como se puede imaginar, unas representan ceros y otras unos. La forma de leer estas tiras de ceros y unos es a través de la proyección de un láser sobre la superficie del CD; según si la zona es plana o hundida, se refleja sobre un sensor óptico o no.
m4e2_rec4.gif
La forma de almacenar datos en un DVD es muy similar a la de los CD pero con una capacidad aproximadamente siete veces mayor a la de éstos. Las dimensiones físicas de un DVD son iguales a las del CD. La diferencia con el CD se basa en la forma de almacenar la información físicamente. Es decir, las zonas hundidas y zonas planas que forman la pista siguiendo una espiral sobre el DVD son más finas que las del CD, con lo que se consigue una pista más larga. Además, hay distintas formas de almacenar estas pistas, con lo que se obtienen varias espirales sobre un mismo DVD usando dos capas e, incluso, utilizando las dos caras del disco en la grabación de información. De esta forma, se consiguen hasta cuatro pistas en forma de espiral sobre un solo disco.
m4e2_rec6.gif

Ejercicios de autoevaluación

1. La codificación en Morse · · · · – – – · – · · · – quiere decir...

a) Hola.
b) Adiós.
c) Hora.

2. La codificación en Morse de la palabra salva es...

a) · · · · – · – · · · · · – · -
b) · · · · – · – · · · · · · · –
c) – – – – – · – ·····

3. Hemos recibido el mensaje en ASCII binario 01000111 01101101 01101101 01000100. ¿Qué quiere decir?

a) GMMD.
b) GmmD.
c) gMMd.

4. El número escrito en sistema binario 100101 es, en sistema decimal,...

a) 41.
b) 37.
c) 35.

5. La letra del NIF correspondiente al número 36.973.043 es...

a) X.
b) Y.
c) Z.

6. El código de barras de mi pintalabios es 3134375002677. ¿Es correcto?

a) Sí.
b) No.
c) No corresponde a un código de barras EAN-13.

7. Uno de los objetivos principales de la codificación es...

a) convertir los mensajes a ceros y unos para que no sean legibles.
b) transmitir mensajes por medio del sistema Morse o por medio del código de banderas.
c) añadir redundancia para que, si hay algún error en la transmisión, lectura o almacenamiento, éste pueda ser detectado y/o corregido.

8. ¿Cuál de las siguientes operaciones es falsa en Z2?

a) 1 + 1 = 0.
b) 0 + 0 = 1.
c) 1 · 1 = 1.

9. La distancia mínima del código lineal C = {000000, 101111, 110111, 011000} es...

a) 2.
b) 5.
c) 4.

10. La distancia mínima del código C = {0000, 0111, 1011, 1111}, que no es lineal, vale...

a) 0.
b) 2.
c) 1.

11. Sabemos que la distancia mínima de un código es d = 8. Este código nos permitirá...

a) detectar siete errores y corregir cuatro.
b) detectar siete errores y corregir tres.
c) detectar ocho errores y corregir cuatro.

12. Tenemos un código con matriz generadora . La codificación de (1 1 1) es...

a) (0 0 0 1 1).
b) (1 1 1 0 0).
c) (0 1 0 1 0).

13. Tenemos la matriz de comprobación de paridad de un cierto código. ¿Cuál de las siguientes palabras pertenece a este código?

a) (1 1 1 1 1 1).
b) (1 0 0 1 1 1).
c) (1 0 0 1 0 1).

14. Una lectora de DVD lee...

a) en forma de espiral de fuera hacia dentro.
b) en forma radial de dentro hacia fuera.
c) en forma de espiral de dentro hacia fuera.

15. En un CD, la información está grabada...

a) en una tira en código ASCII escrito en decimal y en forma de espiral.
b) en zonas microscópicas con una inclinación que el lector de láser clasifica de 0 a 9 y que nos proporciona la información como una tira de números.
c) en una tira de unos 5 km de ceros y unos codificados en zonas planas y zonas hundidas.

Solucionario

1. a) Correcto.
b) Incorrecto. Consultad la tabla del alfabeto del código Morse.
c) Incorrecto. Consultad la tabla del alfabeto del código Morse.

2. a) Correcto.
b) Incorrecto. Consultad la tabla del alfabeto del código Morse.
c) Incorrecto. Consultad la tabla del alfabeto del código Morse.

3. a) Incorrecto. Consultad la tabla de conversión ASCII.
b) Correcto.
c) Incorrecto. Consultad la tabla de conversión ASCII.

4. a) Incorrecto. Repasad los cálculos.
b) Correcto.
c) Incorrecto. Repasad los cálculos.

5. a) Incorrecto. Repasad los cálculos y comprobad el resultado con la tabla de asignación de letra.
b) Incorrecto. Repasad los cálculos y comprobad el resultado con la tabla de asignación de letra.
c) Correcto.

6. a) Correcto.
b) Incorrecto. Repasad la comprobación.
c) Incorrecto. Sí que es código EAN-13.

7. a) Incorrecto. Las conversiones a ceros y unos se hacen normalmente con codificaciones como el ASCII, que son conocidas por todo el mundo.
b) Incorrecto. Actualmente, la teoría de la codificación se centra en las transmisiones y almacenamiento de información en forma electrónica u óptica (CD y DVD).
c) Correcto.

8. a) Incorrecto. Repasad la suma en Z 2.
b) Correcto.
c) Incorrecto. Repasad el producto en Z 2

9. a) Correcto.
b) Incorrecto. En un código lineal, la distancia mínima es el número de unos de la palabra que tiene menos (exceptuando la palabra que tiene todo ceros).
c) Incorrecto. En un código lineal, la distancia mínima es el número de unos de la palabra que tiene menos (exceptuando la palabra de todo ceros).

10. a) Incorrecto. La distancia mínima no puede ser nunca 0.
b) Incorrecto. Calculad todas las distancias posibles y veréis que la mínima no es ésta.
c) Correcto.

11. a) Incorrecto. No habéis aplicado bien la fórmula del número de bits que se pueden corregir.
b) Correcto.
c) Incorrecto. No habéis aplicado bien la fórmula del número de bits que se pueden detectar ni la fórmula del número de bits que se pueden corregir.

12. a) Incorrecto. Repasad el cálculo del vector por la matriz.
b) Correcto.
c) Incorrecto. Repasad el cálculo del vector por la matriz.

13. a) Incorrecto. Repasad el cálculo del vector por la matriz.
b) Correcto.
c) Incorrecto. Repasad el cálculo del vector por la matriz.

14. a) Incorrecto. Consultad cómo se hace la lectura de un DVD.
b) Incorrecto. Consultad cómo se hace la lectura de un DVD.
c) Correcto.

15. a) Incorrecto. En la superficie del disco se graba en forma de zonas hundidas o no hundidas para poder detectarlas con el lector láser.
b) Incorrecto. En la superficie del disco se graba solamente en forma de zonas hundidas o no hundidas para poder detectarlas con el lector láser.
c) Correcto.