Ich muss eine Anwendung zum Erstellen von Logikschaltungen und zum Sehen der Ergebnisse machen. Dies ist vor allem für den Einsatz in A-Level (UK, 16-18 Jahre alt) in der Regel Computing-Kurse.
Ich habe noch nie Anwendungen wie diese gemacht, bin mir also nicht sicher über das beste Design, um die Schaltung zu speichern und die Ergebnisse zu bewerten (mit einer wiederholbaren Geschwindigkeit, sagen wir 100Hz auf einem 1,6Ghz Single-Core Computer).
Anstatt die Schaltung aus den Basisgattern (und, oder, n und usw.) aufzubauen, möchte ich erlauben, dass diese Gatter verwendet werden, um "Chips" herzustellen, die dann in anderen Schaltungen verwendet werden können (z. B. wenn Sie möchten) einen 8-Bit-Register-Chip oder einen 16-Bit-Addierer erstellen.
Das Problem besteht darin, dass die Anzahl der Gatter mit solchen Schaltungen massiv zunimmt, so dass, wenn die Simulation an jedem einzelnen Gatter arbeitete, 1000 Gatter simuliert werden müssten, also muss ich diese Komponenten vereinfachen, die in einem Schaltkreis angeordnet werden können damit sie schnell simuliert werden können.
Ich habe überlegt, für jede Komponente eine Wahrheitstabelle zu generieren, dann könnte die Simulation eine Nachschlagetabelle verwenden, um die Ausgaben für eine gegebene Eingabe zu finden. Das Problem ist mir jedoch aufgefallen, dass die Größe solcher Tabellen massiv mit Eingaben steigt. Wenn ein Chip 32 Eingänge hat, dann benötigt die Wahrheitstabelle 2 ^ 32 Zeilen. Dies verwendet eine große Menge an Speicher in vielen Fällen mehr als es zu verwenden ist, ist also nicht praktisch für nicht-triviale Komponenten, es wird auch nicht mit Chips arbeiten, die ihren Zustand speichern können (zB Register), da sie nicht einfach dargestellt werden können Tabelle der Ein- und Ausgänge.
Ich weiß, ich könnte nur Dinge wie Register-Chips kodieren, aber da dies für Bildungszwecke ist, möchte ich, dass die Leute ihre eigenen Komponenten erstellen und die Implementierungen für Standard-Komponenten ansehen und bearbeiten können. Ich überlegte, ob solche Komponenten mit Code (zB dlls oder einer Skriptsprache) erstellt und bearbeitet werden können, so dass zB ein Addierer als "output = inputA + inputB" dargestellt werden kann, aber davon ausgegangen wird, dass die Schüler genug Programmiert haben gegebene Sprache, um solche Plugins verstehen und schreiben zu können, um die Ergebnisse ihrer Schaltung nachzuahmen, die wahrscheinlich nicht der Fall ist ...
Gibt es eine andere Möglichkeit, eine boolesche Logikschaltung zu verwenden und diese automatisch zu vereinfachen, damit die Simulation die Ausgaben einer Komponente schnell bestimmen kann?
Wie beim Speichern der Komponenten dachte ich darüber nach, eine Art von Baumstruktur zu speichern, so dass jede Komponente ausgewertet wird, sobald alle Komponenten, die mit ihren Eingängen verknüpft sind, ausgewertet werden.
zB in Betracht ziehen: A.B + C Der Simulator würde zuerst das UND-Gatter auswerten und dann das ODER-Gatter unter Verwendung des Ausgangs des UND-Gatters und C auswerten.
Es ist mir aber gerade eingefallen, dass in Fällen, in denen die Ausgänge sich mit den Eingängen verknüpfen, ein Deadlock entsteht, weil dort niemals alle Eingänge ausgewertet werden ... Wie kann ich das überwinden, da das Programm nur einen auswerten kann? Tor zu einer Zeit?
Wenn Sie Schleifen (Ausgänge, die auf Eingänge verweisen) nicht zulassen können, können Sie das Problem erheblich vereinfachen. In diesem Fall gibt es für jeden Eingang genau einen bestimmten Ausgang. Zyklen können jedoch die Ausgabe nicht decideable (oder vielmehr, sich ständig ändern).
Das Auswerten einer Schaltung ohne Schleifen sollte einfach sein - verwenden Sie einfach den BFS-Algorithmus mit "Junctions" (Verbindungen zwischen Logikgattern) als Elemente in der Liste. Beginnen Sie mit allen Eingängen aller Gatter in einem "undefinierten" Zustand. Sobald ein Gatter alle Eingänge "definiert" hat (entweder 1 oder 0), berechnen Sie seine Ausgabe und fügen Sie seine Ausgangsverbindungen zur BFS-Liste hinzu. Auf diese Weise müssen Sie jedes Gatter und jede Kreuzung nur einmal auswerten.
Wenn es Schleifen gibt, kann der gleiche Algorithmus verwendet werden, aber die Schaltung kann so gebaut werden, dass sie nie zu einem "Rest" kommt und einige Verbindungen immer zwischen 1 und 0 wechseln.
OOps, tatsächlich kann dieser Algorithmus in diesem Fall nicht verwendet werden, weil die geloopten Gatter (und Gatter, die von ihnen abhängen) für immer als "undefiniert" bleiben würden.
Vielleicht möchten Sie sich die Kurs-Software von From Nand To Tetris in 12 Schritten ansehen. Es gibt ein Video, das auf youtube darüber spricht.
Die Kursseite ist: Ссылка
Sie sind nicht die erste Person, die ihren eigenen Schaltungssimulator bauen möchte; -).
Mein Vorschlag ist, sich auf eine minimale Menge von Primitiven festzulegen. Als ich mit meinem begann (was ich eines Tages fortsetzen werde ...), hatte ich zwei Primitive:
A und B , eine Ausgabe ist A and not B . Offensichtlich missbrauche ich die Terminologie etwas, ganz zu schweigen von der Vernachlässigung der Feinheiten der Elektronik. Zum zweiten Punkt empfehle ich, zu Drähten zu abstrahieren, die wie ich 1s und 0s tragen. Ich hatte eine Menge Spaß dabei, Diagramme von Gattern und Addierern zu zeichnen. Wenn Sie sie zu Schaltkreisen zusammensetzen und eine Box um das Set zeichnen können (mit Ein- und Ausgängen), können Sie größere Dinge wie Multiplikatoren bauen.
Wenn Sie etwas mit Loops wollen, müssen Sie eine gewisse Verzögerung einbauen - also muss jede Komponente den Zustand ihrer Ausgänge speichern. In jedem Zyklus aktualisieren Sie alle neuen Zustände aus den aktuellen Zuständen der vorgelagerten Komponenten.
Bearbeiten In Bezug auf Ihre Bedenken bezüglich der Skalierbarkeit, wie wäre es mit der Methode der ersten Prinzipien der Simulation jeder Komponente in Bezug auf ihren Zustand und Upstream-Nachbarn, aber Möglichkeiten zur Optimierung von Teilschaltungen bieten:
Wenn Sie eine Unterschaltung S mit den Eingängen A[m] mit m & lt; 8 (sagen wir maximal 256 Zeilen) und gibt B[n] und keine loops aus, erzeugt die Wahrheitstabelle für S und benutzt diese. Dies könnte automatisch für identifizierte Teilschaltungen erfolgen (und wiederverwendet werden, wenn die Teilschaltung mehr als einmal auftritt) oder durch Wahl.
Wenn Sie eine Unterschaltung mit Schleifen haben, können Sie möglicherweise trotzdem eine Wahrheitstabelle erzeugen. Es gibt Festkomma-Methoden, die hier helfen können.
Wenn Ihre Teilschaltung Verzögerungen aufweist (und sie für die einschließende Schaltung von Bedeutung sind), kann die Wahrheitstabelle Zustandsspalten enthalten. Z.B. wenn die Teilschaltung Eingang A, inneren Zustand B und Ausgang C hat, wobei C & lt; - A und B, B & lt; - A, könnte die Wahrheitstabelle sein:
A B | B C
0 0 | 0 0
0 1 | 0 0
1 0 | 1 0
1 1 | 1 1
Wenn Sie eine Teilschaltung haben, die der Benutzer anerkennt, implementiert ein bestimmtes bekanntes Muster wie "Addierer", bieten Sie eine Option für die Verwendung einer fest codierten Implementierung für die Aktualisierung dieser Teilschaltung, anstatt ihre inneren Teile zu simulieren. p>
Wenn ich einen Schaltungs-Emulator gemacht habe (leider auch unvollständig und nicht veröffentlicht), so habe ich hier Schleifen behandelt:
Wenn die E0-Änderung auftritt, wird eine Level-1-Liste aller betroffenen Elemente gespeichert. Wenn ein Element bereits in dieser Liste erscheint, wird es in einer neuen Level-2-Liste gespeichert, aber es benachrichtigt seine Beobachter nicht weiter. Wenn die Sequenz, mit der E0 begonnen hat, keine neuen Elemente mehr benachrichtigt, wird die nächste Warteschlangenebene behandelt. Dh: die Sequenz wird gefolgt und abgeschlossen für das erste Element, das zu Level-2 hinzugefügt wird, dann das nächste zu Level-2 hinzugefügt wird, usw. bis alle von Level-x abgeschlossen sind, dann bewegt man sich zu Level- (x + 1)
Dies ist keineswegs vollständig. Wenn Sie mehrere Oszillatoren haben, die unendliche Loops ausführen, dann kann man, egal in welcher Reihenfolge Sie sie aufnehmen, verhindern, dass der andere jemals an die Reihe kommt. Mein nächstes Ziel war es, dies zu verringern, indem ich Schritte mit clock-basierter Synchronisierung anstelle von kaskadierenden Kombinatorik-Programmen beschränke, aber in meinem Projekt bin ich noch nie so weit gekommen.
Sie könnten alle gängigen Codes fest codieren. Erlauben Sie ihnen dann, ihre eigenen aus den fest codierten zu bauen (die Low-Level-Gatter enthalten würden), die durch Auswertung jeder Subkomponente ausgewertet würden. Wenn schließlich einer ihrer "Chips" weniger als X Eingänge / Ausgänge hat, könnten Sie ihn in eine Nachschlagetabelle "optimieren". Vielleicht erkennen, wie häufig es ist und nur dies für die am häufigsten verwendeten Y-Chips tun? Auf diese Weise haben Sie einen guten Kompromiss zwischen Geschwindigkeit und Platz.
Du könntest immer JIT kompilieren die Schaltungen ...
Da ich nicht wirklich darüber nachgedacht habe, bin ich mir nicht sicher, welchen Ansatz ich nehmen würde. Aber es wäre möglicherweise eine hybride Methode, und ich würde definitiv auch beliebte "Chips" programmieren / p>
Als ich herumspielte, um eine Simulationsumgebung mit "digitaler Schaltung" zu erstellen, hatte ich jede definierte Schaltung (ein Basisgate, einen Mux, einen Demux und ein paar andere Primitive) mit einer Transferfunktion (also einer Funktion) (berechnet alle Ausgänge basierend auf den vorhandenen Eingängen), eine "Agenda" -Struktur (im Grunde eine verkettete Liste von "wann eine bestimmte Übertragungsfunktion aktiviert werden soll"), virtuelle Leitungen und eine globale Uhr.
Ich setze die Drähte willkürlich so ein, dass sie die Eingänge hart modifizieren, wann immer sich der Ausgang ändert, und den Vorgang des Änderns eines Eingangs auf einer beliebigen Schaltung, um eine Übertragungsfunktion zu planen, die nach der Gatterverzögerung aufgerufen wird. Damit konnte ich sowohl getaktete als auch nicht getaktete Schaltungselemente unterbringen (ein getaktetes Element wird so eingestellt, dass seine Übertragungsfunktion bei "nächster Taktübergang plus Gate-Verzögerung" ausgeführt wird, jedes nicht getaktete Element hängt nur von der Gate-Verzögerung ab). p>
Nie wirklich herumgekommen, um eine GUI dafür zu bauen, also habe ich den Code nie veröffentlicht.
Tags und Links design boolean-logic