ich habe 8 Leitungen, die an oder aus sein können. Ich möchte die Anzahl der Leitungen wissen, die "an" sind.
Bisher mache ich das mit Volladdieren, 2 erfassen die ersten 6 Leitungen. Die beiden gehen in einen 3bittigen Volladierer, an dessen Carry In bit 0 geht Leitung sieben, dann noch einen 3bittigen VA, in den geht der vorherige 3bit VA und ins 0bit geht noch die 8te Leitung.
Zum Hintergrund:
Es geht um ein Logiksimulationsspiel, dort hat man einzelne Logikgatter als Bausteine.
Ich versuche gerade, meine "Game of Life"-Zelle kompakter zu bekommen.
Guter Tipp. Er braucht allerdings nur 8 Eingänge, nicht 16.
richtig, aber darum soll es hier nicht gehen. Es ist kein Ersatz gesucht.
Die Frage ist, geht es mit weniger Gattern, wenn man keine Tabelle ausm Speicher befragen will, sondern es tatsächlich mit einzelnen Gattern machen möchte.
Grundsätzlich ist das eine Addition. D.h. Addierer sind grundsätzlich die richtigen Bausteine. Du kannst die Addierer baumartig anordnen, dann kommst du zumindest am Anfang mit Halbaddierern aus, zusätzlich ist die Wortbreite weiter unten im Baum kleiner.
Wozu eine FSM? Ein Addierer ist vollständig kombinatorisch, da braucht es keinen Speicher oder Takt. Also sind auch 8 Addierer reine Kombinatorik und brauchen keinen Takt.
Also reicht ein simples EPROM mit 8 Adressleitungen, das mit dem passenden Bitmuster gefüllt wird.
Beginnend ab Adresse 0 sind das die Werte: 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, usw...
BTW: Es würde ein 2kByte EPROM (256×8) reichen, und selbst davon werden nur 3/8 zum "Rechnen" verwendet.
Noch eine kleine Hürde, die mir im Eingangspost entfallen ist:
Es gibt kein ODER-Gatter im Spiel. Man kann Ausgänge zwar nicht direkt zusammenschalten, aber auf einem "Pin" zusammenführen, dann sind sie quasi wired-Or.
Im Bildchen sind die ODER nur, weils Falstad anderd ist.
Ein Volladdierer ist also ein bischen kleiner, als er sein sollte.
8 Eingänge mit 4 Halbaddierern zusammenfassen. Die dann mit 2 2bittigen VA zusammenfassen, die dann in nem 3bittigen VA zusammenführen.
Vier HA entsprechen etwa 2 VA (wegen dem gesparten ODER wegen wired-or), dann 4 VA für 2 2bittige und dann 3 VA für den dreibittigen. Sind 9 VA.
ist bekannt, ich war aber nie sonderlich gut darin, die Logik zusammenzukomprimieren. Wenn dies dann das in Logik umsetzen kein Problem, das dann knackig kompakt zu bekommen, lag mir nie so... daher ja auch die Nachfrage hier.
ich kann mein Multimeter schlecht in ein Computerspiel halten. Es geht um die Logik, die ist völlig unabhängig vom exakten Wert der jeweiligen Logikpegel.
Wozu eine FSM? Ein Addierer ist vollständig kombinatorisch, da braucht
es keinen Speicher oder Takt. Also sind auch 8 Addierer reine
Kombinatorik und brauchen keinen Takt.
Also reicht ein simples EPROM mit 8 Adressleitingen, das mit dem
passenden Bitmuster gefüllt wird.
BTW: Es würde ein 2kByte EPROM (256×8) reichen, und selbst davon werden
nur 3/8 zum "Rechnen" verwendet.
Ich habe mehrmals gesagt, dass das hier keine Möglichkeit ist. Warum fängt jetzt sogar ein Moderator an, mit darum zu diskutieren, statt die Diskussion in diebgewünschte Richtung zu lenken?
Manmanman, ich weiß schon, warum ich nur noch so selten Fragen stelle...
ich glaub, der erste 3bittige VA sollte 2bittig ausreichen. mit dem Carry sinds ja 3 bit, das reicht um die maximal 2mal 3, also 6, zusammenzufassen, die an den ersten beiden 1 bittigen VA hängen....
Ich habe mehrmals gesagt, dass das hier keine Möglichkeit ist. Warum
fängt jetzt sogar ein Moderator an, mit darum zu diskutieren, statt die
Diskussion in diebgewünschte Richtung zu lenken?
DU hast gefragt ob das mit weniger Gatter geht.
Die Antworten daraufhin haben Lösungen mit weniger bis keine Gatter aufgezeigt.
DU hast direkt am Anfang vergessen zu erwähnen das es bei einer "Gatterlösung" bleiben soll.
Also fass dir an die eigene Nase.
Das hoert sich fuer mich so an, als haetten sich die Herren Veitch, Karnaugh, Quine und McCluskey mit sowas schon vor Jahren beschaeftigt: Also der Vereinfachung von Logikfunktionen...
Ich glaub', dieses Rad muss nicht nochmal erfunden werden, nur verstanden.
Man könnte das auch analog lösen: die 8 Spannungen addieren und auf einem Voltmeter anzeigen (oder mit einem D/A Wandler wieder digitalisieren). Aber auch das wäre nicht im Sinne des TO.
DU hast direkt am Anfang vergessen zu erwähnen das es bei einer
"Gatterlösung" bleiben soll.
Also fass dir an die eigene Nase.
Habe die Gatter aber direkt erwähnt und noch ein Bildchen dazugeliefert, so dass eigentlich relativ klar sein sollte, wprum es geht.
Und im Nachgang dann noch mehrmals ziemlich unmissverständlich gesagt, worum es geht. Aber es wird um PROMS und uCs lamentiert.
d.h man muss doch nur 2 und 3 Nachbarn dekodieren:
Zelle lebt: 2 oder 3 Nachbarn bleibt, sonst stirbt sie.
Zelle leer: bei 3 Nachbarn neue geboren.
ich hab beide Versionen implementiert. Fest verdrahtetes Originalregelwerk und per Schalter wählbar ob nichts passiert, lebt oder stirbt bei 0 bis 8 Nachbarn.
Also für jeweils für 0 lebt, stirbt, bleibt wie es ist, und für 1 usw.
Man könnte das auch analog lösen: die 8 Spannungen addieren und auf
einem Voltmeter anzeigen (oder mit einem D/A Wandler wieder
digitalisieren). Aber auch das wäre nicht im Sinne des TO.
eben, den ich kann immer noch kein MM in ein Computerspiel stecken....
Ich glaub', dieses Rad muss nicht nochmal erfunden werden, nur
verstanden.
Und hast dus verstanden und kannst eine Lösungit weniger Gatterm zeigen
oder bist du mal wieder nur am dummrumschwätzen?
Ja, genau so etwas wollen die Helfenden hören, da ist man doch gleich viel motivierter.
Ich glaube du schaffst das schon alleine. Ist ja eh ein Gedankenspiel, also nicht zeitkritisch. Da kannst du mal schön Google benutzen, oder eine KI. Die gibt dir wenigstens keine Widerworte.
Ich habe mehrmals gesagt, dass das hier keine Möglichkeit ist. Warum
fängt jetzt sogar ein Moderator an, mit darum zu diskutieren, statt die
Diskussion in diebgewünschte Richtung zu lenken?
Manmanman, ich weiß schon, warum ich nur noch so selten Fragen stelle...
Und weiß weshalb ich mir bei solchen Threads keine Mühe gebe. Die Lustlosigkeit beginnt schon bei dem „Schaltplan“ aus dem Eingangspost.
Das Zeichnen der Schaltung erspare ich mir, denn das hast du bereits
getan. Du musst in deiner Schaltung nur alle ungenutzten Leitungen und
alle Gatter ohne Funktion löschen :)
Das hoert sich fuer mich so an, als haetten sich die
Herren Veitch, Karnaugh, Quine und McCluskey mit sowas
schon vor Jahren beschaeftigt:
Also der Vereinfachung von Logikfunktionen...
Sicher -- unter der Voraussetzung eines ZWEISTUFIGEN
Schaltnetzwerkes.
Ich glaub', dieses Rad muss nicht nochmal erfunden
werden, nur verstanden.
Ich vermute, im vorliegenden Fall ist eine Baumstruktur
günstig(er), und die ist gerade nicht zweistufig...
Und hast dus verstanden und kannst eine Lösungit weniger Gatterm zeigen
oder bist du mal wieder nur am dummrumschwätzen?
Ja, ich denke schon, dass ich das verstanden habe. Vor meinem geistigen Auge zeigt sich fuer das LSB deiner Addition ein KV-Diagramm mit "Schachbrett"muster - unschoen zu vereinfachen :-)
[EDIT: ups, nee mein geistiges Auge hat sich verguckt, das stimmt so nicht.]
Nein, ich weiss so aus'm Bauch raus nicht, wieviele Gatter das dann insgesamt braucht.
Ich weiss ja nichtmal, was du fuer Gatter meinst, also zaehlt ein XOR als "ein Gatter", wieviele Eingaenge darf "ein Gatter" bei dir haben?
Aber da du schon so nett nachfragst, zieh' ich es doch vor, hier nur wieder dumm rumzuschwaetzen.
Bit0 des Ergebnisses ist m.E. gerade die Parität;
das läuft auf ein XOR über alle Bits hinaus. Kann
man mit einem 4/2/1-Baum aus 2er XOR-Gattern machen.
Bit3 ist ein AND über alle Eingänge; das kann man
mit einem 4/2/1-Baum aus 2er AND-Gattern machen.
Bit1 ist die Parität über die Paare gesetzter
Eingänge; zu den Paaren, die die unterste Stufe des
AND-Baumes direkt anzeigt, kommen aber noch die hinzu,
die aus zwei einzelnen Eingängen in zwei benachbarten
Zweiergruppen bestehen.
Letzere kann man aus der untersten Stufe des XOR-Baumes
ablesen.
Wie Bit2 zu bilden ist, überlege ich mir, wenn ich vom
Spazierengehen und Einkaufen wieder zu Hause bin und
eine Skizze gemacht habe...
Ja, genau so etwas wollen die Helfenden hören, da ist man doch gleich
viel motivierter.
zu denen gehört der gute Weka hier aber nicht....
oder inwieweit gehört man zu den Helfenden, wenn man explizit ausgeschlossenes vorschlägt?
Gut, das war jetzt nicht des Wekas Makel....
zu denen gehört der gute Weka hier aber nicht....
oder inwieweit gehört man zu den Helfenden, wenn man explizit
ausgeschlossenes vorschlägt?
Gut, das war jetzt nicht des Wekas Makel....
Aeeeeh, das klingt jetzt aber doch arg verwirrt.
Wenn du mich einfach so nicht leiden kannst, ist das OK, du musst das nicht versuchen zu begruenden.
Aeeeeh, das klingt jetzt aber doch arg verwirrt.
Wenn du mich einfach so nicht leiden kannst, ist das OK, du musst das
nicht versuchen zu begruenden.
Das ich dich nicht so recht leiden kann, ist schon richtig. Da du diesmal aber nicht "nicht-gewünschtes" "gesagt" hast, sondern einfach Allgemeinplätze aus der Logik aufgezählt hast, unterlagst du halt nicht dem über das ich mich beschwerte. Dinge vorschlagen, die ausgeschlossen sind.
Und da ich mich darüber beschwerte, dass das getan (EPROMs, uCs vorgeschlagen, obwohl nicht verfügbar bspw) wurde, und auch an dir rummäkelte, musste ich dich von der Mäkelei ja ausnehmen.
OK, da wird wieder mal das Forumsniveau nach unten ausgelotet ...
Also es ist schlicht unmöglich die möglichen 9 Zuständer der 8 Eingangsleitungen mit 3 bit abuibilden, da braucht es einen Outputvektor von 4 bit.
Statt Volladder und so was konnte man aus der 74xxx Familie gleich einen kleinen PROM (471 glaube ich) oder binär decimal encoder (147 oder so verwenden. Letzteres findet man nicht selten als CS-Adressdecoder auf SBC.
Bei FPGA's vielleicht was aus der 6-LUT ecke mit aktivierten Mux und Mux8 und bei Cologne-chip GateMate hat es doch 8 LUT's.
Abgesehen davon, das man diese Frage so bei jedem Vorstellungsinterview als Digitaldesigner gestellt bekommt.
sondern einfach
Allgemeinplätze aus der Logik aufgezählt hast,
Aeeehm - das sind nicht Allgemeinplaetze aus der Logik, sondern die Namen der Entwickler von Verfahren, die genau deine Problemstellung loesen.
Aber nachdem du schon im Eingangspost munter zwischen Halb/Volladdierern und Gattern hin- und herspringst - wie sollte ich da eine Anzahl von Gattern angeben koennen, wenn du nicht definierst, was fuer dich ein Gatter ist?
In deinem Fall hast du ein Schaltnetz mit 8 Eingaengen und 4 Ausgaengen (weil du die Ergebnisse 0,1,2,3,4,5,6,7,8 darstellen koennen musst.
Das LSB dieses 4bit Ausgangs ist ein XOR-Gatter mit 8 Eingaengen, wie ich mich mit mir und Hippelhaxe einig werden konnte.
Das MSB dieses 4bit Ausgangs ist ein AND-Gatter mit 8 Eingaengen.
Zaehlt das jetzt als 2 Gatter oder doch irgendwie nicht?
Die 2 restlichen Bit des Ausgangsworts darfst du selber loesen, wenn dir was dran liegt.
Da geht 1 Signal hinein, und 1 Signal kommt heraus. Das Ausgangssignal
ist gleich dem Eingangssignal. Wie nennt man noch einmal die komplexe
Schaltung, die diese Funktion realisiert?
Statt Volladder und so was konnte man aus der 74xxx Familie gleich einen
kleinen PROM (471 glaube ich) oder binär decimal encoder (147 oder so
verwenden. Letzteres findet man nicht selten als CS-Adressdecoder auf
SBC.
Ebenso wie ich kein Multimeter in die Sumilation halten kann, kann ich kein Chips, welcher Logikfamilie auch immer, in die Simu schmeißen.
In der simulierten Welt besteht ein Halbaddierer aus einem UND- und einem XOR-Gatter. Der Volladdierer aus 2 Halbaddierern, da dass Oder wired umgesetzt wird. Der eine Platz dafür ist also mehr oder weniger umsonst.
Falls es dich interessiert, das Spiel heißt Logic World, Es gibt UND mit 2-4 Eingängen, XOR mit 2 Eingängen, D-FlipFlop, Relais, Buffer, und n paar Taster und Anzeigen... gabs mal fürn Appel und Ei auf Steam.
Ein 8:! Multiplexer (74xx151) , ein 3 bit Zähler der diesen Multiplexer steuert und bei 8 anhält, ein weiterer 3 bit Zähler (74XX393) der pro Takt nur inkrementiert wenn der Multiplexer eine 1 liefert, aber dazu muss Steuerungslogik, eine Taktsignalquelle, keine Ahnung wie viele weitere Chips.
Da geht 1 Signal hinein, und 1 Signal kommt heraus. Das Ausgangssignal
ist gleich dem Eingangssignal. Wie nennt man noch einmal die komplexe
Schaltung, die diese Funktion realisiert?
da hatte noch die Carryverbindung gefehlt, so siehts nu fertig aus, bischn andere Anordnung als bei dir, aber es kommt das gewünschte raus.
Diese Information hätte in's OT gehört, um diesem irgendeinen Sinn zu
geben.
Fiel mir dann auch relativ kurz nachm absenden auf und ich hab ja nachgeliefert. Das es um ein Spiel geht, sagte ich in meinem 2ten oder dritten Post...
Oder mich hats wirklich interessiert und der übliche Mob wollte einem wieder was aufdrücken, was gar nicht zur Lösung passt. Den guten Weka mal explizit ausgenommen, der ist beim Thema geblieben.
Ich wollte halt mal eben schnell nachfragen, da gehen einem die wichtigen Details manchmal flöten, immerhin hab ich nen Schaltplan gemalt, direkt Opening....
Das es um ein Spiel geht, sagte ich in meinem 2ten oder
dritten Post...
Aber nicht, welche "Gatter" verfügbar sind. Und das ist natürlich nach den Gesetzen der Logik der entscheidende Knackpunkt, wenn das Ziel ist, die Zahl eben dieser "Gatter" zum minimieren.
also ich würde stur eine Wahrheitstabelle aufstellen und dann z.B. mit Quine Mc Clusky minimieren, oder was man heute so nimmt. Vermutlich gibt es dafür tausende Tools. Da bin ich dann sicher, dass ich den minimalen Aufwand an Gattern etc. habe. Oder ich bastel ein riesiges KV-Diagramm, aber das wird eher unübersichtlich ;-)
Oder muss die Lösung "kreativ" gefunden/erarbeitet werden?
Ja und, im FPGA wird daraus 256x8 ROM oder ähnlich im SRAM, quasi null Resourcen in halbwegs modernem FPGA und mit 1cycl Latenz, schneller geht fast nicht.
Ansonsten lahm und zig LUTs verbastelt
Und wenn immer noch zu viel, dann halt in 2x 16x8 LUT aufteilen für 2x 4 Datenleitungen und nachher addieren.
also ich würde stur eine Wahrheitstabelle aufstellen und
dann z.B. mit Quine Mc Clusky minimieren, oder was man
heute so nimmt. Vermutlich gibt es dafür tausende Tools.
Da bin ich dann sicher, dass ich den minimalen Aufwand
an Gattern etc. habe.
NEIN !
<Gebetsmühle>
Quine/McClusky, Karnaugh/Veitch etc. liefern minimalen
Aufwand für zweistufige Schaltnetzwerke !
Wenn man mehr Stufen (=längere Signalpfade, längere
Laufzeit) zulässt, kann es immer noch Lösungen mit
geringerem Aufwand an Gattern geben.
</Gebetsmühle>
Es ist Deiner Aufmerksamkeit sicher nicht entgangen,
dass die Lösungen von Yalu oder J.T. mehr als zwei
Stufen enthalten...
Aber wenn es doch nur 8 Leitungen sind, und er die Anzahl der HIGH Pegel zählen will, können das nur 8 HIGH Pegel sein. Ich gebe zu, Logik war noch nie meine Stärke. Mein HIGH Pegel ist jedenfalls nicht höher als Acht. Bitte ein Bit!
Er will mir auch nicht glauben, dass Windows versteckte Dat(ei)en auf Laufwerk C speichert, die man im Explorer nicht sehen kann. Obwohl sein eigener Screenshot das ebenso so belegt, wie meiner.
Beitrag "Re: Windows 11: Ganze Partition in Verzeichnis kopieren"
Quine/McClusky, Karnaugh/Veitch etc. liefern minimalen
Aufwand für zweistufige Schaltnetzwerke !
OK, kann ja sein, dass ich da nicht komplett alle Details berücksichtigt habe. Aber warum "Gebetsmühle"? Habe hier im Forum das Thema noch nirgends gesehen. Links? Also ich bitte um Vergebung! ;-)
Verstehen tu ich es dennoch nicht: Ich kann doch, wenn mir die (realen) Laufzeiten und damit verbundene "Fehler" egal sind, aus jeder kombinatorischen Aufgabe eine Wahrheitstabelle erstellen, und diese dann minimieren?! Wie viele Stufen das Netzwerk dann letztendlich hat, hängt ja von der Realisierung ab. Kannst Du mir Links zum Thema geben?
Quine/McClusky, Karnaugh/Veitch etc. liefern minimalen
Aufwand für zweistufige Schaltnetzwerke !
OK, kann ja sein, dass ich da nicht komplett alle Details
berücksichtigt habe. Aber warum "Gebetsmühle"?
Ein paar Beiträge weiter oben hatte ich den guten
WeKa auch schon daran erinnert, dass die üblichen
Verfahren nur bei zweistufigen Netzwerken
funktionieren...
Also ich bitte um Vergebung! ;-)
Alles gut... war nicht böse gemeint, die "Gebetsmühle".
Verstehen tu ich es dennoch nicht: Ich kann doch, wenn
mir die (realen) Laufzeiten und damit verbundene
"Fehler" egal sind, aus jeder kombinatorischen Aufgabe
eine Wahrheitstabelle erstellen,
Natürlich, ja.
Wahrheitswertetabelle wird häufig der erste Schritt beim
Entwurf sein.
und diese dann minimieren?!
Jein...nein: Vereinfachungen durch "Don't care", die sich
aus der Anwendung selbst ergeben, die berücksichtigt man
ja schon beim Aufstellen der WW-Tabelle.
Das ist aber nur ein (kleiner) Teil des Problems.
Wie viele Stufen das Netzwerk dann letztendlich hat,
hängt ja von der Realisierung ab.
Nee, umgekehrt: Für eine vernünftige Optimierung (Minimierung)
musst Du beim Entwurf schon wissen, welche Gatter Dir in der
realen Schaltung zur Verfügung stehen.
Triviales Beispiel: Du sollst irgend eine logische Funktion
mit drei Variablen realisieren; es sei bekannt, dass nur
8-auf-1-Multiplexer als Grundbausteine zur Verfügung stehen.
Dann bist Du mit dem Erfassen der WW-Tabelle bereits fertig;
weitere Optimierung unnötig: Ein 8-auf-1-Multiplexer kann
JEDE boolsche Funktion mit 3 Variablen darstellen, und es
ist immer EXAKT derselbe Aufwand notwendig...
Nichttriviales Beispiel: Gefordert wird ein 64bit-Paritäts-
prüfer.
Der Gatteraufwand hängt DRAMATISCH davon ab, welche Grund-
gatter erlaubt sind und wieviele Schaltungsstufen zulässig
sind. Überdies wird die WW-Tabelle astronomisch groß, wenn
man keine Tricks anwendet.
Als zweistufige NAND-NAND-Kombinatorik ist ein 64bit-Paritäts-
generator praktisch nicht auführbar, weil man Unmengen von
Gattern mit 64 Eingängen bräuchte.
Hat man nur XOR-Gatter mit zwei Eingängen, kommt man mit
63 Stück zum Ziel, die man zur Minimierung der Laufzeit
als Baum anordnet. Diese Baumstruktur sieht man aber
nicht aus der WW-Tabelle, das muss man WISSEN.
Hat man nur NAND mit zwei Eingängen, kommt man auch zum
Ziel, indem man erstmal ein paar NAND und Inverter zu
XOR kombiniert und dann die Baumstruktur von oben ver-
wendet. Diese kann man u.U. anschließend noch optimieren.
Kannst Du mir Links zum Thema geben?
Leider nicht... aber frag' doch im VHDL-Unterforum...
Nichttriviales Beispiel: Gefordert wird ein 64bit-Paritäts-
prüfer.
Der Gatteraufwand hängt DRAMATISCH davon ab, welche Grund-
gatter erlaubt sind und wieviele Schaltungsstufen zulässig
sind. Überdies wird die WW-Tabelle astronomisch groß, wenn
man keine Tricks anwendet.
Da stimme ich Dir natürlich zu. Aber bei "Paritätsprüfer" denkt man ja sofort an XOR. Überdies würde ich bei 64 Bit gar nicht erst anfangen, mit einer Tabelle zu arbeiten. ;-) Wäre aber mal interessant, das ganze für eine realistische Anzahl von Bits, z.B. 8, mit QMC zu exerzieren. Ich habe das nämlich noch nie gemacht. Für die üblichen Logikschaltungen reichte mir immer einfache boolsche Algebra, und mit FPGAs habe ich noch nichts gemacht.
Nach zwei Tagen immer noch nicht fertig mit Auskaspern ?!
Anbei ein Lehrbuchauszug (ISBN 0-13-082599-9) mit 'ner Implementierung für 32 Eingangsleitungen.
Daraus sollte man eine Variante für acht Eingänge ableiten können.
Mit diskreten NAND/XOR/ Gattergräben macht man sowas schon seit 50 Jahren nicht mehr, schliesslich hat die 74xxx serie (eingeführt 1966 !) auch Fulladder (x80) und 2Bit-adder (x82) und 4 bit adder (x83) oder auch 256x4bit PROM (x188).
"ich habe 8 Leitungen, die an oder aus sein können. Ich möchte die Anzahl der Leitungen wissen, die "an" sind."
Acht Leitungen können 256 Zustände einnehmen. Die darf man durchnummerieren von 0 bis 255 oder von 1 bis 256, es bleiben immer 256 Zustände.
Aber von 8 Leitungen können 0 bis 8 high sein, das sind neun mögliche Fälle. Die gesuchte "Anzahl" lässt sich nicht mit einer 3-Bit-Zahl angeben, sondern muss 4 Bit haben.
Die Fragestellung der Überschrift ist also nicht lösbar.
Eine 4-Bit-Lösung wäre möglich, dazu kann man z.B. vier KV-Diagramme zeichnen, für jedes Bit eines.
Die Fragestellung der Überschrift ist also nicht lösbar.
Wurde doch auch schon am Anfang geklärt, das es mit 3bittigem Volladdierer geht. Und der bringt ja praktischwerweise ein viertes Bit in Form des Carry Bits mit.
Aber haut euch ruhig weiter die Köppe drüber ein, ob man die LUTs besser FPGAt oder EPROMt, das mögen in der Raelität ja alles feine Lösungen sein, aufgrund mangelnder Existenz in dieser Spielwelt aber leider nicht umsetzbar.
Die Fragestellung der Überschrift ist also nicht lösbar.
Wurde doch auch schon am Anfang geklärt, das es mit 3bittigem
Volladdierer geht. Und der bringt ja praktischwerweise ein viertes Bit
in Form des Carry Bits mit.
Du brauchst 4 Bit um binär eine 8 (die Zahl 8, nicht 8 Zustände) darzustellen, egal wie du es nennst.
Erzähl das den Programmierern des Spiels. Es geht immer noch nicht
darum, irgendwas in der ReLität umzusetzen. Einfach nur Spielkrams....
Wenn du unbedingt Logikgatter nehmen musst..bitteschön. Ich würde es tatsächlich mit einem uC plus Display lösen oder sogar mit einem Eprom, einem 4028 und LEDs bzw. einem 4511 und einem 7-Segment-Display für die Anzeige.
Na, du wirst uns deine Gatter-Lösung schon präsentieren, obwohl ich nicht glaube dass es dazu kommt.
Jedenfalls glaube ich nicht dass du hier noch große Unterstützung bekommst..für ein quasi Hirngespinst.
Aber haut euch ruhig weiter die Köppe drüber ein,
Bestimmt nicht wegen dir.
PS: Dein „Plan“ im Eröffnungspost ist eine Frechheit, sowohl was das Gezeichnete angeht als auch die Farbgestaltung.
PS2: Außer deinem Wimmelbild und anderer Kritzeleien erkenne ich auch keine weitere Eigeninitiative deinerseits.
Eigentlich ists ja nich so kompliziert, Wiki-Artikel mit Look-Ahead Adder etc lesen und verstehen.
Im Prinzip nur Adder von 8x1bit.
Letzte Stelle XOR/Parität (bit 7-0)
2. Stelle XOR/Parität (AND(bit0-1), AND(bit3-2), AND(bit5-4), AND(bit7-6)), Quasi XOR/Parität vom Übertrag/AND von je 2 bits
3. Stelle, die AND(bit0-1), AND(bit3-2), AND(bit5-4), AND(bit7-6) Ergebnisse nochmal paar weise verANDen und XOR/Parität davon
....etc....
Wenn du unbedingt Logikgatter nehmen musst..bitteschön.
Dass du es auch nach zig Beiträgen nicht verstanden hast, dass er für seine Aufgabenstellung nichts anderes als eben Logikgatter zur Verfügung hat, spricht nicht gerade für dein Leseverständnis.
Wenn du unbedingt Logikgatter nehmen musst..bitteschön.
Dass du es auch nach zig Beiträgen nicht verstanden hast, dass er für
seine Aufgabenstellung nichts anderes als eben Logikgatter zur Verfügung
hat, spricht nicht gerade für dein Leseverständnis.
Wenn du unbedingt Logikgatter nehmen musst..bitteschön.
Dass du es auch nach zig Beiträgen nicht verstanden hast, dass er für
seine Aufgabenstellung nichts anderes als eben Logikgatter zur Verfügung
hat, spricht nicht gerade für dein Leseverständnis.
Genau genommen wird hier vom TO nicht von "Aufgabe" sondern von "Spiel" geschrieben und dann sind die Gatter wohl auch eher "Spielsteine". Dann gehört das wohl eher in die (nichtvorhandene) Rubrik "Zocken und Gaming" oder in die vorhandene "Offtopic".
Und wenn Studenten aus dem Studierzimmer ins Kasino wechseln gibt es meistens Prügel ;-) Jedenfalls zeigt Hollywood das so: https://youtu.be/0CHdkyMPp_M?t=22
Vermutlich fehlt es dir allerdings an Leseverständnis, denn der TO macht nur ein Gedankenspiel. Daher spielt es überhaupt keine Rolle welche Chips er hat und welche nicht.
Das Vorschläge kommen die von der Vorstellung eines TO abweichen ist übrigens nicht verwerflich sondern normal.
Ich würde als klassischen Lösungsweg immer noch die Erstellung von vier KV-Diagrammen versuchen.
Dass plötzlich noch ein viertes Bit aus dem Hut gezaubert wird entspricht dem Nicknamen chaoskind. Wo wir sind herrscht Chaos, aber wir können nicht überall sein.
Dann die vier Diagramme zusammenfassen, da lässt sich sicher vieles wegstreichen.
Das ergibt erst mal eine einstufige Lösung, ob tatsächlich die mehrstufige Version einfacher wird möchte ich bezweifeln.
Die Titelzeile offeriert aber dass der TO sein eigenes Problem nicht
verstanden hat.
"Sei helle, mach Tabelle" (siehe Anhang aus WP)
Mit der simplen Darstellung der zugrundeliegenden Regel von Conway's Game of Life in einer Tabelle wird sofort klar, das hier 9 Fälle durchzunummieren sind und damit ein dreistellige Binär-Index (n = 2³ = 8) nicht ausreichend ist.
Acht Leitungen - acht Nachbarn; entweder an oder aus - Nachbarzelle lebt oder lebt nicht. Anzahl der Nachbarzellen bestimmt Zustand im nächsten Zyklus (tot oder lebendig). Hm, zu meinen Studentenzeiten war "Zellulärer Automat" resp. "Systolisches array" beliebtes Modell resp. Studienobjekt.
Das war "Standard" wie das Schbrettproblem oder "Türme von Hanoi"
Kommt sicher auch wieder als Hype wenn es um AI ruhiger geworden ist, siehe auch Schwarm-technologie.
Erinnert mich an folgendes Dialog-snippet:
"Warum kann ein Informatiker kein Zehn-Finger Schreibsystem?" - Schulterzuck
"Weil er nur neun Finger hat!" - "Wieso das?"
Na er zählt seine Finger so ab: (Zeigt mit den Händen) : Kleiner Finger Links - 0, Ringfinger links - 1, Mittelfinger links - 2, ..." ;-)
Von Conways Game of life habe ich zuerst in "Der gute Kamerad: Ein Jahrbuch für Jungen. Band 72" (1964) gelesen, also lange vor der Heimcomputerzeit.
https://www.zvab.com/gute-Kamerad-Jahrbuch-Jungen-Band-72/30784785947/bd
Mit Foto von Conway, wenn ich noch recht weiß. Ich finde es nicht mehr, das hat wohl jemand mal entsorgt. "Das neue Universum" aus zwei Jahren habe ich noch.
Die Bücher hat anscheinend noch niemand eingescannt.
https://conwaylife.com/
eine Website, dem Spiel gewidmet, mit Literatur (494 Seiten) als PDF und einer Lifeversion im Browser.
Von Conways Game of life habe ich zuerst in "Der gute Kamerad: Ein
Jahrbuch für Jungen. Band 72" (1964) gelesen, also lange vor der
Heimcomputerzeit.
Hm, aus den Sechszigern sind mir eher Bücher über Radiobau und so untergekommen, auch Raumfahrt, Computer(-kunst) und mathematische Spielereien war IMHO in den Achtzigern groß, da gabs wohl Sonderhefte in "Spektrum der Wissenschaft". Und es sei an dieser Stelle an den Spiegel-Bestseller von 1985 "Gödel, Escher, Bach" erinnert, da dreht sich alles um Zelluläre Automaten und ähnliche Mathematik-/Logik-"spiele".
Mit der simplen Darstellung der zugrundeliegenden Regel von Conway's
Game of Life in einer Tabelle wird sofort klar, das hier 9 Fälle
durchzunummieren sind und damit ein dreistellige Binär-Index (n = 2³ =
8) nicht ausreichend ist.
Hm, also sequentiel hat er nicht erwähnt, nur (reine) Kombinatorik, keine FF oder sonstige Speicherelemente in der Summierung. In dem "Schaltplan" des TO sieht man nur Logik, keine Taktung.
Mathematisch gesehen ist es wurscht aber schaltungstechnisch hat man für Carry-lines gerne eigene routing sourcen weil das eben oft der längste und damit der kritische Pfad ist.
Er hat es nur mit 10 Zeigefingern gelernt.
Hehe, b10 -> da muss ich gleich mal Robert J. Widlar zitieren (siehe Anhang) (auch wenns bei dem der Mittelfinger ist, der zählt ;-))
Ich würde als klassischen Lösungsweg immer noch die Erstellung von vier
KV-Diagrammen versuchen.
Macht mal, das möchte ich sehen ;-)
Mal abgesehen davon, dass die KV-Diagramme für sich gesehen noch nicht
zu einer einfachen Lösung führen (s. Beiträge von Hippelhaxe), ist ein
16×16-KV-Diagramm wohl kaum fehlerfrei aufzustellen und auszuwerten.
Ein 2×2-Diagramm (mit 2 Signalen) ist easy-peasy, bei einem 4×4-Diagramm
(4 Signale) muss man schon etwas tricksen, geht aber noch problemlos.
Bei 8×8 (6 Signale) wird es schon sehr unübersichtlich, da die Bereiche
von 2 der 6 Signale nicht mehr zusammenhängend (auch nicht über die
Ränder des Diagramms hinweg) sind.
Bei 16×16 (8 Signale) belegen die beiden neu hinzugekommenen Signale
sogar jeweils 4 nicht zusammenhängende Bereiche. Da fällt es extrem
schwer, Gruppen von Einsen zusammenzufassen.
Warte, es geht vielleicht doch:
Man muss das Diagramm ja nicht unbedingt auf ein zweidimensionales
Papier zeichnen. Zeichnet man es stattdessen im vierdimensionalen Raum
als 4×4×4×4-Würfel, geht die Auswertung fast so leicht wie bei 4
Signalen im 4×4-Quadrat. Noch leichter geht es, wenn man das Diagramm
auf die (vierdimensionale) Oberfläche eines fünfdimensionalen Torus
zeichnet, weil dann die Bereiche für jedes Signal wirklich
zusammenhängend sind und nicht wie beim 4×4×4×4-Würfel oder beim
4×4-Quadrat über die Ränder fortgesetzt werden müssen.
Ich muss mal schauen, ob es inzwischen für meinen 3D-Drucker ein
Erweiterungsmodul für eine oder zwei zusätzliche Dimensionen gibt.
Oder ich besorge mir gleich eine 8D-Drucker, denn dann hat das
KV-Diagramm nur noch 2 Felder pro Dimension, so dass sogar blutige
KV-Anfänger damit zurechtkommen.
Falls ich fündig werden, werde ich das Ergebnis hier posten.
In der Zwischenzeit könnt ihr auch schon mal am zweidimensionalen
Diagramm die Zähne ausbeißen.
Mal abgesehen davon, dass die KV-Diagramme für sich gesehen noch nicht
zu einer einfachen Lösung führen (s. Beiträge von Hippelhaxe), ist ein
16×16-KV-Diagramm wohl kaum fehlerfrei aufzustellen und auszuwerten.
Und fürs LSb und MSb der Summe ist es reichlich einfach, MSB ist ein AND über alles (also 8 Eingängen) und Lsb ist ein Parity (XOR-Kaskade) über alles.
Aber bei "Paritätsprüfer" denkt man ja sofort an XOR.
Ist ja mathematisch auch richtig -- aber es kann halt
sein, dass das technisch nicht 1:1 umsetzbar ist.
Wenn man aus irgendwelchen Gründen gezwungen sein sollte,
den Paritätsgenerator mit einem PAL oder GAL umzusetzen,
dann ist dadurch die zweistufige AND-OR-Logik schon fest
vorgegeben...
Überdies würde ich bei 64 Bit gar nicht erst anfangen,
mit einer Tabelle zu arbeiten. ;-)
Das sagt sich leicht.
Ausreichend große Systeme will man nur mit Unterstützung
durch den Computer entwickeln -- und wie teilst Du dem
Computer mit, welches Soll-Verhalten Du von der Schaltung
forderst? In den meisten Fällen wird das wohl eine Art
Wahrheitswertetabelle sein müssen...
Der Paritätsgenerator ist da die Ausnahme von der Regel,
bei dem kann man die boolesche Gleichung direkt hin-
schreiben -- aber das geht halt nur selten.
Wäre aber mal interessant, das ganze für eine realistische
Anzahl von Bits, z.B. 8, mit QMC zu exerzieren.
Unbedingt.
Man erkennt erst bei der Handrechnung, wo die Problempunkte
beim Logikentwurf liegen.
Ich habe das nämlich noch nie gemacht.
Na dann los :)
Erwähnte ich schon, dass ich den Plan für einen Sieben-
Segment-Decoder gebrauchen könnte, der A-F korrekt
decodiert und anzeigt? :o)
64bit sind irgendwas 10^19 Zeilen, bisschen mehr als 2Mia.
Läuft aber alles auf even/odd parity raus, also 2^64=>2^1, nur die Anzahl 0/1 sind interessant, Position und Verteilung egal, daher kannst quasi beliebig in kleinere LUTs aufteilen.
Wenns eine 2^64=>2^64 Funktion wäre, wärs nicht möglich, mit auf kleinere LUTs aufbrechen, wenn quasi jede 2^64 Adresse ihren rein zufälligen 0/1 Wert hätte.
Ich würde als klassischen Lösungsweg immer noch die
Erstellung von vier KV-Diagrammen versuchen.
Viel Spaß :-)
Die Arbeit kannst Du Dir aber weitgehend sparen.
Mehreren Leuten sind nämlich bereits folgende
Dinge aufgefallen:
Das höchstwertige Ergebnis-Bit wird dann und nur
dann "1", wenn ALLE acht Eingangsbits gesetzt sind.
Das zugehörige KV-Diagramm ist fast leer -- bis auf
diese eine einzige "1".
Die Umsetzung in eine Gatterschaltung ist trivial --
das ist ein AND-Gatter mit acht Eingängen. Fertig.
Das niederwertigste Ergebnis-Bit entspricht gerade
der Parität des Eingangsvektors; das ist als Formel
((((((E0 xor E1) xor E2) xor... )
Die zugehörige KV-Tafel enthält ein Schachbrettmuster,
d.h. 128 isolierte Einsen. Nix mit zusammenfassen.
Die Gatterschaltung benötigt neben ein paar Invertern
und OR-Gattern 128 AND-Gatter.
Bit0 und Bit3 vom Ergebnis sind damit erledigt; nur
die KV-Tafeln für Bit1 und Bit2 müssten jetzt noch
gezeichnet werden.
Dann die vier Diagramme zusammenfassen, da lässt
sich sicher vieles wegstreichen.
Unwahrscheinlich.
Ergebnis-Bit0 muss gesetzt werden, wenn der Eingangs-
vektor 1, 3, 5, oder 7 Einsen enthält.
Ergebnis-Bit1 muss gesetzt werden, wenn der Eingangs-
vektor 2, 3, 6 oder 7 Einsen enthält. Vektoren mit
zwei Einsen gibt es 28 verschiedene; 8-stellige
Vektoren mit sechs Einsen sind gerade Vektoren mit
zwei Nullen, also gibt es davon auch 28, zusammen
also 56.
"2" und "6" sind gerade Zahlen, also wird -- anders
als bei "3" und "7" -- das Ergebnis-Bit0 NICHT
auf "1" gesetzt.
Es handelt sich somit um Eingangsvektoren, die NICHT
mit solchen identisch sein können, die für Ergebnis-Bit0
schon betrachtet wurden. Die 56 AND-Gatter sind somit
zusätzlich notwendig.
Auf Ergebnis-Bit2 habe ich jetzt keine Lust mehr.
...
Hmm. Ich denke, ich bin gerade dabei, eine 256x4-LUT
zu erfinden. JUHUUU!
In der AND-Stufe werden alle 256 möglichen Eingangs-
belegungen ausdecodiert; in den OR-Stufen werden die
Ausgangs-Bitmuster für jede Belegung definiert.
Das ergibt erst mal eine einstufige Lösung, ob
tatsächlich die mehrstufige Version einfacher wird
möchte ich bezweifeln.
64bit sind irgendwas 10^19 Zeilen, bisschen
mehr als 2Mia.
Mea culpa.
Ich war gedanklich bei 32bit... es sind also
4 Trillionen Zeilen.
Läuft aber alles auf even/odd parity raus, also
2^64=>2^1, nur die Anzahl 0/1 sind interessant,
Position und Verteilung egal, daher kannst
quasi beliebig in kleinere LUTs aufteilen.
Sachlich richtig -- für meine Unterhaltung mit Marci
nicht relevant.
Dafür gibt es etwas in der 74er Reihe: 74HC148 und im Datenblatt sieht man die Schaltung dazu. Hätte nicht gedacht, dass man den noch kaufen kann. Aber Mouser hat die am Lager.
Mea culpa.
Ich war gedanklich bei 32bit... es sind also
4 Trillionen Zeilen.
Auch falsch.
Nicht "auch".
Die 4 Trillionen sind falsch. Punkt.
Und die 2 Mrd waren auch falsch - das wären 31 Bit.
Nein, die 2Mrd sind richtig, und 31Bit sind auch
richtig.
Es müssen nämlich nur die Minterme mit ungerader
Parität erkannt werden -- das ist genau die Hälfte.
Bei 32bit Wortlänge also 2 Mrd.
Nun bist Du bei 62 Bit.
Sehr guter Einwand. Danke.
Es sind also 8 Trillionen. Die anderen 8 Trillionen
mit gerader Parität sind nicht relevant.
31bit ist nicht richtig.
2Mrd ist aber richtig.
32bit ist auch richtig.
Die Eingangsvektoren sind 32bit lang; da aber nur jeder
zweite erkannt werden muss (=ungerade Parität), ergeben
sich trotz der 32bit Vektorlänge nur 2Mrd Zeilen in
der WW-Tabelle.
Das sind neun (gleichartige) Tabellen, nicht eine ...
Es sind vier LUTs a 8 Input und 1 output die man hier braucht,
Acht Leitungen gehen rein, vier gehen raus. Für ner Achter-LUT braucht man 2⁸ Speicherstellen also 256 bit, das wurde oben schon mehrmals vorgerechnet.
Auf einem Blatt A4 kariert mit genormten 210x297 mm sind bei einem 5 mm Raster grob überschlagen (20cm30cm4❌ pro cm²) 2400 Kästchen, da kriegt man die 4 LUT's locker auf ein Blatt. BTDT
Aber für die Optimierung (von bspw. 32 bit) braucht man nicht unbeding die vollen Tabellen, dafür gibt es den Quine McClusky- Algo.
Der ist mit ner Handvoll Codelines runtergeschrieben: https://en.wikipedia.org/wiki/Quine%E2%80%93McCluskey_algorithm#Algorithm Das geht schneller als 2d lang in einem Internetforum darüber zu debattieren.
Marci W. schrieb:
Aber bei "Paritätsprüfer" denkt man ja sofort an XOR.
Ist ja mathematisch auch richtig -- aber es kann halt
sein, dass das technisch nicht 1:1 umsetzbar ist.
Wenn man aus irgendwelchen Gründen gezwungen sein sollte,
den Paritätsgenerator mit einem PAL oder GAL umzusetzen,
dann ist dadurch die zweistufige AND-OR-Logik schon fest
vorgegeben
in einem PLA sind aber die AND recht breit, meint die haben viele Inputs bspw. 13, das MSb wäre also mit einer Zeile erschlagen.
Aber ja, XOR ist was besonders, das ist nicht gut optimierbar (wegen der "diagonal Patterns of '1's in the Karnaugh map") da ist es praktisch ein paar davon (bspw 74x84 -> 4xXOR2) diskret vor dem PLA zu setzen. Oder man bricht die parallele Komplexität mit einer kleinen statemachine und Muxing des Eingangsvectors auf. Oder eben Fulladder mit schnellen Carry-lines. Oder schieberegister mit hochsynthetisierten Clock. da gibt es schon seit Jahrzehnten AppNotes dazu: https://www.cs.york.ac.uk/rts/docs/Xilinx-datasource-2003-q1/appnotes/xapp220.pdf
Und wie gesagt, die hier erforderlichen kleinen PROM's für Lookuptables gibt es bereits in der 74xxx Serie als gering integriert. Bei 16 input Leitungen ist dann eben ein 64 kb ROM, das war schon beim C64 vor 40 Jahren kein Problem. Und parity macht ein UART-Chip wie der uralte 16550 nebenher bitweise. Da das parity am schluss gesendet wird ist die zyklenweise Berechnung auch kein Problem.
aber es kann halt
sein, dass das technisch nicht 1:1 umsetzbar ist.
Ja, klar wenn man sich unbedingt ins Knie schiessen will, bitte! Aber man sollte nicht erwarten, das ein Anderer die Pistole hält und die Verantwortung dafür übernimmt. Man verwendet die Technik, die sinnvoll ist, da muss man sich eben durchsetzen - "So kann ich nicht arbeiten".
Vermutlich fehlt es dir allerdings an Leseverständnis, denn der TO macht
nur ein Gedankenspiel. Daher spielt es überhaupt keine Rolle welche
Chips er hat und welche nicht.
Immer noch nicht verstanden? Es ist ein "Problem" aus einer virtuellen Welt. Und diese Welt gibt halt vor, welche Chips ich habe.
Das Problem war ja auch schon gelöst, als ich die Frage stellte, denn die Frage war ja "geht es mit weniger Gattern?" und nicht "wie kann ich das Problem überhaupt lösen?".
Weil die (selbstegestellte) "Aufgabe" lautet: Baue eine Zelle des Game
of Life aus Logikgattern und vervielfältige sie zu einem Spielfeld.
Analog wäre auch interessant. Mit 2 Komparatoren (VCC * 3/8 und VCC * 2/8) müsste man eigentlich eine Zelle auswerten können, indem man die umliegenden Zellen über Widerstände verbindet.
Vielen Dank für deine (hier vergebliche) Mühe. Aber in der simulierten Welt in der ich mich mit dem Problem befasste, müsstest du dir deinen AT89C2051 auch ersteinmal aus einzelnen Gattern erstellen.
Und das Programm müsstest du per Hand direkt in den Speicher des selbst erstellten uCs einklicken. Du könntest den Speicher abweichend vom Original natürlich auch als Festwertspeicher ausführen :D
Ich wollte nur mal probieren, ob man direkt im Quelltext eine Tabelle erzeugen lassen kann.
Ich wollte erst einen AVR nehmen, der kennt aber keine Repeat-Macros. Und in C gibt es das auch nicht.
Man kann es wohl nur ganz von hinten durch die Brust ins Auge, z.B. über Excel ein Include-File erzeugen.
Ich wollte erst einen AVR nehmen, der kennt aber keine Repeat-Macros.
Kann man ihm schon beibringen, allerdings nicht für unbegrenzte N (die maximale Rekursionstiefe der Macro-Engine begrenzt das).
Und bei höheren N dauert so ein Assemblerlauf dann auch schnell mal ein paar Minuten, selbst wenn der Body des Repeats noch leer ist.
Da muss man sich erst mal dran gewöhnen...
Die Gewohnheit des Normalfalls ist ja, dass die Übersetzung durch den Assembler nach menschlichem Zeitempfinden nahezu instantan erfolgt. Deswegen glaubt man zunächst, dass der Assembler abgestürzt wäre.
8_1bit_ein_zu_1_3bit_aus.jpg
(110 KB)
