Quine-McCluskey yönteminde ikinci bölümü bilen yok mu?

[DumrulBey]

Merhaba,

Bildiğiniz gibi sayısal elektronikte Karnaugh haritaları dışına Quine-McCluskey yöntemini kullanıyoruz. Genelde terim sayısı 6'yı geçtiğinde Karnaugh haritaları üstesinden gelinemeyecek bir hal alıyor. Dolayısıyla Quine-McCluskey yöntemini kullanmak zorundayız. Ancak bu bu yöntem her zaman Karnaugh gibi en sade sonucu vermiyor. Bazı eksiklikleri var ve bunun üstesinden geliniyor. Bana bunu okulda öğretmediler ve farkına vardığımda araştırmaya çalıştım. Fakat öğrenemeden araştırmayı yarıda bırakmak zorunda kaldım. Şimdi yeniden başladım ve yardıma ihtiyaç duyuyorum.

:arrow: Quine-McCluskey Method: http://www.cs.ualberta.ca/~amaral/courses/329/webslides/Topic5-QuineMcCluskey/Topic5-QuineMcCluskey.PPT (PPT, 778 KB.)

Yukarıda, bu yöntemin tarihini ve uygulanışını anlatan indirilebilir bir sunum dosyası var. İşte benim başlangıç noktam da buydu. Eğer bilgisayarınızda PowerPoint yüklü değilse aşağıdaki adrese tıklayıp HTML sürümünü inceleyebilirsiniz. Sunumda, 79. sayfada başlayan ve devamında da yöntemin ikinci kısmı anlatan bir bölüm var. Ama ben anlamadım... :oops:

http://66.102.9.104/search?q=cache:VfINZz4WQGgJ:www.cs.ualberta.ca/~amaral/courses/329/webslides/Topic1-BooleanLogic/Topic1-BooleanLogic.PPT

İşin ilginci ilk farkettiğimde hocalarıma danışıp sordum ama onlarda yardımcı olamadılar. Sonra bitirme ödevi, sınav ve staj gibi nedenlerden kaynadı ve aradan geçen bir sene zarfında araştırmalarım arasında yer aldı. Eğer yardım ederseniz sevinirim. Okullarda bile (en azından bizim okulda) öğretilmeyen bu konuyu öğrenmem lazım. Çünkü yöntemi bize eksik anlattıkları için bilip bilmemem bir işe yaramıyor. Bazı zaman elektronik mühendislerine bile sordum yardımcı olamadılar. Tek umudum siz forum üyelerisiniz.

Orada zorlanacağınız bir terim var o da "Prime Implicant", Türkçesi "İlk ihmal edilebilir" demekmiş. Emin değilim ama doğrudur herhalde. Bu terimin anlamını bile bulmakta çok zorlandım. Ancak şemaları anlamakta hala zorlanıyorum. Belki IQ'su benden yüksek olan arkadaşlar durum çözerler.

Teşekkürler...

[z]

Bilgisayarla lojik devre tasarımında yaygın kullanılan sadeleştirme tekniklerinden birisi olan  Quine-McCluskey yöntemini, bugün öğrendiğiniz takdirde  sık sık kullanmaz iseniz bir ay sonra akılda kalacak bir teknik değil.

Üniversitelerin kendi basımı,  Elektronik müh. bölümünun sayısal elektronikle ilgili kitaplarına gözatarsan bu konuyu bulursun. ITU basımlarında olduğunu kesin biliyorum.

(Yanlış hatırlamıyorsam Sayın Prof. Dervişoğlunun, 80 yılı civarı basımı.)

[DumrulBey]

Sanırım yanlış anlaşıldım. Ben bu yöntemi biliyorum ama üniversitede bize eksik öğrettiler daha doğrusu tam sadeleşmeyen durumlar söz konusu olduğunda ikinci bölüm yapılıyormuş. Verdiğim kaynakta bu ayrıntısı ile açıklanmış ama ben anlamıyorum. Anlayan ve anladığını anlatabilecek bir Allah'ın kulu yok mu?

[z]

Yanlıs anlasılmadın, ünversite basımları sarı saman kagıda basıldığı ve kar amacı gudulmediği için çok ucuz oluyor üstelik Türkçe.

Ordan okursun üstelik kitapda diğer sadeleştirme teknikleride detaylı olarak açıklanıyor.

[cozturk]

Lazım olur mu bilmiyorum isterseniz bir bakın belki de programın daha kapsaplı yeni versiyonu filan vardır.
4x4 Karnaugh Map Minimizer v1.0

http://www.programmersheaven.com/zone13/cat552/
Aslında ben bu karno diyagramlarının gerçekten kullanılmasını gerektiren bir uygulama olup olmadığını çok merak ediyorum. bu kadar çok kapıyı barındıran IC almak yerine bir pic al tak demek geliyor insanın içinden. Yinede  merak ediyorum. pratik bir değeri varsa öğrenmek isterim.

[z]

Aslında ben bu karno diyagramlarının gerçekten kullanılmasını gerektiren bir uygulama olup olmadığını çok merak ediyorum. bu kadar çok kapıyı barındıran IC almak yerine bir pic al tak demek geliyor insanın içinden. Yinede  merak ediyorum. pratik bir değeri varsa öğrenmek isterim.

Karno diagramı 4 değişkenden sonra pratikliğini kaybediyor.

İşlemcilerle de ancak düşük hızlı devrelere  çözümler üretebiliriz. Örneğin VGA ekran kartını işlemci ile gerçekleştirmek imkansız.

Bu gibi durumlarda mecburen lojik devrelere yönelmek durumundayız.
Küçük devreleri kapıılarla yapmak anlamsız hazır fonksiyonel çiplerle yapabilirsiniz peki ya çok büyükleri ne yapacağız?

Burada imdadımıza programlanabilir lojik aileler yetişiyor.

Bu çiplerle çalışırken minimize teknikleri gerekiyor çünkü sınırlı kapı ve FF sözkonusu. Kullandığınız yazılıma optimize işleminde alan optimizasyonu  kullan derseniz, yazılım sizin için karmaşık işleri kendisi yapıyor.

Tekniklerden birisi de bilgisayar yazılımına çok uygun olan Quine-McCluskey yöntemi.

[alayli]

Bu konuda bunalmis'a katılıyorum. Bu tarz hazır entegreler var. Geçmişte PAL diye anılan sonradan ben tanıştığımda PLD (Programmable Logic Device) adı verilen bir takım chipler var. Bir aralar bunların basit olanlarıyla bir kaç uygulama yapmıştım. Şu an daha gelişmişlerinin çıktığını duydum. İsimleri de değişmiş yine galiba...

Aşağıda Altera'nın MAX7000 serisine ait özellikleri ve pdf linkini bulabilirsiniz.

http://www.altera.com/literature/ds/m7000.pdf

Open-drain output option in MAX 7000S devices
■ Programmable macrocell flipflops with individual clear, preset,
clock, and clock enable controls
■ Programmable power-saving mode for a reduction of over 50% in
each macrocell
■ Configurable expander product-term distribution, allowing up to
32 product terms per macrocell
■ 44 to 208 pins available in plastic J-lead chip carrier (PLCC), ceramic
pin-grid array (PGA), plastic quad flat pack (PQFP), power quad flat
pack (RQFP), and 1.0-mm thin quad flat pack (TQFP) packages
■ Programmable security bit for protection of proprietary designs
■ 3.3-V or 5.0-V operation
– MultiVoltTM I/O interface operation, allowing devices to
interface with 3.3-V or 5.0-V devices (MultiVolt I/O operation is
not available in 44-pin packages)
– Pin compatible with low-voltage MAX 7000A and MAX 7000B
devices
■ Enhanced features available in MAX 7000E and MAX 7000S devices
– Six pin- or logic-driven output enable signals
– Two global clock signals with optional inversion
– Enhanced interconnect resources for improved routability
– Fast input setup times provided by a dedicated path from I/O
pin to macrocell registers
– Programmable output slew-rate control
■ Software design support and automatic place-and-route provided by
Altera's development system for Windows-based PCs and Sun
SPARCstation, and HP 9000 Series 700/800 workstations

[cozturk]

Örneğin VGA ekran kartını işlemci ile gerçekleştirmek imkansız.

belki dsp IC ler ile olur. hatta iddialara göre dsPICler dsplerin hızında ve PIC fiyatındaymış.

[z]

VGA mumkun değil hocam. Ama basit bir CRTC yaparsin.
VGA'yi kompleks bir lojik oldugu icin ornek vermisrtim.

Daha basit bit ornek, fazla değil  5-10Mhz lik bir islemcinin adres
decoderi olabilir. Zamanlamanin cok kritik oldugu  buna karsin cok az elemanli basit bir lojik.

Hatirlarsiniz, PIC in 8 bacakli islemcileri ciktiginda yavas devrelerinizde glue logic olarak kullanabilirsiniz diye reklam yapiliyordu.

Glue logic, devrenize kucuk bir lojik devre gerekti fazla yeriniz yok, al yapistir cinsinden minik lojiklere verilen ad.

[DumrulBey]

Lazım olur mu bilmiyorum isterseniz bir bakın belki de programın daha kapsaplı yeni versiyonu filan vardır.
4x4 Karnaugh Map Minimizer v1.0
(Resim gizlendi görmek için tıklayın.)
http://www.programmersheaven.com/zone13/cat552

Korkarım o programın arka tarafında "Quine-McCluskey Method" algoritması çalışıyor. Ben de 1.2 sürüm var ve fazladan terimleri dahil ediyor. Aşağıdaki örneği programa uygularsanız ne demek istediğimiz daha iyi anlayabilirsiniz:

- f(ABCD) =Σ(0, 1, 3, 7, 11, 15) terimlerini en sade biçimde sadeleştirmeye kalktığımızda, tablo yöntemi olarak da adlandırdığımız Quine-McCluskey yöntemi tam sade sonucu vermiyor! Halbu ki hocalarımız bize bu yöntemin en sade sonucu vereceği garantisi vermişlerdir. Bir pazar günü (16 Haziran 2002), sınavım için yaptığım ön çalışma sonucu bunu farkettim ve o günden beri araştırmaktayım.



Yukarıdaki resimde olayı tüm çıplaklığı ile görmektesiniz. Quine-McCluskey tablosunda kırmızı renkteki terimler fazlalık yani olmaması gerekiyor. Bu Karnaugh haritası ile görmekteyiz. İsterseniz daha basit olan Boolean Cebiri ile çözeyim:

Boolean Çözümü:
f(ABCD) = A'B'C'D' + A'B'C'D + A'B'C D + A'B C D + A B' C D + A B C D
f(ABCD) = A'B'C'(D'+D) + A'C D (B'+B) + A C D (B'+B)
f(ABCD) = A'B'C' + C D (A'+A)
f(ABCD) = A'B'C' + CD
Not: Parantez içindeki ifadeler 1'e eşittir ve çarpımda etkisiz elemandır. Harflerin sağ üst köşesindeki tırnak değili (not logic) olarak algılanmalıdır.

İşte bu yöntemde de doğru sonucu buldum. O zaman hocalar "en sade sonucu verir" dedikleri söylemlerinde yanılıyor olabilir mi? Yoksa yöntemin ikinci bölümüne ihtiyaç duyuyor olabilir miyiz? Aslında ben tablonun sonucuna bakarken kapsanan terimleri (minimum term) karşılaştırarak fazlalıkları kafamda eleyebiliyorum. Ancak bunu algoritmaya nasıl dahil edeceğiz veya ilk mesajında adresini verdiğim sunumdaki ikinci bölüm (sayfa 79) nasıl yapılıyor?

Kısa Bilgi: Türkiye'de "tablo yöntemi" olarak ifade ettiğimiz yöntemi, Willard van Orman Quine (1908-2000) 50'li yıllarda kurallarını saptamış. Sonradan Edward J. McCluskey geliştirdiği için "Quine-McCluskey Method" olarak anılır olmuştur. Başka yöntemler olmasına rağmen bilgisayar algoritmaları için en uygunu olduğundan günümüzde tercih edilir.

Sevgiler, saygılar...