نقشه کارنو

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

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

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

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

K-map minterms A.svg

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

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

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

f(A, B, C, D) = \sum_{}(6, 8, 9, 10, 11, 12, 13, 14)

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

# A B C D f(A, B, C, D)
۰ ۰ ۰ ۰ ۰ ۰
۱ ۰ ۰ ۰ ۱ ۰
۲ ۰ ۰ ۱ ۰ ۰
۳ ۰ ۰ ۱ ۱ ۰
۴ ۰ ۱ ۰ ۰ ۰
۵ ۰ ۱ ۰ ۱ ۰
۶ ۰ ۱ ۱ ۰ ۱
۷ ۰ ۱ ۱ ۱ ۰
۸ ۱ ۰ ۰ ۰ ۱
۹ ۱ ۰ ۰ ۱ ۱
۱۰ ۱ ۰ ۱ ۰ ۱
۱۱ ۱ ۰ ۱ ۱ ۱
۱۲ ۱ ۱ ۰ ۰ ۱
۱۳ ۱ ۱ ۰ ۱ ۱
۱۴ ۱ ۱ ۱ ۰ ۱
۱۵ ۱ ۱ ۱ ۱ ۰
K-map 6,8,9,10,11,12,13,14.svg

متغیرها می‌توانند در ۱۶ حالت مختلف ترکیب شوند پس جدول ما ۱۶ سلول دارد. متناظر با مینترم‌هایی که تابع در آنها یک است، خانه‌های جدول را نیز مانند شکل یک می‌کنیم. مابقی خانه‌های جدول را نیز صفر قرار می‌دهیم. سپس باید سلول‌های جدول را به دسته‌های دوتایی، چهارتایی یا هشت تایی تقسیم کنیم. دقت کنید که فقط سلول‌هایی که همسایه هستند قابل انتخاب هستند. در ضمن سلول‌های بالایی با پایینی و سلول‌های راستی با چپی نیز همسایه هستند و قابل دسته بندی هستند. در این مثال سلول‌های قرمز و قهوه‌ای را می‌توان با هم دسته بندی کرد. اگر این عمل را انجام دهیم جواب نهایی ساده تر می‌شود ولی اجباری در این کار نیست.
پس از عملیات دسته بندی باید مینترم متناظر به هر دسته را بنویسیم که در این مثال:

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

سپس تابع بولی ساده شده را بر اساس حاصل جمع حاصل ضرب ها می نویسیم:
'f(a،b،c،d)=BCD' + AB' + AC

معادل‌های انگلیسی[ویرایش]

  1. Boolean Aljebra
  2. Maurice Karnaugh
  3. Edward Veitch
  4. Race Condition
  5. Truth Table
  6. Gray Code
  7. Minterm

نگارخانه[ویرایش]

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

  • مشارکت‌کنندگان ویکی‌پدیا، «Karnaugh map»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۲ژوئیه ۲۰۱۱).

اندیس