أداة حل خريطة كارنوف (K-Map)

تبسيط الدوال البوليانية باستخدام خريطة كارنوف

تساعد خريطة كارنوف (K-Map) على ترتيب قيم الدالة البوليانية بطريقة تجعل الحالات التي تختلف في متغير واحد فقط متجاورة. وهذا يجعل حذف المتغيرات غير الضرورية من التعبير أسهل في الفهم والمراجعة.

تدعم الأداة دوال تحتوي على 2 أو 3 أو 4 أو 5 متغيرات. ويمكن بدء المسألة من خريطة كارنوف نفسها، أو من جدول الحقيقة، أو من تعبير بولياني، أو من المينترمات أو الماكسترومات.

جميع طرق الإدخال تمثل الدالة نفسها. عند تغيير قيمة في أحدها، تتحدث طرق العرض الأخرى لتطابق الدالة الجديدة.

ماذا تعني القيم 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)

يمثل المينترمات (Minterms) التي تكون فيها قيمة الدالة 1.

أما:

ΠM(0,2,4,6)

فيمثل الماكسترومات (Maxterms) التي تكون فيها قيمة الدالة 0.

ويمكن أيضًا إدخال تعبير بولياني مباشرة.

تقوم الأداة بتقييم التعبير وتكوين جدول الحقيقة وخريطة كارنوف والمينترمات والماكسترومات المقابلة له.

وبذلك يمكن مقارنة أكثر من تمثيل للدالة نفسها دون إعادة بناء المسألة من البداية.

كيف تتكون مجموعات خريطة كارنوف؟

يجب أن تحتوي المجموعة الصحيحة على عدد من الخلايا يساوي قوة للعدد اثنين:

1, 2, 4, 8, 16

كلما كانت المجموعة الصحيحة أكبر، أمكن عادة حذف عدد أكبر من المتغيرات من الحد الناتج.

كما أن حواف خريطة كارنوف متجاورة منطقيًا.

فالخلايا الموجودة على الحافة اليمنى يمكن أن تكون مجاورة لخلايا على الحافة اليسرى، وينطبق الشيء نفسه على الحافتين العليا والسفلى.

ولهذا يمكن للخلايا الأربع الموجودة في الزوايا أن تكوّن مجموعة واحدة.

ويمكن أن تتداخل المجموعات أيضًا. مشاركة خلية في أكثر من مجموعة ليست خطأ إذا كانت تساعد على الوصول إلى تعبير أبسط.

تعرض الأداة هذه المجموعات مباشرة على K-Map حتى يكون من السهل ربطها بالنتيجة النهائية.

الفرق بين SOP وPOS

في صيغة SOP (Sum of Products) يعتمد التبسيط أساسًا على الخلايا التي تكون فيها قيمة الدالة 1.

قد تكون النتيجة مثل:

A'B + BC

أما POS (Product of Sums) فتعتمد على الخلايا التي تكون فيها قيمة الدالة 0.

مثال:

(A + B')(B + C)

ليست إحدى الصيغتين أقصر دائمًا.

قد يكون SOP أبسط لدالة معينة، بينما يكون POS أكثر اختصارًا لدالة أخرى.

إذا لم تفرض المسألة صيغة محددة، يمكن مقارنة النتيجتين واختيار التمثيل الأنسب.

Quine-McCluskey وPetrick's Method

في الخرائط الصغيرة يمكن أحيانًا تحديد المجموعات المناسبة بمجرد النظر.

لكن مع 4 أو 5 متغيرات قد تظهر عدة طرق صحيحة لتغطية الخلايا المطلوبة.

تستخدم الأداة Quine-McCluskey للبحث عن الـ prime implicants بطريقة منظمة.

الـ prime implicant هو حد لا يمكن توسيعه أكثر دون إدخال تركيبة غير مسموحة.

بعض هذه الحدود تكون ضرورية لأنها تغطي حالة مطلوبة لا يغطيها أي prime implicant آخر.

إذا بقيت عدة طرق لإكمال الحل بعد تحديد الحدود الضرورية، يتم استخدام Petrick's Method لتحليل التركيبات المتبقية.

هذا مفيد خصوصًا عندما لا يكون اختيار أفضل مجموعات K-Map واضحًا بالنظر فقط.

خرائط كارنوف من 2 إلى 5 متغيرات

خريطة كارنوف ذات متغيرين تحتوي على 4 خلايا، وهي أبسط حالة لفهم فكرة التجميع.

مع 3 متغيرات توجد 8 خلايا، ويصبح التجميع عبر الحواف أوضح.

خريطة 4 متغيرات تحتوي على 16 خلية وتستخدم كثيرًا في مسائل المنطق الرقمي.

أما مع 5 متغيرات فهناك 32 تركيبة إدخال ممكنة. ويصبح الحل اليدوي أصعب عندما توجد حالات X أو عدة مجموعات محتملة.

تحافظ الأداة في جميع هذه الحالات على توافق خريطة كارنوف وجدول الحقيقة والتعبير والمينترمات والماكسترومات مع الدالة نفسها.

الدائرة المنطقية وتصدير PDF

بعد تبسيط الدالة يمكن عرض النتيجة على شكل دائرة منطقية.

يساعد ذلك على رؤية العلاقة بين التعبير المبسط وبوابات AND وOR وNOT.

كما يمكن مراجعة عدد الحدود والـ literals وعدد البوابات في النتيجة.

وعند الحاجة إلى الاحتفاظ بالحل، يمكن تصديره بصيغة PDF مع خريطة كارنوف والمجموعات وخطوات الحل وتمثيل الدائرة.