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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث

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

هناك برنامج يقوم بعملية الاختصار بطريقة كوين ماكلوسكي تم انجازه على يد البروفيسور حاتم حسان في الجامعة الأمريكية في القاهرة [[1]] .

المبدأ[عدل]

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

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

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

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

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

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

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

مثال[عدل]

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


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 والتي تمثل القيم المنطقية للأعداد العشرية.


z y x w الرقم العشري
0 0 0 0 0
0 0 1 0 4
1 0 1 0 5
1 1 1 0 7
0 0 0 1 8
1 1 0 1 11
0 0 1 1 12
1 1 1 1 15


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


z y x w minterm
0 0 0 0 m0
0 0 1 0 m4
0 0 0 1 m8
1 0 1 0 m5
0 0 1 1 m12
1 1 1 0 m7
1 1 0 1 m11
1 1 1 1 m15


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

بعد ترتيب الأرقام حسب أعداد خانات ال (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]


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

z y x w الأرقام العشرية (المجموع)
0 0 - 0 (0،4)
0 0 0 - (0،8)
- 0 1 0 (4،5)
0 0 1 - (4،12)
0 0 - 1 (8،12)
0 - 1 0 (5،7)
1 1 1 - (7،15)
1 1 - 1 (11،15)

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

z y x w الأرقام العشرية (المجموع)
0 0 - - (0،4 و (8،12)
0 0 - - (0،8) و (4،12)
  • الخطوة الثالثة

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

15 12 11 8 7 5 4 0 المعادلة
x x x x
\overline{y}\ \overline{z}
x x
\overline{w}\,x\,\overline{y} 
x x

\overline{w}\,x\,z

x x

x\,y\,z

x x
w\,y\,z 


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

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

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


المصادر[عدل]

  1. ^ Univ.-Prof. Dr.-Ing. Horst Fiedler;TU Dortmund,Rechnergestuetzter Entwurf Integrierter Schaltungen