ডিজিটাল সার্কিট/অপ্টিমাইজেশন

অবস্থান হ্রাস করা

যদিও একটি সঠিক পরিকল্পনা করা অবস্থানের মেশিনগুলির একটি দ্ব্যর্থহীন আচরণ রয়েছে, একই আচরণ বাস্তবায়নের জন্য একাধিক উপায় থাকতে পারে। নিচের দুটি এফএসএম বিবেচনা করুন:

সাধারণভাবে বলতে, আমরা এমন একটি এফএসএম এর বাস্তবায়ন খুঁজে পেতে চাই যার অবস্থান সবচেয়ে কম, এবং সেইজন্য সবচেয়ে কম সংস্থান প্রয়োজন হবে, এটি একটি রম(শুধু পাঠযোগ্য মেমরি) যন্ত্র র আকারই হোক বা এফপিজিএ (ফিল্ড-প্রোগ্রামেবল গেট অ্যারে)-তে লজিক এলিমেন্টস (এলইএস) হোক।

তাৎপর্য তালিকা

তাৎপর্য তালিকা হল এফএসএম কমানোর একটি সাধারণ উপায়। এটি একে অপরের অভিন্ন রূপান্তর আছে এমন অবস্থাগুলি খুঁজে বের করে কাজ করে। এটি একটি রৈখিক(গ্রাফিক্যাল) পদ্ধতি যা হাত দ্বারা দ্রুত গণনার জন্য উপযুক্ত।

প্রথমে, এন×এন আকারের একটি গ্রিড বিবেচনা করা যাক, যেখানে এন হল অবস্থার সংখ্যা। প্রতিটি ক্ষুদ্র কক্ষ বা সেল এক জোড়া অবস্থার প্রতিনিধিত্ব করে। যেহেতু এটি একটি অবিন্যস্ত জোড়া, কক্ষ (আই, জে) কক্ষ(জে,আই) এর সমতুল্য, তাই এটিকে বাদ দেওয়া যেতে পারে (সবুজ বর্গক্ষেত্র)। এছাড়াও, অবস্থা অবশ্যই নিজের সমতুল্য (নীল বর্গক্ষেত্র)। তারপরে আমরা উপরের ডান ত্রিভুজ এবং কর্ণটি নির্মূল করতে পারি। একটি সাতটি-অবস্থান যন্ত্রের জন্য, আমাদের নিম্নলিখিত অন্তর্নিহিত চার্টের রূপরেখা থাকবে:

মনে রাখবেন যে প্রতিটি দিকে এন−১ বর্গক্ষেত্র রয়েছে এবং যে কোনও ঘরে, এম<এন।

একটি এফএসএমে উপলব্ধ বিকল্পগুলির একটি সেট থেকে কার্যকরী সিদ্ধান্ত নেওয়া বা অপ্টিমাইজ করা শুরু করার জন্য, আমাদের একটি অবস্থার রূপান্তর টেবিল প্রয়োজন। এই উদাহরণের জন্য, আমরা একটি উদাহরণ হিসাবে এফএসএম নেব যা নিম্নলিখিতগুলি প্রয়োগ করতে পারে:

বর্তমান অবস্থা	পরবর্তী অবস্থা		ফল
	নিবেশ(ইনপুট) এক্স		নিবেশ(ইনপুট) এক্স
	০	১	০	১
০	৭	২	০	০
১	৭	৫	০	০
২	৭	০	১	০
৩	০	৭	১	০
৪	৩	৬	০	০
৫	৩	১	১	০
৬	৩	৪	১	০
৭	৪	৩	১	০

হ্রাস পদ্ধতি

1. তাৎপর্য তালিকা আঁকুন। অবস্থাগুলির প্রতিটি সম্ভাব্য সংমিশ্রণের জন্য আপনার কাছে একটি ঘর রয়েছে। উদ্দেশ্য হল সমস্ত অ-সমতুল্য জোড় অবস্থাগুলিকে নির্মূল করা। নির্মূল হয়েছে এটা বোঝাতে ঘরটি একটি ক্রস(X) দ্বারা 'চিহ্নিত' করা হয়। একবার সমস্ত অ-সমতুল্য অবস্থাগুলি সরানো হলে, অবশিষ্ট অবস্থাগুলি সমতুল্য -জোড়া হবে।
2. প্রথম ধাপ হল তাৎপর্য তালিকার প্রতিটি কক্ষের (সেলের) মধ্য দিয়ে যাওয়া। প্রতিটি কক্ষের (সেলের) জন্য, স্টেট ট্রানজিশন টেবিলে দুটি স্টেট উল্লেখ করুন এবং প্রতিটি ইনপুটের আউটপুট দেখুন।
   • আউটপুট ভিন্ন হলে, ঘরে একটি ক্রস রাখুন। প্রতিটি ইনপুটের জন্য আউটপুট দেখুন - তারা একই হতে হবে। অবস্থাগুলি সমতুল্য হতে পারে না যদি তাদের আলাদা আউটপুট হয়ে থাকে।
   • আউটপুট একই হলে, অবস্থাগুলি সমতুল্য হতে পারে - এটি ঘটবে যদি পরবর্তী অবস্থাগুলিও একই হয়। কক্ষে, সেই ঘর দ্বারা প্রতিনিধিত্ব করা দুটি অবস্থার প্রতিটির পরবর্তী অবস্থা লিখুন। উদাহরণস্বরূপ, যদি কক্ষ বা সেল (২,৫) হয়:

   একটি ইনপুট এক্স=০:এর জন্য অবস্থা ২ → ৭, অবস্থা ৫ → ৩।

   একটি ইনপুট এক্স=১:এর জন্য অবস্থা ২→ ০, অবস্থা ৫ → ১।

   সুতরাং, অতএব, আমরা ঘরের শীর্ষে "৭−৩" লিখি (২,৫) এবং নীচে "০−১"।আমরা প্রতিটি আউটপুটের জন্য পরবর্তী অবস্থা জোড়া লিখছি। নীচের চিত্র ১ এই পর্যায়ের শেষে তাৎপর্য তালিকা দেখায়।

3. পরবর্তী পর্যায়ে আবার চার্টের মধ্য দিয়ে যেতে হয়। এই সময় আমরা প্রতিটি অচিহ্নিত কক্ষে তালিকাভুক্ত অবস্থান জোড়ার দিকে তাকাই।প্রতিটি পরবর্তী-অবস্থান জোড়া আলাদাভাবে বিবেচনা করুন। যদি পরবর্তী-অবস্থান যুগলের প্রতিনিধিত্বকারী ঘরটি চিহ্নিত করা হয়, তবে বর্তমান অবস্থানটিও চিহ্নিত করুন (আপনাকে অবস্থানগুলির ক্রম বিপরীত করতে হতে পারে)। যদি পরবর্তী-রাজ্য যুগলের প্রতিনিধিত্বকারী ঘরটি চিহ্নিত করা হয়, তবে বর্তমান অবস্থানটিও চিহ্নিত করুন (আপনাকে অবস্থানগুলির ক্রম বিপরীত করতে হতে পারে)। যদি পরবর্তী অবস্থান-জোড়াগুলির কোন সমতুল্য না হয় তবে বর্তমান অবস্থান সমতুল্য হতে পারে না। যদি কক্ষে (সেলে) একটি লেখা "আই−আই" থাকে, তাহলে এটিকে উপেক্ষা করুন, কারণ একটি অবস্থানকে অবশ্যই নিজের সমান হতে হবে।

উদাহরণ স্বরূপ:

1. ইনপুট ০ হলে: অবস্থান ৩ → ০, অবস্থান ৫ → ৩।

   ইনপুট ১ হলে: অবস্থান ৩ → ৭, অবস্থান ৫ → ১।

   এখন, অবস্থান ০ ও ৩ সমতুল্য নয় (কল (০,৩) চিহ্নিত করা হয়েছে)। এখন, যদি পরবর্তী অবস্থানগুলি সমতুল্য না হয়, তাহলে বর্তমান অবস্থানও নয়। অতএব, আমরা চিহ্নিত করি (৩,৫)। চিত্র ২তে প্রথম পাসের পরে লাল রঙের নতুন চিহ্নে ফলাফল দেখানো হয়েছে।

2. ধাপ ৩এর পুনরাবৃত্তি করুন যতক্ষণ না আপনি প্রতিটি অচিহ্নিত ঘর চেক করেন এবং তাদের কোনোটিকে চিহ্নিত করতে না পারেন। এই ক্ষেত্রে, এটি ইতিমধ্যে ঘটেছে।
3. এখন, প্রতিটি অচিহ্নিত সেল (আই, জে) দিয়ে অনুসন্ধান করুন। "আই=জে" সমীকরণ লিখুন। আপনি যদি ইতিমধ্যে একটি সমীকরণে একটি পদ রেখে থাকেন এবং অন্যটি না করে থাকেন তবে পরিবর্তে এটিকে সেই সমীকরণে যোগ করুন। এক্ষেত্রে:

   • ০=১=৪
   • ২=৫=৬
   • ৩=৭

4. আমরা এখন রাষ্ট্রীয় মেশিনকে অনেক কম অবস্থানে (আট থেকে তিনটিতে) কমিয়ে দিয়েছি।

চিত্র ১	চিত্র ২

আমরা প্রতিটি সমীকরণ থেকে মাত্র একটি (সমতুল্য) অবস্থা ব্যবহার করে একটি নতুন রাষ্ট্রীয় রূপান্তর সারণী লিখতে পারি - আমরা ০, ২ এবং ৩ বেছে নেব। আপনি কোনটি বেছে নেবেন তা বিবেচ্য নয়, এবং আপনি তাদের পরে পুনরায় সংখ্যা করতে পারেন, কিন্তু সেটা নিয়ে আমরা এখানে মাথা ঘামাবো না।

বর্তমান অবস্থা	পরবর্তী অবস্থা		ফল
	নিবেশ(ইনপুট) এক্স		নিবেশ(ইনপুট) এক্স
	০	১	০	১
০	৩	২	০	০
২	৩	০	১	০
৩	০	৩	১	০