روش جدولبندی کویین – مک کلاسکی (ساده کردن توابع)

واضح آرشیو وب فارسی:فان پاتوق: روش کویین – مک کلاسکی (Q-M ) یک رهیافت جدولبندی برای می نیمم کردن توابع بولی است.
]7،6،5 [. روش Q-M دو مزیت اصلی کارنو دارد .

اول این که روشی سر راست است وبه توانایی طراح در تشخیص الگوها بر روی جدول کارنو بستگی ندارد .
دوم این که تعداد متغیرهای بیشتری را می توان با آن ساده کرد ، حال آنکه جدول کارنو عملاً به پنج یا شش متغیر محدود می شود .
در روش Q-M یک جستجوی خطی سامان یافته بر روی جملات می نیمم تابع صورت می گیرد
تا تمام ترکیبهای جملات می نیمم مجاور منطقی شناخته شوند . نشان خواهیم داد که این روش را می توان به توابع چند خروجی نیز تعمیم داد .
روش Q-M از فهرست جملات می نیمم n متغیری شروع می شود و به تربیت تمام شاملهای دارای n-1
متغیر ، شاملهای دارای n-2 متغیر ، و... به دست می آیند ، تا سرانجام تمام شاملهای اول مشخص شود .

چهار گام این فرایند در زیر بیان شده ومعنای دقیق هر گام طی مثالهای بعد از آن روشن می شود .

گام1. در یک ستون تمام جملات می نیمم تابعی را که باید ساده شود به صورت دودویی درج می کنیم .
این جملات را بر حسب تعداد بیتهای 1 نمایش دودویی شان دسته بندی می کنیم .
این دسته بندی تشخیص جملات می نیمم مجاور منطقی را ساده می کند ،
چون برای مجاورت منطقی دو جملۀ می نیمم باید تنها در یک حرف تفاوت داشته باشند ،
بنابراین نمایش دودویی یکی باید نسبت به دیگری یا یک 1 بیشتر یا یک 1 کمتر داشته باشد .
گام2. با جستجوی کامل گروه های مجاور جملات می نیمم مجاور را تشخیص دهید وآنها را در ستونی مشتمل بر شاملهای 1- n متغیره قرار دهید .
جملات می نیمم تر کیب شده را علامت بزنید . در نمایش دودویی هر شامل جدید به جای متغیر حذف شده خط تیره بگذارید .
این کار برای ستون جدید تکرار کرده ، با ترکیب شاملهای ( 1- n ) متغیره ستونی از شاملهای 2- n متغیره ترتیب دهید .
برای ستونهای جدید نیز همین کار را انجام دهید تا این که دیگر هیچ شاملی را نتوان ترکیب کرد .
تمام جملات علامت زده نشده شامل اول هستند ، زیرا در شامل بزرگتری ادغام نشده اند . نتیجۀ نهایی فهرستی از شاملهای اول تابع است .

گام3. جدولی از شاملهای اول ترتیب دهید ، که جملات می نیمم در جهت افقی وشاملهای اول درجهت عمودی آن درج شده باشد ،
هر جملۀ می نیممی که توسط یک شامل پوشانده می شود
با علامت × درمحل بر خورد سطر ( شامل ) وستون ( جملۀ می نیمم ) مشخص می شود .
گام4. حداقل از شاملهای اول پوشش جملات می نیمم تابع داده شده را برگزینید .

اکنون با یک مثال کامل این چهار گام را روشن می کنیم .
مثال 1: تابع زیر را به روش کویین مک کلاسکی ساده کنید .
( 15 ، 13 ، 12 ، 10 ، 9 ، 8 ، 7 ، 6 ، 5 ، 4 ، 2 ) E m = A ,B ,C ) ( f
شکل 1-1 جدول کارنوی این مثال را نشان می دهد . توصیه می کنیم خواننده از روش جدول کارنو به ساده این تابع بپردازد

تهیه کننده : لیلا شاه بیک

این صفحه را در گوگل محبوب کنید

[ارسال شده از: فان پاتوق]

[مشاهده در: www.funpatogh.com]

[تعداد بازديد از اين مطلب: 7671]