Karnaugh মানচিত্র

Karnaugh মানচিত্র মানুষের প্যাটার্ন-স্বীকৃতি ক্ষমতার সুবিধা গ্রহণ করে ব্যাপক গণনার প্রয়োজনীয়তা হ্রাস করে। এটি সম্ভাব্য জাতি অবস্থার দ্রুত সনাক্তকরণ এবং নির্মূল করার অনুমতি দেয়।
প্রয়োজনীয় বুলিয়ান ফলাফল একটি সত্য সারণী থেকে একটি দ্বি-মাত্রিক গ্রিডে স্থানান্তরিত হয় যেখানে, কার্নাফ মানচিত্রে, কোষগুলিকে গ্রে কোডে ক্রম করা হয়, এবং প্রতিটি কোষের অবস্থান ইনপুট অবস্থার একটি সংমিশ্রণকে উপস্থাপন করে। কোষগুলি মিনটার্ম হিসাবেও পরিচিত, যখন প্রতিটি কোষের মান বুলিয়ান ফাংশনের সংশ্লিষ্ট আউটপুট মানকে প্রতিনিধিত্ব করে। 1s বা 0s-এর সর্বোত্তম গোষ্ঠীগুলি চিহ্নিত করা হয়, যা মূল সত্য সারণীতে যুক্তির একটি ক্যানোনিকাল ফর্মের শর্তগুলিকে উপস্থাপন করে। এই পদগুলি প্রয়োজনীয় যুক্তি উপস্থাপন করে একটি ন্যূনতম বুলিয়ান অভিব্যক্তি লিখতে ব্যবহার করা যেতে পারে।
Karnaugh মানচিত্র বাস্তব-বিশ্বের লজিক প্রয়োজনীয়তা সহজ করার জন্য ব্যবহার করা হয় যাতে তারা লজিক গেটগুলির ন্যূনতম সংখ্যা ব্যবহার করে প্রয়োগ করা যায়। একটি যোগফল-অফ-প্রোডাক্ট এক্সপ্রেশন (SOP) সর্বদা AND গেট ব্যবহার করে একটি OR গেটে ফিডিং প্রয়োগ করা যেতে পারে, এবং একটি পণ্য-অব-সমস এক্সপ্রেশন (POS) OR গেটগুলিকে AND গেট খাওয়ানোর দিকে নিয়ে যায়। POS এক্সপ্রেশন ফাংশনের একটি পরিপূরক দেয় (যদি F ফাংশন হয় তাহলে এর পরিপূরক হবে F')। সফ্টওয়্যার ডিজাইনে লজিক এক্সপ্রেশনগুলিকে সরল করার জন্য কার্নাফ মানচিত্রগুলিও ব্যবহার করা যেতে পারে। বুলিয়ান শর্তাবলী, যেমন শর্তসাপেক্ষ বিবৃতিতে ব্যবহৃত হয়, খুব জটিল হতে পারে, যা কোডটিকে পড়া এবং বজায় রাখা কঠিন করে তোলে। একবার ছোট করা হলে, ক্যানোনিকাল যোগফল-অফ-প্রডাক্ট এবং প্রোডাক্ট-অফ-সাম এক্সপ্রেশন সরাসরি AND এবং OR লজিক অপারেটর ব্যবহার করে প্রয়োগ করা যেতে পারে।
Karnaugh মানচিত্র বুলিয়ান বীজগণিত ফাংশন সরলীকরণ সহজতর করতে ব্যবহার করা হয়. উদাহরণস্বরূপ, নিম্নলিখিত সত্য সারণী দ্বারা বর্ণিত বুলিয়ান ফাংশন বিবেচনা করুন।
বুলিয়ান ভেরিয়েবল , , , এবং তাদের ইনভার্স ব্যবহার করে বুলিয়ান বীজগণিতে একই ফাংশন বর্ণনা করে দুটি ভিন্ন স্বরলিপি নিচে দেওয়া হল।
উপরের উদাহরণে, চারটি ইনপুট ভেরিয়েবলকে 16টি ভিন্ন উপায়ে একত্রিত করা যেতে পারে, তাই সত্য সারণীতে 16টি সারি রয়েছে এবং Karnaugh মানচিত্রে 16টি অবস্থান রয়েছে। Karnaugh মানচিত্র তাই একটি 4 সাজানো হয় × 4 গ্রিড।
সারি এবং কলামের সূচকগুলি (কারনাফ মানচিত্রের উপরে এবং নীচে বাম দিকে দেখানো হয়েছে) বাইনারি সংখ্যাসূচক ক্রমের পরিবর্তে ধূসর কোডে সাজানো হয়েছে। ধূসর কোড নিশ্চিত করে যে প্রতিটি জোড়া সংলগ্ন কক্ষের মধ্যে শুধুমাত্র একটি পরিবর্তনশীল পরিবর্তন। সম্পূর্ণ করা কার্নাফ মানচিত্রের প্রতিটি ঘরে ইনপুটগুলির সংমিশ্রণের জন্য ফাংশনের আউটপুট প্রতিনিধিত্ব করে একটি বাইনারি সংখ্যা রয়েছে।
Karnaugh মানচিত্র তৈরি হওয়ার পরে, এটি সত্য সারণীতে তথ্যের জন্য সবচেয়ে সহজ সম্ভাব্য ফর্মগুলির মধ্যে একটি - একটি ক্যানোনিকাল ফর্ম - খুঁজে পেতে ব্যবহৃত হয়। Karnaugh মানচিত্রে সংলগ্ন 1s অভিব্যক্তিকে সরল করার সুযোগ উপস্থাপন করে। চূড়ান্ত অভিব্যক্তির জন্য মিনটার্মগুলি ('ন্যূনতম পদ') মানচিত্রে 1s-এর গোষ্ঠীকে ঘিরে রেখে পাওয়া যায়। মিনটারম গ্রুপগুলি অবশ্যই আয়তক্ষেত্রাকার হতে হবে এবং একটি ক্ষেত্র অবশ্যই থাকতে হবে যা দুটির শক্তি (যেমন, 1, 2, 4, 8...)। মিনটারম আয়তক্ষেত্রগুলি 0 সেকেন্ড না রেখে যতটা সম্ভব বড় হওয়া উচিত। প্রত্যেককে বড় করার জন্য গ্রুপগুলি ওভারল্যাপ হতে পারে। নীচের উদাহরণে সর্বোত্তম গ্রুপিংগুলি সবুজ, লাল এবং নীল রেখা দ্বারা চিহ্নিত করা হয়েছে এবং লাল এবং সবুজ গোষ্ঠীগুলি ওভারল্যাপ করে৷ লাল গ্রুপ একটি 2 × 2 বর্গক্ষেত্র, সবুজ গ্রুপ একটি 4 × 1 আয়তক্ষেত্র, এবং ওভারল্যাপ এলাকাটি বাদামী রঙে নির্দেশিত।
কোষগুলিকে প্রায়শই একটি সংক্ষিপ্ত হাত দ্বারা চিহ্নিত করা হয় যা কোষটি কভার করে এমন ইনপুটগুলির যৌক্তিক মান বর্ণনা করে। উদাহরণ স্বরূপ, বলতে এমন একটি ঘর বোঝায় যা 2x2 এলাকাকে কভার করে যেখানে এবং সত্য, অর্থাৎ উপরের চিত্রে 13, 9, 15, 11 নম্বরযুক্ত কোষগুলি। অন্যদিকে, মানে সেই কোষগুলি যেখানে সত্য এবং মিথ্যা (অর্থাৎ, সত্য)।
গ্রিড টরয়েডভাবে সংযুক্ত, যার মানে আয়তক্ষেত্রাকার দলগুলি প্রান্ত জুড়ে মোড়ানো হতে পারে (ছবি দেখুন)। চরম ডানদিকের কক্ষগুলি আসলে 'সংলগ্ন' বাম দিকে, এই অর্থে যে সংশ্লিষ্ট ইনপুট মানগুলি শুধুমাত্র এক বিট দ্বারা পৃথক হয়; একইভাবে, খুব উপরের এবং নীচে যারা. অতএব, একটি বৈধ শব্দ হতে পারে—এতে উপরের দিকে 12 এবং 8টি কক্ষ রয়েছে এবং 10 এবং 14 কোষগুলিকে অন্তর্ভুক্ত করার জন্য নীচের অংশে মোড়ানো হয়—যেমন , যার চারটি কোণ রয়েছে।
একবার Karnaugh মানচিত্র তৈরি হয়ে গেলে এবং সংলগ্ন 1গুলি আয়তক্ষেত্রাকার এবং বর্গাকার বাক্স দ্বারা সংযুক্ত হলে, প্রতিটি বাক্সের মধ্যে কোন ভেরিয়েবলগুলি একই থাকে তা পরীক্ষা করে বীজগণিতীয় মিনটারগুলি পাওয়া যাবে।
লাল দলের জন্য:
এইভাবে বুলিয়ান যোগফল-উৎপাদনের অভিব্যক্তিতে প্রথম মিনটার্ম হল 
সবুজ গ্রুপিংয়ের জন্য, "A" এবং "B" একই অবস্থা বজায় রাখে, যখন "C" এবং "D" পরিবর্তন হয়। "B" হল 0 এবং এটি অন্তর্ভুক্ত করার আগে বাতিল করতে হবে। দ্বিতীয় পদটি তাই মনে রাখবেন যে এটি গ্রহণযোগ্য যে সবুজ গ্রুপিং লাল রঙের সাথে ওভারল্যাপ করে।
একইভাবে, নীল গ্রুপিং শব্দটি দেয়।
প্রতিটি গ্রুপিংয়ের সমাধানগুলি একত্রিত হয়: সার্কিটের স্বাভাবিক ফর্ম formula_5 .
এইভাবে Karnaugh মানচিত্র একটি সরলীকরণ নির্দেশিত হয়েছে
বুলিয়ান বীজগণিতের স্বতঃসিদ্ধগুলিকে সাবধানতার সাথে প্রয়োগ করার মাধ্যমে এই সরলীকরণটি অর্জন করাও সম্ভব হত, তবে এটি করতে যে সময় লাগে তা পদের সংখ্যার সাথে দ্রুতগতিতে বৃদ্ধি পায়।
একটি ফাংশনের বিপরীতটি একইভাবে 0s এর পরিবর্তে গোষ্ঠীবদ্ধ করে সমাধান করা হয়।
বিপরীতটি কভার করার জন্য তিনটি পদ বিভিন্ন রঙের সীমানা সহ ধূসর বাক্সে দেখানো হয়েছে:
এটি বিপরীত ফল দেয়:
ডি মরগানের আইন ব্যবহারের মাধ্যমে, রাশির গুণফল নির্ধারণ করা যেতে পারে:
arnaugh মানচিত্রগুলি ফাংশনগুলিকে সহজে ন্যূনতমকরণের অনুমতি দেয় যার সত্য সারণীতে " কেয়ার নেই " শর্তগুলি অন্তর্ভুক্ত রয়েছে। একটি "যত্ন করবেন না" শর্ত হল ইনপুটগুলির একটি সংমিশ্রণ যার জন্য ডিজাইনার আউটপুট কী তা বিবেচনা করেন না। অতএব, "যত্ন করবেন না" শর্তগুলি যে কোনও আয়তক্ষেত্রাকার গোষ্ঠীতে অন্তর্ভুক্ত বা বাদ দেওয়া যেতে পারে, যেটি এটিকে বড় করে তোলে। এগুলি সাধারণত একটি ড্যাশ বা এক্স দিয়ে মানচিত্রে নির্দেশিত হয়।
ডানদিকের উদাহরণটি উপরের উদাহরণের মতোই কিন্তু "f" (1,1,1,1) এর মান দিয়ে প্রতিস্থাপিত হয়েছে "কোন যত্ন নেই"। এটি লাল শব্দটিকে নীচের দিকে প্রসারিত করতে দেয় এবং এইভাবে, সবুজ শব্দটিকে সম্পূর্ণরূপে সরিয়ে দেয়।
এটি নতুন সর্বনিম্ন সমীকরণ প্রদান করে:
উল্লেখ্য যে প্রথম পদটি শুধু , নয়। এই ক্ষেত্রে, ডোন্ট কেয়ার একটি শব্দ বাদ দিয়েছে (সবুজ আয়তক্ষেত্র); সরলীকৃত অন্য (লাল এক); এবং রেস হ্যাজার্ড রিমুভ করে (হলুদ শব্দটি অপসারণ করা যা রেসের বিপদের উপর নিম্নলিখিত বিভাগে দেখানো হয়েছে)।
বিপরীত ক্ষেত্রে নিম্নরূপ সরলীকৃত করা হয়:
ডি মরগানের আইন ব্যবহারের মাধ্যমে, রাশির গুণফল নির্ধারণ করা যেতে পারে:
কার্নৌ মানচিত্র জাতিগত অবস্থা সনাক্তকরণ এবং নির্মূল করার জন্য কার্যকর। কার্নৌ মানচিত্র ব্যবহার করে জাতিগত ঝুঁকিগুলি সনাক্ত করা খুব সহজ, কারণ মানচিত্রে সীমাবদ্ধ সংলগ্ন, কিন্তু বিচ্ছিন্ন, অঞ্চলগুলির যেকোনো জোড়ার মধ্যে চলাচলের সময় একটি জাতিগত অবস্থা বিদ্যমান থাকতে পারে। তবে, গ্রে কোডিংয়ের প্রকৃতির কারণে, উপরে বর্ণিত "সংযোজনের" একটি বিশেষ সংজ্ঞা রয়েছে - আমরা আসলে একটি আয়তক্ষেত্রের পরিবর্তে একটি টরাসের উপর দিয়ে এগিয়ে যাচ্ছি, যা উপরে, নীচে এবং পাশে মোড়ানো।
আসলেই কোনও সমস্যা হবে কিনা তা বাস্তবায়নের ভৌত প্রকৃতির উপর নির্ভর করে এবং আমাদের এটি নিয়ে চিন্তা করার দরকার কিনা তা প্রয়োগের উপর নির্ভর করে। ক্লকড লজিকে, টাইমিং ডেডলাইন পূরণের জন্য লজিকটি সময়ের মধ্যে কাঙ্ক্ষিত মানের উপর স্থির হওয়া যথেষ্ট। আমাদের উদাহরণে, আমরা ক্লকড লজিক বিবেচনা করছি না।
আমাদের ক্ষেত্রে, একটি অতিরিক্ত মেয়াদ formula_12 সবুজ এবং নীল আউটপুট অবস্থা বা নীল এবং লাল আউটপুট অবস্থাগুলির মধ্যে সেতুবন্ধন করে সম্ভাব্য জাতিগত ঝুঁকি দূর করবে: এটি সংলগ্ন চিত্রে হলুদ অঞ্চল (যা নীচে থেকে ডান অর্ধেকের উপরে মোড়ানো) হিসাবে দেখানো হয়েছে।
সিস্টেমের স্থির যুক্তির পরিপ্রেক্ষিতে এই শব্দটি অপ্রয়োজনীয়, কিন্তু জাতি-মুক্ত গতিশীল কর্মক্ষমতা নিশ্চিত করার জন্য এই ধরনের অপ্রয়োজনীয়, বা ঐক্যমত্যের শব্দগুলি প্রায়শই প্রয়োজন হয়।
একইভাবে, একটি অতিরিক্ত মেয়াদ formula_13 আরেকটি সম্ভাব্য জাতিগত ঝুঁকি দূর করার জন্য বিপরীতে যোগ করতে হবে। ডি মরগানের সূত্র প্রয়োগ করলে "f এর" জন্য যোগফলের আরেকটি গুণফল তৈরি হয়, কিন্তু একটি নতুন গুণনীয়ক সহ formula_14 .
নিম্নলিখিত সমস্ত সম্ভাব্য 2-চলক, 2 × ২টি কার্নৌ মানচিত্র। প্রতিটির সাথে তালিকাভুক্ত করা হয়েছে মিনটার্মগুলিকে একটি ফাংশন হিসেবে formula_15 এবং জাতিগত ঝুঁকিমুক্ত ( "পূর্ববর্তী বিভাগ দেখুন" ) ন্যূনতম সমীকরণ। একটি মিনটার্মকে এমন একটি রাশি হিসেবে সংজ্ঞায়িত করা হয় যা ম্যাপ করা ভেরিয়েবলের সবচেয়ে ন্যূনতম রূপের রাশি প্রদান করে। সমস্ত সম্ভাব্য অনুভূমিক এবং উল্লম্ব আন্তঃসংযুক্ত ব্লক তৈরি করা যেতে পারে। এই ব্লকগুলি অবশ্যই 2 (1, 2, 4, 8, 16, 32, ...) এর ঘাতের আকারের হতে হবে। এই এক্সপ্রেশনগুলি বাইনারি এক্সপ্রেশনগুলিকে ম্যাপ করার জন্য ন্যূনতম লজিক ভেরিয়েবল এক্সপ্রেশনগুলির একটি ন্যূনতম লজিকাল ম্যাপিং তৈরি করে। এখানে একটি ক্ষেত্র সহ সমস্ত ব্লক রয়েছে।
চার্টের নীচে, উপরে, বাম বা ডানে একটি ব্লক চালিয়ে যাওয়া যেতে পারে। ভেরিয়েবল মিনিমাইজেশনের জন্য এটি চার্টের প্রান্তের বাইরেও মোড়ানো যেতে পারে। এর কারণ হল প্রতিটি লজিক ভেরিয়েবল প্রতিটি উল্লম্ব কলাম এবং অনুভূমিক সারির সাথে মিলে যায়। k-মানচিত্রের একটি দৃশ্যায়নকে নলাকার হিসেবে বিবেচনা করা যেতে পারে। বাম এবং ডান দিকের প্রান্তের ক্ষেত্রগুলি সংলগ্ন, এবং উপরের এবং নীচের অংশগুলি সংলগ্ন। চারটি ভেরিয়েবলের জন্য K-মানচিত্রগুলিকে ডোনাট বা টরাস আকৃতি হিসাবে চিত্রিত করতে হবে। k-মানচিত্র দ্বারা অঙ্কিত বর্গক্ষেত্রের চারটি কোণ সংলগ্ন। ৫টি এবং তার বেশি ভেরিয়েবলের জন্য আরও জটিল মানচিত্রের প্রয়োজন।
সম্পর্কিত গ্রাফিক্যাল মিনিমাইজেশন পদ্ধতিগুলির মধ্যে রয়েছে: