Choix d'une représentation
Une solution simple serait d'utiliser des tableaux de booléens : dans cette représentation, la cellule d'indice t contient la valeur du signal pendant le cycle t. Cela nous donne le type boolean[].
Néanmoins, cette représentation est peu compacte pour les signaux dont la valeur ne change pas souvent. Pour remédier à cela, nous pouvons utiliser une représentation dite «creuse», à base de listes, où chaque maillon contient :- une valeur entière (l'indice d'un cycle) ;
- une valeur booléenne (la valeur du signal pendant ce cycle et jusqu'au cycle suivant où elle sera modifiée).
Par exemple, le signal représenté dans la figure présentée plus haut peut être représenté par la structure :
Le type Signal correspond donc à l'enregistrement suivant :
class Signal {
int t;
boolean b;
Signal next;
Signal( int t_0, boolean b_0, Signal next_0 ){
t = t_0;
b = b_0;
next = next_0;
}
}
Construction de la structure compacte et affichage
1. Consignes générales et organisation du programme.
Afin de faciliter les dépôts, on placera l'ensemble du code dans un fichier signal.java. Vous devez y copier l'enregistrement Signal ci-dessus (avec le constructeur). Vous placerez ensuite toutes les fonctions à implémenter dans un programme introduit par class Simu. Ces consignes doivent être suivies IMPÉRATIVEMENT.
La représentation du signal s0 ci-dessus est donnée par
Signal s0 = new Signal(0,false,new Signal(1,true,new Signal(4,false,null)));
2. Création de quelques signaux.
Créer dans la fonction main de la classe Simu les signaux s1 et s2 représentés sur les figures suivantes :
- s1 :
- s2 :
3. Affichage «long» pour le débuggage.
Afin de pouvoir inspecter les signaux retournés par vos programmes et rechercher d'éventuelles erreurs, écrire une fonction d'affichage static void displayDebug(Signal s), suivant le format ci-dessous (ce résultat correspond à s0) :
0 => false 1 => true 4 => false
On testera cette fonction sur les signaux s0, s1 et s2 créés à la question 2.4. Signaux constants.
Ajouter à l'enregistrement Signal un second constructeur prenant une valeur booléenne b_0 et construisant le signal constant, dont la valeur à tout instant t ≥ 0 est égale à b_0. On vérifiera que les signaux ainsi engendrés sont corrects, à l'aide de la fonction displayDebug.
5. Affichage compact.
L'affichage précédent est parfait pour bien visualiser les données manipulées dans votre programme, mais dans certains cas, un affichage plus compact sera plus lisible. Écrire une fonction static void display(Signal s) qui affichera le signal s sur une ligne, sous la forme d'une suite de 0 et de 1, avec un chiffre par cycle. On terminera la ligne par "..." dans la mesure où la dernière valeur affichée se répète ensuite à l'infini. Ainsi display(s0) affichera :
01110...
6. Vérifiction structurelle de bonne construction des représentations de signaux.
Écrire une fonction static boolean checkSignal(Signal s), qui prend comme argument un signal et retourne true si la liste utilisée pour le représenter vérifie les propriétés suivantes (et false sinon) :
- la liste n'est pas vide ;
- le premier élément de la liste correspond au cycle 0 ;
- les éléments successifs de la liste correspondent à des cycles triés dans l'ordre croissant.
Signal incorrect_signal_0 = new Signal(0,true,new Signal(4,false,new Signal(2,true,null))); Signal incorrect_signal_1 = new Signal(2,true,new Signal(4,false,null));
N'hésitez pas à utiliser cette fonction par la suite pour vérifier que les résultats de vos programmes sont raisonnables, en effectuant des tests.7. Conversion d'un tableau en un Signal.
Écrire une fonction static Signal arrayToSignal(boolean[] tab), qui prend en argument un tableau, que l'on supposera de longueur non nulle, et construit la représentation optimale (c'est-à-dire la plus courte possible) du signal dont la valeur au cycle i est donnée dans la cellule d'indice i du tableau, (on fait l'hypothèse que la valeur du signal pour les cycles d'indices plus grands que la taille du tableau est égale à la dernière valeur dans le tableau). Par exemple, le code boolean [] t0={true,false,false,true}; displayDebug(arrayToSignal(t0)) affichera :
0 => true 1 => false 3 => true
Conseil : on pourra partir de la fin du tableau.Opérations sur les signaux
Nous pouvons à présent passer à la programmation de quelques fonctions simples sur les signaux.
Important : dans les fonctions suivantes, à chaque fois que l'on calculera un Signal à partir d'un autre, on ne modifiera pas le signal passé en argument (de manière à pouvoir encore l'utiliser par la suite).8. Calcul de la valeur d'un signal à un cycle donné.
Écrire une fonction static boolean getVal(Signal s,int cycle) qui prend en argument un signal et un cycle et renvoie la valeur du signal pendant ce cycle.
Par exemple, getVal(s0,2) retournera true tandis que getVal(s0,5) retournera false.9. Simplification de la représentation d'un signal.
Écrire une fonction static Signal simplify(Signal s) qui prend un signal en argument et retourne un nouveau signal correspondant à sa représentation optimale.
Par exemple, si on prend la représentation non optimale Signal s3 = new Signal(0,true,new Signal(2,true,new Signal(6,false,null))), alors displayDebug(simplify(s3)) affichera :0 => true 6 => false
Important :- On demande une solution qui effectue un nombre d'opérations proportionnel à la taille de la représentation (c'est-à-dire au nombre d'éléments dans la liste) ; en particulier, on ne transformera pas la liste en tableau, mais on traitera celle-ci directement ;
- On pourra au choix programmer cette fonction de manière itérative ou récursive.
- chacune de vos fonctions devra toujours retourner des représentations optimales de signaux ; la fonction simplify pourra être appliquée dans les cas où vous ne seriez pas sûrs que les signaux que vous avez construits sont bien optimaux ;
- vous pouvez faire l'hypothèse que les arguments passés à vos fonctions sont sous forme optimale.
10. Opérateur «Not».
L'opérateur Not associe à un signal sa négation point par point. Écrire une fonction static Signal opNot(Signal s) qui implémente cet opérateur. La fonction opNot devra retourner un nouveau Signal (celui passé en argument ne sera pas modifié).
On pourra tester cette fonction sur s0, s1, s2.11. Opérateur de «retard».
L'opérateur mathématique Delay associe à un signal s le signal Delay(s) défini par :
- Delay(s)(0)=false ;
- Delay(s)(t+1)=s(t).
Écrire une fonction static Signal opDelay(Signal s) qui implémente cet opérateur. La tester sur s0, s1, s2.
12. Opérateur «And».
L'opérateur binaire And retourne le «ET» booléen point par point de deux signaux. Écrire une fonction static Signal opAnd(Signal s0, Signal s1) qui implémente cet opérateur. La tester sur s0, s1, s2. On choisira de préférence un algorithme ayant un coût au plus linéaire en la somme des tailles des deux listes passées en arguments.
Conseil : cet algorithme n'est pas trivial, car il faut parcourir les deux listes s0 et s1 en même temps ; il faut donc bien faire attention à l'ensemble des cas pouvant se présenter à un stade de ce double parcours (y compris les cas où on a atteint la fin d'une des deux listes, ainsi que les ordres possibles des indices de cycles correspondant aux premiers des éléments des deux listes restant à traiter, lorsque celles-ci sont non vides).
Si vous êtes bloqués : vous pouvez convertir les deux signaux en tableaux, calculer le tableau résultat, puis repasser à un signal à l'aide de arrayToSignal (cette solution sera moins appréciée qu'une solution écrite entièrement sur les listes, dans la mesure où un tel algorithme aura un coût plus que linéaire en la somme des longueurs des deux listes passées en arguments).13. Opérateur «Or».
Écrire une fonction static Signal opOr(Signal s0, Signal s1) qui implémente l'opérateur Or, c'est à dire le «OU» logique de deux signaux, point par point.
On utilisera l'identité de De Morgan, et les fonctions opAnd et opNot, puisque X Or Y = Not(Not(X) And Not(Y))Partie subsidiaire : Simulation de circuits composés
Nous allons à présent utiliser les opérateurs que nous avons définis afin de construire des fonctions logiques un peu plus compliquées.
14. (Question subsidiaire) Additionneur.
En composant les fonctions élémentaires que nous avons définies, nous pouvons aussi concevoir et simuler un circuit additionneur. Nous considérons ici que true vaut 1 et false vaut 0. Un additionneur sur 1 bit prend deux entrées s0 et s1 et calcule deux sorties sum0 et sum1 telles que, pour tout intant t, s0(t) + s1(t) = 2 sum1(t) + sum0(t).
Définir et programmer une fonction static Signal[] sum1(Signal s0,Signal s1) et qui retourne un tableau contenant les deux signaux sum0 et sum1.
Généraliser le principe pour un additionneur sur n bits, et mettre au point une fonction static Signal[] addition(Signal[] num0,Signal[] num1) qui calcule la somme de deux nombres positifs sur n bits (on supposera alors que les deux tableaux passés en arguments sont de longueur n le résultat sera alors de longueur n+1).15. (Question subsidiaire) Rétroaction et signal alterné.
L'opérateur de décalage permet de définir des signaux intéressants de manière récursive. Par exemple, le signal X défini par X = Delay(Not(X)) définit un signal alternatif, qui vaut false pendant tout cycle pair, et true pendant tout cycle impair, comme le montre la figure ci-dessous.
En effet, pendant le cycle, ce signal vaut false, puis ensuite, sa valeur pendant le cycle t+1 est la négation de sa valeur pendant le cycle t.
Pour générer ce signal à partir des opérateurs de base, nous allons devoir effectuer un calcul récursif. En fait, nous pouvons utiliser la méthode suivante : on peut calculer de manière triviale une représentation du signal sur l'intervalle [0,t+1] à partir d'une représentation du signal sur l'intervalle [0,t]. Cela montre que l'on peut calculer en t+1 itérations une représentation du signal qui sera correcte sur l'intervalle [0,t]. Ainsi, après 5 itérations, nous obtenons :
Écrire une fonction static Signal sigAlterne(int t), qui calcule et retourne la représentation du signal décrit par l'équation ci-dessus sur l'intervalle [0,t].
La solution que nous vous avons proposée ici n'est pas très efficace (sa complexité est quadratique), car nous recalculons le début du signal t fois ; on pourrait l'optimiser, mais cela aboutirait à un code plus compliqué. - s2 :