EL CÓDIGO DE GRAY

El código de Gray es usado en informática y resulta útil en determinadas aplicaciones que intentan minimizar el error en un determinado proceso de transmisión de datos. Dado un sistema de numeración cualquiera, el cambio de un número del mismo al siguiente comporta el cambio de uno o varios dígitos: por ejemplo, en el sistema decimal, el paso de 46 a 47 implica un solo cambio, pero el de 999 a 1000 supone cuatro cambios.

El código de Gray establece un “orden númerico” tal que en cada paso de un número al “siguiente” sólo haya que alterar una cifra. Por ejemplo, en el sistema decimal, podríamos establecer este “orden”:

#####	0
1	1
2	11
3	10
4	110
5	111
6	101
7	100
8	1100
9	1101
10	1111
11	1110
12	1010
13	1011
14	1001
15	1000
16	11000
17	11001
18	11011
19	11010
20	11110
21	11111
22	11101
23	11100
24	10100
25	10101
26	10111
27	10110
28	10010
29	10011
30	10001
31	10000
32	110000
33	110001
34	110011
35	110010
36	110110
37	110111
38	110101
39	110100
40	111100
41	111101
42	111111

Existen para cada base multitud de códigos. Observemos que. para el caso binario, el más interesante, un código equivale a un paseo por los cuatro vértices del cuadrado de la figura, numerados como en ella se indica. En el caso de un cubo, la diversidad de posibles paseos aumenta: por ejemplo, uno de ellos podría ser 000-001-011-010-110-111-101-100. Este tipo de camino, en que se retorna al punto de salida, es llamado un “camino hamiltoniano”. El número de posibles caminos hamiltonianos aumenta exponencialmente con la dimensión del hipercubo correspondiente, y hasta ahora, que yo sepan, no se conoce siquiera el número para n=4.

El código de Gray más simple existente para la base binaria es llamado “el código reflejado de Gray”. Para muchos matemáticos es el código Gray por excelencia. Para convertir un número binario cualquiera en su “reflejado equivalente de Gray” sometámoslo a las siguientes manipulaciones:

1. Consideremos cada dígito partiendo de la derecha. Sea éste D(n), siendo n su lugar desde la derecha.

2. Si D(n+1)=0, hágase D(n)=D(n) (MANTENER)

3. Si D(n+1)=1, hágase D(n)=1-D(n) (CAMBIAR)

4. Prosígase así hasta el final (la “siguiente” cifra al dígito más a la izquierda, naturalmente es cero).

Por ejemplo: el número 110111 pasa a 101100.

Existe una regla para deshacer el cambio. Empezando por la derecha, si la suma de los dígitos hacia la izquierda es par, se mantiene el dígito. Si es impar, se cambia. Así, el antes hallado 110111 se restaura a 110111.

El código de Grey es útil en la resolución de determinados problemas, por ejemplo el del baguenodier, que consiste en una serie de nudos que deben ser desenlazados unos de otros de forma que deshacerse uno cada vez.

JMAiO