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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

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

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. \

منابع[ویرایش]

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

پیوندها[ویرایش]