Genel Lojik Fonksiyonların Yalınlaştırılması ( indirgenmesi ) Sayısal Devreler (Lojik Devreleri) ©2000-2009 Yrd.Doç.Dr. Feza BUZLUCA 4.1 http://www.akademi.itu.edu.tr/buzluca Lojik Fonksiyonların Yalınlaştırılması (Dndirgenmesi ) Bir lojik fonksiyonun birçok cebirsel ifadesi vardır. (Bkz. kanonik açılımlar ve yalınlaştırılmış ifadeleri) Yalınlaştırmada amaç, belli bir maliyet kriterine göre bu cebirsel ifadeler içinden en uygun olanını seçmektir. Maliyet kriteri uygulamaya göre değişebilir. Örneğin tasarım aşamasında istenen özellikler şunlar olabilir: Dfadenin az sayıda çarpım (ya da toplam) içermesi, her çarpımda az sayıda değişken olması, devrenin aynı tip bağlaçlar (örneğin TVE) ile gerçeklenebilmesi, elde var olan bağlaçların kullanılabilmesi gibi. Yalınlaştırma Dle Dlgili Tanımlar Asal Çarpım (Temel Dçeren) “ Prime Implicant”: Hatırlatma: Bir fonksiyonun 1. kanonik açılımını oluşturan çarpımlar (minterimler) bu fonksiyon tarafından örtülürler (içerilirler). Buradaki her çarpım sadece bir "doğru" noktaya karşı gelir. Bu çarpımlardan bazılarının bölenleri de o fonksiyon tarafından örtülürler. Buna göre 1. kanonik açılımda yer alan bazı çarpımlar birleştirerek daha az değişken içeren ve birden fazla "doğru" noktaya karşı gelen yeni çarpımlar elde edilebilir. Ders Notlarının Creative Commons lisansı Feza BUZLUCA’ya aittir. Lisans: http://creativecommons.org/licenses/by-nc-nd/3.0/ Sayısal Devreler (Lojik Devreleri) ©2000-2009 Yrd.Doç.Dr. Feza BUZLUCA 4.2 http://www.akademi.itu.edu.tr/buzluca A B C F 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 Buna göre asal çarpım (temel içeren) kendi bölenleri fonksiyonda yer almayan çarpımlardır. • Örneğin yukarıdaki örnekte ABC' bir asal çarpım değildir, çünkü onun böleni olan AB de fonksiyon tarafından örtülmektedir. • AB ise bir asal çarpımdır, çünkü onun bölenleri A ve B fonksiyon tarafından örtülmez (daha fazla 1 üretiyorlar, fonksiyonun ifadesinde yer alamazlar). Yalınlaştırma işlemi 2 aşamadan oluşmaktadır: 1. Tüm asal çarpımlar kümesinin (Tüm temel içerenlerin) bulunması 2. Fonksiyonun tüm "doğru" noktalarını örtecek şekilde, asal çarpımlardan en uygun olanların seçilmesi. F(A, B, C)= ?m(1,3,5,6,7) : 1. kanonik açılım = A'B'C + A'BC + AB'C + ABC' + ABC Bu çarpımlar, asal çarpım (temel içeren) değildir, çünkü onlardan daha az değişkene sahip olan bölenleri de bu fonksiyonun içinde yer almaktadır. Bu durum basitleştirme sonucu görülmüştü ve fonksiyon için aşağıdaki ifade elde edilmişti. F= AB+C Kanonik açılımdaki çarpımlar sadece 1 adet doğru nokta örterken AB çarpımı 2 adet, C ise 4 adet nokta örtmektedir.Sayısal Devreler (Lojik Devreleri) ©2000-2009 Yrd.Doç.Dr. Feza BUZLUCA 4.3 http://www.akademi.itu.edu.tr/buzluca Asal Çarpımların Bulunması: Çarpım terimlerini birleştirerek daha az değişkene sahip ve daha çok doğru noktayı örten çarpımlar elde etmek için Boole cebri kullanılabilir. Bu işlemi özellikle büyük fonksiyonlar için elle kağıt üstünde yapmak zor olur. Bu işlemler bilgisayar programları ile yapılır. Fonksiyonun cebirsel ifadesini kullanmadan daha pratik olarak uygulanabilecek bir yöntem: • Doğruluk tablosunda "1" üreten kombinezonlar incelenir, • Bir veya daha fazla değişkenin (girişin) sabit kaldığı kombinezonlar birleştirilir, • Değeri sabit kalan değişkenler çarpımda kalır, değişenler çarpımdan çıkarılır. Örnek: A B F 0 0 1 0 1 0 1 0 1 1 1 0 B sabit. Her ikisinde de B=0. B değişkeni yeni çarpımda yer alacak. A nın değeri değişiyor. A yeni çarpımda olmayacak. = (A'+A)B' = B' F = A'B'+AB' B=0 olduğu için yeni çarpım: B' Cebirsel olarak birleştirme: Sayısal Devreler (Lojik Devreleri) ©2000-2009 Yrd.Doç.Dr. Feza BUZLUCA 4.4 http://www.akademi.itu.edu.tr/buzluca A B F 0 0 1 0 1 0 1 0 1 1 1 0 Boyutu 0 olan iki nokta birleştirilerek boyutu 1 olan bir çizgi elde edildi. Bu çizgi B=0'ı yani B’nin tümleyenini temsil etmektedir. 0 1 2 3 0 1 B A 0 1 1 1 0 0 F Bu tür gruplamaları Karnaugh diyagramları ile yapmak daha kolaydır. Bitişiklilik özelliğinden yararlanılarak komşu noktalar gruplanabilir. Yukarıda gruplamanın yapıldığı sütunda B=0 (sabit), A ise değişkendir. Bu sütun B’nin tümleyenini temsil etmektedir. A B 11 00 01 10 Yapılan işlemin Boole küpünde gösterilmesi: Yapılan işlemin Karnaugh diyagramında gösterilmesi:Sayısal Devreler (Lojik Devreleri) ©2000-2009 Yrd.Doç.Dr. Feza BUZLUCA 4.5 http://www.akademi.itu.edu.tr/buzluca AC 0 0 0 0 0 1 1 1 00 01 BC A 0 1 11 10 A C B F Aynı anda birden fazla değişken sabit kalıyorsa gruplama sonucu bu değişkenlerin çarpımı oluşur. A=1 , B=1 ve sabit. C ise değişiyor. Bu gruplama sonucu AB çarpımı oluşur. Cebirsel: ABC' + ABC = AB(C'+C) = AB A 000 B C 111 101 100 001 010 011 110 AB AC AB Örnek: A B C F 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 A=1 , C=1 ve sabit. B ise değişiyor. Bu gruplama sonucu AC çarpımı oluşur. Cebirsel: AB'C + ABC = AC(B'+B) = AC Sayısal Devreler (Lojik Devreleri) ©2000-2009 Yrd.Doç.Dr. Feza BUZLUCA 4.6 http://www.akademi.itu.edu.tr/buzluca 1 1 1 1 0 0 0 0 00 01 BC A 0 1 11 10 A C B F Gruplamalarda 2'den daha fazla nokta da birleştirilebilir. Örnek: F(A,B,C) = S (4,5,6,7) A=1 ve sabit. B ve C ise değişiyor. Küpün bu yüzü A yı temsil ediyor. Cebirsel: AB'C' + AB'C + ABC' + ABC = AB'+AB = A A B C 000 111 101 100 001 010 011 110 A=1 ve sabit. B ve C ise değişiyor. Karnaugh diyagramı ile:Sayısal Devreler (Lojik Devreleri) ©2000-2009 Yrd.Doç.Dr. Feza BUZLUCA 4.7 http://www.akademi.itu.edu.tr/buzluca A B C A B C D Asal Çarpımların Karnaugh Diyagramları Dle Bulunması : Karnaugh diyagramlarındaki bitişiklilik ve çevrimlilik özelliği nedeniyle komşu gözler arasındaki geçişlerde sadece 1 değişken (giriş) değer değiştirir, diğerleri sabit kalır. Girişlerin sabit kaldığı komşu gözlerdeki "doğru" noktaları 2'li, 4'lü, 8'li … gruplarda toplamak mümkündür. Aşağıda 3 ve 4 değişkenli Karnaugh diyagramları için girişlerin sabit kaldıkları alanlar gösterilmiştir. 0 2 1 3 00 01 AB C 0 1 6 4 7 5 11 10 C B A 0 1 4 5 00 01 BC A 0 1 3 2 7 6 11 10 Aynı diyagram, değişkenler farklı şekillerde yerleştirilerek de yandaki gibi oluşturulabilir. 0 1 4 5 3 2 7 6 00 01 11 10 12 13 8 9 15 14 11 10 AB CD 00 01 11 10 Lisans: http://creativecommons.org/licenses/by-nc-nd/3.0/ Sayısal Devreler (Lojik Devreleri) ©2000-2009 Yrd.Doç.Dr. Feza BUZLUCA 4.8 http://www.akademi.itu.edu.tr/buzluca Örnek: Aşağıda verilen fonksiyonun asal çarpımlarının bulunması F(A,B,C,D) = S 1 (0,2,5,8,9,10,11,12,13,14,15) C B 00 01 11 10 1 0 0 1 0 1 0 0 1 1 1 1 1 1 1 1 A AB F CD 00 01 11 10 D Asal Çarpımlar: A , B'D' , BC'D • Asal çarpımlar bulunurken fonksiyonun "doğru" noktaları mümkün olan en büyük gruplara yerleştirilirler. • Bir grupta yer alan iki nokta tekrar birleştirilerek daha küçük bir grup oluşturulmaz. • Örneğin ayrı ayrı 4 'lü gruplarda bulunan iki nokta birleştirilerek 2'li yeni bir grup oluşturmaya gerek yoktur. Yeni bir 4’lü grup oluşturulabilir. • Ancak noktalardan biri daha büyük bir gruba ait değilse (yukarıdaki 0101 gibi) o nokta gruptaki başka bir nokta ile kümelenebilir.Sayısal Devreler (Lojik Devreleri) ©2000-2009 Yrd.Doç.Dr. Feza BUZLUCA 4.9 http://www.akademi.itu.edu.tr/buzluca 1 1 1 1 1 1 00 01 BC A 0 1 11 10 A C B Tüm Asal Çarpımlar Kümesinin (Temel Dçeren Tabanını n) Bulunması: Lojik devre tasarımında yalınlaştırma işlemi o fonksiyonun bütün asal çarpımlarının bulunmasıyla başlar. Bütün asal çarpımların oluşturduğu kümeye tüm asal çarpımlar kümesi (tüm temel içeren tabanı) denir. Dndirgemenin 2. aşamasında fonksiyonun bütün doğru noktalarını örtecek şekilde, tüm asal çarpımlar kümesinden en uygun asal çarpımlar seçilir. Fonksiyonun bütün doğru noktalarını örten asal çarpımların oluşturduğu kümeye yeterli taban denir. Yeterli tabandan bir asal çarpım kaldırılırsa fonksiyonun tüm doğru noktaları örtülmemiş olur. Asal Çarpımlar: BC' , A'B , A'C , AB' , B'C , AC' Buna göre bir fonksiyonu yalınlaştırma işlemi en uygun (ucuz) yeterli tabanı bulmak demektir. Örnek: Aşağıdaki fonksiyonun tüm asal çarpımlar kümesini bulunuz. Aynı fonksiyonun bir çok yeterli tabanı olabilir. 1 1 1 1 1 1 00 01 BC A 0 1 11 10 A C B F(A,B,C)= BC' + A'C + AB' 1 1 1 1 1 1 00 01 BC A 0 1 11 10 A C B A'B + B'C + AC' F(A,B,C)= F(A,B,C)= 1 1 1 1 1 1 00 01 BC A 0 1 11 10 A C B A'B + BC' + AB' + B'C 1 1 1 1 1 1 00 01 BC A 0 1 11 10 A C B F(A,B,C)= BC' + A'C + B'C + AC' Yeterli tabandan bir asal çarpım kaldırıldığında tüm doğru noktalar kapsanmamış olur.Sayısal Devreler (Lojik Devreleri) ©2000-2009 Yrd.Doç.Dr. Feza BUZLUCA 4.11 http://www.akademi.itu.edu.tr/buzluca Başlıca Nokta ve Gerekli Asal çarpım: Bazı fonksiyonlarda bazı doğru noktalar sadece bir asal çarpım tarafından örtülürler. Bu noktalara başlıca nokta denir. Bu noktaları örten asal çarpımlara da gerekli asal çarpım denir. Gerekli asal çarpımlar fonksiyonun yeterli tabanında mutlaka yer alırlar. Çünkü başlıca noktaların başka asal çarpımlar tarafından örtülmesi mümkün değildir. Örnek: C B 00 01 11 10 1 1 1 1 1 1 1 1 1 1 1 A AB F CD 00 01 11 10 D Tüm Asal Çarpımlar Kümesi: C'D , BC' , AC' , BD' ,A'CD' , AB'D Başlıca Noktalar Gerekli çarpımlar 0001 C'D 0010 A'CD' 1000 AC' 1110 BD' 1011 AB'D Buradaki gerekli asal çarpımlar fonksiyonun tüm doğru noktalarını örtmektedir. F= C'D + A'CD' + AC' + BD' + AB'D Sayısal Devreler (Lojik Devreleri) ©2000-2009 Yrd.Doç.Dr. Feza BUZLUCA 4.12 http://www.akademi.itu.edu.tr/buzluca C B 00 01 11 10 1 1 1 1 1 1 1 1 1 1 1 A AB F CD 00 01 11 10 D Örnek: Bir fonksiyonun tüm asal çarpımlar kümesinin, başlıca noktalarının ve gerekli çarpımların bulunması. Tüm Asal Çarpımlar Kümesi: CD , AB , A'C , BC , BD' , A'D' Başlıca Noktalar Gerekli çarpımlar 0000 A'D' 1101 AB 1011 CDSayısal Devreler (Lojik Devreleri) ©2000-2009 Yrd.Doç.Dr. Feza BUZLUCA 4.13 http://www.akademi.itu.edu.tr/buzluca Hatırlatma: Yalınlaştırma işlemi 2 aşamadan oluşmaktadır: 1. Tüm asal çarpımlar kümesinin (Tüm temel içerenlerin) bulunması 2. Fonksiyonun tüm "doğru" noktalarını örtecek şekilde, asal çarpımlardan en uygun (ucuz) olanların seçilmesi. En uygun asal çarpımların (yeterli tabanın) seçilmesinde kullanılan yöntemlerden biri seçenekler tablosu yöntemidir. Yalınlaştırma: Uygun Asal Çarpımların Seçilmesi Seçenekler Tablosu: • Fonksiyonun asal çarpımları bulunduktan sonra bu çarpımlara isimler verilir. Örneğin A, B, C, .. gibi. • Verilen bir maliyet kriterine göre her asal çarpımın maliyeti hesaplanır. Seçenekler tablosu bir matris şeklinde hazırlanır. • Tablonun satırlarında, fonksiyonun asal çarpımlarının isimleri yer alır. Sütunlarda ise o fonksiyonun doğru noktalarının numaraları bulunur. • En son sütuna asal çarpımların maliyetleri yazılır. • Bir asal çarpım bir noktayı örtüyorsa matrisin ilgili gözüne X konur. Lisans: http://creativecommons.org/licenses/by-nc-nd/3.0/ Sayısal Devreler (Lojik Devreleri) ©2000-2009 Yrd.Doç.Dr. Feza BUZLUCA 4.14 http://www.akademi.itu.edu.tr/buzluca Örnek: Verilen fonksiyonun tüm asal çarpımlar kümesini bulunuz ve seçenekler tablosunu oluşturunuz. f(x 1 , x 2 , x 3 , x 4 )=S m(2, 4, 6, 8, 9, 10, 12, 13, 15) Maliyet hesabında her değişken 2 birim, her tümleme işlemi 1 birim maliyete sahip olacaktır. x 3 x 2 00 01 11 10 1 1 1 1 1 1 1 1 1 x 1 x 1 x 2 f x 3 x 4 00 01 11 10 x 4 x 1 x 3 ' Tüm Asal Çarpımlar Kümesi: x 2 x 3 ' x 4 ' x 1 x 2 x 4 x 1 'x 2 x 4 ' x 1 x 2 ' x 4 ' x 1 'x 3 x 4 ' x 2 ' x 3 x 4 ' Semboller: A B C D E F G Maliyetler: 5 8 8 6 8 8 8 Örttüğü Noktalar:8,9,12,13 4,12 4, 6 13, 15 2, 6 2, 10 8, 10Sayısal Devreler (Lojik Devreleri) ©2000-2009 Yrd.Doç.Dr. Feza BUZLUCA 4.15 http://www.akademi.itu.edu.tr/buzluca X X X X 5 X X 8 X X 8 X X 6 X X 8 X X 8 x 1 x 3 ' Tüm Asal Çarpımlar Kümesi: x 2 x 3 ' x 4 ' x 1 x 2 x 4 x 1 'x 2 x 4 ' x 1 x 2 ' x 4 ' x 1 'x 3 x 4 ' x 2 ' x 3 x 4 ' Semboller: A B C D E F G Maliyetler: 5 8 8 6 8 8 8 Örttüğü Noktalar:8,9,12,13 4,12 4, 6 13, 15 2, 6 2, 10 8, 10 X X 8 2 4 6 8 9 10 12 13 15 Maliyet A B C D E F G Fonksiyonun "doğru" noktaları Sayısal Devreler (Lojik Devreleri) ©2000-2009 Yrd.Doç.Dr. Feza BUZLUCA 4.16 http://www.akademi.itu.edu.tr/buzluca 1. Başlıca noktalar belirlenir. Bir sütunda sadece bir tane X varsa o sütundaki nokta başlıca noktadır. Başlıca noktayı örten asal çarpım (gerekli asal çarpım) mutlaka fonksiyonun ifadesinde yer alacağından seçilir. Bu asal çarpıma ait satır ve onun örttüğü noktalara ait sütunlar tablodan kaldırılır. 2. Tabloda j. satırın X olan her gözünde i. satırda da X varsa i. satır, j. satırı örtüyor denir. Yani j. satırın örttüğü bütün noktaları i. satır da örtüyordur. Eğer i. satır j. satırı örtüyorsa ve i. satırdaki maliyet j. satırdaki maliyetten küçükse veya ona eşitse j. satır (örtülen satır) tablodan kaldırılır. 3. Bir sütun başka bir sütunu örtüyorsa örten sütun (daha fazla X'e sahip olan) tablodan silinir. Bu kurallar peş peşe uygulanarak fonksiyonun doğru noktaları toplam maliyet en az olacak şekilde örtülmeye çalışılır. Seçenekler Tablosunun DndirgenmesiSayısal Devreler (Lojik Devreleri) ©2000-2009 Yrd.Doç.Dr. Feza BUZLUCA 4.17 http://www.akademi.itu.edu.tr/buzluca Örnek: Aşağıda verilen fonksiyona ait seçenekler tablosunu indirgenmesi. f(x 1 , x 2 , x 3 , x 4 )=S m(2, 4, 6, 8, 9, 10, 12, 13, 15) Fonksiyonun "doğru" noktaları 1. Adım: Bu tabloda 9 ve 15 başlıca noktalardır. A ve D gerekli çarpımlar oldukları için onlara ait satır ve örttükleri sütunlar tablodan kaldırılır. Bu çarpımlar daha sonra sonucu oluştururken kullanılmak üzere işaretlenir. X X X X 5 X X 8 X X 8 X X 6 X X 8 X X 8 x 1 x 3 ' x 2 x 3 ' x 4 ' x 1 x 2 x 4 x 1 'x 2 x 4 ' x 1 x 2 ' x 4 ' x 1 'x 3 x 4 ' x 2 ' x 3 x 4 ' X X 8 2 4 6 8 9 10 12 13 15 Maliyet A B C D E F G Sayısal Devreler (Lojik Devreleri) ©2000-2009 Yrd.Doç.Dr. Feza BUZLUCA 4.18 http://www.akademi.itu.edu.tr/buzluca 2 4 6 10 Maliyet B x 8 C x x 8 E x x 8 F x x 8 G x 8 x 2 x 3 ' x 4 ' x 1 'x 2 x 4 ' x 1 x 2 ' x 4 ' x 1 'x 3 x 4 ' x 2 ' x 3 x 4 ' 2. Adım: Bu tabloda C, B'yi örter. Maliyetleri aynı olduğu için örtülen satır(B) tablodan silinir. Benzer şekilde F, G'yi örter ve maliyetleri aynıdır. Bu nedenle G satırı tablodan silinir. Bu çarpımlar sonuç ifadede yer almayacaktır. 2 4 6 10 Maliyet C x x 8 E x x 8 F x x 8 x 1 'x 2 x 4 ' x 1 'x 3 x 4 ' x 2 ' x 3 x 4 ' 3. Adım: Bu tabloda 4 ve 10 başlıca noktalardır. Bu nedenle C ve F çarpımlarını almak gerekir. Bu iki asal çarpım seçildiğinde tüm noktalar örtülmüş olur. Sayısal Devreler (Lojik Devreleri) ©2000-2009 Yrd.Doç.Dr. Feza BUZLUCA 4.19 http://www.akademi.itu.edu.tr/buzluca Sonuç: Dşaretlenmiş olan asal çarpımlar fonksiyonun en ucu z ifadesini oluştururlar. Seçilen asal çarpımlar: A + D + C + F Toplam Maliyet= 5 + 6 + 8 + 8 = 27 f(x 1 , x 2 , x 3 , x 4 ) = x 1 x 3 ' + x 1 x 2 x 4 + x 1 'x 2 x 4 ' + x 2 ' x 3 x 4 ' Karnaugh diyagramı ile hangi asal çarpımların seçildiğini görebiliriz. x 3 x 2 00 01 11 10 1 1 1 1 1 1 1 1 1 x 1 x 1 x 2 f x 3 x 4 00 01 11 10 x 4 x 1 x 3 ' x 1 x 2 x 4 x 1 'x 2 x 4 ' x 2 ' x 3 x 4 ' Bu seçimde tüm 1’ler örtülmeli ve bir fazlalık olmamalı. Seçilmiş olan asal çarpımlar bir yeterli taban oluşturmalı. Yani çarpımlardan biri kaldırıldığında tüm noktalar örtülememeli. Lisans: http://creativecommons.org/licenses/by-nc-nd/3.0/ Sayısal Devreler (Lojik Devreleri) ©2000-2009 Yrd.Doç.Dr. Feza BUZLUCA 4.20 http://www.akademi.itu.edu.tr/buzluca Tümüyle Tanımlanmamış Fonksiyonların Yalınlaştırılması Bu girişler için devrenin (fonksiyonun) çıkışlarının alacağı değer belirsizdir. Belirsiz değerleri göstermek için X yerine F sembolü de kullanılır. Hatırlatma:Tümüyle tanımlanmamış fonksiyonlarda, bazı giriş kombinezonları için fonksiyonun alacağı değer belirsizdir (önemli değildir). Çünkü bu giriş kombinezonları ilgili devrede fiziksel olarak oluşamazlar ya da tasarımcı tarafından yasaklanmışlardır. I8 I4 I2 I1 O8 O4 O2 O1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 X X X X 1 0 1 1 X X X X 1 1 0 0 X X X X 1 1 0 1 X X X X 1 1 1 0 X X X X 1 1 1 1 X X X X O1 O2 O4 O8 I1 I2 I4 I8 Örnek: BCD sayıları 1 arttıran devreSayısal Devreler (Lojik Devreleri) ©2000-2009 Yrd.Doç.Dr. Feza BUZLUCA 4.21 http://www.akademi.itu.edu.tr/buzluca • Tüm asal çarpımlar kümesi bulunurken daha basit çarpımlar elde etmek için (Karnaugh diyagramında daha büyük gruplamalar yapabilmek için) FF F F ler 1 olarak seçilir. • Seçenekler tablosunda kapsanması gereken noktalar yazılırken FF F F ler 0 olarak seçilir. Çünkü bu noktaların çarpımlar tarafından örtülmesine gerek yoktur. Örnek: Aşağıda verilen tümüyle tanımlanmamış fonksiyonu en düşük maliyetle tasarlayınız. f(x 1 , x 2 , x 3 , x 4 )=S m (2, 4, 8, 9, 13, 15 ) + S F (6,10,12) (Not: f(x 1 , x 2 , x 3 , x 4 )=¨ 1 (2, 4, 8, 9, 13, 15 ) + ¨ F (6,10,12) şeklinde de yazılabilir.) Maliyet hesabında her değişken 2 birim, her tümleme işlemi 1 birim maliyete sahip olacaktır. Yalınlaştırma işleminde, belirsiz değerler (F ) en ucuz ifadeyi elde edecek şekilde gerektiğinde lojik 0, gerektiğinde lojik 1 olarak seçilebilirler. Sayısal Devreler (Lojik Devreleri) ©2000-2009 Yrd.Doç.Dr. Feza BUZLUCA 4.22 http://www.akademi.itu.edu.tr/buzluca x 3 x 2 00 01 11 10 1 1 F F 1 1 1 1 F x 1 x 1 x 2 f x 3 x 4 00 01 11 10 x 4 x 1 x 3 ' Tüm Asal Çarpımlar Kümesi: x 2 x 3 ' x 4 ' x 1 x 2 x 4 x 1 'x 2 x 4 ' x 1 x 2 ' x 4 ' x 1 'x 3 x 4 ' x 2 ' x 3 x 4 ' Semboller: A B C D E F G Maliyetler: 5 8 8 6 8 8 8 Örttüğü Noktalar: 8,9,13 4 4 13,15 2 2 8 Asal çarpımlar bulunurken FF F F ’ler 1 olarak seçilir.Sayısal Devreler (Lojik Devreleri) ©2000-2009 Yrd.Doç.Dr. Feza BUZLUCA 4.23 http://www.akademi.itu.edu.tr/buzluca x 1 x 3 ' Tüm Asal Çarpımlar Kümesi: x 2 x 3 ' x 4 ' x 1 x 2 x 4 x 1 'x 2 x 4 ' x 1 x 2 ' x 4 ' x 1 'x 3 x 4 ' x 2 ' x 3 x 4 ' Semboller: A B C D E F G Maliyetler: 5 8 8 6 8 8 8 Örttüğü Noktalar: 8,9,13 4 4 13,15 2 2 8 X X X 5 X 8 X 8 X X 6 X 8 X 8 X 8 Bu noktaların örtülmesine gerek olmadığından F ’ler seçenekler tablosunda yer almazlar. Tablo oluşturulurken FF F F ’ler 0 olarak seçilir. 2 4 8 9 13 15 Maliyet A B C D E F G Fonksiyonun "doğru" noktaları Sayısal Devreler (Lojik Devreleri) ©2000-2009 Yrd.Doç.Dr. Feza BUZLUCA 4.24 http://www.akademi.itu.edu.tr/buzluca 2 4 8 9 13 15 Maliyet A B C D E F G X X X 5 X 8 X 8 X X 6 X 8 X 8 X 8 Fonksiyonun "doğru" noktaları 1. Adım: Bu tabloda 9 ve 15 başlıca noktalardır. A ve D gerekli çarpımlar oldukları için onlara ait satır ve örttükleri sütunlar tablodan kaldırılır. Bu çarpımlar daha sonra sonucu oluştururken kullanılmak üzere işaretlenir. Sayısal Devreler (Lojik Devreleri) ©2000-2009 Yrd.Doç.Dr. Feza BUZLUCA 4.25 http://www.akademi.itu.edu.tr/buzluca 2 4 Maliyet B x 8 C x 8 E x 8 F x 8 x 2 x 3 ' x 4 ' x 1 'x 2 x 4 ' x 1 'x 3 x 4 ' x 2 ' x 3 x 4 ' 2. Adım: B ve C aynı noktaları örtmektedir ve maliyetleri eşittir. Bu nedenle bu iki çarpım arasında bir seçim yapmak mümkün değildir. Verilen maliyet kriterine göre herhangi biri seçilebilir. Aynı durum E ve F çarpımları için de geçerlidir. Buna göre fonksiyon aşağıdaki ifadelerden herhangi biri kullanılarak gerçeklenebilir: f= A + D + B + E = x 1 x 3 ' + x 1 x 2 x 4 + x 2 x 3 ' x 4 ' + x 1 'x 3 x 4 ' f= A + D + B + F = x 1 x 3 ' + x 1 x 2 x 4 + x 2 x 3 ' x 4 ' + x 2 ' x 3 x 4 ' f= A + D + C + E = x 1 x 3 ' + x 1 x 2 x 4 + x 1 'x 2 x 4 ' + x 1 'x 3 x 4 ' f= A + D + C + F = x 1 x 3 ' + x 1 x 2 x 4 + x 1 'x 2 x 4 ' + x 2 ' x 3 x 4 ' Tüm tasarımların maliyeti eşittir (27). Lisans: http://creativecommons.org/licenses/by-nc-nd/3.0/ Sayısal Devreler (Lojik Devreleri) ©2000-2009 Yrd.Doç.Dr. Feza BUZLUCA 4.26 http://www.akademi.itu.edu.tr/buzluca Genel Fonksiyonların Yalınlaştırılması Hatırlatma: Genel fonksiyonların birden fazla çıkışı vardır. f x 1 x 2 x 3 y 1 y 2 0 0 0 1 1 0 0 1 1 F 0 1 0 0 0 0 1 1 F 0 1 0 0 1 F 1 0 1 0 1 1 1 0 0 1 1 1 1 F 0 x 1 x 2 x 3 y 1 y 2 Genel fonksiyonlar yalınlaştırılırken her çıkışa ait fonksiyon için ayrı ayrı tüm asal çarpımlar kümesi bulunur ve bunların içinden seçim yapılır. Burada dikkat edilmesi gereken nokta her iki çıkış için ortak çarpımların kullanılmaya çalışılmasıdır. Genel fonksiyonlar yalınlaştırılması bu dersin kapsamı dışında tutulmuştur. y 1 = f 1 (x 1 ,x 2 ,x 3 ) y 2 = f 2 (x 1 ,x 2 ,x 3 )Sayısal Devreler (Lojik Devreleri) ©2000-2009 Yrd.Doç.Dr. Feza BUZLUCA 4.27 http://www.akademi.itu.edu.tr/buzluca Tüm Asal Çarpımlar Kümesinin Tablo Yöntemiyle (Quine-McCluskey) Bulunması Karnaugh diyagramları görsel özellikleri nedeniyle az değişkenli fonksiyonlarla ilgili çalışmalarda kolaylık sağlarlar. Ancak değişken sayısı 5 ve daha fazla olduğunda Karnaugh diyagramlarını çizmek ve bitişiklilik özelliğini kullanmak zorlaşır. Tablo yöntemi (Quine-McCluskey) ise sistematik bazı işlemlerin peş peşe tekrarlanmasından oluşmaktadır. Bu işlemleri elle yapmak fazla zaman alabilir, ancak söz konusu işlemleri bilgisayar programı ile gerçekleştirmek kolaydır. Tablo (Quine-McCluskey) Yöntemi: Hatırlanacağı gibi, asal çarpımları bulmak için “1” değeri üreten ve bitişik olan giriş kombinezonları (minterimler) gruplanmaya çalışılıyordu. Sadece bir değişkenin değiştiği (bitişik) olan kombinezonlar aynı gruba alınıyordu. Tablo yönteminde “1” değeri olan her kombinezon (minterim) diğer minterimler ile karşılaştırılır. Eğer iki kombinezon arasında sadece bir giriş (değişken) farklıysa o iki kombine- zon gruplanır. Farklı olan değişken silinerek yeni terim elde edilir. Bu durum hiç gruplama yapılamayana kadar devam eder. Hiç bir gruba girmeyen terimler asal çarpımlardır. Sayısal Devreler (Lojik Devreleri) ©2000-2009 Yrd.Doç.Dr. Feza BUZLUCA 4.28 http://www.akademi.itu.edu.tr/buzluca • Karşılaştırma kolaylığı sağlamak için içindeki 1'lerin sayısına göre kombinezonları kümeleyin. • Komşu kümlerdeki kombinezonları karşılaştırın. Tek girişin farklı olduğu kombinezonları gruplayıp yeni kombinezonlar oluşturun. • Yeni kombinezonlarda değeri değişen giriş yer almayacaktır. • Bir gruba girmiş olan kombinezonları işaretleyin. • Yeni oluşan kombinezonlar üzerinde de aynı gruplama işlemlerini yeni gruplar oluşmayıncaya kadar sürdürün. • Hiç bir gruba girmemiş olan kombinezonlar (işaretsizler) tüm asal çarpımlar kümesini oluştururlar. Yöntem: Quine-McCluskey yöntemi sadece tüm asal çarpımlar kümesini (tüm temel içeren tabanını) bulmamızı sağlar. Yalınlaştırma işlemi için yine seçenekler tablosunu kullanmamız gerekecektir. Willard Van Orman Quine (1908-2000), Felsefe, lojik Edward J. McCluskey(1929-) Elektrik müh.Sayısal Devreler (Lojik Devreleri) ©2000-2009 Yrd.Doç.Dr. Feza BUZLUCA 4.29 http://www.akademi.itu.edu.tr/buzluca 0,8,2,10 - 0 - 0 10,11,14,15 1 - 1 - Tüm asal çarpımlar kümesi (Dşaretsiz olanlar): x 1 ' x 2 ' x 3 ' , x 2 ' x 4 ' , x 1 x 3 Örnek: Aşağıda verilen fonksiyonun tüm asal çarpımlar kümesini Quine-McCluskey yöntemiyle bulunuz. f(x 1 , x 2 , x 3 , x 4 )= S m (0, 1, 2, 8, 10, 11, 14, 15 ) K.No x 1 x 2 x 3 x 4 0,1 0 0 0 - 0,2 0 0 - 0 0,8 - 0 0 0 2,10 - 0 1 0 8,10 1 0 - 0 10,11 1 0 1 - 10,14 1 - 1 0 11,15 1 - 1 1 14,15 1 1 1 - K.No x 1 x 2 x 3 x 4 0,2,8,10 - 0 - 0 10,11,14,15 1 - 1 - Aynı olanları yazmaya gerek yok En ucuz çözümü elde etmek için bu aşamadan sonra seçenekler tablosu oluşturulur ve en ucuz yeterli taban bulunur. K.No x 1 x 2 x 3 x 4 0 0 0 0 0 1 0 0 0 1 2 0 0 1 0 8 1 0 0 0 10 1 0 1 0 11 1 0 1 1 14 1 1 1 0 15 1 1 1 1