اختصار التوابع المنطقية بطريقة كوين ماكلوسكي

تتضمن طريقة كوين – ماكلوسكي ثلاثة مراحل[1] ،هي:

في هذا المثال يتضح كيف يتم اختصار التوابع المنطقية بطريقة كوين ماكلوسكي. الهدف ان نبحث عن معادلة تعطينا مجموع الاعداد 0,4,5,7,8,11,12 بأقل قدر من البوابات المنطقية، ما يعني أقل تكلفة وأكثر سرعة في الدوائر الإلكترونية المدمجة ([1]).

${\displaystyle f(w,x,y,z)=\sum _{m}=\sum 0,4,5,7,8,11,12,15}$

• الخطوة الأولى

الجمع طبعا يجب أن يكون جمعا منطقيا (0,1)، و لذلك نكتب القيمة المنطقية للأعداد المذكورة (نظام عد ثنائي) و بما أن أكبر عدد عندنا هو 15: (1111 بالعد الثنائي)، هذا يعني أن أكبر عدد من المداخل نحتاجه هو 4 مداخل وهو عدد خانات الرقم الأكبر (15) ليحقق المطلوب. المداخل يرمز لها في هذا المثال بالأحرف w,x,y,z والتي تمثل القيم المنطقية للأعداد العشرية.

يتم ترتيب الأعداد بحسب عدد خانات ال (1) فيها، فيكون أعداد ال (1) للرقم صفر هو 0 و للرقمين اربعة (0100) و ثمانية (1000) هو 1، ولهذا تكتب تحت بعضها، وهكذا دواليك للأرقام التي تحتوي على خانتين (11) للرقمين 5 و 12 و ثلاث خانات (111) للرقمين 7 و 11 كما أن الرقم الأخير وهو 15 يحتوي على أربع خانات (1111) و لهذا يتم ترتيبه أسفل الجدول:

• الخطوة الثانية

بعد ترتيب الأرقام حسب أعداد خانات ال (1) (prim terms) نجمع كل عددين يختلفان في بت (bit) واحد فقط وهو ما يعرف بترميز غراي (Gray Coding) و نضع شَرطة (-) مكان الخانة التي فيها الاختلاف، فيتم الجمع كالتالي:

• 0 تجمع مع 4 :يختلفان في بت واحد وهو البت الثالث (بدأ من اليمين، أي من القيمة الصغرى) فيمكن جمعهما.

| 0 || 0 || 0 || 0 || 0
+
| 0 || 0 || 1 || 0 || 4
=
| 0 || 0 || - || 0 || (0,4)

نفس الأمر ينطبق على العددين 0 و 8، حيث يختلفان في مكان البت الرابع.

• [4 مع 5] و [4 مع 12] و [8 مع 12] يجمعان أيضا لانطباق ترميز غراي، حيث يختلفان أيضا في موضع بت واحد أيضا.
• [8 مع 12] بنفس الطريقة. لاحظ انه لا يمكن جمع 8 مع 5 لاختلافهما في أكثر من بت واحد:

| 0 || 0 || 0 || 1 || 8
+
| 1 || 0 || 1 || 0 || 5

الاختلاف واضح في 2 بت: الأول والثالث و لهذا لا يمكن الجمع بينهما.

• تجمع [5 مع 7].
• تجمع [7 مع 15] و [11 مع 15]

فيكون الناتج كالآتي:

نقوم بجمع الأزواج الناتجة من الخطوة السابقة والتي ينطبق عليها ترميز غراي ونضع إشارة✓ بجانب النواتج التي ينطبق عليها هذا بحيث تُستثنى من النتيجة النهائية.

• الخطوة الثالثة

في الخطوة قبل الأخيرة نرسم خريطة كارنوف لما وجدناه (يشير إلى الخانات التي لا تحتوي على إشارة ✓) في الجدولين السابقين (الخطوتين الثالثة والرابعة) و نضع إشارة x و تعني (dont care) هنا. لكل ما تحتوي عليه المعادلة المرادفة.

${\displaystyle {\overline {y}}\ {\overline {z}}}$

${\displaystyle {\overline {w}}\,x\,{\overline {y}}}$

${\displaystyle w\,y\,z}$

فمثلاً (${\displaystyle {\overline {y}}\ {\overline {z}}}$) تكون من جمع الأرقام (0,4) مع (8,12) و لهذا نضع إشارة x تحت هذه الخانات الأربعة وهكذا مع باقي المعادلات الناتجة. ايضا يمكن اختصار المعادلتين الثانية والرابعة لانه يمكن الوصول إلى قيمها من المعادلات الأخرى.

بهذا تكون المعادلات المنطقية المطلوبة لإتمام عملية جمع الأرقام في المثال مختصرة بشكل كبير (مما يعني الحاجة إلى بوابات منطقية أقل) و تكون على الشكل النهائي التالي:

${\displaystyle {\overline {y}}\ {\overline {z}}}$ + ${\displaystyle {\overline {w}}\,x\,z}$ + ${\displaystyle w\,y\,z}$

• برنامج يقوم بالاختصار بطريقة كوين ماكلوسكي.

• بوابة فلسفة
• بوابة خوارزميات
• بوابة رياضيات
• بوابة علم الحاسوب
• بوابة منطق