نقشه کارنو

از ویکی‌پدیا، دانشنامهٔ آزاد
نمونه‌ای از یک جدول کارنو

جدول کارنو روشی است برای ساده‌سازی توابع جبر بولی که به وسیلهٔ موریس کارنو در سال ۱۹۵۳ ارائه شد. این روش کامل شده دیاگرام ویچ است که در سال ۱۹۵۲ توسط ادوارد ویچ ارائه شده بود. جدول کارنو نیاز به محاسبات طولانی را کاهش داده و به مشخص کردن و حذف کردن سریع وضعیت رقابتی کمک می‌کند.

مقادیر بولی از جدول ارزش و با توجه به اصول کد گری به جدول کارنو انتقال می‌یابند. داده‌ها در جدول کارنو که ۲n سلول دارد چیده می‌شوند و مینترم‌ها بر اساس اصول جبر بول ساخته می‌شوند.

نقشه کارنو نموداری از مربع‌ها است که هر مربع یک مینترم را نمایش می‌دهد. به کمک این مربع‌ها می‌توان یک تابع بول را نمایش داد. نقشه کارنو به چند حالت مختلف دو، سه، چهار و گاهی پنج متغیره نمایش می‌یابد. نقشه کارنوی n متغیره، دارای 2n خانه است که هر خانه یک مینترم را نمایش می‌دهد. بعد از اینکه مینترم‌های یک تابع را در نقشه کارنو علامت‌گذاری کردیم، می‌توانیم مربع‌های همجوار را با هم ساده کنیم. در شکل زیر یک نقشه ۴ متغیره که ۱۶ مربع یا خانه دارد نمایش داده شده‌است:

K-map minterms A.svg

برای شماره‌گذاری خانه‌ها از کد گری استفاده شده‌است. چرا که در کد گری، هر عدد با اعداد ماقبل و مابعد خود تنها در یک رقم تفاوت دارد و این خاصیت به ساده کردن توابع بول کمک می‌کند.

مثال[ویرایش]

مثال زیر یک تابع ساده نشده جبر بول را با متغیرهای بولی A،B،C،D نشان می‌دهد.

جدول صحت تابع به صورت زیر ساخته می‌شود:

#
۰ ۰ ۰ ۰ ۰ ۰
۱ ۰ ۰ ۰ ۱ ۰
۲ ۰ ۰ ۱ ۰ ۰
۳ ۰ ۰ ۱ ۱ ۰
۴ ۰ ۱ ۰ ۰ ۰
۵ ۰ ۱ ۰ ۱ ۰
۶ ۰ ۱ ۱ ۰ ۱
۷ ۰ ۱ ۱ ۱ ۰
۸ ۱ ۰ ۰ ۰ ۱
۹ ۱ ۰ ۰ ۱ ۱
۱۰ ۱ ۰ ۱ ۰ ۱
۱۱ ۱ ۰ ۱ ۱ ۱
۱۲ ۱ ۱ ۰ ۰ ۱
۱۳ ۱ ۱ ۰ ۱ ۱
۱۴ ۱ ۱ ۱ ۰ ۱
۱۵ ۱ ۱ ۱ ۱ ۰

تابع فوق با دو نماد گذاری در زیر نمایش داده شده است. در اولی ها مینترم نامیده می شوند که شماره سطر هایی که در جدول درستی مقدار یک دارند را نمایش می دهند و در نماد گذاری دوم ها ماکسترم هستند و نمایانگر شماره سطر هایی که در جدول درستی مقدار صفر دارند هستند.


جدول کارنو[ویرایش]

K-map 6,8,9,10,11,12,13,14.svg

در مثال بالا، برای جدول کارنو چهار متغیره 16 حالت وجود دارد و در نتیجه جدول درستی آن 16 سطر دارد. جدول کارنو در یک صفحه مشبک 4*4 تنظیم می شود.

در این جدول شماره گذاری حاشیه جدول به ترتیب کد گری است و نه ترتیب باینری اعداد. اینگونه شماره گذاری باعث می شود اعداد مجاور در حاشیه جدول تنها در یک بیت تفاوت داشته باشند. هر سلول جدول حاوی یک عدد باینری است که خروجی تابع به ازای ترکیب خاصی از ورودی ها را مشخص می کند.

بعد از اینکه جدول کارنو ساخته شد از آن برای ساده کردن جدول درستی استفاده می شود. با دسته بندی اعداد 1 مجاور در جدول می توان ساده سازی را انجام داد. دسته بندی ها باید مستطیلی باشند به طوری که مساحت آن ها توانی از دو باشد. این گرو ها باید تا حد امکان بزرگ باشند و حاوی صفر نباشند. ممکن است گروه ها همپوشانی داشته باشند. گروه بندی بهینه در مثال زیر با گروه های سبز و قرمز و آبی مشخص شده اند و گروه قرمز و سبز همپوشانی دارند. گروه قرمز به شکل یک مربع 2*2 و گروه سبز یک مستطیل 1*4 است. ناحیه همپوشانی نیز با رنگ قهوه ای مشخص شده است.

برای توصیف خروجی جدول از نماد گذاری خاصی استفاده می شود. مثلا AD به ناحیه 2*2 اشاره می کند همزمان A و D ارزش درست دارند (خانه های 13, 9, 15, 11). مشابها 'AD یعنی ناحیه ای که A ارزش درست و D ارزش نادرست دارند.

خانه های جدول به شکل یک چنبره با هم همسایه اند. بنابراین لبه های راست و چپ با هم و لبه های بالا و پایین جدول با یکدیگر همسایه اند. همچنین چهار گوشه جدول نیز با یکدیگر همسایه اند.

Karnaugh6.gif

شرح راه حل مثال:[ویرایش]

وقتی جدول کارنو ساخته شد و دسته بندی صورت گرفت باید عبارت جبری متناظر با هر دسته نوشته شود. به طور مثال برای گروه قرمز:

  • چون در سراسر گروه بندی قرمز ارزش A یک است بنابراین عبارت جبری متناظر این گروه باید شامل A باشد.
  • از طرف دیگر B تغییر وضعیت می دهد بنابراین نباید در عبارت جبری گروه قرمز بیاید.
  • C تغییر وضعیت نمی دهد و همواره صفر است. بنابراین عبارت جبری گروه قرمز شامل 'C است.
  • D تغییرمی کند پس مشمول نمی شود.


بنابراین اولین مینترم در جمع حاصل ضرب ها 'AC است. مشابها برای برای گروه بندی های سبز و آبی عبارت جبری بدست می آید:

  • سلول‌های آبی: 'BCD
  • سلول‌های قهوه‌ای و سبز: 'AB
  • سلول‌های قرمز و قهوه ای: 'AC

نتیجه ترکیب گروه ها مانند روبرو است: .


می توان با استفاده از اصول و اتحادهای جبر بول عبارت ساده شده را اثبات کرد:

وارون[ویرایش]

وارون کردن یک تابع به طور مشابه، با دسته بندی صفرها در جدول انجام می شود. این سه دسته بندی در شکل با رنگ خاکستری و با رنگ حاشیه متفاوت مشخص شده اند :

K-map 6,8,9,10,11,12,13,14.svg
  • قهوه ای: 'A'B
  • طلایی: 'A'C
  • آبی: BCD

که این تابع وارون را نتیجه می دهد:

از طریق قانون دمورگان، حاصل جمع حاصل ضرب ها مشخص می شود:

حالات بی تفاوت[ویرایش]

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

K-map 6,8,9,10,11,12,13,14 don't care.svg

مثال سمت چپ مشابه مثال قبلی می باشد با این تفاوت که مقدار f(1,1,1,1) بی تفاوت فرض شده است. این باعث می شود دسته قرمز بزرگتر شود و دسته سبز حذف شود. این کار تابع بهینه جدیدی را نتیجه می دهد:

توجه کنید که عبارت اول تنها A است و نه 'A'C. در این صورت، حالت بدون تفاوت موجب شده عبارتی که از دسته سبز نتیجه می شد، حذف شود و عبارت حاصل از دسته بندی قرمز ساده تر و حالت رقابتی بخش زرد حذف شود. ساده شده تابع وارون نیز به شکل زیر است:


نقشه کارنو دو متغیره[ویرایش]

در زیر تمام نقشه های کارنو دو متغیره 2*2 با مینترم ها و تابع ساده شده آمده است:


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