IRIA
laboria

laboratoire de recherche
en informatique
et automatique

Les automates programmables
par coassignation

<figure><img src="image_1.png" /></figure>

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

Rapport de Recherche n°86

Novembre 1974
# LES AUTOMATES PROGRAMMABLES PAR COASSIGNATION

## M. DEPEYROT

### Sommaire

Une classe de macromodules universels - appelés KD - pour logique séquentielle programmable sans diodes est décrite avec une technique d'assignation des états - appelée coassignation - offrant une alternative pour la microprogrammation ou la diagrammation dans les circuits intégrés à grande échelle. Un modèle généralisé des machines séquentielles - appelé polymate et appliqué précédemment au traitement en temps réel - se révèle l'outil adéquat pour l'aide à la conception des KD. Cette étude théorique des polymates a fait la preuve de sa nature pragmatique par le dépôt d'un brevet sur les modules KD.

### Summary.

A class of universal macromodules - called KD - for diode-free programmable sequential logic is described, together with a state-assignment technique - called coassignment - offering a substitute for firmware or chartware for LSI circuits. A generalized model of sequential machines - called polymaton and previously applied to real-time processing - proves to be the adequate tool for KD design automation. This theoretical study of polymata demonstrated its pragmatic nature through the registration of a patent for KD modules.
# 1. Introduction à la logique séquentielle universelle.

La microprogrammation [inventée et baptisée "microprogramming" par WILKES] favorise l'emploi des techniques d'intégration à grande échelle des circuits intégrés logiques (schéma I), mais comporte de nombreuses complications (décodage d'adresse de microinstruction et branchements sur codes de condition) et limitations (une seule microinstruction exécutable par temps de cycle) qui invitent à la mise au point de nouvelles techniques.

La diagrammation [inventée et baptisée "chartware" par BELL, GRASON, NEWELL] simplifie l'emploi des commandes et supprime la sélection d'adresse (permettant donc la simultanéité d'exécution de diverses microinstructions), mais ne permet qu'un faible degré d'intégration.

La coassignation, présentée ici avec un schéma-type de réalisation, est un substitut de ces techniques permettant l'implémentation d'un boitier technologique à haut degré d'intégration pour contenir des modules universels à logique séquentielle programmable appelés KD ou polymates selon les cas.

## Références :

[1] M.V. WILKES. "The Best way to design an automatic Calculating machine". Manchester University computer inaugural Conference. pp. 16-18. (July 1951).

[2] C.G. BELL, J.GRASON, A. NEWELL. "Designing computers and digital Systems". Digital Press (1972).

[3] P. WEINER, J.E. HOPCROFT. "Bounded fan-in, bounded fan-out, uniform decompositions of synchronous sequential machines. IEEE Proc. Letters, Vol. 56, pp. 1219-1220 (July 1968).

Ce dernier article présente une décomposition en modules à faible degré d'intégration basé sur une méthodologie apparentée à la présente mais de moindre généralité.
<figure><img src="image_2.png" /><figcaption>Schéma I. Microprogrammation classique.
initialisation U</figcaption></figure>

Si Z dénote l'ensemble des microinstructions, on peut définir une
table de transition $\tau: Z \times V \to Z$,
et une table de sortie $\sigma: Z \times V \to Y$,
Cette dernière est dite en forme "transition-sortie" (ou T), par opposition à la
forme "état-sortie" (dite S) où une sortie dans Y dépend seulement de l'état
dans Z et non plus d'une entrée dans V. Pour plus de détails sur ce genre de
modèles, le lecteur est invité à se reporter au document de référence [4].

<footnote>[4] M. DEPEYROT. "Sur la Synchronisation et la fiabilité des Automates".
Revue Bleue de l'AFCET. RAIRO. 5ème Année. B-2. pp. 87-110. [Décembre 1971].</footnote>
## 2. Exemple d'un microalgorithme représenté par son graphe des états G(K).

A chaque branchement dans un microalgorithme K est associé un sommet représentant un état dans son graphe G(K). Si pour chaque état la transition de K est définie pour toute condition d'entrée de V, le microalgorithme est dit complètement spécifié.

### Table des états :

<table><thead><tr><th>τ</th><th>v<sub>0</sub></th><th>v<sub>1</sub></th><th>σ</th></tr></thead><tbody><tr><td>z<sub>0</sub></td><td>z<sub>1</sub></td><td>z<sub>2</sub></td><td>y<sub>0</sub></td></tr><tr><td>z<sub>1</sub></td><td>z<sub>1</sub></td><td>z<sub>2</sub></td><td>y<sub>1</sub></td></tr><tr><td>z<sub>2</sub></td><td>z<sub>2</sub></td><td>z<sub>3</sub></td><td>y<sub>0</sub></td></tr><tr><td>z<sub>3</sub></td><td>z<sub>1</sub></td><td>z<sub>0</sub></td><td>y<sub>1</sub></td></tr></tbody></table>

La forme ici est dite état-sortie car la fonction de sortie σ est indépendante des entrées dans V.

### Graphe des états :

Les sommets doublement cerclés correspondent aux états dont la sortie est $y_1$.

<figure><img src="image_3.png" /><figcaption>**Schéma II.** Graphe de l'exemple G(K).</figcaption></figure>
### 3. La coassignation sur modules universels KD.

Pour être utilisables en logique séquentielle universelle, les modules KD définis ci-après requièrent une assignation des états spécifique, donnée par l'algorithme suivant dit de "construction de la table des coétats".

Soit K un microalgorithme complètement spécifié avec un ensemble de m entrées U à codage primitif (1 parmi m) permettant le forçage de certains états initiaux,
- un ensemble de q entrées V à codage primitif permettant le branchement sur codes de conditions,
- un espace de n états Z codés sur le registre d'état fait de bascules binaires M,
- un ensemble de p sorties ou micro-ordres Y à codage primitif permettant la commande d'une logique extérieure,

- une fonction de rythme $\rho$ permettant de bloquer les transitions dues au branchement sur conditions de V et d'effectuer le forçage d'un état initial par une entrée de U,

- une fonction de transition $\tau$ donnée par une table des états indiquant l'état cible pour une paire (état, entrée) dans $Z \times V$,

- une fonction de sortie $\sigma$ associant les microordres aux états (et entrées) présents.

Il existe une assignation des états D telle que chaque chiffre binaire w dans une bascule M du codage d'un état z dépende de exactement q chiffres binaires du codage de l'état précédent. Chaque code $D(z)$ requiert au plus (n-1) chiffres binaires non nuls dans au moins n bascules et au plus d, avec $d \le 2^n-2$.

Alors le microalgorithme K peut être implémenté en une forme itérative KD à l'aide d'un seul type de logique combinatoire d'entrée des bascules en forme normale disjonctive à entrance fixe q. L'état de repos ou d'arrêt du micro-algorithme K est l'état stable $z_\infty$ ayant uniquement des zéros dans son assignation.

Un tel modèle d'algorithme, appelé **polymate**, a été initialement utilisé en [5] pour des problèmes de traitement en temps réel :

<footnote>[5] M. DEPEYROT. "Linear System Identification using Real-Time Deconvolution". IEEE-C-19. N° 12. pp. 1139-1145. (December 1970).</footnote>
L'exemple précédent de G(K) est poursuivi pour illustrer la démarche :
il faut représenter toutes les variables en codage primitif :

$$
z_0 = (1000), z_1 = (0100), z_2 = (0010), z_3 = (0001),
$$

$$
y_0 = (10), y_1 = (01). \quad \text{Ici } n = 4, \text{ et } p = 2.
$$

La représentation correspondante des entrées est alors une matrice
carrée n x n monomiale en ligne :

$$
v_0 = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \end{bmatrix}, \quad v_1 = \begin{bmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{bmatrix}. \quad \text{Ici } q = 2.
$$

$$
A_{\sigma} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 0 \\ 0 & 1 \end{bmatrix}
$$

puisque la réalisation considérée est du type S (état-sortie).

Pour chacune des sorties yᵢ, considérons les coétats générés par
multiplication matricielle à partir de wₖ = Aσ yᵢᵗ où yᵢᵗ est le vecteur trans-
posé de yᵢ, et construisons la table des coétats **différents** à l'aide de tous les
wⱼ = vᵢ vᵢ pour toutes les séquences possibles v = v₁ ... vᵢ ... vᵣ. Par exemple
w₅ = v₁ v₁ v₀ Aσ y₁ᵗ.

<table>
  <thead>
    <tr>
      <th>Coassignation DS</th>
      <th>w<sub>0</sub></th>
      <th>w<sub>1</sub></th>
      <th>w<sub>2</sub></th>
      <th>w<sub>3</sub></th>
      <th>w<sub>4</sub></th>
      <th>w<sub>5</sub></th>
      <th>w<sub>6</sub></th>
      <th>w<sub>7</sub></th>
      <th>&phi;</th>
      <th>z</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>z<sub>0</sub></th>
      <td>0</td>
      <td>1</td>
      <td>0</td>
      <td>0</td>
      <td>1</td>
      <td>1</td>
      <td>0</td>
      <td>1</td>
      <td>0</td>
      <td>1</td>
    </tr>
    <tr>
      <th>z<sub>1</sub></th>
      <td>1</td>
      <td>1</td>
      <td>0</td>
      <td>0</td>
      <td>1</td>
      <td>1</td>
      <td>0</td>
      <td>0</td>
      <td>0</td>
      <td>1</td>
    </tr>
    <tr>
      <th>z<sub>2</sub></th>
      <td>0</td>
      <td>0</td>
      <td>1</td>
      <td>1</td>
      <td>0</td>
      <td>1</td>
      <td>0</td>
      <td>1</td>
      <td>0</td>
      <td>1</td>
    </tr>
    <tr>
      <th>z<sub>3</sub></th>
      <td>1</td>
      <td>1</td>
      <td>0</td>
      <td>1</td>
      <td>0</td>
      <td>0</td>
      <td>1</td>
      <td>0</td>
      <td>0</td>
      <td>1</td>
    </tr>
  </tbody>
</table>
La coassignation consiste à affecter une bascule $M_j$ de type DATA synchrone à chacun des coétats $w_j$ ($d = 8$ ici).

De plus, comme $z_{\infty}=[0000]$, l'initialisation requiert une entrée $u_0$ forçant l'état $z_0$ sous la forme :

$$[w_0 = 0; w_1 = 1; w_2 = 0; w_3 = 0; w_4 = 1; w_5 = 1; w_6 = 0; w_7 = 1].$$

Appelons **table de liaison** $\lambda$ la table indiquant quelles sont les bascules $M_i$ connectées par ET logique (AND) avec quel fil d'entrée $v_k$ pour chaque bascule $M_j$ :

<table><thead><tr><th>λ</th><th>v<sub>0</sub></th><th>v<sub>1</sub></th></tr></thead><tbody><tr><td>M<sub>0</sub></td><td>M<sub>1</sub></td><td>M<sub>2</sub></td></tr><tr><td>M<sub>1</sub></td><td>M<sub>1</sub></td><td>M<sub>3</sub></td></tr><tr><td>M<sub>2</sub></td><td>M<sub>2</sub></td><td>M<sub>4</sub></td></tr><tr><td>M<sub>3</sub></td><td>M<sub>2</sub></td><td>M<sub>5</sub></td></tr><tr><td>M<sub>4</sub></td><td>M<sub>1</sub></td><td>M<sub>6</sub></td></tr><tr><td>M<sub>5</sub></td><td>Z</td><td>M<sub>1</sub></td></tr><tr><td>M<sub>6</sub></td><td>Ø</td><td>M<sub>2</sub></td></tr><tr><td>M<sub>7</sub></td><td>M<sub>2</sub></td><td>M<sub>1</sub></td></tr></tbody></table>

Par exemple :

$$\lambda(M_2, v_1) = M_4$$

parce que

$$v_1, w_2 = w_4$$

Au lieu de monostables aux niveaux logiques 1 et 0 respectivement, Z et Ø peuvent être réalisés chacun par une broche d'entrée.

Aucune sélection d'adresse n'est effectuée en entrée de la mémoire de commande Mb et plusieurs lignes y sont donc simultanément actives. Les connexions dans Mb correspondent exactement aux éléments de la table de liaison $\lambda$ (et ceux de Mc à la table de coassignation DS).

Tous les signaux de sortie possibles sont automatiquement disponibles sans logique de décodage sur une ligne émanant d'une bascule (la table de coassignation DS contient toutes les colonnes possibles pouvant servir à la définition d'une matrice d'agrégation A).
Les bascules peuvent être montées en registre à décalage si l'on ajoute une fonction de mode μ (telle que si l'entrée μ a la valeur logique 1 les fonctionnements précédents de ρ, τ et σ sont inhibés) et chaque temps d'horloge T entraîne les transferts de contenus suivants :

$$M_d \leftrightarrow u_s, M_{i-1} \leftrightarrow M_i \quad \text{pour } i = d, \dots, 2 \text{ et } y_s \leftrightarrow M_1$$

**Schéma III.** Coassignation en forme état-sortie KDS.

<figure><img src="image_4.png" /></figure>
Les sorties Y peuvent être connectées, soit sur les colonnes de Mb ("LEVEL" pris en sortie $Y_L$ des bascules) pour une réalisation de forme S, soit sur les lignes de Mb ("PULSE" pris en entrée $Y_p$ des bascules) pour une réalisation de forme T.

$$ egin{cases} 
Mc = \text{matrice de commande programmable à diodes.} \\
Mb = \text{matrice de transition programmable sans diodes.} 
\end{cases} $$

Symbolisme dans le cas d'une alimentation négative :

<figure><img src="image_5.png" /><figcaption>Schéma IV. Coassignation de l'exemple $G(K)$.</figcaption></figure>

<figure><img src="image_6.png" /></figure>

Mc est polynomiale en ligne et requiert donc une diode à chaque point programmable.

Mb est monomiale en ligne (table de liaison $\lambda$) et ne nécessite pas de diode aux points programmables.
**Note :** Le boîtier est dit polymate lorsque une matrice Mc incorporée (définitions au paragraphe 5) permet le forçage sélectif de chacun des n états de Z ou d'un certain nombre de coassignations (en nombre m).

Il est dit KDS si une bascule est associée à chacun des $d_S$ coélats et KDT si certaines bascules ne sont pas connectées en sortie (dans $Y_L$) et certaines sorties (dans $Y_P$) sont connectées sans bascules.

### 4.Coassignation en forme transition-sortie KDT.

Les matrices de transition doivent être décomposées selon que la sortie est l'un ou l'autre des $y_i$ pendant le branchement sur condition $v_j$, de sorte que $v_j = \sum_{i=1}^{P} (y_i|v_j)$. Il faut alors considérer les coélats $e_k = \bar{v}_k e_{ij}$ générés par multiplication matricielle à partie de $e_{ij} = (y_i|v_j) e_0$ où $e_0^t = (11...1)$.

Dans l'exemple précédent, cela donne :

$$v_0 = (y_0|v_0) + (y_1|v_0) \text{ avec } (y_0|v_0) = \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix} \quad \text{et} \quad (y_1|v_0) = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{bmatrix} \quad \text{et}$$

$$v_1 = (y_0|v_1) + (y_1|v_1) \text{ avec } (y_0|v_1) = \begin{bmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix} \quad \text{et} \quad (y_1|v_1) = \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix}$$

<table><thead><tr><th>Assignation DT</th><th>e<sub>0</sub></th><th>e<sub>1</sub></th><th>e<sub>2</sub></th><th>e<sub>3</sub></th><th>e<sub>4</sub></th><th>e<sub>5</sub></th></tr></thead><tbody><tr><td>z<sub>0</sub></td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td></tr><tr><td>z<sub>1</sub></td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td></tr><tr><td>z<sub>2</sub></td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>z<sub>3</sub></td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td></tr></tbody></table>
Soient $n_S$ et $n_T$ les nombres d'états du microalgorithme K en formes état-sortie et transition-sortie respectivement :

$$n_T \le n_S \le n_T \quad \text{x p où p est le nombre de microordres.}$$

$$\text{Ici } n_S = 4 \text{ et } n_T = 3.$$

Soient $d_S$ et $d_T$ les nombres de coétats correspondants :

$$n_T \le d_T \le d_S. \text{ Ici } d_S = 8 \text{ et } d_T = 4.$$

La forme KDT offre le double avantage sur la forme KDS d'être donc plus compacte mais aussi plus rapide à cause du type de logique de sortie ("PULSE" sur $Y_p$) employé. Elle permet aussi de ne pas implémenter une bascule sans successeur, c'est-à-dire pour une sortie $y_i$ dont le coût $e_{ij}$ est tel qu'il n'existe pas de condition v telle que $e_{ij} = ve_k$ pour un autre coût $e_k$.

## 5. Propriétés et comparaisons des modules KD.

Le forçage d'un état peut être sériel seulement et noté KDS (par connexion des bascules en registre à décalage) ou aussi parallèle et noté KDsp (par réemploi des entrées de transition parallèle intersectées par l'entrée de rythme p ajoutée aux conditions de branchement dans V).

Par comparaison, on observe : qu'une réalisation de Mb par PROM(1) porterait à $2^{q+d}$ le nombre de lignes égal ici à qxd avec $d=d_S$ ou $d_T$,

- qu'une réalisation par PLA(2) gâcherait $qxdxd$ diodes là où il suffit d'autant d'interconnexions avec $d = d_S$ ou $d_T$,

- que la technique de WEINER et HOPCROFT donnée en référence 3 au paragraphe 1 ne permet, ni le traitement de plus de deux sorties (alors qu'ici $p_2=2$), ni la forme transition-sortie,

- qu'une réalisation par AROM(3) n'exploiterait pas la simplicité de la logique (ici en forme normale disjonctive avec entrance 2 par porte ET), ni de la géométrie (croisement orthogonal des lignes de coétats et des colonnes de conditions).

<footnote>(1,2,3) : abréviations explicitées à la fin du paragraphe.</footnote>
Conformément au schéma III, il faut remarquer que :

- le découpage d'un boitier PLA aurait (3d + q + 3) broches logiques avec $d = d_S$ ou $d_T$,

- le boitier KDSs aurait ($d_S + q + 6$) broches et le boitier KDSsp en aurait ($2d_S + q + 7$),

- le polymate KDSsp aurait ($m + d_S + q + 7$) broches logiques avec $m \le d_S$.

- le boitier KDTs aurait ($p + q + 6$) broches et le boitier KDTsp en aurait ($d + p + q + 7$) avec $d \le d_T$.

- le polymate KDTsp aurait ($m + p + q + 7$) broches logiques avec $m \le d_T$.

(1) PROM : Programmable Read-Only Memory.

(2) PLA : Programmable Logic Array.

(3) AROM : Associative Read-only Memory.

## 6. Description d'une réalisation KDSs ($q = 14$; $d_S = 24$).

Le nombre de broches logiques est $d_S + q + 6 = 44$. Il faut aussi ajouter trois broches technologiques GND (ground), CFF (clear flipflops) et VCC (supply voltage) et une broche NC (non connectée), ce qui porte le total du nombre de broches à :

$$44 + 1 + 3 = 48.$$

Le boitier est un parallélépipède rectangle symétrique plat avec ("Flat Package") les dimensions suivantes :

### Schéma V.

<figure><img src="image_7.png" /></figure>
Chaque longueur porte 16 broches et chaque largeur en porte 8,
réparties comme suit :

- une longueur et une largeur adjacentes portent les sorties $Y_L$ des bascules M,

- l'autre longueur porte les 14 entrées de conditions V et les deux broches de signaux logiques 1 et 0 (respectivement Z et Ø).

- l'autre largeur porte les entrées de contrôle (horloge T, mode µ), les connexions sérielles ($u_s$ et $y_s$), la broche libre (NC), les broches technologiques (GND, CFF et VCC).

### Schéma VI.

<figure><img src="image_8.png" /></figure>

Boitier plat ("Flat Package").

La logique interne au boitier est faite d'une superposition de couches semiconductrices CMOS dessinées par masquage et où l'un des masques permet d'effectuer la "programmation" des matrices Mc et Mb.

## 7. Présentation détaillée des avantages pratiques.

### 7.1. Avantages en Technologie de circuits à haut degré d'intégration.

Le dessin des composants et de leurs interconnexions est itératif (un motif par coûtat $M_i$) ce qui facilite l'emploi des techniques de masquage les plus économiques pour dépôt des couches isolantes, semi-conductrices et conductrices.

Ceci est vrai pour tout choix des valeurs des paramètres ($m,n,p,q,d$) et des formes ($S,T$, polymate, etc.) et pour toute technologie.

D'ailleurs le schéma suivant VII montre que cette régularité permet d'extraire d'autres motifs permettant de découper de manière différente mais aussi fructueuse en boitiers à degré d'intégration moyen ou élevé.
Schéma VII. Exemple d'un autre découpage en motif régulier.

<figure><img src="image_9.png" /></figure>

Ici la sortie de la bascule $M_i$ est ramenée sur la matrice $Mb$ de manière interne au boitier ce qui permet de connecter les divers motifs de manière simple et itérative sur une carte à circuits imprimés.

### 7.2. Avantages pour la mise en boitiers.

Le rapport du nombre de portes logiques au nombre de broches d'entrée et sortie du boitier est maximal pour le boitier KDTs mais demeure intéressant pour tous les autres découpages en boitiers. En effet l'impact essentiel de la coassignation est de simplifier les fonctions de transition $t$ et de sortie $\sigma$ par rapport à toute autre forme canonique. En particulier, il faut remarquer que les coétats représentent des fonctions complexes sur les sorties de $Y$ nécessaires : la connexion des bascules $M_i$ en sortie met donc à la disposition du logicien des micro-ordres complexes à peu de frais.

Le lecteur intéressé par l'étude des problèmes de test des composants de calculateur en production et en maintenance peut consulter le rapport de référence [6].

<footnote>[6] M. DEPEYROT. "Computer component and System Testing, a part of Computer-aided manufacturing and maintenance". LABORIA. Rapport de Recherche. à paraître (Octobre 1974).</footnote>
### 7.3. Avantages en fabrication.

Alors qu'une réalisation microprogrammée (schéma I) par PLA, PROM ou AROM requiert un boitier sans défaut en sortie de fabrication, l'absence d'un circuit de sélection d'adresse sur la matrice Mb permet de tolérer la présence de lignes (ou bascules) et colonnes (ou entrées et sorties) défectueuses. Il suffit en effet d'implanter les coétats et les signaux d'interface sur respectivement des lignes et des colonnes non défectueuses.

D'ailleurs la simplicité fonctionnelle de la matrice Mb (absence de diodes aux interconnexions) rend plus fiables sa fabrication et sa programmation.

### 7.4. Simplicité des tests de recette.

D'une part les bascules $M_i$ sont complètement observables et contrôlables (par $y_s$ et $u_s$ respectivement) et immédiatement observables (par $Y$), d'autre part les fonctions en entrée parallèle de chacune étant en forme canonique disjonctive, un programme de test comporterait essentiellement une boucle de test paramétrée par la table de liaison $\lambda$.

De plus il est possible de compléter le schéma des modules en permettant le décalage des bascules dans les deux sens (par adjonction d'une commande de mode $\mu'$ et de $u'_s$ et $y'_s$).

Dans tous les cas le diagnostic obtenu est très complet puisqu'il permet la localisation d'avarie avec précision.

### 7.5. Simplicité fonctionnelle.

Le rapport du nombre de diodes au nombre de bascules, très élevé en microprogrammation (nous entendons par "diode" la fonction logique, même si un transistor est employé pour implémenter un point-mémoire de commande), est considérablement réduit ici puisque le schéma III en fait apparaître $m \times d$ dans $Mc$ et $3(q+1) \times d$ en sortie de $Mb$ (à comparer à $(p + \log_2 n) \times n$ en microprogrammation, non compris le décodeur de $\log_2 n$ à $n$).

En outre le schéma suivant VIII montre qu'il peut être amené à $3(q+m) \times d$ dans $Md$ s'il est intéressant d'éliminer toute diode des points programmables (dans $Mp$).

Surtout tous les micro-ordres possibles dans $Y$ sur un espace d'état donné $Z$ sont directement accessibles sans logique de sortie.
Schéma VIII. Elimination des diodes programmables pour le forçage
des états.

a. Motif extrait du schéma III.

<figure><img src="image_10.png" /></figure>

b. Motif équivalent sans Mc.

<figure><img src="image_11.png" /></figure>
### 7.6. Absence de décodage d'adresse.

Le coût lié à l'accroissement du nombre de bascules en passant d'une assignation compacte ($\log_2 n$ bits pour $n$ états) ou primitive ($n$ bits pour $n$ états) à la coassignation (entre $n$ et $2^n$ bits) est compensé par la réduction en coût et l'accélération du fonctionnement liées à l'élimination de tout décodage pour sélection d'adresse en $Mb$ (comparer à la logique PLA, PROM ou AROM).

### 7.6. Variance du temps de traversée de couches pendant les transitions d'état.

La structure à entrance fixe $q+1$ (ou $q+m$ dans le schéma VIII) en forme canonique disjonctive garantit que pour tout état (ou coétat) et toute entrée $V$ ou $U$, le nombre de couches logiques à traverser pour positionner les bascules de l'état suivant est identique. La variance étant seulement liée aux différences de longueur des interconnexions et aux irrégularités entre composants, il est possible d'ajuster au plus près la période d'horloge $T$ à la valeur du temps de cycle minimal dans le module KD.

### 7.8. Parallélisme de déroulement.

Une autre conséquence de l'absence de sélection d'adresse en entrée de $Mb$ ou $Mp$ est la possibilité d'exécution simultanée de plusieurs micro-algorithmes synchrones sur un seul boitier. Ces microalgorithmes se partagent alors de manière exclusive le registre des bascules $M_i$ mais peuvent avoir en commun, soit des entrées $U$, soit des entrées $V$, soit partie des deux.

Ces microalgorithmes peuvent d'ailleurs être activés et exécutés soit de manière simultanée soit successivement, et dans ce cas il se peut que l'un soit appelé par l'autre, ce qui permet la décomposition en sous-algorithmes ou en coroutines.

### 7.9. Avantages pour la maintenabilité.

Les tests de recette (§.7.4) peuvent être réutilisés en maintenance ce qui favorise la détection d'avarie et sa localisation au boitier près. Mais encore, la disponibilité automatique d'un état de repos stable ($z_\infty$ à coassignation 00...0) garantit l'arrêt absolu du fonctionnement parallèle du boitier. Cet état peut être atteint par une entrée $u_\infty$, mais aussi par la broche technologique CFF (clear flipflops).
## 7.10. Réduction du nombre de broches de sortie ou d'entrée.

Plutôt que d'avoir $d$ (ou $p$) broches de sortie d'un module KD (en codage primitif) il est parfois intéressant de réduire par un code analytique leur nombre à $c$ dont la valeur est comprise à volonté entre $c_{min}$ et $d$ où $[\log_2 d] \le c_{min} \le [\log_2 d]+1$.

<figure><img src="image_12.png" /><figcaption>**Schéma IX.** Codage interne des signaux de sortie.</figcaption></figure>

La matrice d'action $Ma$ est une matrice à diodes dont les points connectés correspondent aux 1 de la table de codage adoptée. Ce dispositif est applicable aussi bien aux entrées V où une matrice $Me$ programmable (PROM) permet d'utiliser un codage adapté à la structure interne (par exemple, compatible avec le découpage des coétats pour le parallélisme de déroulement).

## 8. Principes d'Exploitation.

La sémantique de la coassignation étant moins intuitive que la micro-programmation et son efficacité étant liée à la réduction du nombre de bascules requis par un microalgorithme donné, un certain nombre de programmes d'implantation automatique seraient utiles pour accélérer la coassignation en conception et en développement.
Par exemple, un programme de minimisation du nombre q des entrées V dans le cas d'un microalgorithme incomplètement spécifié [7], ainsi qu'un programme de minimisation du nombre d'états. Ensuite, un programme devrait effectuer le calcul de la table de coassignation et définir les masques correspondants pour l'implémentation du boitier KD. De plus, un programme de décomposition d'un microalgorithme en sous-algorithmes favoriserait la modularisation et la réduction du nombre de coétats, donc du nombre de bascules.

Brevet déposé par la COMPAGNIE INTERNATIONALE
POUR L'INFORMATIQUE le 21 Mars 1974.

<footnote>[7] G. MICHEL, "Minimisation des Machines Séquentielles incomplètement spécifiées".
LABORIA. Rapport de Recherche n° 70. (Mai 1974).</footnote>