Als Übung versuche ich, eine Implementierung von Conways Spiel des Lebens in einfacher digitaler Logik zu entwerfen. Ich könnte das Ganze tun, indem ich eine 9-Variablen-Funktion minimiere, aber ich stelle mir vor, dass das immer noch ziemlich groß sein wird. Eines der Kernelemente des Algorithmus ist die Bestimmung, wie viele Ihrer 8 Nachbarn "leben".
Was ist bei 8 Eingängen der einfachste Weg, um festzustellen, wie viele eingestellt sind? Insbesondere brauche ich einen Ausgang, der hoch ist, wenn 2 eingestellt sind, und einen Ausgang, der hoch ist, wenn 3 eingestellt sind.
Meine Hauptidee besteht jetzt aus einem PISO-Schieberegister, einem Zähler und einem 3: 8-Decoder, aber ich brauche so ziemlich einen Mikrocontroller, um all das anzutreiben. Es scheint nicht so kompliziert von einer Funktion zu sein. Vielleicht würde auch ein 256x2-ROM funktionieren, aber meine Suche hat keinen solchen Teil ergeben.
Ich weiß, dass jedes Bild mit 10 IO dies trivial tun kann, aber ich möchte es so minimal wie möglich implementieren.
quelle
Was ist minimal? Der Mikrocontroller besteht nur aus einem Teil und kann das Ergebnis mit einer minimalen Verzögerung (<1 s) erzeugen . Mit 54 Cent ist der ATTiny20 der billigste Mikrocontroller mit 10 E / A bei Digikey.μ
Die Nachschlagetabelle besteht ebenfalls nur aus einem Teil und ist schneller als der Mikrocontroller. Vergessen Sie parallele EEPROMs, sie sind teuer. Verwenden Sie einen byteweiten parallelen Flash . Dieser ist 512 kByte, das ist 2000-mal mehr als das, was Sie brauchen, aber es ist die billigste Lösung (1 Dollar). Und Sie können 6 weitere 1-Bit-Funktionen zum gleichen Preis hinzufügen.
Sie können auch eine CPLD verwenden . Schreiben Sie die Funktion in VHDL oder Verilog als eine lange SOP-Anweisung (Sum Of Products) und lassen Sie den Synthesizer die Logik erstellen.
Das Schieberegister ist in Ordnung, wenn Sie auf das Ergebnis warten können. Dies ist die langsamste Lösung.
Schließlich können Sie dies mit Logikgattern tun , aber Sie werden viel Zeit damit verbringen, die SOP auf ihre minimale Form zu reduzieren, wenn Sie alle grundlegenden Funktionen ausführen möchten. Rocketmagnet hat die richtige Idee, Addierer zu verwenden, aber seine Zahlen sind falsch: Ein 1-Bit-Halbaddierer ergibt 2 Bit, nicht 3. Das Addieren der Ausgänge der Halbaddierer zwei mal zwei erfordert also zwei 2-Bit-Halbaddierer, was zwei 3- ergibt. Bit Ergebnisse. Verwenden Sie einen 3-Bit-Halbaddierer, um das 4-Bit-Ergebnis zu erhalten. Bei Verwendung von 1-Bit-Volladdierern benötigen Sie nur einen 2-Bit-Addierer.
quelle
Hybride parallel-sequentielle Schaltungen sind tendenziell viel kompakter als rein parallele Schaltungen. Wenn Sie beispielsweise die Regeln so anpassen, dass eine 3x3-Box die Zelle in der Mitte tot macht, wenn weniger als drei lebende Zellen oder mehr als vier vorhanden sind, und sie live dreht, wenn genau drei lebende Zellen vorhanden sind (das Verhalten unter diesen) neue Regeln stimmen mit dem Original überein), man kann die Logik vereinfachen, indem man eine zweistufige Sequenz ausführt:
Das Array
tempVal[x,y]hat zwei Bits pro Zelle; Die letztere Operation summiert drei solcher Zahlen, um einen Wert von 0 bis 9 zu erzeugen (obwohl alle Werte über vier gleichwertig sind), der dann verwendet werden kann, um einen Einzelbit-Live / Dead-Status für die nächste Generation zu berechnen.Übrigens wäre eine Alternative zum Berechnen einer arithmetischen Summe in der zweiten Stufe und zum Untersuchen des Werts, TempVal [x, y] in eine One-Hot-Darstellung umzuwandeln und dann explizit nach einer der neun Wertekombinationen zu suchen, die drei ergeben würden Zellen oder eine der zwölf, die vier ergeben würde.
quelle