ChapII bascules et

  • Published on
    05-Jan-2017

  • View
    214

  • Download
    2

Transcript

  • - II.1 -

    CHAPITRE II :

    CIRCUITS SEQUENTIELS ET SYNTHESE D'AUTOMATES

    INTRODUCTION

    Un circuit squentiel est un circuit dont la sortie dpend de la squence d'entres appliquesdepuis la mise en route du circuit : ce circuit mmorise une information. La valeur del'information mmorise forme l'tat du circuit ; le support de cette information est lesvariables d'tats. Ces variables tant binaires, un circuit squentiel n variables d'tat peutprendre 2n tats.

    Nous n'tudierons ici que les circuits squentiels synchrones : les changements de valeur dechacune des variables d'tat sont synchroniss par un signal ; quand ce signal n'est pas actif,l'tat ne peut pas tre modifi.

    Aprs avoir prsent l'lment de base des circuits squentiels : les bascules, et leur utilisationpour raliser des registres (1), le modle d'automate synchrone sera prsent (2), ainsi queles mthodes de synthse d'automates (3).

    1. CIRCUITS SEQUENTIELS DE BASE : BASCULES ET REGISTRES

    1.1. DEFINITION

    Une bascule est un circuit squentiel lmentaire, capable de mmoriser une variable d'tat et

  • - II.2 -

    donc qui peut prendre 2 tats (tat 0 et tat 1). Il existe diffrents types de bascules, quipeuvent tre classs par :

    - leurs entres de valeur,- l'interprtation de leur(s) entre(s) d'activation,- les entres d'initialisation dont elles disposent.

    1.2. BASCULE D

    Une bascule D (pour Delay) synchrone est un circuit 2 tats, qui a une entre de valeur D,une entre d'activation Act, et 2 sorties y (tat de la bascule) et .

    La figure II-1 dfinit les entres et sorties d'une bascule D, ainsi que son tableau defonctionnement.

    D

    Act

    y

    y

    a) schma symbolique d'une bascule D

    y t : valeur courante de l'tat y t+? t : valeur suivante de l'tat

    Act D yt+? t non * y t oui 0 0 oui 1 1

    b) fonctionnement

    Figure II-1 : bascule D

    Tant qu'il n'y a pas activation de la bascule (Act : non), la bascule garde son tat antrieur,quelle que soit la valeur de l'entre D. Quand la bascule est active (Act : oui), l'tat de labascule prend la valeur de l'entre D : une bascule D permet de mmoriser une valeur entredeux activations.

    La bascule D est la plus utilise, en particulier pour raliser des registres, mais il existe d'autresbascules avec des entres de valeurs diffrentes.

    1.3. BASCULES JK, RS, ...

    Les bascules JK, RS et T sont dfinies ci-dessous (figures II-2 II-4).

  • - II.3 -

    Act

    y

    y

    a) schma symbolique d'une bascule RS

    Act R S y t+? t non * * y t oui 0 0 y t oui 0 1 1 oui 1 0 0 oui 1 1 ???

    b) fonctionnement

    R S

    Figure II 2 : bascule RS

    Act

    y

    y

    a) schma symbolique d'une bascule JK

    Act J K y t+?t non * * y t oui 0 0 y t oui 0 1 0 oui 1 0 1 oui 1 1 y t

    b) fonctionnement

    J K

    Figure II-3 : bascule JK

    T

    Act

    y

    y

    a) schma symbolique d'une bascule T

    Act T y t+?t non * y t oui 0 yt oui 1 yt

    b) fonctionnement

    Figure II-4 : bascule T

    Une bascule D peut tre ralise partir d'une bascule RS (avec S = D et R complmentaire)ou d'une bascule JK (avec J = D et K complmentaire). Une bascule T peut tre ralise partir d'une bascule JK (avec J et K = T).

    1.4. FONCTIONS D'ACTIVATIONS DES BASCULES

    On distingue trois types de bascules d'aprs la fonction d'activation (l'interprtation de l'entreAct).

  • - II.4 -

    1.4.A. BASCULES DE TYPE VERROU (LATCH)

    Il s'agit de bascules sensibles la valeur de l'entre Act :

    - verrou sensible au niveau haut : la bascule est active ds que (et tant que) Act = 1,- verrou sensible au niveau bas : la bascule est active ds que (et tant que) Act = 0,ce qui veut dire que quand la bascule est active, son tat est gal la valeur de l'entre D : unverrou est "transparent" quand il est activ.

    Le fonctionnement temporel d'un verrou D sensible au niveau haut est indiqu l'aide d'unchronogramme donn dans la figure II-5 : la figure II-5 a) illustre le fonctionnement de typeverrou, tandis que la figure II-5 b) met en vidence les retards associs au fonctionnement (enfait, c'est plus complexe : les retards sont diffrents suivant que l'tat passe de 0 1 ou de 1 0 ; de plus, les retards sont diffrents pour la sortie y et la sortie .

    Act

    D

    y ?

    a) verrou sensible au niveau haut

    ?? ??? t2? t1

    Act

    D

    y

    b) retards de positionnement de y par rapport Act ( ? t1) et D (? t2)

    Figure II-5 : fonctionnement temporel d'un verrou D

    Si l'entre D change "au moment o" l'entre d'activation Act passe de 1 0 (pour un verrousensible au niveau haut), l'tat de la bascule aprs la fin de l'activation est indtermin : on nesait pas si la nouvelle valeur de l'entre a t mmorise ou non. Des intervalles de temps t1(temps de positionnement, tset-up) et t2 (temps de maintien, thold) dfinissent l'intervalle de

    temps o D doit tre stable autour du passge de Act de 1 0.

    1.4.B. BASCULES SENSIBLES AU FRONT (EDGE-TRIGGERED FLIP-FLOPS)

    Il s'agit de bascules sensibles aux changements de valeurs de l'entre d'activation Act :

    - bascule sensible au front montant : la bascule est active quand Act passe de 0 1,- bascule sensible au front descendant : la bascule est active quand Act passe de 1 0,ce qui veut dire qu'une telle bascule ne peut changer d'tat qu' des instants bien prcis : la(les) entre(s) de valeur sont chantillonnes aux fronts de l'entre d'activation.

  • - II.5 -

    Act

    D

    y ???? t

    Act

    D

    y

    a) bascule sensible au front montant

    ? ?t1 t2

    b) l'entre D doit tre stable autour du front montant de Act

    Figure II-6 : fonctionnement temporel d'une bascule D sensible au front

    La figure II-6 illustre le fonctionnement temporel d'une bascule D sensible au front montant : ilfaut que D soit stable t1 avant le front de Act (temps de positionnement, set-up time) et t2aprs le front (temps de maintien, hold-time). La sortie varie t aprs le front de l'horloge. Anoter : ce retard est diffrent suivant le sens de variation ; passage de 0 1 : tpLH, passage de1 0 : tpHL.

    Au lieu d'utiliser la notation "tat t+t", on peut se contenter de dfinir le fonctionnementd'une bascule sensible au front en termes de l'tat t + 1 en fonction de l'tat et des entres t, car les fronts d'activation des bascules permettent une discrtisation du temps.

    1.4.C. UTILISATION DES DIFFERENTS TYPES DE BASCULESSupposons qu'on veuille concevoir un circuit 2 tats, qui complmente son tat chaqueactivation (squence d'tats 0101010.....). Il semble logique d'utiliser le montage de la figureII-7 :

  • - II.6 -

    D y

    Act

    a) montage propos

    Act

    D

    y

    ? ? ? ? ?

    ? ? ? ? ?

    b) utilisation d'un verrou

    Act

    D

    y

    ???t ?

    c) utilisation d'une bascule sensible au front

    Figure II-7 : utilisation des bascules

    Si la bascule utilise dans le montage de la figure II-7 a) est de type verrou, le fonctionnementn'est pas correct (Fig.II-7 b)) : ds que la bascule est active, l'tat y est complment ;l'entre D est complmente en consquence. Comme le verrou est toujours activ, son tatse complmente ..... On obtient bien en sortie la squence 010101..., mais les changementsde valeurs ne sont pas synchroniss par l'entre d'activation, et quand Act passe 0, l'tat dela bascule est indtermin.

    Note : un verrou D toujours activ, reboucl suivant le schma de la figure II-7-a avec unechane de 1 ou 2p +1 inverseurs permet de gnrer un signal d'horloge dont la priodedpend du nombre et du retard des inverseurs utiliss. Mais il ne s'agit pas s d'un circuitsquentiel synchrone : le changement d'tat n'est pas synchronis par un signal (Act toujoursvrai).

    Quand on utilise une bascule sensible au front, le fonctionnement est correct (Fig. II-7 c)), condition que l'entre reste stable autour du front de Act, c'est--dire que :

    t + > t2,

    o t est le temps de positionnement de y aprs le front d'activation, est le retard del'inverseur et t2 est le temps de stabilit ncessaire de D aprs le front (hold time).

    Pour que le fonctionnement soit correct, on obtient la condition suivante:

  • - II.7 -

    Min ( tpLH, tpHL.) + > thold.

    En gnral, les bascules sont conues de faon ce que Min ( tpLH, tpHL.) > thold, donc cette

    relation est toujours vrifie.

    De mme, l'entre d'activation Act doit respecter la contrainte suivante :

    T > t + + t1 , o T est le temps entre 2 fronts de Act et t1 le temps minimal destabilit de D avant le front d'activation (set-up time)

    ce qui fixe une frquence maximale pour Act. Par exemple, si = 0 (cas des registres dcalage, voir plus loin), on obtient :

    T > tsetup + Max( tpLH, tpHL.)

    Pour les circuits TTL utiliss en travaux pratiques (les temps caractristiques se comptent ennano-secondes), on obtient des frquences maximales entre 16MHz (7474) et 75 MHz(74AS74). Pour les technologies actuelles, o les temps se comptent en pico-secondes, onobtient des frquences maximales de l'ordre du GHz.

    1.4.D. BASCULES DE TYPE MAITRE-ESCLAVE (MASTER-SLAVE FLIP-FLOPS)

    Pour raliser le type de montage de la figure II-7, on peut aussi utiliser 2 bascules de typeverrou au lieu d'une bascule sensible au front : on connecte ces 2 verrous en srie, en lesactivant alternativement. On obtient une bascule de type matre-esclave (Figure II-8).

    E1

    E2

    D

    y M

    y

    DM y M

    E1

    Act

    DDE y E

    E2

    Act

    y

    a) bascule matre - esclave b) fonctionnement temporel

    Figure II-8 : bascule matre-esclave

    Quand E1 vaut 1, la valeur de l'entre D (connecte DM) est recopie dans le premier

    verrou ; quand E1 passe 0, la dernire valeur de D est mmorise. Ds que E2 passe 1,cette valeur est recopie dans le deuxime verrou et affiche sur la sortie y, o elle sera stablejusqu' la prochaine activation. Le premier verrou est appel verrou matre, et le deuxime,verrou esclave.

  • - II.8 -

    Quand E2 = , cette bascule se comporte comme une bascule sensible au front descendant deE1. La bascule ne se comporte correctement que si on a toujours E1 . E2 = 0 (non-recouvrement des activations).

    Attention, les bascules JK ou RS matre-esclave ne fonctionnent pas comme des bascules JKou RS sensibles au front : toutes les variations des entres J,K ou R,S durant le niveaud'activation de l'tage matre sont prises en compte, et le rsultat est recopi dans l'tageesclave quand il est activ. En gnral, il faut assurer que les entres de l'tage matre sontstables durant toute l'activation de cet tage.

    1.4.E. BASCULES AVEC PLUSIEURS ENTREES D'ACTIVATION

    Certaines bascules (en particulier les bascules sensibles au front) ont plusieurs entresd'activation :

    - une entre d'horloge, note H ou CK (clock), qui fournit le front d'activation,- une entre d'autorisation, note En (enable), qui autorise l'activation.Le tableau ci-dessous prcise la prise en compte de ces entres pour l'activation d'unebascule sensible au front montant :

    En CK Activation

    0 * non

    1 $,0,1 non

    1 # oui

    Pour une bascule qui ne doit pas voluer chaque priode d'horloge, cela permet deconnecter directement l'entre d'horloge de la bascule l'horloge du systme, et donc d'avoirun signal pas trop dgrad et sans alas, et d'utiliser l'entre En pour autoriser ou nonl'volution (la fonction d'autorisation peut tre une fonction boolenne complexe).

    Pour une bascule qui doit voluer chaque priode d'horloge, l'entre En est inutile : il suffitde connecter l'horloge du systme sur l'unique entre d'activation de la bascule ... cette entred'ailleurs est souvent appele entre d'horloge H ou CK dans les documentations.

    1.5. ENTREES D'INITIALISATION DES BASCULES

    Outre les entres de donnes et d'activation, les bascules ont des entres d'initialisation 0 et /ou 1 : ces entres sont prises en compte indpendamment de l'entre d'activation, et servent imposer une valeur initiale dans les bascules la mise sous tension du circuit (Fig.II-9)

  • - II.9 -

    D

    C Py

    y

    Act

    C P Act D y 1 0 * * 0 0 1 * * 1 1 1 * * ? 0 0 non * y 0 0 oui 0 0 0 0 oui 1 1

    t+1

    t

    Figure II-9 : entres d'initialisation

    L'entre C (Clear) force un tat 0, l'entre P (Preset) force un tat 1.

    Ces entres permettent une initialisation asynchrone de l'tat. On peut aussi assurer uneinitialisation synchrone (pour initialiser 0, D = init - - 0 . tat suivant , pour initialiser 1,D = init--1 . tat suivant).

    1.6. BASCULES EN TECHNOLOGIE MOS

    1.6.A. BASCULES DYNAMIQUES

    Nous avons vu au chapitre I (3.1.) que des capacits ralisent, en technologie MOS, unemmorisation rudimentaire : ce mcanisme peut tre utilis pour raliser un verrou (Fig. II-10)

    D

    Act

    y

    Figure II-10 : point de mmorisation dynamique en technologie nMOS

    Quand Act est 1, la capacit associe la grille du transistor de l'inverseur se charge si Dest 1, se dcharge si D est 0 ; quand Act passe 0, l'entre de l'inverseur n'est pasconnecte et donc la dernire valeur de D est mmorise (fonctionnement de type verrou).Cependant, la capacit va se dcharger lentement, et une valeur mmorise 1 va disparatreau bout d'un certain temps : ce verrou n'est utilisable que quand il est activ rgulirement. Onparle d'un point de mmorisation dynamique.

    A l'aide de deux verroux de ce type, activ l'un par Act, l'autre par son complmentaire, il estpossible de raliser une bascule matre-esclave, qui elle aussi est dynamique.

  • - II.10 -

    1.6.B. BASCULES STATIQUES

    Pour obtenir un verrou capable de mmoriser indfiniment une information (tant que le circuitst aliment), la valeur de l'tat est reboucle en entre quand Act= 0 (Fig. II-11).

    y1 0

    D

    Act

    y

    Figure II-11 : verrou statique

    Un multiplexeur slectionne soit l'entre D, soit l'tat courant yt, d'aprs la valeur de Act (ce

    multiplexeur est en gnral ralis par un rseau de transistors MOS (cf Fig.I-19)).

    En utilisant 2 verrous activations complmentaires, on peut raliser une bascule matre-esclave statique.

  • - II.11 -

    3. REGISTRES ET MMOIRES

    3.1. REGISTRE N BITS

    Pour mmoriser un ensemble de n bits an-1, an-2, .., a0, ou mot de n bits, on utilise n bascules qui

    sont actives en mme temps, donc par le mme signal (Fig.III-20).

    a a a

    y y y

    n-1 n-2

    0n-1 n-2

    0

    E R

    A

    Y

    n

    n

    ERregistre R

    a) connexion des bascules b) schma d'un registre

    Figure III-20 : registre n bits

    Le type de bascules utilis est choisi d'aprs l'utilisation du registre. On utilise souvent desbascules deux entres d'activation (horloge et autorisation) : l'horloge du systme estconnecte l'entre d'horloge des bascules, le signal ER est connect l'entre d'autorisation.

    3.2. UTILISATION DES REGISTRES EN ENTREE ET SORTIE D'UN CIRCUIT COMBINATOIRE

    L'utilisation de registres permet d'chantillonner les sorties d'un circuit combinatoirelorsqu'elles sont valides, et de lui fournir des valeurs stables en entre (Fig.III-21)

    CR1 R2

    ER1 ER2

    Figure III-21 : registres d'entre et de sortie d'un circuit combinatoire

    L'intervalle de temps sparant le chargement de R1 (commande ER1), qui fournit de nouvellesvaleurs en entre du circuit combinatoire, et le chargement de R2 (commande ER2) ne doit pastre infrieur au temps de retard maximal du circuit C, ceci pour charger un rsultat valide dansR2 (il faut aussi tenir compte des temps de positionnement et de maintien des bascules).

    La prsence d'un registre en entre d'un circuit combinatoire permet de disposer des variables

  • - II.12 -

    sous les deux formes, normale et complmente, car chaque bascule du registre affiche ensortie ces deux formes.

    3.3.REGISTRES DECALAGE

    Si on veut dcaler gauche ou droite les bits d'information mmoriss dans un registre, ilfaut le munir de la capacit de dcalage. Un circuit registre qui a deux fonctionnalits :

    - dcalage droite (si decal = 1 et ER activ),- chargement parallle (si dcal = 0 et ER activ)

    est donn figure III-22.

    En entre de chaque bascule, un multiplexeur command par le signal "decal" permet deslectionner soit la valeur du bit de gauche, soit la valeur d'entre. Dans tous les cas, il fautactiver le signal ER pour charger le registre.

    1 0 1 01 0decal

    ER

    a a a n-1 n-2 0

    A

    Y

    n

    n

    ERregistre R

    b) schma d'un registre dcalage

    y y y 0n-1 n-2

    e

    e

    decal

    a) conception d'un registre dcalage

    Figure III-22 : registre dcalage droite

    Ce type de registre ne peut pas tre ralis avec des verrous : il y aurait un nombreindtermin de dcalages durant le niveau actif de ER.

    Il existe de nombreux types de registres dcalage :

    - entre parallle, sortie parallle plus dcalage d'une position droite (celui de la figure III-22),

    - entre parallle, sortie parallle plus dcalage d'une position gauche,- entre parallle, sortie parallle plus dcalage gauche ou droite,- entre srie, sortie srie et dcalage droite (entre srie : cf entre e de la figure II-14,

    sortie srie : y0, un seul signal de commande),

    - etc.

  • - II.13 -

    Exercices

    III-16Proposer un circuit registre dcalage entre srie, sortie srie et dcalage gauche ou droite d'une position ( 2 signaux de commandes : chargement du registre ER, / decald.

    III-17Une pile de dimension k est un circuit qui permet de mmoriser k mots de b bits, et deles relire dans l'ordre inverse de celui de leur arrive (dernier entr, premier sorti, ou Last In,First Out : LIFO). Ecrire un mot dans la pile est appel "empiler" ou push, lire un mot dans lapile est appel "dpiler" ou pull (pop).

    Proposer une ralisation d'une pile de 4 mots de 2 bits, l'aide de registres dcalage tel quecelui ralis dans l'exercice III-16. Les entres et sorties du circuit sont indiques figure III-23a).

    push

    pull

    entres sorties

    bb

    PILE k mots de b bits

    push

    pull

    entres sorties

    bb

    PILE k mots de b bits

    pleine

    vide

    a) circuit pile b) pile avec indicateurs de l'tat de la pile

    Figure III-23 : entres / sorties d'un circuit pile

    III-18Il est intressant de connatre l'tat de la pile : pile pleine (donc on ne peut plus faired'opration Push), pile vide (donc qui ne contient plus d'informations). Complter le schmaprcdent pour gnrer ces indicateurs. La solution la plus simple consiste prvoir un bitsupplmentaire dans chaque mot de la pile : V, indicateur de validit. Si V = 1, le mot associest valide, sinon le mot est invalide (ne fait pas partie de l'ensemble des informations stockesactuellement dans la pile).

    3. 4. REGISTRES COMPTEURS

    Si on veut pouvoir incrmenter et / ou dcrmenter l'information contenue dans un registrefacilement, il est possible de le connecter un circuit d'incrmentation et/ou de dcrmentation

  • - II.14 -

    pour obtenir un registre compteur/ dcompteur. La figure III-24 donne le schma d'un registrecompteur entre parallle, sortie parallle.

    n

    n

    registre compteur

    A

    Y

    ch R

    incr R

    max

    la sortie max est gale 1 quand le registre a la valeur 2 -1 n

    n bits : comptage modulo 2 nraz R

    t+1

    tt

    Hincr R ch R Y 1 * Y plus 1 0 0 Y 0 1 A

    Figure III-24 : registre compteur

    Ce compteur modulo 2n est activ chaque priode de l'horloge H. Il peut tre forc 0 parla commande raz R (asynchrone), ou la valeur d'entre A par la commande de chargementch R (prise en compte l'activation par H). La commande d'incrmentation incr R estprioritaire sur la commande de chargement. La sortie max est 1 quand le compteur atteint savaleur maximale 2n 1 (dans certains compteurs, la sortie max est 1 quand le compteurpasse de sa valeur maximale 0). La sortie max permet de cascader des compteurs, parexemple pour construire un compteur modulo 22n partir de deux compteurs 2n .

    Il existe de nombreux types de compteurs, avec ou sans entres et / ou sorties parallles, quieffectuent l'incrmentation et la dcrmentation ou seulement une des oprations.

    Exercices

    III-19Proposer une ralisation du registre compteur de la figure III-24 l'aide d'un registre nbits, d'un incrmenteur n bits et de n multiplexeurs 2 -> 1.

    III-20Proposer une ralisation d'un registre compteur / dcompteur l'aide d'un circuitincmenteur / dcrmenteur.

    3.5. INTERCONNEXION ENTRE REGISTRES : BUS ET PORTES 3-ETATS

    Supposons qu'on conoive un circuit comportant un ensemble de registres et qu'il soitncessaire de pouvoir transfrer les valeurs des registres de l'un l'autre (Fig.III-25 a). Il estpossible de crer cette interconnexion l'aide de multiplexeurs (Fig.III-25 b), mais cettesolution est trs coteuse en fils de connexion. En gnral, si il n'y a pas de ncessit detransferts en parallle, un bus (moyen de transport en commun) est utilis : il s'agit d'un fil deconnexion par bit, auquel les bascules de mme rang des diffrents registres sont connectes

  • - II.15 -

    travers des interrupteurs (Fig III-25 c). Les commandes de ces interrupteurs et celles dechargement des registres permettent de commander les transferts de registre registre(Fig.III-25 d).

    A B

    C D

    a) interconnexions raliser

    ai bi ci di

    0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3

    D D D D

    cA cB cC cD

    EA EB EC ED

    b) connexions par multiplexeurs pour les bits de rang i

    aiD

    biD

    ciD

    diD

    EA EB EC ED

    SA SB SC SD

    fil i du bus

    c) connexion par bus pour les bits de rang i

    EA

    ED

    EB

    EC

    A B

    C D

    SA SB

    SC SD

    transfert de B dans D : SB = 1 et ED = 1 d) schma global

    bus

    Figure III-25 : interconnexion par bus

    Attention, on ne peut transfrer la valeur que d'un registre un instant donn (ce moyen detransport en commun est plus un taxi vhicule partag dans le temps, avec un seul utilisateur la fois qu'un bus !). Pour assurer qu'au plus un regsitre est connect en sortie au bus uninstant donn, il est prudent de gnrer les signaux SA,SB,SC et SD l'aide d'un dcodeur oudmultiplexeur.

    Les interrupteurs peuvent tre raliss par des transistors, en technologie MOS. On appellede tels interrupteurs "portes 3-tats" (tri-state drivers) : leur sortie peut prendre la valeur 0 oula valeur 1 lorsque l'interrupteur est ferm, et prend une 3me valeur, haute impdance, noteZ, lorsque l'interrupteur est ouvert.

    3.6. MMOIRES VIVES

    Une mmoire vive est une mmoire dans laquelle on peut lire et crire : Read/Write Memoryou RWM (par opposition aux ROM, Read Only Memory, vues chapitre III, 2).Une

  • - II.16 -

    mmoire vive de 2n mots de b bits permet de mmoriser 2n informations de b bits, qui sontrepres par un numro cod sur n bits (Fig.III-26 a). Ce numro de mot est appel adressedu mot.

    Une telle mmoire peut tre ralise l'aide de (cf Fig.III-26 b) :- un dcodeur n -> 2n, qui active un signal de slection de mot d'aprs le numro mis en

    entre (cf chapitre III,1),- 2n registres de b bits, qui mmorisent les mots.

    mot 0mot 1mot 2

    mot 2mot 2 n-1

    n-2

    numro

    sortie mot entre mot

    n

    b b

    select L / E

    select L / E action 0 * 1 0 lecture 1 1 criture

    a) schma d'une mmoire et tableau de fonctionnement

    select

    0 1 2 . . . . . 2

    n-1

    numro

    select i

    criture lecture

    ligne d'entre ligne de sortie

    D y

    select 0

    select 1

    select 2

    select 2n-1

    mot 0

    mot 2

    mot 2

    mot 1

    n-1

    b) slection des mots d'une mmoire par un dcodeur

    c) point de mmorisation

    Figure III-26 : mmoire vive

    Une telle mmoire est appele mmoire accs alatoire (parce que le temps d'accs est lemme, quel que soit le mot accd) ou Random Access Memory (RAM). Notez qu'il y a

  • - II.17 -

    souvent une confusion entre les modes d'accs possibles et le type d'accs qui mne opposer RAM et ROM, alors qu'une ROM est en fait une RAM.

    Un point de mmorisation en technologie MOS est propos figure III-26 c) : il s'agit d'uneralisation nave, non optimale. On utilise un verrou, toujours activ :

    - quand la commande de lecture est 1 et que le mot est slectionn (select i = 1), l'tat duverrou est affich sur la ligne de sortie (similaire une ligne de bus),

    - quand la commande d'criture et select i sont 1, la valeur sur la ligne d'entre estmmorise dans le verrou,

    - tant que select i est 0, l'tat du verrou reste inchang.

    Le verrou peut tre de type statique ou dynamique ; dans le dernier cas, il ncessite moins detransistors, mais il est ncessaire de "rafrachir" l'information mmorise rgulirement (en lalisant puis en la rcrivant). Il est possible de raliser des mmoires RWM avec 5 ou 6transistors par point mmoire (type statique) ou mme un seul transistor (type dynamique).

    ligne de slection mot i

    ligne d'entre/sortie

    Point de mmorisation dynamique

    Il est possible de raliser, par extension du schma de la figure III-26 c), des mmoires double accs en lecture et / ou en criture :

    - si il y a 2 dcodeurs (qui gnrent des signaux select1i et select 2i), 2 commandes de lectureet 2 lignes de sortie par bit, il est possible de lire en mme temps 2 mots d'adressesdiffrentes (ou non),

    - avec ces 2 dcodeurs, il est aussi possible de lire un mot et d'en crire un autre, mais il fautviter de lire et crire le mme mot.

  • - II.18 -

    Exercices

    III-21Proposer un point de mmorisation pour une mmoire double accs en lecture (cfFig.III-26 c).

    II-7 On peut raliser une pile (cf exercice III-17 et III-18) l'aide d'une mmoire RWM etd'un registre compteur / dcompteur (cf exercice III-20). Proposer une telle ralisation.pourune pile de 32 mots de b bits.

    Comparer le cot de ralisation d'une pile l'aide de registres dcalages (exercice III-18) etcelui de la ralisation l'aide d'une mmoire. On suppose que les registres dcalage sontraliss avec des bascules matre-esclave MOS de 12 transistors, et que la mmoire est unemmoire statique points de mmorisation de 6 transistors.

    III-22Une file d'attente de k mots de b bits permet de mmoriser des mots et de les reliredans l'ordre de leur arrive (premier entr, premier sorti, ou First In, First Out : FIFO). Unetelle structure peut tre ralise l'aide d'une mmoire RWM et de registres compteurs, quimmorisent l'adresse du mot de tte de la file et l'adresse du mot de queue de la file dans lammoire. Proposer une ralisation d'une file de 32 mots de b bits.

  • - II.19 -

    2. AUTOMATES

    Tout circuit squentiel peut tre modlis formellement par un automate. Inversement,"effectuer la synthse d'un automate" est "raliser un circuit squentiel". Aprs avoir dfini unautomate, nous en tudierons les reprsentations.

    2.1. DEFINITION

    Un automate A est dfini par un quintuplet ( Q , E , S , , ) o :

    - Q est l'ensemble des tats de l'automate,- E est son vocabulaire d'entre (ensemble des valeurs possibles des entres),- S est son vocabulaire de sortie- est l'ensemble des transitions Q E Q- est l'ensemble des sorties Q E S

    Un automate peut tre :

    - synchrone : les changements d'tats sont autoriss par une horloge,- asynchrone : les changements d'tats sont toujours autoriss et peuvent se produire ds

    qu'une entre change de valeur,- tat initial fix ou non, unique ou non,- non dterministe ou dterministe : dans ce dernier cas, il s'agit d'un automate tat initial

    unique, o tout couple (tat, entre) est associe une transition au maximum ; estredfini comme une fonction appele fonction de transition, : Q E -> Q

    - non ractif ou ractif : dans ce dernier cas, tout couple (tat, entre) est associe unetransition au minimum (on parle aussi d'automates complet),

    - automate de Moore : la fonction de sortie est une fonction de Q dans S (les sorties nesont fonction que de l'tat), : Q -> S

    - automate de Mealy sinon : Q E -> S

    Nous n'tudierons que les automates synchrones, principalement de type Moore, tat initialfix, dterministe et ractif ( chaque couple tat, entre est associe une et une seuletransition)

    2.2. REPRESENTATIONS DES AUTOMATES

    2.2.A. GRAPHE D'ETATS

    Un automate peut tre spcifi par un graphe d'tats o :

  • - II.20 -

    - chaque sommet reprsente un tat,- chaque arc reprsente une transition d'un tat un autre, et est tiquet par l'lment du

    vocabulaire d'entre qui conditionne cette transition,- les sorties sont associes aux arcs (automate de Mealy) ou aux tats (automate de

    Moore).

    Exemple

    On veut faire le graphe d'tats d'un automate dfini par :

    E = { a , b} , S = { oui, non}

    tel que la sortie vaut oui si et seulement si les 4 dernires entres reues forment la squence ab b a.

    Les graphes d'tat pour un automate de type Moore et un automate de type Mealy,rpondant cette spcification, sont donns figure II-19.

    A/non

    C/non

    D/non

    E/oui

    B/non

    ba

    a

    b

    b

    aba

    b

    a

    init

    A b/nona/non

    a/non

    b/non

    b/non

    a/oui

    b/non

    a/non

    init

    B

    C

    D

    a) automate de Moore b) automate de Mealy

    Figure II-19 : graphes d'tats

    L'tat initial est l'tat A.

    On peut interprter les tats de la faon suivante ; tat A : l'automate n'a pas encore reud'entre intressante ; tat B : l'automate a reu a ; tat C : l'automate a reu a puis b ; tat D: l'automate a reu a puis b puis b. Ensuite, dans le cas de l'automate de Mealy, la sortie passe oui si une entre a est reue, puis l'automate se met dans l'tat B. Dans le cas de l'automate

  • - II.21 -

    de Moore, l'automate passe l'tat E o la sortie prend la valeur oui, puis se met dans l'tat Bou C, suivant la valeur de l'entre suivante.

    Ces 2 automates sont quivalents (pour toute squence d'entres, les squences de sortie sontidentiques), mais ont un fonctionnement temporel diffrent (cf 3.2.E).

    2.2.B. TABLEAU D'TATS

    On peut aussi reprsenter un automate par un tableau d'tats, donnant l'tat suivant et la sortieen fonction de l'tat courant et de l'entre.

    Exemple

    Pour les automates spcifis par les graphes d'tats de la figure II-19, les tableaux d'tats sontles suivants :

    entre a b tat courant A B A non B B C non C B D non D E A non E B C oui tat suivant sortie

    entre a b tat courant A B/non A/non B B/non C/non C B/non D/non D B/oui A/non tat suivant

    a) automate de Moore b) automate de Mealy

    Figure II-20 : tableaux d'tats

    Exercice

    II-9 Soit un automate spcifi par :

    E = { a, b, c }, S = {d, e, f}, tel que la sortie vaut d ssi les 3 dernires entres taient abc,vaut e ssi les 2 dernires entres taient cb, et f sinon.

    Faire le graphe d'tats et le tableau d'tats de cet automate (type Moore et Mealy).

    3. SYNTHSE D'AUTOMATES

    3.1. PRINCIPE

    Nous tudions ici la ralisation d'un automate synchrone par un circuit digital. Ce circuit seratoujours du type indiqu figure II-21.

  • - II.22 -

    C

    initH

    entres sorties

    bascules d'tat

    Figure II-21 : circuit ralisant un automate

    Un ensemble de bascules mmorisent l'tat de l'automate ; elles peuvent tre mises l'tatinitial par le signal init (qui agit sur les entres d'initialisation des bascules), et sont actives parle signal H, qui est l'horloge de synchronisation de l'automate. Ces bascules doivent tresensibles au front ou matre-esclave, comme il y a rebouclage des sorties des bascules vers lesentres, et que l'tat ne doit voluer qu'une fois au maximum durant une priode d'horloge.

    Le circuit combinatoire C ralise les fonctions et , d'aprs les valeurs des entres et l'tatcourant du circuit.

    3.2. METHODE DE SYNTHESE

    3.2.A. CODAGE

    Avant de songer raliser un automate, il faut choisir un codage binaire des tats et desvocabulaires d'entre et de sortie. Ce codage peut tre quelconque, ou impos par laspcification de l'automate (en gnral, c'est le cas pour les entres et sorties).

    Aprs cette tape de codage, on peut dterminer le graphe d'tats cod : un noeud estassoci le code de l'tat qu'il reprsente, un arc est associ les valeurs des variablesboolennes d'entre et ventuellement de sortie.

    Exemple

    Pour l' automate de Moore des figures II-19 a et II-20 a, nous choisissons le codage :

  • - II.23 -

    - vocabulaire d'entre : 2 lments, codage par une variable boolenne x, a est cod 1, b estcod 0,

    - vocabulaire de sortie : 2 lments, codage par une variable boolenne z, oui est cod 1,non est cod 0,

    - tats : 5 tats, codage par 3 variables d'tats y2 y1 y0 , A : 000, B : 001, C : 010, D : 011,

    E : 100.On en dduit le graphe d'tats cod et le tableau d'tats cod (Fig.II.22).

    000/0

    010/0

    011/0

    100/1

    001/0

    01

    1

    0

    0

    101

    0

    1

    init

    x 1 0 y y y 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 1 0 0 0 1 0 1 1 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 1 tat suivant z Y Y Y

    3 2 1

    3 2 1

    a) graphe d'tats cod b) tableau d'tats cod

    Figure II-22 : graphe et tableau d'tats cods

    On a not Y3Y2Y1 le code de l'tat suivant (y3(t+1) y2(t+1)y1(t+1).

    Pour un automate complexe, une autre forme de graphe d'tats cod permet de raisonner plusfacilement : au lieu d'associer aux arcs les valeurs des entres qui provoque la transition, onleur associe la fonction boolenne des variables d'entres qui vaut 1 si et seulement si cettetransition doit tre effectue. De mme, au lieu d'indiquer la valeur des sorties pour tout arc(ou tout tat), on indique dans quel cas la sortie vaut 1.

    Exemple

    Le graphe d'tat de la figure II-19 a ) peut tre reprsent, aprs codage du vocabulaired'entre et de sortie, par le graphe de la figure II-23.

  • - II.24 -

    A

    C

    D

    E / z

    B

    xx

    x

    x

    x

    xxx

    x

    x

    init

    Figure II-23 : autre reprsentation du graphe d'tats cod

    Attention, notre automate devant tre

    - dterministe, le produit 2 2 des expressions boolennes associes aux arcs sortants d'untat doit tre gal 0

    - compltement dfini, la somme des expressions boolennes associes l'ensemble desarcs sortants d'un tat doit tre gale 1.

    3.2.B. DTERMINATION DES QUATIONS D'ETATS

    Le circuit C ralise la fonction de transition d'tats : cette fonction, une configuration devaleur des variables d'tat yj et des entres, associe les valeurs suivantes des variables d'tatsYi : il s'agit d'un ensemble de fonctions boolennes

    Yi = fi(yn, yn-1, ...,y0, ek, ek-1, ..., e0).

    Cet ensemble de fonctions boolennes dfinit les quations d'tat, qu'il est facile de dterminer partir du tableau d'tats cod.

    De mme, les quations des sorties du circuit sont dtermins partir du tableau d'tats cod.

    Exemple

    Du tableau d'tats cod de la figure II-22 b), on tire les tableaux de Karnaugh de Y3 Y2 Y1 et

    de la sortie z, donns ci-dessous :

  • - II.25 -

    y1 x y3 y2 00 01 11 10 00 000 001 001 010 01 011 001 100 000 11 ? ? ? ? 10 010 001 ? ?

    y1 y3 y2 0 1 00 0 0 01 0 0 11 ? ? 10 1 ?

    tableau de Y3 Y2 Y1 t ableau de z

    Figure 24

    A partir des tableaux, on dtermine de manire classique les quations d'tat :

    Y3 = y2 y1 x

    Y2 = y2 + y3 + y1

    Y1 = y2 + x + x

    ainsi que l'quation de la sortie z :

    z = y3

    Exercice

    II-10 Proposer un codage pour l'automate tudi l'exercice II-9 ; faire le tableau d'tatscod et dterminer les quations d'tats et des sorties de l'automate.

    3.2.C. REALISATION D'UN AUTOMATE AVEC DES BASCULES D

    Les quations d'tat indiquent pour chacune des variables d'tat la valeur de yi (t+1) en

    fonction de l'tat et des entres t. Note : cette quation n'est pas directement implmentable,car elle inclue une dimension temporelle.

    Le fonctionnement de la bascule D peut tre dcrit par y(t+1) = D(t)

    On a donc, pour un automate n variables d'tats et p entres, les deux quations suivantespour y i :

    yi (t+1) = f(tat(t), entres(t))

    yi (t+1) = D(t)

    On en dduit qu' l'instant t, on doit avoir :

    D(t) = f(tat(t), entre(t))

    On peut donc dterminer les quations des entres des bascules D, donc la spcification du

  • - II.26 -

    circuit C, qui peut tre ralis l'aide de portes ou de circuits de moyenne complexit.L'utilisation de PLA est frquente. Les bascules qui mmorisent les variables d'tats nepeuvent pas tre de type verrou : au mme moment, l'ancienne valeur des bascules est utiliseet une nouvelle valeur est charge. Ces bascules sont actives par l'horloge de l'automate etinitialises par le signal init (Fig.II-24).

    Exemple

    Le circuit ralisant l'automate de la figure II-22 a) est donn figure II-25

    C

    init

    H

    x z

    y3y2

    y1

    D3

    D2

    D1

    Figure II-25 : ralisation de l'automate

    avec :

    D3 = y2 y1 x

    D2 = y2 + y3 + y1

    D1 = y2 + x + x

    z = y3

    3.2.D. REALISATION D'UN AUTOMATE AVEC DES BASCULES JK,...

    L'quation de fonctionnement d'une bascule JK est :

    y (t +1) = y(t) K (t) + y (t) J(t)

    Pour pouvoir dterminer les quations de J et de K, il faut mettre chaque quation d'tat sous

  • - II.27 -

    la forme : y(t +1) = y(t) f1(tat(t) , entres(t)) + y(t ) f2(tat(t) , entres(t))

    On en dduit que J = f2(tat(t), entres(t)) et K = f1(tat(t) , entres(t))

    Exemple

    Pour notre exemple, on obtient :

    J 3 = y2 y1 x K3 = y2 y1 x

    J 2 = y1 x + y3 x K 2 = y 1 x + y3 x

    J1 = x + y2 K1 = y 2 x

    On peut effectuer des identifications locales, et pour cela aussi utiliser le tableau de transitionde la bascule JK donn ci-dessous :

    yt yt+1 J K

    0 0 0

    0 1 1

    1 0 1

    1 1 0

    Ce tableau indique quelle doivent tre les valeurs de J et K pour chaque transition d'tat de labascule. On peut alors pour chaque case du tableau d'tats (ou plutt du tableau de Karnaughqu'on en a dduit cf. figure II 24) dterminer quelles doivent tre les valeurs de J et de K.

    Exemple

    y1 x y3 y2 00 01 11 10 00 000 001 001 010 01 011 001 100 000 11 ? ? ? ? 10 010 001 ? ?

    y1 x y3 y2 00 01 11 10 00 0? 0? 0? 0? 01 0? 0? 1? 0? 11 ? ? ? ? 10 ?? ?? ? ?

    tableau de Y3 Y2 Y1 t ableau de J 3 K3

    On obtient :

    J 3 = y2 y1 x K3 = 1

    L'expression de K3 est plus simple que prcdemment, car les correspondant aux codesd'tat non valides ont t utiliss.

  • - II.28 -

    3.2.E. OPTIMISATION D'AUTOMATES

    La ralisation d'un automate peut tre optimise diffrents niveaux :

    - au niveau de la spcification du circuit raliser, par minimisation du nombre d'tatsde l'automate : 2 tats A et B d'un automate sont quivalents si et seulement si, pour toutesquence d'entres applique A, la squence de sorties est la mme que si la squence taitapplique l'tat B. Si 2 tats sont quivalents, ils peuvent tre confondus en 1 seul tat.

    - au niveau du codage des entres et des sorties, ventuellement (en gnral, ces codessont fixs),

    - au niveau du codage des tats : le codage des tats est en gnral choisi par leconcepteur ; deux codages diffrents peuvent mener des quations des variables d'tat etdes sorties plus ou moins complexes.

    Exercices

    On rappelle les tapes de la synthse d'un automate :

    - partir de la spcification, dterminer le graphe d'tats (et le minimiser, si ncessaire)

    - codage des entres, des sorties et des tats => tableau d'tats cods

    - dterminer les tableaux de Karnaugh et/ou les quations des variables d'tats et dessorties

    - choisir un type de bascules et dterminer les quations des entres des bascules

    - faire la synthse du circuit.

    II 11 Raliser l'automate de Mealy donn figure II-20-b partir de bascules D puis debascules JK.

    II-12 Mme exercice pour l'automate tudi dans les exercices II-9 et II-10.

    II-13 Dterminer les tableaux de transitions des bascules RS et des bascules T. Faire lasynthse de l'automate de Moore qui nous a servi d'exemple (le tableau d'tats et de la sortiesont indiqus figure II-24).

    3.2.F. FONCTIONNEMENT TEMPOREL DES AUTOMATES

    Il reste analyser les aspects temporels du fonctionnement des automates, c'est--dire lesrelations entre l'horloge, le type de bascule, l'volution temporelle des entres, le type

  • - II.29 -

    d'automate et l'volution temporelle de la sortie.

    Cette analyse sera faite pour des automates raliss avec des bascules sensibles au frontmontant (ou des bascules matre-esclave dont l'tage esclave est activ par H). Prenonscomme exemples les automates tudis au paragraphe prcdent : la figure II-26 indiquel'volution temporelle de la sortie z (ou chronogramme de z), lorsque la squence d'entre 1 00 1 (squence reconnaitre a b b a) est applique sur l'entre x partir de l'tat initial A.

    H

    init

    x

    tat

    tat z

    type Moore

    type Mealy

    A B C D E

    z

    A B C D B

    a b b a

    Figure II-26 : chronogrammes

    Sur cette figure, l'volution de l'entre x est telle que sa valeur est spcifie autour du frontmontant de H, sans prjuger des instants de variation (les portions en gris indiquent unevaleur indtermine).

    On voit que :

    - dans l'automate de Moore, la sortie reste stable entre 2 fronts d'horloge (elle ne dpendque de l'tat, qui est stable entre 2 fronts) ;

    - dans l'automate de Mealy, la sortie n'est valide que autour de chaque front (en effet, elleest fonction de l'tat et des entres, or l'tat change au front),

    Dans le cas de l'automate de Mealy, pour avoir une valeur de la sortie stable assez longtempspour pouvoir l'exploiter, il faut

    - soit s'assurer que l'entre est stable longtemps avant le front de changement d'tat (de

  • - II.30 -

    prfrence juste aprs le front de changement d'tat prcdent),

    - soit mmoriser la valeur des sorties dans un ensemble de bascules, ce qui revient enfait un automate de Moore.

    C'est pour cela que nous concevrons principalement des automates de Moore, dont lessorties sont stables une priode d'horloge complte, et non des automates de Mealy.

    Pour qu'un automate fonctionne correctement, il faut que les 2 ingalits suivantes soientrespectes :

    - tmax + tamax + t setup,- tamin + t min = thold,

    o T est le temps entre deux fronts d'activations des bascules, c'est--dire la priode del'horloge, tamax est le temps maximal et tamin est le temps minimal de calcul des entres des

    bascules, tmax et t min sont les temps maximal et minimal de changement d'tat desbascules, tsetup et thold sont les temps minimaux imposs de stabilit des entres des bascules

    avant et aprs le front d'activation.

    En gnral, la 2me ingalit est toujours respecte : les bascules sont telles que tmin = thold,

    par construction. La premre ingalit permet de dterminer la frquence maximale del'horloge.

    3.3. SYNTHESE D'AUTOMATES COMPLEXES

    La mthode de synthse expose ci-dessus est valable pour tout automate. Cependant,certaines techniques sont utiles pour raliser des automates complexes, beaucoup d'entreset / ou beaucoup d'tats.

    3.3.A. REPRESENTATIONS DES AUTOMATES COMPLEXES

    On reprsentera en gnral un automate complexe par un graphe d'tats o figurentuniquement les fonctions boolennes des variables d'entre qui provoquent les transitions, eto une sortie n'est indique que quand elle est active (cf Fig.II-23).

    On peut aussi le reprsenter par un tableau de transitions (cf Fig.II-27 c).

    Exemple

    On prendra comme exemple l'automate dfini par le graphe de la figure II-27 (il n'est pasvraiment complexe, mais il permet d'illustrer les techniques employes).

  • - II.31 -

    A

    B / s

    C / t

    D /s,t

    E / u

    F /t,u

    deb

    a.deb a.deb

    1 1b

    c

    b

    cc

    c

    initdeb a b c

    init H

    s

    t

    u

    a) entres et sorties de l'automate

    A

    tat courant tat suivant * entre A. deb A A. a deb B A. a deb D B C C. b A C. b E D E E. c F E. c C F. c F F. c C

    c) tableau de transitions b) graphe d'tats

    Figure II-27 : exemple d'automate complexe

    Les techniques employes pour la synthse de tels automates diffrent suivant le type decircuit utilis. Nous allons en voir quelques exemples.

    3.3.B. SYNTHSE EN CODAGE 1 PARMI N

    Au lieu de coder les tats l'aide du minimum de variables d'tat, on choisit un code dit code1 parmi n, qui associe une variable d'tat yi chaque tat i: les codes valides sont de la forme

    0 0 0 .... 0 1 0 .... 0, avec un seul 1 parmi des 0. L'automate est dans l'tat i si et seulement si.... yi ......= 1, ce qui est caractris par yi = 1.

    Les quations d'tat sont triviales, et la ralisation de l'automate peut tre faite directement partir du graphe d'tats de l'automate.

    Exemple

    Pour l'automate spcifi figure II-27, les quations d'tats et des sorties, ainsi que la ralisationde l'automate sont donnes figure II-28. Les quations d'tat sont obtenues partir du graphed'tats ou du tableau de transitions, en dterminant les tats antcdents d'un tat et lesconditions de transitions

  • - II.32 -

    YA = deb. yA + b . yC YB = a. deb. yA YC = yB + c. yE + c. yF YD = a. deb. yA YE = b . yC + yD YF = c . yE + c. yF s = yB + yD t = yC + yD + yF u = yE + yF

    deb

    a.deb a.debyA

    yB yD

    yC yEbb

    c

    yF

    c

    c

    c

    s

    u

    t

    Figure II-28 : ralisation en codage 1 parmi n

    La bascule mmorisant yA est initialise 1 (signal init connect l'entre "Preset"), les autressont initialises 0 ; toutes les bascules sont actives par l'horloge de l'automate.

    La synthse en codage 1 parmi n simplifie les quations d'tats et les quations des sorties(donc la partie combinatoire du circuit ), mais utilise un grand nombre de bascules.

    3.3.C. SYNTHESE EN CODAGE COMPACT ET RALISATION AVEC UN PLA

    On peut coder les tats d'un automate complexe avec le minimum de variables, pour leraliser avec un PLA par exemple. On cherche alors choisir un code optimisant la taille duPLA, c'est--dire minimisant le nombre de monmes. Ce type de solution est intressant enconception de cartes, car il existe des boitiers PLA incluant des bascules, qui permettent deraliser en un seul boitier un automate de moyenne complexit. En conception de circuits

  • - II.33 -

    intgrs, l'intrt de ces solutions vient de la rgularit d'implmentation des PLA.

    Exemple

    Pour une synthse avec des bascules D, on s'interesse aux variables d'tats 1 dans le codede chaque tat.

    On note :

    - unsi la liste des variables 1 dans le code de l'tat i (par exemple, si i est cod 0101sur les variables y3,y2,y1,y0, unsi = (y2,y0)

    - Ci le monme caractristique du code de i (code de i = 0101, Ci = y3 y2 y1 y0 )

    Du graphe d'tats de la figure II-27, on dduit que :

    unsA = CA + CC unsB = a deb CA

    unsC = CB + c CE + c CF unsD = deb CA

    unsE = b CC + CD unsF = CE + CF

    s = CB + CD t = CC + CD + CF u = CE + CF

    A priori, il y a 14 monmes distincts synthtiser. Mais si les codes de E et de F sontadjacents, on peut crer un monme MEF unique, d'o :

    unsA = CA + CC unsB = a deb CA

    unsC = CB + c MEF unsD = deb CA

    unsE = b CC + CD unsF = MEF

    s = CB + CD t = CC + CD + CF u = MEF

    d'o une ralisation 12 monmes.

    De plus, on remarque que les monmes CC et CF ne sont gnrs que pour faire la somme CC+ CD + CF : si ces 2 monmes sont adjacents, CC + CF se simplifie en un seul monme MCF et

    la ralisation n'aura plus que 11 monmes.

    Il nous reste choisir l'tat cod 0 : cet tat n'aura pas de 1 dans son code, et donc lesmonmes correspondants ne seront pas gnrs ; on a donc intrt utiliser le code 0 pourl'tat ayant le plus d'antcdents. Ici, on choisit A cod 0 et une ralisation 9 monmes auplus (les monmes CA et CC ne seront pas gnrs).

    On obtient ainsi un ensemble de contraintes d'adjacences sur les codes des tats ; il reste trouver un codage qui les satisfait (ce n'est pas toujours possible). Dans notre cas, il s'agitd'associer les tats aux cases d'un tableau de Karnaugh 3 variables ; le placement suivant

  • - II.34 -

    respecte les contraintes.

    y2 y0 y3 00 01 11 10 0 A B C D 1 - E F -

    ETAT A B C D E F CODE 000 001 011 010 101 111

    Exercices

    II-14 Dterminer les quations du PLA pour l'automate de l'exemple, dont un codage a tpropos ci-dessus.

    II-15 Rechercher un codage optimisant la ralisation sur PLA pour l'automate tudi l'exercice II-9. Comparer la solution obtenue avec celle trouve l'exercice II-10.

    3.3.D. SYNTHSE L'AIDE DE COMPTEURS

    Dans la gamme des boitiers de moyenne complexit, on dispose de compteurs modulo 16 ou32. A partir de cet automate compteur, il est possible de raliser d'autres automates, en jouantsur les entres de chargement et d'incrmentation du compteur (cf 1.7.D.).

    On choisit un codage qui maximise le nombre de transitions o les codes des tats d'origine etdestination sont des entiers conscutifs. Si un tat a plusieurs successeurs, le code du ou destats qui ne sont pas obtenus par incrmentation sont chargs dans le compteur.

    Exemple

    Pour l'exemple de la figure II-27, on prend le codage :

    A : 0, D : 1, E : 2, F : 3, B : 6, C : 7.

    On en dduit le tableau suivant, qui indique les valeurs des entres du compteur pour chaquetransition, en utilisant le compteur dfini figure II-16 pour lequel l'entre d'incrmentation estprioritaire sur l'entre de chargement (attention, ce n'est pas forcment ce type de compteurque vous utiliserez en travaux pratiques !) :

  • - II.35 -

    tat courant tat suivant incr cha valeur * entre de chargement A. deb A 0 1 0 A. a deb B 0 1 6 A. a deb D 1 ? ? B C 1 ? ? C. b A 1 ? ? C. b E 0 1 2 D E 1 ? ? E. c F 1 ? ? E. c C 0 1 7 F. c F 0 1 3 F. c C 0 1 7

    En utilisant sytmatiquement des multiplexeurs, on obtient le circuit suivant (Fig.II-29).

    compteur modulo 8

    incr

    cha

    A (valeur de chargement)

    Y

    0 1 2 3 4 5 6 7

    0 1 2 3 4 5 6 7

    0 6

    a deb 1 c 0 0 0 1 b

    Y0 1

    db

    codes chargs dans le compteur

    7

    2

    0 1

    c3 7

    1

    init

    raz En

    H

    Figure II-29 : ralisation avec un compteur

    L'entre cha est toujours 1. Un multiplexeur sert slectionner la valeur de l'entred'incrmentation en fonction du code de l'tat, la valeur slectionne tant fonction des entresde l'automate ds qu'un tat a plus d'un successeur.

    Un systme de multiplexage sert slectionner la valeur charger en fonction du code del'tat et ventuellement des entres de l'automate, d'o les 2 systmes de multiplexeurs 2 -> 1,qui seraient avantageusement remplacs par de simples connexions. Par exemple, lemultiplexage command par db peut tre remplac par les valeurs db, db, 0 connectessur les entres 0 du systme de multiplexage en fonction du code de l'tat (si db = 0, on

  • - II.36 -

    obtient le code 0, si db =1, on obtient le code 6). De mme pour le multiplexage commandpar c (valeurs c,1,1)Les multiplexeurs, n'tant pas compltement utilises, peuvent tresimplifis ou remplacs par un PLA. Les sorties sont gnres partir du code de l'tat Y.

    3.3.E. REALISATION AVEC UNE ROM ET MICROPROGRAMMATION

    Principe

    On peut chercher raliser un automate base de ROM, mais il n'est pas envisageable deraliser directement le circuit combinatoire C par une ROM : en effet, si il y a n variablesd'tats, m entres, la ROM aurait 2n+m mots (soit, pour notre exemple d'automate pas trscomplexe, 3 variables d'tat et 4 entres, une ROM de 128 mots de 6 bits pour gnrerl'tat suivant et les sorties !).

    La solution employe est d'associer un mot de la ROM chaque tat (et non chaque couple(tat , valeurs des entres)), et d'indiquer dans ce mot la valeur des sorties et commentcalculer l'tat suivant. Il est vident que ce principe ne peut s'appliquer qu'aux automates detype Moore.

    Les primitives de calcul de l'tat suivant peuvent tre :

    - incrmenter l'tat courant,- suivant une condition, incrmenter l'tat courant ou charger le code indiqu (branchement

    conditionnel),- charger un code fourni par un circuit combinatoire.

    Ceci est assez similaire la synthse l'aide de compteur. Le schma de principe d'une telleralisation est donn figure II-30.

    ROM

    champ squencement

    champ commande

    E T A T

    circuit de calcul de l'tat suivant

    conditions testes

    init H

    Figure II-30 : ralisation l'aide d'une ROM

  • - II.37 -

    Exemple

    On reprend l'exemple prcdent, avec le codage utilis figure II-29.

    Un mot de la ROM a le format suivant :

    champ squencement champ seq cond adr sorties S1 S0 C A2 A1 A0 s t u

    C condition 0 b 1 c

    S1 SO squencement 0 - tat := tat plus1 1 0 si condition = 1 tat := adr sinon tat := tat plus1 1 1 tat := entre tat

    codage des champs

    Le contenu de la ROM, pour implmenter l'automate, doit tre :

    numro de mot champ squencement sorties

    S1S0 C A2A1A0 s t u

    mot 0 (tat A) 1 1 0 0 0

    mot 1 (tat D) 0 1 1 0

    mot 2 (tat E) 1 0 1 1 1 1 0 1 0

    mot 3 (tat F) 1 1 0 1 1

    mot 4

    mot 5

    mot 6 (tat B) 0 1 0 0

    mot 7 (tat C) 1 0 0 0 1 0 0 1 0

    Le circuit de calcul de l'tat suivant a comme entres : les entres de l'automate (a,deb,b,c) etl'tat courant. Suivant le champ squencement , il en dduit le code de l'tat suivant.

  • - II.38 -

    Exercice

    II-16 Proposer une ralisation du circuit de calcul de l'tat suivant, pour l'exemple ci-dessus.Ce circuit comporte un incrmenteur (cas S1 S0 = 0 - ou 10), un circuit de calcul du code del'tat suivant (cas S1 S0 = 11), un circuit de calcul de la condition (cas S1 S0 = 10), et unsystme de multiplexage qui permet de slectionner le code correct pout l'tat suivant.

    Gnralisation : microprogrammation

    L'avantage de ce type de ralisation base de ROM est sa flexibilit : avec une mme ROMet un mme circuit de calcul de l'tat suivant, il est possible de raliser diffrents automates.De plus, cette ralisation ncessite peu de boitiers. Cette technique a t propose ds lesannes 60 par Wilkes, et trs employe dans les annes 70 ; pour souligner sa flexibilit, lenom de microprogrammation est utilis : le circuit de la figure II-30 est un squenceurmicroprogramm ; le circuit de calcul de l'tat suivant est un microsquenceur (squenceur dusquenceur) ; les bascules mmorisant l'tat forment le registre compteur de microprogramme; une ligne de la ROM contient une microinstruction.

    Les extensions possibles par rapport au cas simple que nous avons trait sont :

    - la possibilit de sous-microprogramme : quand une squence de microinstructions serpte dans la ROM, il est possible de ne l'crire qu'une seule fois et d'effectuer unbranchement vers cette squence unique en sauvegardant le code de l'tat de retour (tataprs la fin de l'excution de la squence) : la fin de la squence, le code sauvegard estrecharg dans le compteur de microprogramme. Dans ce cas, le circuit de calcul de l'tatsuivant comporte une pile de sauvegarde, et on ajoute aux primitives de squencement lespossibilits de branchement sous-microprogramme (pile : = tat + 1 ; tat := adr) et deretour de sous-microprogramme (tat := pile).

    - la possibilit de microprogrammation verticale ; dans ce cas, il existe deux types demicroinstructions : les microinstructions de commande, o des sorties sont actives et pourlesquelles, par convention, l'tat suivant est obtenu par incrmentation, et les microinstructionsde squencement, o les primitives de squencement complexes sont utilises. Lesmicroinstructions sont alors codes avec 2 formats possibles :

    0 champ commandes

    1 champ squencement

    Cela permet d'viter de prvoir un champ squencement dans toute microinstruction, alorsqu'il n'est pas toujours utilis, donc de diminuer le nombre de bits de la ROM ; mais, ds qu'ily a branchement, 2 microinstructions au lieu d'une seule seront excutes. A noter : l'automate

  • - II.39 -

    ralis avec ce principe n'est pas quivalent l'automate initial (priodes d'horlogesupplmentaires durant lesquelles il n'y a pas de sorties mises). Cette solution sera doncrserve des cas particuliers : commande de la partie oprative d'un circuit complexe oud'un processeur, tudis par la suite.

    - sparation des champs commande et squencement : pour certains automates, lemme champ commande est associ plusieurs tats. Si une ROM contient les champssquencement, et une autre les champs commande, cette dernire ne contient alors qu'unexemplaire de chaque valeur de champ commande. Il faut cependant ajouter un circuit decalcul de l'adresse ROM commande partir du code de l'tat, ce qui ralentit l'mission descommandes. En choisissant des codes adjacents pour les tats ayant le mme champcommande, on peut optimiser ce circuit.

    Exercices

    II-17 Nous avons ralis pour notre exemple une solution microprogrammation horizontale(champ squencement et champ commandes dans le mme mot de la ROM). Il s'agitd'tudier une solution microprogrammation verticale, avec deux types de microinstructions.

    1- Dfinir le format des microinstructions verticales.

    2- Proposer une spcification du circuit microsquenceur.

    3- Modifier le graphe d'tats pour prendre en compte la diminution des possibilits desquencement, choisir un codage des tats et crire le microprogramme.

    4- Raliser le circuit microsquenceur.

    5- Evaluer la rentabilit des deux solutions ; le temps sera mesur par le nombre moyend'accs la ROM effectuer pour chaque tat de l'automate initial ; le cot sera mesur parle nombre de bits de la ROM (pour les mots effectivement utiliss), et la rentabilit est dfinieclassiquement par : 1 / temps * cot.

    6- Gnrralisation du rsultat : on suppose que l'automate initial est tel que x% des tatspeuvent tre cods avec des codes conscutifs ; que le champ squencement ncessite m bitset le champ commande n bits. Dans quelles conditions la solution de microprogrammationverticale est-elle intressante ?

    II-18 Proposer une ralisation d'un microsquenceur offrant les primitives de squencementsuivantes :

  • - II.40 -

    champ sq S2 S1 S0 squencement 0 0 0 tat := tat plus 1 0 0 1 si condition alors tat := adr sinon tat := tat plus 1; 0 1 1 si condition alors pile := tat +1, tat := adr sinon tat := tat plus 1 1 0 0 tat := pile 1 0 1 tat := entre1 1 1 0 tat := entre2 1 1 1 tat := 0.....0

    champ cond C1 C0 condition 0 0 a 0 1 b 1 0 c 1 1 d

    II-19 Soit un automate 15 tats, A, B, ...,0. Certains tats ont le mme champ decommande : (A, O) (D, L), (B, E, G), (C, F, I, M).

    1- Proposer une ralisation de l'automate l'aide de 2 ROM et donner la taille de ces 2ROM

    2- En supposant qu'il n'y ait pas de contraintes sur le codage des tats dues ausquencement, proposer un codage des tats et un adressage de la ROM commande.

    3- Si le champ squencement ncessite n bits de codage, et le champ commande m,valuer les cots (en points-mmoire) de la solution n'utilisant qu'une ROM et de cellepropose ici.

Recommended

View more >