مخطط الحالة

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

التخلص من الحالات الزائدة

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

لنستعرض الآن كيفية تحديد الحالات الزائدة في جدول الحالة. ولنأخذ كمثال نظام ميلي الممثل في جدول الحالة (1) والمحتوى على مدخل وحيد (x) ومخرج وحيد (z) (تنطبق ملاحظاتنا التالية على نظام ميلي بعدة مداخل ومخارج وعلى نظام مور أيضاً).

كما هو ملاحظ لم تظهر في الجدول (1) جميع حالات جدول الحالة وإنما حالتين خاصتين فقط وهما (p) و(q) اللتين تتمتعان بالخاصية التالية: إذا كانت الحالة الراهنة هي (p) أو (q) فبغض النظر عن قيمة (x) نحصل على نفس الخرج وعلى نفس الحالة التالية: أي سواء كانت الحالة الراهنة هي (p) أو (q) وكانت (x=0) مثلاً نحصل على الخرج (z) نفسه في الحالتين. كما تكون الحالة التالية هي (r) في الحالتين أيضاً وهذه الحالة هي التي تحدد مستقبل النظام وليس هل الحالة (p) هي التي سبقت الحالة (r) أم الحالة (q) لذلك يمكن القول أن الحالتين (p) أو (q) غير مميزتين عن بعضهما وبالتالي يمكن الاستغناء عن إحداهن.

كمثال على جدول حالة محتو على حالات زائدة يمكن التخلص منها نورد الجدول (2). بفحص صفوف الجدول بالترتيب نجد أن للحالتين (B) و(D) نفس الحالة التالية ونفس الخرج. لذا نستنتج أن الحالة (D) غير لازمة ونستطيع حذفها من الجدول (بالطبع كان من الممكن حذف B عوضاً عن D). بعدها نقوم باستبدال الحالة (D) أينما وجدت في الجدول بالحالة (B) فنحصل على الجدول (3).

بفحص الجدول (3) نلاحظ وجود حالتين متكافئتين وهما (E) و(A) فإذا حذفنا الصف الموجود فيه الحالة (E) ثم بدلنا في الجدول كل حالة (E) بحالة (A) حصلنا على الجدول (4) الذي لا يقبل الاختصار.

التخلص من الحالات الزائدة بطريقة التقسيم (partitioning)

لقد رأينا في المثال السابق أن الحالتين اللتين لهما نفس الحالة التالية ونفس الخرج تعتبران متكافئتين وبالتالي من الممكن حذف إحداهن. سنرى الآن أن جدول الحالة قد يحتوي على حالات زائدة ولو لم تكن فيه صفوف لها حالات تالية متطابقة وخرج متطابق. لتوضيح هذا الأمر وكيفية ملاحظة الحالات الزائدة في هذا النوع من الجداول سنستعرض جدول الحالة (5) بتفحص هذا الجدول لا نلاحظ جود أي صفوف تتطابق فيها الحالة التالية وقيم الخرج. ولكن بتفحص قيم الخرج وتذكر أن الهدف من النظام التتابعي هو إعطاء الخرج المطلوب نلاحظ أن جميع قيم الخرج متطابقة في جميع الحالات ما عدا في الحالة (F). لذلك من المعقول أن نعتبر الحالة (F) مختلفة عن بقية الحالات بغض النظر عن أية عوامل أخرى. لنعتبر الآن جميع الحالات التي تعطي نفس الخرج (z=0 عندما x=0) حالة واحدة بينما الحالة المخالفة (F) والتي تعطي (z=1 عندما x=0) حالة أخرى ولنقسم بناء على ذلك جميع الحالات إلى قسمين.ولنضع جميع الحالات ما عدا (x) في القسم الأول بينما الحالة (F) نضعها في القسم الثاني. إذا قمنا الآن بكتابة الجدول (5) آخذين بعين الاعتبار هذا التقسيم ومستخدمين الدليل (1) للإشارة إلى الحالات التابعة للقسم الأول والدليل (2) للإشارة إلى الحالات التابعة للقسم الثاني نحصل على الجدول (6) والذي تم فيه إهمال الخرج لعدم الحاجة إليه في المرحلة الحاضرة.

بفحص الجدول (6) نلاحظ أن الحالة (D) المصنفة في القسم الأول لا يمكن أن تكون مماثلة لبقية الحالات الموجودة في ذلك القسم وذلك لأن الحالة التالية لهذه الحالة وهي (F) مصنفة في القسم الثاني. بينما الحالات التالية لبقية الحالات الموجودة في القسم الأول تابعة لنفس القسم. وهذا الاستنتاج صحيح لأننا إذا قارنا ما بين الحالة (A) والحالة (D) نلاحظ من الجدول (5) أن (z=0) عندما (x=1) لكلا الحالتين. ولكن عندما تأخذ x القيمة (x=0) في الفترة التالية تصبح (z=0) في الحالة الأولى بينما (z=1) في الحالة الثانية. بتعميم هذه الملاحظات يمكن أن نضع المبدأ التالي: (لا يمكن لحالتين أن تكونا في نفس القسم إذا كانت حالتيهما التاليتين موجودتين في أقسام مختلفة) بتطبيق هذه القاعدة على الجدول (6) نجد بأن الحالات (A,B,C,E,G,H) يمكن أن تنتمي لنفس القسم لذلك تترك في القسم (1) بينما لا بد من نقل الحالة (D) من القسم الأول إلى قسم جديد وليكن (3) ويظهر الجدول (7) جدول الحالة بعد أن تم تصنيف الحالات وفقاً لما ذكر. بفحص الجدول 7 وتطبيق المبدأ المذكور آنفاً نجد غير مناسب أن الحالتين (B) و(C) في القسم (1) وبما أن الحالة التالية لكلاهما تقع في قسم واحد وهو (3) نستطيع وضعهما في قسم واحد جديد وليكن القسم (4). بكتابة الجدول 7 من جديد آخذين بعين الاعتبار التقسيم الجديد.

بفحص الجدول 8 نجد مناسباً حذف الحالتين (C) و(E) من القسم (1) ووضعهما في قسم جديد وليكن القسم (5) بكتابة الجدول 8 من جديد آخذين بعين الاعتبار التقسيم الجديد نحصل على الجدول 9 والغير قابل للتقسيم.

عند الانتهاء من عملية التقسيم تعتبر جميع الحالات الموجودة في القسم الواحد حالة واحدة. فمثلاً إذا أخذنا الحالات (A,C,E) العائدة للقسم الخامس نجد أن هذه الحالات تعطي نفس تتابع الخرج لأي تتابع لقيم الدخل (X) وبما أننا حصلنا على خمسة أقسام نستطيع الاستنتاج بأن هناك خمسة حالات فقط وهذه الحالات هي : $a=(A,C,E)$ $b=(B,G)$ c = D d = F e = H نعود الآن إلى الجدول (5) لنحذف منه جميع الصفوف المحتوية على نفس الحالات في عامود الحالة الراهنة مع الإبقاء على صف واحد لكل قسم كما هو مبين في الجدول (10) بعدها نقوم بتبديل أسماء الحالات العائدة لكل قسم بالاسم المختار للقسم فنحصل في النتيجة على الجدول المختصر (11).

مثال تصميمي

سوف نقوم في هذه الفقرة بتصميم كاشف تتابع آخر وذلك لإعطاء المزيد من الرؤية لعملية توليد مخطط الحالة من مواصفات المشكلة المطروحة بشكل كلمات وبنفس الوقت لتطبيق الخطوات المشروحة في الفقرة السابقة والمستخدمة في التخلص من الحالات الزائدة. يجب أن يتصف كاشف التتابع المطلوب بكونه نظاماً من نوع ميلي وباحتوائه على مدخل وحيد (x) ومخرج وحيد (z) وأن يعطي على مخرجه (z=1) في أي فترة ساعة يكون فيها الدخل (x=0) بشرط أن يكون الدخل في الفترات الأربع السابقة (x=1001). أي أن التتابع المطلوب لتوليد (z=1) هو (x=10010) لزيادة التوضيح نورد الشكل التالي الذي يبين تتابع لقيم الدخل والخرج الموافقة.

نلاحظ من الشكل السابق أن قيم (x) في الفترات (2.3.4.5.6) تشكل تتابعاً ناجحاً. لذلك لدينا في الفترة السادسة (z=1) كما نلاحظ جواز تداخل التتابعات الناجحة مع بعضها. لذا تشكل آخر خانتين في التتابع الأول الخانتين الأوليتين للتابع الثاني الناجح والذي يلي التتابع الأول مباشرة. نجد أيضاً أن عدم تحديد قيمة (x) في الفترة الزمنية الأولى يجعل من الصعب معرفة هل القيمة (x=0) في الفترة الثالثة هي نهاية تتابع ناجح أم لا. وبالتالي من الصعب معرفة قيمة (z) في الفترة الثالثة. لنبدأ مباشرة بمخطط الحالة متجاوزين مخطط الانسياب ولنعرف الحالة الأولى عن طريق تحديد التاريخ الذي أدى إلى الوصول إلى هذه الحالة بشكل لا يدع حاجة أبداً للرجوع إلى ما قبل هذه الحالة. هناك عدة طرق لتعريف الحالة الأولى في مثالنا الحالي. إحدى هذه الطرق والتي سنعتمدها في مثالنا الحالي هي اعتبار الحالة الأولى الحالة التي يصل إليها النظام بعد حصول تتابع لاثنين أو أكثر من الواحدات (1). وهذه الحالة هي الحالة التي يصل إليها النظام في الفترة الزمنية الثالثة المبينة في الشكل السابق (يجب تذكر أن الحالة في أي فترة زمنية لا تتأثر بالدخل في نفس الفترة ولكن بالدخل في الفترات السابقة فقط) على كل حال أن الحالة الأولى (A) المبينة في الشكل التالي هي الحالة التي يتم عندها وصول أول خانة من التتابع الناجح وكل شيء يحدث قبل ذلك (أي قبل الفترتين الزمنيتين المتتاليتين التي يكون فيهما x=1 و z=0 يعتبر غير مهم).

إن حدث الآن وكانت قيمة (x) في الفترة الثالثة (x=1)فإن هذا الواحد سيصبح الخانة الأولى في التتابع المطلوب. وبما أنه لم يطرأ أي تغيير نتيجة لذلك يشار إلى الفترة الثالثة بواسطة السهم المبتدأ من الحالة (A) والمنتهي عند الحالة (A) ويوضع على هذا السهم اللافتة (0/1) للإشارة إلى أن (z=0) عندما (x=1) وأن الحالة الثالثة هي الحالة (A) نفسها. لنفترض الآن أن القيم الأربعة التالية للدخل هي (x=0010) أي أن تتابعا صحيحياً قد ظهر في هذه الحالة يجب تذكر حدوث كل خطوة من هذه الخطوات لذلك يولد كل دخل حالة جديدة كما هو مبين في الشكل السابق تولد القيمة الأخيرة (x=0) خرجاً (z=1) وعند الحافة القادحة التالية يعود النظام إلى الحالة (E). يظهر المخطط (آ) مخطط الحالة كاملاً (سواء كان المخطط صحيحاً أم غير صحيح لا يصبح المخطط كاملاً ما لم ينطلق من كل حالة سهمان). وكما هو مبين عندما يكون النظام في الحالة (B) وتأخذ (x) القيمة (x=1) يصبح التتابع غير مقبول ولا يمكن الانتقال من الحالة (B) إلى الحالة (C). لذلك نقدم حالة جديدة وهي (F). ومن الملاحظ أن (F) هي الحالة التي يتم الوصول إليها بعد التتابع (1001) أي هي حالة تذكر أن الخانة الأولى (آخر واحد) للتتابع المطلوب قد تم استلامها. إذا افترضنا الآن أن الدخل التالي هو (x=0) والنظام موجود في (F) يصبح التتابع (11010) وكل ما نحتاج تذكره عن هذا التتابع هو أن آخر خانتين أي (10) هما أول خانتين في التتابع المطلوب. ولكن هذا هو بالضبط ما يتم حفظه في الحالة (B) لذلك نرى في المخطط (آ) أن (x=0) يعطي (z=0) والحالة التالية هي (B) (انظر السهم الخارج من F والمتجه إلى B). أما إذا كان الدخل التالي هو (x=1) فإن آخر خانتين هما (11) وينتقل النظام إلى الحالة (A) لأن تعريف هذه الحالة هو أنها الحالة التي يصل إليها النظام بعد واحدين متتاليين (انظر السهم الخارج من F والمتجه إلى A). إذا كان الدخل التالي (x=0) والنظام موجود في الحالة (C) يصبح لدينا ثلاث أصفار متتالية وبالتالي يكون التتابع غير مقبول ولا يمكن الانتقال من (C) إلى (D). لذلك نقدم الحالة الجديدة (G) التي تعرف بأنها التي تتذكر بأن التتابع لم يعد مقبولاً لوجود أكثر من صفرين وأنه لا يمكن الحصول على تتابع صحيح ما لم يظهر واحد (1). عندما يكون النظام في الحالة (G) لا تسبب أي أصفار تالية تغيير ما يجب تذكره. لذلك يسبب الدخل (x=0) بقاء النظام في الحالة (G). من ناحية أخرى إذا كان النظام في الحالة (G) وجاء الدخل مساوياً إلى (x=1) نكون قد حصلنا على أول خانة في التتابع المطلوب لذلك

ينتقل النظام إلى الحالة (F) التي تتذكر أن أول خانة قد تم استلامها معطياً على الخرج (z=0). عندما تكون (x=1) والنظام في الحالة (D) فهذا يعني بأن واحدين متتاليين قد تم استلامهما. وهذه الحقيقة كما وجدنا مخزنة في الحالة (A) لذلك عند ورود (x=1) يتم الانتقال من الحالة (D) إلى الحالة (A) ويكون الخرج مساوياً إلى (z=0) وأخيراً لنتذكر بأن تداخل التتابعات مسموح لذا فإن الوصول إلى الحالة (E) لا يعني فقط الحصول على التتابع الصحيح وإنا يعني أيضاً الحصول على أول خانتين في التتابع المطلوب التالي. لذلك إذا كانت (x=0) ونحن في الحالة (E) نحصل على التتابع (100) أي الخانات الثلاث الأولى من التتابع المطلوب وبما أن هذا التتابع هو بالضبط التتابع الذي يقود إلى الحالة (C) فإن مجيء (x=0) يسبب الانتقال من (E) إلى (C) وبهذا يكمل مخطط الحالة. عند إنشاء مخطط الحالة من الممكن أن يصل أشخاص مختلفون إلى مخططات مختلفة في الشكل ومع ذلك صحيحة. لكن عندما يتم التخلص من الحالات الزائدة يجب أن تصبح هذه المخططات متطابقة (بالطبع هناك احتمال لاختلاف أسماء الحالات فقط بين مخطط وآخر). ولإعطاء مثال عن كيف يؤدي التفكير المختلف إلى الوصول إلى مخططات مختلفة نورد المخطط المبين في الشكل (ب) والذي يختلف عن المخطط المبين في الشكل (آ) بنقطة واحدة فقط وهي أن النظام ينتقل عندما (x=0) من الحالة (F) إلى (B) في المخطط الأول بينما ينتقل من (F) إلى (E) في المخطط الثاني وهذا الفرق مسموح به لأن الحالة (B) هي الحالة التي يتم فيها تذكر أن الخانتين السابقتين مباشرة هما الواحد أولاً ثم الصفر وهذا التتابع هو بالضبط الذي يؤدي إلى الوصول إلى الحالة (E) وما عداه من معلومات غير مهم.

لنقوم الآن بتطبيق خطوات التخلص من الحالات الزائدة التي استعرضناها سابقاً على مخططي الحالة المبينين في الشكل (آ) و(ب) ولنبدأ أولاً بتشكيل جدول الحالة (12) للمخطط المبين في الشكل (آ) بتفحص الجدول نلاحظ أن الحالة (F) هي نفس الحالة (A). لذلك تم حذف الحالة (A) لنحصل على الجدول (13) الذي بتفحصه أيضاً نلاحظ أن الحالة (E) هي نفس الحالة (B) لذلك تحذف الحالة (E) منه فنحصل على الجدول (14) الذي لا يمكن اختصار أي حالة منه بطريقة الفحص. وإذا أجرينا الآن طريقة التقسيم نتأكد من عدم إمكانية الاختصار.

نعود الآن إلى مخطط الحالة المبين في الشكل (ب) لنشكل منه جدول الحالة (15) الذي نلاحظ بتفحصه عدم إمكانية اختصار أي حالة. لذلك نلجأ إلى طريقة التقسيم وتظهر الجداول (16) (17) (18) (19) (20) خطوات هذه الطريقة التي تعطي في النهاية الجدول (20) المتطابق مع الجدول (14).

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

تخصيص الحالات (State Assignments)

لقد قمنا في الفقرات السابقة بتخصيص الحالات بشكل عشوائي وذلك لكي نوضح خطوات التخلص من الحالات الزائدة بشكل مبسط. نعود الآن إلى هذا الموضوع لنناقش موضوع اختيار التخصص الأمثل. إذا تفحصنا الأشكال (15) و(14) ثانية نلاحظ أن عملية التخصيص تؤثر بشكل واضح على أماكن ظهور الأصفار والواحدات في مخططات كارناف العائدة للقلابات وللخرج (z) أيضاً وبالتالي تؤثر على علاقات التحريض المستخرجة من هذه الجداول. وبما أننا نسعى دائماً للحصول على أبسط علاقات تحريض فمن البديهي أن نختار التخصيص الذي يؤدي إلى توزع الأصفار والواحدات بشكل يسمح بالحصول على مثل هذه العلاقات حينما تكون عدد الحالات المتوفرة أقل من أربعة من الممكن تجريب جميع التخصصات الممكنة واختيار الأمثل. ولكن حينما يزد أعداد الحالات عن أربعة يزداد عدد حالات التخصص هذه كثيرًا. فمثلاً من أجل خمس حالات يصبح عدد حالات التخصص (140) ومن أجل ست حالات يصبح (426) وهكذا... وهذا العدد الكبير من الصعب تجريبه لذلك لابد من إيجاد طريقة تسمح لنا بسهولة باختيار التخصص الأمثل. لا توجد في الحقيقة قواعد سهلة يمكن تطبيقها للحصول على أفضل تخصيص.

ولكن هناك بعض القواعد التي تؤدي إلى تخصيص جيد (قد لا يكون الأفضل ولكنه حتماً أفض من التخصص العشوائي) وهذه القواعد هي التالية: 1- إعطاء الصفوف في جدول الحالة التي فيها الحالات التالية متماثلة في كل عمود تخصصاً متجاوراً (نقول عن تخصصيين أنهما متجاورين إذا اختلفا فيما بينهما بخانة واحدة فقط). وكذلك إعطاء الحالات التالية في تلك الصفوف تخصصات متجاورة إذا أمكن ذلك. 2- إعطاء الصفوف في جدول الحالة التي فيها الحالات التالية متماثلة ولكن في أعمدة مختلفة تخصصاً متجاوراً. وكذلك إعطاء الحالات التالية في تلك الصفوف تخصصات متجاورة إذا أمكن ذلك. 3- إعطاء الصفوف في جدول الحالة التي فيها بعض الحالات التالية متماثلة تخصصاً متجاوراً وتعطى الأولوية للصفوف التي فيها حالات تالية متماثلة أكثر. 4- إعطاء الحالات التالية لأي صف تخصصات متجاورة. 5- يجب أن تؤدي التخصصات إلى تبسيط مخططات الخرج. ومن الجدير بالذكر أن هذه القواعد قد رتبت حسب تسلسل الأهمية لذلك يتم تطبيقها وفقاً لتسلسلها فإذا حدث تناقض أثناء التطبيق بين قاعدتين تعطي الأفضلية للقاعدة الأكثر أهمية.

لتوضيح كيفية تطبيق هذه القواعد لنأخذ مثال جدول الحالة (ب) ولنحاول إيجاد تخصص جيد له. نلاحظ بتفحص مخطط الحالة (ب) أننا يجب أن نخصص الحالتين (F) و(G) تخصصاً متجاوراً وذلك تطبيقاً للقاعدة الأولى. كما يجب تخصيص الحالتين (E) و(D) تخصيصاً متجاوراً تطبيقاً للقاعدة الثانية وذلك إذا تم تخصيص الحالتين (G) و(F) وكذلك يجب تخصيص الحالتين (C) و(B) تخصيصاً متجاوراً وذلك إذا تم تخصيص الحالتين (E) و(D). وهكذا نحصل على جدول الانتقال (ج).

هذا ويجب الإشارة إلى أن ترتيب متحولات الحالة في جدول الانتقال يجب أن يكون مماثلاً

لترتيبها في مخطط كارناف وهذا منطقي لأن الخطوة التالية هي ترجمة جدول الانتقال إلى مخطط كارناف المسمى بمخطط التحريض. وبما أنه توجد سبع حالات فقط ندخل في الصف الموافق لتشكيله الحالة (180) إشارات اللاتعيين (X) وذلك في جميع الأعمدة كما هو مبين في مخطط الحالة (ج).

المراجع

النظم المنطقيّة والدارات الرقميّة للدكتور: فادي فوز

[1] www.raypub.com

[2] www.sciencedirect.com

[3] www.arab-eng.com