Boolean sadeleştirici: Karnaugh haritası, minimum SOP ve POS

Sonucu nasıl okursunuz

Karnaugh (Karno) haritasının her hücresi doğruluk tablosunun bir satırıdır; hücrenin düğmesi hangisi olduğunu söyler: değerini, satır numarasını ve her değişkenin değerini. Satırlar ve sütunlar Gray kodu sırasındadır, 00, 01, 11, 10; bu yüzden yan yana iki hücre tam olarak bir değişkende ayrılır. Bir satırın ya da sütunun ilk ve son hücresi de öyledir: harita kenarlarından döner. Beş değişken, ilk değişkenin her değeri için bir tane olmak üzere iki harita kaplar; altı değişken dört harita.

Bir grup, ekrandaki örtünün bir terimidir: 1, 2, 4 ya da daha çok hücreden oluşan, mürekkeple çizilmiş, kendine özgü bir çizgi deseni ve numarası olan bir dikdörtgen. Bir kenardan dönen grup açık parçalara bölünür. Haritanın altındaki gösterge, grupları biçimin terimleri yazdığı sırayla, her birini numarası ve terimiyle listeler. Bir gösterge düğmesinin üzerine gelince grubu yanar; düğmeye basarsanız grup yanık kalır. Harita aynı zamanda bir girdidir: bir hücreye tıklayın ya da üzerindeyken 0, 1 veya - tuşuna basın; ekrandaki fonksiyon haritanınki olur.

İki minimum biçim de yazılır. Sum of products (çarpımların toplamı, SOP) VE terimlerinin VEYA'sıdır; product of sums (toplamların çarpımı, POS) VEYA terimlerinin VE'sidir. Her biri, alana geri yapıştırabileceğiniz SystemVerilog olarak yazılır; altında da ders kitabı gösterimiyle, tümlenen adın üstünde bir çizgi ve VEYA için + ile. Bir fonksiyonun aynı maliyette birden çok minimum örtüsü olabilir. "1 / 2" bunu söyler; “Önceki” ve “Sonraki” örtüler arasında gezer. “Harita, kod ve devrede” seçimi, haritadaki grupların, kodun ve devrenin hangi biçimi izleyeceğini belirler.

Kod tek bir assign'dır, her satırda bir terim; devrenin her birinci düzey kapısı kendi satırını yakar. “Çalıştır”a basın: girişler doğruluk tablosunu Gray kodu sırasıyla gezer, her adımda bir giriş değişir ve çıkış, tablonun belirlediği her satırda tabloya göre denetlenir; beş ve altı değişkende her senaryo bir haritayı gezer. Yazdığınız bir SOP ya da POS, zaten minimum değilse, minimumuyla birlikte tek bir dalga biçimi üzerinde çizilir; iki çıkışın her satırda aynı olduğunu izleyebilirsiniz.

Yöntem

Araç prime implicant'ları (asal implikantları) Quine–McCluskey yöntemiyle bulur: bir değişkende ayrılan satırları birleşemeyecek hâle gelene kadar daha büyük gruplarda birleştirir; geriye kalan gruplar asal implikantlardır. Don't care (fark etmez) satırları grup kurmaya yardım eder ama örtülmeleri gerekmez. Her 1'i örten en az sayıda asal implikantı seçmek bir örtme problemidir; araç bunu dal ve sınır (branch and bound) yöntemiyle tam olarak çözer: önce en az terim, sonra en az literal. Sonuçları, dört değişkene kadar her fonksiyonda, beş değişkenli 20.000 ve altı değişkenli 2.000 rastgele fonksiyonda, her örnekte fark etmez satırlarıyla bir kez daha, bağımsız bir referansla karşılaştırıldı.

Minimum POS, aynı fark etmez satırlarıyla tümleyenin minimum SOP'sidir ve De Morgan kuralıyla geri okunur; bu yüzden grupları 0'ların gruplarıdır. Birden çok minimum örtüden ilki, ötekinde olmayan en erken grubu tutan örtüdür; iki gruptan daha erken olanı da ötekinde olmayan, doğruluk tablosunun en erken satırını tutandır.

Minimum her zaman istediğiniz devre değildir

Varsayılan ifade, a & b | ~b & c | a & c, static-1 hazard başvuru sayfasının (İngilizce) örtülmüş biçimidir. Minimumu a & c terimini atar, çünkü öteki iki terim onun örttüğü her satırı zaten örter. Kapı gecikmeleri olan bir devrede bu terim önemlidir: a ve c 1'deyken b düşerse ~b & c, a & b düştükten bir an sonra yükselir ve a & c olmadan çıkış kısa bir süre 0'a iner. Minimum, doğru olan en ucuz ifadedir; hazard'sız bir devre değildir.

Sınırlar

Araç en çok 6 değişken okur; adlar en çok 8 karakterdir: küçük harf, rakam ve _, ilk karakter harf ya da _. Bir SystemVerilog anahtar sözcüğü reddedilir; bir lint aracının reddettiği ad da reddedilir, çünkü kod lint'ten geçmezdi; sözdizimi renklendiricisinin anahtar sözcük gibi boyadığı ad da öyle. İfadeler SystemVerilog'un ~ ! & ^ ~^ | && || işleçlerini ve parantezleri, onun öncelik sırasıyla kullanır.

Devre, şekle sığdığında çizilir: üç değişkene kadar her minimum, en çok 25 literallik her dört değişkenli minimum, en çok 4 terimli ya da 16 literallik beş değişkenli minimumlar ve en çok 3 terimli ya da 13 literallik altı değişkenli minimumlar; daha büyükleri de sığdıklarında. Bunun ötesinde sayfa devrenin ne kadar büyük olacağını söyler; harita, biçimler ve kod devre olmadan da eksiksizdir. En zor altı değişkenli fonksiyonlar yavaş bir telefonda biraz sürer; araç çalışırken durum satırı bunu söyler. Aracın yazdığı bir biçim, fark etmez satırları için olası seçimlerden yalnızca birini yapar ve minimumun gerek duymadığı değişkeni dışarıda bırakır: fonksiyonun tamamını minterm (minterim) listesi ve harita taşır.