مرجع
آخر الزيارات

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

738 كلمة•0 مشاهدة•🗒️ منذ 3 أيام
باختصار: طريقة كوين – ماكلوسكي في اختصار التوابع المنطقية (The Quine – Mc Cluskosy Minimization). تتناول المقالة 10 أقسام، منها «مثال»، «المرحلة الثالثة: إيجاد المدى الأدنى للتغطية» و«+».
المحتويات
  1. مثال
  2. المرحلة الثالثة: إيجاد المدى الأدنى للتغطية
  3. +
  4. الخطوة الثانية
  5. +
  6. المرحلة الأولى: الترتيب حسب القيم الدنيا للأعداد
  7. الخطوة الثالثة
  8. المبدأ
  9. المرحلة الثانية: إيجاد التوابع الرئيسية
  10. الخطوة الأولى

بدايةً، طريقة كوين – ماكلوسكي في اختصار التوابع المنطقية (The Quine – Mc Cluskosy Minimization). هي طريقة لاختصار المعادلات المنطقية ولها مجال واسع في علم الحاسوب وذلك لسهولة دمجها في خوارزميات الحاسوب ولما تحققه من تبسيط للمعادلات المنطقية المركبة وبذلك تقليل التكلفة. وفيما يلي تفاصيل أوسع عن ذلك.

ومن جهة أخرى، قام ماكلوسكي بتعميم طريقة كوين للتعامل مع عدد أكبر من المتغيرات وذلك باستخدام الحدود الدنيا للتابع (minterms) وبمراعاة ترميز غراي (Gray Coding).

مثال

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

المرحلة الثالثة: إيجاد المدى الأدنى للتغطية

علاوةً على ذلك، نقوم في هذه الخطوة الأخيرة بإيجاد مدى التغطية الأصغر للتوابع المختصرة (minimum cover)، بمعنى انه يتم إيجاد أقل عدد من المعادلات المنطقية لكي تعطينا المطلوب، فالهدف هو اختصار عدد كبير من المعادلات المنطقية بعدد أقل بشرط أن يعطيا نفس النتيجة.

+

  • الاختلاف واضح في 2 بت: الأول والثالث ولهذا لا يمكن الجمع بينهما.
  • تجمع [5 مع 7].
  • تجمع [7 مع 15] و [11 مع 15]
  • فيكون الناتج كالآتي:

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

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

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

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

+

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

في هذا الإطار، [4 مع 5] و [4 مع 12] و [8 مع 12] يجمعان كذلك لانطباق ترميز غراي، حيث يختلفان كذلك في موضع بت واحد كذلك.

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

المرحلة الأولى: الترتيب حسب القيم الدنيا للأعداد

من جانب آخر، في المرحلة الأولى نكتب الأعداد بالصيغة الثنائية (0,1) ونرتبها حسب القيم الدنيا بمعنى وفق عدد خانات العدد (1) (minterms) فيها تصاعدياً (الخطوتين الأولى والثانية في المثال).

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

لكل ما تحتوي عليه المعادلة المرادفة.

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

من جانب آخر، فمثلاً تكون من جمع الأرقام (0,4) مع (8,12) ولهذا نضع إشارة x تحت هذه الخانات الأربعة وهكذا مع باقي المعادلات الناتجة.

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

في هذا الإطار، كذلك يمكن اختصار المعادلتين الثانية والرابعة لانه يمكن الوصول إلى قيمها من المعادلات الأخرى.

+ +

المبدأ

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

المرحلة الثانية: إيجاد التوابع الرئيسية

وعلى صعيد آخر، تتمثل الخطوة الثانية بإيجاد التوابع الرئيسية (prime implicants), وهي التي لا يمكن اختصارها. من أجل ذلك نقوم بجمع كل القيم الدنيا (minterms) حتى يتبقى في النهاية ما لا يمكن جمعه.

وفي السياق ذاته، عملية الجمع تتم بمراعاة ترميز غراي (Gray Coding) وينص على أن الجمع بين تابعين (عددين) مسموح فقط إذا ما اختلفا في قيمة واحدة في نظام العد الثنائي، بمعنى أن يختلفا في قيمة بت واحد فقط. لذلك كان لا بد من ترتيب التوابع الدنيا (minterms) حسب عدد خانات (1) فيها. سيتم شرح هذا بالتفصيل في المثال.

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

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

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

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.