| Karnaugh Haritaları ile Mantık Sadeleştirme |
 |
 |
 |
| Administrator tarafından yazıldı |
| PerÅŸembe, 25 Mart 2010 16:59 |
|
Şimdiye kadar yaptığımız mantık sadeleştirme örnekleri Boole cebri ile aynı hızda yapılabilirdi. Gerçek dünyada mantık sadeleştirme problemleri daha büyük Karnaugh haritaları gerektirir ve çok fazla iş yapmak gerekir. Bu bölümde bazı suni örnekler yapacağız gerçek dünya uygulamalarının çoğunu Tümleşik Mantık bölümüne bırakacağız. Suni örnek ile teknikleri gösteren örnekler kastedilmiştir. Bu yaklaşım bize Tümleşik Mantık bölümünde daha kompleks uygulamalara geçişte gerekli olan donanımı kazandıracaktır. Daha önce geliştirdiğimiz Karnaugh haritasını gösterelim. Sağdaki formu kullanacağız.
Haritanın üstündeki sayıların dizisine dikkat edin. 00, 01, 10, 11 gibi olması gereken ikili sayı dizisi değil. Sayı dizisi 00, 01, 11 10 bu dizi Gray kodu dizisidir. Gray kodu dizisinde ikili sistemin aksine, bir sayıdan diğerine geçerken bir ikili bit değişir. Bunun anlamı komşu hücreler sadece bir bit veya bir Boole değişkeni değiştirir. Bir mantık fonksiyonunun çıkışlarının ortak noktalarını görebileceğimiz şekilde organize etmek için gereken şey budur. Ayrıca, sütun ve satır başlıkları Gray kodu şeklinde olmalıdır aksi halde harita bir Karnaugh haritası olmaz. Ortak Boole değişkenlerini paylaşan hücreler komşu olmaz ve görsel düzen göstermez. Komşu hücreler sadece bir bit değişir çünkü bir Gray kodu dizisi de sadece bir bit değişir. Eğer kendi Karnaugh haritalarımızı çizersek, kullandığımız harita büyüklüğü için Gray kodu üretmemiz gerekir.Bu şekilde her büyüklük için Gray kodu üretiriz.
Yukarı sağdaki Gray kodu dizisi listede yukarıdan aşağıya veya aşağıdan yukarıya gittikçe bir bit değiştiğine dikkat edin. Gray kodunun bu özelliği genelde sayısal elektronikte çok kullanışlıdır. Özellikle Karnaugh haritalarına uygulanabilir. Şimdi 3-değişkenli Karnaugh haritalarının sadeleştirilmesine geçelim. Sadeleştirilmemiş mantığın çarpım terimlerinin K-haritasına nasıl eşleştirildiğine bakalım. Sayısal mantığın çarpımların toplamı sadeleştirmesine götüren komşu hücre gruplarının nasıl tanımlandığına bakalım.
Yukarıda herbir çarpım terimi için 1'leri yerleştiriyoruz, ikili bir grubu belirliyoruz, sonra sadeleştirilmiş sonuç olarak grubun tamamı için tek bir çarpım terimi yazıyoruz.
Yukarıda dört çarpım terimini eşleştirmek, A' Boole terimi ile kapsanan dörtlü bir grup oluşturur.
Dört çarpım terimini eşleştirmek, bir değişkenli C tarafından kapsanan dörtlü bir grup oluşturur.
Yukarıda altı çarpım terimini eşleştirdikten sonra, yukarıdaki dörtlü grubu tanımlayın, alttaki iki hücreyi dörtlü bir grup gibi iki hücreyi diğer bir grupla paylaşarak seçin. Bu ikisini dörtlü bir grupla kapsamak daha kolay sonuç verir. İki grup olduğu için,A'+B çarpımların toplamı sonucunda iki çarpım terimi olacaktır.
Yukarıdaki iki çarpım terimi ikili bir grup oluşturur ve BC ye sadeleşir.
Dört çarpım terimini eşleştirmek dörtlü bir grup oluşturur ve bu grup B dir.
Yukarıda dört çarpım terimini eşleştirmek dörtlü bir grup oluşturur. Dörtlü grubu, haritanın uçlarını bir silindir oluşturacak şekilde yuvarlayarak ve sonuçta hücreleri komşu yaparak görebiliriz. Normalde dörtlü grubu yukarıda soldaki gibi belirtiriz. A, B, C değişkenleri dışında ortak bir C' değişkeni de vardır. C' bütün dört hücre için 0 dır. Nihai sonuç C' dür.
Yukarıda, sadeleştirilmemiş denklemin altı hücresi dörtlü iki grup halinde düzenlenebilir. Bu iki grup bize A' + C' nün sadeleştirilmiş sonucunda iki çarpım terimi vermelidir. Aşağıda, Boole cebri bölümünden Zehirli Atık Yakma Fırınını tekrar görüyoruz. Bu örneğin detayları için Boole cebri bölümüne bakınız. Mantığı bir Karnaugh haritası kullanarak sadeleştireceğiz.
Çıktı olan Boolean denklemi dört çarpım terimine sahiptir. Dört 1'i karşılık gelen çarpım terimleri ile eşleştirin. Hücre gruplarını oluşturarak, ikili üç grup elde ederiz. Her bir grup için bir adet çarpım terimi olmak üzere sadeleştirilmiş sonuçta toplam üç çarpım terimi olacaktır. Aşağıda gösterilen sonucun kapı diyagramı için, Boole cebri bölümünden "Zehirli Atık Yakma Fırını" konusuna bakınız.
Aşağıda, karşılaştırma yapmak için Zehirli Atık Yakma Fırınının Boole cebri ile sadeleştirilmesini tekrar ediyoruz.
Aşağıda, yukarıdaki Boole cebri ile yapılan sadeleştirme ile karşılaştırma yapmak için Zehirli Atık Yakma Fırınının Karnaugh haritası çözümünü tekrar ediyoruz. Bu durum Karnaugh haritasının mantık sadeleştirme için neden çokça kullanıldığını gösteriyor.
Karnaugh haritası metodu, önceki sayfadaki Boole cebrinden daha kolay gözükmektedir. 4 Değişkenli Büyük Karnaugh Eşlemleri Gray kosunun nasıl oluşturulacağını bilmek daha büyük haritalar yapmamızı sağlar. Gerçekten yapmamız gereken şey, 3-değişkenli haritanın tepesindeki soldan sağa diziye bakmak ve bunu 4-değişkenli haritanın sol köşesinden aşağıya doğru kopyalamaktır. Aşağıya bakınız.
Sıradaki dört değişkenli Karnaugh haritaları, Boole ifadelerinin Boole cebri ile sadeleştirilmesinin ne denli yorucu olduğunu gösterir. Sadeleştirmeler Boole cebri ile yapılabilir fakat özellikle sadeleştirilmesi gereken fazla sayıda mantık varsa, Karnaugh haritası daha hızlı ve kolaydır.
Yukarıdaki Boole ifadesi yedi çarpım terimi içermektedir. Yukarıdaki K-haritasına yukarıdan aşağıya ve soldan sağa yerleştirilmişlerdir. Örnek olarak ilk çarpım terimi A'B'CD ilk satır üçüncü hücredir, haritada karşılık gelen yerleşimi A=0, B=0, C=1, D=1 olur. Dİğer çarpım terimleri aynı şekilde yerleştirilir. Mümkün olan en büyük grupları kapsayacak şekilde yukarıda dörtlü iki grup gösterilmiştir. Yatayda kesikli çizgi ile belirtilen grup sadeleştirilmiş AB terimine karşılık gelir. Dikey grup CD Boole ifadesine karşılık gelir. İki grup olduğu için, Out=AB+CD işeminin çarpımlar toplamında iki çarpım terimi olacaktır. Dört hücreyi fiziksel olarak komşu yapmak için haritanın köşelerini bir peçete gibi katlayın.
Yukarıdaki dört hücre dörtlü bir gruptur çünkü B' ve D' Boole değişkenleri hepsi için ortaktır. Diğer bir deyişle, dört hücre için B=0 ve D=0 dır. Hücrelerin dört köşesine kıyasla diğer değişkenler (A, B) bazı durumlarda 0 olur, diğer durumlarda 1 olur. Sonuçta (A, B) değişkenleri bu dörtlü grupta yer almaz. Bu tek grup Out=B'C' sadeleştirilmiş sonucu için bir çarpım terimi olarak haritadan çıkar. Aşağıdaki K-haritası için üstteki ve alttaki köşeleri bir silindir oluşturacak şekilde katlayın ve sekiz komşu hücre oluşturun.
B=0 Boole değişkeni yukarıdaki sekizli grup için ortaktır. Bu nedenle, bu sekizli grup bir çarpım terimi olan B' tarafından kapsanır. Orijinal sekiz terimli Boole ifadesi Out=B' ne sadeleşir. Aşağıdaki Boole ifadesi dokuz çarpım terimi içerir, bunlardan üç tanesi dört tane Boole yerine üç tane Boole ye sahiptir. Aradaki fark şudur, dörtlü Boole değişkenine sahip çarpım terimleri bir hücre kapsarken üç Boole ye sahip çarpım terimlerinin her biri bir çift hücre kapsar.
Yukarıda dört Boole değişkenine sahip altı adet çarpım terimi normal olarak tek hücre şeklinde eşleştirilir. Üç Boole değişkenine sahip terimler (her biri üç adet) aşağıda gösterildiği gibi hücre çiftleri şeklinde eşleşir. Çarpım terimlerini K-haritasına eşleştirdiğimize, bu noktada dışarı çıkartmadığımıza dikkat edin. Sadeleştirme için sekizli iki grup oluşturuyoruz. Köşelerdeki hücreler her iki grup tarafından paylaşılır. Bu iyidir. Aslında, bu sekizli bir grup ve hiç bir hücre paylaşmayan dörtlü bir grup oluşturmaktan daha iyi bir çözümdür. Nihai çözüm Out=B'+D' dur. Aşağıda sadeleştirilmemiş Boole ifadesini Karnaugh haritasına eşleştiriyoruz.
Yukarıdaki hücrelerin üçü iki hücreli gruplar oluşturur. "gerçek hayattaki" problemlerde sıkça rastlandığı gibi dördüncü hücre hiç bir şeyle birleştirilemez. Bu durumda, sadeleştirme işleminde ABCD Boole çarpım terimi değişmez. Sonuç: Out= B'C'D'+A'B'D+ABCD Çoğu zaman bir sadeleştirme probleminin birden fazla en düşük maliyet çözümü vardır. Böyle bir durum aşağıda gösterilmiştir.
Yukarıdaki her iki çözüm her bir üç Boole değişkeni içeren dört çarpım terimine sahiptir. Her ikisi de geçerli en az maliyet çözümleridir. Nihai çözümdeki farklılık yukarıda gösterildiği gibi hücrelerin nasıl gruplandırıldığından kaynaklanmaktadır. Bir en az maliyet çözümü en az sayıda girdisi olan en az sayıdaki geçide sahip geçerli bir mantık tasarımıdır. Aşağıda sadeleştirilmemiş Boole denklemini normal şekilde eşleştiriyoruz ve ilk adım olarak dörtlü bir grup oluşturuyoruz. Geri kalan hücrelerin seçimi çok açık olmayabilir.
Yukarıda ortada bulunan dörtlü bir grup içinden üç tane daha hücre seçin. Geride hala iki hücre kalıyor. Bunları seçmenin en düşük maliyetli çözüm metodu yukarıda sağda gösterildiği gibi bunları dörtlü gruplar halindeki komşu hücrelerle gruplandırmaktır. Dikkat edilmesi gereken bir nokta üçlü gruplar oluşturmamaktır. Gruplandırma 2 nin üssü şeklinde olmalıdır, yani 1, 2, 4, 8 ... Aşağıda en az maliyetli çözümün iki olası örneği gösterilmiştir. Hücreleri eşleştirdikten sonra dörtlü grupların çiftleştirilmesiyle başlayın.
İki çözüm geri kalan tek hücrenin birinci veya ikinci dörtlü gruptan hangisiyle gruplandırılacağına ve iki hücreli bir grup oluşturacağına bağlıdır. O hücre sizin seçiminize bağlı olarak ABC' veya ABD olarak alınabilir. Her iki yolda bu hücre her iki Boole çarpan terimi tarafından kapsanır. Nihai sonuçlar yukarıda gösterilmiştir. Aşağıda solda Karnaugh haritası ile sadeleştirilen sağda ise Boole cebri ile sadeleştirilen bir örnek vardır. Harita üzerinde C' nü, C=0 adresinin kapsadığı soldaki 8-hücrenin alanı olarak çiziniz. Ardından tek ABCD hücresini çiziniz. Bu tek hücre gösterildiği gibi 2-hücreli bir grup oluşturur, bu da ABD çarpım terimine indirgenir. Sonuç olarak da Çıkış = C' + ABD elde edilir.
Yukarıdaki bu örnek, teoremleri hatırlarsanız Boole cebri ile çok zorlanmadan sadeleştirebileceğimiz nadir bir örnektir. Minterm'e Karşı Maxterm Çözümü Şimdiye kadar mantık sadeleştirme problemlerine Çarpımlar-ın-Toplamı (SOP) çözümlerini bulduk. Her bir SOP çözümü için aynı zamanda Toplamlar-ın-Çarpımı (POS) çözümü de vardır, uygulamaya bağlı olarak bu daha kullanışlı olabilir. Toplamlar-ın-Çarpımı çözümüyle uğraşmadan önce yeni bir terminolojiye ihtiyacımız vardır. Çarpım terimlerini eşleştiren aşağıdaki prosedür bu bölümde yeni değildir. Mintermler için uygun bir prosedür geliştirmek istiyoruz bunu da maxtermler için olan yeni bir prosedürle kıyaslamak istiyoruz.
Bir minterm bir Karnaugh haritasında veya doğruluk tablosunda tek hücre çıktısı için 1 veren ve diğer bütün hücreler için 0 veren bir Boole ifadesidir. Eğer bir minterm tek bir 1 ve geri kalan hücreler için 0 ise 1 için minimum alan kaplar. Yukarı soldaki çizim mintörm ABC yi tek bir çarpan terimi olarak göstermektedir, bu çarpan teriminde bir tane 1 vardır diğer bütün durumlar 0 dır. Şimdiye kadar 0 ları Karnaugh haritasından göstermedik çünkü özellikle ihtiyaç duyulmadığı taktirde bunları elemek tabiidir. Diğer bir minterm A'BC' yukarıda sağda gösterilmiştir. Üzerinde durulması gereken nokta şu ki hücrenin adresi direkt olarak eşleştirilmek istenen minterm e karşılık geldiğidir. Yani yukarıda solda111 hücresi ABC minterm üne karşılık gelir. Yukarıda sağda A'BC' mintermünün 010 hücresine karşılık geldiği görülmektedir. Bir Boole ifadesi veya haritası birden fazla minterm içerebilir, yukarıdaki şekle göre bir K-haritasında bir minterm yerleştirmenin prosedürünü özetleyelim:
Yukarıda gösterildiği gibi genellikle bir Boole ifadesi bir Karnaugh haritasında çoklu hücrelere karşılık gelen birden fazla minterme sahip değildir. Bu haritadaki birden fazla mintermler yukarıda önceki şekilde gördüğümüz bireysel mintermlerdir. Referans olması için incelediğimiz nokta, K-haritasındaki 1 lerin bir veya fazla çarpım terimini dönüştüren ikili hücre adresi olarak ortaya çıkmasıdır. Burada kastettiğimiz 0 tümlenmiş değişkene karşılık kelir 1 ise gerçek bir değişkene karşılık gelir. Örnek: 010 direkt olarak A'BC' ye dönüşür. Bu örnekte hiç sadeleştirme yoktu. Fakat mintermlerden gelen Çarpımlar-ın-Toplamı sonucu vardır. Yukarıdaki şekle göre, bir K-haritasından bir Boole denklemini Çarpımlar-ın-Toplamı olarak sadeleştiren prosedürü özetleyelim:
Şimdiye kadar yeni bir şey yapmadık, mintermlerle uğraşmak için uygun bir prosedür yazdık. Bu maxtermlerle uğraşmak için bir modeldir. Sonra tek bir hücrede 0 diğer bütün hücrelerde 1 olan Boole fonksiyonuna bakalım.
Bir maxterm bir Karnaugh haritasında veya doğruluk tablosunda tek hücre çıktısı için 0 veren ve diğer bütün hücreler için 1 veren bir Boole ifadesidir. Yukarı soldaki şekil tek bir toplam terimi olan maxterm (A+B+C) yi gösterir, haritada tek bir 0 vardır diğer tüm ifadeler 1 dir. Eğer bir maxterm tek bir 0 a sahipse ve geri kalan bütün hücreler 1 ise 1 lerden oluşan maksimum alanı kapsar. Şimdi yeni bir şey olan maxtermlerle uğraştığımız için bazı farklılıklar karşımıza çıkıyor. Bir maxterm bir Karnaugh haritasında bir 0 veya bir 1 değildir. Maxterm bir toplam terimidir, bizim örneğimizde (A+B+C) dir bir çarpım terimi değildir. Ayrıca (A+B+C) nin 000 hücresine karşılık gelmesi ilginçtir. Çıkış=(A+B+C)=0 denklemi için (A, B, C) üç değişkeninin her biri ayrı ayrı 0 olması gerekir. Sadece (0+0+0)=00 a eşit olacaktır. Bu yüzden K-haritasında minterm (A+B+C) için 0 değerini sadece A,B,C=000 hücresine yerleştiririz, burada bütün girdiler0 dır. Bu bize maxterm olarak 0 değerini verecek tek durumdur. Diğer bütün hücrelerde 1 vardır çünkü (A+B+C) (0,0,0) ifadesinden başka bütün girdi değerleri 1 verir. Yukarıdaki şekle göre, bir K-haritasına maxterm yerleştirme prosedürü şöyledir:
Yukarıda başka bir A'+B'+C' maxterm ifadesi gösterilmiştir. Sayısal 000 A'+B'+C' ne karşılık gelir. Tümleyeni 111 olur. Yukarıda gösterildiği gibi K-haritasının (1,1,1) hücresine (A'+B'+C') maxtermü için bir 0 yerleştirin. (A'+B'+C') 111 hücresinde neden 0 değeri verir? A'+B'+C' (1'+1'+1') olduğunda tüm 1 lerin tümleyeni alındıktan sonra (0+0+0) olur ve bize 0 veren tek durum budur. Tüm birler 1 ler 0 lara tümlenir, bunun OR sonucu bize 0 verir.
Yukarıda gösterildiği gibi bir Boole Toplamlar-ın-Çarpımı ifadesi veya haritası birden fazla maxterme sahip olabilir. Maxterm (A+B+C) sayısal olarak 111 verir bu da 000 a tümlenir, sonuçta (0,0,0) hücresine bir 0 yerleştirilir. Maxterm (A+B+C') sayısal oalrak 110 verir bu da 001 e tümlenir, sonuçta (0,0,1) hücresine bir 0 yerleştirilir. Şimdi bir K-haritası düzenine sahip olduğumuza göre gerçekte ilgilendiğimiz şey Toplanlar-ın-Çarpımı indirgemesinin nasıl yazılacağını göstermektir. 0 ları gruplandırın. Altta bu ikili bir grup olacaktır. (0,0,X) olan toplam-terimine karşılık gelen ikili değeri yazın. Grup için hem A hem de B 0 dır. Fakat C hem 0 hem de 1 değerini alır, bunun için C yerine X yazarız. (1,1,X) tümleyenini oluşturun. C yi ve onun yerini tutan X i çıkartarak (A+B) toplam terimini yazın. Genel olarak Toplamlar-ın-Çarpımı sonucunda toplam-terimlerinin birbiriyle çarpımının fazla olmasını bekleyin. Burada basit bir örneğimiz var.
Bir K-haritası için Toplamlar-ın-Çarpımı Boole indirgemesinin prosedürünü özetleyelim:
Örnek: Sonucun POS formda olmasını sağlayarak aşağıdaki Toplamlar-ın-Çarpımı Boole ifadesini sadeleştirin.
Çözüm: Yedi adet maxtermü aşağıdaki haritaya 0 olarak taşıyın. Uygun hücre yerini bulmak için giriş değerlerinin tümleyenini almayı unutmayın.
0 lar ortaya çıktıkça yukarıdaki haritadan soldan sağa ve yukarıdan aşağıya bunları yerleştiririz. Son üç maxtermü çizgilerin yanına yerleştiririz. Yukarıda hücreler yerlerine yerleştirildikten sonra aşağıda gösterildiği gibi hücre grupları oluşturun. Büyük gruplar daha az sayıda girdisi olan toplam terimleri verirler. Daha az sayıda grup daha az toplam-terimi sonucunu verir.
Üç grubumuz var, sonuçta yukarıdaki POS sonucunda üç tane toplam-terimi olmasını bekleriz. 4-hücreli grup 2-değişkenli toplam-terimi verir. 2-hücreli iki grup 3-değişkenli iki toplam-terimi verir. Yukarıda Toplam-terimlerine nasıl ulaştığımızın detayları gösterilmiştir. Bir grup için, ikili grup girdi adresini yazın sonra tümleyenini alın ve böylece Boole toplam-terimine dönüştürün. Nihai sonuç üç toplamın çarpımıdır. Örnek: Sonucun SOP formunda olmasını sağlayarak aşağıdaki Toplamlar-ın-Çarpımı Boole ifadesini sadeleştirin.
Çözüm: Bu önceki problemin tekrarı gibi görünmektedir. Aradaki fark daha önce yaptığımız Toplamlar-ın-Çarpımı yerine Çarpımlar-ın-Toplamının çözümü istenmektedir. Aşağıda solda daha önceki problemde olduğu gibi Toplamlar-ın-Çarpımından 0 ların maxtermlerini yerleştirin.
Yukarıda sağda haritanın geri kalan hücrelerine gerekli 1 leri yerleştirin.
Bütün 1 leri kapsayan 1 ler grubunu oluşturun. Bu bölümün bir önceki konusunda olduğu gibi Çarpımlar-ın-Toplamı sadeleştirmesi sonucunu yazınız. Bu bir önceki probleme benzerdir.
Yukarıda karşılaştırma yapabilmek için daha önceki örneğin Toplamlar-ın-Çarpımı çözümü ve bu problemdeki Çarpımlar-ın-Toplamı çözümü verilmiştir. Hangisi daha kolay bir çözümdür? POS da 3-OR geçidi ve 1-AND geçidi vardır SOP da ise 3-AND geçidi ve 1-OR geçidi vardır. Her biri toplam dört geçitten oluşur. Dikkatli baktığımızda geçit girdilerinin sayısını topladığımızı görürüz. POS da 8-girdi vardır; SOP da ise 7-girdi vardır. En az maliyetli çözümün tanımında SOP çözümünün daha basit olduğu ortaya çıkar. Bu teknik olarak doğru fakat gerçek hayatta az kullanılan bir örnektir. Daha iyi çözüm problemin karmaşıklığına ve kullanılan mantık ailesine bağlıdır. Genelde TTL mantık ailesi için SOP daha iyi bir çözümdür çünkü NAND geçitleri temel yapı taşlarıdır ve bunlar SOP yöntemiyle daha iyi çalışır. Diğer taraftan, çeşitli büyüklükteki NOR geçitleri bulunduğundan CMOS mantık ailesi için POS çözümü kullanılması daha uygundur.
Yukarıda her iki durum içinde geçit diyagramları gösterilmiştir, solda Toplamlar-ın-Çarpımı sağda ise Çarpımlar-ın-Toplamı vardır. Aşağıda solda tekrarlanan örnek mantığımızın Çarpımlar-ın-Toplamı uyarlamasına daha yakından bakalım.
Yukarıda soldaki bütün AND geçitleri sağda NAND geçidi ile yer değiştirmiştir. Çıkıştaki OR geçidi NAND geçidi yer değiştirmiştir. AND-OR mantığının NAND-NAND mantığına eşdeğer olduğunu ispatlamak için, 3-NAND geçidinin çıkışındaki eviricinin evirme balonlarını yukarıda sağdaki şekilden aşağı soldaki şekle geçişteki gibi sondaki NAND nin girişine götürün.
Yukarı sağda evirilmiş girişlere sahip NAND geçidinin çıkışı mantıksal olarak bir OR geçidine eşdeğer olduğu DeMorgan teoremi ve çift tersinme ile görülür. Bu bilgi TTL mantık ailesi NAND geçitlerinin diğer tiplere göre daha rahat bulunabildiği bir laboratuarda sayısal mantık inşa etmede kullanışlıdır. AND-OR mantığı yerine NAND-NAND mantığı oluşturmanın prosedürü şu şekildedir:
Örnek: Şimdi SOP minimizasyonu içeren önceki bir problemi tekrar görelim. Bir Toplamlar-ın-Çarpımı çözümü üretin. POS çözümünü önceki SOP ile karşılaştırın.
Çözüm: Yukarı solda basitleştirilmemiş 9-minterm Boole ifadesi ile başlayan orijinal problemimiz var. Aşağı solda 4-çarpan-terimli SOP sonucu veren 4-hücreli 4-grup oluşturduk. Yukarıda ortadaki şekilde boş yerleri gerekli olan 0 larla doldururuz. 0 4-hücreli iki grup oluşturur. Bütün çizgili kırmızı grup (A'+B) dir, kesikli çizgili kırmızı grup ise (C'+D) dir. Bu Toplamlar-ın-Çarpımı sonucunda iki-toplam terimi verir, yukarı sağdaki gibi Çıkış = (A'+B)(C'+D) Solda bulunan önceki SOP sadeleştirmesini sağdaki POS sadeleştirmesi ile kıyaslarsak POS çözümünün en az maliyetli çözüm olduğunu görürüz. SOP toplamda 5-geçit kullanırken POS sadece 3-geçit kullanır. Sonucun basitliğinden dolayı TTL mantık kullanırken bu POS çözümü daha çekici görünür. AND geçitlerini ve OR geçidini 2-girişli şekilde bulabiliriz.
Karşılaştırma problemimizdeki SOP ve POS geçit diyagramları yukarıda gösterilmiştir. Aşağıda TTL mantık ailesi entegre devre geçitleri için pin-çıkışları verilmiştir, yukarı sağda Devre işaretçileri (U1-a, U1-b, U2-a vs.) ve pin numaralarını kullanarak maxterm terimini etiketleyin.
Kullandığımız her bir entegre devre paketi bir devre işaretçisi alır: U1, U2, U3. Paket içindeki farklı geçitleri ayırmak için a, b, c, d, vs. şeklinde tanımlanırlar. 7404 hex-evirici paketi U1 dir. Onun içindeki her bir evirici U1-a, U1-b, U1-c, vs. dir. U2 7432 dörtlü OR geçidine atanmıştır. U3 7408 dörtlü AND geçidine atanmıştır. Yukarıda paket diyagramı üzerindeki pin numaralarına bakarak aşağıdaki bütün geçit girişlerine ve çıkışlarına pin numarası veririz. Şimdi bu devreyi bir laboratuar düzeninde kurabiliriz. Veya bunun için bir baskılı devre kartı tasarlayabiliriz. Bir baskılı devre kartı yalıtkan fenolik veya epoxy-fiberglass dan oluşan yalıtkan altlık üzerinde "kablolama" vazifesi gören bakır folyodan oluşur. Baskılı devre kartları elektronik devrelerin seri üretiminde kullanılır. Kullanılmayan geçitlerin girişleri topraklanır.
Yukarı solda (üç şekil geri) önceki POS çözüm diyagramını Devre işaretleyicileri ve pin numaraları ile etiketleyin. Bu az önce yaptığımıza benzer olacaktır.
2-girişli AND geçidini bir önceki örnekteki 7408 de bulabiliriz. Bununla birlikte, 4-girişli OR geçidini TTL katalogunda bulmakta problemimiz var. 4-girişli tek geçit yukarı sağda gösterilen 7420 NAND geçididir. 4-girişli NAND geçidini 4-girişli OR geçidine çevirmek için NAND geçidinin girişlerini aşağıda gösterildiği gibi evrilmemiş gerekir. Böylece 7420 4-girişli NAND geçidini girişlerini evirerek bir OR geçidi olarak kullanacağız.
7420 4-girişli NAND geçidinin girişlerini evirmek için ayrı eviriciler kullanmayacağız fakat SOP minterm çözümünde gerekli olan AND geçitleri yerine 2-girişli NAND geçitleri ile besleyeceğiz. 2-girişli NAND geçidinin çıkışındaki evirme 4-girişli OR geçidindeki evirmeyi besler.
Sonuç yukarı da gösterilmiştir. NAND-NAND mantığının yerine AND-OR mantık kullanarak TTL geçitleri yapmanın tek pratik yolu budur. Σ (Toplam) ve Π(Çarpım) Notasyonu Referans olması açısından bu bölüm bir Karnaugh haritasına atanan mintermleri ve maxtermleri tanımlamak için gerekli terminolojiyi ortaya koyar. Bunun dışında burada yeni bir şey yoktur. ? (sigma) toplamı ve küçük harf "m" ise mintermleri ifade eder. ?m mintermlerin toplamını ifade eder. Sıradaki örnek bu noktayı açıklamak için verilmiştir. Sadeleştirilmemiş mantığı tanımlayan Boole denklemi yerine mintermleri listeleriz. f(A,B,C,D) = ? m(1, 2, 3, 4, 5, 7, 8, 9, 11, 12, 13, 15) veya f(A,B,C,D) = ?(m1,m2,m3,m4,m5,m7,m8,m9,m11,m12,m13,m15) Numaralar aşağıda sağda gösterildiği gibi bir Karnaugh haritası içinde hücrelerin yerini veya adresini gösterir. Bu bir K-haritasında mintermlerin veya hücrelerin bir listesini tanımlamanın kısa bir yoludur.
Çarpımlar-ın-Toplamı çözümü bu yeni terminolojiden etkilenmez. Haritadaki mintermler, 1 ler daha önce olduğu gibi gruplandırılmıştır ve Çarpımlar-ın-Toplamı çözümleri yazılmıştır. Aşağıda, maxtermlerden oluşan bir listeyi tanımlamak için gerekli terminolojiyi gösteriyoruz. Çarpım yunanca ? (pi) harfi ile gösterilir ve maxtermler büyük "M" harfi ile gösterilir. ?M maxtermlerin çarpımını gösterir. Aynı örnek bizim metodumuzu gösterir. Sadeleştirilmemiş mantığı tanımlayan Boole denklemi maxtermlerin bir listesiyle yer değiştirilmiştir. f(A,B,C,D) = ? M(2, 6, 8, 9, 10, 11, 14) veya f(A,B,C,D) = ?(M2, M6, M8, M9, M10, M11, M14) Numaralar K-haritasındaki hücrelerin adreslerinin yerlerini belirtir. Aşağıda gösterildiği gibi maxtermler için bu 0 ların olduğu yerdir. Toplamlar-ın-Çarpımı çözümü bilindik şekilde tamamlanmıştır.
Karnaugh Haritasındaki Hücreler İçin Endişelenmemek Şimdiye kadar giriş şartları tamamıyla belirlenmiş mantık sadeleştirme problemlerini ele aldık. Yani 3-değişkenli bir doğruluk tablosu ve Karnaugh haritası 2n = 23 ve 8-girdiye sahipti, böylece tam dolu bir tablo veya harita elde edildi. Gerçek-dünya problemleri için doğruluk tablosunu tamamen doldurmak her zaman gerekli değildir. Bütün tabloyu doldurmama seçeneğimizde olabilir. Örnek olarak, dört bit olarak kodlanmış BCD (İkili Kodlanmış Onlu) sayıları ile uğraşırken BCD aralığı (0, 1, 2...9) dışındaki herhangi bir kodlamayı dikkate almak zorunda değiliz. (Ah, Bh, Ch, Eh, Fh) onaltılı sayılar için olan 4-bit ikili kodları geçerli BCD kodu değildir. Böylece bir doğruluk tablosu veya K-haritası sonunda eğer istemezsek bu kodları doldurmak zorunda değiliz. Bu kodları doldurmak için uğraşmayız çünkü bu kodlar (1010, 1011, 1100, 1101, 1110, 1111) biz sadece BCD kodlanmış sayılarla uğraştığımız sürece var olmayacaktır. Bu altı geçersiz kod bize göre dikkate değer değildir. Yani bizim mantık devremizin çıkışının bu kodlar için ne ürettiği önemli değildir. Bir Karnaugh haritası veya doğruluk tablosunda bu önemsiz kodlar 1 veya 0 lardan oluşabilir, hiç bir zaman görmeyi ummadığımız giriş koşulu için olan çıkış bizi ilgilendirmez. Normal 1 ler ve 01 yada 0 lar olarak ele alın yada bunları ihmal edin. Bu önemsiz hücreler olmadan oluşturabileceğimiz gruptan daha büyük bir grup oluşturmamızı sağlayan durumlarda bu kullanışlıdır. Önemsiz hücrelerin bir kısmını veya hepsini gruplandırma ile ilgili bir zorunluluğumuz yoktur. Onları sadece mantığı basitleştiriyorsa bir grubun içerisinde kullanın. ların arasında bu hücreleri bir "*" ile belirtiriz. Bir hücreler grubu oluştururken bu önemsiz hücreleri ya
Yukarıda 000 dan 101 aralığına ABC = 101 girişi için 1 çıkışını veren bir mantık fonksiyonuna örnek vardır. Diğer olası girişler (110, 111) için çıktının ne olacağıyla ilgilenmeyiz. Bu ikisini önemsiz hücreler olarak işaretleyin. İki çözüm gösteriyoruz. Sağdaki Çıkış = AB'C çözümü önemsiz hücreleri kullanmadığımız için daha karmaşık bir çözümdür. Ortadaki Çıkış=AC çözümü tekli 1 ile ikili bir grup oluşturmak için önemsiz hücreyi kullandığımızdan daha az karmaşıktır. Sağdaki üçüncü çözüm olan Toplamlar-ın-Çarpımı önemsiz bir hücreyi üç adet sıfırla birlikte dört 0 dan oluşan bir grup oluşturacak şekilde gruplandırma sonucunda ortaya çıkar. Bu daha az karmaşık olan Çıkış=AC sonucudur. Önemsiz hücrelerin 1 veya 0 dan hangisi kullanışlı ise onun kullanılabileceğini gösterdik.
Lightning State College inin elektronik sınıfından yerel bir bilim müzesinde sergilenen durağan bir bisiklet için lamba mantığı oluşturmaları istenmiştir. Sürücü pedal çevirme hızını artırdıkça bir bar grafik ekranındaki lambalar yanacaktır. Hareket olmazsa lambaların hiç biri yanmayacaktır. Hız arttıkça en aşağıdaki L1 lambası yanar sonra L1 ve L2 sonra L1, L2 ve L3 en yüksek hızda da bütün lambalar yanar. Bütün lambalar yandıktan sonra hızdaki artış ekranda hiçbir etki göstermeyecektir. Bisikletin tekerine bağlı bir ufak DC üreteci hızla doğru orantılı bir gerilim üretir. Bu bütün lambaların yandığı en üst hızda gerilimi sınırlayan bir takometre kartını besler. Hızdaki daha fazla artış bu seviyeden sonra gerilimi artırmaz. Bu önemlidir çünkü A D (Analogdan Sayısala) çeviricisi 3-bitlik ABC, 23 veya 8-kod üretir fakat bizim sadece beş lambamız vardır. A en anlamlı bittir C ise en az anlamlı bittir. A dan D ye çevrimde lamba mantığı altı adet koda yanıt vermelidir. ABC=000 için hareket yoktur, hiç bir lamba yanmaz. (001 den 101) e olan beş kod için hız, gerilim ve A dan D ye (ABC) kodu arttıkça sırasıyla L1, L1veL2, L1veL2veL3 bütün lambaların yanması durumuna kadar yanar. (110, 111) giriş kodlarının çıkışıyla ilgilenmeyiz çünkü bu kodlar takometre bloğundaki sınırlamadan dolayı A dan D ye olan çevrimden çıkmazlar. Beş lambayı besleyecek beş adet mantık devresi tasarlamamız gerekir.
A dan D ye çevrimimde ABC=000 durumunda hiç bir lamba yanmadığı için ABC=000 hücresi için bütün K-haritalarına 0 girin. Hiç bir zaman karşılaşılmayan(110, 111) kodları için bütün beş K-haritalarındaki ilgili iki hücreye yıldız girin. L5 lambası sadece ABC=101 kodu için yanar. K-haritasında o hücreye 1 girin ve L5 in geri kalan bütün hücrelerine 0 girin. L4 ABC=100 kodunda yanmaya başlar ve daha büyük ABC=101 bütün kodlar için L5 yandığında L5 in altındaki bütün lambalar da yanar. L4 haritasındaki 100 ve 101 hücrelerine 10 doldurur. girin böylece bu kodlar için lamba yanar. Geri kalan L4 hücrelerini dört adet L3 lambası ABC=011 kodu için yanmaya başlar. L5 ve L4 ün yandığı durumlar için o da yanar. L3 haritası için 011, 100, 101 hücrelerine üç tane 1 girin. Geri kalan L3 hücrelerine üç tane 0 girin. L2 lambası ABC=010 ve daha büyük kodlar için yanar. 010, 011, 100, 101 hücrelerini 1 ile doldurun ve geri kalan hücrelerine iki tane 0 girin. L1 in yanmadığı tek durum hareketsizliktir. ABC=000 için zaten bir 0 vardır. Diğer tüm beş hücre 1 dir. Yukarıda gösterildiği gibi daha büyük grup oluşturmak için önemsiz hücreleri kullanarak 1 leri gruplandırın. L1 haritası 4-hücreli üç gruba karşılık gelen üç çarpım terimini gösterir. Biz önemsiz iki hücreyi grupların ikisinde ve bir önemsiz hücreyi üçüncü grupta kullandık. Önemsiz hücreler dörtlü gruplar oluşturmamızı sağlarlar. Aynı şekilde L2 ve L4 haritaları önemsiz hücrelerin yardımıyla 4-hücreli gruplar oluşturur. L4 lambası A dan D ye çeviricide en önemli bit L5=A tarafından kontrol edildiğinden L4 indirgenmesi dikkat çekicidir. L4 lambası için hiç bir mantık geçidi gerekmez. L3 ve L5 haritalarında tekli hücreler önemsiz hücrelerle iki grup oluşturur. Bütün beş haritada indirgenmiş Boole denklemi önemsiz hücreler olmadığı durumdan daha az karmaşıktır.
Devre için geçit diyagramı yukarıdadır. Beş K-haritası denkleminin çıkışları eviricileri besler. L1 OR geçidinin 3-girişli bir geçit olmayan girdisi (A+B), C çıktısı A+B+C olan iki girişli bir geçittir. 7406 açık toplayıcı eviriciler LED leri beslemede tercih edilir fakat bunlar K-haritası mantık tasarımının bir parçası değldir. Açık toplayıcı geçidi yada eviricisinin çıkışı harici bir yük üzerinden tüm toplayıcı akımın akabilmesi için entegre devre paketinde toplayıcı dahilinde açık devre yapılmıştır. Eviricilerin herhangi birine aktif yüksek gelirse çıkış düşük olur, akımı LED ve sınırlama direnci üzerinden sürer. LED ler bir müze sergisinde 120VAC lamba besleyen bir katı hal rölesinin parçası olurlar, burada gösterilmemiştir. 5 ve 6 Değişkenli Büyük Karnaugh Haritaları Büyük Karnaugh haritaları büyük mantık tasarımlarını indirger. Ne kadar büyüklük yeteri kadar büyüktür? Bu mantık devresine olan girdi sayısına ve girdi yelpazesine bağlıdır. Büyük programlanabilir mantık şirketlerinden birinin bir cevabı var. Altera'nın müşteri tasarımları kütüphanesinden çıkan kendi verileri, farklılık değerini destekler. Mantık konilerini inceleyerek, onları LUT-bazlı düğümlere eşleyerek ve onları her düğümde en iyi olacak şekilde girdi sayısına göre dizerek, Altera iki ve altı arası girdi için girdi yelpazesinin dağılımının yaklaşık olarak düzgün olduğunu ve beş girdi için güzel bir tepe yaptığını buldu. Cevap, bütün tasarımların çoğu için altıdan fazla girdi olmaması ve ortalama mantık tasarımı için beş girdi olmasıdır. Beş değişkenli Karnaugh haritası şöyledir:
Yukarıda, beş değişkenli K-haritasının eski sürümü olan bir Gray Kodu haritası veya yansıma haritası gösterilmiştir. Haritanın üstü (ve 6-değişkenli harita için köşesi) tamamen Gray kodu ile numaralandırılmıştır. Gray kodu yaklaşık olarak kodun ortasından yansır. Bu stildeki harita eski kitaplarda bulunur. Tercih edilen yeni stil aşağıdadır.
Yukarıda gösterilen katmanlı Karnaugh haritası, yukarıdaki 3-bit adresin en anlamlı biti haricinde iki (6-değişkenli harita için dört) eşit haritadır. Haritanın tepesine bakarsak numaralandırmanın önceki Gray kodu haritasından farklı olduğunu görürüz. 3-basamaklı sayıların en anlamlı basamağını ihmal edersek, 00, 01, 11, 10 dizisi katmanlı haritanın her iki alt haritasının başlığı olur. Sekiz adet 3-basamaklı sayının dizisi bir Gray kodu değildir. Fakat en az anlamlı iki bitin dört tanesinin dizisi bir Gray kodudur. 5-değişkenli Karnaugh haritasını kullanalım. 5-bitlik (A, B, C, D, E) ikili girişi olan bir devre tasarlayın, A burada MSB (En Anlamlı Bit(Most Significant Bit)) dir. Giriş verisinde algılanan herhangi bir asal sayı için Yüksek mantık çıkışı üretmelidir.
Referans olması için çözümü yukarıda eski Gray kod (yansıma) haritası üzerinde gösteriyoruz. Asal sayılar (1,2,3,5,7,11,13,17,19,23,29,31) dır. Karşılık gelen her bir hücreye 1 yerleştirin. Sonra hücrelerin gruplandırmasıyla devam edin. Sadeleştirilmiş sonucu yazarak bitirin. Dört hücreli A'B'E grubunun ayna hattının her iki tarafında iki çift hücreden oluştuğuna dikkat edin. Aynısı 2-hücreli AB'DE grubu için de geçerlidir. Bu ayna hattı etrafında yansıtılan 2-hücreli bir gruptur. K-haritasının bu biçimini kullanırken haritanın diğer yarısında ayna imajlarını arayın. Çıkış = A'B'E + B'C'E + A'C'DE + A'CD'E + ABCE + AB'DE + A'B'C'D Aşağıda 5-değişkenli haritanın en genel biçimi olan katmanlı(bindirmeli(overlay)) haritayı gösteriyoruz.
İki haritayı karşılaştırırsak, sağ taraftaki haritadaki bazı hücreler yer değiştirmiştir çünkü haritanın üzerindeki adresleme farklıdır. Haritanın iki yarısı arasındaki ortak noktaları belirlerken farklı bir yaklaşım ele alırız. Haritanın bir yarısını diğerinin üzerine bindiririz. Yukarıdaki haritadan aşağıdaki haritaya olan herhangi bir kesişme potansiyel bir gruptur. Aşağıdaki şekil AB'DE grubunun iki hücre yığınından oluştuğunu gösterir. A'B'E grubu iki hücre çiftleri yığınından oluşur. 4-hücreli A'B'E grubu için ABCDE = 00xx1. Yani bu grup için A,B,E sırasıyla 001 e eşittir. Ve, CD=xx yani değişir, 4-hücreli grup için CD=xx de bir benzerlik yoktur. ABCDE = 00xx1 olduğundan dolayı 4-hücreli grup A'B'XXE = A'B'E tarafından kapsanır.
Yukarıdaki 5-değişkenli bindirmeli harita yığındı olarak gösterilmiştir. Sırada altı değişkenli bir Karnaugh haritasının örneği var. Çıkış = C'F' e karşılık gelen 4-hücreli grubu görmek için dört alt haritayı hayali olarak yığınladık.
Bir büyüklük karşılaştırıcısı (6-değişkenli K-haritasını göstermek için kullanılır) iki ikili sayıyı karşılaştırır ve üç çıkışından bu sayıların eşit olup olmadığı ve birinin diğerinden büyük veya küçük olduğunu gösterir. Üç bitlik bir büyüklük karşılaştırıcısının iki girişi vardır, A2A1A0 ve B2B1B0. Entegre devre büyüklük karşılaştırıcısının (7485) gerçekte dört girişi olur fakat aşağıdaki Karnaugh haritası belli bir büyüklükte tutulmalıdır. Biz sadece A>B çıkışı için çözüyoruz. Aşağıda 6-değişkenli bir Karnaugh haritası 3-bitlik bir büyüklük karşılaştırıcının mantık sadeleştirmesine yardımcı olur. Bu birdirmeli tip bir haritadır. Haritanın üstünde ve soldaki yukarıdan aşağıya ikili adres kodu tamamen 3-bitli Gray kod değildir. Buna rağmen dört adet alt haritanın 2-bitli adres kodu Gray koddur. Dört alt haritayı birbiri üstüne koyarak fazla ifadeleri bulunuz (yukarıda gösterilmiştir). Her dört harita için ortak olan hücreler olabilir, fakat aşağıdaki örnekte bu yoktur. Alt harita çiftleri için ortak olan hücreler vardır.
Yukarıdaki A>B çıkışı aşağıdaki harita üzerinde ABC>XYZ dir.
ABC nin XYZ den büyük olduğu yerlerde 1 konur. İlk sırada ABC=000 XYZ nin herhangi bir değeri için ondan büyük olamaz. Bu çizgide hiç 1 yoktur. İkinci çizgide ABC=001 sadece ilk hücre ABCXYZ= 001000 için ABC XYZ den büyüktür. İkinci çizginin birinci hücresine tek bir 1 girilir. Dördüncü çizgide ABC=010 bir çift 1 vardır. Üçüncü çizgide ABC=011 üç tane 1 vardır. Böylece ABC nin XYZ den büyük olduğu her bir hücre1 lerle doldurulur. Hücreleri gruplandırırken mümkünde komşu olan alt haritalarla grup oluşturun. 16-hücreli bir grubun biri haricinde hepsi alt harita çiftlerinden hücreler içerir. Aşağıdaki grupları arayınız:
16-hücreli AX' grubu sağ alttaki alt haritanın tamamını işgal eder; fakat onu şekil üzerinde göstermiyoruz. 8-hücreli bir grup yukarıdaki alt haritada bulunan 4-hücreli bir grup ve altındaki soldaki benzer bir gruptan oluşur. 8-hücreli ikinci grup birbirine benzer 4-hücreli gruplardan oluşur, bu gruplardan biri sağdaki alt haritada diğer alt soldaki haritada bulunur. 4-hücreli dört grup karşılık gelen çarpım terimleriyle birlikte yukarıdaki Karnaugh haritasında gösterilmiştir. 8-hücreli iki grubun çarpım terimleri ve 16-hücreli bir grup Çarpımlar-ın-Toplamı son indirgemesi gösterilmiştir, bunların hepsi yedi terim yapar. Haritadaki 1 leri sayarsak toplamda 16+6+6=28 adet bir vardır. K-haritası mantık indirgemesinden önce SOP çıktımızda her biri 6-giriş olan 28 çarpım terimi olacaktır. Karnaugh haritası dört yada daha az girişli yedi çarpım terimi verir. Bu da Karnaugh haritalarının ne olduğunu bize gösterir! Kablolama diyagramı burada gösterilmemiştir. Fakat burada 4 TTL mantık ailesini kullanarak ABC>XYZ için 3-bitli büyüklük karşılaştırıcısının malzeme listesi verilmiştir:
kaynak:cizgi tagem
Favorilerinize ekleyin
Okuma: 1999 Yorumlar (0)
 Yorum yaz
|
Bu yorumun beslemesine abone olun