Multiplexer, decoder আর encoder — বেছে নেওয়া আর ঠিকানা খোঁজা

১ · বেছে নেওয়া আর ঠিকানা খোঁজা — combinational logic-এর তৈরি block

পর্ব ০৭ থেকে ০৯-এ আপনি Boolean algebra, logic gate আর K-map দিয়ে একটি একটি function সরল করতে শিখেছেন। পর্ব ১১-তে সেই দক্ষতা দিয়ে adder বানানো হয়েছে। কিন্তু একটি বাস্তব CPU নকশা করতে গিয়ে কেউ প্রতিবার শূন্য থেকে gate বসান না — বারবার যে ধরনের কাজ লাগে, তার জন্য কয়েকটি তৈরি block আছে, ঠিক যেমন রাজমিস্ত্রি প্রতিবার মাটি থেকে ইট বানান না।

এই পর্বের সব block-ই combinational circuit — output নির্ভর করে শুধু এই মুহূর্তের input-এর ওপর, আগের কোনো স্মৃতি নেই। প্রতিটির আচরণ তাই একটি truth table দিয়ে পুরোপুরি বলা যায়। কাজ অনুযায়ী এদের চারটি দলে ভাগ করা যায়:

এই পর্বে লেখার রীতি: কোনো চলকের উল্টো (complement) লেখা হবে A′ (prime) দিয়ে, যেমন S′ মানে “S নয়”। কোডে একই জিনিস ~A বা 1 - a. XOR লেখা হবে ⊕ দিয়ে। Minterm m_i মানে truth table-এর i নম্বর সারি, যেখানে সবচেয়ে বাঁয়ের চলক MSB — পর্ব ০৭-এর রীতি।

২ · Multiplexer — অনেক রাস্তার একটি বেছে নেওয়া

2:1 mux — সবচেয়ে ছোট বাছাইকারী

2:1 mux-এর দুটি data input A আর B, একটি select line S, আর একটি output Y. নিয়ম: S = 0 হলে Y = A, S = 1 হলে Y = B. পুরো truth table-এ ৩টি input, তাই ৮টি সারি — কিন্তু সংক্ষেপে লেখা যায় মাত্র দুই সারিতে:

এখানে x মানে “যা খুশি থাকুক, ফলে প্রভাব নেই”। সংক্ষিপ্ত টেবিল থেকে সরাসরি সূত্র আসে: Y = 1 হয় যখন (S = 0 এবং A = 1) অথবা (S = 1 এবং B = 1). অর্থাৎ

Gate-এ এটি একটি NOT (S′ বানাতে), দুটি ২-input AND আর একটি OR — মোট চারটি gate. প্রতিটি AND gate একটি “দরজা”: S′ = 1 হলে ওপরের দরজা খোলা, A ভেতর দিয়ে যায়; তখন S = 0 বলে নিচের দরজা বন্ধ, B আটকে যায়। দুটি দরজা কখনো একসাথে খোলা থাকে না, তাই OR gate-এ সবসময় ঠিক একটি সংকেত পৌঁছায়।

        S ──┬──[NOT]── S′
            │           │
   A ───────┼──────[AND]─┐
            │      (S′·A) ├──[OR]── Y = S′A + SB
   B ───────┴──────[AND]─┘
                   (S·B)

4:1 আর 8:1 mux

Input বাড়লে select বিটও বাড়ে: ২ⁿটি input-এর জন্য n টি select বিট। 4:1 mux-এর select S₁S₀ একটি ২-বিটের binary সংখ্যা — তার মানই বলে কোন input যাবে: 00 → I₀, 01 → I₁, 10 → I₂, 11 → I₃. সূত্রে প্রতিটি data input-কে তার নম্বরের minterm দিয়ে AND করা হয়:

এই সাধারণ রূপটি মনে রাখুন: ২ⁿ:1 mux = select বিটের সবগুলো minterm, প্রতিটি নিজের data input-এর সাথে AND, তারপর সব মিলিয়ে একটি বড় OR. 8:1 mux-এ ৩টি select, ৮টি ৪-input AND (৩টি select-literal + ১টি data) আর একটি ৮-input OR. দেখুন, এখানে লুকিয়ে আছে একটি decoder — select বিট থেকে minterm বানানোর অংশটি ঠিক অংশ ৪-এর decoder. নিচের stepper-এ select বদলালে কোন AND “দরজা” খোলে, দেখুন:

CPU-তে mux সর্বত্র: ALU-র দ্বিতীয় operand register থেকে আসবে নাকি instruction-এর immediate থেকে, পরের PC হবে PC + 4 নাকি branch-এর ঠিকানা, register-এ লেখা হবে ALU-র ফল নাকি মেমরি থেকে পড়া মান — প্রতিটি সিদ্ধান্ত একটি mux. পর্ব ১৩-এ দেখবেন ALU নিজেও যোগ, AND, OR-এর ফল একসাথে হিসাব করে রাখে, তারপর একটি mux দিয়ে দরকারিটি বেছে নেয়। পর্ব ৩২-এর datapath-এ এমন mux আরও অনেক।

৩ · Mux-এর গাছ, আর mux দিয়ে যেকোনো function

ছোট mux জুড়ে বড় mux

বাজারে বা লাইব্রেরিতে যদি শুধু 4:1 mux থাকে, অথচ লাগে 16:1? উত্তর: একটি mux tree. ১৬টি input-কে ৪টি দলে ভাগ করুন; প্রথম স্তরে ৪টি 4:1 mux, প্রত্যেকে নিচের দুটি select বিট S₁S₀ দিয়ে নিজের দলের একটিকে বাছে। দ্বিতীয় স্তরে আরেকটি 4:1 mux ওপরের দুটি বিট S₃S₂ দিয়ে চারটি বিজয়ীর একটিকে বাছে। মোট ৫টি 4:1 mux. একইভাবে 8:1 = দুটি 4:1 + একটি 2:1.

নিয়মটি ক্রিকেট টুর্নামেন্টের নকআউটের মতো: প্রতিটি ম্যাচে দুই দল থেকে এক দল এগোয়। ১৬টি দল থেকে একটি চ্যাম্পিয়ন পেতে ঠিক ১৫টি ম্যাচ লাগে, কারণ প্রতিটি ম্যাচে ঠিক একটি দল বাদ পড়ে আর ১৫টি দল বাদ পড়তে হবে। তাই ২ⁿ:1 mux বানাতে ২ⁿ − ১টি 2:1 mux লাগে, আর গাছের উচ্চতা n স্তর। একই যুক্তিতে k:1 mux দিয়ে N:1 বানাতে (N − 1)/(k − 1)টি mux লাগে, যখন সংখ্যাটি পূর্ণসংখ্যা — 4:1 দিয়ে 16:1-এ (১৬ − ১)/(৪ − ১) = ৫। খেয়াল করুন: নিচের স্তরে যায় select-এর কম গুরুত্বের বিট, ওপরের স্তরে বেশি গুরুত্বের — উল্টে দিলে ভুল input বাছাই হবে।

Mux একটি সর্বজনীন function generator — প্রমাণ

এবার এই পর্বের সবচেয়ে সুন্দর ধারণা। 8:1 mux-এর select-এ যদি তিনটি চলক A, B, C লাগান, তাহলে প্রতিটি সারি ABC-র জন্য ঠিক একটি data input I_i output-এ আসে। এখন I_i-তে সরাসরি সেই সারির F-এর মান (0 বা 1) বসিয়ে দিলে, output হবে ঠিক F. অর্থাৎ truth table-এর output কলামটিই data input-এ বসিয়ে দিন — কোনো সরলীকরণ লাগে না। সূত্রে: Y = Σ m_i·I_i, আর I_i = F(i) হলে Y = Σ_F(i)=1 m_i — যা F-এর canonical SOP (পর্ব ০৭)।

কিন্তু আরও সস্তায় করা যায় — একটি ছোট, ২ⁿ⁻¹:1 mux দিয়ে। এর ভিত্তি Shannon expansion: যেকোনো function-কে একটি চলক x ধরে দুই ভাগ করা যায়,

যুক্তি: x = 0 বসালে ডান দিক হয় ১·F(…,0) + ০ = F(…,0); x = 1 বসালে ০ + F(…,1). x-এর দুটি মানেই দুই দিক সমান, তাই সূত্রটি সবসময় সত্য। এবার select-এ প্রথম n−1টি চলক দিন। প্রতিটি select মানের জন্য বাকি থাকে শুধু x-এর একটি function — আর এক চলকের function মাত্র চার রকম হতে পারে: সবসময় 0, সবসময় 1, x, অথবা x′. তাই প্রতিটি data input-এ এই চারটির একটি বসালেই কাজ শেষ। কোনটি বসবে, তা ঠিক হয় truth table-এর জোড়া সারি দেখে:

কাজ করা উদাহরণ — F(A, B, C) = Σm(1, 3, 5, 6)

প্রথমে truth table-এর F কলাম: সারি ০ থেকে ৭-এ 0 1 0 1 0 1 1 0.

(ক) 8:1 mux দিয়ে: A, B, C → S₂, S₁, S₀. Data: I₀ = 0, I₁ = 1, I₂ = 0, I₃ = 1, I₄ = 0, I₅ = 1, I₆ = 1, I₇ = 0. অর্থাৎ I₁, I₃, I₅, I₆-কে 1-এ (V_CC), বাকিগুলো 0-তে (ground).

(খ) 4:1 mux দিয়ে: A, B → S₁, S₀, আর C যাবে data-তে। নিচের stepper-এ জোড়ায় জোড়ায় সারি দেখে প্রতিটি data input বের করা হলো:

একটি বোনাস তথ্য: 2:1 mux নিজেই functionally complete — শুধু 2:1 mux আর ধ্রুবক 0, 1 দিয়ে যেকোনো circuit বানানো যায়, ঠিক NAND-এর মতো (পর্ব ০৮)। NOT A = mux(S = A, I₀ = 1, I₁ = 0); A·B = mux(S = A, I₀ = 0, I₁ = B); A + B = mux(S = A, I₀ = B, I₁ = 1). NOT, AND, OR পাওয়া গেলে বাকি সব পাওয়া যায়।

এবার হাতের পদ্ধতিটি যন্ত্রে চালিয়ে দেখুন। নিচের synthesiser একটি minterm তালিকা থেকে ২ⁿ⁻¹:1 mux-এর data input বের করে (0/1/x/x′), তারপর mux-টি simulate করে truth table-এর প্রতিটি সারির সাথে মেলায়। তিনটি function দিয়ে পরীক্ষা করা হয়েছে — নিজের minterm দিয়েও বদলে দেখুন:

// Any n-variable function with ONE 2^(n-1):1 mux.
// First n-1 variables drive the select lines; the last variable x feeds data inputs.
function synth(n, minterms) {
  const on = new Set(minterms), inputs = [];
  for (let i = 0; i < 2 ** (n - 1); i++) {
    const f0 = on.has(2 * i), f1 = on.has(2 * i + 1);      // F at x=0 and at x=1
    inputs.push(f0 && f1 ? "1" : !f0 && !f1 ? "0" : f1 ? "x" : "x'");
  }
  return inputs;
}
function runMux(inputs, v) {                // v = all n inputs as one integer
  const sel = v >> 1, x = v & 1;            // top n-1 bits select, LSB is x
  const d = inputs[sel];
  return d === "1" ? 1 : d === "0" ? 0 : d === "x" ? x : 1 - x;
}
const NAMES = "ABCD";
const tests = [[3, [1, 3, 5, 6]], [3, [3, 5, 6, 7]], [4, [0, 1, 3, 4, 8, 9, 15]]];
for (const [n, mt] of tests) {
  const ins = synth(n, mt), x = NAMES[n - 1];
  console.log(`F(${NAMES.slice(0, n).split("").join(",")}) = Sum m(${mt.join(",")})`);
  console.log(`  ${2 ** n}:1 mux data I0..I${2 ** n - 1} = ` +
    [...Array(2 ** n)].map((_, v) => (mt.includes(v) ? 1 : 0)).join(" "));
  console.log(`  ${2 ** (n - 1)}:1 mux, select = ${NAMES.slice(0, n - 1)}, x = ${x}:`);
  console.log("    " + ins.map((d, i) => `I${i}=${d.replace("x", x)}`).join("  "));
  let bad = 0;
  for (let v = 0; v < 2 ** n; v++)
    if (runMux(ins, v) !== (mt.includes(v) ? 1 : 0)) bad++;
  console.log(`  simulated all ${2 ** n} rows: ${bad === 0 ? "matches truth table" : bad + " mismatches"}`);
}

F(A,B,C) = Sum m(1,3,5,6)
  8:1 mux data I0..I7 = 0 1 0 1 0 1 1 0
  4:1 mux, select = AB, x = C:
    I0=C  I1=C  I2=C  I3=C'
  simulated all 8 rows: matches truth table
F(A,B,C) = Sum m(3,5,6,7)
  8:1 mux data I0..I7 = 0 0 0 1 0 1 1 1
  4:1 mux, select = AB, x = C:
    I0=0  I1=C  I2=C  I3=1
  simulated all 8 rows: matches truth table
F(A,B,C,D) = Sum m(0,1,3,4,8,9,15)
  16:1 mux data I0..I15 = 1 1 0 1 1 0 0 0 1 1 0 0 0 0 0 1
  8:1 mux, select = ABC, x = D:
    I0=1  I1=D  I2=D'  I3=0  I4=1  I5=0  I6=0  I7=D
  simulated all 16 rows: matches truth table

৪ · Demultiplexer আর decoder — একটি থেকে অনেক

Demultiplexer — উল্টো দিকের লিভার

Mux অনেক থেকে একটি বাছে; demultiplexer (demux) একটি input D-কে n টি select বিট দিয়ে ২ⁿটি output-এর একটিতে পাঠায়, বাকি সব output 0 থাকে। ডাকঘরের বাছাইকারীর মতো: একটি বস্তা থেকে প্রতিটি চিঠি পিনকোড দেখে ঠিক একটি খোপে যায়। 1:4 demux-এর সূত্র:

অর্থাৎ Y_i = m_i(S)·D. এবার D-কে স্থায়ীভাবে 1 করে দিন: Y_i = m_i(S) — প্রতিটি output শুধু একটি minterm. এই circuit-টির নামই decoder. উল্টো দিক থেকে বললে: enable input থাকা একটি decoder-ই demultiplexer — data-কে enable-এ দিন, ঠিকানাকে input-এ। এজন্য বাণিজ্যিক IC-র নামেও প্রায়ই একসাথে লেখা থাকে “decoder/demultiplexer”.

2:4 আর 3:8 decoder — প্রতিটি output একটি minterm

n:২ⁿ decoder-এর n টি input, আর ২ⁿটি output-এর ঠিক একটি 1 — input-এর binary মান যত, সেই নম্বরের output. এমন “ঠিক একটি 1” নকশাকে বলে one-hot. 3:8 decoder-এ Y₅ = A₂A₁′A₀ = m₅, আর Y₀ = A₂′A₁′A₀′ = m₀. গঠন সোজা: n টি NOT gate (প্রতিটি input-এর উল্টো বানাতে) আর ২ⁿটি n-input AND.

প্রায় সব বাস্তব decoder-এ একটি enable input (EN) থাকে: EN = 0 হলে সব output 0, input যা-ই হোক; EN = 1 হলে স্বাভাবিক কাজ। প্রতিটি AND gate-এ একটি বাড়তি input হিসেবে EN যোগ করলেই হয়: Y_i = EN·m_i. এই ছোট্ট সুবিধাটিই decoder জুড়ে বড় decoder বানানোর চাবি। আরেকটি বাস্তব কথা: অনেক IC-তে output আর enable active-low — বাছাই করা লাইনটি 0 হয়, বাকিগুলো 1 (নামের ওপর দাগ বা শেষে N দিয়ে বোঝানো হয়)। যুক্তি একই, শুধু চিহ্ন উল্টো; ডেটাশিট দেখে নিশ্চিত হওয়া জরুরি।

নিচের simulator decoder আর mux দুটোকেই gate-এর স্তরে বানায় — decoder প্রতিটি output-এর জন্য enable আর n টি literal-এর AND করে, আর mux সেই minterm-গুলোকে data-র সাথে AND করে OR করে। অর্থাৎ mux-এর ভেতরে সত্যিই একটি decoder বসানো:

// Gate-level mux and decoder: a decoder makes minterms, a mux ANDs them with data.
function decoder(sel, en = 1) {            // sel = [S(n-1) ... S0]
  const n = sel.length, out = [];
  for (let i = 0; i < 2 ** n; i++) {
    let m = en;                              // AND gate: enable and n literals
    for (let k = 0; k < n; k++) {
      const want = (i >> (n - 1 - k)) & 1;
      m &= want ? sel[k] : 1 - sel[k];       // literal S or S'
    }
    out.push(m);                             // output i = minterm m_i
  }
  return out;
}
function mux(data, sel) {                    // Y = OR of (m_i AND I_i)
  return decoder(sel).reduce((y, m, i) => y | (m & data[i]), 0);
}
const bits = (v, n) => [...Array(n)].map((_, k) => (v >> (n - 1 - k)) & 1);

console.log("4:1 mux   S1 S0 | Y");
let ok = 0;
for (let s = 0; s < 4; s++) {
  for (let d = 0; d < 16; d++) {             // try all 16 data patterns
    const data = bits(d, 4).reverse();       // data[i] = I_i
    if (mux(data, bits(s, 2)) === data[s]) ok++;
  }
  console.log(`           ${bits(s, 2).join("  ")}  | I${s}`);
}
console.log(`checked ${ok} of 64 cases: Y always equals the selected input`);

console.log("\n3:8 decoder  EN A2 A1 A0 | Y0 Y1 Y2 Y3 Y4 Y5 Y6 Y7");
console.log("              0  x  x  x |", decoder([0, 0, 0], 0).join("  "));
for (let v = 0; v < 8; v++)
  console.log(`              1  ${bits(v, 3).join("  ")} |`, decoder(bits(v, 3), 1).join("  "));

4:1 mux   S1 S0 | Y
           0  0  | I0
           0  1  | I1
           1  0  | I2
           1  1  | I3
checked 64 of 64 cases: Y always equals the selected input

3:8 decoder  EN A2 A1 A0 | Y0 Y1 Y2 Y3 Y4 Y5 Y6 Y7
              0  x  x  x | 0  0  0  0  0  0  0  0
              1  0  0  0 | 1  0  0  0  0  0  0  0
              1  0  0  1 | 0  1  0  0  0  0  0  0
              1  0  1  0 | 0  0  1  0  0  0  0  0
              1  0  1  1 | 0  0  0  1  0  0  0  0
              1  1  0  0 | 0  0  0  0  1  0  0  0
              1  1  0  1 | 0  0  0  0  0  1  0  0
              1  1  1  0 | 0  0  0  0  0  0  1  0
              1  1  1  1 | 0  0  0  0  0  0  0  1

কাজ করা উদাহরণ — দুটি 3:8 বা পাঁচটি 2:4 দিয়ে 4:16 decoder

দুটি 3:8 দিয়ে: চার input A, B, C, D (A = MSB). B, C, D দুটি decoder-এরই input-এ সমান্তরালে যায়। A ঠিক করে কোনটি চালু: নিচের decoder-এর EN = A′ (একটি NOT দিয়ে), ওপরের decoder-এর EN = A. A = 0 হলে নিচের decoder Y₀–Y₇ দেয়, A = 1 হলে ওপরেরটি Y₈–Y₁₅. যেমন ABCD = 1011: A = 1, তাই ওপরের decoder চালু, BCD = 011 বলে তার ৩ নম্বর output — অর্থাৎ সামগ্রিক Y₁₁. ঠিক, কারণ 1011 = ১১। (বাস্তব 74138-এর তিনটি enable থাকায় এখানে বাইরের NOT-ও লাগে না — একটির active-low enable-এ A, অন্যটির active-high enable-এ A.)

পাঁচটি 2:4 দিয়ে: এটি একটি দুই স্তরের গাছ। প্রথম স্তরে একটি 2:4 decoder ওপরের দুটি বিট AB নেয়; তার চারটি output চারটি দ্বিতীয়-স্তরের 2:4 decoder-এর EN-এ যায়। দ্বিতীয় স্তরের চারটিই CD নেয়। AB = 10 হলে শুধু তৃতীয় decoder (নম্বর ২) চালু, আর CD = 11 হলে তার ৩ নম্বর output — সামগ্রিক নম্বর ২ × ৪ + ৩ = ১১। মোট ১ + ৪ = ৫টি. সাধারণ নিয়ম: k:২^k decoder দিয়ে বড় decoder বানাতে শেষ স্তরে (মোট output ÷ ২^k)টি, তার ওপর enable বণ্টনের জন্য আরেকটি ছোট গাছ।

কাজ করা উদাহরণ — decoder আর OR gate দিয়ে function

Decoder-এর প্রতিটি output একটি minterm, আর যেকোনো function হলো তার minterm-গুলোর OR (canonical SOP). তাই একটি n:২ⁿ decoder আর প্রতিটি output function-এর জন্য একটি OR gate — যত function-ই হোক, decoder একটিই। সবচেয়ে প্রচলিত উদাহরণ full adder (পর্ব ১১): input A, B, C_in.

• Sum S = 1 হয় যখন বিজোড় সংখ্যক input 1: S = Σm(1, 2, 4, 7) → Y₁, Y₂, Y₄, Y₇ একটি ৪-input OR-এ।
• Carry C_out = 1 হয় যখন অন্তত দুটি input 1: C_out = Σm(3, 5, 6, 7) → Y₃, Y₅, Y₆, Y₇ আরেকটি ৪-input OR-এ।

একটি 3:8 decoder, দুটি OR — পুরো full adder. Y₇ দুটি OR-এই যায়, এতে কোনো সমস্যা নেই: একটি output অনেক gate-কে চালাতে পারে (fan-out-এর সীমার মধ্যে)। কোনো function-এ অর্ধেকের বেশি minterm থাকলে উল্টো কৌশল সস্তা: F′-এর minterm-গুলো একটি NOR-এ দিন। Active-low output-এর decoder হলে OR-এর জায়গায় NAND বসে — কারণ De Morgan অনুযায়ী (Y₁′·Y₂′·…)′ = Y₁ + Y₂ + …

৫ · Address decoding আর 7-segment — decoder বাস্তবে

মহল্লার কথা ভাবুন। চিঠিতে লেখা “রোড ৩, বাড়ি ১২”. ডাকপিয়ন প্রথমে রোড নম্বর দেখে সঠিক গলিতে ঢোকেন, তারপর বাড়ি নম্বর দেখে দরজা খোঁজেন। কম্পিউটারের মেমরিও এভাবে সাজানো: CPU একটি ঠিকানা (address) পাঠায়; ঠিকানার ওপরের কয়েকটি বিট ঠিক করে কোন chip (গলি), আর নিচের বিটগুলো সেই chip-এর ভেতরের কোন byte (বাড়ি)। ওপরের বিটগুলো থেকে chip বাছাইয়ের কাজটি করে একটি decoder — একে বলে address decoding, আর প্রতিটি chip-এর যে input-এ decoder-এর লাইন যায় তার নাম chip select (CS).

কাজ করা উদাহরণ — চারটি 16 KiB chip, 64 KiB ঠিকানা

ধরুন একটি ছোট ৮-বিট ধরনের computer-এর ১৬টি address লাইন A₁₅…A₀, অর্থাৎ ২^১৬ = ৬৫,৫৩৬টি ঠিকানা (64 KiB). আমাদের কাছে চারটি 16 KiB-এর মেমরি chip. প্রতিটি chip-এর ভেতরে ঠিকানা লাগে ২^১৪ = 16 KiB-এর জন্য ১৪টি বিট — A₁₃…A₀, যা চারটি chip-এ সমান্তরালে যায়। বাকি ওপরের দুটি বিট A₁₅A₁₄ যায় একটি 2:4 decoder-এ, যার চারটি output চারটি chip-এর CS-এ। এর ফলে যে ঠিকানা-বণ্টন দাঁড়ায়, তাকে বলে memory map:

Hex-এ ব্যাপারটি চোখে পড়ে: ঠিকানার প্রথম hex অঙ্ক 0–3 হলে chip 0, 4–7 হলে chip 1, 8–B হলে chip 2, C–F হলে chip 3 — কারণ প্রথম hex অঙ্কের ওপরের দুটি বিটই A₁₅A₁₄. ভেতরের offset পেতে ঠিকানা থেকে ওপরের দুটি বিট মুছে দিন (addr & 0x3FFF).

আধুনিক computer-এ এই কাজ আরও বড় পরিসরে হয় — DRAM-এর ভেতরে row আর column decoder, chipset বা SoC-এর ভেতরে ঠিকানা দেখে RAM, ROM নাকি কোনো device — সব একই নীতিতে। বাস্তব মেমরির address decoding দেখবেন পর্ব ৪৯-এ (Main memory), আর device-গুলোকে ঠিকানা দেওয়ার memory-mapped I/O ও port I/O-র decoding পর্ব ৫১-এ (I/O আর bus). নিচের অংশ ৬-এর simulator-এ এই memory map-টি কোডে চালিয়ে দেখবেন।

7-segment display decoder — ক্যালকুলেটরের অঙ্ক

বাজারের ক্যালকুলেটর বা ডিজিটাল ঘড়ির প্রতিটি অঙ্ক সাতটি দাগে (segment a থেকে g) তৈরি — এটি 7-segment display. একটি BCD অঙ্ক (৪ বিট, ০–৯) থেকে কোন দাগগুলো জ্বলবে তা বের করার circuit-কে 7-segment decoder বলে। নামে decoder হলেও এটি one-hot নয় — একটি ৪-input, ৭-output code converter, যার প্রতিটি output আলাদা একটি function. যেমন ওপরের দাগ a জ্বলে ০, ২, ৩, ৫, ৬, ৭, ৮, ৯-এ (১ আর ৪-এ নয়)। ১০–১৫ BCD-তে কখনো আসে না, তাই সেগুলো don't care. পর্ব ০৯-এর K-map দিয়ে don't care কাজে লাগিয়ে পাওয়া যায় (A = MSB):

৭টি segment-এর জন্য ৭টি এমন সূত্র — K-map অনুশীলনের ক্লাসিক সমস্যা, পর্ব ০৯-এ বিস্তারিত। ল্যাবে এর জন্য তৈরি IC-ও পাওয়া যায় (যেমন 7447 বা 4511 ধরনের BCD-to-7-segment decoder).

৬ · Encoder আর priority encoder — অনেক লাইন থেকে একটি নম্বর

Encoder decoder-এর উল্টো: ২ⁿটি input লাইনের কোনটি চালু, তার n-বিটের নম্বর বের করে। 4:2 encoder-এর input D₀…D₃, output Y₁Y₀. যদি ধরে নিই একবারে ঠিক একটি input 1, তাহলে Y₁ = 1 হয় D₂ বা D₃ চালু হলে, Y₀ = 1 হয় D₁ বা D₃ চালু হলে:

8:3 encoder-ও একই রকম: Y₂ = D₄ + D₅ + D₆ + D₇, Y₁ = D₂ + D₃ + D₆ + D₇, Y₀ = D₁ + D₃ + D₅ + D₇ — প্রতিটি output বিট সেই input-গুলোর OR, যাদের নম্বরে ওই বিট 1. মাত্র তিনটি OR gate!

দুটি সমস্যা — একসাথে কয়েকজন, আর কেউ না

কিন্তু “ঠিক একটি input 1” অনুমানটি বাস্তবে টেকে না। সমস্যা ১: D₁ আর D₂ একসাথে 1 হলে সাধারণ 4:2 encoder দেয় Y₁Y₀ = 11 — অর্থাৎ ৩, যে লাইন আদৌ চালু নয়! সমস্যা ২: কোনো input চালু না থাকলে output 00 — আর D₀ চালু থাকলেও 00. দুটি সম্পূর্ণ ভিন্ন অবস্থা একই রকম দেখায়।

সমাধান priority encoder: প্রতিটি input-এর একটি অগ্রাধিকার আছে (সাধারণত বড় নম্বর = বেশি অগ্রাধিকার), আর একাধিক চালু থাকলে output হয় সবচেয়ে উঁচু চালু input-এর নম্বর। সাথে একটি বাড়তি output V (valid): অন্তত একটি input চালু থাকলে V = 1. ব্যাংকের লাইনে একজন বয়স্ক মানুষ বা প্রতিবন্ধী গ্রাহক এলে তাঁকে আগে ডাকা হয় — বাকিরা যতক্ষণ থাকুন, কাউন্টার একবারে একজনকেই ডাকে, আর লাইন ফাঁকা হলে “এখন কেউ নেই” বাতি জ্বলে।

টেবিলে দুই ধরনের x আছে। Input-এর x মানে “এই নিচু অগ্রাধিকারের লাইন যা খুশি থাকুক” — তাই পাঁচ সারিতেই ১৬টি সারি ঢাকা পড়েছে। Output-এর x মানে don't care: V = 0 হলে Y কেউ পড়ে না। সূত্র বের করা: Y₁ = 1 শেষ দুই সারিতে: D₃ + D₃′D₂ = D₃ + D₂ (absorption: X + X′Y = X + Y). Y₀ = 1 তৃতীয় আর পঞ্চম সারিতে: D₃′D₂′D₁ + D₃ = D₃ + D₂′D₁. আর V = D₀ + D₁ + D₂ + D₃.

সাধারণ encoder-এর সাথে পার্থক্য শুধু Y₀-এ D₂′ — “D₁ তখনই গোনা হবে যখন তার চেয়ে উঁচু D₂ নীরব”। একই যুক্তিতে 8:3 priority encoder (I₇ সবচেয়ে উঁচু):

• Y₂ = I₇ + I₆ + I₅ + I₄
• Y₁ = I₇ + I₆ + I₅′I₄′(I₃ + I₂)
• Y₀ = I₇ + I₆′I₅ + I₆′I₄′I₃ + I₆′I₄′I₂′I₁
• V = I₀ + I₁ + … + I₇

Y₀-এর পদগুলো পড়ে দেখুন: I₅ গোনা হয় যদি I₆ নীরব থাকে (I₇ চালু হলে প্রথম পদই 1 করে দেয়, তাই I₇′ লেখার দরকার হয়নি); I₃ গোনা হয় যদি I₆ আর I₄ নীরব (I₅ চালু থাকলে Y₀ এমনিতেই 1). এই ছোট সরলীকরণগুলোই পরীক্ষায় সূত্র ছোট করার কৌশল। এবার একটি বাস্তব দৃশ্যে দেখুন priority encoder একসাথে আসা অনুরোধ কীভাবে সামলায়:

এই কারণেই priority encoder interrupt সামলানোর hardware-এর একটি মূল অংশ: কয়েকটি device একসাথে CPU-র মনোযোগ চাইলে কে আগে পাবে, তা এক নিমেষে ঠিক হয়ে যায় — বিস্তারিত পর্ব ৫২-এ (Interrupt আর DMA). আরেকটি পুরোনো ব্যবহার keyboard: একটি চাপা চাবিকে তার কোডে বদলানো, আর একসাথে দুটি চাবি চাপলে একটিকে বেছে নেওয়া। (আধুনিক keyboard সাধারণত একটি microcontroller দিয়ে চাবির matrix বারবার scan করে, কিন্তু ধারণা একই।) Floating point-এর normalization-এ “প্রথম 1 বিটটি কোথায়” খোঁজার leading-zero counter-ও আসলে একটি বড় priority encoder (পর্ব ২৪)।

নিচের কোড প্রথমে হাতে বের করা 8:3 সূত্রগুলোকে ২৫৬টি সম্ভাব্য input-এ আচরণের সাথে মেলায়, তারপর কয়েকটি নকশায় encoder চালায়, শেষে অংশ ৫-এর memory map-এর decoder চালায়:

// 8:3 priority encoder (I7 = highest priority) checked against its gate equations,
// then a 2:4 decoder on A15 A14 choosing one of four 16 KiB memory chips.
function priorityEncoder(I) {               // I[k] = request on input k
  for (let k = 7; k >= 0; k--) if (I[k]) return { y: k, v: 1 };
  return { y: 0, v: 0 };                     // no request: V = 0, Y meaningless
}
function gates(I) {                          // equations derived by hand
  const n = (b) => 1 - b;
  const y2 = I[7] | I[6] | I[5] | I[4];
  const y1 = I[7] | I[6] | (n(I[5]) & n(I[4]) & (I[3] | I[2]));
  const y0 = I[7] | (n(I[6]) & I[5]) | (n(I[6]) & n(I[4]) & I[3]) | (n(I[6]) & n(I[4]) & n(I[2]) & I[1]);
  return 4 * y2 + 2 * y1 + y0;
}
let agree = 0;
for (let p = 0; p < 256; p++) {
  const I = [...Array(8)].map((_, k) => (p >> k) & 1);
  const r = priorityEncoder(I);
  if (!r.v || gates(I) === r.y) agree++;
}
console.log(`gate equations agree with behaviour on ${agree}/256 inputs`);
console.log("I7..I0     Y2Y1Y0  V");
for (const s of ["00000000", "00000001", "00010100", "01100000", "00001010", "10000001"]) {
  const I = s.split("").reverse().map(Number);    // string is I7..I0
  const r = priorityEncoder(I);
  console.log(`${s}   ${r.v ? r.y.toString(2).padStart(3, "0") : "xxx"}     ${r.v}`);
}
const hex = (a) => "0x" + a.toString(16).toUpperCase().padStart(4, "0");
console.log("\nchip  A15 A14  range");
for (let c = 0; c < 4; c++)
  console.log(` CS${c}    ${c >> 1}   ${c & 1}   ${hex(c << 14)}-${hex((c << 14) | 0x3FFF)}`);
for (const a of [0x1234, 0x3FFF, 0x4000, 0x9ABC, 0xC000, 0xFFFF]) {
  const top = a >> 14;                       // decoder input = A15 A14
  console.log(`${hex(a)} -> CS${top} active, offset inside chip ${hex(a & 0x3FFF)}`);
}

gate equations agree with behaviour on 256/256 inputs
I7..I0     Y2Y1Y0  V
00000000   xxx     0
00000001   000     1
00010100   100     1
01100000   110     1
00001010   011     1
10000001   111     1

chip  A15 A14  range
 CS0    0   0   0x0000-0x3FFF
 CS1    0   1   0x4000-0x7FFF
 CS2    1   0   0x8000-0xBFFF
 CS3    1   1   0xC000-0xFFFF
0x1234 -> CS0 active, offset inside chip 0x1234
0x3FFF -> CS0 active, offset inside chip 0x3FFF
0x4000 -> CS1 active, offset inside chip 0x0000
0x9ABC -> CS2 active, offset inside chip 0x1ABC
0xC000 -> CS3 active, offset inside chip 0x0000
0xFFFF -> CS3 active, offset inside chip 0x3FFF

৭ · Comparator, parity আর code converter

সমতা — XNOR দিয়ে

দুটি বিট A আর B সমান কি না, তা বলে XNOR: A ⊙ B = (A ⊕ B)′ = A′B′ + AB — দুটি সমান হলে 1. দুটি n-বিটের সংখ্যা সমান হয় যখন প্রতিটি অবস্থানের বিট সমান। তাই প্রতিটি বিটজোড়ার জন্য x_i = A_i ⊙ B_i, আর সমতা E = x_n−1·…·x₁·x₀ — n টি XNOR আর একটি AND. Cache-এ tag মেলানো (পর্ব ৪৫) ঠিক এই রকম একটি বড় equality comparator.

Magnitude comparator — কোনটি বড়

দুটি সংখ্যা তুলনা আমরা যেভাবে করি, magnitude comparator-ও তাই করে: বাঁ দিক (MSB) থেকে শুরু করুন; প্রথম যে অবস্থানে বিট আলাদা, সেখানে যার 1, সে-ই বড়। ২-বিটের A = A₁A₀, B = B₁B₀-এর জন্য:

প্রথম পদ: MSB-তেই A-র 1, B-র 0 — A বড়, আর কিছু দেখার দরকার নেই। দ্বিতীয় পদ: MSB সমান (x₁ = 1), তখন পরের বিট ঠিক করে। ৪-বিটে একই ছক আরও দুই ধাপ লম্বা হয়:

L-কে আলাদা করে বানানোর দরকার নেই: তিনটি অবস্থার ঠিক একটি সত্য, তাই G আর E দুটিই 0 হলে L = 1. (এই সূত্রগুলো ১৬ × ১৬ = ২৫৬টি জোড়ায় script দিয়ে যাচাই করা হয়েছে।)

Cascading — বড় সংখ্যার তুলনা: ৮-বিট তুলনার জন্য দুটি ৪-বিট comparator জোড়া যায়। ওপরের (বেশি গুরুত্বের) ৪ বিটের comparator-এর তিনটি বাড়তি “cascade input” থাকে, যেখানে নিচের comparator-এর G, E, L আসে। নিয়ম: ওপরের ৪ বিট আলাদা হলে সেটিই উত্তর; সমান হলে নিচের অংশের ফল পার করে দেওয়া হয়। ল্যাবের 7485 ধরনের ৪-বিট magnitude comparator IC-তে এই cascade input থাকে। মনে রাখুন, এটি unsigned তুলনা; two's complement-এর signed তুলনায় sign বিটের নিয়ম উল্টো। পর্ব ১৩-এ দেখবেন CPU প্রায়ই আলাদা magnitude comparator না বানিয়ে ALU-তে বিয়োগ করেই তুলনা করে — x86 আর ARM ফলটি flag-এ রাখে, আর RISC-V-এর slt আর blt কোনো flag register ছাড়াই একই বিয়োগের নিয়ম (N ⊕ V) কাজে লাগায়।

Parity generator আর checker — XOR-এর গাছ

ডেটা পাঠানোর সময় একটি বিট উল্টে গেলে ধরার সবচেয়ে সস্তা উপায় parity bit. Even parity-তে বাড়তি বিট P এমনভাবে বসানো হয় যাতে মোট 1-এর সংখ্যা জোড় হয়: P = D₃ ⊕ D₂ ⊕ D₁ ⊕ D₀ — এটি parity generator. গ্রহণকারী সব বিট আর P একসাথে XOR করে: ফল 0 হলে ঠিক আছে, 1 হলে বিজোড় সংখ্যক বিট উল্টেছে — এটি parity checker. যেমন 1011 0010-এ চারটি 1, তাই even parity বিট 0.

৮ বিটের parity-তে ৭টি ২-input XOR লাগে, কিন্তু সাজানোর ধরন গুরুত্বপূর্ণ। একটির পর একটি শিকল বানালে সংকেতকে ৭টি gate পার হতে হয়; জোড়ায় জোড়ায় গাছ বানালে (৪ → ২ → ১) মাত্র ৩ স্তর — log₂৮ = ৩। XOR associative বলে দুটির ফল একই, কিন্তু গাছটি অনেক দ্রুত। এক বিটের ভুল ধরা যায়, দুই বিট উল্টালে parity ধরতে পারে না — CRC আর Hamming code-এর মতো শক্তিশালী পদ্ধতি দেখুন কম্পিউটার নেটওয়ার্কস কোর্সের error detection পর্বে। ল্যাবে 74280 ধরনের ৯-বিট parity generator/checker IC পাওয়া যায়।

Code converter — binary ↔ Gray

পর্ব ০৪-এ Gray code-এর সূত্র দেখেছেন: g = b ⊕ (b ≫ 1). Hardware-এ এটি সরাসরি XOR gate: ৪ বিটে g₃ = b₃, g₂ = b₃ ⊕ b₂, g₁ = b₂ ⊕ b₁, g₀ = b₁ ⊕ b₀ — তিনটি XOR, সবগুলো সমান্তরালে, মাত্র এক স্তরের delay. উল্টো দিকে b₃ = g₃, b₂ = b₃ ⊕ g₂, b₁ = b₂ ⊕ g₁, b₀ = b₁ ⊕ g₀ — এখানে প্রতিটি বিট আগেরটির ওপর নির্ভর করে, তাই XOR-গুলো শিকলের মতো (n − 1 স্তর)। উদাহরণ: binary 1011 → Gray 1110; আর Gray 1110 → b₃ = 1, b₂ = 1 ⊕ 1 = 0, b₁ = 0 ⊕ 1 = 1, b₀ = 1 ⊕ 0 = 1 → 1011. BCD → excess-3 (প্রতিটি অঙ্কে +3), BCD → 7-segment — এগুলোও code converter, প্রতিটি output-এর জন্য একটি K-map.

৮ · CPU-র ভেতরে আর ল্যাবের IC-তে

Register file — কয়েকটি বড় mux আর একটি decoder

RISC-V (RV32I)-এর ৩২টি register, প্রতিটি ৩২ বিটের। একটি add x5, x6, x7 instruction-এ একসাথে দুটি register পড়তে হয় (x6, x7) আর একটি লিখতে হয় (x5). এই কাজের hardware-কে বলে register file, আর তার ভেতরটা এই পর্বের block দিয়েই তৈরি:

• দুটি read port = দুটি 32:1 mux, প্রতিটি ৩২ বিট চওড়া (অর্থাৎ প্রতি বিটে একটি করে, মোট ৩২টি 32:1 mux-এর সারি)। Instruction-এর ৫ বিটের rs1 ফিল্ড প্রথম mux-এর select-এ, rs2 দ্বিতীয়টির — ২^৫ = ৩২, তাই ঠিক ৫ বিট।
• Write port = একটি 5:32 decoder: rd ফিল্ড decoder-এর input-এ, আর RegWrite control সংকেত তার enable-এ। শুধু বাছাই করা register-এর write enable চালু হয়, আর পরের clock-এ শুধু সেটিই নতুন মান নেয়।
• RISC-V-এর x0 সবসময় ০ — hardware-এ decoder-এর ০ নম্বর output কোথাও লেখার অনুমতি দেয় না, আর read mux-এর ০ নম্বর input-এ সরাসরি ০ বসানো থাকে।

পুরো datapath-এ register file কীভাবে বসে, আর instruction-এর ফিল্ড থেকে এই select-গুলো কীভাবে আসে, দেখবেন পর্ব ৩২-এ (Single-cycle datapath). বড় processor-এ একসাথে অনেক instruction চলায় read port অনেক বেশি লাগে — তখন এই mux-গুলোই chip-এর জায়গা আর সময়ের বড় খরচ হয়ে দাঁড়ায় (ভাবনার প্রশ্ন ০৫)।

Verilog-এ একই block — উদাহরণ

বাস্তব নকশায় কেউ gate একটি একটি আঁকেন না; hardware description language-এ আচরণ লেখেন, আর synthesis tool gate বানায়। পর্ব ১৪-এ Verilog বিস্তারিত শিখবেন; এখানে শুধু দেখুন এই পর্বের তিনটি block কত ছোট করে লেখা যায় (synthesizable Verilog-2001, চালানো যায় না — উদাহরণ):

// উদাহরণ — 4:1 mux, 3:8 decoder with enable, 8:3 priority encoder
module mux4 (input wire [3:0] i, input wire [1:0] s, output wire y);
  assign y = i[s];                          // synthesis builds the AND-OR tree
endmodule

module dec3to8 (input wire [2:0] a, input wire en, output reg [7:0] y);
  always @* begin
    y = 8'b0;                               // default: every output 0
    if (en) y[a] = 1'b1;                    // exactly one line high
  end
endmodule

module prienc8 (input wire [7:0] i, output reg [2:0] y, output reg v);
  integer k;
  always @* begin
    y = 3'd0; v = 1'b0;
    for (k = 0; k < 8; k = k + 1)
      if (i[k]) begin y = k[2:0]; v = 1'b1; end   // higher k overwrites lower
  end
endmodule

Priority encoder-এর loop-টি hardware-এ “লুপ” নয় — synthesis tool এটিকে খুলে আটটি শর্তের একটি শিকল বানায়, যেখানে পরে আসা (বড় k) শর্ত আগেরটিকে ছাপিয়ে যায়। ফলাফল ঠিক অংশ ৬-এর সূত্রগুলোর সমান। প্রতিটি always @*-এ শুরুতে default মান দেওয়া জরুরি; না দিলে tool অনিচ্ছাকৃত latch বানিয়ে ফেলতে পারে — একটি প্রচলিত নতুনদের ভুল।

ল্যাবের পরিচিত IC

বিশ্ববিদ্যালয়ের ডিজিটাল লজিক ল্যাবে প্রায়ই 74-series-এর TTL বা CMOS (74HC, 74LS ইত্যাদি) chip দিয়ে এই block-গুলো হাতে জোড়া হয়। কয়েকটি বহুল ব্যবহৃত নম্বর (বিস্তারিত pin আর সংকেতের জন্য নির্মাতার datasheet দেখুন — সংস্করণভেদে সামান্য পার্থক্য থাকতে পারে):

৯ · AI-এর যুগে — নকশা নিজে simulate করে যাচাই

“এই function-টি 4:1 mux দিয়ে বানান” ধরনের প্রশ্নে AI চ্যাটবট দ্রুত একটি উত্তর দেয় — দেখতে নিখুঁত, কিন্তু প্রায়ই একটি data input ভুল। ভাষা মডেল truth table মনে মনে simulate করে না; কোন চলক select-এ আর কোনটি data-তে, MSB কোনটি — এসব নিয়মে সামান্য গোলমাল পুরো উত্তর বদলে দেয়। এই পর্বের বিষয়ে সাধারণ ভুলগুলো:

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

• কোন চলক কোন select-এ আর কোনটি MSB — প্রশ্ন আর উত্তরে একই আছে, মিলিয়েছি
• সব ২ⁿটি সারিতে নকশাটি simulate করেছি (হাতে, এই পর্বের synthesiser-এ, বা নিজের script-এ)
• Priority encoder-এ একসাথে কয়েকটি input চালু রেখে, আর সব শূন্য রেখে, V সহ পরীক্ষা করেছি
• Address map-এর প্রতিটি পরিসরের প্রথম আর শেষ ঠিকানা, আর সীমানার ঠিক পরের ঠিকানা পরীক্ষা করেছি
• IC-র নম্বর, active-low সংকেত আর pin — নির্মাতার datasheet-এ মিলিয়েছি