آلة الحالة الخوارزمية

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

آلة الحالة الخوارزمية ( ASM ) هي طريقة لتصميم آلات الحالة المحدودة (FSMs)، طُوِّرت في الأصل على يد توماس إي. أوزبورن في جامعة كاليفورنيا، بيركلي (UCB) منذ عام 1960، [ 1 ] ثم عُرضت وطُبِّقت في شركة هيوليت-باكارد عام 1968، ووُضِّحت ووُسِّعت منذ عام 1967، وكتب عنها كريستوفر آر. كلير منذ عام 1970. [ 2 ] [ 3 ] [ 4 ] تُستخدم هذه الآلة لتمثيل مخططات الدوائر المتكاملة الرقمية . يشبه مخطط ASM مخطط الحالة ، ولكنه أكثر تنظيمًا، وبالتالي أسهل فهمًا. يُعد مخطط ASM طريقة لوصف العمليات المتسلسلة لنظام رقمي.

طريقة ASM

تتكون طريقة ASM من الخطوات التالية:

1. قم بإنشاء خوارزمية، باستخدام الشفرة الزائفة ، لوصف العملية المطلوبة للجهاز.
2. قم بتحويل الشفرة الزائفة إلى مخطط ASM .
3. صمم مسار البيانات بناءً على مخطط ASM.
4. أنشئ مخطط ASM مفصلًا بناءً على مسار البيانات.
5. صمم منطق التحكم بناءً على مخطط ASM المفصل.

مخطط ASM

يتكون مخطط ASM من أربعة أنواع من العناصر الأساسية المترابطة: اسم الحالة، ومربع الحالة، ومربع القرار، ومربع المخرجات الشرطية. تمثل حالة ASM، المُمثلة بمستطيل، حالةً واحدةً من حالات مخطط الحالة العادي أو آلة الحالة المحدودة. تُدرج مخرجات مور داخل المربع.

اسم الولاية

اسم الولاية: يتم تحديد اسم الولاية داخل الدائرة، وتوضع الدائرة في الزاوية العلوية اليسرى، أو يتم وضع الاسم بدون الدائرة.

صندوق الحالة

مربع الحالة: يتم عرض ناتج الحالة داخل المربع المستطيل

مربع القرار المستخدم في مخطط ASM

مربع القرار: يشير المعين إلى أنه سيتم اختبار الشرط/التعبير المحدد، وسيتم اختيار مسار الخروج بناءً على ذلك. يحتوي تعبير الشرط على مدخل واحد أو أكثر لآلة الحالة المحدودة (FSM). يُستخدم فحص شرط ASM، المشار إليه بمعين ذي مدخل واحد ومخرجين (للصواب والخطأ)، للانتقال المشروط بين مربعي حالة، أو إلى مربع قرار آخر، أو إلى مربع مخرج مشروط. يحتوي مربع القرار على تعبير الشرط المحدد المراد اختباره، ويحتوي هذا التعبير على مدخل واحد أو أكثر لآلة الحالة المحدودة (FSM).

مربع الإخراج المشروط

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

مسار البيانات

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

مخطط ASM مفصل

بعد تصميم مسار البيانات، يتم تحويل مخطط ASM إلى مخطط ASM مفصل. ويتم استبدال تدوين RTL بالإشارات المحددة في مسار البيانات.

انظر أيضاً

مراجع

  1. ↑ أوزبورن، توماس "توم" إي. (11 نوفمبر 2004) [1994]. "قصة توم أوزبورن بكلماته الخاصة" . صفحة ستيف ليبسون HP9825 (رسالة إلى بارني أوليفر). مؤرشفة من الأصل بتاريخ 24 فبراير 2021. تم الاطلاع عليها بتاريخ 24 فبراير 2021 .
  2. ↑ كلير، كريستوفر "كريس" ر. (فبراير 1971) [نوفمبر 1970]. التصميم المنطقي لآلات الحالة الخوارزمية . مختبرات هيوليت-باكارد، الولايات المتحدة الأمريكية: هيوليت-باكارد . رقم كتالوج CHM 102650285 . (110 صفحات)(ملاحظة: كانت هناك عدة مراجعات داخلية في عامي 1970 و1971. وقد نشرتها لاحقًا شركة ماكجرو هيل. [أ] )
  3. ↑ كلير، كريستوفر "كريس" ر. (1973) [نوفمبر 1972]. تصميم الأنظمة المنطقية باستخدام آلات الحالة . أوزبورن، توماس "توم" إي. (مساهمات أولية) ( الطبعة الأولى). مختبر أبحاث الإلكترونيات، مختبرات هيوليت-باكارد: ماكجرو-هيل، إنك. ISBN  0-07011120-0. S2CID 60509061 . SBN  07-011120-0رقم الكتاب المعياري الدولي ( ISBN) 978-0-07011120-2. ark:/13960/t9383kw8n. 79876543 . تم الاسترجاع بتاريخ 14-02-2021 .(7+114+3 صفحات)(ملاحظة: يستند هذا الكتاب إلى وثيقة داخلية لشركة هيوليت-باكارد تعود لعام 1970. [ب] )
  4. ↑ هاوس، تشارلز "تشاك" هـ. (24 ديسمبر 2012). "تحول نموذجي يحدث من حولنا" (ملف PDF) . مجلة IEEE للدوائر المتكاملة . المجلد 4، العدد 4. جامعة ستانفورد: معهد مهندسي الكهرباء والإلكترونيات . الصفحات 32-35 . doi : 10.1109/MSSC.2012.2215759 . eISSN 1943-0590 . ISSN 1943-0582 . مؤرشف (PDF) من الأصل في 20 يناير 2013. تاريخ الاسترجاع: 30 يونيو 2023 . الصفحات ٢-٣ : عُقدت ورشة عمل IEEE السنوية الثانية حول المعالجات الدقيقة (والتي تُسمى الآن ورشة عمل أسيلومار للحواسيب الصغيرة ، أو AMW) من الأربعاء إلى الجمعة، ٢٨-٣٠ أبريل ١٩٧٦، بالقرب من مونتيري، كاليفورنيا [...] وصفتُ في محاضرتي مساء الأربعاء أدواتٍ مكّنت من اتباع منهجية تصميم مختلفة تمامًا - تصميم آلة الحالة الخوارزمية (ASM) - باستخدام رياضيات متغيرات حالة ليابونوف ، وتقنيات مشتقة رائدة في شركة HP من قِبل كريس كلير وديف كوكران للآلات الحاسبة العلمية المحمولة الناجحة بشكلٍ باهر (مثل HP 35 ) [...] خلاصة القول: لم يعد تصميم الدوائر مسألة عنصر بعنصر، بل أصبح مسألة "تدفق الحالة" عند العديد من العُقد - "كلمات" السجلات المتسلسلة بدلًا من فولتية دبابيس الجهاز. بمعنى آخر، جادلت هذه المنهجية بأن الفولتية الإلكترونية، سواء كانت تناظرية أو مُبدّلة، "ستخسر" أمام تعليمات البرامج و"حالات البيانات". سيتم تصميم الأنظمة وتحليلها لضمان تسلسل الحالات الصحيح بدلاً من التركيز على تشويه الإشارة التناظرية أو أوقات التبديل الرقمي. [...] لقد لمستُ بالفعل قوة الكتب قبل النشر . فقد لاقى كتاب كلير القيّم حول منهجية ASM، بعنوان " تصميم الأنظمة المنطقية باستخدام آلات الحالة" ، رواجًا واسعًا في أوساط مجتمع HPdesign. [...] إلا أن قسم الهندسة الكهربائية في جامعة ستانفورد لم يكن متفائلًا، حيث ألغى دورة كلير عام 1974، مُعللًا ذلك بأنها "غير تقليدية بعض الشيء". [...] فضّلت ستانفورد تقنيات كوين-مكلوسكي للتقليل . ومن المناسب أن زميل ميد في معهد كاليفورنيا للتكنولوجيا ، إيفان ساذرلاند، أعدّ مقالًا لمجلة ساينتفك أمريكان (1977) [...] حول التحدي الذي تُشكّله الإلكترونيات الدقيقة على نظرية الحوسبة وتطبيقاتها، مُشيرًا إلى أنه نظرًا لأن معظم سطح الشريحة يشغله "أسلاك" (مسارات موصلة) بدلاً من "مكونات" (ترانزستورات)، فقد أصبحت عقود من نظرية التقليل في تصميم المنطق غير ذات صلة. [...]      (4 صفحات)

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

  • لي، سونغ غو (2000) [1999]. تصميم الحواسيب والأجهزة الرقمية المعقدة الأخرى (  الطبعة الأولى). أبر سادل ريفر، نيو جيرسي، الولايات المتحدة الأمريكية: برنتيس هول، إنك. ISBN 0-13-040267-2LCCN 99-049967 . ISBN​  978-0-13040267-7.(xiv+418 صفحة)
  • لي، سونغ غو (2000). تصميم الحاسوب: مثال على تصميم المنطق الرقمي المتقدم . برنتيس هول .
  • لي، سونغ غو (2006). تصميم المنطق الرقمي المتقدم: استخدام لغة VHDL، وآلات الحالة، والتوليف لـ FPGAs . تومسون. ISBN 0-534-46602-8.
  • براون، ستيفن د.؛ فرانزيك، زفونكو . أساسيات المنطق الرقمي مع تصميم VHDL (  الطبعة الأولى).
    • براون، ستيفن د.؛ فرانزيك، زفونكو (2004). أساسيات المنطق الرقمي باستخدام تصميم VHDL (  الطبعة الثانية). ماكجرو هيل. ISBN 978-0-07-249938-4.
    • براون، ستيفن د.؛ فرانزيك، زفونكو (2009). أساسيات المنطق الرقمي باستخدام تصميم VHDL (  الطبعة الثالثة). ماكجرو هيل. ISBN 978-0-07-352953-0.
  • بيورنر، داينز (ديسمبر 1970) [1970-05-04، 1970-04-07، 1970-02-04]. "آلات المخططات الانسيابية" . مجلة BIT للرياضيات العددية . 10 (4). مختبر أبحاث IBM، سان خوسيه، كاليفورنيا: 415-442 . doi : 10.1007/BF01935563 . S2CID 189767592. RJ-685 (رقم 13346). 
  • لي، صموئيل سي. (1976). الدوائر الرقمية وتصميم المنطق . إنجلوود كليفس، نيو جيرسي، الولايات المتحدة الأمريكية: برنتيس هول .
  • سانتراكول، كرايم (1983). تصميم منطق الدوائر المتكاملة واسعة النطاق/الدوائر المتكاملة فائقة النطاق متعددة القيم (ملف PDF) (أطروحة دكتوراه). جامعة أوكلاهوما. مؤرشف (ملف PDF) من الأصل بتاريخ 17 أغسطس 2016. تم الاطلاع عليه بتاريخ 17 فبراير 2021 .
  • شولتز، جي دبليو (مارس 1969). كُتب في شركة أنظمة البيانات المركزية، ساني فيل، كاليفورنيا، الولايات المتحدة الأمريكية. "خوارزمية لتوليف الشبكات التسلسلية المعقدة" . تصميم الحاسوب . المجلد  8، العدد  3. كونكورد، ماساتشوستس، الولايات المتحدة الأمريكية: مؤسسة نشر تصميم الحاسوب. الصفحات 49-55 . الرقم الدولي الموحد للدوريات 0010-4566 . رمز OCLC 828863003. تاريخ الاسترجاع 22 فبراير 2021 .   (7 صفحات) (ملاحظة: تسببت هذه المقالة في عدد من الرسائل إلى المحرر في أعداد لاحقة من المجلة.)
  • شولتز، جي دبليو (1969). كُتب في شركة أنظمة البيانات المركزية، صني فيل، كاليفورنيا، الولايات المتحدة الأمريكية. "إلى المحرر" . رسائل إلى المحرر. تصميم الحاسوب . المجلد  8، العدد  5-12؟ كونكورد، ماساتشوستس، الولايات المتحدة الأمريكية: شركة نشر تصميم الحاسوب. ص  10. الرقم الدولي الموحد للدوريات 0010-4566 . رمز OCLC 828863003. ص 10: [...] في عدد أبريل، نشرتم رسالة بقلم آر إل داينلي تصف طريقة بسيطة للتعامل مع التعبيرات المنطقية من نوع حاصل ضرب المجاميع . [...] يُعلّم دي إيه هوفمان طريقة أبسط . تعتمد هذه الطريقة على إدراك أن التعبير البولياني سيكون صفرًا عندما يكون أي من العوامل في صيغة حاصل ضرب المجاميع صفرًا. رسم أصفار العوامل على مخطط فيتش أو خريطة كارنو سهلٌ مثل تحديد الآحاد لتعبير مجموع حاصل الضرب . […] للتوضيح، باستخدام مثال داينلي (A+BC)(A+C): […] ستُحدد الأصفار الناتجة عن A+BC حيثما يكون كل من A وBC صفرًا. لذلك، نحدد على الخريطة التعبير A * BC (الذي يساوي A * B + A * C ). وبالمثل، تُحدد أصفار A+C وتُرسم عند A * C. بعد تحديد جميع الأصفار، يمكن ملء باقي الخريطة بالآحاد. يمكن للمرء أن يكون أكثر رسمية قليلاً ويحسب جبريًا المتمم المنطقي للتعبير قيد الدراسة ثم يرسم أصفار ذلك التعبير الناتج. ومع ذلك، في تمثيل بسيط لحاصل ضرب المجاميع، يمكن كتابة الحدود المكملة بالنظر؛ أو يمكن رسم الأصفار بالنظر دون كتابة التعبير بالكامل […] "الاختزال الكلاسيكي الذي يتضمن متغيرات قليلة الاستخدام" 11 أكتوبر 1968. جامعة سانتا كلارا […] يتشابه عمل السيد أوزبورن بشكل كبير مع ما قدمته في هذه المقالة ، وبالتالي، سيكون بالتأكيد ذا أهمية للقراء الذين يبحثون عن مزيد من المعلومات. أفهم أنه قد عمل على تطبيق تقنية المتغيرات النادرة في تصميم الشبكات التسلسلية المُنشأة من ذاكرة القراءة فقط . ولأنه لم ينشر أي شيء في هذا المجال حتى الآن، فإذا رغب القراء في الحصول على معلومات إضافية، فيمكنهم مراسلة السيد أوزبورن على العنوان التالي: […] توماس إي. أوزبورن […] المبنى 1U […] 1501 طريق بيج ميل […] بالو ألتو، كاليفورنيا […] شكرًا لكم على إتاحة الفرصة لي للنشر معكم. […] جي دبليو شولتز […] شركة أنظمة البيانات المركزية […] صني فيل، كاليفورنيا.   (صفحة واحدة) (ملاحظة: تم نشر طريقة أوزبورن لاحقًا بواسطة كلير. [ب] )
  • لانغدون الابن، غلين ج. (1974). "الفصل 4. العلاقات المتبادلة، د. تصميم المنطق ونظرية التبديل، 3. جدول التدفق كنقطة انطلاق للتصميم" . كُتب في شركة آي بي إم، سان خوسيه، كاليفورنيا، الولايات المتحدة الأمريكية. في آشنهرست، روبرت "بوب" لوفيت [في ويكي بيانات] (محرر). تصميم المنطق - مراجعة للنظرية والتطبيق . سلسلة دراسات ACM (الطبعة الأولى  ). نيويورك، الولايات المتحدة الأمريكية: أكاديميك برس، شركة تابعة لهاركورت بريس جوفانوفيتش، ناشرون . ص  149. ISBN 0-12-436550-7ISSN 0572-4252 . LCCN 73-18988 . مؤرشف من الأصل بتاريخ 17 أبريل 2021. تم الاطلاع عليه بتاريخ 17 أبريل 2021. صفحة 149: [...] قدم شولتز [20] إسهامًا هامًا في تكييف النظرية مع التطبيق العملي ؛ إذ يعتمد على فهم المصمم الأساسي للمشكلة ويطلب منه تحديد " المتغيرات غير المتكررة ". هذه المتغيرات، بتعريفها المبسط، لا ترتبط بجميع الحالات الداخلية، أي أنها ليست ضرورية لتحديد كل حالة. في جوهرها، ترتبط المتغيرات غير المتكررة بعدد قليل فقط (ربما حالة أو حالتين) أو انتقالات بين الحالات. يقترح شولتز أن يقوم المصمم أولًا بترجمة المشكلة اللفظية إلى رسم بياني مُختزل لانتقالات الحالات. ثم تُشفّر الحالات الداخلية، وبعد ذلك تُضاف المعلومات المتعلقة بالمتغيرات غير المتكررة إلى انتقالات الحالات المناسبة. يتم إجراء "تقريب أولي" لمعادلات إدخال القلاب ، بالاعتماد فقط على المتغيرات المتكررة. يوضح شولتز كيف يمكن تعديل هذه المعادلات لاحقًا لتضمين الانتقالات التي تتحكم بها المتغيرات غير المتكررة. في أمثلة شولتز، جميع المتغيرات غير المتكررة هي إشارات إدخال، ولكن هذه الفكرة تنطبق أيضًا على إشارات متغيرات الحالة الداخلية التي يمكن اعتبارها "غير متكررة". في هذه الحالة، على سبيل المثال، قد يتم ضبط قلاب متغير الحالة الداخلية غير المتكرر بواسطة ظرف معين، ثم إعادة ضبطه لاحقًا. يمكن الآن التعامل مع خرج القلاب كمتغير إدخال غير متكرر. […]   (9+1+179+3 صفحات)