Mantık optimizasyonu - Logic optimization

Mantık optimizasyonu , bir veya daha fazla belirtilen kısıtlama altında belirtilen mantık devresinin eşdeğer bir temsilini bulma sürecidir . Bu işlem, dijital elektroniklerde ve Entegre devre tasarımında uygulanan bir mantık sentezinin bir parçasıdır .

Genel olarak devre, önceden tanımlanmış bir yanıt gecikmesini karşılayan minimum bir çip alanıyla sınırlıdır. Belirli bir devrenin mantık optimizasyonunun amacı , orijinal devre ile aynı değerleri değerlendiren en küçük mantık devresini elde etmektir . Aynı işleve sahip daha küçük devre daha ucuzdur, daha az yer kaplar, daha az güç tüketir , daha kısa gecikme süresine sahiptir ve beklenmeyen çapraz konuşma , gecikmeli sinyal işleme tehlikesi ve metalik yapıların nano ölçekli seviyesindeki diğer sorunları en aza indirir. bir üzerinde bir entegre devre .

Boole cebri açısından, karmaşık bir boole ifadesinin optimizasyonu, daha basit bir ifade bulma sürecidir ve bu, değerlendirme üzerine nihai olarak orijinal olanla aynı sonuçları üretecektir.

Motivasyon

Karmaşık bir devre (yani mantık kapıları gibi birçok elemana sahip bir devre) sahip olmanın sorunu , her elemanın uygulanmasında fiziksel yer kaplaması ve kendi içinde üretilmesi zaman ve paraya mal olmasıdır. Devre minimizasyonu, entegre devrelerdeki karmaşık mantık alanını azaltmak için kullanılan bir mantık optimizasyonu şekli olabilir .

Mantık sentezinin ortaya çıkmasıyla , elektronik tasarım otomasyonu (EDA) endüstrisinin karşılaştığı en büyük zorluklardan biri, verilen tasarım açıklamasının en basit devre temsilini bulmaktı. İken iki seviyeli mantık optimizasyonu uzun şeklinde var olmuş Quine-McCluskey algoritması daha sonra ardından Espresso sezgisel mantık asgarileştirir hızla ilerleyen yonga yoğunlukları ve geniş kabulü Donanım tanımlama dilleri devre tanımı için, mantık optimizasyonu resmileştirdi bugün olduğu gibi etki alanı.

yöntemler

Mantık devresi basitleştirme yöntemleri, boole ifadesi minimizasyonuna eşit derecede uygulanabilir .

sınıflandırma

Bugün, mantık optimizasyonu çeşitli kategorilere ayrılmıştır:

Devre temsiline dayalı

İki seviyeli mantık optimizasyonu

Çok seviyeli mantık optimizasyonu

Devre özelliklerine göre

Sıralı mantık optimizasyonu

Birleşimsel mantık optimizasyonu

Yürütme türüne göre

Grafiksel optimizasyon yöntemleri

Tablolu optimizasyon yöntemleri

Cebirsel optimizasyon yöntemleri

Grafik yöntemler

İki seviyeli mantık için grafik küçültme yöntemleri şunları içerir:

• Euler diyagramı (aka Euler dairesi ) (1768) Leonhard P. Euler (1707-1783) tarafından
• John Venn (1834–1923)tarafından hazırlanan Venn şeması (1880)
• Allan Marquand (1853–1924)tarafından Marquand diyagramı (1881)
• Howard H. Aiken (1900–1973) ve Martha L. Whitehouse tarafından hazırlanan Harvard küçültme tablosu (diğer adıyla Harvard şeması ) (1951)
• Ayrışma tablosu (1952), Robert L. Ashenhurst (1929–2009) ve Theodore Singer (1916–1991)
• Veitch tablosu (1952) Edward W. Veitch tarafından(1924–2013)
• Karnaugh haritası (1953) Maurice Karnaugh tarafından(1924–)
• Kontak kemikleri , kontak ızgaraları (1955) ve Antonín Svoboda (1907–1980) tarafından hazırlanan üçlü harita
• Grafik yöntemi (1957) Vadim Nikolaevich Roginskij [ Вадим Николаевич Рогинский ] (1913–1983)
• Händler diyagramı (aka Händler daire grafiği , Händler'scher Kreisgraph , Kreisgraph nach Händler , Händler-Kreisgraph , Händler-Diagramm , Minimisierungsgraph , M ⁿ grafiği ) (1958) Wolfgang Händler (1920–1998)
• Mahoney haritası aka M-haritası veya atama numaraları (1963) Matthew V. Mahoney tarafından
• Grafik yöntemi (1965) Herbert F. Kortum  [ de ] (1907–1979)
• Azaltılmış Karnaugh haritası (RKM)
• Hiperküp yöntemi (1982) Stamatios V. Kartalopoulos
• Minterm-halka haritası (MRM) veya Minterm-halka algoritması (1990) Thomas R. McCalla tarafından
• V diyagramı (2001), Jonathan Westphal (1951–)
• Paraboomig (2003), Shrish Verma ve Kiran D. Permar tarafından
• Luca Amarú, Pierre-Emmanuel Gaillardon ve Giovanni De Micheli tarafından hazırlanan çoğunluk-inverter grafiği (MIG) (2014)
• Pandit arsa (2017) tarafından Vedhas Pandit ve Björn W. Schuller (1975–)
• Eisa Alharbi tarafından hazırlanan doğruluk grafiği (2020)

Boole ifadesi minimizasyonu

Aşağıda listelenen aynı boole ifadesi minimizasyonu (basitleştirme) yöntemleri devre optimizasyonuna uygulanabilir.

Boole fonksiyonunun bir devre tarafından belirtildiği durumda (yani, mümkün olan minimum boyutta bir eşdeğer devre bulmak istiyoruz), sınırsız devre minimizasyon probleminin uzun süredir -tamamlanmış olduğu varsayıldı , sonuç olarak 2008'de kanıtlandı, ancak süreci kolaylaştıran Karnaugh haritaları ve Quine–McCluskey algoritması gibi etkili buluşsal yöntemler vardır . ${\displaystyle \Sigma _{2}^{P}}$

Boolean işlevi küçültme yöntemleri şunları içerir:

• Blake – Poretsky yöntemi
• Nelson yöntemi
• Quine–McCluskey algoritması
• cebirsel dönüşümler yöntemi
• Petrick'in yöntemi
• Roth yöntemi
• Kudielka yöntemi
• kuyu yöntemi
• Scheinman'ın ikili yöntemi
• EVET-HAYIR ve VEYA-DEĞİL tabanlarında işlevleri en aza indirme yöntemi (Schaeffer ve Pierce temeli)
• belirsiz katsayılar yöntemi
• hiperküp yöntemi
• fonksiyonel ayrıştırma yöntemi

Espresso buluşsal mantık küçültücü

İki seviyeli ve çok seviyeli temsiller

Devrelerin iki seviyeli bir devre temsili, SOP'ler ( ürünlerin toplamı ) açısından devrenin düzleştirilmiş görünümüne atıfta bulunurken - bu, tasarımın bir PLA uygulamasına daha uygundur - çok seviyeli bir temsil , daha fazla Devrenin keyfi olarak bağlanmış SOP'ler, POS'lar ( toplamların çarpımı ), çarpanlara ayrılmış form vb . açısından genel görünümü . Mantık optimizasyon algoritmaları genellikle yapısal (SOP'ler, çarpanlara ayrılmış form) veya işlevsel ( İkili karar diyagramları , ADD'ler ) temsili üzerinde çalışır. devrenin.

İki fonksiyonumuz varsa F ₁ ve F ₂ :

${\displaystyle F_{1}=AB+AC+AD,\,}$

${\displaystyle F_{2}=A'B+A'C+A'E.\,}$

Yukarıdaki 2 seviyeli gösterim, CMOS Rep'de altı ürün terimi ve 24 transistör alır.

Çok düzeyli işlevsel olarak eşdeğer bir temsil şöyle olabilir:

P = B + C .

F ₁ = AP + AD .

F ₂ = A'P + A'E .

Buradaki düzey sayısı 3 iken, B + C teriminin paylaşılması nedeniyle toplam ürün terimleri ve literal sayısı azalmaktadır.

Benzer şekilde, davranışları sırasıyla sonlu durum makine durum tabloları/şemaları veya Boole fonksiyonları ve ilişkileri ile tanımlanabilen sıralı ve kombinasyonel devreler arasında ayrım yaparız .

Örnek

Orijinal ve basitleştirilmiş örnek devre

Bir devreyi küçültmenin birçok yolu olsa da, bu, bir Boole işlevini en aza indiren (veya basitleştiren) bir örnektir. Devre tarafından gerçekleştirilen Boole işlevi, işlevin gerçekleştirildiği cebirsel ifadeyle doğrudan ilişkilidir. temsil etmek için kullanılan devreyi düşünün . Bu ifadede iki olumsuzlama, iki bağlaç ve bir ayırmanın kullanıldığı açıktır. Bu, devreyi kurmak için iki invertöre , iki AND geçidine ve bir OR geçidine ihtiyaç duyulacağı anlamına gelir . ${\displaystyle (A\kama {\bar {B}})\vee ({\bar {A}}\kama B)}$

Devre, Boole cebri yasaları uygulanarak veya sezgi kullanılarak basitleştirilebilir (en aza indirilebilir). Örnek , doğru olduğunda yanlış olduğunu ve bunun tersi olduğunu belirttiğinden, bunun basitçe şu anlama geldiği sonucuna varılabilir . Mantıksal kapılar açısından, eşitsizlik basitçe bir XOR kapısı (dışlayıcı veya) anlamına gelir . Bu nedenle, . O halde aşağıda gösterilen iki devre eşdeğerdir: ${\görüntüleme stili A}$${\görüntüleme stili B}$${\ Displaystyle A\neq B}$${\displaystyle (A\wedge {\bar {B}})\vee ({\bar {A}}\wedge B)\iff A\neq B}$

Sonucun doğruluğu bir doğruluk tablosu kullanılarak kontrol edilebilir .

Ayrıca bakınız

• İkili karar diyagramı (BDD)
• durumu umursama
• asıl ilgili
• Devre karmaşıklığı — devre karmaşıklığının tahmini üzerine
• Fonksiyon bileşimi
• fonksiyon ayrıştırma
• Kapı yetersiz kullanımı
• Harvard küçültme tablosu (Wikiversity) (Wikibooks)

Referanslar

daha fazla okuma

• Hwa, "Sherman" Hsuen Ren (Haziran 1974). "Bir Boole İfadesinin Asal Etkilerini Oluşturma Yöntemi" . Bilgisayarlarda IEEE İşlemleri . IEEE . C-23 (6): 637-641. doi : 10.1109/TC.1974.24.24003 . eISSN  1557-9956 . ISSN  0018-9340 . S2CID  10646917 . CD- ISSN  2326-3814 . 1F09 . Alındı 2020-05-12 ; Hwa, "Sherman" Hsuen Ren (Nisan 1973). Bir Boolean İfadesinin Asal Etkilerini Oluşturma Yöntemi . Basser Bilgisayar Bilimleri Bölümü , Sidney Üniversitesi . Teknik Rapor 82.
• Lind, Larry Frederick; Nelson, John Christopher Cunliffe (1977). Sıralı Sayısal Sistemlerin Analizi ve Tasarımı . Macmillan Basın . ISBN'si 0-33319266-4. [49] (146 sayfa)
• Ghosh, Debidas (Haziran 1977) [1977-01-21]. "Bir Boolean İfadesinin asal faktörlerini, Don't care kombinasyonunun dahil edilme olasılığı ile birleştirici normal formda üretme yöntemi" (PDF) . Teknoloji Dergisi . Matematik Bölümü, Bengal Mühendislik Koleji, Howrah, Hindistan. XXII (1). 2020-05-12 tarihinde orijinalinden arşivlendi (PDF) . 2020-05-12 alındı .
• De Micheli, Giovanni (1994). Sayısal Devrelerin Sentezi ve Optimizasyonu . McGraw-Hill . ISBN'si 0-07-016333-2. (NB. Bölüm 7-9, birleşimsel iki seviyeli, birleşimsel çok seviyeli ve sırasıyla sıralı devre optimizasyonunu kapsar.)
• Hachtel, Gary D.; Somenzi, Fabio (2006) [1996]. Mantık Sentezi ve Doğrulama Algoritmaları . Springer Bilim ve İş Medyası . ISBN'si 978-0-387-31005-3.
• Kohavi, Zvi; Jha, Niraj K. (2009). "4-6". Anahtarlama ve Sonlu Otomata Teorisi (3. baskı). Cambridge Üniversitesi Yayınları . ISBN'si 978-0-521-85748-2.
• Knuth, Donald Ervin (2010). "7.1.2: Boole Değerlendirmesi". Bilgisayar Programlama Sanatı . 4A . Addison-Wesley . s. 96–133. ISBN'si 978-0-201-03804-0.
• Rutenbar, Rob A. Çok seviyeli minimizasyon, Bölüm I: Modeller ve Yöntemler (PDF) (ders slaytları). Carnegie Mellon Üniversitesi (CMU). Ders 7. Orijinalinden 2018-01-15 tarihinde arşivlendi (PDF) . Alındı 2018-01-15 ; Rutenbar, Rob A. Çok seviyeli minimizasyon, Bölüm II: Küp/Kokernel Özü (PDF) (ders slaytları). Carnegie Mellon Üniversitesi (CMU). Ders 8. Orijinalinden 2018-01-15 tarihinde arşivlendi (PDF) . 2018-01-15 alındı .
• Tomaszewski, Sebastian P.; Çelik, Ilgaz Ü.; Antoniou, George E. (Aralık 2003) [2003-03-05, 2002-04-09]. "WWW tabanlı Boole işlevi minimizasyonu" (PDF) . Uluslararası Uygulamalı Matematik ve Bilgisayar Bilimleri Dergisi . 13 (4): 577-584. 2020-05-10 tarihinde orijinalinden arşivlendi (PDF) . 2020-05-10 alındı . [50] [51] (7 sayfa)
• Wilhelmi, İskender; Kudielka, Viktor; Deussen, Peter; Böhling, Karl Heinz ; Handler, Wolfgang ; Neander, Joachim (Ocak 1963) [1961-10-18]. Dorr, Johannes; Peschl, Ernst Ferdinand ; Unger, Heinz (ed.). 2. Colloquium über Schaltkreis- und Schaltwerk-Theorie - Vortragsauszüge vom 18. bis 20. Ekim 1961, Saarbrücken . Internationale Schriftenreihe zur Numerischen Mathematik [Uluslararası Sayısal Matematik Dizisi] (ISNM) (Almanca). 4 (1. baskının 2013-12-20 yeni baskısı). Institut für Angewandte Mathematik, Universität Saarbrücken , Rheinisch-Westfälisches Institut für Instrumentelle Mathematik: Springer Basel AG / Birkhäuser Verlag Basel . doi : 10.1007/978-3-0348-4156-6 . ISBN'si 978-3-0348-4081-1. 2020-04-15 alındı . (152 sayfa)
• Brayton, Robert King ; Rudell, Richard L.; Sangiovanni-Vincentelli, Alberto Luigi ; Wang, Albert R. (Aralık 1987). "MIS: Çok Düzeyli Mantık Optimizasyon Sistemi" . Tümleşik Devrelerin ve Sistemlerin Bilgisayar Destekli Tasarımına İlişkin IEEE İşlemleri . 6 (6): 1062–1081. doi : 10.1109/TCAD.1987.1270347 . (MIS) (20 sayfa)
• De Geus, Aart J .; Cohen, William W. (Temmuz-Ağustos 1985). "Birleşimsel Mantığı Optimize Etmek İçin Kural Tabanlı Bir Sistem" . IEEE Bilgisayarların Tasarımı ve Testi . 2 (4): 22–32. doi : 10.1109/MDT.1985.294719 . eISSN  1558-1918 . ISSN  0740-7475 . S2CID  46651690 . 2021-02-19 tarihinde kaynağından arşivlendi . 2021-02-19 alındı .(11 sayfa) [52] (SOKRATES)
• Khatri, Sunil P.; Gulati, Kanupria, ed. (2011). Mantık Sentezinde İleri Teknikler, Optimizasyonlar ve Uygulamalar (1 ed.). New York / Dordrecht / Heidelberg / Londra: Springer Science+Business Media, LLC . ISBN'si 978-1-4419-7517-1. (xxii+423+1 sayfa)
• Jesse, Jobst E. (Şubat 1972). Sunnyvale, California, ABD'de yazıldı. "Karnaugh Haritalarının Daha Verimli Kullanımı" . Bilgisayar Tasarımı . Cilt 11 hayır. 2. Concord, Massachusetts, ABD: Bilgisayar Tasarımı Yayıncılık Şirketi. s. 80–82. ISSN  0010-4566 . OCLC  828863003 . CODEN  CMPDA . (3 sayfa)
• Reusch, Bernd (Eylül 1975). "Alt Fonksiyonlardan Asal Etkilerin Oluşturulması ve Kaplama Problemine Birleştirici Bir Yaklaşım" . Bilgisayarlarda IEEE İşlemleri . IEEE . C-24 (9): 924-930. doi : 10.1109/TC.1975.224338 . eISSN  1557-9956 . ISSN  0018-9340 . S2CID  32090834 . CD- ISSN  2326-3814 . 2021-02-19 alındı . (7 sayfa)
• Dineley, RL (Nisan 1969). "Editöre" . Editöre Mektuplar. Bilgisayar Tasarımı . Cilt 8 hayır. 4. Concord, Massachusetts, ABD: Bilgisayar Tasarımı Yayıncılık Şirketi. P. 16. ISSN  0010-4566 . OCLC  828863003 . CODEN  CMPDA . P. 16: […] Maxterm tipi Boole ifadesinin Veitch diyagramını kullanarak sadeleştirilmesi için bir yöntem önermek istiyorum . Bildiğim kadarıyla, 1960 yılında Redstone Arsenal'deki Dijital Bilgisayarın Temelleri kursuna katılırken onu türetmiş olan yöntemin yaratıcısıyım . Çoğu metin , ayrı ayrı terimleri ayrı Veitch diyagramları üzerine çizerek ve sonra kesişmeleri veya "ve" işlevini keşfetmek için diyagramları üst üste bindirerek maxterm ( toplamların çarpımı ) türündeki ifadeyi basitleştirir . […] Burada sunulan yöntem, tüm terimlerin kolayca fark edilebilir "ve" ilişkisi ile tek bir diyagram üzerinde çizilmesine izin verir. […] İfadenin her toplam terimine bir sembol atanır. Bu sembol, terimin veya'd faktörlerinin her biri için Veitch'te çizilir. "ve" işlevi, herhangi bir kare veya 2 ⁿ bitişik karenin kombinasyonu , atanan tüm sembolleri içerdiğinde ortaya çıkar . Basit bir örnek açıklayacaktır. […] (A + BC) ^[1] (A + C) ^[2] = A + BC […] Saygılarımla, RL Dineley, Sperry Rand Corp.(1 sayfa) (Not. Schultz'un yukarıdaki mektubunda atıfta bulunulmuştur .)
• Perkowski, Marek A.; Grygiel, Stanislaw (1995-11-20). "6. Ayrışma Araştırmalarına Tarihsel Bakış". Fonksiyon Ayrışımına İlişkin Bir Literatür Taraması (PDF) . Sürüm IV. Fonksiyonel Ayrışma Grubu, Elektrik Mühendisliği Bölümü, Portland Üniversitesi, Portland, Oregon, ABD. CiteSeerX  10.1.1.64.1129 . Orijinalinden 2021-03-28 tarihinde arşivlendi (PDF) . 2021-03-28 alındı . (188 sayfa)
• Stanković, Radomir S.; Sasao, Tsutomu; Astola, Jaakko T. (Ağustos 2001). "Anahtarlama Teorisi ve Mantık Tasarımının İlk Yirmi Yılında Yayınlar" (PDF) . Tampere Uluslararası Sinyal İşleme Merkezi (TICSP) Serisi. Tampere Teknoloji Üniversitesi / TTKK, Monistamo, Finlandiya. ISSN  1456-2774 . S2CID  62319288 . # 14. Orijinalinden 2017-08-09 tarihinde arşivlendi (PDF) . 2021-03-28 alındı . (4+60 sayfa)