লজিক গেট/কার্নো মানচিত্র

কার্নো মানচিত্র হলো বুলিয়ান বীজগণিতের রাশি সরলীকরণের একটি চিত্রভিত্তিক পদ্ধতি। ১৯৫৩ সালে বেল ল্যাবসের প্রকৌশলী মরিস কার্নো এই পদ্ধতি উদ্ভাবন করেন। ডিজিটাল বর্তনী নকশায় এটি অত্যন্ত গুরুত্বপূর্ণ, কারণ এর মাধ্যমে জটিল বুলিয়ান রাশিকে সহজে সরল করা যায় এবং কম সংখ্যক লজিক গেট ব্যবহার করে বর্তনী তৈরি করা যায়।

কার্নো মানচিত্র কেন দরকার?

ধরো তোমার কাছে একটি জটিল বুলিয়ান রাশি আছে:

$F=\overline{A}\overline{B}C+\overline{A}BC+A\overline{B}C+ABC$

এটি দেখে বোঝাই কঠিন, আর এত গেট দিয়ে সার্কিট বানানো ব্যয়বহুলও। কিন্তু কার্নো মানচিত্র ব্যবহার করলে এটি সহজে সরল হয়ে যায়:

$F=C$

শুধু একটি তার! কোনো গেটই লাগে না। এটাই কার্নো মানচিত্রের জাদু।

মূল ধারণা: গ্রে কোড

কার্নো মানচিত্রের সবচেয়ে গুরুত্বপূর্ণ বৈশিষ্ট্য হলো এর বিশেষ বিন্যাস। সাধারণ বাইনারি গণনায় আমরা লিখি:

$\text{০০}\to \text{০১}\to \text{১০}\to \text{১১}$

এখানে $\text{০১}$ থেকে $\text{১০}$-এ যাওয়ার সময় দুটি চলক একসাথে বদলায়। কিন্তু কার্নো মানচিত্রে গ্রে কোড ব্যবহার করা হয়:

$\text{০০}\to \text{০১}\to \text{১১}\to \text{১০}$

এখানে প্রতিটি ধাপে মাত্র একটি চলক বদলায়। এই বৈশিষ্ট্যের কারণে পাশাপাশি দুটি ঘরকে একত্রিত করলে একটি চলক বাদ পড়ে যায় এবং রাশি সরল হয়।

সহজ উদাহরণ: ধরো দুটি ঘর পাশাপাশি আছে। একটিতে $AB=\text{০১}$ এবং অন্যটিতে $AB=\text{১১}$। এখানে $B$ সবসময় $\text{১}$, শুধু $A$ বদলাচ্ছে। তাই এই দুটি ঘর একত্রিত করলে $A$ বাদ পড়ে এবং শুধু $B$ থাকে।

মিনটার্ম কী?

বুলিয়ান ফাংশনের প্রতিটি সম্ভাব্য ইনপুট সমন্বয়কে মিনটার্ম বলে। দুটি চলক $A$ ও $B$ থাকলে চারটি মিনটার্ম হবে:

মিনটার্ম সারণী

মিনটার্ম নম্বর	$A$	$B$	বুলিয়ান রাশি
$m_0$	$\text{০}$	$\text{০}$	$\overline{A}\overline{B}$
$m_1$	$\text{০}$	$\text{১}$	$\overline{A}B$
$m_2$	$\text{১}$	$\text{০}$	$A\overline{B}$
$m_3$	$\text{১}$	$\text{১}$	$AB$

মিনটার্ম নম্বরটি আসলে ইনপুটের বাইনারি মানকে দশমিকে রূপান্তর করলে যা পাওয়া যায়। যেমন $AB=\text{১০}$ মানে দশমিকে $\text{২}$, তাই এটি $m_2$।

দুই চলকের কার্নো মানচিত্র

দুই চলকের জন্য কার্নো মানচিত্রে মোট ${\text{২}}^{\text{২}}=\text{৪}$টি ঘর থাকে।

দুই চলকের কার্নো মানচিত্রের কাঠামো

$A\mathrm{\setminus }B$	$B=\text{০}$	$B=\text{১}$
$A=\text{০}$	$m_0$	$m_1$
$A=\text{১}$	$m_2$	$m_3$

এই মানচিত্রে:

• বাম থেকে ডানে গেলে $B$-এর মান $\text{০}$ থেকে $\text{১}$ হয়
• উপর থেকে নিচে গেলে $A$-এর মান $\text{০}$ থেকে $\text{১}$ হয়
• প্রতিটি ঘরে সংশ্লিষ্ট মিনটার্মের ফাংশন মান ($\text{০}$ বা $\text{১}$) বসানো হয়

উদাহরণ: দুই চলকের ফাংশন

$F(A,B)=\mathrm{\Sigma }(1,2,3)$ অর্থ $m_1,m_2,m_3$ মিনটার্মে $F=\text{১}$।

কার্নো মানচিত্রে মান বসানো

$A\mathrm{\setminus }B$	$\text{০}$	$\text{১}$
$\text{০}$	$\text{০}$	$\text{১}$
$\text{১}$	$\text{১}$	$\text{১}$

এখন দলবদ্ধ করা যাক:

• ডান কলামের দুটি ঘর ($m_1,m_3$): এখানে $B=\text{১}$ সবসময়, $A$ বদলাচ্ছে → দল দেয় $B$
• নিচের সারির দুটি ঘর ($m_2,m_3$): এখানে $A=\text{১}$ সবসময়, $B$ বদলাচ্ছে → দল দেয় $A$

সুতরাং: $F=A+B$

তিন চলকের কার্নো মানচিত্র

তিন চলকের জন্য মোট ${\text{২}}^{\text{৩}}=\text{৮}$টি ঘর থাকে। এখানে একটি অক্ষে একটি চলক ($A$) এবং অন্য অক্ষে দুটি চলক ($BC$) থাকে।

তিন চলকের কার্নো মানচিত্রের কাঠামো

$A$	$BC$
	$\text{০০}$	$\text{০১}$	$\text{১১}$	$\text{১০}$
$\text{০}$	$m_0$	$m_1$	$m_3$	$m_2$
$\text{১}$	$m_4$	$m_5$	$m_7$	$m_6$

গুরুত্বপূর্ণ লক্ষ্য করো: কলামের ক্রম হলো $\text{০০, ০১, ১১, ১০}$ — এটি সাধারণ বাইনারি ক্রম নয়! এটি গ্রে কোড। তৃতীয় ও চতুর্থ কলাম উল্টো মনে হলেও এই বিন্যাসই নিশ্চিত করে যে পাশাপাশি যেকোনো দুটি ঘরে মাত্র একটি চলক বদলায়।

মিনটার্ম নম্বর কীভাবে বসে?

প্রতিটি ঘরের মিনটার্ম নম্বর নির্ণয় করা হয় সেই ঘরের সারি ও কলামের বিট একত্রিত করে:

• $A=\text{০}$ এবং $BC=\text{১১}$ → বিট একত্রে $\text{০১১}$ → দশমিকে $\text{৩}$ → $m_3$
• $A=\text{১}$ এবং $BC=\text{১০}$ → বিট একত্রে $\text{১১০}$ → দশমিকে $\text{৬}$ → $m_6$

উদাহরণ: তিন চলকের ফাংশন

$F(A,B,C)=\mathrm{\Sigma }(1,3,5,7)$ সরল করো।

প্রথমে মানচিত্রে $\text{১}$ বসাই:

কার্নো মানচিত্রে মান বসানো

$A$	$BC$
	$\text{০০}$	$\text{০১}$	$\text{১১}$	$\text{১০}$
$\text{০}$	$\text{০}$	$\text{১}$	$\text{১}$	$\text{০}$
$\text{১}$	$\text{০}$	$\text{১}$	$\text{১}$	$\text{০}$

এখন দলবদ্ধকরণ: মাঝের দুটি কলামের সব চারটি ঘর ($m_1,m_3,m_5,m_7$) একটি বড় দল তৈরি করে।

এই দলে:

• $A$: $\text{০}$ এবং $\text{১}$ উভয়ই আছে → $A$ বাদ পড়ে
• $B$: $\text{০}$ এবং $\text{১}$ উভয়ই আছে → $B$ বাদ পড়ে
• $C$: সবসময় $\text{১}$ → $C$ থাকে

সুতরাং: $F=C$

চার চলকের কার্নো মানচিত্র

চার চলকের জন্য মোট ${\text{২}}^{\text{৪}}=\text{১৬}$টি ঘর থাকে। এখানে উভয় অক্ষে দুটি করে চলক থাকে।

চার চলকের কার্নো মানচিত্রের কাঠামো

$AB$	$CD$
	$\text{০০}$	$\text{০১}$	$\text{১১}$	$\text{১০}$
$\text{০০}$	$m_0$	$m_1$	$m_3$	$m_2$
$\text{০১}$	$m_4$	$m_5$	$m_7$	$m_6$
$\text{১১}$	$m_{12}$	$m_{13}$	$m_{15}$	$m_{14}$
$\text{১০}$	$m_8$	$m_9$	$m_{11}$	$m_{10}$

লক্ষ্য করো: সারির ক্রমও গ্রে কোড অনুযায়ী: $\text{০০, ০১, ১১, ১০}$। তৃতীয় সারি $\text{১১}$ এবং চতুর্থ সারি $\text{১০}$ — এটি উল্টো মনে হলেও নিয়ম মেনেই বসানো।

উদাহরণ: চার চলকের ফাংশন

$F(A,B,C,D)=\mathrm{\Sigma }(0,2,8,10)$ সরল করো।

কার্নো মানচিত্রে মান বসানো

$AB$	$CD$
	$\text{০০}$	$\text{০১}$	$\text{১১}$	$\text{১০}$
$\text{০০}$	$\mathrm{𝟏}$	$\text{০}$	$\text{০}$	$\mathrm{𝟏}$
$\text{০১}$	$\text{০}$	$\text{০}$	$\text{০}$	$\text{০}$
$\text{১১}$	$\text{০}$	$\text{০}$	$\text{০}$	$\text{০}$
$\text{১০}$	$\mathrm{𝟏}$	$\text{০}$	$\text{০}$	$\mathrm{𝟏}$

এখানে চারটি কোণের ঘর ($m_0,m_2,m_8,m_{10}$) একটি দল তৈরি করে।

এই দলে:

• $A$: $\text{০}$ এবং $\text{১}$ উভয়ই → বাদ পড়ে
• $B$: সবসময় $\text{০}$ → $\overline{B}$ থাকে
• $C$: $\text{০}$ এবং $\text{১}$ উভয়ই → বাদ পড়ে
• $D$: সবসময় $\text{০}$ → $\overline{D}$ থাকে

সুতরাং: $F=\overline{B}\overline{D}$

দলবদ্ধকরণের বিস্তারিত নিয়ম

নিয়ম ১: দলের আকার

দলে ঘরের সংখ্যা অবশ্যই $2^n$ আকারের হতে হবে, অর্থাৎ $\text{১, ২, ৪, ৮, ১৬}$।

দলের আকার ও চলক বাদ পড়ার সম্পর্ক

দলের ঘর সংখ্যা	বাদ পড়া চলকের সংখ্যা
$\text{১}$ (একা)	$\text{০}$টি চলক বাদ পড়ে
$\text{২}$	$\text{১}$টি চলক বাদ পড়ে
$\text{৪}$	$\text{২}$টি চলক বাদ পড়ে
$\text{৮}$	$\text{৩}$টি চলক বাদ পড়ে
$\text{১৬}$	$\text{৪}$টি চলক বাদ পড়ে

দল যত বড়, তত বেশি চলক বাদ পড়ে, রাশি তত সরল হয়। তাই সবসময় যত বড় সম্ভব দল তৈরি করতে হবে।

নিয়ম ২: সবচেয়ে বড় দল তৈরি করো

যদি একটি ঘরকে ২টি বা ৪টি উভয় আকারের দলে রাখা সম্ভব হয়, তাহলে সবসময় ৪টির দল বেছে নিতে হবে। ছোট দল রেখে বড় দল না নেওয়া একটি সাধারণ ভুল।

নিয়ম ৩: একটি ঘর একাধিক দলে থাকতে পারে

এটি বীজগণিতের সাথে সামঞ্জস্যপূর্ণ কারণ বুলিয়ান বীজগণিতে $A+A=A$। একটি ঘরকে যতবার দরকার ব্যবহার করা যাবে।

নিয়ম ৪: মানচিত্র গোলাকার

কার্নো মানচিত্রকে একটি গোলাকার পৃষ্ঠ মনে করতে হবে। বাম প্রান্ত ও ডান প্রান্ত পরস্পরের প্রতিবেশী, উপরের প্রান্ত ও নিচের প্রান্তও পরস্পরের প্রতিবেশী।

উদাহরণ হিসেবে চার চলকের মানচিত্রে:

• প্রথম কলাম ($CD=\text{০০}$) এবং শেষ কলাম ($CD=\text{১০}$) পাশাপাশি গণ্য হয়
• প্রথম সারি ($AB=\text{০০}$) এবং শেষ সারি ($AB=\text{১০}$) পাশাপাশি গণ্য হয়

নিয়ম ৫: তির্যক ঘর পাশাপাশি নয়

শুধুমাত্র অনুভূমিক ও উল্লম্বভাবে পাশাপাশি ঘরগুলো প্রতিবেশী। কোণাকোণি বা তির্যক ঘর কখনো পাশাপাশি গণ্য হয় না।

নিয়ম ৬: প্রতিটি ১-ঘর অন্তত একটি দলে থাকতে হবে

কোনো $\text{১}$ মানের ঘর বাদ দেওয়া যাবে না। প্রতিটি $\text{১}$-ঘরকে কোনো না কোনো দলে অন্তর্ভুক্ত করতে হবে।

নিয়ম ৭: অপ্রয়োজনীয় দল এড়াতে হবে

যদি কোনো দলের সব ঘর ইতিমধ্যে অন্য দলে ঢাকা থাকে, তাহলে সেই দল না নেওয়াই ভালো। অতিরিক্ত দল রাশি জটিল করে।

দল থেকে রাশি বের করার পদ্ধতি

একটি দল থেকে রাশি বের করার ধাপগুলো:

ধাপ ১: দলের ঘরগুলোতে প্রতিটি চলকের মান দেখো।

ধাপ ২: যে চলকের মান পুরো দলে একই থাকে সেই চলক রাশিতে থাকবে।

ধাপ ৩: যে চলকের মান দলের মধ্যে বদলায় (কখনো $\text{০}$, কখনো $\text{১}$) সেই চলক বাদ পড়বে।

ধাপ ৪: যে চলক থাকে, সেটি সরাসরি লেখো যদি তার মান $\text{১}$ হয়, পরিপূরক ($\overline{}$) লেখো যদি মান $\text{০}$ হয়।

উদাহরণ: একটি দলে $AB=\text{০১}$ এবং $AB=\text{১১}$ আছে।

• $A$: একবার $\text{০}$, একবার $\text{১}$ → বাদ পড়ে
• $B$: সবসময় $\text{১}$ → $B$ থাকে

রাশি: $B$

ধাপে ধাপে সম্পূর্ণ উদাহরণ

উদাহরণ ১: সহজ তিন চলকের ফাংশন

$F(A,B,C)=\mathrm{\Sigma }(0,2,4,6)$ সরল করো।

ধাপ ১: মানচিত্র আঁকো এবং ১ বসাও।

$A$	$BC$
	$\text{০০}$	$\text{০১}$	$\text{১১}$	$\text{১০}$
$\text{০}$	$\mathrm{𝟏}$	$\text{০}$	$\text{০}$	$\mathrm{𝟏}$
$\text{১}$	$\mathrm{𝟏}$	$\text{০}$	$\text{০}$	$\mathrm{𝟏}$

ধাপ ২: দলবদ্ধ করো।

চারটি ঘর ($m_0,m_2,m_4,m_6$) একটি বড় দল তৈরি করে। এগুলো প্রথম ও শেষ কলামে আছে — মানচিত্র গোলাকার হওয়ায় এরা পাশাপাশি।

ধাপ ৩: রাশি বের করো।

• $A$: $\text{০}$ এবং $\text{১}$ উভয়ই → বাদ পড়ে
• $B$: সবসময় $\text{০}$ → $\overline{B}$ থাকে
• $C$: $\text{০}$ এবং $\text{১}$ উভয়ই → বাদ পড়ে

ফলাফল: $F=\overline{B}$

উদাহরণ ২: একাধিক দলের ফাংশন

$F(A,B,C)=\mathrm{\Sigma }(0,1,2,4,5,6)$ সরল করো।

ধাপ ১: মানচিত্রে মান বসাও।

$A$	$BC$
	$\text{০০}$	$\text{০১}$	$\text{১১}$	$\text{১০}$
$\text{০}$	$\mathrm{𝟏}$	$\mathrm{𝟏}$	$\text{০}$	$\mathrm{𝟏}$
$\text{১}$	$\mathrm{𝟏}$	$\mathrm{𝟏}$	$\text{০}$	$\mathrm{𝟏}$

ধাপ ২: দলবদ্ধ করো।

• দল ১: $m_0,m_1,m_4,m_5$ (বাম দুটি কলামের সব ঘর) → চারটির দল
• দল ২: $m_0,m_2,m_4,m_6$ (প্রথম ও শেষ কলামের সব ঘর, মানচিত্র গোলাকার) → চারটির দল

মনে রাখো: $m_0$ এবং $m_4$ উভয় দলেই আছে — এটি বৈধ।

ধাপ ৩: প্রতিটি দল থেকে রাশি বের করো।

দল ১ ($m_0,m_1,m_4,m_5$):

• $A$: বদলায় → বাদ
• $B$: সবসময় $\text{০}$ → $\overline{B}$
• $C$: বদলায় → বাদ

→ রাশি: $\overline{B}$

দল ২ ($m_0,m_2,m_4,m_6$):

• $A$: বদলায় → বাদ
• $B$: বদলায় → বাদ
• $C$: সবসময় $\text{০}$ → $\overline{C}$

→ রাশি: $\overline{C}$

ফলাফল: $F=\overline{B}+\overline{C}$

উদাহরণ ৩: চার চলকের জটিল ফাংশন

$F(A,B,C,D)=\mathrm{\Sigma }(4,5,6,7,12,13,14,15)$ সরল করো।

ধাপ ১: মানচিত্রে মান বসাও।

$AB$	$CD$
	$\text{০০}$	$\text{০১}$	$\text{১১}$	$\text{১০}$
$\text{০০}$	$\text{০}$	$\text{০}$	$\text{০}$	$\text{০}$
$\text{০১}$	$\mathrm{𝟏}$	$\mathrm{𝟏}$	$\mathrm{𝟏}$	$\mathrm{𝟏}$
$\text{১১}$	$\mathrm{𝟏}$	$\mathrm{𝟏}$	$\mathrm{𝟏}$	$\mathrm{𝟏}$
$\text{১০}$	$\text{০}$	$\text{০}$	$\text{০}$	$\text{০}$

ধাপ ২: দলবদ্ধ করো।

মাঝের দুটি সারির আটটি ঘর ($m_4$ থেকে $m_7$ এবং $m_{12}$ থেকে $m_{15}$) একটি বিশাল দল তৈরি করে।

ধাপ ৩: রাশি বের করো।

• $A$: বদলায় → বাদ
• $B$: সবসময় $\text{১}$ → $B$ থাকে
• $C$: বদলায় → বাদ
• $D$: বদলায় → বাদ

ফলাফল: $F=B$

ডোন্ট কেয়ার অবস্থা

কখনও কখনও কিছু মিনটার্মের মান গুরুত্বপূর্ণ নয় — সেগুলো বাস্তবে কখনো ঘটে না। এসব অবস্থাকে ডোন্ট কেয়ার বলে এবং $X$ বা $d$ দিয়ে প্রকাশ করা হয়।

ডোন্ট কেয়ার কখন ঘটে? উদাহরণ হিসেবে BCD (বাইনারি কোডেড ডেসিমেল) কোডের কথা ভাবো। এখানে চারটি বিট দিয়ে $\text{০}$ থেকে $\text{৯}$ পর্যন্ত সংখ্যা প্রকাশ করা হয়। কিন্তু চারটি বিটে $\text{১০১০}$ থেকে $\text{১১১১}$ পর্যন্ত ছয়টি অতিরিক্ত সমন্বয় আছে যেগুলো BCD-তে কখনো ব্যবহার হয় না। তাই এগুলো ডোন্ট কেয়ার।

ডোন্ট কেয়ার ব্যবহারের নিয়ম

• ডোন্ট কেয়ার ঘরগুলোকে $\text{১}$ ধরে বড় দল তৈরিতে ব্যবহার করা যায়
• ডোন্ট কেয়ার ঘরগুলোকে $\text{০}$ ধরে উপেক্ষাও করা যায়
• সুবিধামতো যেকোনোটা করা যাবে, কারণ এই ঘরগুলোর মান যাই হোক সমস্যা নেই
• তবে একটি ডোন্ট কেয়ার ঘর শুধু দল বড় করতেই ব্যবহার করো, একা দল তৈরি করতে নয়

উদাহরণ: ডোন্ট কেয়ার সহ ফাংশন

$F(A,B,C,D)=\mathrm{\Sigma }(1,3,7,11,15)$, ডোন্ট কেয়ার: $d(0,2,5)$

$AB$	$CD$
	$\text{০০}$	$\text{০১}$	$\text{১১}$	$\text{১০}$
$\text{০০}$	$X$	$\mathrm{𝟏}$	$\mathrm{𝟏}$	$X$
$\text{০১}$	$\text{০}$	$X$	$\mathrm{𝟏}$	$\text{০}$
$\text{১১}$	$\text{০}$	$\text{০}$	$\mathrm{𝟏}$	$\text{০}$
$\text{১০}$	$\text{০}$	$\text{০}$	$\mathrm{𝟏}$	$\text{০}$

ডোন্ট কেয়ার ঘরগুলো ($m_0,m_2,m_5$) ব্যবহার করে দল বড় করা যায়:

• দল ১: $m_1,m_3$ এবং ডোন্ট কেয়ার $m_0,m_2$ → চারটির দল → রাশি: $\overline{A}\overline{B}$
• দল ২: $m_3,m_7,m_{11},m_{15}$ → চারটির দল → রাশি: $CD$

ফলাফল: $F=\overline{A}\overline{B}+CD$

ডোন্ট কেয়ার না ব্যবহার করলে রাশি অনেক জটিল হতো। ডোন্ট কেয়ার ব্যবহার করে দল বড় করা এবং রাশি সরল রাখা কার্নো মানচিত্রের একটি বড় সুবিধা।

বিপরীত প্রান্তের দলবদ্ধকরণ: বিস্তারিত

কার্নো মানচিত্রকে একটি টোরাস (ডোনাটের মতো আকৃতি) ভাবলে বোঝা সহজ হয়। ডান প্রান্ত বাম প্রান্তের সাথে যুক্ত, নিচের প্রান্ত উপরের প্রান্তের সাথে যুক্ত।

অনুভূমিক বিপরীত প্রান্ত

তিন চলকের মানচিত্রে $BC=\text{০০}$ (প্রথম কলাম) এবং $BC=\text{১০}$ (শেষ কলাম) পাশাপাশি। এই দুটিতে $C=\text{০}$ এবং $B$ বদলায়।

উল্লম্ব বিপরীত প্রান্ত

চার চলকের মানচিত্রে $AB=\text{০০}$ (প্রথম সারি) এবং $AB=\text{১০}$ (শেষ সারি) পাশাপাশি। এই দুটিতে $B=\text{০}$ এবং $A$ বদলায়।

চার কোণের দল

চার চলকের মানচিত্রে চার কোণের ঘরগুলো ($m_0,m_2,m_8,m_{10}$) একটি দল তৈরি করতে পারে। এটি অনেকের কাছে আশ্চর্যজনক মনে হয়, কিন্তু বিপরীত প্রান্তের নিয়ম অনুযায়ী এটি বৈধ।

সাধারণ ভুল ও সতর্কতা

সাধারণ ভুল ও সঠিক নিয়ম

ভুল	কেন ভুল	সঠিক নিয়ম
তির্যক ঘরকে পাশাপাশি ধরা	তির্যকভাবে একটি চলক পরিবর্তন হয় না, দুটি হয়	শুধুমাত্র অনুভূমিক ও উল্লম্ব প্রতিবেশী গ্রহণযোগ্য
ছোট দল তৈরি করা যখন বড় সম্ভব	কম চলক বাদ পড়ে, রাশি জটিল থাকে	সম্ভব হলে সবচেয়ে বড় দল তৈরি করতে হবে
বিপরীত প্রান্তকে আলাদা ধরা	মানচিত্র গোলাকার, বিপরীত প্রান্ত সংযুক্ত	বিপরীত প্রান্তের ঘরও পাশাপাশি গণ্য হয়
${\text{২}}^n$ নয় এমন দল তৈরি	বুলিয়ান সরলীকরণ ভুল হবে	দলের ঘরসংখ্যা অবশ্যই $\text{১, ২, ৪, ৮}$ হতে হবে
কোনো $\text{১}$-ঘর বাদ দেওয়া	ফাংশন সঠিক হবে না	প্রতিটি $\text{১}$-ঘর অন্তত একটি দলে থাকতে হবে
অপ্রয়োজনীয় বাড়তি দল নেওয়া	রাশি অকারণে জটিল হয়	বাড়তি দল এড়িয়ে চলো
ডোন্ট কেয়ার একা দলে রাখা	রাশিতে অতিরিক্ত পদ আসে	ডোন্ট কেয়ার শুধু দল বড় করতে ব্যবহার করো

মাল্টার্ম পদ্ধতি: শূন্য দলবদ্ধ করা

এতক্ষণ আমরা $\text{১}$-মানের ঘর দলবদ্ধ করেছি এবং যোগফল-গুণফল (Sum of Products বা SOP) রাশি পেয়েছি। কিন্তু একইভাবে $\text{০}$-মানের ঘর দলবদ্ধ করেও গুণফল-যোগফল (Product of Sums বা POS) রাশি পাওয়া যায়।

$\text{০}$-ঘর দলবদ্ধ করলে পাওয়া রাশি $F$-এর পরিপূরক ($\overline{F}$), তারপর ডি মর্গান প্রয়োগ করলে POS রাশি পাওয়া যায়।

SOP এবং POS — দুটি রাশিই সমকক্ষ, কোনটি ব্যবহার করা হবে তা নির্ভর করে কোনটিতে কম গেট লাগে তার উপর।

কার্নো মানচিত্র ও বুলিয়ান বীজগণিতের সংযোগ

কার্নো মানচিত্র বুঝতে হলে আগে বুলিয়ান বীজগণিতের মূল সূত্রগুলো ভালোভাবে বোঝা দরকার, কারণ কার্নো মানচিত্র আসলে এই সূত্রগুলোকেই চিত্রের আকারে প্রকাশ করে। যখন তুমি দুটি ঘর একসাথে দলবদ্ধ করো, তখন আসলে বুলিয়ান সূত্র প্রয়োগ করছো — শুধু সেটা না দেখে, চোখে দেখে করছো।

বুলিয়ান সূত্রের সাথে কার্নো মানচিত্রের সম্পর্ক

ধরো দুটি মিনটার্ম আছে:

$m_1=\overline{A}B\overline{C}D$ এবং $m_3=\overline{A}BCD$

এদের যোগ করলে:

$\overline{A}B\overline{C}D+\overline{A}BCD=\overline{A}BD(\overline{C}+C)=\overline{A}BD\cdot 1=\overline{A}BD$

এখানে বুলিয়ান সূত্র $X+\overline{X}=1$ ব্যবহার হয়েছে এবং $C$ বাদ পড়ে গেছে। কার্নো মানচিত্রে এই দুটি ঘর পাশাপাশি থাকে (কারণ তারা গ্রে কোডে একধাপ দূরে), এবং তাদের একসাথে দলবদ্ধ করলে স্বয়ংক্রিয়ভাবে $C$ বাদ পড়ে যায়। অর্থাৎ, কার্নো মানচিত্রের দলবদ্ধকরণ প্রক্রিয়াটি আসলে এই বীজগণিতিক সরলীকরণকেই চিত্রে রূপ দিয়েছে।

এইভাবে:

• ২টি ঘরের দল → একবার $X+\overline{X}=1$ প্রয়োগ → ১টি চলক বাদ পড়ে
• ৪টি ঘরের দল → দুইবার $X+\overline{X}=1$ প্রয়োগ → ২টি চলক বাদ পড়ে
• ৮টি ঘরের দল → তিনবার প্রয়োগ → ৩টি চলক বাদ পড়ে

ইউনিভার্সাল গেট দিয়ে বাস্তবায়ন

কার্নো মানচিত্র থেকে পাওয়া SOP রাশি সরাসরি NAND গেট দিয়ে বাস্তবায়ন করা যায়। এটি ডিজিটাল ইলেকট্রনিক্সে অত্যন্ত গুরুত্বপূর্ণ কারণ NAND গেট হলো ইউনিভার্সাল গেট — শুধু NAND দিয়ে যেকোনো লজিক সার্কিট তৈরি করা সম্ভব।

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

$\overline{\overline{X}\cdot \overline{Y}}=X+Y$

অর্থাৎ দুটি NAND গেটের আউটপুটের NAND নেওয়া মানেই OR নেওয়া। এটি NAND-NAND বাস্তবায়ন নামে পরিচিত।

গ্রে কোডের গভীর আলোচনা

গ্রে কোড শুধু কার্নো মানচিত্রেই ব্যবহার হয় না — এটি ডিজিটাল ইলেকট্রনিক্সের আরও অনেক ক্ষেত্রে ব্যবহৃত হয়। গ্রে কোড বোঝা কার্নো মানচিত্রকে আরও গভীরভাবে বুঝতে সাহায্য করে।

গ্রে কোড কী এবং কেন?

গ্রে কোড হলো এমন একটি বাইনারি সংখ্যা পদ্ধতি যেখানে পরপর দুটি সংখ্যার মধ্যে শুধুমাত্র একটি বিট পরিবর্তন হয়। ফ্র্যাঙ্ক গ্রে ১৯৫৩ সালে এই কোড পেটেন্ট করেন।

সাধারণ বাইনারি থেকে গ্রে কোডে রূপান্তর:

বাইনারি থেকে গ্রে কোডে রূপান্তর (৪ বিট)

দশমিক	সাধারণ বাইনারি	গ্রে কোড	পরিবর্তিত বিট সংখ্যা
$0$	$0000$	$0000$	—
$1$	$0001$	$0001$	১টি
$2$	$0010$	$0011$	১টি
$3$	$0011$	$0010$	১টি
$4$	$0100$	$0110$	১টি
$5$	$0101$	$0111$	১টি
$6$	$0110$	$0101$	১টি
$7$	$0111$	$0100$	১টি
$8$	$1000$	$1100$	১টি
$9$	$1001$	$1101$	১টি
$10$	$1010$	$1111$	১টি
$11$	$1011$	$1110$	১টি
$12$	$1100$	$1010$	১টি
$13$	$1101$	$1011$	১টি
$14$	$1110$	$1001$	১টি
$15$	$1111$	$1000$	১টি

লক্ষ্য করো, প্রতিটি পরপর দুটি গ্রে কোডের মধ্যে ঠিক একটি বিট পরিবর্তন হয়। এটি কার্নো মানচিত্রের কলাম বা সারির বিন্যাসে ব্যবহৃত হয় বলেই পাশের যেকোনো দুটি ঘর সর্বদা শুধু একটি চলকে আলাদা।

গ্রে কোড থেকে বাইনারিতে রূপান্তর সূত্র

যদি গ্রে কোডের বিটগুলো হয় $g_{n-1},g_{n-2},\dots ,g_1,g_0$ তবে বাইনারি বিট $b_i$:

$b_{n-1}=g_{n-1}$

$b_i=b_{i+1}\oplus g_i(i<n-1)$

যেখানে $\oplus$ হলো XOR অপারেশন।

কার্নো মানচিত্রে গ্রে কোডের প্রভাব

গ্রে কোড ব্যবহার না করলে পাশের ঘরে দুটি চলক একসাথে বদলাত এবং দলবদ্ধকরণ কখনোই একটি চলক সরাসরি বাদ দিতে পারত না। সাধারণ বাইনারি ক্রমে যদি মানচিত্র বানানো হতো:

ভুল বিন্যাস (সাধারণ বাইনারি): পাশের ঘরে দুটি চলক বদলায়

$A\mathrm{\setminus }BC$	$\text{০০}$	$\text{০১}$	$\text{১০}$	$\text{১১}$
$\text{০}$	$m_0$	$m_1$	$m_2$	$m_3$
$\text{১}$	$m_4$	$m_5$	$m_6$	$m_7$

এই বিন্যাসে $m_1$ ($BC=01$) এবং $m_2$ ($BC=10$) পাশাপাশি কিন্তু এদের মধ্যে $B$ এবং $C$ দুটোই বদলায়। ফলে এদের একসাথে দলবদ্ধ করলে কোনো চলক বাদ পড়বে না — যা সম্পূর্ণ ভুল। তাই গ্রে কোড অপরিহার্য।

মিনটার্ম ও ম্যাক্সটার্ম: বিস্তারিত আলোচনা

ম্যাক্সটার্ম কী?

মিনটার্মের বিপরীত হলো ম্যাক্সটার্ম। মিনটার্ম হলো AND রাশি যেখানে ফাংশনের মান ১, আর ম্যাক্সটার্ম হলো OR রাশি যেখানে ফাংশনের মান ০।

দুটি চলক $A$ ও $B$-এর জন্য ম্যাক্সটার্ম:

ম্যাক্সটার্ম সারণী

ম্যাক্সটার্ম	$A$	$B$	বুলিয়ান রাশি
$M_0$	$\text{০}$	$\text{০}$	$A+B$
$M_1$	$\text{০}$	$\text{১}$	$A+\overline{B}$
$M_2$	$\text{১}$	$\text{০}$	$\overline{A}+B$
$M_3$	$\text{১}$	$\text{১}$	$\overline{A}+\overline{B}$

গুরুত্বপূর্ণ পার্থক্য: মিনটার্মে যেখানে চলকের মান ০, সেখানে পরিপূরক লেখা হয়। ম্যাক্সটার্মে এর উল্টো — যেখানে চলকের মান ১, সেখানে পরিপূরক লেখা হয়।

SOP ও POS রূপান্তর

একটি ফাংশন দুটি উপায়ে প্রকাশ করা যায়:

• মিনটার্মের যোগফল (SOP): $F=\mathrm{\Sigma }m(i,j,k,\dots )$
• ম্যাক্সটার্মের গুণফল (POS): $F=\mathrm{\Pi }M(i,j,k,\dots )$

এই দুটির মধ্যে সম্পর্ক: যদি কোনো মিনটার্ম SOP-এ না থাকে, তবে সেটি POS-এ থাকে।

উদাহরণ: $F=\mathrm{\Sigma }(1,3,5)=\mathrm{\Pi }M(0,2,4,6,7)$ (তিন চলকের ক্ষেত্রে মোট ৮টি মিনটার্ম)

কার্নো মানচিত্রে POS সরলীকরণ

POS রাশি পেতে কার্নো মানচিত্রে $\text{০}$ মানের ঘরগুলো দলবদ্ধ করতে হয়। প্রতিটি দল থেকে একটি ম্যাক্সটার্ম (OR পদ) পাওয়া যায়, এবং সব OR পদের গুণফল হলো POS রাশি।

$\text{০}$ দলবদ্ধকরণের নিয়ম:

• $\text{০}$-ঘর দলবদ্ধ করো (একই নিয়মে: ২ⁿ আকারের দল, সর্বোচ্চ বড় দল)
• প্রতিটি দলে যে চলক সবসময় একই থাকে সেটি নাও, কিন্তু এবার উল্টো: মান ১ হলে পরিপূরক ($\overline{X}$) লেখো, মান ০ হলে সরাসরি ($X$) লেখো
• সব পদকে OR করে একটি ম্যাক্সটার্ম তৈরি করো
• সব ম্যাক্সটার্মকে AND করো

উদাহরণ: $F(A,B,C)=\mathrm{\Sigma }(1,3,5,7)$

$\text{০}$-ঘর: $m_0,m_2,m_4,m_6$

কার্নো মানচিত্রে এই চারটি ঘর একটি বড় দল তৈরি করে:

• $A$: বদলায় → বাদ
• $B$: বদলায় → বাদ
• $C$: সবসময় $\text{০}$ → মান ০ হওয়ায় POS-এ $C$ (পরিপূরক নয়) লেখা হয়

POS রাশি: $F=C$

SOP রাশিও ছিল $F=C$ — দুটো একই, যা প্রমাণ করে উভয় পদ্ধতি সঠিক।

প্রাইম ইমপ্লিক্যান্ট: কার্নো মানচিত্রের কেন্দ্রীয় ধারণা

কার্নো মানচিত্রকে পেশাদারভাবে বুঝতে হলে প্রাইম ইমপ্লিক্যান্ট ধারণাটি জানা অপরিহার্য।

ইমপ্লিক্যান্ট কী?

একটি ইমপ্লিক্যান্ট হলো এমন যেকোনো বৈধ দল (১-ঘরের গ্রুপ) যেটি কার্নো মানচিত্রের নিয়ম মেনে তৈরি। অর্থাৎ প্রতিটি একক ১-ঘরও একটি ইমপ্লিক্যান্ট, প্রতিটি বৈধ জোড়াও ইমপ্লিক্যান্ট।

প্রাইম ইমপ্লিক্যান্ট কী?

প্রাইম ইমপ্লিক্যান্ট হলো এমন একটি ইমপ্লিক্যান্ট যেটিকে আর বড় করা সম্ভব নয় — অর্থাৎ এই দলে আর কোনো ১-ঘর যোগ করা যাবে না। এটি সর্বোচ্চ বড় বৈধ দল।

উদাহরণ: যদি $m_0,m_1,m_4,m_5$ একটি বৈধ চারটির দল হয় এবং এই চারটি ঘরকে অন্য কোনো ১-ঘরের সাথে মিলিয়ে ৮টির দল তৈরি করা না যায়, তবে এটি একটি প্রাইম ইমপ্লিক্যান্ট।

এসেনশিয়াল প্রাইম ইমপ্লিক্যান্ট কী?

এসেনশিয়াল প্রাইম ইমপ্লিক্যান্ট হলো এমন প্রাইম ইমপ্লিক্যান্ট যেটিতে এমন একটি ১-ঘর আছে যেটি অন্য কোনো প্রাইম ইমপ্লিক্যান্টে নেই। এই ঘরটিকে ঢাকতে হলে এই প্রাইম ইমপ্লিক্যান্টটি অবশ্যই নিতে হবে।

কৌশল: সর্বনিম্ন পদের SOP রাশি পেতে সবসময় প্রথমে সব এসেনশিয়াল প্রাইম ইমপ্লিক্যান্ট নাও, তারপর বাকি অনাবৃত ১-ঘর ঢাকার জন্য যত কম সংখ্যক প্রাইম ইমপ্লিক্যান্ট দরকার ততটা নাও।

বিস্তারিত উদাহরণ: প্রাইম ইমপ্লিক্যান্ট খোঁজা

$F(A,B,C,D)=\mathrm{\Sigma }(0,1,2,5,6,7,8,9,10,14)$

ধাপ ১: মানচিত্রে মান বসাও।

$AB$	$CD$
	$\text{০০}$	$\text{০১}$	$\text{১১}$	$\text{১০}$
$\text{০০}$	$\mathrm{𝟏}$	$\mathrm{𝟏}$	$\text{০}$	$\mathrm{𝟏}$
$\text{০১}$	$\text{০}$	$\mathrm{𝟏}$	$\mathrm{𝟏}$	$\mathrm{𝟏}$
$\text{১১}$	$\text{০}$	$\text{০}$	$\text{০}$	$\mathrm{𝟏}$
$\text{১০}$	$\mathrm{𝟏}$	$\mathrm{𝟏}$	$\text{০}$	$\mathrm{𝟏}$

ধাপ ২: সমস্ত প্রাইম ইমপ্লিক্যান্ট খোঁজো।

• PI-1: $m_0,m_1,m_8,m_9$ → $\overline{B}\overline{D}$ অথবা পরীক্ষা করে দেখো: $A$ বদলায়, $B$=০, $C$ বদলায়, $D$ বদলায়... আরও যত্নশীলভাবে পরীক্ষা করলে: $m_0(0000),m_1(0001),m_8(1000),m_9(1001)$ → $B=0,C=0$ সবসময়, $A$ ও $D$ বদলায় → রাশি: $\overline{B}\overline{C}$
• PI-2: $m_0,m_2,m_8,m_{10}$ → $m_0(0000),m_2(0010),m_8(1000),m_{10}(1010)$ → $B=0,D=0$ সবসময় → রাশি: $\overline{B}\overline{D}$
• PI-3: $m_1,m_5,m_9$... (পরীক্ষা করো যদি বৈধ দল হয়)
• PI-4: $m_5,m_7$ → $m_5(0101),m_7(0111)$ → $A=0,B=1,D=1$ সবসময়, $C$ বদলায় → রাশি: $\overline{A}BD$
• PI-5: $m_6,m_7,m_{14}$... পরীক্ষা করো, $m_6(0110),m_7(0111),m_{14}(1110)$ তিনটি একসাথে বৈধ দল হয় না (৩ = ২ⁿ নয়)। তাই আলাদাভাবে: $m_6,m_{14}$ → $B=1,C=1,D=0$ সবসময়, $A$ বদলায় → রাশি: $BC\overline{D}$
• PI-6: $m_2,m_6,m_{10},m_{14}$ → $m_2(0010),m_6(0110),m_{10}(1010),m_{14}(1110)$ → $C=1,D=0$ সবসময় → রাশি: $C\overline{D}$

ধাপ ৩: এসেনশিয়াল PI খোঁজো।

$m_5$ শুধুমাত্র PI-4-এ আছে → PI-4 ($\overline{A}BD$) অবশ্যই নিতে হবে। $m_{14}$ শুধুমাত্র PI-6-এ আছে → PI-6 ($C\overline{D}$) অবশ্যই নিতে হবে।

PI-4 নিলে $m_5,m_7$ ঢাকা পড়ে। PI-6 নিলে $m_2,m_6,m_{10},m_{14}$ ঢাকা পড়ে।

এখনও অনাবৃত: $m_0,m_1,m_8,m_9$। এদের জন্য PI-1 ($\overline{B}\overline{C}$) নাও।

চূড়ান্ত রাশি: $F=\overline{A}BD+C\overline{D}+\overline{B}\overline{C}$

পাঁচ চলকের কার্নো মানচিত্র

পাঁচ চলকের ক্ষেত্রে মোট $2^5=32$টি মিনটার্ম থাকে। এটি একটি একক মানচিত্রে রাখা কঠিন, তাই দুটি পৃথক $4\times 4$ মানচিত্র ব্যবহার করা হয়।

দুটি মানচিত্রের ধারণা

• মানচিত্র-১ (E=০): চলক $E=\text{০}$ এর জন্য মিনটার্ম $m_0$ থেকে $m_{15}$
• মানচিত্র-২ (E=১): চলক $E=\text{১}$ এর জন্য মিনটার্ম $m_{16}$ থেকে $m_{31}$

পাঁচ চলকের কার্নো মানচিত্র — মানচিত্র-১ ($E=\text{০}$)

$AB$	$CD$
	$\text{০০}$	$\text{০১}$	$\text{১১}$	$\text{১০}$
$\text{০০}$	$m_0$	$m_1$	$m_3$	$m_2$
$\text{০১}$	$m_4$	$m_5$	$m_7$	$m_6$
$\text{১১}$	$m_{12}$	$m_{13}$	$m_{15}$	$m_{14}$
$\text{১০}$	$m_8$	$m_9$	$m_{11}$	$m_{10}$

পাঁচ চলকের কার্নো মানচিত্র — মানচিত্র-২ ($E=\text{১}$)

$AB$	$CD$
	$\text{০০}$	$\text{০১}$	$\text{১১}$	$\text{১০}$
$\text{০০}$	$m_{16}$	$m_{17}$	$m_{19}$	$m_{18}$
$\text{০১}$	$m_{20}$	$m_{21}$	$m_{23}$	$m_{22}$
$\text{১১}$	$m_{28}$	$m_{29}$	$m_{31}$	$m_{30}$
$\text{১০}$	$m_{24}$	$m_{25}$	$m_{27}$	$m_{26}$

পাঁচ চলকে দলবদ্ধকরণের বিশেষ নিয়ম

পাঁচ চলকের ক্ষেত্রে দলবদ্ধকরণ একটু আলাদা:

• একটি মানচিত্রের ভেতরে সাধারণ নিয়মে দল তৈরি করা যায়
• দুটি মানচিত্রের একই অবস্থানের ঘরগুলো পরস্পরের প্রতিবেশী (কারণ শুধু $E$ বদলায়)

উদাহরণ: মানচিত্র-১-এর $m_5$ এবং মানচিত্র-২-এর $m_{21}$ পরস্পরের প্রতিবেশী। এই দুটি একসাথে দল তৈরি করলে $E$ বাদ পড়ে।

উদাহরণ: পাঁচ চলকের ফাংশন

$F(A,B,C,D,E)=\mathrm{\Sigma }(0,2,4,6,16,18,20,22)$

মানচিত্র-১-এ ($E=0$): $m_0,m_2,m_4,m_6$ — এগুলো প্রথম ও শেষ কলামের চারটি ঘর, $D=0$ সবসময়।

মানচিত্র-২-এ ($E=1$): $m_{16},m_{18},m_{20},m_{22}$ — একইভাবে, $D=0$ সবসময়।

দুটি মানচিত্রের একই অবস্থানে ১ আছে, তাই আটটি ঘরের একটি বড় দল তৈরি হয়:

• $A$: বদলায় → বাদ
• $B$: বদলায় → বাদ
• $C$: বদলায় → বাদ
• $D$: সবসময় ০ → $\overline{D}$ থাকে
• $E$: বদলায় (দুটি মানচিত্র) → বাদ

ফলাফল: $F=\overline{D}$

কোয়াইন-ম্যাককলাস্কি পদ্ধতির সাথে তুলনা

কার্নো মানচিত্র পাঁচ বা ছয় চলকের বেশি হলে ব্যবহারিকভাবে কঠিন হয়ে পড়ে। এই সমস্যার সমাধানে কোয়াইন-ম্যাককলাস্কি (QM) পদ্ধতি ব্যবহার করা হয়।

কার্নো মানচিত্র বনাম কোয়াইন-ম্যাককলাস্কি পদ্ধতি

বৈশিষ্ট্য	কার্নো মানচিত্র	কোয়াইন-ম্যাককলাস্কি
সর্বোচ্চ ব্যবহারিক চলক সংখ্যা	৪–৬টি	যেকোনো সংখ্যা
পদ্ধতির ধরন	চিত্রভিত্তিক (ভিজ্যুয়াল)	সারণীভিত্তিক (অ্যালগরিদমিক)
কম্পিউটারে স্বয়ংক্রিয়করণ	কঠিন	সহজ
শিক্ষার্থীদের জন্য	সহজ ও স্বজ্ঞাত	তুলনামূলক জটিল
নিশ্চিত সর্বনিম্ন রাশি	অভিজ্ঞতার উপর নির্ভর করে	সবসময় নিশ্চিত
সময় জটিলতা	O(2n) অনুশীলনে	O(3n/2) তাত্ত্বিক

QM পদ্ধতির সংক্ষিপ্ত বিবরণ

কোয়াইন-ম্যাককলাস্কি পদ্ধতিতে:

ধাপ ১: সব মিনটার্মকে বাইনারিতে লিখে ১-এর সংখ্যা অনুযায়ী দলে ভাগ করো।

ধাপ ২: পরপর দলের মিনটার্মগুলো তুলনা করো। যদি দুটি মিনটার্মে ঠিক একটি বিট আলাদা হয়, সেই বিটটিকে ড্যাশ (−) দিয়ে প্রতিস্থাপন করো।

ধাপ ৩: নতুন গ্রুপ থেকে আবার একই প্রক্রিয়া চালাও যতক্ষণ না আর কোনো মিলন সম্ভব।

ধাপ ৪: যে মিনটার্মগুলো কোনো মিলনে অংশ নেয়নি সেগুলো প্রাইম ইমপ্লিক্যান্ট।

ধাপ ৫: প্রাইম ইমপ্লিক্যান্ট চার্ট তৈরি করে এসেনশিয়াল PI বেছে নাও।

বাস্তব জীবনে কার্নো মানচিত্রের প্রয়োগ

ডিজিটাল সার্কিট ডিজাইন

আধুনিক ডিজিটাল সার্কিটে — যেমন মাইক্রোপ্রসেসর, মেমোরি ডিকোডার, মাল্টিপ্লেক্সার — কার্নো মানচিত্র ব্যবহার করে লজিক সার্কিট সরল করা হয়। কম গেট মানে কম বিদ্যুৎ খরচ, কম তাপ উৎপাদন এবং বেশি নির্ভরযোগ্যতা।

সেগমেন্ট ডিসপ্লে ডিকোডার

সাত-সেগমেন্ট ডিসপ্লেতে (যেমন ডিজিটাল ঘড়িতে ব্যবহৃত) BCD সংখ্যা প্রদর্শন করতে একটি ডিকোডার সার্কিট দরকার। এই ডিকোডারের প্রতিটি সেগমেন্টের জন্য একটি বুলিয়ান ফাংশন থাকে এবং প্রতিটিকে কার্নো মানচিত্র দিয়ে সরল করা হয়।

উদাহরণ: সেগমেন্ট 'a' (সবচেয়ে উপরের অনুভূমিক সেগমেন্ট) নিচের মতো হতে পারে:

$a(A,B,C,D)=\mathrm{\Sigma }(0,2,3,5,6,7,8,9)$

এটি কার্নো মানচিত্র দিয়ে সরল করলে: $a=A+C+BD+\overline{B}\overline{D}$

অ্যাডার ও ALU

কম্পিউটারের গাণিতিক যুক্তি একক (ALU)-তে ব্যবহৃত ফুল অ্যাডার, সাবট্রাক্টর ইত্যাদি সার্কিটের লজিক ফাংশন কার্নো মানচিত্র দিয়ে সরল করা হয়।

ফুল অ্যাডারের ক্যারি আউটপুট: $C_{out}(A,B,C_{in})=\mathrm{\Sigma }(3,5,6,7)$

কার্নো মানচিত্র দিয়ে সরল করলে: $C_{out}=AB+A{C}_{in}+B{C}_{in}$

ট্রাফিক লাইট নিয়ন্ত্রণ

ধরো একটি ট্রাফিক লাইট সিস্টেমে তিনটি ইনপুট আছে: $P$ (পথচারী আছে), $V$ (যান আছে), $T$ (টাইমার চলছে)। সবুজ বাতির শর্ত একটি বুলিয়ান ফাংশন, যা কার্নো মানচিত্র দিয়ে সরল করা যায়।

মেমোরি অ্যাড্রেস ডিকোডার

কম্পিউটারের মেমোরি সিস্টেমে নির্দিষ্ট অ্যাড্রেস রেঞ্জ চেনার জন্য ডিকোডার সার্কিট ব্যবহার হয়। এই ডিকোডারের লজিক কার্নো মানচিত্র দিয়ে সরল করা হয়।

সংখ্যক গেটের প্রভাব: সরলীকরণের অর্থনীতি

কেন বুলিয়ান রাশি সরল করা গুরুত্বপূর্ণ? শুধু তাত্ত্বিক কারণে নয়, বাস্তব অর্থনৈতিক কারণেও।

লজিক গেটের খরচ

একটি সাধারণ ২-ইনপুট গেটের ট্রানজিস্টর সংখ্যা:

• NAND গেট: ৪টি ট্রানজিস্টর
• NOR গেট: ৪টি ট্রানজিস্টর
• AND গেট: ৬টি ট্রানজিস্টর (NAND + NOT)
• OR গেট: ৬টি ট্রানজিস্টর (NOR + NOT)

একটি আধুনিক মাইক্রোচিপে বিলিয়ন ট্রানজিস্টর থাকে। প্রতিটি বাড়তি গেট:

• বেশি সিলিকন ক্ষেত্রফল নেয় → চিপ বড় হয় → দাম বাড়ে
• বেশি বিদ্যুৎ খরচ করে → ব্যাটারি তাড়াতাড়ি শেষ হয়
• বেশি তাপ উৎপন্ন করে → কুলিং সিস্টেম দরকার
• বেশি প্রচার বিলম্ব (propagation delay) তৈরি করে → সার্কিট ধীর হয়

একটি তুলনামূলক উদাহরণ

অসরলীকৃত রাশি:

$F=\overline{A}\overline{B}C+\overline{A}BC+A\overline{B}C+ABC$

এটি বাস্তবায়নে দরকার: ৪টি ৩-ইনপুট AND গেট + ১টি ৪-ইনপুট OR গেট + ইনভার্টার = মোট প্রায় ৬০+ ট্রানজিস্টর

সরলীকৃত রাশি (কার্নো মানচিত্র দিয়ে):

$F=C$

এটি বাস্তবায়নে দরকার: মাত্র একটি তার! ০ ট্রানজিস্টর।

এই উদাহরণটি অতিরিক্ত সরল, কিন্তু বাস্তব সার্কিটে এই ধরনের সরলীকরণ লক্ষাধিক ট্রানজিস্টর বাঁচাতে পারে।

কার্নো মানচিত্রে পদ্ধতিগত ধাপ: চেকলিস্ট

কার্নো মানচিত্র সমাধান করার সময় এই ধাপগুলো ক্রমানুযায়ী অনুসরণ করলে ভুল হওয়ার সম্ভাবনা কমে যায়:

ধাপ ১: মানচিত্র তৈরি করো

• চলকের সংখ্যা গণনা করো: $n$ চলক → $2^n$ ঘর
• সঠিক গ্রে কোড বিন্যাসে সারি ও কলামের লেবেল লেখো
• কখনো সাধারণ বাইনারি ক্রম ব্যবহার করো না

ধাপ ২: মিনটার্ম মান বসাও

• প্রতিটি মিনটার্মের সংখ্যা থেকে সংশ্লিষ্ট ঘর খোঁজো
• সঠিক ঘরে ১ বসাও
• বাকি ঘরে ০ বসাও (ডোন্ট কেয়ার থাকলে X বসাও)

ধাপ ৩: সব প্রাইম ইমপ্লিক্যান্ট চিহ্নিত করো

• সবচেয়ে বড় সম্ভব দল খোঁজো
• বিপরীত প্রান্তের দল ভুলো না
• প্রতিটি সম্ভাব্য দলের একটি তালিকা তৈরি করো

ধাপ ৪: এসেনশিয়াল প্রাইম ইমপ্লিক্যান্ট বেছে নাও

• এমন ১-ঘর খোঁজো যেটি শুধু একটি PI-তে আছে
• সেই PI অবশ্যই নাও

ধাপ ৫: বাকি ১-ঘর ঢাকো

• যত কম PI দিয়ে সম্ভব বাকি ঘরগুলো ঢাকো

ধাপ ৬: প্রতিটি PI থেকে রাশি বের করো

• একই চলক → সরাসরি বা পরিপূরক রাখো
• বদলানো চলক → বাদ দাও

ধাপ ৭: সব রাশি OR করো

• সব PI-এর রাশি যোগ (OR) করলেই চূড়ান্ত SOP রাশি পাওয়া যায়

ধাপ ৮: যাচাই করো

• দুটি-তিনটি মিনটার্মের মান ফাংশনে বসিয়ে পরীক্ষা করো
• সত্যক-সারণী (truth table) তৈরি করে মূল ও সরলীকৃত রাশি মিলিয়ে দেখো

অনুশীলন সমস্যা ও সমাধান

সমস্যা ১ (সহজ)

$F(A,B,C)=\mathrm{\Sigma }(0,1,4,5)$ সরল করো।

সমাধান:

$A$	$BC$
	$\text{০০}$	$\text{০১}$	$\text{১১}$	$\text{১০}$
$\text{০}$	$\mathrm{𝟏}$	$\mathrm{𝟏}$	$\text{০}$	$\text{০}$
$\text{১}$	$\mathrm{𝟏}$	$\mathrm{𝟏}$	$\text{০}$	$\text{০}$

$m_0,m_1,m_4,m_5$: বাম দুই কলামের সব ঘর → $A$ বদলায়, $B$=০, $C$ বদলায় → রাশি: $\overline{B}$

উত্তর: $F=\overline{B}$

সমস্যা ২ (মাঝারি)

$F(A,B,C,D)=\mathrm{\Sigma }(1,5,9,13)$ সরল করো।

সমাধান:

$AB$	$CD$
	$\text{০০}$	$\text{০১}$	$\text{১১}$	$\text{১০}$
$\text{০০}$	$\text{০}$	$\mathrm{𝟏}$	$\text{০}$	$\text{০}$
$\text{০১}$	$\text{০}$	$\mathrm{𝟏}$	$\text{০}$	$\text{০}$
$\text{১১}$	$\text{০}$	$\mathrm{𝟏}$	$\text{০}$	$\text{০}$
$\text{১০}$	$\text{০}$	$\mathrm{𝟏}$	$\text{০}$	$\text{০}$

$m_1,m_5,m_9,m_{13}$: দ্বিতীয় কলামের সব ঘর → $A$ বদলায়, $B$ বদলায়, $C$=০, $D$=১ → রাশি: $\overline{C}D$

উত্তর: $F=\overline{C}D$

সমস্যা ৩ (কঠিন: ডোন্ট কেয়ার সহ)

$F(A,B,C,D)=\mathrm{\Sigma }(2,3,7,10,11)$, ডোন্ট কেয়ার: $d(1,15)$

সমাধান:

$AB$	$CD$
	$\text{০০}$	$\text{০১}$	$\text{১১}$	$\text{১০}$
$\text{০০}$	$\text{০}$	$X$	$\mathrm{𝟏}$	$\mathrm{𝟏}$
$\text{০১}$	$\text{০}$	$\text{০}$	$\mathrm{𝟏}$	$\text{০}$
$\text{১১}$	$\text{০}$	$\text{০}$	$X$	$\text{০}$
$\text{১০}$	$\text{০}$	$\text{০}$	$\mathrm{𝟏}$	$\mathrm{𝟏}$

দলবদ্ধকরণ:

• দল ১: $m_2,m_3$ এবং ডোন্ট কেয়ার $m_1$ ব্যবহার করে → $m_1,m_2,m_3$... কিন্তু এটি ৩টি (২ⁿ নয়)। তাই: $m_2,m_3,m_{10},m_{11}$ পরীক্ষা করো। $m_2(0010),m_3(0011),m_{10}(1010),m_{11}(1011)$ → $B=0,C=1$ সবসময়, $A$ ও $D$ বদলায় → রাশি: $\overline{B}C$
• দল ২: $m_3,m_7$ এবং ডোন্ট কেয়ার $m_{15}$: $m_3(0011),m_7(0111),m_{15}(1111)$ — তিনটি আবার ২ⁿ নয়। $m_3,m_7$: $A=0,C=1,D=1$ সবসময়, $B$ বদলায় → রাশি: $\overline{A}CD$। কিন্তু ডোন্ট কেয়ার $m_{15}$ যোগ করলে: $m_3,m_7,m_{11},m_{15}$ হয়। পরীক্ষা: $C=1,D=1$ সবসময়, $A$ ও $B$ বদলায় → রাশি: $CD$ (বড় দল, ডোন্ট কেয়ার ব্যবহার করে সরল)

চূড়ান্ত রাশি: $F=\overline{B}C+CD$

যাচাই: $m_2$: $\overline{B}C=1\cdot 1=1$; $m_7$: $CD=1\cdot 1=1$; $m_{10}$: $\overline{B}C=1\cdot 1=1$

ঐতিহাসিক প্রেক্ষাপট ও বিবর্তন

বুলিয়ান বীজগণিতের সূচনা

জর্জ বুল ১৮৫৪ সালে তাঁর বিখ্যাত গ্রন্থ An Investigation of the Laws of Thought প্রকাশ করেন। এতে তিনি যুক্তিকে গাণিতিক সমীকরণ দিয়ে প্রকাশ করেন। তবে তখন এটি কোনো প্রকৌশল প্রয়োগে ব্যবহৃত হয়নি।

ক্লড শ্যানন-এর অবদান

১৯৩৭ সালে এমআইটির গবেষক ক্লড শ্যানন প্রথম দেখান যে বুলিয়ান বীজগণিত ইলেকট্রিক সুইচিং সার্কিটে প্রয়োগ করা যায়। তাঁর মাস্টার্স থিসিস পরবর্তীকালে ডিজিটাল সার্কিট ডিজাইনের ভিত্তি স্থাপন করে।

মরিস কার্নো-র উদ্ভাবন

১৯৫৩ সালে বেল টেলিফোন ল্যাবরেটরিজের প্রকৌশলী মরিস কার্নো তাঁর পেপারে এই মানচিত্র পদ্ধতি প্রস্তাব করেন। কার্নো মানচিত্রের আগে বুলিয়ান রাশি সরল করতে বীজগণিতিক নিয়ম মুখস্থ করে ধাপে ধাপে প্রয়োগ করতে হতো — একটি ক্লান্তিকর ও ভুল-প্রবণ প্রক্রিয়া।

ভেইচ ডায়াগ্রাম

কার্নো মানচিত্রের একটি পূর্বসূরি হলো এডওয়ার্ড ভেইচ-এর ভেইচ ডায়াগ্রাম (১৯৫২)। কার্নো মূলত ভেইচের কাজকে উন্নত ও পদ্ধতিগত করেন। কিছু বই এই মানচিত্রকে ভেইচ-কার্নো মানচিত্র বলে।

আধুনিক EDA টুলস

আজকের ইলেকট্রনিক ডিজাইন অটোমেশন (EDA) সফটওয়্যার — যেমন Synopsys, Cadence, Xilinx Vivado — স্বয়ংক্রিয়ভাবে লক্ষ লক্ষ চলকের বুলিয়ান ফাংশন সরল করতে পারে, QM পদ্ধতি ও তার উন্নত সংস্করণ ব্যবহার করে। কিন্তু কার্নো মানচিত্র শিক্ষার সরঞ্জাম হিসেবে আজও অপরিহার্য।

সিকোয়েন্শিয়াল লজিক ও ফ্লিপ-ফ্লপ ডিজাইনে কার্নো মানচিত্র

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

ফ্লিপ-ফ্লপ পরিচিতি

ফ্লিপ-ফ্লপ হলো একটি বিস্টেবল মাল্টিভাইব্রেটর — এটি দুটি স্থিতিশীল অবস্থায় থাকতে পারে: ০ অথবা ১। প্রতিটি ফ্লিপ-ফ্লপ একটি বিট তথ্য সংরক্ষণ করতে পারে। ক্লক পালসের সাথে সাথে এটি তার অবস্থা পরিবর্তন করে।

চারটি প্রধান ফ্লিপ-ফ্লপ:

ফ্লিপ-ফ্লপের ধরন ও বৈশিষ্ট্য

ফ্লিপ-ফ্লপ	ইনপুট	বৈশিষ্ট্য	ব্যবহার
SR	S, R	সেট ও রিসেট, অবৈধ অবস্থা আছে	সরল মেমোরি
JK	J, K	SR-এর উন্নত সংস্করণ, সব অবস্থা বৈধ	কাউন্টার
D	D	ডেটা সঞ্চয়, পরবর্তী অবস্থা = D	রেজিস্টার
T	T	টগল, T=১ হলে অবস্থা বদলায়	কাউন্টার

এক্সাইটেশন টেবিল

ফ্লিপ-ফ্লপ ডিজাইনে এক্সাইটেশন টেবিল ব্যবহার করা হয়। এটি বলে দেয় — বর্তমান অবস্থা ($Q$) থেকে পরবর্তী অবস্থা ($Q^{+}$)-এ যেতে ফ্লিপ-ফ্লপের ইনপুটে কী দিতে হবে।

SR ফ্লিপ-ফ্লপের এক্সাইটেশন টেবিল

$Q$	$Q^{+}$	$S$	$R$
০	০	০	X
০	১	১	০
১	০	০	১
১	১	X	০

JK ফ্লিপ-ফ্লপের এক্সাইটেশন টেবিল

$Q$	$Q^{+}$	$J$	$K$
০	০	০	X
০	১	১	X
১	০	X	১
১	১	X	০

D ফ্লিপ-ফ্লপের এক্সাইটেশন টেবিল

$Q$	$Q^{+}$	$D$
০	০	০
০	১	১
১	০	০
১	১	১

D ফ্লিপ-ফ্লপ সবচেয়ে সহজ: $D=Q^{+}$। পরবর্তী অবস্থাই হলো D ইনপুট।

T ফ্লিপ-ফ্লপের এক্সাইটেশন টেবিল

$Q$	$Q^{+}$	$T$
০	০	০
০	১	১
১	০	১
১	১	০

T ফ্লিপ-ফ্লপে: $T=Q\oplus Q^{+}$। অবস্থা বদলালে T=১, না বদলালে T=০।

৩-বিট আপ কাউন্টার ডিজাইন: JK ফ্লিপ-ফ্লপ দিয়ে

এখন একটি সম্পূর্ণ উদাহরণ দেখা যাক: ৩-বিট বাইনারি আপ কাউন্টার। এটি ০০০ থেকে ১১১ পর্যন্ত গণনা করে, তারপর আবার ০০০-এ ফিরে আসে।

ধাপ ১: স্টেট ট্রানজিশন টেবিল তৈরি করো।

তিনটি ফ্লিপ-ফ্লপ: $Q_A$ (MSB), $Q_B$, $Q_C$ (LSB)।

৩-বিট আপ কাউন্টারের স্টেট ট্রানজিশন ও JK ইনপুট

বর্তমান অবস্থা		পরবর্তী অবস্থা		JK ইনপুট (A)		JK ইনপুট (B)		JK ইনপুট (C)
$Q_A{Q}_B{Q}_C$		$Q_A^{+}{Q}_B^{+}{Q}_C^{+}$		$J_A$ $K_A$		$J_B$ $K_B$		$J_C$ $K_C$
০ ০ ০	→	০ ০ ১		০ X		০ X		১ X
০ ০ ১	→	০ ১ ০		০ X		১ X		X ১
০ ১ ০	→	০ ১ ১		০ X		X ০		১ X
০ ১ ১	→	১ ০ ০		১ X		X ১		X ১
১ ০ ০	→	১ ০ ১		X ০		০ X		১ X
১ ০ ১	→	১ ১ ০		X ০		১ X		X ১
১ ১ ০	→	১ ১ ১		X ০		X ০		১ X
১ ১ ১	→	০ ০ ০		X ১		X ১		X ১

ধাপ ২: কার্নো মানচিত্র দিয়ে প্রতিটি ইনপুট সরল করো।

$J_A$-এর জন্য কার্নো মানচিত্র ($J_A$: ০,০,০,১,X,X,X,X):

$J_A$-এর কার্নো মানচিত্র

$Q_A$	$Q_B{Q}_C$
	$\text{০০}$	$\text{০১}$	$\text{১১}$	$\text{১০}$
$\text{০}$	০	০	১	০
$\text{১}$	X	X	X	X

দ্বিতীয় সারির সব X কে ১ ধরে দলবদ্ধকরণ: $m_3$ এবং $m_4,m_5,m_6,m_7$ মিলে একটি চারটির দল হয় না সরাসরি, কিন্তু $m_3$ এবং X গুলো মিলিয়ে:

• $m_3$ এবং $m_7(X)$: দুটির দল → $Q_B{Q}_C$ (উভয় ১)
• X গুলো বড় দল তৈরিতে ব্যবহার: $m_3,m_7,m_5,m_1$... কিন্তু $m_1$ = ০। তাই শুধু $m_3$ আর X দিয়ে: সরলতম → $J_A=Q_B{Q}_C$

$K_A$-এর জন্য (K_A: X,X,X,X,০,০,০,১):

$K_A$-এর কার্নো মানচিত্র

$Q_A$	$Q_B{Q}_C$
	$\text{০০}$	$\text{০১}$	$\text{১১}$	$\text{১০}$
$\text{০}$	X	X	X	X
$\text{১}$	০	০	১	০

একইভাবে: $K_A=Q_B{Q}_C$

$J_B$-এর জন্য (J_B: ০,১,X,X,০,১,X,X):

$J_B$-এর কার্নো মানচিত্র

$Q_A$	$Q_B{Q}_C$
	$\text{০০}$	$\text{০১}$	$\text{১১}$	$\text{১০}$
$\text{০}$	০	১	X	X
$\text{১}$	০	১	X	X

দলবদ্ধকরণ: দ্বিতীয় কলাম ($Q_C=1$) এবং তৃতীয় কলাম (X)। $m_1,m_5$ এবং X গুলো মিলিয়ে চারটির দল: $Q_C$ সবসময় ১ (প্রথম দুটিতে), X ব্যবহার করে: $J_B=Q_C$

$K_B=Q_C$ (একইভাবে বিশ্লেষণ করলে)

$J_C=K_C=1$ (সবসময়, কারণ C সবসময় টগল করে)

চূড়ান্ত ডিজাইন সমীকরণ:

$J_A=K_A=Q_B{Q}_C$

$J_B=K_B=Q_C$

$J_C=K_C=1$

এই সমীকরণ দিয়েই ৩-বিট আপ কাউন্টার সার্কিট তৈরি হয়। কার্নো মানচিত্র না থাকলে এই সরলীকরণ অনেক কঠিন হতো।

D ফ্লিপ-ফ্লপ দিয়ে সিকোয়েন্স ডিটেক্টর

ধরো আমরা একটি সার্কিট বানাতে চাই যেটি ইনপুট সিকোয়েন্সে "১০১" শনাক্ত করবে। এটি একটি মিড ডিটেক্টর।

স্টেট ডায়াগ্রাম থেকে স্টেট ট্রানজিশন টেবিল তৈরি করে, তারপর D ফ্লিপ-ফ্লপের জন্য কার্নো মানচিত্র ব্যবহার করলে পরবর্তী অবস্থার সমীকরণ পাওয়া যায়।

D ফ্লিপ-ফ্লপের ক্ষেত্রে কাজটি সহজ: $D_i=Q_i^{+}$, অর্থাৎ পরবর্তী অবস্থার মান সরাসরি D ইনপুটে দিতে হবে। তাই স্টেট ট্রানজিশন টেবিল থেকে পরবর্তী অবস্থার কার্নো মানচিত্র বানিয়ে সরল করলেই D ইনপুটের সমীকরণ পাওয়া যায়।

হ্যাজার্ড ও রেস কন্ডিশন: কার্নো মানচিত্রে সনাক্তকরণ

হ্যাজার্ড কী?

বাস্তব ডিজিটাল সার্কিটে গেটের মধ্য দিয়ে সংকেত যেতে একটু সময় লাগে — এই বিলম্বকে প্রচার বিলম্ব (propagation delay) বলে। ইনপুট পরিবর্তনের সময় বিভিন্ন পথে সংকেত বিভিন্ন সময়ে পৌঁছায়, ফলে আউটপুটে সাময়িক ভুল মান দেখা দিতে পারে। এই অপ্রত্যাশিত ক্ষণস্থায়ী ভুলকে হ্যাজার্ড বলে।

হ্যাজার্ড দুই ধরনের:

হ্যাজার্ডের শ্রেণীবিভাগ

হ্যাজার্ডের ধরন	সংজ্ঞা	উদাহরণ
স্ট্যাটিক-১ হ্যাজার্ড	আউটপুট ১ থাকা উচিত, কিন্তু ক্ষণিকের জন্য ০ হয়	$1\to 0\to 1$
স্ট্যাটিক-০ হ্যাজার্ড	আউটপুট ০ থাকা উচিত, কিন্তু ক্ষণিকের জন্য ১ হয়	$0\to 1\to 0$
ডায়নামিক হ্যাজার্ড	আউটপুট একবার বদলানোর বদলে তিনবার বদলায়	$0\to 1\to 0\to 1$

কার্নো মানচিত্রে স্ট্যাটিক হ্যাজার্ড সনাক্তকরণ

স্ট্যাটিক-১ হ্যাজার্ড কার্নো মানচিত্রে সনাক্ত করা যায়। যদি দুটি ১-ঘর পাশাপাশি থাকে কিন্তু তারা একই দলে না থাকে, তবে ইনপুট পরিবর্তনের সময় হ্যাজার্ড দেখা দিতে পারে।

উদাহরণ: $F(A,B,C)=\mathrm{\Sigma }(1,3,5)$

হ্যাজার্ড সনাক্তকরণ — কার্নো মানচিত্র

$A$	$BC$
	$\text{০০}$	$\text{০১}$	$\text{১১}$	$\text{১০}$
$\text{০}$	০	১	১	০
$\text{১}$	০	১	০	০

এখানে দুটি দল হতে পারে:

• দল ১: $m_1,m_3$ → $\overline{A}C$
• দল ২: $m_1,m_5$ → $\overline{B}C$... অপেক্ষা, $m_1(001),m_5(101)$: $C=1,B=0$ সবসময় → $\overline{B}C$

তাহলে: $F=\overline{A}C+\overline{B}C$... কিন্তু $m_3$ এবং $m_5$ পাশাপাশি আছে কিন্তু তারা ভিন্ন দলে। যদি ইনপুট $m_3(A=0,B=1,C=1)$ থেকে $m_5(A=1,B=0,C=1)$-এ পরিবর্তিত হয় (A ও B একসাথে বদলায়), তবে হ্যাজার্ড হতে পারে।

হ্যাজার্ড দূর করার পদ্ধতি

হ্যাজার্ড দূর করতে একটি রিডান্ড্যান্ট দল যোগ করতে হয় — এমন একটি দল যেটি লজিক্যালি অপ্রয়োজনীয় কিন্তু হ্যাজার্ডের দুটি ঘরকে একই দলে রাখে।

উপরের উদাহরণে: $m_3$ এবং $m_5$ উভয়ই ঢাকতে একটি নতুন দল যোগ করো: আসলে এই দুটো ঘর পাশাপাশি নয় (গ্রে কোডে দুই ধাপ দূরে — একসাথে A এবং B দুটো বদলে)। তাই এই বিশেষ ট্রানজিশনে হ্যাজার্ড হবে না। হ্যাজার্ড হয় যখন দুটি ১-ঘর একটি চলকের পার্থক্যে আলাদা কিন্তু ভিন্ন দলে।

সঠিক উদাহরণ: $F(A,B,C)=\mathrm{\Sigma }(1,3,5,7)$-এ দুটি দল নিলে:

• দল ১: $m_1,m_3$ → $\overline{A}C$
• দল ২: $m_5,m_7$ → $AC$

$m_3$ ও $m_7$ পাশাপাশি ($B$ বদলে) কিন্তু ভিন্ন দলে → হ্যাজার্ড সম্ভব।

হ্যাজার্ড দূর করতে রিডান্ড্যান্ট দল: $m_3,m_7$ → $BC$

হ্যাজার্ড-মুক্ত রাশি: $F=\overline{A}C+AC+BC=C+BC=C$

তবে সরলীকরণে $F=C$ হয়ে যায়। ব্যবহারিক ক্ষেত্রে রিডান্ড্যান্ট পদটি রাখা হয় শুধু হ্যাজার্ড প্রতিরোধের জন্য, এমনকি যদি সে পদটি বুলিয়ানভাবে অপ্রয়োজনীয় হয়।

স্ট্যাটিক-০ হ্যাজার্ড দূর করা

POS রাশিতে স্ট্যাটিক-০ হ্যাজার্ড থাকতে পারে। কার্নো মানচিত্রে ০-ঘর দলবদ্ধ করার সময় দুটি ০-ঘর পাশাপাশি থাকলে কিন্তু ভিন্ন দলে হলে হ্যাজার্ড হয়। সমাধান: ০-ঘরের জন্যও রিডান্ড্যান্ট দল যোগ করো।

ডায়নামিক হ্যাজার্ড

ডায়নামিক হ্যাজার্ড কার্নো মানচিত্র দিয়ে সরাসরি সনাক্ত করা যায় না — এটি সার্কিটের কাঠামোর উপর নির্ভর করে। তিন বা তার বেশি স্তরের গেট ব্যবহার করলে ডায়নামিক হ্যাজার্ড হতে পারে। সমাধান: দুই-স্তর (SOP বা POS) সার্কিট ব্যবহার করো।

মাল্টিপ্লেক্সার দিয়ে কার্নো ফাংশন বাস্তবায়ন

মাল্টিপ্লেক্সার কী?

মাল্টিপ্লেক্সার (MUX) হলো এমন একটি সার্কিট যেটি একাধিক ইনপুট থেকে একটিকে বেছে আউটপুটে পাঠায়। $n$টি সিলেক্ট লাইন দিয়ে $2^n$টি ইনপুটের মধ্যে একটি বেছে নেওয়া যায়।

৪:১ MUX-এর সত্য-সারণী:

৪:১ MUX

$S_1$	$S_0$	আউটপুট ($Y$)
০	০	$I_0$
০	১	$I_1$
১	০	$I_2$
১	১	$I_3$

MUX দিয়ে যেকোনো বুলিয়ান ফাংশন বাস্তবায়ন

$n$ চলকের ফাংশন বাস্তবায়নে $2^{n-1}:1$ MUX ব্যবহার করা যায়।

পদ্ধতি (n চলক, ৪:১ MUX):

• একটি চলক বাদ দিয়ে বাকি দুটিকে সিলেক্ট লাইনে দাও
• কার্নো মানচিত্র থেকে প্রতিটি MUX ইনপুটের মান নির্ণয় করো

উদাহরণ: ৩ চলকের ফাংশন, ৪:১ MUX দিয়ে

$F(A,B,C)=\mathrm{\Sigma }(1,2,6,7)$

সিলেক্ট লাইনে A ও B দাও, C-কে পরিবর্তনশীল ধরো।

MUX ইনপুট নির্ণয়

$A$	$B$	MUX ইনপুট	$C=0$ হলে F	$C=1$ হলে F	$I$-এর মান
০	০	$I_0$	$F(0,0,0)=0$	$F(0,0,1)=1$	$C$
০	১	$I_1$	$F(0,1,0)=1$	$F(0,1,1)=0$	$\overline{C}$
১	০	$I_2$	$F(1,0,0)=0$	$F(1,0,1)=0$	$0$
১	১	$I_3$	$F(1,1,0)=1$	$F(1,1,1)=1$	$1$

বাস্তবায়ন: ৪:১ MUX-এ $I_0=C$, $I_1=\overline{C}$, $I_2=0$, $I_3=1$, $S_1=A$, $S_0=B$।

৮:১ MUX দিয়ে ৩ চলকের ফাংশন

$8:1$ MUX ব্যবহার করলে তিনটি চলককেই সিলেক্ট লাইনে দেওয়া যায়। তখন প্রতিটি MUX ইনপুট হবে সরাসরি সংশ্লিষ্ট মিনটার্মের মান (০ বা ১)।

$F(A,B,C)=\mathrm{\Sigma }(1,2,6,7)$-এর জন্য:

• $I_0=0$ ($m_0=0$), $I_1=1$ ($m_1=1$), $I_2=1$, $I_3=0$
• $I_4=0$, $I_5=0$, $I_6=1$, $I_7=1$

এই পদ্ধতিতে কোনো গেট লাগে না — শুধু MUX এবং সঠিক ইনপুট সংযোগ।

MUX বনাম গেট বাস্তবায়ন

MUX বনাম গেট বাস্তবায়নের তুলনা

বৈশিষ্ট্য	MUX বাস্তবায়ন	গেট বাস্তবায়ন
নকশার জটিলতা	কম (শুধু টেবিল দেখলেই হয়)	বেশি (কার্নো মানচিত্র লাগে)
নমনীয়তা	বেশি (ফাংশন পরিবর্তন সহজ)	কম
গেটের সংখ্যা	বেশি (MUX নিজেই গেটের সমষ্টি)	কম (সরল ফাংশনে)
ব্যবহার	FPGA, প্রোটোটাইপ	ASIC, অপ্টিমাইজড ডিজাইন

FPGA ও PLA-তে কার্নো মানচিত্রের ভূমিকা

PLA (Programmable Logic Array)

PLA হলো একটি প্রোগ্রামযোগ্য সার্কিট যেখানে AND গেটের একটি অ্যারে এবং OR গেটের একটি অ্যারে থাকে। এটি SOP রাশি সরাসরি বাস্তবায়ন করতে পারে।

PLA-তে ফাংশন বাস্তবায়নের ধাপ:

1. কার্নো মানচিত্র দিয়ে SOP রাশি সরল করো
2. প্রতিটি গুণফল পদের জন্য একটি AND গেট প্রোগ্রাম করো
3. সেই AND গেটের আউটপুটগুলো OR গেটে সংযুক্ত করো

কার্নো মানচিত্র দিয়ে SOP সরল না করলে প্রয়োজনের চেয়ে বেশি AND গেট ব্যবহার হবে — PLA-র জায়গা নষ্ট হবে।

PAL (Programmable Array Logic)

PAL-এ AND অ্যারে প্রোগ্রামযোগ্য কিন্তু OR অ্যারে স্থির। এতে প্রতিটি OR গেটে নির্দিষ্ট সংখ্যক AND গেট সংযুক্ত থাকে। কার্নো মানচিত্র দিয়ে SOP সরল করলে পদের সংখ্যা কমে, যা PAL-এ ফিট করা সহজ হয়।

FPGA-র লুকআপ টেবিল (LUT)

আধুনিক FPGA-তে মূল বিল্ডিং ব্লক হলো লুকআপ টেবিল (LUT)। একটি $n$-ইনপুট LUT যেকোনো $n$-চলকের বুলিয়ান ফাংশন বাস্তবায়ন করতে পারে — কারণ এটি আসলে $2^n$ বিটের একটি মেমোরি।

উদাহরণ: ৪-ইনপুট LUT-এ $2^4=16$ বিটের মেমোরি থাকে। সত্য-সারণীর আউটপুট কলামের ১৬টি মান সরাসরি এই মেমোরিতে লোড করা হয়।

কার্নো মানচিত্রের ভূমিকা FPGA-তে:

• কার্নো মানচিত্র দিয়ে ফাংশন ন্যূনতম চলকে সরল করলে কম LUT লাগে
• EDA সফটওয়্যার স্বয়ংক্রিয়ভাবে এই কাজ করে (QM পদ্ধতি ব্যবহার করে)
• কার্নো মানচিত্র বোঝা থাকলে EDA আউটপুট যাচাই করা সহজ হয়

CPLD (জটিল প্রোগ্রামেবল লজিক ডিভাইস)

CPLD হলো PLD এবং FPGA-র মাঝামাঝি একটি ডিভাইস। এতে একাধিক PLA ব্লক থাকে যেগুলো ইন্টারকানেকশন দিয়ে যুক্ত। কার্নো মানচিত্র থেকে পাওয়া সরলীকৃত SOP রাশি CPLD-তে দক্ষভাবে বাস্তবায়ন করা যায়।

কার্নো মানচিত্র ও ভেন ডায়াগ্রামের সম্পর্ক

গাণিতিক দৃষ্টিকোণ

কার্নো মানচিত্র আসলে একটি বিশেষ ভেন ডায়াগ্রামের সমতুল্য। ভেন ডায়াগ্রামে প্রতিটি চলক একটি বৃত্ত দিয়ে প্রকাশ করা হয়, এবং বিভিন্ন অঞ্চল বিভিন্ন মিনটার্ম প্রকাশ করে।

দুই চলকের ভেন ডায়াগ্রামে চারটি অঞ্চল: $\overline{A}\overline{B}$, $\overline{A}B$, $A\overline{B}$, $AB$। কার্নো মানচিত্রের চারটি ঘরও ঠিক এই চারটি মিনটার্ম প্রকাশ করে।

পার্থক্য হলো: ভেন ডায়াগ্রামে পাশের অঞ্চলগুলো বুলিয়ান সরলীকরণের উপযোগী বিন্যাসে থাকে না, কিন্তু কার্নো মানচিত্রে গ্রে কোড ব্যবহার করে পাশের ঘরগুলোকে সবসময় একটি চলকের পার্থক্যে রাখা হয়।

সেট তত্ত্বের আলোকে

বুলিয়ান বীজগণিত এবং সেট তত্ত্ব একই কাঠামোর দুটি রূপ:

বুলিয়ান বীজগণিত ও সেট তত্ত্বের সম্পর্ক

বুলিয়ান বীজগণিত	সেট তত্ত্ব
AND ($\cdot$)	ছেদ ($\cap$)
OR ($+$)	মিলন ($\cup$)
NOT ($\overline{}$)	পরিপূরক ($A^c$)
০	শূন্য সেট ($\mathrm{\varnothing }$)
১	সার্বজনীন সেট ($U$)
মিনটার্ম	একক উপাদানের সেট

কার্নো মানচিত্রে দলবদ্ধকরণ আসলে সেট মিলনের মতো: একাধিক মিনটার্মের সেট একত্রিত করে একটি বড় সেট তৈরি করা।

টোপোলজিক্যাল দৃষ্টিভঙ্গি

কার্নো মানচিত্রকে একটি টোরাস (ডোনাটের আকৃতি) হিসেবে ভাবা যায়। যদি মানচিত্রের বাম ও ডান প্রান্ত একসাথে জোড়া লাগানো হয় এবং উপর ও নিচের প্রান্ত একসাথে জোড়া লাগানো হয়, তাহলে একটি টোরাস তৈরি হয়।

এই টোরাসে প্রতিটি ঘরের ঠিক চারটি প্রতিবেশী থাকে (উপর, নিচ, বাম, ডান) — কোনো "প্রান্ত" নেই। এই কারণেই বিপরীত প্রান্তের ঘরগুলো পাশাপাশি গণ্য হয়।

চার চলকের মানচিত্রে সম্ভাব্য বৈধ দলের মোট সংখ্যা অনেক বেশি — প্রতিটি আকারের (১, ২, ৪, ৮, ১৬) এবং প্রতিটি অবস্থানের দল বিবেচনা করলে। টোরাসের সম্পদসম্মত ব্যবহারই কার্নো মানচিত্রকে এত শক্তিশালী করে।

অনুশীলন সমস্যা ও বিশদ সমাধান

সমস্যা ১: তিন চলক, সহজ

$F(A,B,C)=\mathrm{\Sigma }(0,3,4,7)$ সরল করো।

সমাধান:

মানচিত্রে মান বসাই:

$A$	$BC$
	$\text{০০}$	$\text{০১}$	$\text{১১}$	$\text{১০}$
$\text{০}$	১	০	১	০
$\text{১}$	১	০	১	০

দলবদ্ধকরণ:

• প্রথম কলাম ($m_0,m_4$): $B=0,C=0$ সবসময়, A বদলায় → $\overline{B}\overline{C}$
• তৃতীয় কলাম ($m_3,m_7$): $B=1,C=1$ সবসময়, A বদলায় → $BC$

চূড়ান্ত রাশি: $F=\overline{B}\overline{C}+BC$

এটি আসলে XNOR ফাংশন: $F=\overline{B\oplus C}$

সমস্যা ২: চার চলক, মাঝারি

$F(A,B,C,D)=\mathrm{\Sigma }(0,1,4,5,10,11,14,15)$ সরল করো।

সমাধান:

$AB$	$CD$
	$\text{০০}$	$\text{০১}$	$\text{১১}$	$\text{১০}$
$\text{০০}$	১	১	০	০
$\text{০১}$	১	১	০	০
$\text{১১}$	০	০	১	১
$\text{১০}$	০	০	১	১

দলবদ্ধকরণ:

• দল ১: $m_0,m_1,m_4,m_5$ (উপরের দুই সারির বাম দুই কলাম) → $A=0,C=0$ সবসময়, B ও D বদলায় → $\overline{A}\overline{C}$
• দল ২: $m_{10},m_{11},m_{14},m_{15}$ (নিচের দুই সারির ডান দুই কলাম) → $A=1,C=1$ সবসময়, B ও D বদলায় → $AC$

চূড়ান্ত রাশি: $F=\overline{A}\overline{C}+AC=\overline{A\oplus C}$

সমস্যা ৩: চার চলক, কঠিন

$F(A,B,C,D)=\mathrm{\Sigma }(0,2,3,6,7,8,10,11,12,13)$ সরল করো।

সমাধান:

$AB$	$CD$
	$\text{০০}$	$\text{০১}$	$\text{১১}$	$\text{১০}$
$\text{০০}$	১	০	১	১
$\text{০১}$	০	০	১	১
$\text{১১}$	১	১	০	০
$\text{১০}$	১	০	১	১

দলবদ্ধকরণ (ধাপে ধাপে):

• দল ১: $m_2,m_3,m_6,m_7$: $AB=00$ ও $AB=01$-এর তৃতীয় ও চতুর্থ কলাম → $A=0,C=1$ সবসময় → $\overline{A}C$
• দল ২: $m_0,m_2,m_8,m_{10}$: কোণের দল (প্রথম ও শেষ কলাম, প্রথম ও শেষ সারি) → $B=0,D=0$ সবসময় → $\overline{B}\overline{D}$
• দল ৩: $m_{12},m_{13}$: $AB=11$-এর প্রথম দুই কলাম → $A=1,B=1,C=0$ → $AB\overline{C}$

সব ১-ঘর ঢাকা হয়েছে কিনা পরীক্ষা: $m_0$(দল-২)✓, $m_2$(দল-১,দল-২)✓, $m_3$(দল-১)✓, $m_6$(দল-১)✓, $m_7$(দল-১)✓, $m_8$(দল-২)✓, $m_{10}$(দল-২)✓, $m_{11}$... অপেক্ষা! $m_{11}$-এর স্থানে কী আছে? $AB=10,CD=11$ → $m_{11}$: আউটপুট ১। কিন্তু কোনো দলে নেই। নতুন দল দরকার।

• দল ৪: $m_{10},m_{11}$: $A=1,B=0,C=1$ সবসময়, D বদলায় → $A\overline{B}C$

চূড়ান্ত রাশি: $F=\overline{A}C+\overline{B}\overline{D}+AB\overline{C}+A\overline{B}C$

সমস্যা ৪: ডোন্ট কেয়ার সহ, মাঝারি

$F(A,B,C,D)=\mathrm{\Sigma }(3,9,11,12,13)$, ডোন্ট কেয়ার: $d(1,4,14,15)$

সমাধান:

$AB$	$CD$
	$\text{০০}$	$\text{০১}$	$\text{১১}$	$\text{১০}$
$\text{০০}$	০	X	১	০
$\text{০১}$	X	০	০	০
$\text{১১}$	১	১	X	X
$\text{১০}$	০	১	১	০

দলবদ্ধকরণ:

• দল ১: $m_{12},m_{13}$ এবং X ($m_{14},m_{15}$) → চারটির দল → $A=1,B=1$ সবসময় → $AB$
• দল ২: $m_9,m_{13}$: $A=1,C=0,D=1$... পরীক্ষা: $m_9(1001),m_{13}(1101)$ → $A=1,D=1$, B বদলায়, C বদলায়... দুটিতে $A=1$ এবং $D=1$ সবসময়, B ও C বদলায় → রাশি হবে $A\overline{C}D$ না... আবার: $m_9:AB=10,CD=01$; $m_{13}:AB=11,CD=01$ → C=0, D=1 সবসময়, A বদলায় (০→১), B বদলায় (০→১) নয় সবার জন্য... সঠিকভাবে: শুধু $A$ বদলায়, পার্স করতে ব্যর্থ (সিনট্যাক্স ত্রুটি): {\displaystyle B=0→1} ... এটি একটি ২-ঘরের দল: $\overline{C}D$ (যদি আরও বড় দল না হয়)।
• X ($m_1$) ব্যবহার করে: $m_1(0001),m_3(0011),m_9(1001),m_{11}(1011)$ → $C$ বদলায়, $D=1$ সবসময়, $B=0$ সবসময়, $A$ বদলায় → $\overline{B}D$

সব ১-ঘর ঢাকা: $m_3$(দল-নতুন), $m_9$(দল-নতুন), $m_{11}$(দল-নতুন), $m_{12}$(দল-১), $m_{13}$(দল-১)

চূড়ান্ত রাশি: $F=AB+\overline{B}D$

সমস্যা ৫: POS রাশি নির্ণয়

$F(A,B,C)=\mathrm{\Sigma }(0,1,2,4)$-এর POS রাশি নির্ণয় করো।

সমাধান:

$F$-এর মানচিত্র (০-ঘর খুঁজি — এগুলো $m_3,m_5,m_6,m_7$):

$A$	$BC$
	$\text{০০}$	$\text{০১}$	$\text{১১}$	$\text{১০}$
$\text{০}$	১	১	০	১
$\text{১}$	১	০	০	০

০-ঘর দলবদ্ধকরণ:

• দল ১ (০-ঘর): $m_3,m_7$: $B=1,C=1$ সবসময়, A বদলায় → POS পদ: $(\overline{B}+\overline{C})$
• দল ২ (০-ঘর): $m_5,m_7$: $A=1,C=1$... $m_5(101),m_7(111)$ → $A=1,C=1$ সবসময়, B বদলায় → POS পদ: $(\overline{A}+\overline{C})$
• দল ৩ (০-ঘর): $m_6,m_7$: $A=1,B=1$ সবসময়, C বদলায় → POS পদ: $(\overline{A}+\overline{B})$

$m_3$ শুধু দল-১ ও দল-৩-এ আছে, $m_5$ শুধু দল-২-এ।

সব দল নিতে হবে (প্রতিটি ০-ঘর অন্তত একটি দলে)।

POS রাশি: $F=(\overline{B}+\overline{C})(\overline{A}+\overline{C})(\overline{A}+\overline{B})$

যাচাই: $m_3(A=0,B=1,C=1)$: প্রথম ফ্যাক্টর $(\overline{1}+\overline{1})=0+0=0$। $F=0$

বিস্তারিত সংখ্যাতাত্ত্বিক বিশ্লেষণ: কার্নো মানচিত্র কতটুকু সরল করতে পারে?

সবচেয়ে জটিল ক্ষেত্র

$n$ চলকের একটি ফাংশনের সবচেয়ে জটিল SOP রাশি হতে পারে যখন কোনো দলবদ্ধকরণ সম্ভব নয় — অর্থাৎ প্রতিটি মিনটার্ম একটি আলাদা পদ। এক্ষেত্রে সর্বোচ্চ $2^{n-1}$টি মিনটার্ম থাকতে পারে সর্বনিম্ন রাশিতে।

চেকারবোর্ড প্যাটার্ন: XOR ফাংশন

কার্নো মানচিত্রে যদি ১ এবং ০ পর্যায়ক্রমে চেকারবোর্ডের মতো সাজানো থাকে, তবে কোনো দলবদ্ধকরণ সম্ভব নয়। এই ফাংশনটি হলো XOR:

$F(A,B,C,D)=A\oplus B\oplus C\oplus D$

XOR ফাংশনের কার্নো মানচিত্র (চেকারবোর্ড প্যাটার্ন)

$AB$	$CD$
	$\text{০০}$	$\text{০১}$	$\text{১১}$	$\text{১০}$
$\text{০০}$	০	১	০	১
$\text{০১}$	১	০	১	০
$\text{১১}$	০	১	০	১
$\text{১০}$	১	০	১	০

এই মানচিত্রে কোনো দুটি পাশাপাশি ১-ঘর নেই। তাই কার্নো মানচিত্র এখানে কোনো সরলীকরণ দিতে পারে না। XOR ফাংশন কার্নো মানচিত্রের দুর্বল ক্ষেত্র — এটি XOR গেট দিয়ে সরাসরি বাস্তবায়ন করাই ভালো।

সর্বোচ্চ সরলীকৃত ক্ষেত্র

সবচেয়ে সহজ ক্ষেত্র যেখানে সব ঘরে ১: $F=1$ (সবসময় সত্য)। অথবা একটি বড় দলে সব ঘর: কম চলকের ফাংশন।

ভুল বিশ্লেষণ: শিক্ষার্থীদের সাধারণ ভুল =

ভুল ১: গ্রে কোড বিন্যাস ভুলে সাধারণ ক্রম ব্যবহার

অনেক শিক্ষার্থী কলামের ক্রম $00,01,10,11$ লেখেন (সাধারণ বাইনারি), যেখানে হওয়া উচিত $00,01,11,10$ (গ্রে কোড)। ফলে সব দলবদ্ধকরণ ভুল হয়।

সহজ মনে রাখার উপায়: মাঝের দুটি কলাম বা সারি সবসময় উভয় বিট ১ (যেমন ১১), প্রথম ও শেষ সবসময় আলাদা।

ভুল ২: ৩টি ঘরের দল তৈরি

কার্নো মানচিত্রে ৩টি ঘরের দল কখনো বৈধ নয়। $2^n$-এর সিরিজে ৩ নেই।

• • ভুল উদাহরণ:** $m_0,m_1,m_2$ একসাথে দলবদ্ধ করা। সঠিক কাজ: $m_0,m_1$ একসাথে এবং $m_0,m_2$ বা $m_1,m_3$ ইত্যাদি আলাদা দল।

ভুল ৩: ডোন্ট কেয়ার একা দলে রাখা

ডোন্ট কেয়ার ঘরকে একা একটি দল হিসেবে নেওয়া মানে রাশিতে একটি অতিরিক্ত পদ যোগ করা যা প্রয়োজন নেই।

• • সঠিক নিয়ম:** ডোন্ট কেয়ার শুধু বিদ্যমান ১-ঘরের দলকে বড় করতে ব্যবহার করো। যদি কোনো ১-ঘর না থাকে তার আশেপাশে, তাহলে ডোন্ট কেয়ারটি উপেক্ষা করো।

ভুল ৪: কোনো ১-ঘর ঢাকা না পড়া

সব ১-ঘর অন্তত একটি দলে থাকতেই হবে। কোনো ঘর বাদ পড়লে ফাংশনের মান সেই মিনটার্মে ভুল হবে।

ভুল ৫: অপ্রয়োজনীয় দল রাখা

যদি একটি দলের সব ঘর ইতিমধ্যে অন্য দলে আছে, সেই দলটি রাখা মানে রাশিতে বাড়তি পদ যোগ করা। এটি ভুল নয়, কিন্তু সর্বনিম্ন রাশি দেয় না।

• • পরীক্ষার পদ্ধতি:** প্রতিটি দলে এমন কোনো ঘর আছে কিনা দেখো যেটি শুধু সেই দলেই আছে, অন্য কোনো দলে নেই। না থাকলে সেই দলটি অপ্রয়োজনীয়।

সারণী পদ্ধতিতে সব উদাহরণের তুলনামূলক বিশ্লেষণ

এই নিবন্ধের উদাহরণগুলোর সারসংক্ষেপ

উদাহরণ	ফাংশন	মূল পদ সংখ্যা	সরলীকৃত রাশি	পদ সংখ্যা	সরলীকরণ মাত্রা
$\mathrm{\Sigma }(1,2,3)$	৩টি AND পদ	$A+B$	২	উল্লেখযোগ্য
$\mathrm{\Sigma }(1,3,5,7)$	৪টি AND পদ	$C$	১	সর্বোচ্চ
$\mathrm{\Sigma }(0,2,8,10)$	৪টি AND পদ	$\overline{B}\overline{D}$	১	সর্বোচ্চ
$\mathrm{\Sigma }(4,5,6,7,12,13,14,15)$	৮টি AND পদ	$B$	১	অসাধারণ
$\mathrm{\Sigma }(1,3,7,11,15)+d(0,2,5)$	৫টি AND পদ	$\overline{A}\overline{B}+CD$	২	ভালো

সারসংক্ষেপ: কার্নো মানচিত্রের মূল বিষয়গুলো

কার্নো মানচিত্রের মূল বিষয়সমূহ

বিষয়	মূল কথা
গ্রে কোড	প্রতি ধাপে একটি বিট পরিবর্তন; দলবদ্ধকরণের ভিত্তি
দলের আকার	অবশ্যই $2^n$: ১, ২, ৪, ৮, ১৬
সর্বোচ্চ বড় দল	বেশি চলক বাদ পড়ে, রাশি সরল হয়
একাধিক দলে থাকা	বৈধ: $A+A=A$ নিয়মে
গোলাকার মানচিত্র	বিপরীত প্রান্ত পরস্পর সংযুক্ত
ডোন্ট কেয়ার	দল বড় করতে ব্যবহার করো, একা দল নয়
প্রাইম ইমপ্লিক্যান্ট	সর্বোচ্চ বড় বৈধ দল
এসেনশিয়াল PI	অবশ্যই নিতে হবে — অন্য PI-তে নেই এমন ঘর আছে
POS রাশি	০-ঘর দলবদ্ধ করে পাওয়া যায়
পাঁচ+ চলক	দুটি মানচিত্র বা QM পদ্ধতি ব্যবহার করো

প্রয়োগ

কার্নো মানচিত্রের প্রধান ব্যবহারগুলো হলো:

• বুলিয়ান রাশি সরলীকরণ করে সার্কিটের জটিলতা কমানো
• কম সংখ্যক গেট ব্যবহার করে বর্তনী নির্মাণ করা ও খরচ কমানো
• সার্কিটের বিদ্যুৎ খরচ ও তাপ উৎপাদন কমানো
• দ্রুততর ডিজিটাল বর্তনী তৈরি করা কারণ কম গেট মানে কম বিলম্ব
• অর্ধযোগকারী, পূর্ণযোগকারী, ডিকোডার ইত্যাদি সার্কিট নকশায় ব্যবহার

অনুশীলনী

কার্নো মানচিত্র ব্যবহার করে নিচের রাশিগুলো সরল করো:

1. $F(A,B)=\mathrm{\Sigma }(1,2,3)$
2. $F(A,B,C)=\mathrm{\Sigma }(0,1,2,3)$
3. $F(A,B,C)=\mathrm{\Sigma }(1,3,5,7)$
4. $F(A,B,C,D)=\mathrm{\Sigma }(0,2,8,10)$
5. $F(A,B,C,D)=\mathrm{\Sigma }(4,5,6,7)$
6. $F(A,B,C,D)=\mathrm{\Sigma }(0,1,4,5,10,11,14,15)$
7. $F(A,B,C,D)=\mathrm{\Sigma }(1,5,7,11,13,15)$, ডোন্ট কেয়ার: $d(3,9)$
8. $F(A,B,C)=\mathrm{\Sigma }(0,2,3,4,6,7)$

উত্তর:

1. $F=A+B$ (নিচের সারি + ডান কলাম)
2. $F=\overline{A}$ (উপরের সারির চারটি ঘর একটি দল)
3. $F=C$ (মাঝের দুই কলামের চারটি ঘর একটি দল)
4. $F=\overline{B}\overline{D}$ (চার কোণের দল)
5. $F=\overline{A}B$ (দ্বিতীয় সারির চারটি ঘর একটি দল)
6. $F=\overline{B}\overline{C}+BD$ (দুটি দল: চার কোণ + মাঝের দুই সারির ডান দুই কলাম)
7. $F=CD+\overline{B}D$ (ডোন্ট কেয়ার ব্যবহার করে দুটি দল)
8. $F=\overline{A}\overline{C}+B$ (দুটি দল: কোণ দল + নিচের সারি)

[[টেমপ্লেট:BOOKCATEGORY]]