Schaltalgebra

[annA]

Hallo zusammen,

in der Digitaltechnik verwenden wir KV-Tafeln um logische
Ausdrücke zu vereinfachen:
[http://www-ihs.theoinf.tu-ilmenau.de/~sane/projekte/karnaugh/]
Wie programmiert man sowas??
Die Tafeln müssen nicht grafisch darstellbar sein, möchte nur,
daß mein Programm logische Ausdrücke vereinfach kann.
Würde man sowas am besten mit einem mehrdimensionalen Array lösen,
dieses dann Feld für Feld durchlaufen, Gruppen zusammenfassen etc?

Ist das ein Standard-Probelm?

Freue mich über jede Idee...

Kann mein Taschenrechner TI-83plus das vielleicht sogar schon von alleine?

Viele Grüße
annA

[annA]

Sorry,
Nachtrag des Linkes:
http://www-ihs.theoinf.tu-ilmenau.de/~sane/projekte/karnaugh/

Gruss
annA

[Stephan Huber]

Hallo annA,

in der Digitaltechnik verwenden wir KV-Tafeln um logische
Ausdrücke zu vereinfachen:
[http://www-ihs.theoinf.tu-ilmenau.de/~sane/projekte/karnaugh/]
Wie programmiert man sowas??

Wenn Du es als Programm machen willst, ist das Quine-McCluskey-Verfahren vielleicht besser, Karnaugh geht nur mit Mühen mit mehr als vier Variablen, und QMC lässt sich wohl auch einfacher in ein Programm umsetzen. Und nachdem Du es nicht zeichnen willst, bringts ja nichts, daß Karnaugh intuitiver aussieht ;-)

Mehr über das QMC-Verfahren:
http://qmc.pollaknet.at/index.php
http://www.cs.byu.edu/courses/cs143/reading/quine.html
http://www.eng.uwi.tt/depts/elec/staff/fmuddeen/EE37C/QMA.doc

Würde man sowas am besten mit einem mehrdimensionalen Array lösen,
dieses dann Feld für Feld durchlaufen, Gruppen zusammenfassen etc?

<mit vorsicht geniessen, hab nur kurz drübergeschaut!>
Ich würde bei beiden mit einem mehrdimensionalen Array arbeiten, bei Karnaugh dann noch ein zweites, gleich großes Array, in dem sich das Programm die Markierungen "merken" kann. Da jedes Element zu mehreren Gruppen gehören kann, mußt Du das in diesem zweiten Array als Bitmaske o.ä. speichern. QMC erscheint mir da einfacher, da gibts nur abgehakt und nicht abgehakt.

Viele Grüße
Stephan

[Michael Schröpl]

Hi annA,

Die Tafeln müssen nicht grafisch darstellbar sein, möchte nur,
daß mein Programm logische Ausdrücke vereinfach kann.

Das Hauptproblem Deiner Aufgabenstellung ist meiner Meinung nach, daß der Begriff "vereinfachen" hoffnungslos unterdefiniert ist. Welches Komplexitätsmaß legst Du diesem Begriff zugrunde? (Stringlänge? Klammertiefe? Anzahl Operatoren? Anzahl elementarer Schaltbausteine - und aus welchem Vorrat? Letzteres war mal früher ein Optimierungsziel, wo es hauptsächlich NAND und EXOR gab, oder was auch immer - das waren diese Bausteine direkt ein Kostenfaktor, also mußte man scheinbar triviale Ausdrücke in schauerlicher Weise umschreiben, weil das eigentlich gewünschte Koordinatensystem nicht zur Realität der Hardware paßte ... ist das heute immer noch so?)

Würde man sowas am besten mit einem mehrdimensionalen Array lösen,
dieses dann Feld für Feld durchlaufen, Gruppen zusammenfassen etc?

Algebraische Transformationen direkt durchzuführen ist schwierig, weil es viel Intelligenz erfordert. Operationen wie "Terme ausklammern" aus beliebig komplexen Konstruktionen, das ist nicht in drei Zeilen zu beschreiben.
Wenn Du so etwas willst, solltest Du als Datenmodell einen Operatoren-Baum für den Ausdruck erzeugen. Innerhalb eines solchen Baums lassen sich bestimte Transformationen als Zusammenfassungen und Manipulationen von Teilbäumen formulieren - "Ausklammern" ist beispielsweise eine solche Transformation, die dann über die Suche identischer Teilbäume an 'passenden' Stellen funktionieren würde. Dies alles ist aber hochkomplex ...

Für die Methode mit dem Array spricht, daß Du bei <n> variablen gerade mal 2^n Werte auszurechnen hast. Anschließend aus der vollständigen Wertemenge einzelne Variablen als irrelevant zu erkennen usw., das ist dann der 'tricky' Teil des Problems.

Ist das ein Standard-Problem?

Wenn Du einen vollständigen n-dimensionalen Binärwürfel erzeugt hast, dann kannst Du diesen wohl irgendwie algorithmisch in einen Ausdruck umwandeln, welcher ein OR aus so vielen Termen ist, bis Du alle Werte einer bestimmten Sorte (Nuller, Einser) abgedeckt hast. Das erinnert entfernt an das Knapsack-Problem.
Was Dir bisher fehlt, das ist eine Bewertungsfunktion für die Komplexität eines Ausdruckes - hast Du diese, dann kannst Du überhaupt erst eine Strategie definieren, welche die Minimierung dieser Bewertungsfunktion zum Ziel hat.

Kann mein Taschenrechner TI-83plus das vielleicht sogar schon von alleine?

Momentan sind wir noch im Stadium der Definition der Aufgabenstellung - über Lösungswege können wir später diskutieren.

Viele Grüße
      Michael

[Stephan Huber]

Hallo Michael,

Das Hauptproblem Deiner Aufgabenstellung ist meiner Meinung nach, daß der Begriff "vereinfachen" hoffnungslos unterdefiniert ist.

Der ist quasi durch das Verfahren mitdefiniert - Karnaugh liefert eine bestimmte (MSOP)-Darstellung eines boolschen Ausdrucks, den man dann einfacher (mit weniger Gates) umsetzen kann, wenn man nur AND und OR zur Verfügung hat. Wenn Du sagst, daß da einige schauerliche Umformungen rauskommen, mußt Du erst mal sagen, warum diese Transformation für Dich schauerlicher ist als andere - d.h. Du mußt auf die Metaebene wechseln. Du scheinst kritisieren zu wollen, daß diese Transformation umgangssprachlich auch als "vereinfachen" bezeichnet wird, naja, die meisten Logiker würde Dir das Argument gerne schenken, die Transformation ist gültig, benützt einige wunderschöne Theoreme, und daß sie dann außerhalb der formalen Sprache das Prädikat "vereinfachen" erhält, spielt eigentlich keine Rolle, in der Logik ist das einfache die MSOP-Darstellung.

Kann mein Taschenrechner TI-83plus das vielleicht sogar schon von alleine?

Momentan sind wir noch im Stadium der Definition der Aufgabenstellung - über Lösungswege können wir später diskutieren.

Gib' es zu, TI hat Dich bestochen (ich habe in Google gesucht, für manche HP-Taschenrechner gibt es Programme, die die MSOP ausrechnen ;-)

Viele Grüße
Stephan

[Michael Schröpl]

Hi Stephan,

Der ist quasi durch das Verfahren mitdefiniert - Karnaugh liefert eine bestimmte (MSOP)-Darstellung eines boolschen Ausdrucks, den man dann einfacher (mit weniger Gates) umsetzen kann, wenn man nur AND und OR zur Verfügung hat.

Und ist dies das Ziel? Bei "logisch einfachen" Ausdrücken, die ein Mensch lesen soll, wahrscheinlich schon - aber gibt es AND und OR wirklich als (kostengünstige) Gatter? Genau an dieser Stelle habe ich eben das Gegenteil gelernt ... wobei mein Wissen selbstverständlich veraltet sein kann.

Viele Grüße
      Michael

[Stephan Huber]

Hallo Michael,

Und ist dies das Ziel? Bei "logisch einfachen" Ausdrücken, die ein Mensch lesen soll, wahrscheinlich schon - aber gibt es AND und OR wirklich als (kostengünstige) Gatter? Genau an dieser Stelle habe ich eben das Gegenteil gelernt ... wobei mein Wissen selbstverständlich veraltet sein kann.

Ich hab' das bei den Logikern gelernt, die scheren sich recht wenig wenig um real existierende Siliziumgatter und deren Kosten. Es geht also nur um "Papiergatter", bzw. einfach um die logischen Operatoren und deren Anzahl - die gibts umsonst. (Für die reale Welt hast Du recht, glaube ich).

Viele Grüße
Stephan

[Michael Schröpl]

Hi Stephan,

Ich hab' das bei den Logikern gelernt, die scheren sich recht wenig wenig um real existierende Siliziumgatter und deren Kosten. Es geht also nur um "Papiergatter", bzw. einfach um die logischen Operatoren und deren Anzahl - die gibts umsonst. (Für die reale Welt hast Du recht, glaube ich).

ich habe beide Vorlesungen gehört - zunächst die Strukturtheorie und Boolesche Algebra im Grundstudium, später Rechnerorganisation und Schaltwerke im Hauptstudium.

Es läuft wohl darauf hinaus, daß bestimmte Mengen von Grundoperationen ausreichen, um daraus ein äquivalentes algebraisches Gebilde (Körper? Ring?) zu bauen zu demjenigen mit AND, OR und NOT - und ich glaube mich vage zu erinnern, daß NAND und EXOR dafür auch ausreichen und genau diese beiden eben als elementare Hardware-Gatter verfügbar sind, AND und OR aber nicht ... es wurde damals auch behandelt, wie man konkrete Funktionen zwischen diesen Systemen transformieren kann (weil man sie als Mensch im einen System entwerfen will, aber im anderen System als Hardware bauen muß) ...

Und wenn man tatsächlich etwas optimieren will, dann wohl am sinnvollsten in demjenigen Universum, in dem die Schaltung tatsächlich gebaut (und bezahlt) werden soll.
(Genau wie bei einem optimierenden Hochsprachen-Compiler, der ja auch den Maschinencode optimiert, welchen der Programmierer selbst gar nicht mehr verstehen möchte.)

Das ist aber alles fast 20 Jahre lange her (inzwischen gibt es auch AND-Gatter, wie Google gerade bestätigt). Und heute baut halt auch niemand mehr selbst Rechner, wenn man sich schon beim ALDI kaufen kann. ;-)

Viele Grüße
      Michael