Quine-McCluskey algoritması
Asal implikants yöntemi olarak da bilinen Quine–McCluskey algoritması (QMA), 1952'de Willard V. Quine tarafından geliştirilen ve 1956'da Edward J. McCluskey tarafından genişletilen Boole işlevlerinin minimizasyonu için kullanılan bir yöntemdir.[1][2][3] Genel bir ilke olarak bu yaklaşım, mantıkçı Hugh McColl tarafından 1878'de gösterilmişti.[4][5] 1937'de Archie Blake tarafından[5][6] kanıtlandı ve yeniden keşfedildi. 1954'te Edward W. Samson ve Burton E. Mills ve 1955'te Raymond J. Nelson.[7] Yine 1955'te Paul W. Abrahams ve John G. Nordahl[8] ile Albert A. Mullin ve Wayne G. Kellner yöntemin ondalık bir varyantını önerdiler.[9][10]
Quine–McCluskey algoritması, işlevsel olarak Karno haritasıyla aynıdır, ancak tablo biçimi bilgisayar algoritmalarında kullanım için daha verimli hale getirir ve bir Boole işlevinin minimum biçimine ulaşıldığını kontrol etmek için deterministik bir yol sağlar. Bazen tablolama yöntemi olarak da adlandırılır.
Yöntem iki adımı içerir:
- Fonksiyonun tüm asal çarpanları bulunur.
- Bu asal çarpanları, fonksiyonun temel asal etkilerini ayrıca fonksiyonu kapsamak için gerekli olan diğer asal çarpanları bulmak için bir asal çarpanlar tablosu kullanılır.
Örnek değiştir
1. Adım: Asal çarpanların bulunması değiştir
İlk olarak, fonksiyonu bir tablo olarak yazıyoruz.
| A | B | C | D | F | |
|---|---|---|---|---|---|
| m0 | 0 | 0 | 0 | 0 | 0 |
| m1 | 0 | 0 | 0 | 1 | 0 |
| m2 | 0 | 0 | 1 | 0 | 0 |
| m3 | 0 | 0 | 1 | 1 | 0 |
| m4 | 0 | 1 | 0 | 0 | 1 |
| m5 | 0 | 1 | 0 | 1 | 0 |
| m6 | 0 | 1 | 1 | 0 | 0 |
| m7 | 0 | 1 | 1 | 1 | 0 |
| m8 | 1 | 0 | 0 | 0 | 1 |
| m9 | 1 | 0 | 0 | 1 | x |
| m10 | 1 | 0 | 1 | 0 | 1 |
| m11 | 1 | 0 | 1 | 1 | 1 |
| m12 | 1 | 1 | 0 | 0 | 1 |
| m13 | 1 | 1 | 0 | 1 | 0 |
| m14 | 1 | 1 | 1 | 0 | x |
| m15 | 1 | 1 | 1 | 1 | 1 |
Bu tablodan çarpımların kanonik toplamını, fonksiyonun bir olarak değerlendirdiği mintermleri (önemsiz terimleri dışarıda bırakarak) toplayarak kolayca oluşturabilirsiniz:
fA,B,C,D=A'BCD' + ABC'D' + AB'CD' + ABC'D + ABC'D' + ABCD
Bu nedenle, optimize etmek için, bir olarak değerlendirilen tüm mintermler önce bir minterm tablosuna yerleştirilir. Önemsiz terimler de bu tabloya eklenir (adlar parantez içindedir), böylece mintermlerle birleştirilebilirler:
| 1lerin
sayısı |
Minterm | İkili Gösterimi |
|---|---|---|
| 1 | m4 | 0100 |
| m8 | 1000 | |
| 2 | (m9) | 1001 |
| m10 | 1010 | |
| m12 | 1100 | |
| 3 | m11 | 1011 |
| (m14) | 1110 | |
| 4 | m15 | 1111 |
Bu noktada mintermleri diğer mintermlerle birleştirmeye başlanabilir. İki terim yalnızca tek bir basamakla farklılık gösteriyorsa, o basamak, basamağın önemli olmadığını belirten bir tire ile değiştirilebilir. Artık birleştirilemeyecek terimler bir yıldız (*) ile işaretlenmiştir. Örneğin 1000 ve 1001, 100- verecek şekilde birleştirilebilir; bu, her iki mintermin de ilk hanenin 1 ve sonraki ikisinin 0 olduğunu ima ettiğini gösterir.
| 1lerin
sayısı |
Minterm | 0-küp | 2. Boyut etkileri | |
|---|---|---|---|---|
| 1 | m4 | 0100 | m(4,12) | -100* |
| m8 | 1000 | m(8,9) | 100- | |
| - | - | m(8,10) | 10-0 | |
| - | - | m(8,12) | 1-00 | |
| 2 | m9 | 1001 | m(9,11) | 10-1 |
| m10 | 1010 | m(10,11) | 101- | |
| - | - | m(10,14) | 1-10 | |
| m12 | 1100 | m(12,14) | 11-0 | |
| 3 | m11 | 1011 | m(11,15) | 1-11 |
| m14 | 1110 | m(14,15) | 111- | |
| 4 | m15 | 1111 | - | |
Boyut 2'den Boyut 4'e geçerken - üçüncü bir bit değeri olarak ele alın. Örneğin, -110 ve -100, -1-0'ı vermek üzere birleştirilebilir, ca -110 ve -11-'in -11- vermesi gibi, ancak -110 ve 011- olamaz çünkü -110, 1110 tarafından ima edilirken 011- değil. (Püf Noktası: İlkini eşleştirin.)
| 1lerin
sayısı |
minterm | 0-küp | 2. Boyut etkileri | 4. Boyut etkileri | ||
|---|---|---|---|---|---|---|
| 1 | m4 | 0100 | m(4,12) | -100* | m(8,9,10,11) | 10--* |
| m8 | 1000 | m(8,9) | 100- | m(8,10,12,14) | 1--0* | |
| - | - | m(8,10) | 10-0 | - | ||
| - | - | m(8,12) | 1-00 | - | ||
| 2 | m9 | 1001 | m(9,11) | 10-1 | m(10,11,14,15) | 1-1-* |
| m10 | 1010 | m(10,11) | 101- | - | ||
| - | - | m(10,14) | 1-10 | - | ||
| m12 | 1100 | m(12,14) | 11-0 | - | ||
| 3 | m11 | 1011 | m(11,15) | 1-11 | - | |
| m14 | 1110 | m(14,15) | 111- | - | ||
| 4 | m15 | 1111 | - | - | ||
Not: Genel olarak bu işleme daha fazla terim birleştirilemeyecek duruma gelene kadar devam edilmelidir. Bu örnekteki terimlerin hiçbiri daha fazla birleştirilemez.
2. Adım değiştir
Terimlerin hiçbiri bundan daha fazla birleştirilemez, bu nedenle bu noktada bir asal dolaylı tablo oluşturuyoruz. Kenar boyunca, henüz oluşturulmuş olan asal çıkarımlar gider ve üst kısım boyunca daha önce belirtilen mintermler gider. Önemsiz terimler en üste yerleştirilmemiştir - gerekli girdiler olmadıkları için bu bölümden çıkarılmıştır.
Temel asal çıkarımları bulmak için en üst sıra boyunca ilerliyoruz. Sadece bir "✓" içeren sütunları aramamız gerekiyor. Bir sütunda yalnızca bir "✓" varsa, bu, minterm'in yalnızca bir asal dolaylı tarafından kapsanabileceği anlamına gelir. Örneğin: ilk sütunda minterm 4 ile yalnızca bir "✓" vardır.4 8 10 11 12 15 ⇒ A B C D Şablon:Ts | m(4,12)* 
⇒ - 1 0 0 Şablon:Ts | m(8,9,10,11) ⇒ 1 0 - - Şablon:Ts | m(8,10,12,14) ⇒ 1 - - 0 Şablon:Ts | m(10,11,14,15)* ⇒ 1 - 1 -
- Bu, m(4,12)'nin gerekli olduğu anlamına gelir. Bu yüzden yanına bir yıldız koyuyoruz. Minterm 15'te de sadece bir "✓" vardır, dolayısıyla m(10,11,14,15) de esastır. Artık bir "✓" içeren tüm sütunlar kapsanmıştır.
- İkinci asal implikant üçüncü ve dördüncü tarafından "kapsanabilir" ve üçüncü asal implikeant ikinci ve birinci tarafından "kapsanabilir" bu nedenle hiçbiri zorunlu değildir. Bir asal implikant gerekliyse, beklendiği gibi, onu minimize edilmiş boole denklemine dahil etmek gerekir. Bazı durumlarda, temel asal çıkarımlar tüm mintermleri kapsamaz, bu durumda çizelge indirgemesi için ek prosedürler kullanılabilir. En basit "ek prosedür" deneme yanılma yöntemidir, ancak daha sistematik bir yol Petrick'in yöntemidir. Mevcut örnekte, temel asal çıkarımlar tüm mintermleri işlemez, bu nedenle, bu durumda, temel çıkarımlar, bir denklem elde etmek için iki temel olmayanlardan biriyle birleştirilebilir:
- fA,B,C,D=BC'D' + AB' + AC
- veya
- fA,B,C,D=BC'D' + AD' + AC
- Bu son denklemlerin her ikisi de orijinal denkleme işlevsel olarak eşdeğerdir:
- fA,B,C,D = A'BC'D' + AB'C'D' + AB'C'D + AB'CD' + AB'CD + ABC'D' + ABCD' + ABCD.
Kaynakça değiştir
- ^ Quine, W. V. (1 Ekim 1952). "The Problem of Simplifying Truth Functions". The American Mathematical Monthly. 59 (8): 521-531. doi:10.1080/00029890.1952.11988183. ISSN 0002-9890.
- ^ Quine, W. V. (1 Kasım 1955). "A Way to Simplify Truth Functions". The American Mathematical Monthly. 62 (9): 627-631. doi:10.1080/00029890.1955.11988710. ISSN 0002-9890.
- ^ McCluskey, E. J. (Kasım 1956). "Minimization of Boolean functions". The Bell System Technical Journal. 35 (6): 1417-1444. doi:10.1002/j.1538-7305.1956.tb03835.x. ISSN 0005-8580. 24 Haziran 2021 tarihinde kaynağından arşivlendi. Erişim tarihi: 21 Haziran 2021.
- ^ McColl, Hugh (1878). "The Calculus of Equivalent Statements (Third Paper)". Proceedings of the London Mathematical Society (İngilizce). s1-10 (1): 16-28. doi:10.1112/plms/s1-10.1.16. ISSN 1460-244X. 24 Haziran 2021 tarihinde kaynağından arşivlendi. Erişim tarihi: 21 Haziran 2021.
- ^ a b Brown, Frank Markham (1 Kasım 2010). "McColl and Minimization". History and Philosophy of Logic. 31 (4): 337-348. doi:10.1080/01445340.2010.517387. ISSN 0144-5340.
- ^ Blake, Archie (Haziran 1938). "Corrections to Canonical expressions in Boolean algebra". The Journal of Symbolic Logic (İngilizce). 3 (2): 112-113. doi:10.2307/2267595. ISSN 0022-4812. 25 Haziran 2021 tarihinde kaynağından arşivlendi. Erişim tarihi: 21 Haziran 2021.
- ^ Nelson, Raymond J. (Mart 1955). "Simplest normal truth functions". The Journal of Symbolic Logic (İngilizce). 20 (2): 105-108. doi:10.2307/2266893. ISSN 0022-4812. 25 Haziran 2021 tarihinde kaynağından arşivlendi. Erişim tarihi: 21 Haziran 2021.
- ^ home, Jellison Funeral. "Obituary for John "Jack" G Nordahl". Obituary for John "Jack" G Nordahl (İngilizce). 5 Mayıs 2020 tarihinde kaynağından arşivlendi. Erişim tarihi: 21 Haziran 2021.
- ^ Fielder, Daniel C. (Aralık 1966). "Classroom Reduction of Boolean Functions". IEEE Transactions on Education. 9 (4): 202-205. doi:10.1109/TE.1966.4321989. ISSN 1557-9638. 24 Haziran 2021 tarihinde kaynağından arşivlendi. Erişim tarihi: 21 Haziran 2021.
- ^ Majumder, Alak; Chowdhury, Barnali; Mondai, Abir J; Jain, Kunj (Ocak 2015). "Investigation on Quine McCluskey method: A decimal manipulation based novel approach for the minimization of Boolean function". 2015 International Conference on Electronic Design, Computer Networks Automated Verification (EDCAV): 18-22. doi:10.1109/EDCAV.2015.7060531. 24 Haziran 2021 tarihinde kaynağından arşivlendi. Erişim tarihi: 21 Haziran 2021.