Tool um KV-Diagramme auszuwerten HILFE!

Froggerprogger · Beitrag von **Froggerprogger** » 12.06.2006 10:46

Das Problem ist NP-vollständig, deswegen wirst du an irgendeiner Stelle deines Algorithmus um das Ausprobieren nahezu sämtlicher Kombinationen nicht herumkommen. Ziel sollte daher sein, nur so wenig Kombinationen wie möglich testen zu müssen, indem du z.B. ein Backtracking-Verfahren mit möglichst vielen guten Abbruchbedingungen zu erreichen versuchst.

Ohne die don't cares ist das noch relativ einfach:
- Bestimme erst alle Primimplikanten, also maximal große rechteckige Flächen (die auch über den Rand hinausgehen dürfen), die nur aus Eins-Einträgen bestehen. Starte dazu von jeder 1 aus und schaue die Felder rundherum an (mit Randübersprung) und erweitere es gegebenfalls. Ebenso wenn die Ränder dann 2,3 Felder breit sind.

- behalte von allen mehrfach auftauchenden Primimplikanten jeden nur einmal, also entferne bereits auftauchende.

- Schaue, ob und welche Primimplikanten als einzige unter allen ein Feld überdecken und kennzeichne sie als "essentiell". Diese müssen auf jeden Fall in der endgültigen Formel vorkommen, und so können sie bereits übernommen werden und ihre überdeckte Fläche im weiteren ignoriert.

- Mache nun ein Backtracking mit sämtlichen restlichen Primimplikanten (die irgendwo geordnet gespeichert sind). Also nimm den ersten und falls nicht der gesamte Rest Einsen überdeckt wird, dann den zweiten, etc. bis alle restlichen Einsen überdeckt sind. Dann breche ab und merke dir das Ergebnis und gehe einen Schritt zurück (entferne den zuletzt hinzugefügten Primimplikanten) und füge einen anderen hinzu. Usw.
Also durchlaufe einmal komplett den Baum. In jedem Schritt schaust du dabei, ob die aktuelle potentielle Lösung bereits schlechter als die bereits gefundene wäre, in diesem Fall kannst du den gesamten Zweig ignorieren, den zuletzt hinzugefügten rauswerfen und mit dem nächsten fortfahren.
Außerdem beachte die Kommutativität - du brauchst also auf die Reihenfolge der Primimplikanten nicht zu achten, das spart ebenfalls viele Testkombinationen.

Ein einfaches Verfahren mit don't cares wäre nun, obigen Algorithmus für sämtliche möglichen Belegungskombinationen der don`t cares durchzuführen. Enthält das KV-Diagramm also bspw. 5 don`t cares, so müsstest du obigen Algorithmus 2^5 mal durchführen und jeweils die beste Lösung speichern und nachher vergleichen. Hier ließe sich mit etwas weiterem Gehirnschmalz aber bestimmt noch etwas optimieren. Allerdings wird es - da NP-vollständig - tendenziell zu dieser exponentiellen Laufzeit führen.

Wenn du diese Methode nicht nur für Lernzwecke, sondern in einer Software verwenden willst, dann schau dir lieber das Quine-McCluskey-Verfahren an. Dafür gibt es auch gute Implementationsrichtlinien und es ist insbesondere bei größeren Problemen schneller. Außerdem lassen sich dort gute Heuristiken mit polynomieller Laufzeit anwenden. Also Verfahren, die wesentlich schneller sind, aber nicht immer die beste Lösung finden.

btw: Deine Anwendung ist sehr schön und übersichtlich gestaltet!

Karl · Beitrag von **Karl** » 12.06.2006 11:01

@Froggerprogger:

Ich persönlich finde Quine-McCluskey auch besser. Allerdings erfordert die Bestimmung der Kernimplikanten wohl etwas "Kreativität" von Seiten des Rechners (möglichst maximale Abdeckungen). Willste das auch mit Backtracking lösen?

Gruß Karl

Frogger · Beitrag von **Frogger** » 12.06.2006 11:47

Warum nimmst du nur zwei Variablen. Es wird erst ab 6 unübersichtlich.

KV-Diagramme mit 6 Variablen ist schon ne ganz andere Liga.
Das Tool brauche ich in erster Linie um mir etwas Arbeit mit der LOGO! zu ersparen. (wenn ich in 2 Wochen damit fertig bin, kann ich das Tool gut für die Präsentation von meinem LOGO! Projekt gebrauchen)
Deswegen reichen erstmal 4 Variablen, denn die LOGO! hat auch nur max. 4 Eingänge.

Das mit den 2 Variablen hab ich schon gelöst, indem ich alle Kombinationen abgefragt habe. Allerdings ohne Don't-Care Stellen.
Ich kann mir aber nicht vorstellen KV's mit 4 Variablen auf die gleiche Art zu lösen. Es wären dann 256 Kombinationen, die ich alle durchgehen müsste.

Die "konjunktive Normalform" ist in den Tat am einfachsten. Die werde ich wahrscheinlich als erste einfügen.
Mann muss nur gucken bei welchen Variablen eine 1 steht und diese Variablen in einer Klammer mit UND verknüpfen und die Klammern untereinander mit ODER.
Die Don't-Care's kann man ignorieren oder?

Ich denke mal Backtracking ist die beste Methode für dieses Problem aber ich bin auch bereit mich eines Besseren belehren zu lassen.

Über das Quine-McCluskey-Verfahren muss ich mich noch genauer informieren.

Hattet ihr das schonmal Softwaremäßig gelöst?

Vielen dank für die guten Tipps

Froggerprogger · Beitrag von **Froggerprogger** » 12.06.2006 12:23

Allerdings erfordert die Bestimmung der Kernimplikanten wohl etwas "Kreativität" von Seiten des Rechners (möglichst maximale Abdeckungen)

Was genau sprichst du da an? Ich denke, das Finden der Kernimplikanten (=essentieller Primimplikanten - also solcher Primimplikanten die irgendeinen Minterm als einzige überdecken) dürfte doch gar nicht schwer sein, wenn man alle Primimplikanten hat ? Die Kernimplikanten sind doch sämtlich eindeutig bestimmt ? Möglicher Algorithmus:

Code: Alles auswählen

- Erzeuge ein Array mit den Dimensionen wie das KV-Diagramm, das je Feld einen Counterwert und eine Referenz auf einen Primimplikanten speichert
- Für alle Primimplikanten P: Trage an allen von P überdeckten Stellen eine Referenz auf P ein und erhöhe den dortigen Counter um eins.
- Untersuche alle Felder. Wenn Eintrag 1, dann kennzeichne den Primimplikanten als essentiell, also nehme ihn zur Gesamtlösung hinzu.

Nun kann man noch alle absolut inessentiellen Primimplikanten rausschmeißen, also all solche, die nur Minterme überdecken, die bereits von Kernimplikanten überdeckt sind. Verfahren ähnlich wie eben: Erzeuge ein solches Array und kennzeichne alle Felder, die von den essentiellen Primimplikanten überdeckt werden. Untersuche nun alle anderen Primimplikanten, ob darunter welche sind, die ausschließlich gekennzeichnete Felder überdecken. Diese Primimplikanten können entfernt werden, da sie nichts neues zur Gesamtlösung hinzusteuern können.

Erst ab jetzt beginnen die Probleme aufgrund von Wahlmöglichkeiten, aber bis hierhin war alles eindeutig festgelegt.

[edit]

Die "konjunktive Normalform" ist in den Tat am einfachsten. Die werde ich wahrscheinlich als erste einfügen.
Mann muss nur gucken bei welchen Variablen eine 1 steht und diese Variablen in einer Klammer mit UND verknüpfen und die Klammern untereinander mit ODER.

Dann hast du aber doch eine Summe von Mintermen, also eine DNF.

Die Don't-Care's kann man ignorieren oder?

Ja. Für die Minterm/Maxterm-Normalform, also z.B. die wie eben erhaltene DNF, sind sie irrelevant, da ja egal ist, was dabei für ein Ergebnis herauskommt. Erst auf die Minimierung des Ausdrucks wirken sie sich aus.

Ich denke mal Backtracking ist die beste Methode für dieses Problem aber ich bin auch bereit mich eines Besseren belehren zu lassen.

Solange du eine minimale Form finden möchstest ist zumindest ein Verfahren wie Backtracking optimal, trotz exponentieller Laufzeit.

Über das Quine-McCluskey-Verfahren muss ich mich noch genauer informieren. Hattet ihr das schonmal Softwaremäßig gelöst?

Ich noch nicht. Aber das sollte nicht allzu schwierig sein, da es auch zahlreiche Pseudo-codes hierzu gibt.

Frogger · Beitrag von **Frogger** » 12.06.2006 13:03

Code: Alles auswählen

  ;{/ konjunktiv
  
  
  If Matrix3(0) = 1
    ergebnisskon + "(!A^!B^!C)"
  EndIf
  
  If Matrix3(1) = 1
    If Matrix3(0) = 1
      ergebnisskon + " v "
    EndIf
    ergebnisskon + "(A^!B^!C)"
  EndIf
  
  If Matrix3(2) = 1
    If Matrix3(1) = 1 Or Matrix3(0) = 1
      ergebnisskon + " v "
    EndIf
    ergebnisskon + "(!A^B^!C)"
  EndIf
  
  If Matrix3(3) = 1
    If Matrix3(2) = 1 Or Matrix3(1) = 1 Or Matrix3(0) = 1 
      ergebnisskon + " v "
    EndIf
    ergebnisskon + "(A^B^!C)"
  EndIf
  
  If Matrix3(4) = 1
    If Matrix3(3) = 1 Or Matrix3(2) = 1 Or Matrix3(1) = 1 Or Matrix3(0) = 1
      ergebnisskon + " v "
    EndIf
    ergebnisskon + "(!A^!B^C)"
  EndIf
  
  If Matrix3(5) = 1
    If Matrix3(4) = 1 Or Matrix3(3) = 1 Or Matrix3(2) = 1 Or Matrix3(1) = 1 Or Matrix3(0) = 1
      ergebnisskon + " v "
    EndIf
    ergebnisskon + "(A^!B^C)"
  EndIf
  
  If Matrix3(6) = 1
    If Matrix3(5) = 1 Or Matrix3(4) = 1 Or Matrix3(3) = 1 Or Matrix3(2) = 1 Or Matrix3(1) = 1 Or Matrix3(0) = 1
      ergebnisskon + " v "
    EndIf
    ergebnisskon + "(!A^B^C)"
  EndIf
  
  If Matrix3(7) = 1
    If Matrix3(6) = 1 Or Matrix3(5) = 1 Or Matrix3(4) = 1 Or Matrix3(3) = 1 Or Matrix3(2) = 1 Or Matrix3(1) = 1 Or Matrix3(0) = 1
      ergebnisskon + " v "
    EndIf
    ergebnisskon + "(A^B^C)"
  EndIf
  
  
  ;}

Das ist meine Lösung für ein KV-Diagramm mit 3 Eingängen. Das Ergebniss ist eine konjunktive Normalform
Mann kann jetzt die erzeugte Funktion analysieren und sie zu einer disjunktiven Normalform umformen ohne Backtracing anzuwenden.
Für die Don't-Care-Stellen müsste man sich dann später was einfallen lassen.

Bsp.:

konjunktiv: f() = (!A^!B^C) v (A^!B^C)
vereinfacht: f() = (!B^C)
!A und A heben sich gegenseitig auf

noch ein Bsp.:

konjunktiv: f() = (!A^!B^C) v (A^!B^C) v (!A^B^C) v (A^B^C)
vereinfacht: f() = (!B^C) v (B^C)
weiter vereinfacht: f() = C

Was meint ihr dazu?

Karl · Beitrag von **Karl** » 12.06.2006 14:24

@Froggerprogger:

Nein, ich meine es gibt Situationen, in denen zur Überdeckung eines Minterms eine oder mehrere Implikanten vorhanden sind, ich aber mindestens zwei benötige. Zur Minimierung der DNF sollte ich aber die Implikanten mit der größten Überdeckung aller Minterme wählen. OK, sie sind dann höchstwahrscheinlich keine Kernimplikanten, weil sie von mindestens einem anderen überdeckt werden.

Bsp:

0 1 5 4
2 3 7 6
10 11 15 14
8 9 13 12

markierte Minterme: 1, 3, 11, 9, 5, 7, 15, 13, 10, 14

@Frogger:

C ist keine DNF, sondern nur eine Variable. KNFs erreichst du, indem du alle mit 0 gekennzeichneten Stellen invertierst (DeMorgan) und die so entstandenen Maxterme aufUNDest.

Froggerprogger · Beitrag von **Froggerprogger** » 12.06.2006 15:30

@frogger

konjunktiv: f() = (!A^!B^C) v (A^!B^C)

ist keine KNF, sondern DNF

f() = C als Ausdruck aufgefasst ist in DNF und KNF.
Was du hier aber versuchst, ist eine minimale Form durch algebraische Umformungen (der booleschen Algebra) zu finden. Das hat mit KV-Diagrammen nicht mehr viel zu tun, aber ist eine Alternative zu KV-Diagrammen und Quine-McCluskey. Allerdings kann das schnell sehr kompliziert werden, da man durch geschicktes Ausklammern und umständliche Zwischenergebnisse oft später noch weiter reduzieren kann.

@Karl
Ich sehe noch nicht ganz, was du meinst. In deinem Beispiel gibt es genau zwei verschiedene Primimplikanten, einmal
(1,3,5,7,9,11,13,15)
und (10,11,14,15)
Beide überdecken zwar die Felder (Minterme) 11 und 15, aber sind trotzdem beide essentiell (also Kernimplikanten), da sie beide auch Felder überdecken, die von keinem anderen überdeckt werden. Es genügt ja ein einziger Minterm, der von keinem anderen Primimplikanten überdeckt wird, damit ein Primimplikant Kernimplikant ist. Hier kann man die minimale Form also direkt ablesen, da die beiden einzigen Primimplikanten Kernimplikanten sind.
Implikanten gibt es in deinem Beispiel wesentlich mehr, so sind z.B. alle Minterme selbst Implikanten und ebenso alle möglichen 2er-Ketten, die noch weiter vergrößert werden können.

Nochmal grad zu den Begriffen. Zuerst werden alle Implikanten (wie auch Minterme selbst welche sind) zu Primimplikanten 'aufgepumpt' (also Implikanten maximaler Größe). Dann kann man die Kernimplikanten (also essentielle Primimplikanten) falls vorhanden rausnehmen. Nun bleiben eine Reihe von Primimplikanten übrig, unter denen eine minimale Überdeckung des Rests gefunden werden muss. In diesem Beispiel hier:
1111
1110
1111
1001
gibt es z.B. eine ganze Menge Primimplikanten, allerdings keine Kernimplikanten, da es für jeden Minterm mehrere mögliche Primimplikanten für die Überdeckung gibt. Dann beginnt die Krux, zunächst möglichst bei den großen beginnend welche herauszupicken.

Karl · Beitrag von **Karl** » 13.06.2006 09:14

@Froggerprogger:

Genau eben nicht:

Nur einer der beiden angegebenen Terme kann ein Kernimplikant sein , obwohl beide Primterme sind.

Aber ein vielleicht besseres Beispiel mit einem überflüssigen Primterm:

Markierte Felder: 2, 3, 6, 7, 9, 11, 13, 15
___________________________________

Es gibt auch Situationen, in denen es mehr als eine beste Lösung gibt.

Gruß Karl

Froggerprogger · Beitrag von **Froggerprogger** » 13.06.2006 09:59

@Karl
Laut Definition ist ein Primimplikant Kernimplikant, wenn er irgendeinen Minterm als einziger unter allen vorkommenden Primimplikanten überdeckt. Da die Funktion ja auch für diesen Minterm 1 liefern muss, muss dieser Primimplikant also auch in der minimalen Form vorkommen.

In deinem ersten Beispiel überdeckt: (1,3,5,7,9,11,13,15) als einziger bspw. den Minterm 1 und (10,11,14,15) überdeckt als einziger den Minterm 10. Damit sind bereits beide Kernimplikanten und müssen in der Lösung auftauchen.

In deinem neuen Beispiel gibt es die Primimplikanten P1 = (2, 3, 6, 7), P2 = (9,11,13,15) und P3 = (3,7,11,15)
Dabei überdeckt P1 als einziger die 2 und P2 als einziger die 13, also sind diese beiden bereits Kernimplikanten und müssen in der Lösung vorkommen. P3 ist nicht Kernimplikant, da alle Felder, die er überdeckt auch von anderen Primimplikanten überdeckt werden. Er ist sogar absolut inessentiell, da er nur Felder überdeckt, die von Kernimplikanten überdeckt werden und kann daher ignoriert werden. Eine minimale SOP ist also P1 \/ P2

Karl · Beitrag von **Karl** » 13.06.2006 10:55

OK, ja es ist so (das Beispiel war wirklich nicht geeignet). Prim und Kern, beide.

Aber hier eine Sache, die mehrere Lösungen zulässt:

1, 2, 5, 6, 7

Mindestens ein Primkern ist kein Kernimplikant.

Gruß Karl