Mise en table

Une autre solution pour implémenter l'ABSG consiste à faire des mises en tables. Pour chaque entrée de quatre bits à l'ABSG, on va pré-calculer la ou les sortie(s) si elle(s) existe(nt) ainsi que les nouvelles valeurs du bit à sortir et du bit à rechercher (cf. Exemple précédent). Pour chaque couple (bit à rechercher 'r', bit à sortir 's'), on a les bonnes mises à jour grâce aux tables. Cinq couples ont été traités:

	Bit à rechercher	Bit à sortir
Table 1	r = 1	s = 0
Table 2	r = 0	s = 1
Table 3	r = 1	s = ?
Table 4	r = 0	s = ?
Table 5	r = ?	s = ?

Exemple 1

Bit recherché:	1
Bit à sortir:	?
Séquence d'entrée:	0000
Sortie de l'ABSG:	rien à sortir
Bit à rechercher:	1
Bit à sortir:	0

A la fin du traitement de ce mot de 4 bits, le bit à rechercher 'r' reste à 1 et celui à sortir est passé à 0, ce qui correspond à la table 1. Exemple 2

Bit recherché:	?
Bit à sortir:	?
Séquence en entrée:	1100
Sortie de l'ABSG:	1	0
Bit à rechercher:	?
Bit à sortir:	?

Pour le mot binaire 1100, les valeurs recherchées ont été retrouvées immédiatement et l'ABSG a sorti deux valeurs. La mise à jour n'a pas permis au bit à rechercher et au bit à sortir d'avoir des valeurs connues.

En observant les exemples présentés précédemment, on se rend compte que nous avons besoin de plus que 4 bits pour coder l'état interne de l'ABSG. D'où, pour créer les tables, nous avons pris un octet pour enregistrer chacun de ces cas en suivant le découpage binaire suivant:

bit 0	le premier bit à sortir.
bit 1	le deuxième bit à sortir.
bit 2 et 3	le nombre de bits à sortir.
bit 4	le bit à rechercher.
bit 5	l'état du bit à rechercher : connu ou inconnu.
bit 6	le bit à sortir.
bit 7	l'état du bit à sortir : connu ou inconnu.

Les cinq tables obtenues contiennent les octets qui permettent les mises à jour de l'état interne de l'ABSG. Chaque octet suit le découpage présenté dans la figure .

Figure: Découpage binaire de l'ABSG.

Pour distinguer les différents cas, on s'est fixé les règles suivantes:

• Si le prochain bit à rechercher ou à sortir est inconnu alors le bit d'état lui correspondant est mis à 1, sinon à 0.
• Le mot de deux bits (bit 2 et bit 3) prend l'une des valeurs suivantes :
  - (00) ou (11): rien à sortir.
  - (01): 1 bit à sortir.
  - (10): deux bits à sortir.
  

Ces règles nous facilite la tâche. En effet dans la fonction de l'ABSG, il n'y aura que 5 valeurs possibles de couples correspondants au mot composé par les bits 4, 5, 6 et 7:

• $0001_2$ : le bit à rechercher: 1, le bit à sortir: 0.
• $0100_2$ : le bit à rechercher: 0, le bit à sortir: 1.
• $0111_2$ : le bit à rechercher: 1, le bit à sortir: ?.
• $0011_2$ : le bit à rechercher: 0, le bit à sortir: ?.
• $1111_2$ : le bit à rechercher: ?, le bit à sortir: ?.
  

Pour mettre à jour le bit à rechercher, le bit à sauvegarder et le(s) bit(s) à sortir, il suffit d'accéder à la case correspondante de la table adéquate. En implémentant l'ABSG nous avons fait en sorte que les quatre bits de poids fort (bits 4, 5, 6 et 7) nous donne la table et les quatre bits restant nous renvoie sur la case à laquelle il faut accéder.
Les tables qui contiennent les valeurs de sorties de l'ABSG suivant la valeur du bit à rechercher et de celui à sortir ont été créées automatiquement par un programme écrit en C.