Des circuits logiques sur une image bitmap
J’ai toujours été fasciné par les possibilités que nous offre l’algèbre de Boole. A partir de règles très simples, il est possible de construire des systèmes extrèmement complexes… comme des ordinateurs!
Rappels sur la logique booléenne
L’algèbre de Boole est un champ des mathématique qui est utilisé en logique et dans la conception de circuits électroniques. C’est un algèbre très simple qui traite des nombres booléens (Vrai ou Faux), et permet de les manipuler avec des opérations élémentaires:
- And, un opérateur binaire noté ⋅
- Or, un opérateur binaire noté +
- Not, un opérateur unaire noté -
Pour rappel:
- On appelle conjonction une operation composé uniquement de And.
- On appelle disjonction une operation composé uniquement de Or.
Opérations:
- A⋅B⋅ … ⋅Z = 1 seulement si toutes les opérandes (A .. Z) valent 1. Si une seule opérande vaut 0, la conjonction vaudra 0.
- A+B+ … +Z = 0 seulement si toutes les opérandes valent 0. Si une seule opérande vaut 1, la disjonction vaudra 1.
- not 1 = 0, not 0 = 1
Interessant:
- A⋅B = -(-A + -B)
- A+B = -(-A ⋅ -B)
A partir de ces briques élémentaires, il est possible de créer des fonctions plus complexes, comme la porte logique Xor:
- A xor B = A⋅-B + -A⋅B
Ou encore les portes Nand, Nor et Xnor:
- A nand B = -(A ⋅ B)
- A nor B = -(A + B)
- A xnor B = -(A xor B) = (-A + B)⋅(A + -B)
On peut obtenir une porte Not à partir de deux Nand ou Nor:
- A nand A = -A
- A nor A = -A
Circuits logiques
Quand on s’interesse à l’algèbre booléenne, et notamment quand on l’étudie en cours, on est très vite emmené à vouloir du concret, à l’essayer en situation réelle. C-a-d élaborer des circuits logiques et les visualiser, ce qui serait bien plus interessant qu’écrire des opérations sur papier.
Ainsi certaines personnes vont utiliser la redstone de minecraft par frustration, mais pour ma part, je me suis demandé s’il n’était pas possible d’avoir quelque chose de plus pratique. C’est wireworld qui m’a donné l’idée de partir sur des circuits bitmaps. D’autant plus que je pratique et affectionne le pixel art, ce sera une occasion de relier ces deux univers.
Wireworld et ses limitations
Wireworld est un automate cellulaire qui permet de représenter des circuits logiques avec seulement 4 couleurs:
- Vide
- Conducteur
- Electron (avant)
- Electron (arrière)
Les deux couleurs différentes de l’électron permettent de savoir dans quel sens il doit se déplacer.
Wireworld permet de faire des choses étonnamment complexes comme… un ordinateur.
The wireworld computer permet par exemple le calcul de nombres premiers, et vous pouvez l’essayer sous Golly, un logiciel qui permet de simuler des automates cellulaires rapidement.
Une chose qui devrais vous frapper, c’est le nombre d’itérations qu’il faut pour calculer un nombre premier.
Il faut 20k itérations pour le premier, 44k pour le second, 180k pour le troisième…
En effet, wireworld n’utilise pas un courant “instantané”, mais des particules. Cela pose plusieurs problèmes:
- Simuler un circuit requier de très nombreuses itérations, couteuses en temps de calcul.
- Les portes logiques de base sont étonnamment complexes et adaptées à une fréquence spécifique, elles ne fonctionneront pas forcement si on utilise un oscillateur différent.
Bref, wireworld est interessant mais est très loin d’être idéal pour simuler rapidement et simplement des circuits logiques.
Un nouveau paradigme
L’idée est donc de s’inspirer de wireworld, on veut pouvoir tracer directement nos circuits sur une image, puis la simuler. On veut que le courant se déplace de manière instantané sur un cable, et une simulation rapide pour pouvoir executer nos circuits à des fréquences très élevées.
Problèmes:
- Comment on determine le “sens” du courant?
- Les boucles.
- Comment représenter les portes logiques?
- Comment gérer les croisements?
Représentation des fils dans TICS.
Commençons par reflechir à la représentation des portes logiques et des croisements. Représenter un croisement est assez simple, il suffit d’un pixel bridge qui indique que l’on doit le traverser pour continuer sur le pixel suivant.
Croisements des cables TICS.
Une porte logique à deux entrées et une sortie, et il faut être capable de determiner l’un de l’autre.
La solution la plus simple est de représenter une porte logique par un seul pixel:
- Les entrées sont les deux pixels adjacents opposés l’un à l’autre.
- La sortie est le troisième pixel adjacent, opposé à du vide.
Portes logiques dans TICS.
Cette représentation permet de faire toutes les rotations possibles tout en sachant ou se situent les entrées et la sortie.
Orientation des portes logiques dans TICS.
On peut facilement créer des portes Not orientées, ainsi que des diodes, en reliant les deux entrées entre elles.
Portes logiques unaires dans TICS.
Comme on a bien la distinction entre entrées et sorties, il est possible de définir un sens unique au courant. Ainsi le courant ira toujours dans le sens des entrées vers les sorties. On définira les entrées du circuit comme les pixels tout à gauche de l’image, et les sorties comme étant les pixels tout à droite.
Portes Xor et Xnor dans TICS.
L’avantage d’un courant unidirectionnel est qu’il permet de grandement simplifier la représentation du circuit. Il reste désormais le problème des boucles.
Le choix des performances
J’ai décidé d’interdire les boucles afin de permettre d’optimiser au maximum la simulation des circuits.
Sans boucle il est possible de:
- Déterminer à l’avance le nombre d’opérations maximum nécessaires pour calculer une itération du circuit.
- Simplifier le pattern matching et permettre même de compiler nos circuits en des fonctions haut niveau très rapides à calculer.
- Simplifier la lecture du circuit.
Cependant, les boucles sont un élément primordial nécessaire à l’élaboration de mémoires, flip-flops et autres portes logiques incontournables…
Il faut donc un moyen de remplacer les boucles par quelque chose d’équivalent fonctionnellement.
La solution que j’ai choisi est de permettre de créer des sous circuits en profondeur. Ainsi, si je veux faire une boucle, je crée un rectangle dans mon circuit, qui contiendra lui même un circuit.
Les deux circuits sont reliés en utilisant le même principe de gauche=entrées et droite=sorties, ce qui permet de relier les deux circuits, mais on ne les calculera pas au même instant.
Les circuits sont calculés par niveau de profondeur. Ainsi tout est déterminable à l’avance.
Exemple de sous circuit dans TICS.
Exemples
Voici quelques exemples de ce qu’il est possible de faire en l’état.
Un compteur + 7-segment.
Simuler Game of Life, ici un pulsar.
Cliquer pour animer.
Aller plus loin
Faire des mémoires à l’aide de sous circuits est tout sauf pratique, que ce soit à utiliser ou a visualiser. L’idée est donc d’ajouter des blocks spéciaux de mémoire.
Un block mémoire dans TICS.
- ADDR. IN est l’addresse du selecteur d’entrée. Il permet de choisir le segment de données à lire.
- ADDR. OUT est la sortie directement connectée à ADDR. IN, et permet de chainer les blocks mémoire horizontalement.
- DATA IN (optionnel) est l’entrée des données, utilisé en général pour écrire des données sur le segment de données spécifié via ADDR. IN.
- DATA OUT est généralement utilisé pour lire la mémoire sur le segment de données choisis, mais il applique aussi un Or binaire entre DATA IN et les données lues (s’il y en a sur ADDR. IN).
- SET IN (optionnel) permet d’écrire des données sur la mémoire si activé.
- SET OUT (optionnel) sont les sorties directement connectées à SET IN pour chainer les blocks.
- DISABLED (optionnel) désactive les opérations de lecture/écriture sur le segment de données si activé.
On peut initialiser le contenu d’une mémoire en dessinant directement dedans.
Un block mémoire initialisé dans TICS.
Grace aux blocks mémoire, on peut desormais créer des RAM complètement fonctionnelles facilement.
Une petite RAM de 64 octets.
Une grosse RAM de 1ko.
Cliquer pour animer.
Problèmes
Bien que complète, cette première itération de TICS souffre de plusieurs défauts. Le plus gros défaut est que ce paradigme n’est pas réaliste, et ne permet pas de simuler des circuits existants.
Ensuite, les sous circuits sont compliqués à maitriser et à utiliser correctement, et donnent plus l’impression d’être un trick pour combler un trou qu’une réelle feature.
Ils ont néanmoins l’avantage de tenir leurs promesses au niveau des performances. Cependant, on ne peut pas les orienter, ce qui peut poser problème selon le design que l’on fait.
Même problème avec les mémoires qui ne sont pas orientables. De plus, cette feature est difficile à “compiler” et rend la simulation de circuit plus difficile à optimiser.
Un calculateur fait avec TICS
Malgrès les défauts, il est possible de créer des structures complexes. Voici un petit proof of concept de CPU capable de calculer la suite de Fibonnacci.
Un CPU basique qui calcule la suite de Fibonacci.
fib(13) = 233 = 0xE9.
Cliquer pour animer.