কারনো ম্যাপ (K-Map) সিমপ্লিফিকেশন

১ · কারনো ম্যাপ (K-Map) কী

কারনো ম্যাপKarnaugh Map (K-map)একটি ভিজ্যুয়াল, গ্রিড-ভিত্তিক পদ্ধতি যা বুলিয়ান এক্সপ্রেশন সরল করে — সেলগুলো এমনভাবে সাজানো থাকে যে পাশাপাশি সেল ঠিক একটি ভ্যারিয়েবলে ভিন্ন হয়, তাই 1-দের গ্রুপ দেখেই বোঝা যায় কোন ভ্যারিয়েবল বাদ দেওয়া যায়। হলো একটি ভিজ্যুয়াল, গ্রিড-ভিত্তিক পদ্ধতি যা দিয়ে ৪-৫ ভ্যারিয়েবল পর্যন্ত এক্সপ্রেশন সরল করা যায় — L05-এর মতো একের পর এক বীজগাণিতিক নিয়ম হাতে প্রয়োগ না করেই। এর সেলগুলো এমনভাবে সাজানো থাকে যে যেকোনো দুটি পাশাপাশি সেল (wrap-around প্রান্তসহ — অর্থাৎ গ্রিডের এক প্রান্ত অন্য প্রান্তের সাথেও "পাশাপাশি" ধরা হয়) ঠিক একটি মাত্র ভ্যারিয়েবলে ভিন্ন হয় — একে বলা হয় Gray codeGray Codeএমন একটি বাইনারি সংখ্যা-ক্রম যেখানে পরপর দুটি সংখ্যা ঠিক একটি বিটে ভিন্ন হয় (00, 01, 11, 10 — সাধারণ বাইনারি গণনা ক্রম 00,01,10,11 নয়)। অর্ডারিং। এই বিশেষ সাজানোর কারণেই পাশাপাশি 1-দের একটি গ্রুপ সরাসরি দেখিয়ে দেয় কোন ভ্যারিয়েবল(গুলো) বাদ দেওয়া যায়।

২ · গ্রুপিং নিয়ম

K-map-এ 1 বসানো সেলগুলোকে বৃত্তাকারে ঘিরে গ্রুপ বানাতে হয়, নিচের নিয়ম মেনে —

• প্রতিটি গ্রুপের আকার হতে হবে 2-এর ঘাত (1, 2, 4, 8...) — অন্য কোনো আকার বৈধ নয়।
• প্রতিটি গ্রুপ যতটা সম্ভব বড় বানাতে হবে — বড় গ্রুপ মানে বেশি ভ্যারিয়েবল বাদ, ছোট সরল টার্ম।
• প্রতিটি 1 অন্তত একবার কোনো না কোনো গ্রুপে কভার হতে হবে।
• গ্রুপগুলো একে অপরের সাথে ওভারল্যাপ করতে পারে — একই সেল একাধিক গ্রুপে থাকতে পারে।

প্রতিটি বৈধ গ্রুপ চূড়ান্ত Sum-of-Products (SOP)Sum-of-Productsএকাধিক AND-টার্মের OR — বুলিয়ান এক্সপ্রেশন লেখার একটি সাধারণ, প্রমিত রূপ, যেখানে প্রতিটি টার্ম কিছু ভ্যারিয়েবলের AND আর টার্মগুলো একে অপরের সাথে OR। এক্সপ্রেশনে একটি করে টার্মে পরিণত হয় — গ্রুপের ভেতর যে ভ্যারিয়েবলের মান সব সেলে স্থির থাকে, সেটাই সেই টার্মে থেকে যায়; যে ভ্যারিয়েবলের মান গ্রুপের মধ্যে বদলে যায় (0 ও 1 দুটোই দেখা যায়), সেটা বাদ পড়ে যায়।

৩ · Worked example — F(A,B,C) = Σ(1,3,5,7)

নিচের mintermMintermএকটি ৩-ভ্যারিয়েবল ফাংশনে, ইনপুট কম্বিনেশনের বাইনারি মানকেই তার minterm সংখ্যা বলা হয় — যেমন A=0,B=0,C=1 হলে বাইনারি "001" = minterm 1। তালিকা Σ(1,3,5,7) মানে F হলো 1 ঠিক সেই ইনপুট কম্বিনেশনগুলোর জন্য যাদের বাইনারি মান (ABC হিসেবে পড়লে) 1, 3, 5, অথবা 7 — বাইনারিতে যথাক্রমে 001, 011, 101, 111। লক্ষ্য করুন — এই চারটি মিনটার্মেই শেষ বিট (C) সবসময় 1, A ও B যেকোনো মান নিতে পারে। নিচের K-map-এ এই মিনটার্মগুলো বসিয়ে দেখা যাক:

নিচের সারির চারটি সেল (C=1) একটি একক ৪-সেল গ্রুপ বানায় — এই গ্রুপে AB-এর মান 00, 01, 11, 10 সবগুলোই আছে (অর্থাৎ A ও B দুজনেই গ্রুপের মধ্যে 0 এবং 1 দুটো মানই নিয়েছে), কিন্তু C সবসময় 1 স্থির। গ্রুপিং নিয়ম অনুযায়ী যে ভ্যারিয়েবল গ্রুপের মধ্যে বদলে যায় তা বাদ পড়ে (A ও B বাদ), আর যেটা স্থির থাকে তা টার্মে থেকে যায় (C)। তাই:

$$F(A,B,C) = C$$

উপরের সারি (C=0)-এ কোনো 1 নেই, তাই তার জন্য কোনো গ্রুপ দরকার নেই। এই ফলাফলটি নিচের কোডে ব্রুট-ফোর্স ট্রুথ টেবিলের বিরুদ্ধে যাচাই করে নেওয়া হলো — L05-এর মতো একই "সম্পূর্ণ ট্রুথ টেবিল তুলনা" পদ্ধতি, এবার K-map-এর ফলাফলের উপর প্রয়োগ করা হয়েছে।

# মিনটার্ম তালিকা থেকে ব্রুট-ফোর্স ট্রুথ টেবিল বনাম K-map-সরলীকৃত এক্সপ্রেশন -- সারি-বাই-সারি তুলনা
def generate_truth_table_from_minterms(minterms, num_vars):
    """মিনটার্ম-তালিকা থেকে ব্রুট-ফোর্স সম্পূর্ণ ট্রুথ টেবিল তৈরি করে -- প্রতিটি কম্বিনেশনের বাইনারি মান সেটে আছে কিনা যাচাই করে"""
    table = {}
    for combo_index in range(2 ** num_vars):
        bits = tuple((combo_index >> (num_vars - 1 - i)) & 1 for i in range(num_vars))
        table[bits] = 1 if combo_index in minterms else 0
    return table

def simplified_F_is_C(a, b, c):
    """K-map দিয়ে হাতে-কলমে বের করা সরলীকৃত দাবি: F(A,B,C) = C"""
    return c

minterms = [1, 3, 5, 7]
num_vars = 3
brute_force_table = generate_truth_table_from_minterms(minterms, num_vars)

print("A B C | ব্রুট-ফোর্স F (Σ মিনটার্ম) | K-map-সরলীকৃত F=C | মিলেছে?")
print("-" * 62)
identical = True
for a in (0, 1):
    for b in (0, 1):
        for c in (0, 1):
            brute_val = brute_force_table[(a, b, c)]
            simplified_val = simplified_F_is_C(a, b, c)
            match = brute_val == simplified_val
            if not match:
                identical = False
            print(f"{a} {b} {c} |          {brute_val}                |        {simplified_val}         |  {'হ্যাঁ' if match else 'না!'}")

print()
print(f"F=C আসলেই Σ(1,3,5,7)-এর সঠিক সরলীকরণ? {'হ্যাঁ' if identical else 'না'}")