Ελαχιστοποίηση λογικών εκφράσεων – συναρτήσεων με χρήση πινάκων Karnaugh και με χρήση της μεθόδου Quine-McCluskey

Abstract

Τα ολοκληρωμένα κυκλώματα που χρησιμοποιούνται στις σύγχρονες διατάξεις και συσκευές βασίζονται στη σωστή σχεδίαση και οργάνωση των λογικών στοιχείων που περιλαμβάνουν. Βασικό ρόλο σ’ αυτό παίζει η διαδικασία «απλοποίησης» της λογικής έκφρασης, ώστε να ελαχιστοποιηθεί ο αριθμός των απαιτούμενων λογικών στοιχείων, ώστε να περιοριστεί τόσο το μέγεθος όσο και το κόστος του τελικού προϊόντος. Υπάρχουν δύο βασικές μέθοδοι/αλγόριθμοι που συνήθως χρησιμοποιούνται για την υλοποίηση της διαδικασίας απλοποίησης: Οι πίνακες Karnaugh (διαγράμματα Veitch) και η μέθοδος Quine-McCluskey. Η πρώτη μέθοδος είναι σχετικά απλή και βασίζεται στην παρατηρητικότητα, ωστόσο είναι δύσκολα κατανοητή όταν αναφέρεται σε 5 ή περισσότερες μεταβλητές εισόδου, ενώ είναι σχετικά δύσκολη η κατασκευή προγραμμάτων για την υλοποίησή της. Η μέθοδος Quine-McCluskey απ’ την άλλη είναι πιο περίπλοκη αλλά υλοποιείται εύκολα σε πρόγραμμα. Στον πίνακα Karnaugh μεταφέρονται οι όροι απ’ τον αντίστοιχο πίνακα αλήθειας και κατατάσσονται σύμφωνα με τον κώδικα Gray, ώστε να αλλάζει η τιμή μίας μόνο μεταβλητής σε κάθε γειτονική θέση του πίνακα. Οι τιμές του πίνακα ομαδοποιούνται σε ομάδες κελιών πλήθους 2n (n=0,1,2,3,..) και παράγεται η έκφραση με τους ελάχιστους όρους σύμφωνα με τους κανόνες της άλγεβρας Boole. Η μέθοδος Quine-McCluskey βασίζεται στην καταγραφή των primeimplicants μιας λογικής συνάρτησης, δηλαδή των όρων που «καλύπτουν» (δίνουν το ίδιο αποτέλεσμα) με την λογική συνάρτηση. Στη συνέχεια οι όροι αυτοί συνδυάζονται με βάση την απαίτηση σε κάθε ομάδα να αλλάζει η τιμή μιας μόνο μεταβλητής, η οποία «διαγράφεται» απ’ τον εκάστοτε όρο. Η διαδικασία συνεχίζεται μέχρι να μην μπορούν πλέον να συνδυαστούν οι όροι μεταξύ τους, οπότε προκύπτει η απλοποιημένη έκφραση.