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:

1. Fonksiyonun tüm asal çarpanları bulunur.
2. 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

1. Adım: Asal çarpanların bulunması

İ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:

f_A,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

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.

	4	8	10	11	12	15	⇒	A	B	C	D
m(4,12)*							⇒	-	1	0	0
m(8,9,10,11)							⇒	1	0	-	-
m(8,10,12,14)							⇒	1	-	-	0
m(10,11,14,15)*							⇒	1	-	1	-

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.

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:

f_A,B,C,D=BC'D' + AB' + AC

veya

f_A,B,C,D=BC'D' + AD' + AC

Bu son denklemlerin her ikisi de orijinal denkleme işlevsel olarak eşdeğerdir:

f_A,B,C,D = A'BC'D' + AB'C'D' + AB'C'D + AB'CD' + AB'CD + ABC'D' + ABCD' + ABCD.