Χάρτης Karnaugh — Οδηγός απλοποίησης K-Map

Ένας χάρτης Karnaugh, ή K-map, είναι ένα πλέγμα που χρησιμοποιείται για την απλοποίηση μιας λογικής έκφρασης Boolean χωρίς να χρειάζεται τόση άλγεβρα με το χέρι. Τοποθετείς τις τιμές εξόδου από έναν πίνακα αληθείας στο πλέγμα, ομαδοποιείς γειτονικά $1$ και μετά γράφεις έναν απλούστερο όρο για κάθε ομάδα.

Η προϋπόθεση έχει σημασία: τα K-map είναι πιο πρακτικά για μικρές συναρτήσεις, συνήθως με δύο, τρεις ή τέσσερις μεταβλητές. Καθώς αυξάνεται ο αριθμός των μεταβλητών, ο χάρτης γίνεται πιο δύσκολος στην ανάγνωση και συνήθως άλλες μέθοδοι είναι καλύτερες.

Τι δείχνει ένας χάρτης Karnaugh

Ένα K-map περιέχει τις ίδιες πληροφορίες με έναν πίνακα αληθείας, αλλά διατάσσει τα κελιά σε σειρά Gray-code αντί για τη συνηθισμένη δυαδική σειρά. Αυτή η διάταξη κάνει τα γειτονικά κελιά να διαφέρουν ακριβώς σε μία μεταβλητή.

Αυτή η διαφορά μίας μεταβλητής είναι όλο το νόημα. Αν δύο γειτονικά κελιά είναι και τα δύο $1$, η μεταβλητή που αλλάζει μπορεί να απαλειφθεί από τον απλοποιημένο όρο.

Πώς η ομαδοποίηση αφαιρεί μεταβλητές

Ο οπτικός κανόνας προκύπτει από ταυτοτικές σχέσεις της άλγεβρας Boolean όπως

$$XY + X\overline{Y} = X$$

Οι δύο όροι διαφέρουν μόνο στο $Y$, άρα το $Y$ απαλείφεται και παραμένει το κοινό μέρος $X$. Ένα K-map σου επιτρέπει να εντοπίζεις αυτό το μοτίβο απάλειψης απευθείας πάνω στο πλέγμα.

Παράδειγμα χάρτη Karnaugh

Έστω

$$F(A,B,C) = \sum m(1,3,4,5,7)$$

Αυτό σημαίνει ότι $F=1$ για τους ελαχόρους $1$, $3$, $4$, $5$ και $7$.

Για ένα K-map $3$ μεταβλητών, χρησιμοποίησε το $A$ για τις γραμμές και το $BC$ για τις στήλες σε σειρά Gray-code $00$, $01$, $11$, $10$:

$$\begin{array}{c|cccc} A \backslash BC & 00 & 01 & 11 & 10 \\ \hline 0 & 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 \end{array}$$

Ξεκίνα με τη μεγαλύτερη έγκυρη ομάδα. Τα τέσσερα $1$ στις δύο μεσαίες στήλες σχηματίζουν μία ομάδα. Σε αυτά τα τέσσερα κελιά, το $C=1$ παραμένει σταθερό ενώ τα $A$ και $B$ αλλάζουν, οπότε αυτή η ομάδα απλοποιείται σε

$$C$$

Ένα $1$ παραμένει ακόμη ακάλυπτο: ο ελαχόρος $4$, που είναι $(A,B,C)=(1,0,0)$. Ταίριαξέ τον με τον γειτονικό ελαχόρο $5$, που είναι $(1,0,1)$.

Σε αυτό το ζεύγος, το $A=1$ και το $B=0$ παραμένουν σταθερά ενώ το $C$ αλλάζει, οπότε το ζεύγος απλοποιείται σε

$$A\overline{B}$$

Άρα η απλοποιημένη έκφραση είναι

$$F(A,B,C) = C + A\overline{B}$$

Αυτή η συντομότερη έκφραση είναι ισοδύναμη με την αρχική λίστα ελαχορών.

Κανόνες για έγκυρες ομάδες σε K-map

Χρησιμοποίησε ομάδες των οποίων τα μεγέθη είναι δυνάμεις του δύο: $1$, $2$, $4$, $8$ και ούτω καθεξής.

Χρησιμοποίησε τις μεγαλύτερες έγκυρες ομάδες που μπορείς. Οι μεγαλύτερες ομάδες συνήθως αφαιρούν περισσότερες μεταβλητές.

Να θυμάσαι ότι ο χάρτης «τυλίγεται». Το αριστερό και το δεξί άκρο είναι γειτονικά, και το πάνω και το κάτω άκρο είναι επίσης γειτονικά.

Τα διαγώνια κελιά δεν είναι γειτονικά.

Η επικάλυψη επιτρέπεται όταν βοηθά να δημιουργηθεί μια μεγαλύτερη ή απλούστερη ομαδοποίηση.

Συνηθισμένα λάθη στους χάρτες Karnaugh

Χρήση της συνηθισμένης δυαδικής σειράς

Αν σημειώσεις τις γραμμές ή τις στήλες ως $00$, $01$, $10$, $11$, η γειτνίαση είναι λανθασμένη. Τα K-map πρέπει να χρησιμοποιούν σειρά Gray-code ώστε τα γειτονικά κελιά να διαφέρουν μόνο κατά ένα bit.

Δημιουργία ομάδων των τριών

Μια ομάδα τριών κελιών δεν είναι ποτέ έγκυρη. Το μέγεθος πρέπει να είναι δύναμη του δύο.

Παράλειψη της γειτνίασης με αναδίπλωση

Μερικές από τις καλύτερες απλοποιήσεις χρησιμοποιούν κελιά που βρίσκονται σε απέναντι άκρα του χάρτη. Αν ξεχάσεις τον κανόνα της αναδίπλωσης, η απάντησή σου συχνά θα είναι πιο μεγάλη απ’ όσο χρειάζεται.

Να βάζεις κάθε $1$ σε ακριβώς μία ομάδα

Αυτό δεν είναι κανόνας. Η επαναχρησιμοποίηση ενός κελιού μπορεί να είναι ο καλύτερος τρόπος για να δημιουργηθεί μια μεγαλύτερη ομάδα και μια συντομότερη τελική έκφραση.

Πότε χρησιμοποιείται ένας χάρτης Karnaugh

Τα K-map είναι συνηθισμένα στην ψηφιακή λογική και στα εισαγωγικά μαθήματα μηχανικής υπολογιστών, επειδή μετατρέπουν την απλοποίηση Boolean σε οπτική διαδικασία. Είναι ιδιαίτερα χρήσιμα όταν θέλεις μια απλούστερη έκφραση sum-of-products πριν σχεδιάσεις ή υλοποιήσεις ένα λογικό κύκλωμα.

Είναι επίσης καλά για την κατανόηση της διαίσθησης πίσω από τη μέθοδο. Ακόμη κι αν το λογισμικό χειρίζεται μεγαλύτερα σχέδια, η εκμάθηση των K-map κάνει πιο εύκολο να δεις γιατί ορισμένοι όροι Boolean συνδυάζονται και άλλοι όχι.

Δοκίμασε ένα παρόμοιο πρόβλημα

Δοκίμασε να απλοποιήσεις μόνος σου το $F(A,B,C)=\sum m(0,2,4,6,7)$. Σχεδίασε τον χάρτη, φτιάξε πρώτα τις μεγαλύτερες έγκυρες ομάδες και μετά κράτησε μόνο τις μεταβλητές που παραμένουν σταθερές σε κάθε ομάδα.

Αν θέλεις να πας ένα βήμα παραπέρα, δοκίμασε μια εκδοχή με τιμές don't-care και χρησιμοποίησέ τες μόνο όταν σε βοηθούν να σχηματίσεις μια μεγαλύτερη έγκυρη ομάδα.