Folgende Funktion würde ich gerne mit minmalem Rechenaufwand
realisieren:
1
a b c E
2
0 0 0 0
3
0 0 1 0
4
0 1 0 0
5
0 1 1 1
6
1 0 0 0
7
1 0 1 1
8
1 1 0 1
9
1 1 1 1
Bisher habe ich:
E = ( a | b ) & ( a | c ) & ( b | c )
Das läßt sich mittels Distributivgesetz vereinfachen zu:
E = ( a | ( b & c ) ) & ( b | c )
So komme ich auf vier logische Operationen.
Meine Frage ist nun, kann jemand das mit noch weniger Operationen
hinbekommen (XOR und NICHT sind auch erlaubt) oder/und kann jemand
beweisen (nicht mathematisch, sondern nur "plausibel"), daß es nicht mit
weniger Operationen geht?
Das funktioniert doch mit einem LUT. Du hast alle Zustände
aufgeschrieben die auftreten können. Die LUT auf einem Virtex 5 oder
Spartand 6 haben bis zu 6 Eingänge. Demnach kann Deine Logik sogar noch
komplexer werden :-)
In der Überschrift steht "mit Gattern" also CMOS- oder TTL nehme ich an.
Für so etwas benutze ich immer noch das gute alte
Karnaugh-Veitch-Diagramm auf "Karopapier":
http://de.wikipedia.org/wiki/Karnaugh-Veitch-Diagramm
da fehlen allerdings Vereinfachungen mit EXOR-Gatter
Elektroniker schrieb:> unter Mitbenutzung des ersten Terms.
Wie nochmal?
> Das ist soch auf den ersten Blick ersichtlich:
Der Ausgang ist high, wenn mehr als 1 Eingang high ist. Man kann die
Eingänge beliebig benennen, die Namen abc sind austauschbar...
Gattermann schrieb:> Meine Frage ist nun, kann jemand das mit noch weniger Operationen> hinbekommen
Natürlich. Das ist eine klassische Hausaufgabe die sich mit 3 dualen
Operatoren erledigen lässt mit der man einfachst herausfinden kann, wie
intelligent der Proband ist.
Der Aufgabensteller will NICHT die Intelligenz dieses Forums
kennenlernen, obwohl der Dümmste hier sicher wieder mit der
Hausaufgabenantwort kommt.
Max H. schrieb:> Mit einem KV Diagramm komme ich auf E=AB+AC+CB
Also völlig identisch mit dem, was Gattermann schon im Eröffnungspost
geschrieben hatte.
Gattermann schrieb:> Bisher habe ich:>> E = ( a | b ) & ( a | c ) & ( b | c )
Vielen Dank für die vielen Antworten!
@Johann und Gerald B.: Tatsächlich muß ich das mit einer CPU erledigen,
die für and, or, xor und not jeweils gleich viele Taktzyklen benötigt,
für Speicher- und Peripheriezugriffe aber deutlich mehr. Daher fallen
LUTs und EPROMs aus.
@Elektroniker: Abgesehen davon, daß Du C nicht beachtest, hat "A UND (
NICHT (A UND B) ) ODER (A UND B)" nach meiner Zählung 5 Operationen.
@Max H.: "E=AB+AC+CB" hatte ich ja auch schon, das KV Diagramm bringt
mich nicht mehr weiter (auch @Christoph Kessler).
@MaWin: Hätte wirklich eine HA sein können. Ist es aber nicht. Hier
gehts auch nicht um Intelligenz (irgendwann würde ich sicher selbst
drauf kommen), sondern um die Systematik beim Suchen der Lösung, bzw.
eine plausible Erklärung, warum 3 Gatter reichen ("Hab ich in Inf so
gelernt" zählt hier nicht).
Ich muß noch dazu sagen, daß die CPU nur mit zwei Operanden gleichzeitig
arbeiten kann. Deswegen darf kein Gatter mehr als 2 Eingänge haben.
Ja, und ich suche tatsächlich auch die Lösung, weil eine zeitkritische
Schleife bei mir zu lahm ist.
PS.: Diesen Lösungsansatz gibts ja auch noch:
E = (!a & b & c) | (a & !b & c) | (a & b & !c) | (a & b & c)
foo schrieb:> Dann nimm zwei XOR und fertig ist die Laube!
Und wie soll das gehen?
Mit XOR komme ich auf 4 2-Input Gatter:
E=((A^C)(B^C))^C
Hintergrund ist DeMorgan. Wenn man sich die Tabelle ansieht sieht man
das für C=0 E=AB und für C=1 E=A+B.
Für C=0 (x^0=x) also wird die Funktion zu E=AB
Für C=1 (x^1=x') also wird die Funktion zu E=(A'B')' Wendet man DeMorgan
an kommt man auf E=A+B
Wenn man ein 3-fach AND/OR als 2 Operationen zählt haben wie eine
gespart.
@S. E.: Overflow, da nur 1 Bit zur Verfügung steht (genauer: Es werden 8
Bits gleichzeitig bearbeitet):
@Max H.: Verzweigungen gehen nicht, auch weil der Branch mehr Taktzyklen
braucht. Oder habe ich bei Deiner Lösung etwas falsch verstanden?
Ich habe mal meine beiden Lösungen in AVR-Assembler gegossen:
5 Taktzyklen:
E = ( a | ( b & c ) ) & ( b | c )
mov t, b
and t, c
or t, a
or b, c
and b, t
(E in b)
6 Taktzyklen:
E = ( a | b ) & ( a | c ) & ( b | c )
mov t, a
or t, b
or a, c
and a, t
or b, c
and a, b
(E in a)
Man sieht schon, meine Lösungen brauchen immer noch ein Hilfsregister t
(die Register mit den Eingangswerten werden nicht mehr gebraucht).
Gattermann schrieb:> Tatsächlich muß ich das mit einer CPU erledigen, die für and, or, xor> und not jeweils gleich viele Taktzyklen benötigt
Falsches Forum. Ich verschiebe das mal dorthin, wo es hingehört...
Gattermann schrieb:> @Max H.: Verzweigungen gehen nicht, auch weil der Branch mehr Taktzyklen> braucht. Oder habe ich bei Deiner Lösung etwas falsch verstanden?
Ich glaube ja.
E=((A^C)(B^C))^C
war die gesamte Formel, der rest war nur erklärung wie sie funktioniert.
@S. E.: wow. Ein Hilfsregister zu sparen, ist auch gut.
Deine Funktion ist also:
t = (a ^ b)
E = (a & !t) | (c & t)
5 Operationen, aber kein mov
Bin ich nicht drauf gekommen. Aber in 4T scheint es nicht zu gehen. Ich
denke schon so lange darüber nach, daß ich mittlerweile betriebsblind
bin
@Max H.: Super! 4 Operationen, kein Hilfsregister:
eor a, c
eor b, c
and a, b
eor a, c
Bin ich wirklich nicht drauf gekommen! Es gibt immer einen, der besser
ist als man selbst ;-)
> Tatsächlich muß ich das mit einer CPU erledigen, die für and, or, xor> und not jeweils gleich viele Taktzyklen benötigt
Also dann würde ich eher eine Tabelle verwenden (analog zum obigen
Vorschlag eines Eproms):
1
uint8 table[0,0,0,1,0,1,1,1;
2
result=table[input];
Jetzt musst du nur noch dafür sorgen, dass die drei Eingabe-Bits in der
Variable input stehen (a=Bit 2, b=Bit 1, c=Bit 0). Vielleicht ist das ja
sogar schon der Fall, weil es sich um drei Leitungen handelt, die an
einen Eingabe-Port angeschlossen sind.
Jedenfalls benötigt dieser Tabellen-Lookup immer gleich lange, egal
welche Einagngskombination vorliegt.
Wenn er was hochsprachliches wöllte, könnte er auch einfach b und c zu a
addieren und das Ganze dann ein Bit nach rechts schieben. Er schrieb
aber: 'mit Gattern'.
Wenn man davon ausgeht, dass a,b,c in einem Register anfallen, sind die
oben angegeben Abläufe sinnfrei weil man a,b,c erst auf Register
aufteilen muss. Bei mehreren Registern ist eine aufeinander folgende
Abfrage, ob ein Bit im jeweiligen Register gesetzt ist, vermutlich nicht
langsamer als die Aufteilung auf einzelne Register plus Auswertung.
Folgendes bei Bits a,b,c in r1 als 00000abc, mit Bitverdoppelung von Bit
c.
Benötigt temporär 2 Register (r1,r2) und T Flag bei Porteingabe auf
einem PORT bei AVR z.B.:
Read :
IN r1,PORT ; PORT lesen
ANDI r1,7 ; andere Bits wegunden, ergibt 00000abc
MOV r2,r1 ; kopieren
LSL r2 ; Kopie eins nach links schieben
BST r1,0 ; Bit c nach t zwischenspeichern
BLD r1,3 ; Bit t nach Bit 3, verdoppeln von c
AND r1,r2 ; Ergebnis (E in r1: r1 = 0 für E = 0)
BREQ Done ; Sprung zum Ende bei NULL
... (Aktionen bei E = 1)
Done :
RJMP ... (Rücksprung)
Die Auswertung beruht auf den Vorhandensein von aufeinander folgenden
Einsen die durch Verdoppelung von c als höchste Stelle und den Shift nur
bei E = 1 auftreten, dann wird r1 UND r2 nicht NULL.
Das wären nur 8 Clocks vom Label zum Befehl (9. Clock).
Falls das noch zu langsam ist, und du das von einem Port einliest,
kannst ja extern die Aufgabe mit einer Logikschaltung lösen:
E = a*(b+c)+b*c = a*b + a*c + b*c
Und wenn du einfach einen 8 zu 1 Multiplexer nimmst kannst dir auch
jeglichen Denkvorgang sparen. Einfach nach Tabelle anschließen.
E = ( a | b ) & ( a | c ) & ( b | c )
Was du mit dieser Form willst kann ich leider nicht verstehen, Minterm
und Maxterm sind zwar equivalent, aber diese Form begreift doch keiner.
Vielen Dank an alle, die sich den Kopf zerbrochen haben. Ich denke, das
Thema ist gegessen.
Es ist tatsächlich so, daß die Ausgangsbasis je 8 Bit in drei
verschiedenen Registern ist. Das heißt, die Ausgangsfunktion läuft
8-fach parallel und letztendlich in 4 AVR-Taktzyklen ab, also 0.5T pro 3
Bits.
Ich lehne mit mal aus dem Fenster und behaupte, das läßt sich nicht
weiter beschleunigen. 3T wäre schön gewesen, geht aber nicht.
Insofern sind alle Fragen geklärt bis auf den Plausibilitätsbeweis und
auch z.B. die konsequente Herleitung der besten Lösungen. Es scheint
einfach so zu sein, daß man probieren muß, und dann wird es richtig
unübersichtlich mit z.B. 5 Ausgangsregistern. Schade.
Uranhexafluorid schrieb:> Wenn er was hochsprachliches wöllte, könnte er auch einfach b und c zu a> addieren und das Ganze dann ein Bit nach rechts schieben.
Der Vorschlag war schon mal da und geht nicht, weil da 8 Bit parallel
verarbeitet werden sollen. Siehe
Beitrag "Re: Logische Funktion mit Gattern realisieren"> Er schrieb aber: 'mit Gattern'.
Weil man solche "Gatterfunktionen" parallel auf ein ganzes Byte anwenden
kann. Du solltest dir mal die Tastenreoutine von PeDa genau ansehen, da
ist ein Zwei-Bit-Zähler auf solche Weise realisiert...
Beweisen, soweit das möglich ist, kannst dir das selber mal, wenn du
z.B. das
https://www.fbi.h-da.de/fileadmin/personal/e.komar/public_html/DGT-Skript-Teil1.PDF
gelesen hast (interessant v.a. die Aufstellung der Lösungsverfahren).
Möglichkeiten mit Ergebnis immer minimal, ohne Probieren:
- KV Tafel, bis 4 ohne Problem, mehr geht aber auch
- Alle Terme für E=0 oder E=1 aufstellen und vereinfachen
- berechnen mit Quine McCluskey
Möglichkeiten mit Ergebnis ohne Gewähr:
- Genau anschauen
- Andere Methode suchen, siehe mein Post davor, oder z.B. Quersumme bei
einzelnen Bits
Möglichkeiten ohne Denken, Ergebnis garantiert:
-Multiplexer
-Eprom
-LUT
-CASE
> Wenn er was hochsprachliches wöllte, könnte er auch> einfach ... Er schrieb aber: 'mit Gattern'.
Ja, und etwas später schrieb er, dass er das mit einem Programm und
einer CPU lösen will. Also doch keine Gatter. Inzwischen wissen wir
auch, dass es sich um einen AVR handelt.
Man mann, Fragen ordentlich formulieren muss ja schwer sein. Drei
viertel der Beiträge sind wegen irreführender Fragestelung für die Katz
gewesen!
Einen hab ich noch:
E = a*b + a*c + b*c = a*(b+c) + b*c = a*/(b*c) + b*c
E = a*b + a*c + b*c = a*b + (a+b)*c = a*b + /(a*b)*c
Bring aber nur bei diskreter Logik was (->NAND), nicht bei CPU wegen MOV
und CMP (es sei denn man hätte diese Paare schon irgendwo).
