Going backwards A5/1

On A5/1 Explained V (Spanish Version)

By Juan Chamero, juan.chamero@intag.org, as of April 2006

 

Determinación de posibles ancestros de un estado S(t) dado

Algoritmo de Bifurcación

 

    Vamos a crear una tabla para el análisis de los distintos estados del Vector Reloj que podrá servirnos además para una función de “table lookup” que nos permita ir creando el árbol de ancestros de un estado inicial dado y navegar por el mismo subiendo por el árbol que surge de S(t) “hacia atrás” dentro del proceso del algoritmo A5/1 pero adelante en el árbol. La tabla tiene 64 entradas correspondientes a un vector secuencial de (0 0 0 0 0 0) a (1 1 1 1 1 1) construido en base a los vectores vecindad y de reloj, de 3 bits cada uno. Al arribar a un nodo dado el par (vecindad, reloj)  se sabe la apertura (b) del mismo  y los b estados que podrán ser ancestros.

Siendo las probabilidades de bifurcación

 

P(0) = 12/32

P(1) = 13/32

P(2) = 3/32

P(3) = 3/32

P(4) = 1/32

 

Nota: Estas probabilidades surgen directamente de la distribución de frecuencias del factor abertura b.

 

Con una esperanza matemática de b=1 expresada por:

 

(E(b)=0x12/32 + 1x13/32 + 2x3/32 + 3x3/32 + 4x1/32 = 1)

 

 

Detección de los estados completos en cada nodo.

 

    Empleando el sistema de tripletes, bastará con ir abriendo nodos según ellos. Así si al llegar a un nodo caracterizado por el par (0 3) (sombreado en amarillo en nuestra tabla) tendremos como posibles ancestros los 3 estados cuyos respectivos vectores reloj son los del centro de las matrices de 3x3 sombreadas de color celeste, que estarán en las cercanías de los estados correspondientes al nivel del nodo y que las iremos registrando como tripletes (i j k).

 

Nota: No confundir con los i j k que eventualmente apuntan a los registros en nuestros análisis.

 

0

0

 

 

0

0

 

 

0

0

 

0

0

 

 

 

0

0

 

0

1

 

 

0

1

 

0

1

 

 

 

0

1

 

 

0

1

 

0

1

 

0

1

 

 

 

0

1

 

 

0

1

 

 

0

1

3

 

La mecánica del algoritmo de determinación de estos tripletes, y que es el que genera el contenido de cada nodo, es la siguiente:

 

 

Notación a emplear

 

Vector Reloj: ( s1(10(t)), s2(11(t)), s3(12(t))) apuntando a los bits 10, 11 y 12 de los registros R1, R2 y R3 respectivamente en l momento (t).

 

Vector Vecindad: ( s1(9(t)), s2(10(t)), s3(11(t))) apuntando a los bits 9, 10 y 11 de los registros R1, R2 y R3 respectivamente en l momento (t).

 

A los fines de entender la mecánica del algoritmo haremos la siguiente simplificación:

 

( s1(10(t)), s2(11(t)), s3(12(t))): (s1, s2, s3)

( s1(9(t)), s2(10(t)), s3(11(t))): (s1´, s2´, s3´)3

 

 

Algoritmo de Creación de ancestros por nodo

 

Daremos por sentado que estamos refiriéndonos en cada momento de la creación de la arborescencia al momento (t) para “avanzar” hacia el momento (t-1) obteniendo los posibles S(t´).

 

De la tabla se extraen todas las posibles transformaciones que llevan de S(t-1) a S(t), desde 0 a cuatro con las probabilidades calculadas. De análisis de la tabla surgen los siguientes seis tipos de casos:

 

a) 1 único ancestro del tipo: “se desplazan” R1-R2 o R1-R3 o R2-R3

b) No hay ancestros

c) 1 ancestro del tipo: “se desplazan” los tres registros al unísono

d) 4 ancestros, R1-R2 y R1-R3 y R2-R3 y R1-R-R3

e) 2 ancestros del tipo: “se desplazan” (R1-R2 o R1-R3 o R2-R3) y R1-R2-R3

f) 3 ancestros del tipo: {(R1-R2 y R1-R3) o (R1-R2 y R2-R3) o (R1-R3 y R2.R3) y R1-R2-R3

 

Ahora analicemos lo que ocurre con los elementos del los dos vectores para cada uno de los tipos de casos y tendremos resuelto la lógica del algoritmo de bifurcación (ver complemento matemático al fin de este módulo).

 

 

 

a) SI si´ = sj´¬ =sk´ = sk, para cualquier k, ENTONCES CONTROL RELOJ (t – 1) = (i j)

b) SI si´ = sj ´ ¬= sk´ ¬ = sk, para cualquier k, ENTONCES No hay ancestro posible

c) SI s1´ = s2´ = s3´ = s1 = s2 = s3, ENTONCES CONTROL RELOJ (t – 1) = (1 2 3)

d SI s1´= s2´= s3´ ¬= s1 = s2 = s3, ENTONCES CONTROL RELOJ (t – 1) puede ser ((1 2) o (1 3) o (2 3)) o (1 2 3)

e) SI s1´ = s2´ = s3´ = si = sj ¬ = sk, para cualquier k, ENTONCES CONTROL RELOJ (t – 1)  puede ser cualquier par (i j) y (1 2 3)

f) SI s1´= s2´= s3´= si ¬ = sj = sk, para cualquier i, ENTONCES CONTROL RELOJ (t – 1) toma cualquiera de los tres valores (i j), (i k), y (1 2 3)

 

 

 

 

Cómo se llega a la lógica del algoritmo de bifurcación

 

  Veamos la parte del algoritmo para casos a). Extraigamos de la tabla estos casos y veamos algunas de sus estructuras, por ejemplo para R1-R2:

 

 

0

0

 

 

0

0

0

0

 

 

0

0

1

1

 

1

1

 

0

0

 

 

0

0

0

1

 

 

0

1

1

1

 

1

1

 

0

1

 

 

0

1

0

1

 

 

0

1

1

1

 

1

1

 

0

1

 

 

0

1

0

1

 

 

0

1

1

1

 

1

1

 

1

0

 

 

1

0

1

0

 

 

1

0

0

0

 

0

0

 

1

0

 

 

1

0

1

1

 

 

1

1

0

0

 

0

0

 

1

1

 

 

1

1

1

0

 

 

1

0

0

0

 

0

0

 

1

1

 

 

1

1

1

1

 

 

1

1

0

0

 

0

0

 

 

 

¿Qué es lo que se encuentra como plantilla común en los 8 casos?. Que en todos los casos s1´=s2´ y que a su vez deben ser complementarios con s3´=s3, formando una especie de “escuadra lógica de 90 grados. Lo mismo ocurrirá para R1-R3 y para R2-R3 permutando los índices. Por ello usaremos para referenciar a los registros y a través de estos los índices del triplete del estado ancestro en cuestión la notación (i j k) y sus seis posibles permutaciones: (1 2 3), (1 3 2), (2 1 3), (2 3 1), (3 1 2), (3 2 1). Pruébese para los otros casos y encontrará el mecanismo lógico.

 

 

 

Tabla de todas las 64 posibles transformaciones del Vector reloj

 

 

v

C

 

R1-R2

 

R1-R3

 

R2-R3

 

R1-R2-R3

b

0

0

 

 

0

0

 

 

0

0

 

0

0

 

 

 

0

0

 

0

0

 

 

0

0

 

0

0

 

 

 

0

0

 

 

0

0

 

0

0

 

0

0

 

 

 

0

0

 

 

0

0

 

 

0

0

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

0

 

 

0

0

 

 

0

0

 

0

0

 

 

 

0

0

 

0

0

 

 

0

0

 

0

0

 

 

 

0

0

 

 

0

0

 

0

1

 

0

1

 

 

 

0

1

 

 

0

1

 

 

0

1

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

0

 

 

0

0

 

 

0

0

 

0

0

 

 

 

0

0

 

0

0

 

 

0

0

 

0

0

 

 

 

0

0

 

 

0

0

 

1

0

 

1

0

 

 

 

1

0

 

 

1

0

 

 

1

0

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

0

 

 

0

0

 

 

0

0

 

0

0

 

 

 

0

0

 

0

0

 

 

0

0

 

0

0

 

 

 

0

0

 

 

0

0

 

1

1

 

1

1

 

 

 

1

1

 

 

1

1

 

 

1

1

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

0

 

 

0

0

 

 

0

0

 

0

0

 

 

 

0

0

 

0

1

 

 

0

1

 

0

1

 

 

 

0

1

 

 

0

1

 

0

0

 

0

0

 

 

 

0

0

 

 

0

0

 

 

0

0

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

0

 

 

0

0

 

 

0

0

 

0

0

 

 

 

0

0

 

0

1

 

 

0

1

 

0

1

 

 

 

0

1

 

 

0

1

 

0

1

 

0

1

 

 

 

0

1

 

 

0

1

 

 

0

1

3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

0

 

 

0

0

 

 

0

0

 

0

0

 

 

 

0

0

 

0

1

 

 

0

1

 

0

1

 

 

 

0

1

 

 

0

1

 

1

0

 

1

0

 

 

 

1

0

 

 

1

0

 

 

1

0

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

0

 

 

0

0

 

 

0

0

 

0

0

 

 

 

0

0

 

0

1

 

 

0

1

 

0

1

 

 

 

0

1

 

 

0

1

 

1

1

 

1

1

 

 

 

1

1

 

 

1

1

 

 

1

1

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

0

 

 

0

0

 

 

0

0

 

0

0

 

 

 

0

0

 

1

0

 

 

1

0

 

1

0

 

 

 

1

0

 

 

1

0

 

0

0

 

0

0

 

 

 

0

0

 

 

0

0

 

 

0

0

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

0

 

 

0

0

 

 

0

0

 

0

0

 

 

 

0

0

 

1

0

 

 

1

0

 

1

0

 

 

 

1

0

 

 

1

0

 

0

1

 

0

1

 

 

 

0

1

 

 

0

1

 

 

0

1

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

0

 

 

0

0

 

 

0

0

 

0

0

 

 

 

0

0

 

1

0

 

 

1

0

 

1

0

 

 

 

1

0

 

 

1

0

 

1

0

 

1

0

 

 

 

1

0

 

 

1

0

 

 

1

0

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

0

 

 

0

0

 

 

0

0

 

0

0

 

 

 

0

0

 

1

0

 

 

1

0

 

1

0

 

 

 

1

0

 

 

1

0

 

1

1

 

1

1

 

 

 

1

1

 

 

1

1

 

 

1

1

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

0

 

 

0

0

 

 

0

0

 

0

0

 

 

 

0

0

 

 1

1

 

 

1

1

 

1

1

 

 

 

1

1

 

 

1

1

 

0

0

 

0

0

 

 

 

0

0

 

 

0

0

 

 

0

0

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

0

 

 

0

0

 

 

0

0

 

0

0

 

 

 

0

0

 

1

1

 

 

1

1

 

1

1

 

 

 

1

1

 

 

1

1

 

0

1

 

0

1

 

 

 

0

1

 

 

0

1

 

 

0

1

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

0

 

 

0

0

 

 

0

0

 

0

0

 

 

 

0

0

 

1

1

 

 

1

1

 

1

1

 

 

 

1

1

 

 

1

1

 

1

0

 

1

0

 

 

 

1

0

 

 

1

0

 

 

1

0

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

0

 

 

0

0

 

 

0

0

 

0

0

 

 

 

0

0

 

1

1

 

 

1

1

 

1

1

 

 

 

1

1

 

 

1

1

 

1

1

 

1

1

 

 

 

1

1

 

 

1

1

 

 

1

1

1

 

0

1

 

 

0

1

 

 

0

1

 

0

1

 

 

 

0

1

 

0

0

 

 

0

0

 

0

0

 

 

 

0

0

 

 

0

0

 

0

0

 

0

0

 

 

 

0

0

 

 

0

0

 

 

0

0

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

1

 

 

0

1

 

 

0

1

 

0

1

 

 

 

0

1

 

0

0

 

 

0

0

 

0

0

 

 

 

0

0

 

 

0

0

 

0

1

 

0

1

 

 

 

0

1

 

 

0

1

 

 

0

1

3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

1

 

 

0

1

 

 

0

1

 

0

1

 

 

 

0

1

 

0

0

 

 

0

0

 

0

0

 

 

 

0

0

 

 

0

0

 

1

0

 

1

0

 

 

 

1

0

 

 

1

0

 

 

1

0

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

1

 

 

0

1

 

 

0

1

 

0

1

 

 

 

0

1

 

0

0

 

 

0

0

 

0

0

 

 

 

0

0

 

 

0

0

 

1

1

 

1

1

 

 

 

1

1

 

 

1

1

 

 

1

1

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

1

 

 

0

1

 

 

0

1

 

0

1

 

 

 

0

1

 

0

1

 

 

0

1

 

0

1

 

 

 

0

1

 

 

0

1

 

0

0

 

0

0

 

 

 

0

0

 

 

0

0

 

 

0

0

3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

1

 

 

0

1

 

 

0

1

 

0

1

 

 

 

0

1

 

0

1

 

 

0

1

 

0

1

 

 

 

0

1

 

 

0

1

 

0

1

 

0

1

 

 

 

0

1

 

 

0

1

 

 

0

1

4

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

1

 

 

0

1

 

 

0

1

 

0

1

 

 

 

0

1

 

0

1

 

 

0

1

 

0

1

 

 

 

0

1

 

 

0

1

 

1

0

 

1

0

 

 

 

1

0

 

 

1

0

 

 

1

0

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

1

 

 

0

1

 

 

0

1

 

0

1

 

 

 

0

1

 

0

1

 

 

0

1

 

0

1

 

 

 

0

1

 

 

0

1

 

1

1

 

1

1

 

 

 

1

1

 

 

1

1

 

 

1

1

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

1

 

 

0

1

 

 

0

1

 

0

1

 

 

 

0

1

 

1

0

 

 

1

0

 

1

0

 

 

 

1

0

 

 

1

0

 

0

0

 

0

0

 

 

 

0

0

 

 

0

0

 

 

0

0

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

1

 

 

0

1

 

 

0

1

 

0

1

 

 

 

0

1

 

1

0

 

 

1

0

 

1

0

 

 

 

1

0

 

 

1

0

 

0

1

 

0

1

 

 

 

0

1

 

 

0

1

 

 

0

1

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

1

 

 

0

1

 

 

0

1

 

0

1

 

 

 

0

1

 

1

0

 

 

1

0

 

1

0

 

 

 

1

0

 

 

1

0

 

1

0

 

1

0

 

 

 

1

0

 

 

1

0

 

 

1

0

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

1

 

 

0

1

 

 

0

1

 

0

1

 

 

 

0

1

 

1

0

 

 

1

0

 

1

0

 

 

 

1

0

 

 

1

0

 

1

1

 

1

1

 

 

 

1

1

 

 

1

1

 

 

1

1

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

1

 

 

0

1

 

 

0

1

 

0

1

 

 

 

0

1

 

1

1

 

 

1

1

 

1

1

 

 

 

1

1

 

 

1

1

 

0

0

 

0

0

 

 

 

0

0

 

 

0

0

 

 

0

0

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

1

 

 

0

1

 

 

0

1

 

0

1

 

 

 

0

1

 

1

1

 

 

1

1

 

1

1

 

 

 

1

1

 

 

1

1

 

0

1

 

0

1

 

 

 

0

1

 

 

0

1

 

 

0

1

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

1

 

 

0

1

 

 

0

1

 

0

1

 

 

 

0

1

 

1

1

 

 

1

1

 

1

1

 

 

 

1

1

 

 

1

1

 

1

0

 

1

0

 

 

 

1

0

 

 

1

0

 

 

1

0

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

1

 

 

0

1

 

 

0

1

 

0

1

 

 

 

0

1

 

1

1

 

 

1

1

 

1

1

 

 

 

1

1

 

 

1

1

 

1

1

 

1

1

 

 

 

1

1

 

 

1

1

 

 

1

1

0

 

1

0

 

 

1

0

 

 

1

0

 

1

0

 

 

 

1

0

 

0

0

 

 

0

0

 

0

0

 

 

 

0

0

 

 

0

0

 

0

0

 

0

0

 

 

 

0

0

 

 

0

0

 

 

0

0

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

0

 

 

1

0

 

 

1

0

 

1

0

 

 

 

1

0

 

0

0

 

 

0

0

 

0

0

 

 

 

0

0

 

 

0

0

 

0

1

 

0

1

 

 

 

0

1

 

 

0

1

 

 

0

1

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

0

 

 

1

0

 

 

1

0

 

1

0

 

 

 

1

0

 

0

0

 

 

0

0

 

0

0

 

 

 

0

0

 

 

0

0

 

1

0

 

1

0

 

 

 

1

0

 

 

1

0

 

 

1

0

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

0

 

 

1

0

 

 

1

0

 

1

0

 

 

 

1

0

 

0

0

 

 

0

0

 

0

0

 

 

 

0

0

 

 

0

0

 

1

1

 

1

1

 

 

 

1

1

 

 

1

1

 

 

1

1

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

0

 

 

1

0

 

 

1

0

 

1

0

 

 

 

1

0

 

0

1

 

 

0

1

 

0

1

 

 

 

0

1

 

 

0

1

 

0

0

 

0

0

 

 

 

0

0

 

 

0

0

 

 

0

0

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

0

 

 

1

0

 

 

1

0

 

1

0

 

 

 

1

0

 

0

1

 

 

0

1

 

0

1

 

 

 

0

1

 

 

0

1

 

0

1

 

0

1

 

 

 

0

1

 

 

0

1

 

 

0

1

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

0

 

 

1

0

 

 

1

0

 

1

0

 

 

 

1

0

 

0

1

 

 

0

1

 

0

1

 

 

 

0

1

 

 

0

1

 

1

0

 

1

0

 

 

 

1

0

 

 

1

0

 

 

1

0

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

0

 

 

1

0

 

 

1

0

 

1

0

 

 

 

1

0

 

0

1

 

 

0

1

 

0

1

 

 

 

0

1

 

 

0

1

 

1

1

 

1

1

 

 

 

1

1

 

 

1

1

 

 

1

1

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

0

 

 

1

0

 

 

1

0

 

1

0

 

 

 

1

0

 

1

0

 

 

1

0

 

1

0

 

 

 

1

0

 

 

1

0

 

0

0

 

0

0

 

 

 

0

0

 

 

0

0

 

 

0

0

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

0

 

 

1

0

 

 

1

0

 

1

0

 

 

 

1

0

 

1

0

 

 

1

0

 

1

0

 

 

 

1

0

 

 

1

0

 

0

1

 

0

1

 

 

 

0

1

 

 

0

1

 

 

0

1

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

0

 

 

1

0

 

 

1

0

 

1

0

 

 

 

1

0

 

1

0

 

 

1

0

 

1

0

 

 

 

1

0

 

 

1

0

 

1

0

 

1

0

 

 

 

1

0

 

 

1

0

 

 

1

0

4

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

0

 

 

1

0

 

 

1

0

 

1

0

 

 

 

1

0

 

1

0

 

 

1

0

 

1

0

 

 

 

1

0

 

 

1

0

 

1

1

 

1

1

 

 

 

1

1

 

 

1

1

 

 

1

1

3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

0

 

 

1

0

 

 

1

0

 

1

0

 

 

 

1

0

 

1

1

 

 

1

1

 

1

1

 

 

 

1

1

 

 

1

1

 

0

0

 

0

0

 

 

 

0

0

 

 

0

0