Dijital Tasarım · Karnaugh Haritalarıyla Boolean Sadeleştirme

#06 Gray-code komşuluğu, kenardan sarma ve ikinin kuvveti hücre grupları

Truth table satırlarını Gray-code düzenli Karnaugh haritasına taşı; kenar komşuluğunu ve en büyük ikinin kuvveti gruplarını kullanarak sekiz mintermi tek literale indir.

Soru

Dört değişkenli Karnaugh haritasında üst ve alt satırları kenardan birleştiren sekiz hücreli grubun F eşittir B değil sonucunu verdiğini gösteren görsel. — Üst `AB=00` ve alt `AB=10` satırları sarma komşusudur; sekiz hücre boyunca yalnız B sabit sıfır kaldığı için `F=¬B`.

Dört değişkenli Karnaugh haritasının truth table satırlarını neden Gray-code sırasıyla yerleştirdiğini açıklayın. SOP için geçerli grup boyutlarını, kenar komşuluğunu ve gruptan terim okuma kuralını yazın. F=Σm(0,1,2,3,8,9,10,11) fonksiyonunu haritada sekizli bir sarma grubuyla sadeleştirip sonucun ¬B olduğunu hücre, değişken ve truth table mantığıyla doğrulayın.

Yazılı çözüm ve anlatım dökümü(çözümün tamamını gösterir)

Aşağıda defterde yazılan bütün satırlar ve bunlara eşlik eden sesli anlatımın tam metni bulunur.

1. Truth table satırlarını K-map hücrelerine taşı
K-map yeni bir tablo değildir; `2⁴=16` truth table satırını komşulukları görünür kılan bir geometriye yeniden dizer.
4 giriş → 2⁴=16 minterm ve 16 K-map hücresi
Her hücre tam bir ABCD giriş satırıdır
Hücre değeri o satırdaki F çıkışıdır
Satır ekseni: AB
Sütun ekseni: CD
K-map truth table davranışını değiştirmez
Yalnız satırların geometrik yerleşimini değiştirir
Amaç: tek bit farklı mintermleri yan yana getirmek
Sesli anlatım metni
Karnaugh map hâlâ bir truth table'dır. Yalnızca satırları bir grid üzerinde yeniden düzenler; böylece işe yarayan komşular yan yana gelir. Her hücre tam bir minterm'i, yani tek bir input kombinasyonunu ve o kombinasyonun output değerini temsil eder. Dört değişkenli bir haritada satırları A ve B, sütunları C ve D adlandırır. K-map yeni bir Boolean kuralı değildir. Birleşebilen terimleri görmemizi sağlayan daha iyi bir geometridir.
2. Gray-code sırasıyla tek bitlik komşuluğu kur
Ardışık Gray etiketleri bir bit farklıdır; böylece iki komşu hücre gruplanınca yalnız değişen literal elenir.
Gray sırası: 00 → 01 → 11 → 10
00↔01: yalnız düşük bit değişir
01↔11: yalnız yüksek bit değişir
11↔10: yalnız düşük bit değişir
10↔00: kenardan sarar; yalnız yüksek bit değişir
Normal 00,01,10,11 sırası uygun değildir
Çünkü 01↔10 geçişinde iki bit değişir
Komşu hücrelerde değişen tek değişken terimden çıkar
Diyagonal hücreler komşu değildir
Sesli anlatım metni
Her eksendeki sıra bu yöntemin kilit noktasıdır. Sıfır sıfır, sıfır bir, bir bir, bir sıfır yazarız. Buna Gray-code sırası denir. Bir hücre sola, sağa, yukarı veya aşağı taşındığımızda yalnızca bir input biti değişir. Normal binary sıra, iki bit birden değiştiği hâlde sıfır bir ile bir sıfırı yan yana getirirdi. Gray sırası bu hatayı önler. Komşu iki bir hücresi yalnızca tek bir değişkende farklıysa, o değişken sadeleştirilmiş terimden çıkar.
3. SOP için en büyük geçerli ikinin kuvveti gruplarını seç
Gruplar dikdörtgen, yalnız 1 hücrelerinden ve ikinin kuvveti boyutunda olmalı; karşı kenarlar birbirine komşudur.
SOP hedefi: bütün F=1 hücrelerini kapsa
Geçerli boyutlar: 1, 2, 4, 8, 16
Her boyut 2ᵏ biçimindedir
Grup dikdörtgen olmalı
Grubun içinde 0 hücresi bulunamaz
Önce mümkün olan en büyük grubu seç
Yararlıysa bir hücre birden çok gruba girebilir
İlk↔son sütun ve ilk↔son satır komşudur
Köşeler de dört hücreli sarma grubu oluşturabilir
Sesli anlatım metni
Sum of products için output'u bir olan hücreleri grupla. Her grup bir power of two büyüklüğünde olmalıdır: bir, iki, dört, sekiz veya on altı hücre. Grup harita üzerinde dikdörtgen olmalı ve mümkün olan en büyük bir hücre grubunu kapsamalıdır. Daha büyük veya daha sade bir sonuç üretiyorsa aynı hücre birden fazla gruba girebilir. İlk bakışta şaşırtan kural şudur: harita kenarlardan sarılır. İlk ve son sütunlar, ayrıca ilk ve son satırlar birbirine komşudur.
4. Sekiz mintermi tek sarma grubunda birleştir
Gray düzenindeki üst ve alt satırlar fiziksel olarak uzakta görünse de harita kenarından komşudur.
$\displaystyle F=Σm\left(0,1,2,3,8,9,10,11\right)$
Sütun Gray sırası: CD=00,01,11,10
AB=00 satırı: m₀,m₁,m₃,m₂ → hepsi 1
AB=10 satırı: m₈,m₉,m₁₁,m₁₀ → hepsi 1
Üst ve alt satırlar kenardan komşudur
İki tam satır → tek 8 hücreli dikdörtgen
8=2³ → üç değişken elenebilir
Bütün sekiz 1 hücresi eksiksiz kapsandı
Ek küçük gruplar gereksizdir
En büyük grup en az literal hedefini destekler
Sesli anlatım metni
Şimdi tam bir örneği sadeleştirelim. Fonksiyonun sıfır, bir, iki, üç, sekiz, dokuz, on ve on bir numaralı minterm'lerde bir olduğunu düşün. Bu sekiz tane biri dört değişkenli haritaya yerleştir. A B'nin sıfır sıfır olduğu üst satırı ve A B'nin bir sıfır olduğu alt satırı tamamen doldururlar. Bu satırlar kâğıt üzerinde ayrı görünür; fakat K-map onları üst ve alt kenar üzerinden birleştirir. Birlikte sekiz hücreli tek bir sarma grubu oluştururlar.
5. Sekizli grupta sabit kalan literali oku
Grupta değişen değişkenler elenir; sabit sıfır kalan B, tümleyen literal `¬B` olarak yazılır.
Grup okuma: yalnız sabit kalan değişkenleri tut
A: üst satırda 0, alt satırda 1 → elenir
C: dört sütunda 0 ve 1 → elenir
D: dört sütunda 0 ve 1 → elenir
B: AB=00 ve AB=10 için daima 0
Sabit 0 değişken → tümleyen literal ¬B
Sonuç:
$\displaystyle F=¬B$
Truth table sağlaması: B=0 olan 8 satırda F=1
B=1 olan diğer 8 satırda F=0
Sesli anlatım metni
Şimdi tek tek hücreleri değil, grubun tamamını oku. Sekiz hücre boyunca A sıfırdan bire değişir; bu yüzden A kaybolur. C ve D de mümkün olan tüm değerleri alır ve onlar da kaybolur. Yalnızca B sabit kalır ve değeri daima sıfırdır. Sıfır kalan değişken complement olarak yazılır; dolayısıyla sekiz hücreli grubun tamamı B prime olur. Sonuç budur: sekiz canonical minterm tek bir literal'e indirgenmiştir.
6. Karnaugh haritası sadeleştirme akışını toparla
Birleri yerleştir, en büyük geçerli grupları oluştur ve her grupta yalnız sabit kalan literalleri yaz.
1) Truth table birlerini Gray-code haritasına yerleştir
2) En büyük geçerli 2ᵏ gruplarını oluştur
3) Her grupta yalnız sabit değişkenleri tut
Kenar sarma ve yararlı çakışmayı unutma
Değişen değişken elenir
Sabit 1 → değişken; sabit 0 → tümleyen
Bu örnek: 8 minterm → tek literal ¬B
Sonraki ders: universal NAND ve NOR gerçekleştirmeleri
Sesli anlatım metni
K-map çalışma akışı şöyledir. Truth table'daki birleri Gray-code sırasına yerleştir. Harita kenardan sarılıyorsa bunu da kullanarak mümkün olan en büyük power of two gruplarını oluştur. Sonra her grupta yalnızca sabit kalan değişkenleri tut. Karnaugh haritaları Boolean sadeleştirmeyi görsel ve kontrol edilebilir bir sürece dönüştürür. Sonraki derste NAND ve NOR kapılarıyla, yalnızca tek bir universal gate ailesi kullanarak herhangi bir Boolean fonksiyonu kuracağız.