Signal transition graphs
سگنل ٹرانزیشن گراف (ایس ٹی جی) عام طور پر الیکٹرانک انجینئرنگ اور کمپیوٹر انجینئرنگ میں ان کے تجزیے یا ترکیب کے مقاصد کے لیے غیر متزلزل سرکٹس کے متحرک رویے کو بیان کرنے کے لیے استعمال ہوتے ہیں۔ اہم تعریفیں اور ایپلی کیشنز غیر رسمی طور پر، ایس ٹی جی اس شکل میں ایک غیر متزلزل سرکٹ کے رویے کی گرافیکل وضاحت ہے جہاں سگنلنگ کے واقعات کے درمیان وجہ تعلقات کے بارے میں معلومات کو براہ راست پیش کیا جاتا ہے، جیسا کہ ریاستوں پر مبنی وضاحتوں کے برخلاف ہے۔ اس طرح، ایس ٹی جی ایک سرکٹ کی تفصیل کو باقاعدہ بنانے میں مدد کرتے ہیں جس کی نمائندگی عام طور پر ٹائمنگ ڈائیگرام کے ذریعے کی جاتی ہے، جسے بعض اوقات لہر کی شکلیں بھی کہا جاتا ہے۔ مؤخر الذکر الیکٹرانک انجینئرز کے ذریعہ بڑے پیمانے پر استعمال ہوتے ہیں۔ مزید رسمی طور پر، ایس ٹی جی ایک تشریح شدہ (یا لیبل شدہ) پیٹری نیٹ کی ایک قسم ہے جس کی منتقلی کو سگنلز کی اقدار میں ہونے والی تبدیلیوں کے ناموں کے ساتھ لیبل کیا جاتا ہے (سی ایف۔ سگنل ٹرانزیشن)۔ مثال کے طور پر، لیبلنگ کا عام معاملہ وہ معاملہ ہے جہاں سگنلز بائنری ہوتے ہیں، اس لیے منتقلی کی تشریح سرکٹ میں سگنلز کے بڑھتے اور گرتے کناروں کے طور پر کی جاتی ہے۔ ایس ٹی جی عام طور پر ریاستی گراف کے مقابلے غیر متغیر سرکٹس کے رویے کی زیادہ کمپیکٹ وضاحتیں دیتے ہیں۔ سرکٹ کی ایس ٹی جی تفصیلات کی پیچیدگی عام طور پر سرکٹ میں سگنلز کی تعداد میں لکیری ہوتی ہے جبکہ اسٹیٹ گراف کی پیچیدگی تیزی سے بڑھ سکتی ہے، اس حقیقت کی وجہ سے کہ غیر متغیر سرکٹس میں اعلی درجے کی ہم آہنگی ہوتی ہے۔ ایس ٹی جی میں بیک وقت ہونے والے واقعات کی نمائندگی کاز-سیکوینس ریلیشنز (سی ایف۔ حقیقی ہم آہنگی) جبکہ ریاستی گراف میں ہم آہنگی کی نمائندگی انٹرلییونگ کے ذریعے کی جاتی ہے۔ ایس ٹی جی کو پہلی بار 1981 میں سگنل گراف کے نام سے لیونڈ روزنبلم (روسی میں) نے تجویز کیا تھا۔ ان کا مزید رسمی طور پر مطالعہ کیا گیا اور 1982 میں الیکس یاکوولیف نے اپنے پی ایچ ڈی مقالے (روسی میں) میں اسنکرونس انٹرفیس کے ڈیزائن پر لاگو کیا۔ انہیں بعد میں 1985 میں انگریزی میں دو آزاد ذرائع میں پیش کیا گیا، ایک میں روزنبلم اور یاکوولیف نے اور دوسرا میں تام-انہ چو نے (اس سے پہلے کا ورژن آئی سی سی ڈی '85 میں پیش کیا گیا تھا)۔ اس کے بعد سے، ایس ٹی جیز کا نظریہ اور عمل میں بڑے پیمانے پر مطالعہ کیا گیا ہے، جس کی وجہ سے غیر متغیر کنٹرول سرکٹس کے تجزیہ اور ترکیب کے لیے مقبول سافٹ ویئر ٹولز کی ترقی ہوئی ہے، جیسے کہ پیٹریفی (چیف ڈویلپر: جورڈی کورٹیڈیلا) اور ورک کرافٹ (نیو کیسل یونیورسٹی کا ایک ٹول کٹ)۔ اسنکرونس سرکٹس کو ڈیزائن کرنے میں ایس ٹی جی کے استعمال کی مختلف مثالوں میں، سب سے زیادہ مشہور وہ ہیں جو اسنکرونس انٹرفیس، کنٹرولرز، آربیٹرز اور اینالاگ مکسڈ سگنل سرکٹس کے ڈومین میں ہیں، سی ایف۔، حال ہی میں ایس ٹی جی کو ماڈل کازل رویے تک بڑھایا گیا ہے جس میں کیپیسیٹیو جوڑی کے ذریعے ثالثی کی وجہ شامل ہے، جیسے کہ وہ جو سوئچڈ کیپیسیٹر کنورٹرز (ایس سی سی) میں استعمال ہوتے ہیں۔ توسیعات اور متعلقہ ماڈلز ایس ٹی جیز کے علاوہ، بائنری سگنلز پر مبنی، علامتی ایس ٹی جیز بھی ہیں، جہاں سگنلز کی کثیر قدر کی جا سکتی ہے۔ ٹائمنگ (تاخیر) انفارمیشن اینوٹیشن کے ساتھ ایس ٹی جیز کو سب سے پہلے 1998 میں متعارف کرایا گیا تھا، اور بعد میں 1998 میں، جہاں وقت کی رکاوٹوں کے ساتھ سرکٹس کے رویے کے تجزیے کے خیالات، جنہیں بعد میں ریلیٹو ٹائمنگ کہا گیا، کو بھی سب سے پہلے متعارف کرایا گیا تھا۔ بنیادی بنیادی پیٹری نیٹ ماڈلز کی خصوصی توسیعات، ایک کمپیکٹ شکل میں اسنکرونی اور انٹرپٹس کو پکڑنے کے لیے، پلیس چارٹ نیٹ میں متعارف کرائی گئیں۔ غیر متغیر سرکٹس کے ریاست پر مبنی ماڈلز اور پیٹری نیٹ پر مبنی ماڈلز (بشمول ایس ٹی جی) کے درمیان ایک اہم تعلق تھیوری آف ریجنز (سی ایف۔) کے استعمال میں قائم کیا گیا ہے۔ علاقوں کا نظریہ رابرٹ اسپرول، ایوان سدھرلینڈ اور چارلس مولنار کی وجہ سے کاؤنٹر فلو پائپ لائن پروسیسر کے لیے ایس ٹی جی ماڈل اور اس کے سرکٹ کے نفاذ کو حاصل کرنے کے لیے استعمال کیا گیا تھا۔ ایس ٹی جی سے قریب سے متعلق ماڈلز میں سے ایک چینج ڈائیگرام ہے، جسے مائیکل کشینیوسکی، الیکس کونڈراٹیوف، الیگزینڈر توبن اور وکٹر ورشاوسکی نے تجویز کیا ہے۔ تبدیلی کے خاکے میں AND اور OR کازالیٹی دونوں کو کمپیکٹ طریقے سے ماڈل کرنے کے قابل ہونے کے فوائد ہیں۔ لیکن ان میں انتخاب کے لحاظ سے وضاحتی طاقت کا فقدان ہے۔ پیٹری نیٹ اور تبدیلی کے خاکے کے درمیان موازنہ ان کی وضاحتی طاقت اور کازل لاجک نیٹ کی شکل میں ان کے اتحاد کے لحاظ سے پیش کیا گیا ہے۔ ہارڈ ویئر تفصیل زبانوں کے ساتھ روابط ایس ٹی جی کو مختلف ایچ ڈی ایل کے ساتھ مربوط کیا گیا ہے، مثال کے طور پر وی ایچ ڈی ایل (1996) اور ویرلوگ (2000) کے ساتھ لنک دیکھیں جس کا مقصد غیر متزلزل ڈیزائن کی حمایت کرنا ہے۔ وی ایچ ڈی ایل، ایس ٹی جیز اور پیٹری نیٹ سے ترکیب کے بہاؤ میں رکھے گئے آلات کو دکھایا گیا ہے، اور اسی طرح ویرلوگ کے ساتھ، جہاں ایک ٹول ویریزین تیار کیا گیا تھا۔ حال ہی میں ایس ٹی جی کو ان اشاروں سے جوڑا گیا ہے جن کے بارے میں خیال کیا جاتا ہے کہ وہ عملی ہارڈ ویئر ڈیزائنرز کے لیے آسان ہیں، اس لیے ویوفارم-ٹرانزیشن گراف (ڈبلیو ٹی جی) کے ماڈل کا ظہور ہوا ہے۔ اسی طرح، یہ محسوس کرتے ہوئے کہ فائنائٹ اسٹیٹ مشین (ایف ایس ایم) کا ماڈل ڈیزائنرز کے لیے ہینڈل کرنا آسان ہو سکتا ہے، مثال کے طور پر، پیٹری نیٹ یا ایس ٹی جی، برسٹ موڈ ایف ایس ایم کے ساتھ فرنٹ اینڈ کے طور پر ایک لنک تیار کیا گیا ہے۔ تجزیہ کے طریقے اس وقت، غیر متزلزل سرکٹس کے تجزیہ اور ترکیب کے لیے سب سے زیادہ موثر طریقے پیٹری نیٹ کے انکشافات پر مبنی ہیں-ان کا مطالعہ وکٹر کھومینکو نے اپنے پی ایچ ڈی مقالے میں کیا تھا۔ انہیں ورک کرافٹ کے تحت نافذ کیا جاتا ہے۔ اسنکرونس سرکٹس کے پیٹری نیٹ ماڈلز کے کچھ ذیلی کلاسوں کی کارکردگی کے تجزیے کی تحقیقات ایگوو زی اور پیٹر بیرل نے کی ہے۔ غیر متزلزل سرکٹ کی ترکیب ایس ٹی جی تفصیلات سے غیر متزلزل سرکٹس کی ترکیب میں مختلف مسائل کی تحقیقات کی گئی ہیں۔ ان کی درجہ بندی کا ایک طریقہ ایس ٹی جی کی تفصیلات کی ریاستی جگہ کی نمائندگی کرنے کے لیے استعمال ہونے والے تجزیے کے طریقوں پر مبنی ہے، جیسے کہ واضح ریاستی جگہیں، بنیادی پیٹری نیٹ کا انکشاف، پیٹری نیٹ کا ساختی تجزیہ اور ایس ٹی جی کی براہ راست نقشہ سازی (نحو-براہ راست ترجمہ)۔ یہ نقطہ نظر عام طور پر ترکیب کے الگورتھم کی پیچیدگی اور اس وجہ سے ٹولز کے رن ٹائم سے منسلک ہوتے ہیں۔ دوسری طرف، ان میں سے کچھ تکنیکیں پیٹری جالوں کی کلاس پر کچھ پابندیاں عائد کرتی ہیں۔ مثال کے طور پر، واضح ریاستی جگہ پر مبنی طریقے عام طور پر من مانی پیٹری نیٹ کی قسم کے لیے کام کرتے ہیں، جبکہ کچھ ساختی طریقوں کے لیے ضروری ہے کہ بنیادی پیٹری نیٹ ایک نشان زدہ گراف یا فری چوائس نیٹ ہو۔ مکمل ریاستی کوڈنگ کا مسئلہ سرکٹ کے نفاذ کی ترکیب میں کلیدی معروف مسائل میں سے ایک مکمل ریاستی کوڈنگ (سی ایس سی) ہے۔ اس مسئلے سے نمٹنے کے لیے مختلف طریقے تیار کیے گئے ہیں۔ سی ایس سی اطمینان کے لیے تجزیہ کرنے کا ایک خاص طور پر اصل طریقہ جوڑے کے تعلق کے تصور پر مبنی ہے یا، مساوی طور پر، لاک ریلیشن، جسے الیکس یاکوولیف اور پیٹر وانبیکبرگن نے آزادانہ طور پر تیار کیا ہے۔ ایک اور طریقہ نے خطوں کے نظریہ کا استحصال کیا جو ریاستی گراف میں پیٹری نیٹ کے عناصر کو ریاستوں کے خطوں سے جوڑتا ہے۔ جزوی آرڈرز اور پیٹری نیٹ کے انکشافات پر مبنی سی ایس سی کا پتہ لگانے اور ریزولوشن کے لیے ترکیب کے طریقے الیکس سیمنوف اور وکٹر کھومینکو نے تیار کیے ہیں۔ ان طریقوں نے ورک کرافٹ میں نافذ کردہ سی ایس سی کور پر مبنی سی ایس سی کے مسائل کے موثر تصور کے لیے ایک طریقہ کار کو باقاعدہ بنانے اور نافذ کرنے میں مدد کی ہے۔ ایس ٹی جی پر مبنی ترکیب کے لیے ساختی انکوڈنگ کے طریقے جوزپ کارمونا نے تیار کیے ہیں۔ محدود منطق کے اڈوں میں ترکیب رفتار سے آزاد (یا مساوی طور پر نیم تاخیر سے غیر حساس-کیو ڈی آئی) سرکٹس کی ترکیب میں ایک اہم مسئلہ محدود منطقی بنیاد کے اندر ترکیب ہے، مثال کے طور پر، صرف محدود بیس منطق گیٹس جیسے AND اور OR کا استعمال کرتے ہوئے-مثال کے طور پر، الیکس یاکوولیف کا کام دیکھیں، جہاں E (جوش) کی مستقل مزاجی کی شرط متعارف کرائی گئی تھی تاکہ نفاذ میں خطرے کی آزادی کو یقینی بنایا جا سکے جس میں ایکسائٹیشن افعال کے لیے دو سطحی سم آف پروڈکٹس (ایس او پی) منطق اور دی گئی ایس ٹی جی تفصیلات کے اہم آؤٹ پٹ سگنلز کے لیے ایس آر-لیچز شامل ہیں۔ بعد میں، کام الیکس کونڈراٹیوف اور دیگر نے اس حالت کو مونوٹونک کور کے تصور میں عام کیا، جس نے سافٹ ویئر ٹولز میں اس کا احساس پایا۔ منفی گیٹ بیس، NAND اور NOR میں ترکیب کا مسئلہ زیادہ مشکل ہے۔ اس کے لیے کئی طریقے تیار کیے گئے ہیں، جن میں سے زیادہ تر نیکولے سٹاروڈوبٹسیو کی قیادت میں ہیں۔ ترکیب کے لیے ایس ٹی جیز کی تحلیل بڑے سائز کے ایس ٹی جیز کے لیے ترکیب کی توسیع پذیری کے مسئلے، اور ریاستی خلائی دھماکے کو کم کرنے کی ضروریات کو بنیادی پیٹری نیٹ کی ساختی خصوصیات کے حوالے سے ایس ٹی جیز کے سنکچن کی بنیاد پر طریقوں سے نمٹا گیا ہے-جیسے کہ آزاد انتخاب والے پیٹری نیٹ کو ریاستی مشینوں یا نشان زد گرافوں میں تقسیم کرنے کے طریقے-نیز فین ان سگنل سبسیٹ (سگنل کے لیے محرک واقعات)۔ اسکیل ایبلٹی سے نمٹنے کا ایک اور طریقہ ایس ٹی جی کی غیر متغیر سرکٹس کی براہ راست نقشہ سازی کے ذریعے ہے جس کی ڈینیل سوکولوف نے تحقیقات کی ہے۔ ثالثی کے ساتھ ایس ٹی جی سے ترکیب ایک خاص طور پر چیلنجنگ مسئلہ ثالثوں کے لیے غیر متزلزل سرکٹس کو خود بخود ترکیب کرنا ہے، کیونکہ ان کی ایس ٹی جی کی تفصیلات ان کے بنیادی پیٹری نیٹ میں رویے کے تنازعات پر مشتمل ہوں گی۔ طرز عمل کے تنازعات ان تبدیلیوں کے وجود کو ظاہر کرتے ہیں جو مستقل نہیں ہیں۔ عام طور پر، اس طرح کے ایس ٹی جیز کے منطق پر مبنی نفاذ کے لیے، سرکٹ خطرات کا شکار ہوگا۔ ورک کرافٹ میں خصوصی تکنیکیں جیسے کہ میوٹیکس سگنل ٹرانزیشن کا نیم خودکار اندراج، اصل تفصیلات کو محفوظ رکھنا، تیار اور نافذ کیا گیا ہے۔ مزید پڑھنے کے لیے حوالہ جات نیو کیسل یونیورسٹی اسنکرونس ڈیزائن گروپ پیج گروپ آن الگورتھمز فار وی ایل ایس آئی ڈیزائن آٹومیشن پیج ہارڈ ویئر ڈیزائن اینڈ پیٹری نیٹ، ایڈ: اے یاکوولیف، ایل لاوگنو اینڈ ایل گومز، سپرنگر، 2002 آٹومیٹا (کمپیوٹیشن)