Derivation of the complete sum of a switching function with the aid of the variableentered karnaugh map اشتقاق المجموع الكامل لدالة تبديلية بالاستعانة بخريطة كارنوه متغيرة المحتويات

Abstract

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

The complete sum (CS) of a switching function f is defined as a sumofproducts formula whose products constitute all and nothing but the prime implicants off It has many useful applications including the simplification and minimization of switching functions proving equivalence or independence solution of Boolean equations and transient hazard analysis This paper presents two novel techniques for deriving the CS with the aid of the variableentered Kamaugh map (VEKM) ; a map that enjoys several pictorial advantages and a doubled variablehandling capability and hence is recommended when the number of variables ranges from 7 to 12 or even more Only completely specified switching functions (CSSFs) are considered herein simply because the CS of an incompletely specified function f is that of the CSSF that represents the upper bound fort Our first technique uses the VEKM for obtaining any productofsums expression for the function which can be multiplied out to produce the CS after deletion of any absorbable terms The second technique starts with a VEKM of CS entries and after repeated folding of the VEKM ends up with the required CS provided necessary absorptions are implemented after each folding Both techniques gain much from the use of a novel multiplication matrix that restricts the number of term compmisons needed for implementing absorptions This matrix can be used to advantage also with some purely algebraic techniques such as Tison method However algebraic techniques even after improvement might remain infelior to VEKM techniques obviously since the latter can combine most merits of map and algebra Dual versions of the VEKM techniques considered can be used to obtain the dual of the complete sum viz the complete product