رسم بياني لعكس الإشارة

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

الرسم البياني "و-عاكس" (AIG) هو رسم بياني موجه وغير دوري يمثل التنفيذ الهيكلي للوظائف المنطقية لدائرة أو شبكة . يتكون الرسم البياني "و-عاكس" من عقدتين مدخلتين تمثلان الاقتران المنطقي ، وعقد طرفية تحمل أسماء متغيرات، وحواف قد تحتوي على علامات تشير إلى النفي المنطقي . نادرًا ما يكون هذا التمثيل للدالة المنطقية فعالًا من الناحية الهيكلية للدوائر الكبيرة، ولكنه تمثيل فعال لمعالجة الدوال المنطقية . عادةً ما يُمثَّل الرسم البياني المجرد كبنية بيانات في البرمجيات.

نموذجان مختلفان هيكليًا لـ AIGs للدالة f(x1, x2, x3) = x2 * ( x1 + x3 )

يُعدّ التحويل من شبكة البوابات المنطقية إلى نماذج البوابات المنطقية (AIGs) سريعًا وقابلًا للتوسع. ولا يتطلب سوى التعبير عن كل بوابة باستخدام بوابات AND وعواكس . ولا يؤدي هذا التحويل إلى زيادة غير متوقعة في استخدام الذاكرة أو وقت التشغيل. وهذا ما يجعل نموذج البوابات المنطقية تمثيلًا فعالًا مقارنةً بمخطط القرار الثنائي (BDD) أو صيغة "مجموع الضرب" (ΣoΠ)، أي الصيغة المتعارف عليها في الجبر البولياني والمعروفة بالصيغة الانفصالية الطبيعية (DNF). ويمكن أيضًا اعتبار مخطط القرار الثنائي والصيغة الانفصالية الطبيعية دوائر كهربائية، لكنهما ينطويان على قيود رسمية تحدّ من قابليتهما للتوسع. فعلى سبيل المثال، تتكون صيغ مجموع الضرب من مستويين على الأكثر، بينما تُعدّ مخططات القرار الثنائي متعارف عليها، أي أنها تتطلب تقييم متغيرات الإدخال بنفس الترتيب على جميع المسارات.

تُعدّ الدوائر الإلكترونية المُكوّنة من بوابات بسيطة، بما في ذلك بوابات AIG، موضوعًا بحثيًا عريقًا. بدأ الاهتمام ببوابات AIG مع ورقة آلان تورينج الرائدة عام 1948 [ 1 ] حول الشبكات العصبية، حيث وصف شبكة قابلة للتدريب عشوائيًا من بوابات NAND. استمر الاهتمام خلال أواخر الخمسينيات [ 2 ] ، وتواصل في السبعينيات مع تطوير العديد من التحويلات المحلية. طُبّقت هذه التحويلات في العديد من أنظمة توليف المنطق والتحقق منه، مثل نظام دارينجر وآخرون [ 3 ] ونظام سميث وآخرون [ 4 ] ، والتي تُقلّل من حجم الدوائر لتحسين المساحة والتأخير أثناء التوليف، أو لتسريع التحقق من التكافؤ الرسمي . اكتُشفت العديد من التقنيات المهمة مبكرًا في شركة IBM ، مثل دمج وإعادة استخدام تعابير المنطق متعددة المدخلات والتعابير الفرعية، والمعروفة الآن باسم التجزئة الهيكلية .

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

وجدت نماذج AIGs نجاحًا في تطبيقات EDA المتنوعة . وقد أحدث الجمع الأمثل بين نماذج AIGs وقابلية الإرضاء المنطقي تأثيرًا كبيرًا على التحقق الرسمي ، بما في ذلك التحقق من النموذج والتحقق من التكافؤ. [ 5 ] كما تُظهر دراسة حديثة أخرى إمكانية تطوير تقنيات ضغط دوائر فعالة باستخدام نماذج AIGs. [ 6 ] ويتزايد الفهم لإمكانية حل مشكلات التركيب المنطقي والفيزيائي باستخدام المحاكاة وقابلية الإرضاء المنطقي لحساب الخصائص الوظيفية (مثل التناظرات) [ 7 ] ومرونة العقد (مثل المصطلحات غير المهمة ، وإعادة الاستبدال ، و SPFDs ). [ 8 ] [ 9 ] [ 10 ] ويُبين ميشينكو وآخرون أن نماذج AIGs تمثل تمثيلًا موحدًا واعدًا ، قادرًا على الربط بين التركيب المنطقي ، ورسم خرائط التكنولوجيا ، والتركيب الفيزيائي، والتحقق الرسمي. ويعود ذلك، إلى حد كبير، إلى البنية البسيطة والموحدة لنماذج AIGs، التي تسمح بإعادة الكتابة والمحاكاة ورسم الخرائط والتحديد والتحقق من خلال مشاركة نفس بنية البيانات.

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

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

التطبيقات

انظر أيضاً

مراجع

  1. ↑ أُعيد نشر ورقة تورينج البحثية لعام 1948 بعنوان: تورينج إيه إم. الآلات الذكية. في: إنس دي سي، محرر. الأعمال الكاملة لتورينج إيه إم - الذكاء الميكانيكي. دار نشر إلسيفير للعلوم، 1992.
  2. ↑ هيلرمان، ليو (يونيو 1963). "فهرس لدوائر منطقية من نوع أو-عكس و أن-عكس بثلاثة متغيرات". معاملات IEEE في الحواسيب الإلكترونية . EC-12 (3): 198-223 . doi : 10.1109/PGEC.1963.263531 .
  3. ↑ أ. دارينجر؛ و. هـ. جوينر الابن؛ س. ل. بيرمان؛ ل. تريفيليان (يوليو 1981). "توليف المنطق من خلال التحويلات المحلية". مجلة آي بي إم للبحوث والتطوير . 25 (4): 272-280 . CiteSeerX 10.1.1.85.7515 . doi : 10.1147/rd.254.0272 . 
  4. ↑ جي إل سميث؛ آر جيه باهنسن؛ إتش هاليول (يناير 1982). "مقارنة منطقية بين الأجهزة ومخططات التدفق". مجلة آي بي إم للبحوث والتطوير . 26 (1): 106-116 . CiteSeerX 10.1.1.85.2196 . doi : 10.1147/rd.261.0106 . 
  5. ↑ أ. كوهلمان؛ ف. باروثي؛ ف. كروهم؛ م. ك. غاناي (2002). "استدلال منطقي قوي للتحقق من التكافؤ والتحقق من الخصائص الوظيفية". معاملات IEEE في التصميم بمساعدة الحاسوب للدوائر والأنظمة المتكاملة . 21 (12): 1377-1394 . Bibcode : 2002ITCAD..21.1377K . CiteSeerX 10.1.1.119.9047 . doi : 10.1109/tcad.2002.804386 . 
  6. ↑ بير بيسي؛ آرني بورالف (2004). "ضغط الدوائر المدركة للرسوم البيانية الموجهة غير الدورية للتحقق الرسمي" (ملف PDF) . وقائع مؤتمر ICCAD '04 . الصفحات 42-49 . 
  7. ↑ كيه-إتش تشانغ؛ آي إل ماركوف؛ في. بيرتاكو (2005). "إعادة التوصيل وإعادة التخزين المؤقت بعد التنسيب من خلال البحث الشامل عن التناظرات الوظيفية" (ملف PDF) . وقائع المؤتمر الدولي للتصميم بمساعدة الحاسوب (ICCAD) لعام 2005. الصفحات 56-63 . 
  8. ↑ أ. ميشينكو؛ ج. س. تشانغ؛ س. سينها؛ ج. ر. بيرش؛ ر. برايتون؛ م. تشزانوفسكا-جيسكي (مايو 2006). "استخدام المحاكاة وقابلية الإرضاء لحساب المرونة في الشبكات المنطقية" (ملف PDF) . معاملات IEEE في التصميم بمساعدة الحاسوب للدوائر والأنظمة المتكاملة . 25 (5): 743-755 . Bibcode : 2006ITCAD..25..743M . CiteSeerX 10.1.1.62.8602 . doi : 10.1109/tcad.2005.860955 . S2CID 13099806 .  
  9. ↑ س. سينها؛ ر. ك. برايتون (1998). "تطبيق واستخدام مخططات SPFD في تحسين الشبكات المنطقية". وقائع المؤتمر الدولي للتصميم بمساعدة الحاسوب (ICCAD ). الصفحات 103-110 . CiteSeerX 10.1.1.488.8889 .  
  10. ↑ س. ياماشيتا؛ هـ. ساوادا؛ أ. ناغويا (1996). "طريقة جديدة للتعبير عن الصلاحيات الوظيفية لوحدات FPGA القائمة على جداول البحث وتطبيقاتها" (ملف PDF) . وقائع المؤتمر الدولي لتصميم الدوائر المتكاملة بمساعدة الحاسوب (ICCAD ). الصفحات 254-261 . 
  11. ↑ ج. بومغارتنر؛ أ. كولمان (2001). "إعادة التوقيت في أصغر مساحة على هياكل الدوائر المرنة" (ملف PDF) . وقائع مؤتمر ICCAD'01 . الصفحات 176-182 . 
  • هذا المقال مقتبس من عمود في النشرة الإلكترونية لجمعية ACM SIGDA بقلم آلان ميشينكو . النص الأصلي متاح هنا .