حل‌کننده نقشه کارنو (K-Map)

سادهسازی تابع بولی با نقشه کارنو

نقشه کارنو (K-Map) ترکیبهای ورودی را طوری کنار هم قرار میدهد که خانههای مجاور فقط در یک متغیر تفاوت داشته باشند. این چینش کمک میکند راحتتر ببینید کدام متغیرها در عبارت نهایی قابل حذف هستند.

این solver از توابع ۲، ۳، ۴ و ۵ متغیره پشتیبانی میکند. میتوانید از خود K-Map شروع کنید یا جدول درستی، عبارت بولی، مینترمها یا ماکسترمها را وارد کنید.

همه این روشها یک تابع را نشان میدهند. اگر مقداری را در یک بخش تغییر دهید، بخشهای دیگر هم بر اساس همان تابع بهروزرسانی میشوند.

مقادیر 0، 1 و X چه معنایی دارند؟

هر خانه میتواند یکی از این مقادیر را داشته باشد:

• 1 — تابع برای آن ترکیب ورودی درست است.
• 0 — تابع نادرست است.
• X — مقدار خروجی برای آن ترکیب اهمیتی ندارد.

X یک حالت don't-care است. اگر استفاده از آن باعث ایجاد گروه بزرگتر و عبارت سادهتر شود، میتوان آن را داخل گروه قرار داد. در غیر این صورت لازم نیست استفاده شود.

تبدیل جدول درستی به K-Map

جدول درستی همه ترکیبهای ورودی ممکن و خروجی مربوط به هر کدام را نشان میدهد.

نقشه کارنو همان اطلاعات را دارد، اما خانهها را با ترتیب Gray code میچیند. به همین دلیل دو خانه مجاور فقط در یک متغیر تفاوت دارند.

برای مثال:

A'B'

A'B

فقط B تغییر میکند.

پس این دو جمله را میتوان به:

A'

ساده کرد.

متغیری که داخل یک گروه تغییر میکند، در جمله سادهشده باقی نمیماند.

همین منطق برای گروههای بزرگتر هم استفاده میشود.

مینترم، ماکسترم و عبارت بولی

اگر مسئله مینترمها را بهصورت شماره داده باشد، لازم نیست هر خانه را جداگانه وارد کنید.

برای مثال:

Σm(1,3,5,7)

مینترمهایی را مشخص میکند که خروجی تابع در آنها 1 است.

همچنین:

ΠM(0,2,4,6)

ماکسترمهایی را نشان میدهد که خروجی آنها 0 است.

میتوانید یک عبارت بولی را هم مستقیماً وارد کنید.

Solver عبارت را برای همه ترکیبهای ورودی ارزیابی میکند و جدول درستی، K-Map، مینترمها و ماکسترمهای متناظر را میسازد.

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

قوانین گروهبندی در K-Map

اندازه یک گروه معتبر باید توان عدد دو باشد:

1, 2, 4, 8, 16

معمولاً هرچه گروه معتبر بزرگتر باشد، تعداد literalهای باقیمانده در جمله نهایی کمتر میشود.

لبههای نقشه کارنو نیز از نظر منطقی به هم متصل هستند.

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

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

گروهها میتوانند روی هم قرار بگیرند. اگر حضور یک خانه در بیش از یک گروه باعث سادهتر شدن تابع شود، این حالت کاملاً معتبر است.

Solver گروههای انتخابشده را مستقیماً روی K-Map نمایش میدهد.

تفاوت SOP و POS

در SOP (Sum of Products) سادهسازی بیشتر بر اساس خانههایی انجام میشود که خروجی آنها 1 است.

مثال:

A'B + BC

در POS (Product of Sums) از خانههایی استفاده میشود که خروجی آنها 0 است.

مثال:

(A + B')(B + C)

SOP همیشه کوتاهتر از POS نیست.

برای بعضی توابع، SOP سادهتر است و برای بعضی دیگر POS تعداد جمله یا literal کمتری دارد.

اگر صورت سؤال قالب خاصی تعیین نکرده باشد، میتوانید هر دو نتیجه را مقایسه کنید.

Quine-McCluskey و Petrick's Method

در K-Mapهای کوچک، معمولاً میتوان گروههای مناسب را با نگاه کردن پیدا کرد.

اما در توابع ۴ یا ۵ متغیره ممکن است چند پوشش معتبر مختلف وجود داشته باشد.

Solver از Quine-McCluskey برای پیدا کردن implicantها بهصورت منظم استفاده میکند.

Implicantی که دیگر نمیتوان آن را بزرگتر کرد، prime implicant است.

برخی prime implicantها ضروری هستند، چون مینترمی را پوشش میدهند که هیچ prime implicant دیگری آن را پوشش نمیدهد.

اگر بعد از انتخاب موارد ضروری هنوز چند راه برای تکمیل پوشش باقی بماند، Petrick's Method برای بررسی ترکیبهای باقیمانده استفاده میشود.

این روش در مسائلی مفید است که بهترین گروهبندی فقط با نگاه کردن به نقشه مشخص نیست.

K-Map برای ۲ تا ۵ متغیر

K-Map دو متغیره ۴ خانه دارد.

K-Map سه متغیره ۸ خانه دارد و مفهوم همسایگی لبههای مخالف را واضحتر نشان میدهد.

نقشه کارنو چهار متغیره ۱۶ خانه دارد و در تمرینهای منطق دیجیتال بسیار رایج است.

در حالت پنج متغیره، ۳۲ ترکیب ورودی وجود دارد. وقتی چند prime implicant یا حالت don't-care وجود داشته باشد، حل دستی میتواند دشوارتر شود.

Solver در تمام اندازههای پشتیبانیشده، K-Map، جدول درستی، عبارت، مینترم و ماکسترم را با یک تابع واحد هماهنگ نگه میدارد.

مدار منطقی و خروجی PDF

پس از سادهسازی، نتیجه را میتوان به شکل مدار منطقی هم مشاهده کرد.

این نمایش نشان میدهد که عبارت SOP یا POS چگونه با گیتهای AND، OR و NOT ساخته میشود.

همچنین میتوان تعداد جملهها، literalها و گیتها را بررسی کرد.

برای نگه داشتن راهحل، میتوانید K-Map، گروهها، مراحل و مدار را همراه هم به صورت PDF خروجی بگیرید.