مخطط الحالة

مثال تصميمي

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

ومن جهة أخرى، ينتقل النظام إلى الحالة (F) التي تتذكر أن أول خانة قد تم استلامها معطياً على الخرج (z=0).

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

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

من جانب آخر، لتوضيح كيفية تطبيق هذه القواعد لنأخذ مثال جدول الحالة (ب) ولنحاول إيجاد تخصص جيد له.

5- يجب أن تؤدي التخصصات إلى تبسيط مخططات الخرج.

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

وفي هذا السياق، 2- إعطاء الصفوف في جدول الحالة التي فيها الحالات التالية متماثلة ولكن في أعمدة مختلفة تخصصاً متجاوراً.

من جانب آخر، وكذلك إعطاء الحالات التالية في تلك الصفوف تخصصات متجاورة إذا أمكن ذلك.

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

وفي السياق ذاته، (E) لا يعني فقط الحصول على التتابع الصحيح وإنا يعني كذلك الحصول على أول خانتين في التتابع المطلوب التالي.

من جانب آخر، وكذلك إعطاء الحالات التالية في تلك الصفوف تخصصات متجاورة إذا أمكن ذلك.

في هذا الإطار، (11) وينتقل النظام إلى الحالة (A) لأن تعريف هذه الحالة هو أنها الحالة التي يصل إليها النظام بعد واحدين متتاليين (انظر السهم الخارج من F والمتجه إلى A).

وفي السياق ذاته، سوف نقوم في هذه الفقرة بتصميم كاشف تتابع آخر وذلك لإعطاء المزيد من الرؤية لعملية توليد مخطط الحالة من مواصفات المشكلة المطروحة بشكل كلمات وبنفس الوقت لتطبيق الخطوات المشروحة في الفقرة السابقة والمستعملة في التخلص من الحالات الزائدة.

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

وفي هذا الصدد، 3- إعطاء الصفوف في جدول الحالة التي فيها بعض الحالات التالية متماثلة تخصصاً متجاوراً وتعطى الأولوية للصفوف التي فيها حالات تالية متماثلة أكثر.

علاوةً على ذلك، لذلك إذا كانت (x=0) ونحن في الحالة (E) نحصل على التتابع (100) أي الخانات الثلاث الأولى من التتابع المطلوب وبما أن هذا التتابع هو بالضبط التتابع الذي يقود إلى الحالة (C) فإن مجيء (x=0) يسبب الانتقال من (E) إلى (C) وبهذا يكمل مخطط الحالة.

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

من جهة ثانية، إذا افترضنا الآن أن الدخل التالي هو (x=0) والنظام موجود في (F) يصبح التتابع (11010) وكل ما نحتاج تذكره عن هذا التتابع هو أن آخر خانتين أي (10) هما أول خانتين في التتابع المطلوب. ولكن هذا هو بالضبط ما يتم حفظه في الحالة (B) لذلك نرى في المخطط (آ) أن (x=0) يعطي (z=0) والحالة التالية هي (B) (انظر السهم الخارج من F والمتجه إلى B). أما إذا كان الدخل التالي هو (x=1) فإن آخر خانتين هما

المراجع

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

وفي هذا السياق، يظهر المخطط (آ) مخطط الحالة كاملاً (سواء كان المخطط صحيحاً أم غير صحيح لا يصبح المخطط كاملاً ما لم ينطلق من كل حالة سهمان). وكما هو مبين عندما يكون النظام في الحالة (B) وتأخذ (x) القيمة (x=1) يصبح التتابع غير مقبول ولا يمكن الانتقال من الحالة (B) إلى الحالة (C). لذلك نقدم حالة جديدة وهي (F). ومن الملاحظ أن (F) هي الحالة التي يتم الوصول إليها بعد التتابع (1001) أي هي حالة تذكر أن الخانة الأولى (آخر واحد) للتتابع المطلوب قد تم استلامها.

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

4- إعطاء الحالات التالية لأي صف تخصصات متجاورة.

علاوةً على ذلك، بعد ملء هذه الجداول بالقيم المناسبة يتم استخراج العلاقات المنطقية الممثلة لكل مدخل من مداخل القلابات (J) و(K) وللخرج (z). وبالاعتماد على هذه القلابات يمكن رسم مخطط الدارة النهائي.

في هذا الإطار، 1- إعطاء الصفوف في جدول الحالة التي فيها الحالات التالية متماثلة في كل عمود تخصصاً متجاوراً (نقول عن تخصصيين أنهما متجاورين إذا اختلفا فيما بينهما بخانة واحدة فقط).

علاوةً على ذلك، عندما تكون (x=1) والنظام في الحالة (D) فهذا يعني بأن واحدين متتاليين قد تم استلامهما. وهذه الحقيقة كما وجدنا مخزنة في الحالة (A) لذلك عند ورود (x=1) يُنْتَقَلُ من الحالة (D) إلى الحالة (A) ويكون الخرج مساوياً إلى (z=0) وأخيراً لنتذكر بأن تداخل التتابعات مسموح لذا فإن الوصول إلى الحالة

ومن جهة أخرى، عندما يكون النظام في الحالة (G) لا تسبب أي أصفار تالية تغيير ما يجب تذكره. لذلك يسبب الدخل (x=0) بقاء النظام في الحالة (G). من ناحية أخرى إذا كان النظام في الحالة (G) وجاء الدخل مساوياً إلى (x=1) نكون قد حصلنا على أول خانة في التتابع المطلوب لذلك

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

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

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

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

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

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

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

وبالتالي من الصعب معرفة قيمة (z) في الفترة الثالثة.

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

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

كذلك، إذا كان الدخل التالي (x=0) والنظام موجود في الحالة (C) يصبح لدينا ثلاث أصفار متتالية وبالتالي يكون التتابع غير مقبول ولا يمكن الانتقال من (C) إلى (D). لذلك نقدم الحالة الجديدة (G) التي تعرف بأنها التي تتذكر بأن التتابع لم يعد مقبولاً لوجود أكثر من صفرين وأنه لا يمكن الحصول على تتابع صحيح ما لم يظهر واحد (1).

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

e = H

إضافةً إلى ذلك، نعود الآن إلى الجدول (5) لنحذف منه جميع الصفوف المحتوية على نفس الحالات في عامود الحالة الراهنة مع الإبقاء على صف واحد لكل قسم كما هو مبين في الجدول (10) بعدها نقوم بتبديل أسماء الحالات العائدة لكل قسم بالاسم المختار للقسم فنحصل في النتيجة على الجدول المختصر (11).

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

من جهة ثانية، إذا قمنا الآن بكتابة الجدول (5) آخذين بعين الاعتبار هذا التقسيم ومستعملين الدليل (1) للإشارة إلى الحالات التابعة للقسم الأول والدليل (2) للإشارة إلى الحالات التابعة للقسم الثاني نحصل على الجدول (6) والذي تم فيه إهمال الخرج لعدم الحاجة إليه في المرحلة الحاضرة.

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

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

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

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

في هذا الإطار، كمثال على جدول حالة محتو على حالات زائدة يمكن التخلص منها نورد الجدول (2).

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

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

وفي السياق ذاته، لنعتبر الآن جميع الحالات التي تعطي نفس الخرج (z=0 عندما x=0) حالة واحدة بينما الحالة المخالفة (F) والتي تعطي (z=1 عندما x=0) حالة أخرى ولنقسم بناء على ذلك جميع الحالات إلى قسمين.ولنضع جميع الحالات ما عدا (x) في القسم الأول بينما الحالة (F) نضعها في القسم الثاني.

d = F

ومن ناحية أخرى، عند الانتهاء من عملية التقسيم تعتبر جميع الحالات الموجودة في القسم الواحد حالة واحدة.

ومن جهة أخرى، سنرى الآن أن جدول الحالة قد يحتوي على حالات زائدة ولو لم تكن فيه صفوف لها حالات تالية متطابقة وخرج متطابق.

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

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

وفي هذا الصدد، بفحص الجدول (6) نلاحظ أن الحالة (D) المصنفة في القسم الأول لا يمكن أن تكون مماثلة لبقية الحالات الموجودة في ذلك القسم وذلك لأن الحالة التالية لهذه الحالة وهي (F) مصنفة في القسم الثاني. بينما الحالات التالية لبقية الحالات الموجودة في القسم الأول تابعة لنفس القسم. وهذا الاستنتاج صحيح لأننا إذا قارنا بين الحالة (A) والحالة (D) نلاحظ من الجدول (5) أن (z=0) عندما (x=1) لكلا الحالتين. ولكن عندما تأخذ x القيمة (x=0) في الفترة التالية تصبح (z=0) في الحالة الأولى بينما (z=1) في الحالة الثانية. بتعميم هذه الملاحظات يمكن أن نضع المبدأ التالي:

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

c = D

وفي السياق ذاته، بفحص الجدول 7 وتطبيق المبدأ المذكور آنفاً نجد غير مناسب أن الحالتين (B) و(C) في القسم (1) وبما أن الحالة التالية لكلاهما تقع في قسم واحد وهو (3) نستطيع وضعهما في قسم واحد جديد وليكن القسم (4). بكتابة الجدول 7 من جديد آخذين بعين الاعتبار التقسيم الجديد.

وعلى صعيد آخر، كما تكون الحالة التالية هي (r) في الحالتين كذلك وهذه الحالة هي التي تحدد مستقبل النظام وليس هل الحالة (p) هي التي سبقت الحالة (r) أم الحالة (q) لذلك يمكن القول أن الحالتين (p) أو (q) غير مميزتين عن بعضهما وبالتالي يمكن الاستغناء عن إحداهن.

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

من جانب آخر، فمثلاً إذا أخذنا الحالات (A,C,E) العائدة للقسم الخامس نجد أن هذه الحالات تعطي نفس تتابع الخرج لأي تتابع لقيم الدخل (X) وبما أننا حصلنا على خمسة أقسام نستطيع الاستنتاج بأن هناك خمسة حالات فقط وهذه الحالات هي :

وفي هذا الصدد، (لا يمكن لحالتين أن تكونا في نفس القسم إذا كانت حالتيهما التاليتين موجودتين في أقسام مختلفة) بتطبيق هذه القاعدة على الجدول (6) نجد بأن الحالات (A,B,C,E,G,H) يمكن أن تنتمي لنفس القسم لذلك تترك في القسم (1) بينما لا بد من نقل الحالة (D) من القسم الأول إلى قسم جديد وليكن (3) ويظهر الجدول (7) جدول الحالة بعد أن صُنِّفَت الحالات بحسب ما ذكر.