الگوریتم کوین مک کلاسکی

الگوریتم کوین مک کلاسکی روشی است که برای کمینه کردن توابع بولی توسط کوین و ادوارد مک کلاسکی ایجاد شد. این روش از لحاظ تابعی با جدول کارنو یکسان است. ولی حالت جدولی این روش را برای استفاده در الگوریتم‌های کامپیوتری کارآمد تر می‌کند. علاوه بر این، این روش به طور قطعی می‌تواند بیان کند که آیا به کمینه استفاده از توابع بولی رسیده‌ایم یا نه. این روش گاهی با روش جدولی نیز نام برده می‌شود.

این الگوریتم از ۲ قسمت تشکیل شده‌است:

1- یافتن تمامی دلالت کننده‌های نخستین(Prime Implicant)

۲- تمامی آن دلالت کننده‌ها را در جدول دلالت کننده‌های نخستین قرار دهیم تا دلالت کننده‌های ضروری را بیابیم.

پیچیدگی

اگر چه این الگوریتم در مقایسه با جدول کارنو برای داده‌های با بیشتر از ۴ متغیر، عملی تر است، این الگوریتم به دلیل این که مسئله ای که حل می‌کند ان پی سخت است، محدودیت دارد و زمان اجرایی آن به صورت نمایی رشد می‌کند. می‌توان نشان داد که برای تابعی با n متغیر، مقدار کران بالا برای دلالت کننده‌های نخستین برابر exp(3,n)/n است. به طور مثال اگر n=32 حدودا exp(10,15)*6.5 دلالت کنندهٔ نخستین خواهیم داشت.

مثال

مرحله اول: یافتن دلالت کننده‌های نخستین

کوچک کردن یک تابع دلخواه

$f(A,B,C,D) =\sum m(4,8,10,11,12,15) + d(9,14). \,$

	A	B	C	D		f
m0	۰	۰	۰	۰		۰
m1	۰	۰	۰	۱		۰
m2	۰	۰	۱	۰		۰
m3	۰	۰	۱	۱		۰
m4	۰	۱	۰	۰		۱
m5	۰	۱	۰	۱		۰
m6	۰	۱	۱	۰		۰
m7	۰	۱	۱	۱		۰
m8	۱	۰	۰	۰		۱
m9	۱	۰	۰	۱		x
m10	۱	۰	۱	۰		۱
m11	۱	۰	۱	۱		۱
m12	۱	۱	۰	۰		۱
m13	۱	۱	۰	۱		۰
m14	۱	۱	۱	۰		x
m15	۱	۱	۱	۱		۱

به سادگی می‌توان ساده شدهٔ عبارت بالا را با توجه به جدول بالا، با جمع زدن مین ترم‌ها(minterm) یافت. به نوعی که آن تابع به صورت یک عبارت واحد نشان داده می‌شود:

$f_{A,B,C,D} = A'BC'D' + AB'C'D' + AB'CD' + AB'CD + ABC'D' + ABCD.$

به طور قطع این عبارت ساده ترین حالت نیست و برای ساده کردن آن می‌بایست مین ترم‌ها را در جدول مربوطه قرار داد و همچنین ترم‌های غیر مهم نیز در این جدول قرار داد و سپس این دو را با یکدیگر ترکیب کرد:

تعداد ۱‌ها	مین ترم	نمایش در مبنای ۲
۱	m4	۰۱۰۰
	m8	۱۰۰۰
۲	m9	۱۰۰۱
	m10	۱۰۱۰
	m12	۱۱۰۰
۳	m11	۱۰۱۱
	m14	۱۱۱۰
۴	m15	۱۱۱۱

حال باید به ترکیب در جدول پرداخت. اگر دو مینترم فقط در یک رقم با یکدیگر تفاوت داشتند، آن دو را در هم ادغام کرده و جای رقم متفاوت، «-» را قرار می‌دهیم.

تعداد ۱‌ها	مین ترم	نمایش مبنای ۲	دلالت کنندهٔ به اندازه ۲	دلالت کنندهٔ به اندازه ۴
۱	m4	۰۱۰۰	m(4,12) -100*	m(8,9,10,11) 10--*
	m8	۱۰۰۰	m(8,9) 100-	m(8,10,12,14) 1--0*
--	--	--	m(8,10) 10-0	--
۲	m9	۱۰۰۱	m(8,12) 1-00	m(10,11,14,15) 1-1-*
	m10	۱۰۱۰	--	--
	m12	۱۱۰۰	m(9,11) 10-1	--
--	--	--	m(10,11) 101-	--
۳	m11	۱۰۱۱	m(10,14) 1-10	--
	m14	۱۱۱۰	m(12,14) 11-0	--
۴	m15	۱۱۱۱	m(11,15) 1-11	--
			m(14,15) 111-

مرحله دوم: جدول دلالت کننده‌های نخستین

تا به اینجا در جدولی که داشته‌ایم، دیگر نمی‌تون مین ترم‌ها را بیشتر از این با هم ترکیب کرد. پس در اینجا جدولی را برای دلالت کننده‌های نخستین ضروری درست می‌کنیم. در این جدول، از مین ترم‌هایی که در قبل داشتیم و آنها که ترکیب کرده‌ایم، استفاده می‌کنیم. در این قسمت ترم‌های غیر مهم را حذف می‌کنیم، چون اهمیتی ندارند.

۴

۸

۱۰

۱۱

۱۲

۱۵

=>

A

B

C

D

m(4,12)*

X

X

-۱۰۰

=>

-

۱

۰

۰

m(8,9,10,11)

X

X

X

۱۰--

=>

۱

۰

-

-

m(8,10,12,14)

X

X

X

۱--۰

=>

۱

-

-

۰

m(10,11,14,15)*

X

X

X

۱-۱-

=>

۱

-

۱

-

با توجه به جدول بالا می‌توان ۲ عبارت ساده را برای تابع مد نظر در نظر گرفت. هر دوی این نمایش‌ها درست هستند:

$f_{A,B,C,D} = BC'D' + AB' + AC \$

$f_{A,B,C,D} = BC'D' + AD' + AC. \$

این دو تابع ساده شده، در اصل همان تابع ابتدایی می‌باشند:

$f_{A,B,C,D} = A'BC'D' + AB'C'D' + AB'C'D + AB'CD' + AB'CD + ABC'D' + ABCD' + ABCD. \$

منابع

۱. نلسون، کتاب تحلیل و طراحی مدار‌های دیجیتال

پیوندها

• پیاده سازی الگوریتم کوین مک کلاسکی با جستجوی تمام راه حل‌ها.
• All دربارهٔ کوین مک کلاسکی.
• کوچک کنندهٔ جدول کارنو.
• ارائه‌ای بر الگوریتم کوین مک کلاسکی
• Python پیاده سازی
• پیاده سازی الگوریتم کوین مک کلاسکی
• مقاله اول و مقاله دوم
• بول‌های کوچک
• ماژول پرل
• برای مشاهدهٔ مثالی کامل با توضیحات مفصل به آدرس روبرو مراجعه فرمایید visit: http://www.cs.ualberta.ca/~amaral/courses/329/webslides/Topic5-QuineMcCluskey/sld024.htm