پرش به محتوا

نمودار حالت

از ویکی‌پدیا، دانشنامهٔ آزاد
نمودار حالت یک در با قابلیت باز و بسته شدن

نمودار حالت نوعی دیاگرام برای تشریح و توضیح رفتار یک سیستم به صورت مرحله‌ای در علوم کامپیوتری و دیجیتال می‌باشد. نمودار حالت، از تعداد محدودی «حالت» تشکیل شده‌است که این حالت‌ها بیانگر یکی از حالت‌های مختلف سیستم می‌باشد. برخی اوقات نیز برای یک نگاه کلی به مدار سیستم از این نمودارها استفاده می‌شود. اشکال مختلفی از نمودار حالت وجود داشته که بعضاً دارای معانی متفاوتی می‌باشند. معمولاً هنگام طراحی یک ماشین یا مدار، برای راحتی و قابل فهم بودن کارکرد آن ابتدا نمودار حالت آن رسم شده و سپس از روی آن جدول حالت و شماتیک آن به دست می‌آورند. این عمل به دلیل نزدیکی فهم بصری نمودار با کارکردی کلی مدار می‌باشد.

کلیات

[ویرایش]

نمودار حالت یک دید کلی و خلاصه از رفتار یک سیستم را به ما می‌دهد. این نمودار مجموعه‌ای از رخدادها را که در حالات مختلف و ممکن یک سیستم رخ می‌دهد را تجزیه و تحلیل می‌کند. بدینوسیله هر نمودار معمولاً اشیایی از یک کلاس را ارائه می‌کند و با حالات مختلف این کلاس، سیستم را مورد ارزیابی و پیگیری قرار می‌دهد. این موضوع ابتدا به وسیله دانشمندی به نام "شانون" و " ویوور" در کتاب " تئوری ریاضیات در ارتباطات " در سال ۱۹۴۹ مطرح شد. منبع دیگر، کتاب "تیلور بوث" با نام" ماشین‌های ترتیبی و تئوری خودکارسازی " در سال ۱۹۶۷ می‌باشد. در طرف دیگر استفاده از "جدول درستی انتقال " نیز شیوه‌ای دیگر برای بیان این مفهوم می‌باشد.

در نمودار حالت، کلیه حالات یک ماشین در نظر گرفته شده و هر حالت با یک دایره نشان داده می‌شود. سپس شرایط آن حالت مورد بررسی قرار گرفته و بررسی می‌شود که بر اثر ورودی‌های مختلف ماشین به کدام حالت جدید می‌رود یا در حالت فعلی باقی می‌ماند. این انتقال حالت‌ها را به وسیله پیکانهایی از حالت فعلی به سمت حالت جدید نشان می‌دهند و دارای این مفهوم می‌باشد که ماشین با دریافت یک ورودی خاص، از این حالت به حالت جدید می‌رود. همچنین معمولاً بروی این پیکان‌ها مقدار ورودی متناظر برای این انتقال و مقدار خروجی از حالت فعلی را برای آن نشان داده و آن‌ها را با یک ممیز از هم جدا می‌کنند. این نمودار حالت در واقع شکل بصری جدول حالت یک ماشین یا مدار منطقی می‌باشد و به وسیله آن دید بهتری را می‌توان نسبت به مدار به دست آورد.

گراف جهت دار

[ویرایش]
A گراف جهت دار

یک فرم کلاسیک از نمودار حالت برای سیستم‌هایی با حالات محدود، «گراف جهت دار» با المان‌ها (Q,Σ،Z,δ،q0,F) می‌باشد:

رأس‌های Q: حالت‌های محدود یک سیستم، با دایره‌ها و برچسب‌هایی بر روی آن‌ها که یکتا هستند، نشان داده می‌شود. گاهی نیز نام حالت را در دایره می‌نویسند. مؤلفه ورودی Σ: مجموعه متناهی از نمادهای ورودی یا اختصاص داده شده به ورودی‌ها. مؤلفه خروجی Z: مجموعه متناهی از نمادهای خروجی یا اختصاص داده شده به خروجی‌ها.

تابع خروجی ω نقشه‌ای برداری از زوج‌های مرتب ورودی‌ها و حالات به خروجی سیستم را ارائه می‌کند و معادل ریاضی آن به صورت ω: Σ × Q→ Z نشان داده می‌شود.

لبه δ: که نشاندهنده تغییر از یک حالت به حالت دیگر بر اثر یک ورودی می‌باشد. (که با نماد خود آن بر روی لبه دایره‌ها نشان داده می‌شود). یک لبه معمولاً به وسیله یک بردار از یک دایره (یک حالت) به دایره دیگر (حالت بعدی) متصل می‌شود. این لبه تغییر حالت را براساس یک ورودی خاص بیان می‌کند. این را به صورت δ: Q × Σ → Q نشان داده که در آن δ تابع انتقال نامیده می‌شود. برهمین اساس δ(q,a)= p معرف خروجی P برای حالت q با ورودی a می‌باشد.

حالت اولیه q0: یکی از حالات سیستم می‌باشد که در راه اندازی اولیه سیستم در آن وضعیت قرار گرفته و در صورت نداشتن برنامه خاص به صورت تصافی می‌باشد. حالت پذیرش F: معمولاً به صورت دو دایره داخل هم نشان دهده شده و در واقع حالت پذیرش اولین و شروع‌کننده سیکل سیستم است. البته برخی اوقات برای مرحله نهایی یا مرحله‌ای که وضعیت ماشین از آن خارج نمی‌شود نیز استفاده می‌گردد.

مثال

[ویرایش]

در شکل زیر S1 و S2 حالات مدار و S1 حالت پذیرش، می‌باشد. هر یک از بردارهای لبه با یک ورودی نشانه گذاری شده‌است. مثلاً در حالت S2 در صورتی که ورودی ۱ به مدار اعمال شود، سیستم در حالت خود می‌ماند.

DFAexample.svg
DFAexample.svg

مثال: ماشین Mealy

[ویرایش]

S1 و S2 و S2 حالات سیستم می‌باشند. هر بردار لبه به صورت "j / k" نشان داده شده‌است که در آن j ورودی مدار و k خروجی را نشان می‌دهد.

State diagram of a simple Mealy machine

مدل ماشین میلی در واقع بر اساس این فرض استوار است که یک مدار ترتیبی از دو جزء مداری به صورت زیر ساخته شده‌است: یک قسمت حافظه و یک قسمت مدار ترکیبی. خروجی مدار وابسته به شرایط فعلی و ورودی‌های فعلی بوده و حافظه نیز تابع شرایط ورودی است. درست مانند یک فیدبک، مدار به حالت فعلی و ورودی آن وابسته است. این وابستگی باعث می‌گردد تا در لحاظت بسیار کوچکی نتوان خروجی درستی از مدار گرفت (زمانی که هنوز فیدبک به خروجی نرسیده و خروجی پایدار نشده‌است) البته این زمان بسیار کوته می‌باشد. به این گونه مدارها اصطلاحاً مدارهای میلی گویند.

نمودار حالت در مقابل فلوچارت

[ویرایش]

افراد تازه‌کار در نمودار حالت، معمولاً آن را با فلوچارت اشتباه می‌گیرند. شکل زیر تفاوت نمودار حالت را با فلوچارت نشان می‌دهد. در نمودار حالت، عبور از یک حالت به حالت دیگر به واسطه یک ورودی به صراحت بیان می‌شود در حالتی که در فلوچارت با انجام مراحل هر وضعیت به مرحله بعد رفته و فلوچارت را می‌پیماییم.

State diagram (a) and flowchart (b)

در فلوچارت مراحل به واسطه یک عملکرد خاص (مثلاً اجرای یک برنامه) انجام شده و مرحله بعد آغاز می‌شود و در واقع آن‌ها حالت یک سیستم را بیان نمی‌کنند بلکه وظایف یک سیستم را مشخص می‌کند. اغلب از فلوچارت برای اجرای برنامه‌های پشت سرهم استفاده شده و برنامه به صورت مرحله به مرحله اجرا می‌شود و این دقیقاً همان فلوچارت است. به صورت دقیق تر هنگامی یک برنامه کار می‌کند، کد آن به صورت خط به خط اجرا شده و فلوچارت را پیمایش می‌کند. در هر کد مشخص شده‌است که چه کاری را انجام دهد و بنابراین خود برنامه بین دو وضعیت مختلف تصمیم‌گیری می‌کند. در سوی دیگر، یک نمودار حالت، براساس شرایط فعلی و بسته به ورودی‌های سیستم رفتار می‌کند و خود آن از قبل برنامه‌ریزی شده نیست هرچند که تمام حالت‌های ورودی در آن تعریف شده باشد.

جستارهای وابسته

[ویرایش]

رجوع به

[ویرایش]

منابع

[ویرایش]

پیوند به بیرون

[ویرایش]