Schaltalgebra mit McCluskey-Implikationen history menue Letztmalig dran rumgefummelt: 09.09.21 18:01:42
Ob ich via Kanonische Normalformen wirklich die kürzeste Gleichung erwischt habe bleibt so lange in Frage, bis zu sämtlichen Kombinationen einschließlich ihrer Negationen alle Ersetzungen durchprobiert worden sind. Anschließend werden die de Morgan'schen Theoreme zur Gelichungszusammenfassung eingesetzt. Hier genau setzen die Karnaugh-Veitch-Diagramme an - sie zeigen von vornherein, ob es überhaupt eine Vereinfachung gibt - und wenn ja, gewinne ich sofort die optimierte Gleichung (bzw. eine davon, was meistens der Fall ist - es gibt von vornherein meist mehrere gleichwertige optimierte Lösungsvarianten).
 Das Karnaugh-Diagramm (Karnaugh-Veitch-Diagramm, KV-Diagramm) enthält in gedrängter Form die Informationen der Wertetabelle. Das Karnaugh-Diagramm hat bei n Eingangsvariablen 2n Felder (Bilder unten). In die Felder wird 1 eingetragen, wenn der UND-Term der Eingangsvariablen den Wert 1 der Schaltfunktion liefert. Die anderen Felder erhalten den Wert 0, wobei das entscheidende die hexdezimal gesplittete Anordnung der Zielfelder sowie ihre logische Zusammenfassung ist.
 Die Bestimmung der reduzierten Schaltfunktion ist bei mehr als zwei Eingangsvariablen mit Hilfe des Karnaugh-Diagramms meist einfacher als mit schaltalgebraischen Mitteln.
1. Maurice Karnaugh
2. Grundaufbau von Karnaugh-Veitch-Tafeln
3. Eintragen logischer Funktionen in KV-Diagramme
4. Auswerten von Karnaugh-Veitch-Tafeln
5. Verwandte Themen
6. Übungsaufgaben zu KV-Diagrammen
7. Linksammlung zu KV-Diagrammen

Schaltungssythese

McClusky - das Logo

inhaltlich auf korrektem Stand - evtl. partiell unvollständig ;-)

Wissen für Fortgeschrittene der Informatik

Das Kombinatorik-Projekt

Logik-Projekt 2012
1. Edward Joseph McCluskey - mein Rechenbeispiel history menue scroll up

Edward Joseph McCluskey, Jr. (* 16. Oktober 1929; † 13. Februar 2016) war Elektrotechnik- und Informatik-Professor an der Stanford University. Er entwarf 1956 als Doktorand am MIT gemeinsam mit Willard Quine den Quine-McCluskey-Algorithmus, eine der effizientesten Methoden zum Minimieren Boolescher Funktionen. Der Schwerpunkt seiner Arbeit in Stanford liegt im Design und in der Entwicklung fehlertoleranter Systeme und entsprechender Testszenarien bzw. Verifikationen. McCluskey wurde auch der erste Präsident der Computersparte des IEEE, deren Mitglied er weiterhin ist, ebenso wie des AAAS und der Association for Computing Machinery. Er wurde 2012 mit der John-von-Neumann-Medaille ausgezeichnet.

Quelle: WIKIPEDIA

Definition Binärzahlen
... und weil ich das jedes Jahr neu lernen muss, habe ich mir gedacht: "... schreiben wir's doch mal ganz detailliert mit Beispiel auf!" ... los geht's:
  • ... Prinzip ist es (wie auch bereits bei den Karnagh/Veitch-Tafeln, logische Eingangssignale, welche auf das Ergebnis keinen Einfluss haben, zu eliminieren
  • gesucht werden Veränderungen in genau einem Bit zweier Lösungsgruppen
  • die Ausgänge können dabei beliebig logisch "0" oder "1" sein - Sinn macht die Logik am Ausgang, welche sich besser zusammenfassen lässt
  •  
gegebene Logiktabelle dazugehörige Logikgleichungen dazugehörige Kanonik

Anne's Ausganstabelle

das Original im WORD-Format

Logikgleichungen zum Projekt

Kanonisch konjunktive Normalform

Download als ProfiLab 4.0-Datei
Implikation 0. Ordnung suchen Implikation 1. Ordnung suchen dazugehörige Kanonik
Ausgang y1 Ausgang y0
Zeile X3 X2 X1 X0 HEX
0 0 0 0 0 00H
2 0 0 1 0 02H
9 1 0 0 1 09H
15 1 1 1 1 0FH
Zeile X3 X2 X1 X0 HEX
7 0 1 1 1 07H
10 0 0 1 0 0AH
14 1 1 1 0 0EH
Ausgang y1 Ausgang y0
Zeile X3 X2 X1 X0
0, 2 0 0 - 0
10 1 0 1 0
         
Zeile X3 X2 X1 X0
7 0 1 1 1
10 1 0 1 0
14 1 1 1 0

Logik-Projekt 2012
quine mccluskey – Google Suche

2. Grundaufbau von McClusky-Tafeln history menue scroll up

In der ersten Implikationsstufe werden ähnlich den Karnaugh-Tafeln nur die "Eins" gesetzten Zeilen herausgesucht - allerdings notieren wir hier die gesetzten Bitkombinatinen - nicht ihre maximal Nähe, wie beim Kar´naugh-Verfahren
Es werden so genannte "Implikationen" gesucht und zusammengefasst. Implizieren heißt "Verbinden", "Einschließen"
McCluskey-Implikations-Tafel für n=2
Zeile HEX-Wert x1 x0 y Implikation 1. Ordnung
0. 00H 0 0

X1 x0
1. 01H 0 1    
2. 02H 1 0    
3. 03H 1 0    

Vorgegebene Logiktabelle
  • ein Implikant 0. Ordnung entspricht einer Zeile in einer Wahrheitstafel.
  • die Zählung der Zeilennummern beginnt mit 0!!!
  • somit ist es die eine Zusammensetzungen aus logischen Ein- sowie Ausgängen
  • ein Primimplikant ist ein Implikant, der nicht weiter mit anderen zusammengefasst werden kann

 
McCluskey-Implikations-Tafel für n=3
Zeile HEX-Wert x2 x1 x0 y
1. 00H 0 0 0  
2. 01H 0 0 1  
3. 02H 0 1 0  
4. 03H 0 1 0  
5. 04H 1 0 1  
6. 05H 1 0 0  
7. 06H 1 1 1  
8. 07H 1 1 0  

Vorgegebene Logiktabelle

Resultierende Karnaugh-Veitch-Tafel für 3-Eingangs-Logiken (richtig seit 18.11.2012)

  • ein Implikant entspricht einer Zeile in einer Wahrheitstafel. Somit ist es die eine Zusammensetzungen aus logischen Ein- sowie Ausgängen
  • ein Primimplikant ist ein Implikant, der nicht weiter mit anderen zusammengefasst werden kann
McCluskey-Implikations-Tafel für n=4
Zeile HEX-Wert x3 x2 x1 x0 y
1. 00H 0 0 0 0  
2. 01H 0 0 0 1  
3. 02H 0 0 1 0  
4. 03H 0 0 1 1  
5. 04H 0 1 0 0  
6. 05H 0 1 0 1  
7. 06H 0 1 1 0  
8. 07H 0 1 1 1  
9. 08H 1 0 0 0  
10. 09H 1 0 0 1  
11. 0AH 1 0 1 0  
12. 0BH 1 0 1 1  
13. 0CH 1 1 0 0  
14. 0DH 1 1 0 1  
15. 0EH 1 1 1 0  
16. 0FH 1 1 1 1  

Vorgegebene Logiktabelle

Resultierende Karnaugh-Veitch-Tafel für 4-Eingangs-Logiken (richtig seit 17.11.2012)

  • ein Implikant entspricht einer Zeile in einer Wahrheitstafel. Somit ist es die eine Zusammensetzungen aus logischen Ein- sowie Ausgängen
  • ein Primimplikant ist ein Implikant, der nicht weiter mit anderen zusammengefasst werden kann
McCluskey-Implikations-Tafel für n=5
Zeile HEX-Wert x4 x3 x2 x1 x0 y
1. 00H 0 0 0 0 0  
2. 01H 0 0 0 0 1  
3. 02H 0 0 0 1 0  
4. 03H 0 0 0 1 1  
5. 04H 0 0 1 0 0  
6. 05H 0 0 1 0 1  
7. 06H 0 0 1 1 0  
8. 07H 0 0 1 1 1  
9. 08H 0 1 0 0 0  
10. 09H 0 1 0 0 1  
11. 0AH 0 1 0 1 0  
12. 0BH 0 1 0 1 1  
13. 0CH 0 1 1 0 0  
14. 0DH 0 1 1 0 1  
15. 0EH 0 1 1 1 0  
16. 0FH 0 1 1 1 1  
17. 10H 1 0 0 0 0  
18. 11H 1 0 0 0 1  
19. 12H 1 0 0 1 0  
20. 13H 1 0 0 1 1  
21. 14H 1 0 1 0 0  
22. 15H 1 0 1 0 1  
23. 16H 1 0 1 1 0  
24. 17H 1 0 1 1 1  
25. 18H 1 1 0 0 0  
26. 19H 1 1 0 0 1  
27. 1AH 1 1 0 1 0  
28. 1BH 1 1 0 1 1  
29. 1CH 1 1 1 0 0  
30. 1DH 1 1 1 0 1  
31. 1EH 1 1 1 1 0  
32. 1FH 1 1 1 1 1  

Vorgegebene Logiktabelle

Resultierende Karnaugh-Veitch-Tafel für 5-Eingangs-Logiken  (richtig seit 18.11.2012)

 

Karnaugh-Veich-Diagramm für maximal 6 Eingangsvariable (hier a bis f)

  • ein Implikant entspricht einer Zeile in einer Wahrheitstafel. Somit ist es die eine Zusammensetzungen aus logischen Ein- sowie Ausgängen
  • ein Primimplikant ist ein Implikant, der nicht weiter mit anderen zusammengefasst werden kann
McCluskey-Implikations-Tafel für n=6
Zeile x5 x4 x3 x2 x1 x0 y
1. 0 0 0 0 0 0
2. 0 0 0 0 0 1
3. 0 0 0 0 1 0
4. 0 0 0 0 1 1
5. 0 0 0 1 0 0
6. 0 0 0 1 0 1
7. 0 0 0 1 1 0
8. 0 0 0 1 1 1
9. 0 0 1 0 0 0
10. 0 0 1 0 0 1
11. 0 0 1 0 1 0
12. 0 0 1 0 1 1
13. 0 0 1 1 0 0
14. 0 0 1 1 0 1
15. 0 0 1 1 1 0
16. 0 0 1 1 1 1
17. 0 1 0 0 0 0
18. 0 1 0 0 0 1
19. 0 1 0 0 1 0
20. 0 1 0 0 1 1
21. 0 1 0 1 0 0
22. 0 1 0 1 0 1
23. 0 1 0 1 1 0
24. 0 1 0 1 1 1
25. 0 1 1 0 0 0
26. 0 1 1 0 0 1
27. 0 1 1 0 1 0
28. 0 1 1 0 1 1
29. 0 1 1 1 0 0
30. 0 1 1 1 0 1
31. 0 1 1 1 1 0
32. 0 1 1 1 1 1
33. 1 0 0 0 0 0
34. 1 0 0 0 0 1
35. 1 0 0 0 1 0
36. 1 0 0 0 1 1
37. 1 0 0 1 0 0
38. 1 0 0 1 0 1
39. 1 0 0 1 1 0
40. 1 0 0 1 1 1
41. 1 0 1 0 0 0
42. 1 0 1 0 0 1
43. 1 0 1 0 1 0
44. 1 0 1 0 1 1
45. 1 0 1 1 0 0
46. 1 0 1 1 0 1
47. 1 0 1 1 1 0
48. 1 0 1 1 1 1
49. 1 1 0 0 0 0
50. 1 1 0 0 0 1
51. 1 1 0 0 1 0
52. 1 1 0 0 1 1
53. 1 1 0 1 0 0
54. 1 1 0 1 0 1
55. 1 1 0 1 1 0
56. 1 1 0 1 1 1
57. 1 1 1 0 0 0
58. 1 1 1 0 0 1
59. 1 1 1 0 1 0
60. 1 1 1 0 1 1
61. 1 1 1 1 0 0
62. 1 1 1 1 0 1
63. 1 1 1 1 1 0
64. 1 1 1 1 1 1

Vorgegebene Logiktabelle
Zeile x5 x4 x3 x2 x1 x0 y
1. 0 0 0 0 0 0  
2. 0 0 0 0 0 1  
3. 0 0 0 0 1 0  
4. 0 0 0 0 1 1  
5. 0 0 0 1 0 0  
6. 0 0 0 1 0 1  
7. 0 0 0 1 1 0  
8. 0 0 0 1 1 1  
9. 0 0 1 0 0 0  
10. 0 0 1 0 0 1  
11. 0 0 1 0 1 0  
12. 0 0 1 0 1 1  
13. 0 0 1 1 0 0  
14. 0 0 1 1 0 1  
15. 0 0 1 1 1 0  
16. 0 0 1 1 1 1  
17. 0 1 0 0 0 0  
18. 0 1 0 0 0 1  
19. 0 1 0 0 1 0  
20. 0 1 0 0 1 1  
21. 0 1 0 1 0 0  
22. 0 1 0 1 0 1  
23. 0 1 0 1 1 0  
24. 0 1 0 1 1 1  
25. 0 1 1 0 0 0  
26. 0 1 1 0 0 1  
27. 0 1 1 0 1 0  
28. 0 1 1 0 1 1  
29. 0 1 1 1 0 0  
30. 0 1 1 1 0 1  
31. 0 1 1 1 1 0  
32. 0 1 1 1 1 1  
33. 1 0 0 0 0 0  
34. 1 0 0 0 0 1  
35. 1 0 0 0 1 0  
36. 1 0 0 0 1 1  
37. 1 0 0 1 0 0  
38. 1 0 0 1 0 1  
39. 1 0 0 1 1 0  
40. 1 0 0 1 1 1  
41. 1 0 1 0 0 0  
42. 1 0 1 0 0 1  
43. 1 0 1 0 1 0  
44. 1 0 1 0 1 1  
45. 1 0 1 1 0 0  
46. 1 0 1 1 0 1  
47. 1 0 1 1 1 0  
48. 1 0 1 1 1 1  
49. 1 1 0 0 0 0  
50. 1 1 0 0 0 1  
51. 1 1 0 0 1 0  
52. 1 1 0 0 1 1  
53. 1 1 0 1 0 0  
54. 1 1 0 1 0 1  
55. 1 1 0 1 1 0  
56. 1 1 0 1 1 1  
57. 1 1 1 0 0 0  
58. 1 1 1 0 0 1  
59. 1 1 1 0 1 0  
60. 1 1 1 0 1 1  
61. 1 1 1 1 0 0  
62. 1 1 1 1 0 1  
63. 1 1 1 1 1 0  
64. 1 1 1 1 1 1  

Resultierende Karnaugh-Veitch-Tafel für 6-Eingangs-Logiken

  • ein Implikant entspricht einer Zeile in einer Wahrheitstafel. Somit ist es die eine Zusammensetzungen aus logischen Ein- sowie Ausgängen
  • ein Primimplikant ist ein Implikant, der nicht weiter mit anderen zusammengefasst werden kann

3. Eintragen der logischen Funktionen in KV-Diagramme history menue scroll up
Das Karnaugh-Veitch-Diagramm ist primär nichts anderes, als eine andere (eigentlich sogar kürzere!) Schreibweise der Wertetabelle einer logischen Funktion. Felder werden eigentlich nur noch für die Ergebnisse der Funktion vorgesehen - und das sind immer so viele, wie die Funktion maximale Schaltkombinationen hat.
Beispiel 1:
jjghjghj
a b c d x
0 1 0 1 1
1 1 1 0 1
1 0 1 1 1
0 0 0 1 1
alle übrigen 0

 

 Übertragen Sie aus nebenstehender Wertetabelle die Schaltkombinationen, die x = 1 liefern, in ein Karnaugh-Diagramm!
Lösung: Das Karnaugh-Diagramm hat 24 = 16 Felder Für die erste Zeile der Wertetabelle a b c d sucht man im Diagramm das Feld, welches keine a-Markierung (Felder 1 bis 8), welches b-Markierung (verbleiben Felder 3, 4, 7, 8), welches keine c-Markierunc (verbleiben Felder 4, 8) und welches d-Markierunc (verbleibt Feld 8) enthält. Entsprechend überträg man die restlichen Zeilen der Wertetabelle.
Jeder Zeile der Wertetabelle entspricht ein Feld im KV-Diagramm. Die Streifen für die Variablen (a, b, c, d) können im KV-Diagramm auch anders liegen, z. B. a mit d getauscht.
Beispiel 2:
Zeile x3 x2 x1 x0 y HEX-Code
1. 0 0 0 0 0 00H
2. 0 0 0 1 0 01H
3. 0 0 1 0 0 02H
4. 0 0 1 1 0 03H
5. 0 1 0 0 0 04H
6. 0 1 0 1 0 05H
7. 0 1 1 0 1 06H
8. 0 1 1 1 1 07H
9. 1 0 0 0 0 08H
10. 1 0 0 1 0 09H
11. 1 0 1 0 0 0AH
12. 1 0 1 1 0 0BH
13. 1 1 0 0 1 0CH
14. 1 1 0 1 0 0DH
15. 1 1 1 0 1 0EH
16. 1 1 1 1 0 0FH

Gegebene Tabelle
4. Auswerten von Karnaugh-Veitch-Tafeln history menue scroll up
Maximal zusammengefasst werden minimal benachbarte Felder (so schön hab' ich das in keiner Definition gefunden). Die Zusammenfassung muss immer so erfolgen, dass ein Block 1, 2, 4 oder 8 Felder enthält, die ein Rechteck oder ein Quadrat bilden und deren Gesamtanzahl geradzahlig ist (außer 1!!!). Benachbarte Felder sind auch Felder der letzten und der ersten Zeile und der letzten und der ersten Spalte. Die einzelnen Felder dürfen auch in mehreren Zusammenfassungen vorkommen.
Jede Zusammenfassung im Karnaugh-Diagramm soll möglichst viele Felder enthalten. Die Zahl der Zusammenfassungen soll möglichst klein sein. Jede Zusammenfassung (Block) bildet ein Glied der gesuchten Schaltfunktion. Die Variablen, die innerhalb des Blocks ihren Zahlenwert nicht ändern, werden miteinander durch die UND-Funktion verknüpft. Die sich ergebenden Terme der Blöcke verknüpft man durch die ODER-Funktion. Diese schaltalgebraische Gleichung ist die reduzierte Schaltfunktion. Die Zusammenfassung der Felder mit dem Wert 1 im Karnaugh-Diagramm liefert die reduzierte Schaltfunktion für die Ausgangsvariable s. Überwiegen im Diagramm die Felder mit dem Wert 1, so ist es zweckmäßig durch Blockbildung der Felder mit dem Wert 0 den Wert s der Ausgangsvariablen zu ermitteln. Durch nochmaliges Negieren von s erhält man dann den Wert s der Ausgangsvariablen.
  • wenn benachbarte Felder eine 1 enthalten, werden sie zusammengefasst
  • diese Zusammenfassung darf keine Nullen enthalten
  • die Zusammenfassungen müssen Rechtecke sein
  • die Gruppen dürfen sich überlappen
  • eine Gruppe darf nicht vollständig von einer anderen Gruppe umschlossen werden
  • die Anzahl der Felder die man zusammenfasst, muss einer Potenz der Zahl 2 entsprechen, also 1, 2, 4, 8, 16, ...
  • die Zusammenfassung kann auch über die Ränder des Diagramms hinausgehen, also z.B. Feld 3 und 7, oder 6 und 14
  • alle zusammengehörenden Felder sollten über jeweils eine 2-Eingangs-AND-Logik geschalten werden können (solange die Eingangsanzahl kleiner 5 ist - Einzelfelder benötigen hier bereits eine 3-Eingangs-AND-Logik
    •
5. Verwandte Themen history menue scroll up

Hat schon diese Site viel mit Logik zu tun, so kann's auf einer der folgenden damit noch happiger werden. Mich beeindruckt dabei immer wieder, wie man unter dem unwissenden Volk (das bist Du, der Du erarbeitend bis zu diesem Punkte gelangt bist, schon lange nicht mehr!) mit den Wörtchen "und", "oder" und "nicht" evtl. gespickt mit den Regeln der Schachtelung sowie Relationenalgebra Verwirrung stiften kann. Wer's nicht glaubt, löst die Aufgaben unter dem dritten Verweis - aber bitte alle - und das schnell ;-)

Praktischer Entwurf von Logikschaltungen

Schaltungen mit IC's

Installation von Logikschaltungen

komplexe Logiken

Logikfunktionen und technologische Fertigungsverfahren

Transistor-Kennlinienfeld

 

Beschreibung des Eingangssignalverhaltens für die Party-Aufgabe

Übersicht der logischen Grundfunktionen

TTL-Liste

zur CMOS-Liste

EPROM-Logik

ROM-Logik

1 aus n-Decoder

Bool'sches Aussagenkalkül

Multiplexer

logische Arrays

de Morgan'schen Theoreme

 

    

6. Übungsaufgaben zu KV-Diagrammen history menue scroll up
Alle der nachfolgenden Aufgaben beziehen irgendwie die logische Zuordnung und/oder kanonische Normalformen in die Lösungsstrategien ein (wenngleich das auch prinzipiell anders geht). Dabei liefern die KV-Diagramme, wenn überhaupt möglich (also Blöcke gebildet werden können ) von vornherein eine fast optimierte Lösung.

Michael Krasselts Extrem-Logik von 2012/2013
Zeile x3

x2

 x1 x0 y1 y0
1. 0 0 0 0 1 0
2. 0 0 0 1 1 0
3. 0 0 1 0 1 0
4. 0 0 1 1 1 0
5. 0 1 0 0 1 1
6. 0 1 0 1 0 0
7. 0 1 1 0 0 0
8. 0 1 1 1 0 1
9. 1 0 0 0 0 0
10. 1 0 0 1 1 1
11. 1 0 1 0 0 1
12. 1 0 1 1 1 1
13. 1 1 0 0 0 0
14. 1 1 0 1 1 0
15. 1 1 1 0 0 1
16. 1 1 1 1 0 1

Logik-Aufgaben 2012 - die Übung
7. Linksammlung zu KV-Diagrammen history menue scroll up
Das Verfahren an sich ist noch nicht all zu alt, hataber an allen einschlägigen Studiengängen weltweit Eingang gefunden, welche sich nur annähernd damit befassen. Das sind schon einmal alle ingeieurwissenschaftlichen Disziplinen - komischerweise jedoch nicht Mathematik und auch nicht Kerninformatik.
http://www.vias.org/mikroelektronik/dig_karnaughveitch.html
 

zur Hauptseite		 © Samuel-von-Pufendorf-Gymnasium Flöha © Frank Rost am 20. Dezember 2019 um 15.51 Uhr

... dieser Text wurde nach den Regeln irgendeiner Rechtschreibreform verfasst - ich hab' irgendwann einmal beschlossen, an diesem Zirkus nicht mehr teilzunehemn ;-)

„Dieses Land braucht eine Steuerreform, dieses Land braucht eine Rentenreform - wir schreiben Schiffahrt mit drei „f“!“

Diddi Hallervorden, dt. Komiker und Kabarettist

Diese Seite wurde ohne Zusatz irgendwelcher Konversationsstoffe erstellt ;-)