تحسين المنطق

📅 آخر تحديث: ٢٦ يوليو ٢٠٢٦
✍️ نُشر في: ٢٦ يوليو ٢٠٢٦
📷 يحتوي على 9 صور
الموسوعة الحرة

تحسين المنطق هو عملية إيجاد تمثيل مكافئ لدائرة منطقية محددة في ظل قيد واحد أو أكثر من القيود المحددة. وتُعد هذه العملية جزءًا من توليف المنطق المُطبق في الإلكترونيات الرقمية وتصميم الدوائر المتكاملة .

بشكل عام، تُقيّد الدائرة بمساحة شريحة دنيا مع مراعاة زمن استجابة مُحدد مسبقًا. يهدف تحسين منطق دائرة معينة إلى الحصول على أصغر دائرة منطقية تُعطي نفس قيم الدائرة الأصلية. [ 1 ] عادةً ما تكون الدائرة الأصغر ذات الوظيفة نفسها أرخص، [ 2 ] وتشغل مساحة أقل، وتستهلك طاقة أقل ، ولها زمن استجابة أقصر، وتقلل من مخاطر التداخل غير المتوقع ، ومخاطر تأخر معالجة الإشارة ، وغيرها من المشكلات الموجودة على المستوى النانوي للهياكل المعدنية في الدوائر المتكاملة .

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

تحفيز

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

مع ظهور توليف المنطق ، كان أحد أكبر التحديات التي واجهت صناعة أتمتة تصميم الإلكترونيات (EDA) هو إيجاد أبسط تمثيل للدائرة وفقًا لوصف التصميم المُعطى. [ ملاحظة 1 ] على الرغم من وجود تحسين المنطق ثنائي المستوى منذ فترة طويلة في شكل خوارزمية كوين-مكلوسكي ، والتي تلتها لاحقًا مُصغِّر المنطق الاستدلالي إسبريسو ، إلا أن التحسن السريع في كثافة الرقائق، والاعتماد الواسع للغات وصف الأجهزة لوصف الدوائر، قد أضفيا الطابع الرسمي على مجال تحسين المنطق كما هو عليه اليوم، بما في ذلك Logic Friday (واجهة رسومية)، وMinilog، وESPRESSO-IISOJS (منطق متعدد القيم). [ 3 ]

طُرق

تُطبق أساليب تبسيط الدوائر المنطقية بنفس القدر على تقليل التعبيرات المنطقية .

تصنيف

اليوم، ينقسم تحسين المنطق إلى فئات مختلفة:

استنادًا إلى تمثيل الدائرة
تحسين المنطق على مستويين
تحسين المنطق متعدد المستويات
بناءً على خصائص الدائرة
تحسين المنطق التسلسلي
تحسين المنطق التوافقي
بناءً على نوع التنفيذ
أساليب التحسين الرسومي
أساليب التحسين الجدولية
أساليب التحسين الجبري

الأساليب البيانية

تمثل الطرق البيانية الوظيفة المنطقية المطلوبة من خلال رسم تخطيطي يوضح متغيرات المنطق وقيمة الوظيفة. ومن خلال معالجة الرسم التخطيطي أو فحصه، يمكن الاستغناء عن الكثير من العمليات الحسابية المرهقة. تشمل طرق التبسيط البياني للمنطق ثنائي المستوى ما يلي:

تبسيط التعبيرات المنطقية

يمكن تطبيق نفس أساليب تقليل التعبيرات المنطقية (التبسيط) المدرجة أدناه على تحسين الدائرة.

في حالة تحديد الدالة المنطقية بواسطة دائرة (أي أننا نريد إيجاد دائرة مكافئة ذات حجم أصغر ما يمكن)، فقد تم افتراض أن مشكلة تصغير الدائرة غير المحدودة هيΣ2P{\displaystyle \Sigma _{2}^{P}}-كاملة في تعقيد الوقت ، وهي نتيجة تم إثباتها أخيرًا في عام 2008، [ 4 ] ولكن هناك طرق استدلالية فعالة مثل خرائط كارنو وخوارزمية كوين-مكلوسكي التي تسهل العملية.

تشمل طرق تقليل الدوال المنطقية ما يلي:

الأساليب المثلى متعددة المستويات

تُعرف الطرق التي تُستخدم لإيجاد التمثيل الأمثل للدوائر المنطقية في الأدبيات العلمية باسم " التوليف الدقيق" . ونظرًا للتعقيد الحسابي، فإن التوليف الدقيق لا يُمكن تطبيقه إلا على الدوال المنطقية الصغيرة. وتُحوّل المناهج الحديثة مسألة التحسين إلى مسألة إرضاء منطقي . [ 5 ] [ 6 ] وهذا يُتيح إيجاد التمثيل الأمثل للدوائر باستخدام مُحلِّل SAT .

الأساليب الاستدلالية

تستخدم الطريقة الاستدلالية قواعد راسخة لحل مجموعة فرعية عملية مفيدة من مجموعة أكبر بكثير من المشكلات المحتملة. قد لا تُنتج الطريقة الاستدلالية الحل الأمثل نظريًا، ولكن إذا كانت مفيدة، فإنها ستوفر معظم التحسين المطلوب بأقل جهد ممكن. ومن الأمثلة على أنظمة الحاسوب التي تستخدم الطرق الاستدلالية لتحسين المنطق، برنامج Espresso المُصغِّر للمنطق الاستدلالي .

التمثيلات ثنائية المستوى مقابل التمثيلات متعددة المستويات

بينما يشير تمثيل الدوائر ثنائي المستوى بدقة إلى العرض المُبسط للدائرة من حيث مجموعات المنتجات (SOPs ) - وهو الأنسب لتنفيذ التصميم على مصفوفة منطقية قابلة للبرمجة (PLA ) - فإن التمثيل متعدد المستويات هو عرض أكثر عمومية للدائرة من حيث مجموعات المنتجات (SOPs) ومجموعات حاصل الجمع (POSs ) المتصلة بشكل عشوائي، والشكل المُحلل، وما إلى ذلك. تعمل خوارزميات تحسين المنطق عمومًا إما على التمثيل الهيكلي (مجموعات المنتجات، الشكل المُحلل) أو التمثيل الوظيفي ( مخططات القرار الثنائية ، مخططات القرار الجبرية ) للدائرة. في شكل مجموعات المنتجات (SOPs)، تُشكل بوابات AND أصغر وحدة ويتم ربطها معًا باستخدام بوابات OR، بينما في شكل مجموعات الجمع (POS) يكون العكس. يتطلب شكل مجموعات الجمع (POS) استخدام الأقواس لتجميع حدود OR معًا تحت بوابات AND، لأن OR لها أسبقية أقل من AND. يُترجم كل من شكلي مجموعات المنتجات (SOPs) ومجموعات الجمع (POS) بشكل جيد إلى منطق الدوائر.

إذا كان لدينا دالتان F 1 و F 2 :

F1=أب+أج+أد،{\displaystyle F_{1}=AB+AC+AD,\,}
F2=أ′ب+أ′ج+أ′هـ.{\displaystyle F_{2}=A'B+A'C+A'E.\,}

يتطلب التمثيل ذو المستويين المذكور أعلاه ستة مصطلحات منتج و24 ترانزستورًا في CMOS Rep.

يمكن أن يكون التمثيل المكافئ وظيفيًا في المستويات المتعددة كما يلي:

P = B + C .
F 1 = AP + AD .
F 2 = A ' P + A ' E .

على الرغم من أن عدد المستويات هنا هو 3، إلا أن العدد الإجمالي لمصطلحات المنتج والحرفيات ينخفض ​​بسبب مشاركة المصطلح B + C.

وبالمثل، نميز بين الدوائر التوافقية والدوائر التتابعية . تنتج الدوائر التوافقية مخرجاتها بناءً على المدخلات الحالية فقط، ويمكن تمثيلها بعلاقات منطقية . ومن أمثلتها: مشفرات الأولوية ، ومفككات التشفير الثنائية ، ومضاعفات الإرسال ، ومفككات الإرسال .

تُنتج الدوائر التتابعية مخرجاتها بناءً على المدخلات الحالية والسابقة، معتمدةً على إشارة الساعة لتمييز المدخلات السابقة عن المدخلات الحالية. ويمكن تمثيلها بآلات الحالة المحدودة. ومن أمثلتها القلابات والعدادات .

مثال

مثال الدائرة الأصلي والمبسط

رغم وجود طرق عديدة لتبسيط الدوائر الكهربائية، إلا أن هذا المثال يُبسّط دالة منطقية. ترتبط الدالة المنطقية التي تُنفذها الدائرة ارتباطًا مباشرًا بالتعبير الجبري الذي تُستمد منه هذه الدالة. [ 7 ] لنفترض الدائرة المستخدمة لتمثيل(أ∧ب¯)∨(أ¯∧ب){\displaystyle (A\wedge {\bar {B}})\vee ({\bar {A}}\wedge B)}من الواضح أن هذه العبارة تستخدم دالتين نفي، ودالتين ربط، ودالة فصل. وهذا يعني أنه لبناء الدائرة، نحتاج إلى عاكسين ، وبوابتي " و" ، وبوابة "أو" .

يمكن تبسيط الدائرة (تقليل حجمها) بتطبيق قوانين الجبر البولياني أو باستخدام الحدس. بما أن المثال ينص على أنأ{\displaystyle A}صحيح عندماب{\displaystyle B}إذا كان هذا غير صحيح، والعكس صحيح، فيمكن للمرء أن يستنتج أن هذا يعني ببساطةأ≠ب{\displaystyle A\neq B}فيما يتعلق بالبوابات المنطقية، فإن عدم المساواة يعني ببساطة بوابة XOR (أو الحصرية). لذلك،(أ∧ب¯)∨(أ¯∧ب)⟺أ≠ب{\displaystyle (A\wedge {\bar {B}})\vee ({\bar {A}}\wedge B)\iff A\neq B}إذن، الدائرتان الموضحتان أدناه متكافئتان، ويمكن التحقق من ذلك باستخدام جدول الحقيقة :

أب(أ)∧ب )∨( أ)∧ب)أ≠ب
FFFFتيFتيFFFFF
FتيFFFتيتيتيتيFتيتي
تيFتيتيتيتيFFFتيتيF
تيتيتيFFFFFتيتيFتي

انظر أيضاً

ملحوظات

  1. ↑ يمكن استخدام حجم قائمة الشبكة لقياس البساطة.

مراجع

  1. ↑ ماكسفيلد، كلايف "ماكس" (1 يناير 2008). "الفصل 5: تدفقات التصميم "التقليدية"" . في ماكسفيلد، كلايف "ماكس" (محرر). FPGAs . الوصول الفوري. بيرلينجتون: نيونس / إلسيفير. الصفحات 75-106 . doi : 10.1016/B978-0-7506-8974-8.00005-3 . ISBN  978-0-7506-8974-8تم الاطلاع عليه بتاريخ 2021-10-04 .
  2. ↑ بالاسانيان، سيران؛ أغاجوليان، مانيه؛ ووتكه، هاينز-ديتريش؛ هينكه، كارستن (16 مايو 2018). "الإلكترونيات الرقمية" (ملف PDF) . بكالوريوس الأنظمة المدمجة - السنة الدراسية. تيمبوس. ديزاير. مؤرشف (ملف PDF) من الأصل بتاريخ 4 أكتوبر 2021. تم الاطلاع عليه بتاريخ 4 أكتوبر 2021 .(101 صفحة)
  3. ↑ ثيوبالد، م.؛ ناوك، إس إم (نوفمبر 1998). "خوارزميات استدلالية سريعة ودقيقة لتقليل منطق خالٍ من المخاطر على مستويين" . معاملات IEEE في التصميم بمساعدة الحاسوب للدوائر المتكاملة والأنظمة . 17 (11): 1130-1147 . doi : 10.1109/43.736186 .
  4. ↑ بوخفوهر، ديفيد؛ أومانس، كريستوفر (يناير 2011). "تعقيد تبسيط الصيغ المنطقية" (ملف PDF) . مجلة علوم الحاسوب والأنظمة . 77 (1). قسم علوم الحاسوب، معهد كاليفورنيا للتكنولوجيا ، باسادينا، كاليفورنيا، الولايات المتحدة الأمريكية: إلسيفير : 142-153 . doi : 10.1016/j.jcss.2010.06.011 .هذه نسخة موسعة من ورقة المؤتمر: بوخفوهر، ديفيد؛ أومانس، كريستوفر (2008). "تعقيد تبسيط الصيغ المنطقية". وقائع المؤتمر الدولي الخامس والثلاثين للأتمتة واللغات والبرمجة (ICALP) (ملف PDF) . سلسلة محاضرات في علوم الحاسوب . المجلد 5125. برلين/هايدلبرغ، ألمانيا: سبرينغر-فيرلاغ . الصفحات 24-35 . doi : 10.1007/978-3-540-70575-8_3 . ISBN   978-3-540-70574-1تمت أرشفة الملف (PDF) من النسخة الأصلية بتاريخ 14 يناير 2018. تم الاطلاع عليه بتاريخ 14 يناير 2018 .
  5. ↑ هاسويك، وينستون. "التوليف الدقيق القائم على SAT: الترميزات، وعائلات الطوبولوجيا، والتوازي" (ملف PDF) . EPFL . تم الاطلاع عليه بتاريخ 7 ديسمبر 2022 .
  6. ↑ هاسويك، وينستون. "التوليف الدقيق القائم على SAT لشبكات المنطق متعددة المستويات" (ملف PDF) . EPFL . تم الاطلاع عليه بتاريخ 7 ديسمبر 2022 .
  7. ↑ مانو، م. موريس؛ كيم، تشارلز ر. (2014). أساسيات المنطق وتصميم الحاسوب (الطبعة الدولية الجديدة الرابعة ). بيرسون للتعليم المحدودة . ص 54. ISBN   978-1-292-02468-4.

للمزيد من القراءة