Signal transition graphs
সিগন্যাল ট্রানজিশন গ্রাফ (এস. টি. জি) সাধারণত ইলেকট্রনিক ইঞ্জিনিয়ারিং এবং কম্পিউটার ইঞ্জিনিয়ারিংয়ে অ্যাসিঙ্ক্রোনাস সার্কিটের গতিশীল আচরণ বর্ণনা করতে, তাদের বিশ্লেষণ বা সংশ্লেষণের উদ্দেশ্যে ব্যবহৃত হয়। প্রধান সংজ্ঞা এবং প্রয়োগ অনানুষ্ঠানিকভাবে, একটি এস. টি. জি হল একটি অ্যাসিঙ্ক্রোনাস সার্কিটের আচরণের একটি গ্রাফিকাল বিবরণ যেখানে সংকেতের ঘটনাগুলির মধ্যে কার্যকারণ সম্পর্ক সম্পর্কে তথ্য সরাসরি উপস্থাপিত হয়, অবস্থার উপর ভিত্তি করে বর্ণনার বিপরীতে। এইভাবে, এস. টি. জি সাধারণত সময় রেখাচিত্র দ্বারা প্রতিনিধিত্ব করা একটি বর্তনীর বিবরণকে আনুষ্ঠানিক করতে সহায়তা করে, যাকে কখনও কখনও তরঙ্গ রূপও বলা হয়। পরেরটি বৈদ্যুতিন প্রকৌশলীদের দ্বারা ব্যাপকভাবে ব্যবহৃত হয়। আরও আনুষ্ঠানিকভাবে, একটি এস. টি. জি হল এক ধরনের ব্যাখ্যামূলক (বা লেবেলযুক্ত) পেট্রি নেট যার রূপান্তরগুলি সংকেতের মানগুলির পরিবর্তনের নামগুলির সাথে লেবেল করা হয় (সি. এফ। সংকেত রূপান্তর)। উদাহরণস্বরূপ, লেবেলিংয়ের সাধারণ ক্ষেত্রে সংকেতগুলি বাইনারি হয়, তাই রূপান্তরটিকে বর্তনীতে সংকেতগুলির উত্থান এবং পতনশীল প্রান্ত হিসাবে ব্যাখ্যা করা হয়। এস. টি. জি সাধারণত স্টেট গ্রাফের তুলনায় অ্যাসিঙ্ক্রোনাস সার্কিটের আচরণের আরও সংক্ষিপ্ত বিবরণ দেয়। একটি সার্কিটের একটি এস. টি. জি নির্দিষ্টকরণের জটিলতা সাধারণত সার্কিটের সংকেতের সংখ্যার ক্ষেত্রে রৈখিক হয়, যেখানে একটি স্টেট গ্রাফের জটিলতা তাত্পর্যপূর্ণভাবে বৃদ্ধি পেতে পারে, কারণ অ্যাসিঙ্ক্রোনাস সার্কিটগুলির উচ্চ মাত্রার সমান্তরালতা রয়েছে। এস. টি. জি-তে সমবর্তী ঘটনাগুলি কারণ-ক্রম সম্পর্কের মাধ্যমে প্রতিনিধিত্ব করা হয় (সি. এফ। প্রকৃত সমান্তরাল মুদ্রা) যখন রাজ্য গ্রাফে সমান্তরাল মুদ্রা ইন্টারলিভিংয়ের মাধ্যমে প্রতিনিধিত্ব করা হয়। 1981 সালে লিওনিড রোজেনব্লাম (রাশিয়ান ভাষায়) সিগন্যাল গ্রাফ নামে এস. টি. জি-র প্রথম প্রস্তাব করেন। এগুলি আরও আনুষ্ঠানিকভাবে অধ্যয়ন করা হয়েছিল এবং 1982 সালে অ্যালেক্স ইয়াকোভলেভ তাঁর পিএইচডি থিসিসে (রাশিয়ান ভাষায়) অ্যাসিঙ্ক্রোনাস ইন্টারফেসের নকশায় প্রয়োগ করেছিলেন। এগুলি পরে 1985 সালে দুটি স্বাধীন সূত্রে ইংরেজিতে উপস্থাপন করা হয়েছিল, একটি রোসেনব্লাম এবং ইয়াকোভলেভ দ্বারা এবং অন্যটি তাম-আন চু দ্বারা (একটি পূর্ববর্তী সংস্করণ আই. সি. সি. ডি '85-এ উপস্থাপিত হয়েছিল)। তারপর থেকে, এস. টি. জি তত্ত্ব এবং অনুশীলনে ব্যাপকভাবে অধ্যয়ন করা হয়েছে, যা অ্যাসিঙ্ক্রোনাস কন্ট্রোল সার্কিটগুলির বিশ্লেষণ এবং সংশ্লেষণের জন্য জনপ্রিয় সফ্টওয়্যার সরঞ্জামগুলির বিকাশের দিকে পরিচালিত করেছে, যেমন পেট্রিফি (প্রধান বিকাশকঃ জর্ডি কর্টাডেল্লা) এবং ওয়ার্কক্রাফট (নিউক্যাসল বিশ্ববিদ্যালয়ের একটি টুলকিট)। অ্যাসিঙ্ক্রোনাস সার্কিট ডিজাইনের ক্ষেত্রে এস. টি. জি ব্যবহারের বিভিন্ন উদাহরণের মধ্যে, সবচেয়ে সুপরিচিত হল অ্যাসিঙ্ক্রোনাস ইন্টারফেস, কন্ট্রোলার, আরবিটার্স এবং অ্যানালগ-মিক্সড সিগন্যাল সার্কিট, সি. এফ., অতি সম্প্রতি এস. টি. জি-কে ক্যাপাসিটিভ কাপলিং দ্বারা মধ্যস্থতাকারী কার্যকারণের সাথে জড়িত মডেল কার্যকারণ আচরণে প্রসারিত করা হয়েছে, যেমন সুইচড ক্যাপাসিটর কনভার্টারে (এস. সি. সি) ব্যবহৃত হয়। বাইনারি সিগন্যালের উপর ভিত্তি করে এস. টি. জি ছাড়াও, প্রতীকী এস. টি. জি রয়েছে, যেখানে সংকেত বহু-মূল্যবান হতে পারে। সময় (বিলম্ব) তথ্য টীকা সহ এস. টি. জি প্রথম চালু করা হয়েছিল এবং পরে, যেখানে সময় সীমাবদ্ধতার সাথে সার্কিটের আচরণ বিশ্লেষণের ধারণাগুলি, পরে রিলেটিভ টাইমিং নামে পরিচিত, প্রথম চালু করা হয়েছিল। মৌলিক অন্তর্নিহিত পেট্রি নেট মডেলগুলির বিশেষ সম্প্রসারণ, অ্যাসিঙ্ক্রোনি এবং ইন্টারাপ্টগুলিকে একটি সংক্ষিপ্ত আকারে ক্যাপচার করার জন্য, প্লেস চার্ট নেটগুলিতে চালু করা হয়েছিল। অ্যাসিঙ্ক্রোনাস সার্কিটের রাজ্য-ভিত্তিক মডেল এবং পেট্রি নেট-ভিত্তিক মডেলের (ইনক. এস. টি. জি) মধ্যে একটি গুরুত্বপূর্ণ সংযোগ অঞ্চলগুলির তত্ত্ব (সি. এফ.) ব্যবহারের ক্ষেত্রে প্রতিষ্ঠিত হয়েছে। রবার্ট স্প্রোল, ইভান সাদারল্যান্ড এবং চার্লস মোলনারের কারণে কাউন্টারফ্লো পাইপলাইন প্রসেসরের জন্য একটি এস. টি. জি মডেল এবং এর সার্কিট বাস্তবায়নের জন্য অঞ্চলগুলির তত্ত্ব ব্যবহার করা হয়েছিল। এস. টি. জি-র সঙ্গে ঘনিষ্ঠভাবে সম্পর্কিত মডেলগুলির মধ্যে একটি হল চেঞ্জ ডায়াগ্রাম, যা মাইকেল কিশিনেভস্কি, অ্যালেক্স কোন্দ্রাতিয়েভ, আলেকজান্ডার তৌবিন এবং ভিক্টর ভার্শাভস্কি দ্বারা প্রস্তাবিত। পরিবর্তন রেখাচিত্রগুলির একটি সংক্ষিপ্ত উপায়ে AND এবং OR উভয় কার্যকারণের মডেল তৈরি করতে সক্ষম হওয়ার সুবিধা রয়েছে। কিন্তু পছন্দের ক্ষেত্রে তাদের বর্ণনামূলক ক্ষমতার অভাব রয়েছে। পেট্রি নেট এবং চেঞ্জ ডায়াগ্রামের মধ্যে তুলনা তাদের বর্ণনামূলক শক্তি এবং কার্যকারণ লজিক নেট আকারে তাদের একীকরণের পরিপ্রেক্ষিতে উপস্থাপন করা হয়েছে। এস. টি. জি-গুলিকে বিভিন্ন এইচ. ডি. এল-এর সঙ্গে যুক্ত করা হয়েছে, উদাহরণস্বরূপ ভি. এইচ. ডি. এল (1996) এবং ভেরিলগ (2000)-এর সঙ্গে যুক্ত লিঙ্কগুলি দেখুন যাতে অ্যাসিঙ্ক্রোনাস ডিজাইনকে সমর্থন করা যায়। ভি. এইচ. ডি. এল থেকে সংশ্লেষণ প্রবাহে স্থাপন করা, এস. টি. জি এবং পেট্রি নেটগুলি সহায়ক হিসাবে দেখানো হয়েছে, এবং একইভাবে ভেরিলগের ক্ষেত্রে, যেখানে একটি টুল ভেরিসিন তৈরি করা হয়েছিল। আরও সম্প্রতি এস. টি. জি-কে এমন স্বরলিপির সঙ্গে যুক্ত করা হয়েছে যা ব্যবহারিক হার্ডওয়্যার ডিজাইনারদের জন্য সহজ বলে মনে করা হয়, তাই তরঙ্গ-রূপান্তর গ্রাফের (ডব্লিউ. টি. জি) মডেলের উত্থান ঘটেছে। একইভাবে, এটি উপলব্ধি করে যে ফাইনাইট স্টেট মেশিনের (এফ. এস. এম) মডেল ডিজাইনারদের জন্য পরিচালনা করা সহজ হতে পারে, উদাহরণস্বরূপ, পেট্রি নেট বা এস. টি. জি, ফ্রন্ট-এন্ড হিসাবে বার্স্ট মোড এফ. এস. এম-এর সাথে একটি লিঙ্ক তৈরি করা হয়েছে। বিশ্লেষণ পদ্ধতি এই মুহুর্তে, অ্যাসিঙ্ক্রোনাস সার্কিটগুলির বিশ্লেষণ এবং সংশ্লেষণের জন্য যুক্তিযুক্তভাবে সবচেয়ে কার্যকর পদ্ধতিগুলি পেট্রি নেট আনফোল্ডিংয়ের উপর ভিত্তি করে-সেগুলি ভিক্টর খোমেঙ্কো তাঁর পিএইচডি থিসিসে অধ্যয়ন করেছিলেন। এগুলি ওয়ার্কক্রাফ্টের অধীনে বাস্তবায়িত হয়। অ্যাসিঙ্ক্রোনাস সার্কিটের পেট্রি নেট মডেলের কিছু উপশ্রেণীর কার্যকারিতা বিশ্লেষণ আইগুও জি এবং পিটার বিয়ারেল দ্বারা তদন্ত করা হয়েছে। অ্যাসিঙ্ক্রোনাস সার্কিট সংশ্লেষণ এস. টি. জি নির্দিষ্টকরণ থেকে অ্যাসিঙ্ক্রোনাস সার্কিট সংশ্লেষণের বিভিন্ন সমস্যা তদন্ত করা হয়েছে। তাদের শ্রেণিবিন্যাসের একটি উপায় হল এস. টি. জি নির্দিষ্টকরণের রাষ্ট্রীয় স্থানের প্রতিনিধিত্ব করার জন্য ব্যবহৃত বিশ্লেষণ পদ্ধতির উপর ভিত্তি করে, যেমন স্পষ্ট রাষ্ট্রীয় স্থান, অন্তর্নিহিত পেট্রি নেটের উন্মোচন, পেট্রি নেটের কাঠামোগত বিশ্লেষণ এবং এস. টি. জি-র সরাসরি ম্যাপিং (বাক্য গঠন-সরাসরি অনুবাদ)। এই পদ্ধতিগুলি সাধারণত সংশ্লেষণের অ্যালগরিদমগুলির জটিলতার সাথে যুক্ত এবং তাই, সরঞ্জামগুলির রান-টাইম। অন্যদিকে, এই কৌশলগুলির মধ্যে কয়েকটি পেট্রি জালের শ্রেণীর উপর কিছু সীমাবদ্ধতা আরোপ করে। উদাহরণস্বরূপ, এক্সপ্লিসিট স্টেট স্পেস ভিত্তিক পদ্ধতিগুলি সাধারণত একটি নির্বিচারে পেট্রি নেট প্রকারের জন্য কাজ করে, যেখানে কিছু কাঠামোগত পদ্ধতির জন্য অন্তর্নিহিত পেট্রি নেট একটি চিহ্নিত গ্রাফ বা একটি মুক্ত-পছন্দের নেট হতে হবে। কম্পলিট স্টেট কোডিং সমস্যা সার্কিট বাস্তবায়নের সংশ্লেষণের মূল সুপরিচিত সমস্যাগুলির মধ্যে একটি হল কম্পলিট স্টেট কোডিং (সিএসসি)। এই সমস্যা সমাধানের জন্য বিভিন্ন পদ্ধতি উদ্ভাবন করা হয়েছে। সিএসসি সন্তুষ্টির জন্য বিশ্লেষণ করার একটি বিশেষ মৌলিক উপায় হল অ্যালেক্স ইয়াকোভলেভ এবং পিটার ভ্যানবেকবারগেন দ্বারা স্বাধীনভাবে বিকশিত যুগ্ম সম্পর্ক বা সমতুল্য, লক সম্পর্কের ধারণার উপর ভিত্তি করে। আরেকটি পদ্ধতি অঞ্চলগুলির তত্ত্বকে কাজে লাগায় যা পেট্রি জালের উপাদানগুলিকে রাজ্য গ্রাফের রাজ্যগুলির অঞ্চলের সাথে সংযুক্ত করে। অ্যালেক্স সেমেনোভ এবং ভিক্টর খোমেঙ্কো আংশিক অর্ডার এবং পেট্রি নেট আনফোল্ডিংয়ের উপর ভিত্তি করে সিএসসি সনাক্তকরণ এবং রেজোলিউশনের জন্য সংশ্লেষণ পদ্ধতি তৈরি করেছেন। এই পদ্ধতিগুলি ওয়ার্কক্রাফটে বাস্তবায়িত সিএসসি কোরের উপর ভিত্তি করে সিএসসি সমস্যাগুলির কার্যকর ভিজ্যুয়ালাইজেশনের জন্য একটি পদ্ধতি আনুষ্ঠানিক করতে এবং বাস্তবায়নে সহায়তা করেছে। জোসেপ কারমোনা এস. টি. জি-ভিত্তিক সংশ্লেষণের জন্য কাঠামোগত এনকোডিং পদ্ধতি তৈরি করেছেন। সীমাবদ্ধ যুক্তিবিদ্যার ভিত্তিতে সংশ্লেষণ গতি-স্বাধীন (বা সমতুল্যভাবে আধা-বিলম্ব-সংবেদনশীল-কিউডিআই) সার্কিট সংশ্লেষণের ক্ষেত্রে একটি গুরুত্বপূর্ণ সমস্যা হল একটি সীমাবদ্ধ যৌক্তিক ভিত্তির মধ্যে সংশ্লেষণ, উদাহরণস্বরূপ, AND এবং OR-এর মতো শুধুমাত্র সীমাবদ্ধ বেসিস লজিক গেট ব্যবহার করে-দেখুন, উদাহরণস্বরূপ, অ্যালেক্স ইয়াকোভলেভের কাজ, যেখানে E (উত্তেজনা)-ধারাবাহিকতার শর্তটি প্রয়োগের ক্ষেত্রে বিপদ-স্বাধীনতা নিশ্চিত করার জন্য প্রবর্তন করা হয়েছিল যাতে উত্তেজনা ফাংশনের জন্য দ্বি-স্তরের সাম-অফ-প্রোডাক্ট (এসওপি) যুক্তি এবং প্রদত্ত এস. টি. জি নির্দিষ্টকরণের প্রধান আউটপুট সংকেতগুলির জন্য এস. আর-ল্যাচ থাকে। পরে, অ্যালেক্স কোন্দ্রাতিয়েভ এবং অন্যান্যরা এই শর্তটিকে একঘেয়ে প্রচ্ছদের ধারণায় সাধারণীকরণ করেছিলেন, যা সফ্টওয়্যার সরঞ্জামগুলিতে এর উপলব্ধি খুঁজে পেয়েছিল। আরও চ্যালেঞ্জিং হল নেতিবাচক গেট বেস, NAND এবং NOR-এ সংশ্লেষণের সমস্যা। এর জন্য বেশ কয়েকটি পদ্ধতি তৈরি করা হয়েছে, যার বেশিরভাগই নিকোলাই স্টারোডাউটসেভের নেতৃত্বে। সংশ্লেষণের জন্য এস. টি. জি-র পচন বড় আকারের এস. টি. জি-র জন্য সংশ্লেষণের মাপনীয়তার সমস্যা এবং রাষ্ট্রীয় স্থান বিস্ফোরণ হ্রাস করার প্রয়োজনীয়তা অন্তর্নিহিত পেট্রি নেটের কাঠামোগত বৈশিষ্ট্যগুলির সাথে সম্পর্কিত এস. টি. জি-র সংকোচনের উপর ভিত্তি করে পদ্ধতিতে মোকাবেলা করা হয়েছে-যেমন একটি মুক্ত-পছন্দের পেট্রি নেটকে রাষ্ট্রীয় মেশিন বা চিহ্নিত গ্রাফগুলিতে বিভক্ত করার উপায়-পাশাপাশি ফ্যান-ইন সিগন্যাল উপসেট (একটি সংকেতের জন্য ট্রিগার ইভেন্ট)। স্কেলাবিলিটি মোকাবেলা করার আরেকটি পদ্ধতি হল এস. টি. জি থেকে অ্যাসিঙ্ক্রোনাস সার্কিটের সরাসরি ম্যাপিং যা ড্যানিল সোকোলভ দ্বারা তদন্ত করা হয়েছে। সালিশের সাথে এস. টি. জি থেকে সংশ্লেষণ একটি বিশেষভাবে চ্যালেঞ্জিং সমস্যা হল সালিশকারীদের জন্য অ্যাসিঙ্ক্রোনাস সার্কিটগুলি স্বয়ংক্রিয়ভাবে সংশ্লেষিত করা, কারণ তাদের এস. টি. জি নির্দিষ্টকরণে তাদের অন্তর্নিহিত পেট্রি নেটগুলিতে আচরণগত দ্বন্দ্ব থাকবে। আচরণগত দ্বন্দ্ব এমন পরিবর্তনের অস্তিত্বকে বোঝায় যা স্থায়ী নয়। সাধারণত, এই ধরনের এস. টি. জি-র যুক্তি ভিত্তিক বাস্তবায়নের জন্য, সার্কিটটি ঝুঁকির ঝুঁকিতে থাকবে। ওয়ার্কক্রাফটে আধা-স্বয়ংক্রিয়ভাবে মিউটেক্স সংকেত স্থানান্তর সন্নিবেশ, মূল নির্দিষ্টকরণ সংরক্ষণের মতো বিশেষ কৌশলগুলি তৈরি এবং প্রয়োগ করা হয়েছে। আরও পড়ার তথ্যসূত্র নিউক্যাসল ইউনিভার্সিটি অ্যাসিঙ্ক্রোনাস ডিজাইন গ্রুপ পেজ গ্রুপ অন অ্যালগরিদমস ফর ভিএলএসআই ডিজাইন অটোমেশন পেজ হার্ডওয়্যার ডিজাইন এবং পেট্রি নেট, এডঃ এ. ইয়াকোভলেভ, এল. লাভাগনো এবং এল. গোমেস, স্প্রিঙ্গার, 2002 অটোমাটা (গণনা)