Karnaugh Map چیست و چطور با آن مدار منطقی را ساده کنیم؟
وقتی یک عبارت Boolean کمی بزرگ میشود، سادهکردن آن با قوانین جبر Boolean میتواند حسابی وقتگیر شود. اینجاست که Karnaugh Map یا به اختصار K-Map به کمکمان میآید.
K-Map در واقع یک روش تصویری برای سادهکردن مدارهای منطقی است. بهجای اینکه فقط با AND، OR و قوانین Boolean کار کنیم، مقدارهای تابع را داخل یک جدول قرار میدهیم و الگوی 1ها را پیدا میکنیم.
ایده اصلی K-Map چیست؟
فرض کنید تابعی داریم که برای بعضی ترکیبهای ورودی خروجی 1 و برای بقیه خروجی 0 است. در K-Map، خانههایی که مقدارشان 1 است را کنار هم گروهبندی میکنیم.
هدف این است که بزرگترین گروه ممکن را تشکیل دهیم. هرچه گروه بزرگتر باشد، متغیرهای بیشتری حذف میشوند و عبارت Boolean سادهتر خواهد شد.
اندازه گروهها باید توان ۲ باشد:
1 → 2 → 4 → 8 → 16
یک نکته مهم: ترتیب خانهها معمولی نیست!
یکی از اشتباههای رایج در K-Map این است که متغیرها را به ترتیب Binary قرار دهیم. ترتیب درست بر اساس Gray Code است:
00 → 01 → 11 → 10
دلیلش این است که بین هر دو خانه مجاور فقط یک متغیر تغییر کند. همین ویژگی اساس سادهسازی K-Map است.
مثال ۱: K-Map دو متغیره
ابتدا یک مثال خیلی ساده داشته باشیم:
F(A,B) = Σm(1,3)
جدول K-Map دو متغیره به شکل زیر است:
| A \ B | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 0 | 1 |
دو تا 1 کنار هم داریم، پس آنها را در یک گروه دوتایی قرار میدهیم.
در این گروه، مقدار A یک بار 0 و یک بار 1 است، پس A حذف میشود. اما B در هر دو خانه برابر 1 است.
بنابراین:
F = B
یعنی کل آن عبارت نسبتاً ساده را میتوان با یک سیم مستقیم برای B پیادهسازی کرد. این دقیقاً همان چیزی است که از سادهسازی منطق میخواهیم.
مثال ۲: K-Map سه متغیره
حالا یک مرحله سختتر:
F(A,B,C) = Σm(1,3,5,7)
برای سه متغیر، معمولاً A را در یک طرف و BC را در طرف دیگر قرار میدهیم:
| A \ BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 1 | 0 |
چهار خانه دارای 1 را یک گروه چهارتایی میکنیم.
در این گروه، A تغییر میکند و بنابراین حذف میشود. B هم تغییر میکند، پس آن هم حذف میشود. اما C در تمام چهار خانه برابر 1 است.
پس:
F = C
چه اتفاق جالبی افتاد؟ تابعی که با سه متغیر تعریف شده بود، در نهایت فقط به یک ورودی وابسته شد.
مثال ۳: چهار متغیره و مفهوم لبهها
حالا میرسیم به مثال معروف چهارمتغیره:
F(A,B,C,D) = Σm(0,2,5,7,8,10,13,15)
در K-Map چهارمتغیره، هم سطرها و هم ستونها با Gray Code مرتب میشوند:
| AB \ CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 1 | 0 | 0 | 1 |
| 01 | 0 | 1 | 1 | 0 |
| 11 | 0 | 1 | 1 | 0 |
| 10 | 1 | 0 | 0 | 1 |
گروه اول: چهار گوشه!
در نگاه اول ممکن است چهار گوشه اصلاً کنار هم به نظر نرسند. اما در K-Map، لبههای جدول به یکدیگر متصل هستند.
یعنی ستون اول با ستون آخر همسایه است و سطر اول نیز با سطر آخر همسایه محسوب میشود.
پس چهار گوشه را میتوانیم یک گروه چهارتایی در نظر بگیریم.
در این گروه، A و C تغییر میکنند و حذف میشوند. B همیشه برابر 0 و D همیشه برابر 0 است.
بنابراین این گروه میدهد:
B'D'
گروه دوم: چهار خانه وسط
چهار 1 وسط جدول را نیز میتوانیم بهصورت یک گروه چهارتایی در نظر بگیریم.
در این گروه، A تغییر میکند و حذف میشود. C نیز تغییر میکند و حذف میشود. اما B و D همیشه برابر 1 هستند.
پس:
BD
در نتیجه تابع نهایی میشود:
F = B'D' + BD
چرا متغیرها حذف میشوند؟
فرض کنید در یک گروه، A در بعضی خانهها 0 و در بعضی خانهها 1 باشد. یعنی برای اینکه خروجی آن گروه 1 شود، مقدار A اهمیتی ندارد.
پس A را از عبارت حذف میکنیم.
اما اگر مثلاً B در تمام خانههای گروه برابر 1 باشد، B باید در عبارت باقی بماند.
بنابراین یک قانون ذهنی بسیار خوب داریم:
ثابت ماند → نگه دار
تغییر کرد → حذف کن
مثال ۴: گروه بزرگتر همیشه ارزشمند است
فرض کنید در یک K-Map هشت خانه دارای 1 هستند و همه آنها را میتوانیم در یک گروه هشتتایی قرار دهیم.
در این حالت نسبت به گروه چهارتایی، متغیرهای بیشتری حذف میشوند.
پس هنگام حل K-Map معمولاً این ترتیب ذهنی را داشته باش:
بزرگترین گروه ممکن → گروه کوچکتر در صورت نیاز → پوشش تمام 1ها
البته یک خانه میتواند در بیش از یک گروه قرار بگیرد. بنابراین اگر یک 1 با استفاده از یک گروه بزرگتر بهتر پوشش داده شود، لازم نیست از همپوشانی بترسیم.
قوانین مهم K-Map
- اندازه گروه: تعداد خانههای هر گروه باید توان ۲ باشد.
- گروه بزرگتر: تا حد امکان گروه بزرگتر انتخاب کن.
- همسایگی: فقط خانههایی که واقعاً مجاور هستند میتوانند در یک گروه قرار بگیرند.
- لبهها: اولین و آخرین سطر یا ستون میتوانند همسایه باشند.
- همپوشانی: یک خانه میتواند عضو چند گروه باشد.
- تمام 1ها: در حالت سادهسازی SOP باید همه 1های موردنیاز پوشش داده شوند.
یک اشتباه رایج
در K-Map نباید صرفاً هر دو یا چهار عدد 1 را که کنار هم دیدیم گروه کنیم. باید بررسی کنیم آیا گروه بزرگتری وجود دارد یا نه.
همچنین خانههای مورب همسایه محسوب نمیشوند. K-Map با منطق مشخصی ساخته شده و قرار نیست هر خانهای که «نزدیک» به نظر میرسد را بتوانیم گروه کنیم.
ارتباط K-Map با سختافزار واقعی
شاید K-Map در نگاه اول فقط یک تکنیک برای حل تمرین مدار منطقی به نظر برسد، اما پشت آن یک ایده سختافزاری مهم وجود دارد: کمکردن منطق غیرضروری.
اگر یک تابع Boolean را سادهتر کنیم، ممکن است به Gateهای کمتر، مسیر منطقی کوتاهتر و مدار سادهتری برسیم. همین نگاه در طراحی دیجیتال، RTL و در نهایت پیادهسازی روی FPGA اهمیت پیدا میکند.
البته در FPGAهای امروزی، ابزار Synthesis بسیاری از سادهسازیهای منطقی را خودش انجام میدهد؛ بنابراین هدف K-Map فقط «دستی کم کردن Gateها» نیست. مهمتر از آن، K-Map باعث میشود بفهمیم یک عبارت Boolean چطور به ساختار منطقی تبدیل میشود.
جمعبندی
Karnaugh Map یک ابزار تصویری برای سادهسازی Boolean Logic است. مسیر حل تقریباً همیشه همین است:
تابع → قرار دادن 1ها در K-Map → پیدا کردن بزرگترین گروهها → پیدا کردن متغیرهای ثابت → نوشتن عبارت سادهشده
اگر این منطق را خوب بفهمیم، بعداً هنگام یادگیری MUX، Decoder، Adder، ALU و RTL با Verilog خیلی راحتتر میتوانیم ببینیم چیزی که روی کاغذ به شکل Boolean Expression نوشته شده، چطور تبدیل به سختافزار میشود.
سؤال برای فکر کردن: اگر در یک K-Map چهارمتغیره، 8 خانه را بتوانیم در یک گروه قرار دهیم، چند متغیر از عبارت نهایی حذف میشوند؟
dariush
دستهبندی پیشنهادی
- مدار منطقی
- طراحی دیجیتال
- آموزش
هشتگها
#مدار_منطقی #KMap #KarnaughMap #BooleanAlgebra #DigitalDesign #LogicGates #FPGA #Verilog
| AB \ CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 1 | 0 | 0 | 1 |
| 01 | 0 | 1 | 1 | 0 |
| 11 | 0 | 1 | 1 | 0 |
| 10 | 1 | 0 | 0 | 1 |
حل مثال مرحلهبهمرحله
تابع موردنظر:
F(A,B,C,D) = Σm(0,2,5,7,8,10,13,15)
ابتدا mintermها را داخل K-Map قرار میدهیم. خانههایی که مقدارشان 1 است، مشخص شدهاند.
حالا دو گروه اصلی داریم.
گروه اول: چهار گوشه
چهار گوشه را یک گروه در نظر میگیریم. نکته مهم این است که لبههای K-Map به یکدیگر متصل هستند؛ بنابراین ستون اول و آخر همسایه محسوب میشوند و همینطور سطر اول و آخر.
در این گروه:
- A تغییر میکند → حذف میشود.
- C تغییر میکند → حذف میشود.
- B = 0 ثابت است →
B' - D = 0 ثابت است →
D'
پس حاصل گروه اول:
B'D'
گروه دوم: چهار خانه وسط
حالا چهار خانه وسط را گروهبندی میکنیم.
- A تغییر میکند → حذف میشود.
- C تغییر میکند → حذف میشود.
- B = 1 ثابت است →
B - D = 1 ثابت است →
D
پس حاصل گروه دوم:
BD
نتیجه نهایی
حالا عبارت حاصل از گروهها را با OR به هم متصل میکنیم:
F = B'D' + BD
نکته ذهنی مهم: در هر گروه، متغیرهای ثابت را نگه میداریم و متغیرهایی که تغییر میکنند حذف میشوند.