Forum: Projekte & Code KV-Tabelle minimieren mit Quine-McCluskey die 1000ste


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Ralph S. (jjflash)


Angehängte Dateien:

Bewertung
6 lesenswert
nicht lesenswert
... weil:  Vor einer Woche oder so es einen Thread um Minimierung 
digitaler Logik gab (mal wieder) hatte ich einen Spaß daran, eine 
Progrämmchen für die Linux-Console zu schreiben, die die Logik 
simuliert.

Der Vorteil von Konsolenprogrammen ist es, dass (meistens) nichts 
installiert werden muß, es wird "irgendwohin kopiert" und von dort 
gestartet.

Viel Spaß

R. Seelig

von Ralph S. (jjflash)


Bewertung
0 lesenswert
nicht lesenswert
Ralph S. schrieb:
> die die Logik
> simuliert.

muß natürlich "minimiert" heißen !

von Johannes S. (demofreak)


Bewertung
1 lesenswert
nicht lesenswert
Hübsch. :-)

von udok (Gast)


Bewertung
-3 lesenswert
nicht lesenswert
Schaut aus wie aus den 80'ern...

von Ralph S. (jjflash)


Bewertung
3 lesenswert
nicht lesenswert
udok schrieb:
> Schaut aus wie aus den 80'ern...

Na ja: Kommandozeile halt, aaaaaaber: funktioniert damals wie heute 
uuuund: häufig wird über die Optik das eigentliche Programm vergessen.

Hier gings ja nur darum das darzustellen. Mach das in eine GUI und dann 
ist das nicht mal eben schnelle gemacht !

==> ich gebs ja zu: ich bin ein 80er Jahre (okay auch 90er Jahre) - Fan, 
oldschool und ich bin ein Fan der Konsole (einfach deshalb, weil es 
alleine für die GUI abartig Resourcen braucht, die ich für unnötig 
empfinde).

von udok (Gast)


Bewertung
-1 lesenswert
nicht lesenswert
Ralph S. schrieb:
> Schaut aus wie aus den 80'ern...
>
> Na ja: Kommandozeile halt, aaaaaaber: funktioniert damals wie heute
> uuuund: häufig wird über die Optik das eigentliche Programm vergessen.
>
> Hier gings ja nur darum das darzustellen. Mach das in eine GUI und dann
> ist das nicht mal eben schnelle gemacht !
>
> ==> ich gebs ja zu: ich bin ein 80er Jahre (okay auch 90er Jahre) - Fan,
> oldschool und ich bin ein Fan der Konsole (einfach deshalb, weil es
> alleine für die GUI abartig Resourcen braucht, die ich für unnötig
> empfinde).

Ich habe es mal unter Windows/Cygwin compiliert:

rscontrols3.c:13:10: fatal error: linux/fb.h: No such file or directory
   13 | #include <linux/fb.h>
      |          ^~~~~~~~~~~~
compilation terminated.
make: *** [Makefile:104: rscontrols3.o] Error 1

Ist das nicht ncurses kompatibel?

Ich habe absolut nichts gegen Retro und 80'er, hat auch einen
ganz besonderen Charme.

Sinnvoll wäre es noch, wenn man ein Config-File angeben kann.
Sonst muss man ja immer alles mühselig einstellen,
und da bin ich ja im Kopf schneller...
Noch sinnvoller wäre es, wenn man wenigstens 6 Variablen optimieren 
kann,
vier Variablen sind zu wenig.
Wahrscheinlich kann man das brute-force in < 1 Sekunde lösen.

Gruss,
Udo

von Ralph S. (jjflash)


Bewertung
0 lesenswert
nicht lesenswert
udok schrieb:
> rscontrols3.c:13:10: fatal error: linux/fb.h: No such file or directory
>    13 | #include <linux/fb.h>
>       |          ^~~~~~~~~~~~
> compilation terminated.
> make: *** [Makefile:104: rscontrols3.o] Error 1
>
> Ist das nicht ncurses kompatibel?

Nein, das baut tatsaechlich nicht auf ncurses auf, sondern greift auf 
Hardware direkt zu. Den Zugriff auf den Framebuffer werde ich naechste 
Woche entfernen.

udok schrieb:
> Noch sinnvoller wäre es, wenn man wenigstens 6 Variablen optimieren
> kann,
> vier Variablen sind zu wenig.

Hmmm, fuer 6 Variable bedarf es eine Wahrheitstabelle mit 64 Eintraegen. 
Dann braucht es ein scrollbares UI, entweder mit Curses, Tvision oder 
eines der vielen GUI Moeglichkeiten. Hier waere dann wirklich darueber 
nachzudenken, ob man ein reines Konsolenprogramm ohne Interaktion macht, 
mit einer Steuerungsdatei, die ausgewertet wird.

von Yalu X. (yalu) (Moderator)


Bewertung
2 lesenswert
nicht lesenswert
udok schrieb:
> rscontrols3.c:13:10: fatal error: linux/fb.h: No such file or directory
>    13 | #include <linux/fb.h>
>       |          ^~~~~~~~~~~~

Die Zeile mit dem fb.h kannst du IMHO ersatzlos streichen. Zumindest 
hier auf meinem Handy funktioniert das Programm auch ohne dieses Include 
perfekt.

von Ralph S. (jjflash)


Bewertung
0 lesenswert
nicht lesenswert
udok schrieb:
> rscontrols3.c:13:10: fatal error: linux/fb.h: No such file or directory
>    13 | #include <linux/fb.h>
>       |          ^~~~~~~~~~~~
> compilation terminated.
> make: *** [Makefile:104: rscontrols3.o] Error 1

Jetzt habe ich mir das doch heute morgen angeschaut: Das wird von 
"termios.h" in weiterem Verlauf eingebunden, welches wohl unter einem 
Cygwin nicht vorhanden ist (weil dort wohl niemand mehr auf einer reinen 
Konsole werkeln mag).

Von daher tut mir das leid, dass das unter Cygwin nicht laufen wird !

von Yalu X. (yalu) (Moderator)


Angehängte Dateien:

Bewertung
3 lesenswert
nicht lesenswert
Ich habe mal einen Minimierer für logische Ausdrücke mit einem einfachen
GUI in Python gebastelt. Auf der linken Seite wird die Logik durch
Klicken eingegeben, auf der rechten wird der minimierte Term angezeigt.

Der Quine-McCluskey-Algorithmus war mir zuviel Tipperei, deswegen habe
ich einen einfacheren genommen. Vermutlich ist er weniger effizient als
der Quine-McCluskey, für eine realistische Anzahl von Variablen, erfolgt
die Minimierung aber auch hier im Bruchteil einer Sekunde. Deutlich
länger dauert die Initialisierung, weswegen ich die Anzahl der Variablen
auf 10 begrenzt habe.

Der Algorithmus erstellt in der Initialisierungsphase eine Liste aller
3**n möglichen Feldergruppen, die im KV-Diagramm zusammengefasst werden
können (n ist dabei die Anzahl der Variablen). Bei der eigentlichen
Minimierung werden diese Gruppen – beginnend mit den größten – der Reihe
nach durchprobiert. Das KV-Diagramm selber wird nicht angezeigt, da es
für mehr als 4 Variablen sowieso unübersichtlich wird.

Die Minimierung wird bei jeder Änderung der Wahrheitstabelle sofort
gestartet.

Die Anzahl der Variablen ist defaultmäßig 4. Per Kommandozeilenargument
kann sie aber auf einen beliebigen Wert im Bereich von 1 bis 10 gesetzt
werden.

Das Programm sollte auf jeder Plattform laufen, für die Python 3 und Tk
verfügbar ist. Getestet habe ich es unter Linux und Windows 7.

von Ralph S. (jjflash)


Bewertung
0 lesenswert
nicht lesenswert
Yalu X. schrieb:
> Ich habe mal einen Minimierer für logische Ausdrücke mit einem einfachen
> GUI in Python gebastelt. Auf der linken Seite wird die Logik durch
> Klicken eingegeben, auf der rechten wird der minimierte Term angezeigt.

Cool

von udok (Gast)


Bewertung
-2 lesenswert
nicht lesenswert
Läuft auch unter Windows.
Danke!

von Ralph S. (jjflash)


Bewertung
2 lesenswert
nicht lesenswert
Yalu X. schrieb:
> udok schrieb:
>> rscontrols3.c:13:10: fatal error: linux/fb.h: No such file or directory
>>    13 | #include <linux/fb.h>
>>       |          ^~~~~~~~~~~~
>
> Die Zeile mit dem fb.h kannst du IMHO ersatzlos streichen. Zumindest
> hier auf meinem Handy funktioniert das Programm auch ohne dieses Include
> perfekt.

Yalu hat absolut recht: In einer Vorgängerversion meiner "rscontrols" 
hatte ich Teile direkt in den Framebuffer geschrieben gehabt (weil ich 
schlicht auch auf Linux-System ohne X unterwegs bin) und hierfür auch 
Teile meiner "eigenen Distribution" verändert.

Nachdem ich das umgestellt hatte auf reine Farbsteuerung über 
ESC-Sequenzen ist fb.h obsolet geworden. Außerdem ist mir - zu meiner 
Schande - auch nicht aufgefallen gewesen, dass fb.h noch einmal explizit 
in rscontrols3.c inkludiert war.

;--) außerdem ist das Progrämmchen inzwischen - Yalu sei Dank - obsolet 
geworden (na ja fast: ich werkel dennoch gerne auf der Konsole).

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.