Foundationপ্রথম নীতি থেকে
LEVEL 2লেসন ৭/১৬মাঝারি৫০ মিনিট

Multiplexer ও Decoder — ডেটা রাউটিং-এর ভাষা

Multiplexers and Decoders

MUX এক তথ্য-নির্বাচক — N ইনপুট, log₂N select লাইন, ১ আউটপুট — আর এর dual, decoder। এই দুইটা ব্লক দিয়েই CPU-র মধ্যে data আর control সিগন্যাল রাউট হয়।

এই লেসন শেষে আপনি পারবেন

  • 2-to-1 MUX-কে গেট থেকে বানিয়ে এর boolean equation (Y = S′A + SB) আর truth table হাতে প্রতিষ্ঠা করতে পারবেন
  • ছোট MUX থেকে বড় MUX (4-to-1, 8-to-1) দুইভাবে বানাতে পারবেন — MUX-এর tree হিসেবে, আর decoder+AND array হিসেবে
  • যেকোনো n-variable Boolean function একটা single 2ⁿ-to-1 MUX দিয়ে বাস্তবায়ন করতে পারবেন — নতুন গেট বসিয়ে নয়, শুধু data input-এ truth table-এর মান বসিয়ে
  • Decoder আর demultiplexer-এর গঠনগত সম্পর্ক ব্যাখ্যা করে address decoding আর opcode decoding-এ এর ব্যবহার দেখাতে পারবেন
  • Encoder ও priority encoder-এর পার্থক্য বুঝে একাধিক input সক্রিয় থাকলে priority encoder ঠিক কী সিদ্ধান্ত নেয় তা ট্রেস করতে পারবেন

আগে যা বোঝা থাকা দরকার

আগে এটা বুঝি

গত কয়েকটা লেসনে আমরা adder বানিয়েছি — একটা সার্কিট যেটা সবসময় একটাই কাজ করে: যোগ করা। কিন্তু একটা বাস্তব CPU-তে হাজার হাজার তার (wire) থাকে, আর প্রতিটা মুহূর্তে সিদ্ধান্ত নিতে হয় — কোন তারের সিগন্যাল এখন গুরুত্বপূর্ণ, কোনটা এখন উপেক্ষা করা উচিত? register file-এর ৩২টা register-এর মধ্যে কোনটা এই মুহূর্তে ALU-তে পাঠানো হবে? RAM-এর কোটি কোটি ঠিকানার মধ্যে কোনটা এখন “সক্রিয়”?

এই প্রশ্নের উত্তর একটা সাধারণ, বিনয়ী circuit দেয় — multiplexer (MUX)। ধারণাটা এতটাই মৌলিক যে এটা ছাড়া কোনো CPU দুই ধাপ এগোতে পারবে না। আজকের লেসনে আমরা দেখব কীভাবে মাত্র কয়েকটা গেট দিয়ে “অনেকগুলো থেকে একটা বেছে নেওয়া” এই কাজটা সমাধান হয় — আর এর dual, decoder, যেটা উল্টো কাজ করে: একটা ঠিকানা থেকে ঠিক একটা সিগন্যাল সক্রিয় করে।

এই দুইটা ব্লক এতটাই মৌলিক যে এদের উপর ভিত্তি করেই তৈরি হবে পরের লেসনের ALU-র ভেতরের output-selection যন্ত্র, আর Level ৩-এর পুরো control unit।

মূল ধারণা

2-to-1 MUX — সবচেয়ে ছোট data selector

একটা multiplexer আসলে একটা controlled switch। দুইটা ডেটা ইনপুট (A, B), একটা select ইনপুট (S), আর একটা আউটপুট (Y)। নিয়ম সহজ:

S=0⇒Y=AS=1⇒Y=BS=0 \Rightarrow Y=A \qquad S=1 \Rightarrow Y=B

SY
0A
1B

এটাকে boolean expression-এ লিখলে:

Y=S′⋅A+S⋅BY = S' \cdot A + S \cdot B

কেন এই expression সঠিক তা যাচাই করা সহজ — S=0 হলে S'=1, তাই প্রথম term A, দ্বিতীয় term 0 (কারণ S=0); ফলে Y=A। S=1 হলে উল্টোটা ঘটে, Y=B।

গেট দিয়ে বানানো

এই একটা expression-ই সরাসরি একটা circuit — AND-AND-OR গঠন (একেই বলে AOI — AND-OR-Invert-এর পরিবার, যদিও এখানে কোনো invert নেই শেষে):

        ┌─────┐
   S ───┤ NOT ├─── S' ──────┐
        └─────┘              │
                              ▼
                          ┌───────┐
   A ─────────────────────┤  AND  ├──┐
                    S' ────┤       │  │
                          └───────┘  │      ┌──────┐
                                      ├──────┤  OR  ├──── Y
                          ┌───────┐   │      └──────┘
   B ─────────────────────┤  AND  ├──┘
                    S ─────┤       │
                          └───────┘
Fig 7.12-to-1 MUX — তিনটা গেট: একটা NOT, দুইটা AND, একটা OR। এই কাঠামোই প্রতিটা বড় MUX-এর ভিত্তি।

সম্পূর্ণ ৩-ভেরিয়েবল truth table (A, B, S — ৮ সারি) লিখলে দেখা যায়, expression-টা প্রতিটা row-তেই মেলে:

ABSY = S′A + SB
0000
0100
1001
1101
0010
0111
1010
1111

লক্ষ্য করুন — S=0 কলামে Y হুবহু A-এর মতো আচরণ করছে, S=1 কলামে Y হুবহু B-এর মতো। এটাই একটা MUX-এর সংজ্ঞা।

4-to-1 MUX — দুইভাবে বানানো যায়

চারটা ডেটা ইনপুট (I₀, I₁, I₂, I₃) থেকে একটা বেছে নিতে দুইটা select লাইন লাগে (S₁S₀), কারণ 2² = 4টা সম্ভাব্য combination দরকার:

S₁S₀Y
00I₀
01I₁
10I₂
11I₃

Y=I0S1′S0′+I1S1′S0+I2S1S0′+I3S1S0Y = I_0 S_1' S_0' + I_1 S_1' S_0 + I_2 S_1 S_0' + I_3 S_1 S_0

এই সার্কিট বানানোর দুইটা সমতুল্য উপায় আছে — দুটোই গুরুত্বপূর্ণ, কারণ দুটোই বাস্তবে ব্যবহৃত হয়।

পদ্ধতি ১ — 2-to-1 MUX-এর tree। তিনটা 2-to-1 MUX দিয়ে: প্রথম MUX I₀, I₁-এর মধ্যে বেছে নেয় S₀ দিয়ে, দ্বিতীয় MUX I₂, I₃-এর মধ্যে বেছে নেয় S₀ দিয়ে, আর তৃতীয় (শেষ) MUX ওই দুইটার আউটপুটের মধ্যে বেছে নেয় S₁ দিয়ে।

   I0 ──┐
        ├─[2:1 MUX]── (S0 নির্বাচক) ──┐
   I1 ──┘                              │
                                        ├─[2:1 MUX]── (S1 নির্বাচক) ── Y
   I2 ──┐                              │
        ├─[2:1 MUX]── (S0 নির্বাচক) ──┘
   I3 ──┘
Fig 7.24-to-1 MUX — 2-to-1 MUX-এর tree হিসেবে। এই প্যাটার্ন recursively বড় করা যায়: 8-to-1 = দুইটা 4-to-1 + একটা 2-to-1।

পদ্ধতি ২ — decoder + AND array। একটা 2-to-4 decoder S₁S₀-কে চারটা “one-hot” লাইনে রূপান্তর করে (ঠিক একটা লাইন 1, বাকি সব 0)। প্রতিটা decoder-আউটপুটকে সংশ্লিষ্ট Iᵢ-এর সাথে AND করে, তারপর সব AND-এর output একটা বড় OR-এ দিলেই Y পাওয়া যায় — এটা ঠিক উপরের expression-টাই gate-এ রূপান্তরিত।

দুইটা পদ্ধতিই একই truth table দেয় — পার্থক্য শুধু gate delay আর gate count-এ (tree পদ্ধতিতে signal-কে দুইটা MUX-layer পার হতে হয়, decoder পদ্ধতিতে এক-স্তরের AND-OR, কিন্তু decoder নিজেও ভেতরে গেট নিয়ে গঠিত)। এই লেসনের decoder অংশে এই সম্পর্কটা আরও স্পষ্ট হবে।

গভীর অন্তর্দৃষ্টি — MUX নিজেই একটা universal building block

গত module-এ (Level ০, Boolean Algebra লেসন) আমরা দেখেছিলাম শুধু NAND গেট দিয়ে যেকোনো Boolean function বানানো যায় — সেটা ছিল “bottom-up” পথ: primitive গেট জোড়া লাগিয়ে জটিল ফাংশন তৈরি করা।

MUX একটা সম্পূর্ণ ভিন্ন, hardware-flavored পথে ঠিক একই সিদ্ধান্তে পৌঁছায় — কিন্তু bottom-up নয়, lookup-based।

উদাহরণ — XOR-কে 4-to-1 MUX দিয়ে বানানো। f(A,B) = A \oplus B-এর truth table:

ABf
000
011
101
110

সরাসরি বসিয়ে দিন: select লাইন S₁=A, S₀=B, data input I₀=0, I₁=1, I₂=1, I₃=0 (এই চারটা মান স্থির — সরাসরি ground/Vcc-এ তার বাঁধা)। আর কোনো XOR গেট লাগলই না — একটা 4-to-1 MUX, চারটা তার আর তারের প্রান্তে হার্ডওয়্যার্ড 0/1 দিয়েই XOR “বাস্তবায়িত” হয়ে গেল।

Shannon Expansion — MUX-এর আকার অর্ধেক করার একটা কৌশল

আগের অন্তর্দৃষ্টিতে আমরা n ভেরিয়েবলের function বানাতে 2ⁿ-to-1 MUX ব্যবহার করেছি — select লাইনে সবগুলো ভেরিয়েবল। কিন্তু একটা চতুর পর্যবেক্ষণ দিয়ে MUX-এর আকার অর্ধেক করা যায়।

এটা আসলে K-map লেসনের একটা ধারণারই পুনরাবৃত্তি — Shannon expansion (বা cofactor expansion): যেকোনো function f(x₁, ..., xₙ)-কে শেষ ভেরিয়েবল xₙ দিয়ে ভাগ করে লেখা যায়:

f=xn′⋅f∣xn=0+xn⋅f∣xn=1f = x_n' \cdot f|_{x_n=0} + x_n \cdot f|_{x_n=1}

এখানে “f-এ xₙ=0 বসিয়ে দিলে যা থাকে” তাকেই f cofactor (residual function) বলা হয় — এই দুইটা residual function-ই তখন শুধু বাকি n-1 টা ভেরিয়েবলের উপর নির্ভর করে। এটা ঠিক একটা 2-to-1 MUX-এর equation-এর মতোই দেখতে (Y = S'A + SB) — কারণ এটাই সেই একই কাঠামো, শুধু A আর B এখন ধ্রুবক নয়, বরং বাকি ভেরিয়েবলের উপর নির্ভরশীল sub-function।

ব্যবহারিক ফল: n ভেরিয়েবলের function বানাতে 2ⁿ-to-1 MUX-এর বদলে একটা 2^(n-1)-to-1 MUX দিয়েও চলে — শেষ ভেরিয়েবল xₙ-কে select লাইনে না দিয়ে, তাকে data input-এ (0, 1, xₙ, বা xₙ' — এই চারটার যেকোনো একটা, residual function অনুযায়ী) বসিয়ে। অর্ধেক select লাইন, অর্ধেক data input — সমান কার্যকারিতা।

Demultiplexer (DEMUX) — উল্টো দিকের সার্কিট

MUX একাধিক ইনপুট থেকে একটা বেছে নেয়। DEMUX ঠিক উল্টোটা করে — একটা মাত্র ইনপুট নিয়ে সেটাকে Nটা সম্ভাব্য আউটপুটের ঠিক একটায় পাঠায়, বাকি সব আউটপুট নিষ্ক্রিয় (0) থাকে।

S₁S₀Y₀Y₁Y₂Y₃
00In000
010In00
1000In0
11000In

প্রতিটা আউটপুট একটা সাধারণ AND গেট দিয়ে বানানো যায় — Yᵢ = In · (select লাইনগুলোর সংশ্লিষ্ট minterm)।

              ┌───────┐
   In ──┬─────┤  AND  ├──── Y0   (সক্রিয় যখন S1S0 = 00)
        │     └───────┘
        │     ┌───────┐
        ├─────┤  AND  ├──── Y1   (সক্রিয় যখন S1S0 = 01)
        │     └───────┘
        │     ┌───────┐
        ├─────┤  AND  ├──── Y2   (সক্রিয় যখন S1S0 = 10)
        │     └───────┘
        │     ┌───────┐
        └─────┤  AND  ├──── Y3   (সক্রিয় যখন S1S0 = 11)
              └───────┘
   S1,S0 প্রতিটা AND গেটে (decode করা আকারে) যায়
Fig 7.31-to-4 DEMUX — চারটা AND গেট, প্রতিটার একটা ইনপুট 'In', অন্যটা select লাইনের একটা নির্দিষ্ট combination।

Decoder — একটা address থেকে ঠিক একটা “হ্যাঁ”

DEMUX-এর In ইনপুটটা যদি সবসময় 1-এ বাঁধা রাখা হয় (মানে “সবসময় enable”), তাহলে যা অবশিষ্ট থাকে সেটাই একটা decoder: n টা ইনপুট থেকে 2ⁿ টা আউটপুটে যায়, প্রতিটা বৈধ input combination-এ ঠিক একটা আউটপুট 1 (active), বাকিগুলো 0। একেই বলে one-hot output।

এই সম্পর্কটা মনে রাখার মতো:

2-to-4 decoder-এর সম্পূর্ণ truth table:

A₁A₀D₀D₁D₂D₃
001000
010100
100010
110001

D0=A1′A0′D1=A1′A0D2=A1A0′D3=A1A0D_0 = A_1'A_0' \quad D_1 = A_1'A_0 \quad D_2 = A_1A_0' \quad D_3 = A_1A_0

প্রতিটা Dᵢ মূলত একটা minterm — Boolean algebra লেসনে যা শেখা হয়েছিল, সেই একই ধারণা এখন সরাসরি হার্ডওয়্যারে: একটা n-input decoder আসলে n ভেরিয়েবলের সবগুলো সম্ভাব্য minterm একসাথে, প্যারালালে বানিয়ে দেয়।

বাস্তব decoder chip-এ (যেমন 74138, ৩-থেকে-৮) সাধারণত একটা বা একাধিক Enable ইনপুটও থাকে — enable 0 হলে সব আউটপুট নিষ্ক্রিয়, A ইনপুট যাই হোক না কেন। এই একটা পিন দিয়েই ছোট decoder জোড়া লাগিয়ে বড় decoder বানানো যায় (cascading)।

3-to-8 decoder ও cascading — ছোট থেকে বড় বানানো

প্যাটার্নটা n-input-এ সাধারণীকরণ করা যায়: একটা n-to-2ⁿ decoder-এ n টা input, 2ⁿ টা one-hot output। বাস্তব জগতের সবচেয়ে পরিচিত decoder chip — 74138, একটা 3-to-8 decoder:

A₂A₁A₀সক্রিয় আউটপুট
000Y0
001Y1
010Y2
011Y3
100Y4
101Y5
110Y6
111Y7

74138-এ তিনটা Enable ইনপুট আছে — G1 (active-high), G2A, G2B (দুইটাই active-low)। তিনটাই একসাথে সক্রিয় (G1=1, G2A=G2B=0) না হলে সব আউটপুট নিষ্ক্রিয়, A যাই হোক না কেন। এই বাড়তি enable-লজিকটাই cascading সম্ভব করে — নিচের figure-এ দুইটা 3-to-8 decoder জোড়া লাগিয়ে একটা 4-to-16 decoder বানানো হয়েছে, একটা বাড়তি select বিট (A₃) দিয়ে কোন 8-block সক্রিয় হবে তা ঠিক করে।

                    ┌─────────────────┐
   A3 = 0 ──────────┤ Enable           │
   A2,A1,A0 ─────────┤ Decoder #1       ├──── Y0..Y7
                    │ (3-to-8)         │
                    └─────────────────┘

                    ┌─────────────────┐
   A3 = 1 ──────────┤ Enable           │
   A2,A1,A0 ─────────┤ Decoder #2       ├──── Y8..Y15
                    │ (3-to-8)         │
                    └─────────────────┘

   A3 সরাসরি এক decoder-এর Enable-এ, আর তার NOT অন্যটার Enable-এ —
   ফলে A3 = 0 হলে শুধু Decoder #1 জেগে থাকে, A3 = 1 হলে শুধু #2।
Fig 7.4দুইটা 3-to-8 decoder + একটা বাড়তি select বিট (A₃) = একটা 4-to-16 decoder। A₃ নিজেই একটা 1-to-2 DEMUX-এর মতো কাজ করছে, ঠিক কোন 8-block-এর enable সক্রিয় হবে তা ঠিক করে।

এই একই কৌশল বারবার প্রয়োগ করে (আরেকটা বাড়তি select বিট, আরও দুইটা 4-to-16 ব্লক…) বাস্তবে যেকোনো আকারের decoder বানানো সম্ভব — এটাই বড় memory system-এ শত শত মেগাবাইট address space কয়েকটা ছোট, সস্তা, standard-part decoder চিপ দিয়ে সামলানোর আসল প্রকৌশল কৌশল।

Tri-state buffer — bus শেয়ার করার আরেকটা বাস্তব কৌশল

MUX একটাই উপায় নয় “অনেক উৎস থেকে একটা বেছে নেওয়ার।” বাস্তব বাসে (bus) আরেকটা কৌশল খুব সাধারণ — tri-state buffer। এটা একটা সাধারণ buffer গেট, কিন্তু তৃতীয় একটা আউটপুট state আছে সাধারণ 0/1-এর পাশাপাশি: high-impedance (Z) — মানে আউটপুট পিনটা কার্যত তারের সাথে সংযোগ-বিচ্ছিন্ন, না 0 না 1, বরং “চুপ” — অন্য কোনো ডিভাইস সেই একই তারে ভোল্টেজ বসালে কোনো সংঘর্ষ হয় না।

EnableInputOutput
0XZ (high-impedance — চুপ)
100
111

কৌশলটা: একাধিক ডিভাইস একই shared বাসে (একটা তার/তারের গুচ্ছ) নিজেদের tri-state buffer দিয়ে সংযুক্ত থাকে। যেকোনো মুহূর্তে, একটা decoder/enable-logic নিশ্চিত করে ঠিক একটা ডিভাইসের buffer enable হয় (বাকিরা Z, চুপ) — ফলে বাসে কোনো সংঘর্ষ (দুই ডিভাইস একসাথে ভিন্ন ভোল্টেজ চাপানো — যেটা শর্ট-সার্কিটের মতো ক্ষতিকর) হয় না।

বাস্তব ব্যবহার ১ — Memory address decoding

একটা CPU-র address bus-এ, ধরুন, ১৬টা বিট থাকে। সেই ১৬ বিটের উপরের কয়েকটা (যেমন উপরের ৪ বিট) একটা 4-to-16 decoder-এ যায়। Decoder-এর ১৬টা আউটপুটের প্রতিটা একটা আলাদা মেমরি চিপ বা peripheral device-এর chip-select (CS) লাইনে যুক্ত থাকে। CPU যখন একটা নির্দিষ্ট address-এ read/write করতে চায়, decoder স্বয়ংক্রিয়ভাবে ঠিক সেই একটা চিপ “জাগিয়ে তোলে” (তার CS pin সক্রিয় করে), বাকি সব চিপ ঘুমিয়ে থাকে (bus-এ কোনো প্রভাব ফেলে না)। এটাই একটা কম্পিউটারের memory map-এর হার্ডওয়্যার বাস্তবায়ন — Level ৪-এ যখন আমরা memory management নিয়ে পড়ব, এই একই decoder ধারণা সেখানে “physical address কোন device-এর” প্রশ্নের গোড়ায় থাকবে।

বাস্তব ব্যবহার ২ — Opcode decoding (Level ৩-এর পূর্বাভাস)

একটা CPU instruction-এর প্রথম কয়েক বিট সাধারণত opcode (কোন operation — ADD, SUB, LOAD…)। Control unit-এর ভেতরে একটা decoder এই opcode বিটগুলো নিয়ে one-hot সিগন্যালে রূপান্তর করে — “এটা ADD instruction” বোঝাতে ঠিক একটা লাইন সক্রিয় হয়, আর সেই লাইনটাই datapath-এর সঠিক control সিগন্যাল (register write enable, ALU op-select, ইত্যাদি) চালু করে। Level ৩-এ পুরো control unit যখন আমরা বানাব, তার কেন্দ্রেই থাকবে ঠিক এই decoder — শুধু input বড়, output বেশি জায়গায় যায়।

ভেতরে কী ঘটছে

যেখানে ব্লক ডায়াগ্রাম আর বাস্তব সিলিকন আলাদা হয়ে যায়

Encoder — decoder-এর উল্টো, কিন্তু ambiguous

Decoder নেয় n ইনপুট, দেয় 2ⁿ one-hot আউটপুট। Encoder ঠিক উল্টো কাজ করে — 2ⁿ (বা তার কম) one-hot ইনপুট নিয়ে n-বিট বাইনারি কোডে সংকুচিত করে।

I₀I₁I₂I₃A₁A₀
100000
010001
001010
000111

A0=I1+I3A1=I2+I3A_0 = I_1 + I_3 \qquad A_1 = I_2 + I_3

কিন্তু একটা মৌলিক সমস্যা আছে — এই সাধারণ encoder ধরে নেয় যে ঠিক একটা ইনপুট সক্রিয়। যদি I₁ আর I₂ দুটোই একসাথে 1 হয়, উপরের equation দেবে A₁A₀ = 11, যেটা I₃-এর কোড — সম্পূর্ণ ভুল উত্তর, আর কোনো সতর্কতা ছাড়াই। আর যদি কোনো ইনপুট সক্রিয় না থাকে (I₀=I₁=I₂=I₃=0), আউটপুট হয় 00 — যেটা আবার I₀-এর কোডের মতোই দেখায়, যদিও আসলে কিছুই সক্রিয় ছিল না।

Priority encoder — বাস্তব জগতের সমাধান

বাস্তব সিস্টেমে একাধিক সিগন্যাল প্রায়ই একই সাথে সক্রিয় হয় — এটা edge case নয়, এটাই স্বাভাবিক। Priority encoder এই সমস্যাটা সমাধান করে একটা নিয়ম দিয়ে: প্রতিটা ইনপুটকে একটা priority (গুরুত্ব) দেওয়া হয় (সাধারণত input নম্বর যত বেশি, priority তত বেশি), আর আউটপুট হয় সর্বোচ্চ priority-র সক্রিয় ইনপুট-এর কোড — বাকি নিম্ন-priority ইনপুট উপেক্ষিত হয়, তারা সক্রিয় থাকুক বা না থাকুক তাতে কিছু যায় আসে না।

4-to-2 priority encoder (I₃ সর্বোচ্চ priority):

I₃I₂I₁I₀A₁A₀V (valid)
0000XX0
0001001
001X011
01XX101
1XXX111

X মানে “don’t care” — সেই বিটের মান গুরুত্বহীন, কারণ উচ্চতর priority-র কোনো ইনপুট ইতিমধ্যে আউটপুট নির্ধারণ করে ফেলেছে। লক্ষ্য করুন সারি ৪-এ: I₃=0, I₂=1, তখন I₁ আর I₀ যাই হোক না কেন (এমনকি I₁=I₀=1 হলেও), আউটপুট শুধু I₂-এর কোড (10) — I₂-ই সর্বোচ্চ সক্রিয় priority। V বিটটা জানায় আদৌ কোনো ইনপুট সক্রিয় ছিল কি না — সাধারণ encoder-এর “সব-শূন্য মানেই I₀” সমস্যাটা এভাবেই সমাধান হয়।

Propagation delay — কেন MUX-tree বনাম decoder পদ্ধতি ভিন্ন গতির

আগে দেখানো 4-to-1 MUX-এর দুইটা নির্মাণ পদ্ধতি (tree বনাম decoder+AND) আচরণগতভাবে অভিন্ন হলেও গতিতে ভিন্ন। Logic Gate গ্লোসারিতে যেমন দেখা গেছে, প্রতিটা গেট একটা propagation delay যোগ করে, আর সবচেয়ে দীর্ঘ path (critical path) সিদ্ধান্ত নেয় circuit কত দ্রুত স্থির output দিতে পারে।

  • Tree পদ্ধতি: সিগন্যালকে দুইটা ধারাবাহিক 2-to-1 MUX পার হতে হয় — critical path = ২ MUX delay।
  • Decoder পদ্ধতি: decoder নিজেই ১-২ গেট গভীর (একটা NOT + একটা AND, প্যারালালে সব আউটপুটের জন্য), তারপর একটা AND + একটা বড় OR — critical path কাছাকাছি, তবে বড় n-এ decoder-এর ভেতরের গেট-fan-in বাড়ে।

n বড় হলে (যেমন ৩২-to-1 বা ৬৪-to-1), এই পার্থক্য গুরুত্বপূর্ণ হয়ে ওঠে — বাস্তব chip design-এ MUX-tree-র depth \log_2 n-এ বাড়ে, যেটা বড় n-এর জন্য decoder পদ্ধতির single-level fan-in সমস্যার (একটা গেটে অনেকগুলো ইনপুট, যেটা বাস্তব transistor-এ ধীর হয়ে যায়) চেয়ে প্রায়ই ভালো ট্রেড-অফ দেয়। এই কারণেই বড় MUX বাস্তবে প্রায়ই balanced tree হিসেবে বানানো হয়, একটা বিশাল সমতল AND-OR হিসেবে নয়।

কেন বড় fan-in ধীর — একটু গভীরে। একটা k-input AND/OR গেট বাস্তবে CMOS-এ কয়েকটা transistor সিরিজ/প্যারালালে বানানো হয় (pull-up/pull-down network)। k বাড়লে সেই transistor-চেইনের resistance-ও প্রায় রৈখিকভাবে বাড়ে, আর গেটের output-এ যে capacitance charge/discharge করতে হয় সেটাও বাড়ে — ফলে delay মোটামুটি k-এর সাথে (কিছু ক্ষেত্রে k²-এর কাছাকাছিও) বাড়ে, রৈখিক-বা-তার চেয়ে খারাপ হারে। বিপরীতে, একই k টা ইনপুটকে \log_2 k টা ধাপে ২-ইনপুট গেটের tree দিয়ে combine করলে delay বাড়ে \log_2 k-এর সমানুপাতিকভাবে — বড় k-এ পার্থক্যটা বিশাল।

n (MUX আকার)সমতল AND-OR fan-inTree depth (\log_2 n)
42-input2
83-input3
325-input5
2568-input8

Fan-in কলামটা ধীরে বাড়ে দেখতে লাগলেও, বাস্তবে প্রতিটা AND গেটের fan-in নিজেই select লাইনের সংখ্যার সমান বাড়ে না — বরং decoder-এর প্রতিটা আউটপুট গেটের ইনপুট সংখ্যা সরাসরি \log_2 n-এর সমানুপাতিক, তাই decoder-ভিত্তিক পদ্ধতিও শেষ পর্যন্ত কার্যত tree-এর মতোই আচরণ করে — শুধু ভেতরে ভিন্নভাবে সাজানো। এই পুরো বিশ্লেষণটাই একটা বাস্তব logic-synthesis tool (Yosys, Synopsys Design Compiler-এর মতো) স্বয়ংক্রিয়ভাবে করে যখন আপনি একটা HDL-এ শুধু আচরণ (Y = data[sel]) লিখে দেন — গেট-লেভেল গঠন বেছে নেওয়াটা tool-এর কাজ, designer-এর নয়।

উদাহরণ

সম্পূর্ণ ট্রেস করা উদাহরণ — 8-to-1 MUX দিয়ে একটা 3-variable function

ধরা যাক আমাদের একটা function দরকার: f(A,B,C) = 1 ঠিক তখনই যখন কমপক্ষে দুইটা ভেরিয়েবল 1 (এটাকে বলে majority function — তিনটা বিটের “ভোট” নিয়ে সংখ্যাগরিষ্ঠ ফলাফল বলা, একটা বাস্তব circuit primitive, যেমন triple-redundant sensor voting-এ ব্যবহৃত)।

ধাপ ১ — truth table বানাই:

ABCন্যূনতম দুইটা 1?f
000না0
001না0
010না0
011হ্যাঁ1
100না0
101হ্যাঁ1
110হ্যাঁ1
111হ্যাঁ1

ধাপ ২ — 8-to-1 MUX-এ বসাই: select লাইন S₂S₁S₀ = A,B,C, data input I₀..I₇ = truth table-এর f কলাম, ঠিক সেই ক্রমে:

I0=0, I1=0, I2=0, I3=1, I4=0, I5=1, I6=1, I7=1I_0=0,\ I_1=0,\ I_2=0,\ I_3=1,\ I_4=0,\ I_5=1,\ I_6=1,\ I_7=1

ধাপ ৩ — যাচাই। ধরুন A=1, B=0, C=1। Select লাইন S₂S₁S₀ = 101₂ = 5। MUX তাই I₅ কে আউটপুটে পাঠাবে — I₅ = 1। সত্যিই, A=1,B=0,C=1-এ দুইটা 1 আছে (A আর C), তাই f হওয়া উচিত 1। মিলে গেল — কোনো majority-vote গেট না বানিয়েই, শুধু একটা fixed MUX আর ছয়টা তারে 1/0 বেঁধেই।

এটাই আগের অংশের universal-function-generator দাবির একটা সম্পূর্ণ, ৩-ভেরিয়েবল কার্যকর প্রমাণ।

8-to-1 MUX দিয়ে majority function — select থেকে output পর্যন্ত
  1. A=1, B=0, C=1ইনপুট, যেগুলো একইসাথে select লাইনও
  2. S₂S₁S₀ = 101₂ = 5select লাইনের বাইনারি মান — এটাই "address"
  3. MUX ঠিকানা 5-এ যায়I₅ পিনের সাথে সংযুক্ত তার অনুসরণ করে
  4. I₅ = 1 (হার্ডওয়্যার্ড)truth table-এর ৬ষ্ঠ row থেকেই এই মান বসানো হয়েছিল
  5. Y = 1majority(1,0,1) = 1 — সঠিক উত্তর, কোনো নতুন গেট ছাড়াই

দ্বিতীয় উদাহরণ — একটা numeric address decoding trace

ধরুন একটা toy CPU-র address bus ১৬ বিট (A15..A0), মোট address space 2¹⁶ = 65536 বাইট (0x0000 থেকে 0xFFFF)। আমরা এই স্পেসটা ১৬টা সমান খণ্ডে ভাগ করব — প্রতিটা খণ্ড 4096 বাইট (4 KB, যেহেতু 65536/16=4096), প্রতিটা একটা আলাদা device-এর জন্য। এই ভাগটা করতে ঠিক উপরের বিট A15..A12 (৪ বিট) একটা 4-to-16 decoder-এ পাঠালেই হয় — এই ৪ বিটই ঠিক করে কোন 4KB খণ্ডে address পড়েছে, বাকি ১২ বিট (A11..A0) সেই খণ্ডের ভেতরের নির্দিষ্ট বাইট চেনায়।

প্রশ্ন — address 0x3A4F-এ কোন device সক্রিয় হবে?

ধাপ ১ — হেক্সকে বাইনারিতে লিখি:

0x3A4F = 0011 1010 0100 1111

ধাপ ২ — উপরের ৪ বিট আলাদা করি (decoder-এর input):

A15 A14 A13 A12 | A11 ... A0
 0   0   1   1  | 1010 0100 1111

A15A14A13A12 = 0011₂ = 3।

ধাপ ৩ — decoder-এর ঠিকানায় বসাই। 4-to-16 decoder-এর আউটপুট D3 সক্রিয় হবে (one-hot — বাকি ১৫টা আউটপুট নিষ্ক্রিয়)। যদি device #3 (ধরুন, একটা UART controller) সেই D3 লাইনে chip-select হিসেবে যুক্ত থাকে, ঠিক সেই UART-টাই এখন “জাগবে,” বাকি সব RAM/ROM/ অন্য peripheral bus থেকে বিচ্ছিন্ন (high-impedance) থাকবে।

ধাপ ৪ — device-এর ভেতরের ঠিকানা। বাকি ১২ বিট (A11..A0 = 1010 0100 1111₂ = 0xA4F) সেই UART controller-এর নিজস্ব রেজিস্টার ম্যাপে কোন byte-কে বোঝায় তা ঠিক করে — decoder-এর কাজ এখানেই শেষ, এরপরের ব্যাখ্যা সেই নির্দিষ্ট device-এর দায়িত্ব।

নিজে চালিয়ে দেখুন

EXPERIMENT

Digital/Logisim-এ 4-to-1 MUX বানিয়ে সব ১৬টা input combination যাচাই

Digital (hneemann) বা Logisim Evolution· ১৫ মিনিট

১. দুইটা Input pin S1, S0 বসান, চারটা Input pin I0, I1, I2, I3, একটা Output pin Y। 2. Fig 7.2-এর tree গঠন অনুসরণ করে তিনটা 2-to-1 MUX গেট (Digital-এ সরাসরি “Multiplexer” component আছে, বা এই লেসনের Fig 7.1 অনুযায়ী নিজে AND-OR-NOT দিয়ে বানান — দুইভাবেই একই ফলাফল পাওয়া উচিত, এই সমতা নিজে যাচাই করাই এই experiment-এর একটা অংশ)। 3. I0=0, I1=1, I2=1, I3=0 বসিয়ে (majority-এর মতো কোনো নির্দিষ্ট pattern নয়, শুধু চারটা ভিন্ন মান) S1S0-এর চারটা combination (00, 01, 10, 11) একে একে বসান। 4. প্রতিটায় Y-র মান লিখে রাখুন, এই লেসনের truth table-এর সাথে মেলান।

প্রত্যাশিত ফলাফল:

S1 S0 | Y
 0  0 | 0   (= I0)
 0  1 | 1   (= I1)
 1  0 | 1   (= I2)
 1  1 | 0   (= I3)
এটা কী প্রমাণ করে

AND-OR গঠন থেকে হাতে বের করা truth table বাস্তব simulated circuit-এর আচরণের সাথে হুবহু মেলে — কোনো hidden edge case নেই।

EXPERIMENT

Python দিয়ে brute-force যাচাই — MUX truth table বনাম boolean equation

Python 3· ১০ মিনিট
from itertools import product

def mux4(i0, i1, i2, i3, s1, s0):
    """Decoder + AND-OR গঠন হুবহু কোডে।"""
    d0 = (not s1) and (not s0)
    d1 = (not s1) and s0
    d2 = s1 and (not s0)
    d3 = s1 and s0
    return (i0 and d0) or (i1 and d1) or (i2 and d2) or (i3 and d3)

def mux4_direct(data, s1, s0):
    """সরাসরি 'ঠিকানা' ব্যবহার করে — এটাই আসল hardware আচরণ।"""
    addr = (s1 <\< 1) | s0
    return data[addr]

# সব সম্ভাব্য data + select combination-এ দুই পদ্ধতি মেলে কি না
mismatches = 0
for i0, i1, i2, i3, s1, s0 in product([0, 1], repeat=6):
    a = mux4(i0, i1, i2, i3, s1, s0)
    b = mux4_direct([i0, i1, i2, i3], s1, s0)
    if bool(a) != bool(b):
        mismatches += 1

print(f"মোট combination পরীক্ষা করা হলো: {2**6}")
print(f"অমিল: {mismatches}")

প্রত্যাশিত output:

মোট combination পরীক্ষা করা হলো: 64
অমিল: 0

mux4 ফাংশনটা গেট-লেভেল equation, mux4_direct সরাসরি array indexing — দুটো ভিন্ন abstraction level থেকে লেখা, তবু ৬৪টা combination-এর প্রতিটায় মিলে যাচ্ছে। এটাই প্রমাণ করে যে “select লাইন একটা address” — এই মানসিক মডেলটা শুধু analogy নয়, গাণিতিকভাবে সমতুল্য।

এটা কী প্রমাণ করে

একটা MUX-এর equation (Y = Σ Iᵢ · minterm(select=i)) সব সম্ভাব্য select/data combination-এ সবসময় সঠিক আউটপুট দেয় — এটাই decoder+AND পদ্ধতির সাধারণীকৃত প্রমাণ, শুধু একটা 4-to-1 কেসের জন্য নয়।

নিজে বানান

BUILD IT

8-to-1 MUX (function generator হিসেবে) + একটা 3-to-8 priority encoder

Digital / Logisim schematic + Python verifier · ●●○○○
  1. দুইটা 4-to-1 MUX (Fig 7.2-এর tree প্যাটার্ন অনুসরণ করে) আর একটা final 2-to-1 MUX দিয়ে একটা 8-to-1 MUX বানান — মোট তিনটা select লাইন
  2. একটা নিজের পছন্দের 3-variable function বেছে নিন (parity function চেষ্টা করুন — 1 ঠিক তখনই যখন বিজোড় সংখ্যক input 1), তার truth table হাতে লিখুন
  3. সেই truth table-এর 8টা মান MUX-এর data input-এ হার্ডওয়্যার্ড করুন, তিনটা ভেরিয়েবল select লাইনে দিন
  4. সব ৮টা input combination যাচাই করুন — কোনো নতুন গেট ছাড়াই function সঠিক কি না দেখুন
  5. এবার একটা 4-to-2 priority encoder বানান (এই লেসনের truth table অনুযায়ী, I3 সর্বোচ্চ priority) — একাধিক input একসাথে সক্রিয় করে valid-বিট আর output কোড যাচাই করুন

Function generator অংশটা শেষ করলে দেখবেন — এই একই প্যাটার্ন দিয়ে আপনি যেকোনো ৩-variable function সেকেন্ডের মধ্যে বানাতে পারবেন, নতুন schematic না এঁকেই, শুধু data input বদলে। এটাই পরের লেসনের ALU-র output-selection MUX-এর ঠিক একই নীতি — সেখানে data input হবে বিভিন্ন sub-circuit-এর ফলাফল, function হবে না বরং কোন sub-circuit-এর ফলাফল ব্যবহার হবে তার নির্বাচন।

Priority encoder অংশে বিশেষভাবে লক্ষ্য করুন: I3=1 আর I1=1 একসাথে সক্রিয় করে দেখুন আউটপুট I3-এর কোড দেখাচ্ছে কি না — এটাই interrupt controller বাস্তবে যা করে তার একটা mini-simulation।

বাস্তব সিস্টেমে

MUX আর Decoder যেখানে প্রতিদিন কাজ করছে

Register file read port। একটা CPU-র ৩২টা general-purpose register থাকলে, একটা instruction-এর rs ফিল্ড (৫ বিট, যেহেতু 2⁵=32) সরাসরি একটা 32-to-1 MUX-এর select লাইনে যায় — সেই ৫ বিটই ঠিক করে কোন register-এর মান ALU-তে পাঠানো হবে। Level ৩-এর CPU datapath-এ এটাই register file-এর read port-এর সবচেয়ে সাধারণ implementation।

CPU-র pipeline-এ forwarding MUX। আধুনিক pipelined CPU-তে একই register বারবার ভিন্ন উৎস থেকে আসতে পারে (register file থেকে সরাসরি, বা আগের instruction-এর এখনো-write-না-হওয়া ফলাফল থেকে “forward” করে)। একটা MUX প্রতিটা সম্ভাব্য উৎসের মধ্যে সঠিকটা বেছে নেয় control logic-এর সিদ্ধান্ত অনুযায়ী — Level ৩-এর “forwarding ও stalling” অংশে এটা বিস্তারিত আসবে।

Memory chip-select / address decoding। ইতিমধ্যে দেখানো — CPU-র address bus decode করে ঠিক একটা RAM চিপ বা peripheral সক্রিয় করা।

7-segment display driver। একটা BCD-to-7-segment decoder (0-9 এই ৪-বিট বাইনারি কোড থেকে সাতটা LED segment-এর কোনগুলো জ্বলবে তা ঠিক করে) একটা বিশেষ decoder — one-hot নয়, বরং প্রতিটা input digit-এর জন্য একটা নির্দিষ্ট pattern of active segments। সাধারণ decoder-এর ধারণাই এখানে সাধারণীকৃত হয়েছে।

Video/graphics pipeline। পুরনো CRT/video controller circuit-এ pixel data বিভিন্ন source (background layer, sprite layer, overlay text) থেকে একটা MUX দিয়ে বাছাই হতো, প্রতি pixel clock-এ — আধুনিক GPU-র “blending” পাইপলাইনের এক ধরনের পূর্বপুরুষ।

Telephone/network switching। ঐতিহাসিকভাবে টেলিফোন এক্সচেঞ্জে একটা কলকে হাজার হাজার সম্ভাব্য লাইনের একটায় রাউট করার জন্য বড় crossbar switch ব্যবহার হতো — গঠনগতভাবে এটা একটা বিশাল MUX/DEMUX network, আজকের নেটওয়ার্ক switch-এও একই মৌলিক ধারণা (packet-কে সঠিক output port-এ রাউট করা) টিকে আছে, যদিও বাস্তবায়ন সম্পূর্ণ ভিন্ন (Level ৭ নেটওয়ার্কিং-এ)।

Bus arbitration। যখন একাধিক device একই shared bus ব্যবহার করতে চায় (যেমন পুরনো PCI bus, বা একাধিক CPU core একই memory bus-এ), একটা priority-encoder-জাতীয় arbiter সিদ্ধান্ত নেয় কে এখন bus নিয়ন্ত্রণ পাবে — ঠিক interrupt controller-এর মতোই যুক্তি, ভিন্ন প্রসঙ্গে প্রয়োগ।

FPGA LUT। ইতিমধ্যে আলোচিত — MUX + configurable data input = programmable logic-এর ভিত্তি।

Analog multiplexer — sensor array স্ক্যান করা। এই লেসনে আলোচিত সবই ডিজিটাল MUX (0/1 সিগন্যাল), কিন্তু একই নীতির একটা analog সংস্করণও আছে — analog MUX চিপ (যেমন 4051/4052 সিরিজ), যেখানে data input ধারাবাহিক ভোল্টেজ (0V থেকে 5V-এর মাঝে যেকোনো মান) বহন করতে পারে, digital 0/1 নয়। একটা মাইক্রোকন্ট্রোলারের হয়তো মাত্র একটা ADC (Analog-to-Digital Converter) পিন থাকে, কিন্তু সিস্টেমে আছে আটটা তাপমাত্রা সেন্সর — একটা analog MUX সেই আটটা সেন্সরকে পালাক্রমে সেই একটা ADC পিনের সাথে সংযুক্ত করে, প্রতি চক্রে একটা করে পড়ে। এখানে “select লাইন” (S₂S₁S₀) মাইক্রোকন্ট্রোলার নিজেই control করে, ঠিক এই লেসনের ডিজিটাল MUX-এর মতোই যুক্তিতে — শুধু যেটা রাউট হচ্ছে সেটা এখন একটা analog সিগন্যাল।

ALU-র operand selection — পরের লেসনের সরাসরি ভিত্তি। একটা CPU-র ALU সবসময় register file থেকে সরাসরি অপারেন্ড পায় না — মাঝেমধ্যে instruction-এর ভেতরে embedded একটা constant (immediate value) ব্যবহার করতে হয় (যেমন x = x + 5-এ 5)। একটা 2-to-1 MUX ALU-র দ্বিতীয় ইনপুটে বসে, control signal অনুযায়ী register থেকে আসা মান বা instruction-এর ভেতরের constant — এই দুইয়ের মধ্যে বেছে নেয়। এটা এমন সাধারণ একটা প্যাটার্ন যে প্রায় প্রতিটা বাস্তব CPU datapath-এ এটা থাকে। পরের লেসনে যখন আমরা সম্পূর্ণ ALU ডিজাইন করব, দেখবেন এই একই MUX-ভিত্তিক “নির্বাচন” নীতিটাই ALU-র আউটপুট সাইডে আরও বড় আকারে ফিরে আসছে — কোন sub-circuit (adder, logic unit, shifter) এর ফলাফল চূড়ান্ত আউটপুট হবে, সেটাও একটা MUX-ই ঠিক করবে।

যে ভুলগুলো সবাই করে

“MUX শুধু ডেটা 'পাস' করে, তাই এটা কোনো Boolean function তৈরি করে না — শুধু routing।”

একদিক থেকে এটা সত্যি (MUX নিজে কোনো নতুন গেট বানায় না), কিন্তু আরেকদিক থেকে সম্পূর্ণ ভুল। যেহেতু data input-এ যেকোনো fixed মান বসানো যায় (0, 1, বা এমনকি অন্য কোনো সিগন্যাল), আর select লাইন-ই function-এর ভেরিয়েবল, একটা MUX সত্যিকারের একটা Boolean function বাস্তবায়ন করে — শুধু ভিন্ন কৌশলে (lookup, গেট composition নয়)। এই লেসনের majority-function উদাহরণটা এর প্রমাণ — ওখানে কোনো majority-নির্দিষ্ট গেট নেই, শুধু একটা generic MUX + wiring, তবু ফলাফল একটা সত্যিকারের নতুন function।

“Decoder আর demultiplexer সম্পূর্ণ ভিন্ন দুইটা circuit।”

গেট-লেভেলে এরা একই সার্কিট — পার্থক্য শুধু ব্যাখ্যায়। DEMUX-এ একটা “In” পিনকে ডেটা হিসেবে দেখা হয়; decoder-এ সেই একই পিনকে “Enable” হিসেবে দেখে সবসময় 1-এ বেঁধে রাখা হয়। বাস্তব চিপ (যেমন 74138) datasheet-এ প্রায়ই দুইটা নামেই বিক্রি হয়, কারণ ব্যবহারকারীর প্রয়োগই ঠিক করে এটাকে কোন নামে ডাকা হবে।

“Priority encoder-এ 'don't care' (X) মানে সেই বিটগুলো circuit-এ বাস্তবিকই অনুপস্থিত, বা 'random' মান।”

X শুধু বোঝায় যে truth table-এ সেই ইনপুট combination-এর জন্য আউটপুট সংজ্ঞায়িত করার প্রয়োজন নেই, কারণ উচ্চতর priority-র কোনো ইনপুট ইতিমধ্যে ফলাফল ঠিক করে দিয়েছে। বাস্তব circuit-এ সেই ইনপুট পিনগুলো নিশ্চিতভাবেই কোনো না কোনো বাস্তব ভোল্টেজ বহন করছে (0 বা 1) — শুধু সেই মান আউটপুট নির্ধারণে কোনো ভূমিকা রাখছে না, তাই hardware designer সেই কেসগুলো don’t-care হিসেবে চিহ্নিত করে সরলীকরণের (K-map-এর মতো) সুযোগ নেন।

“Decoder-এর 'সক্রিয়' আউটপুট সবসময় 1 হবে, active-high — এটাই একমাত্র কনভেনশন।”

এই লেসনের শেখার-উপযোগী truth table-গুলো active-high ধরে (সরলতার জন্য), কিন্তু বাস্তব চিপে এটা সার্বজনীন নিয়ম নয়। 74138-এর মতো বহু-বহু-ব্যবহৃত বাস্তব decoder chip-এর আউটপুট active-low — নির্বাচিত আউটপুট 0 হয়, বাকি সব 1। কারণ বাস্তব মেমরি/peripheral চিপের chip-select পিনও প্রায়ই active-low, তাই সরাসরি সংযোগ দেওয়া যায়। Datasheet না পড়ে “decoder মানেই output 1 হবে” ধরে নিলে বাস্তব সার্কিটে ভুল wiring হবে — সবসময় নির্দিষ্ট চিপের datasheet-এ pin-এর convention (pin নামের বার, বা L/N suffix) যাচাই করা জরুরি।

বুঝেছেন কি না দেখুন

1

একটা 8-to-1 MUX-এ S₂S₁S₀ = A, B, C (এই ক্রমে) আর data input I0=1, I1=0, I2=1, I3=1, I4=0, I5=0, I6=1, I7=0। A=1, B=1, C=0-এ আউটপুট কী?

প্রয়োগ

Select লাইনের বাইনারি মান বের করি: S₂S₁S₀ = ABC = 110₂ = 6।

MUX ঠিকানা 6-এ যায়, মানে I6 আউটপুটে যাবে।

I6 = 1।

উত্তর: Y = 1।

2

কেন একটা n-to-1 MUX-এ ঠিক \log_2 n টা select লাইন লাগে — কম বা বেশি নয় কেন, তা যুক্তি দিয়ে ব্যাখ্যা করুন।

যুক্তি

Select লাইনের কাজ হলো n টা data input-এর মধ্যে ঠিক একটাকে অনন্যভাবে চিহ্নিত করা — প্রতিটা Iᵢ-এর একটা আলাদা “ঠিকানা” থাকতে হবে। k টা বাইনারি select লাইন দিয়ে সর্বোচ্চ 2^k টা ভিন্ন combination বানানো যায়। তাই অন্তত n টা ভিন্ন ঠিকানা পেতে হলে 2^k \ge n, অর্থাৎ k \ge \log_2 n লাগবেই — এটাই নিচের সীমা, কম হলে একাধিক input একই ঠিকানা শেয়ার করবে, MUX অস্পষ্ট (ambiguous) হয়ে যাবে।

উপরের দিকে, k টা লাইন থেকে ঠিক \log_2 n নেওয়াই যথেষ্ট আর সর্বোচ্চ কার্যকর — একটা বাড়তি select লাইন যোগ করলে ঠিকানা স্পেস দ্বিগুণ হয়ে যায় (2^(k+1)), কিন্তু নতুন data input লাগবে না — শুধু অপচয়। তাই ঠিক \log_2 n টাই optimal এবং প্রয়োজনীয়।

3

একটা 2-variable function f(A,B) = A (মানে f সবসময় শুধু A-এর মান কপি করে, B-এর উপর নির্ভর করে না) — একটা 4-to-1 MUX দিয়ে এটা বাস্তবায়নের জন্য data input I0, I1, I2, I3 কী হওয়া উচিত, যদি S1=A, S0=B?

ডিজাইন

প্রথমে f-এর সম্পূর্ণ truth table লিখি (যদিও f শুধু A-এর উপর নির্ভর করে, formal truth table তৈরিতে B-ও রাখতে হবে):

ABf=A
000
010
101
111

Select S1S0 = AB হলে ঠিকানা ক্রম সেই একই — I0 ↔ AB=00, I1 ↔ AB=01, I2 ↔ AB=10, I3 ↔ AB=11।

তাই:

I0=0,I1=0,I2=1,I3=1I_0=0,\quad I_1=0,\quad I_2=1,\quad I_3=1

লক্ষ্য করুন I0=I1 (দুটোই 0, কারণ A=0 উভয় ক্ষেত্রে) আর I2=I3 (দুটোই 1, কারণ A=1 উভয় ক্ষেত্রে) — এই প্যাটার্নটা বলে দেয় B আসলে অপ্রাসঙ্গিক, শুধু A গুরুত্বপূর্ণ। এটাই একটা ব্যবহারিক অন্তর্দৃষ্টি: MUX data input-এ যদি pair-wise সমান মান দেখা যায় (I0=I1, I2=I3), তার মানে সেই select লাইন (S0) আসলে বাদ দিয়ে একটা ছোট, সস্তা MUX দিয়েই কাজ চলত (এইখানে একটা সাধারণ 2-to-1 MUX, select শুধু A)। এটা এক অর্থে MUX-লেভেলে K-map simplification-এরই প্রতিফলন।

4

একটা 4-to-2 priority encoder-এ (এই লেসনের truth table অনুযায়ী, I3 সর্বোচ্চ priority) — যদি I3=0, I2=0, I1=1, I0=1 (দুইটা input একসাথে সক্রিয়), আউটপুট A1A0 এবং V কী হবে?

প্রয়োগ

সর্বোচ্চ priority থেকে চেক করা শুরু করি: I3=0 (নিষ্ক্রিয়), I2=0 (নিষ্ক্রিয়), I1=1 — এটাই সর্বোচ্চ-priority সক্রিয় ইনপুট।

Truth table-এর তৃতীয় সারি অনুযায়ী (I3=0,I2=0,I1=1, I0 don’t-care): A1A0 = 01, V=1।

উত্তর: A1A0 = 01, V = 1। I0=1 হওয়া সত্ত্বেও এটা আউটপুটে কোনো প্রভাব ফেলল না — কারণ I1-এর priority বেশি। এটাই ঠিক interrupt controller-এর আচরণ: একই সাথে দুইটা device interrupt পাঠালে, শুধু বেশি-priority-র device-টা এখনই সার্ভিস পাবে, অন্যটা pending থাকবে।

5

এই লেসনে দেখানো হয়েছে decoder-এর প্রতিটা আউটপুট আসলে একটা minterm। Boolean algebra লেসনের সাথে যুক্ত করে ব্যাখ্যা করুন — একটা n-input decoder দিয়ে যেকোনো n-variable function কীভাবে বানানো সম্ভব (এই লেসনের MUX-based universal function generator-এর বিকল্প হিসেবে)?

যুক্তি

Boolean algebra-য় শেখা মূল সত্য: যেকোনো function-কে তার sum-of-minterms (SOP/DNF) আকারে লেখা যায় — যে সব input combination-এ function 1, সেই combination-গুলোর minterm-এর OR।

একটা n-input decoder এমনভাবে বানানো যে তার 2ⁿ আউটপুট হলো ঠিক n ভেরিয়েবলের 2ⁿ টা সম্ভাব্য minterm, সবগুলো একসাথে, প্যারালালে উপলব্ধ। তাই যেকোনো function বানাতে:

  1. Function-টাকে minterm-এর OR হিসেবে লিখুন (truth table থেকে সরাসরি — যেখানে f=1 সেই row-গুলোর minterm নিন)
  2. Decoder-এর সেই নির্দিষ্ট minterm-আউটপুটগুলো একটা OR গেটে সংযুক্ত করুন
  3. যেসব minterm-এ f=0, সেগুলোর decoder-আউটপুট OR-এ যুক্ত করবেন না

এটা MUX-based পদ্ধতির থেকে ভিন্ন — MUX পদ্ধতিতে কোনো বাড়তি OR গেট লাগে না (data input-ই সরাসরি উত্তর বহন করে), decoder পদ্ধতিতে একটা বাড়তি external OR গেট লাগে (function-নির্দিষ্ট, প্রতিটা ভিন্ন function-এর জন্য ভিন্ন wiring of the OR গেট)। কিন্তু মূলনীতি একই: একটা fixed, function-independent structure (MUX বা decoder) + কিছু বাইরের wiring/data দিয়ে যেকোনো Boolean function বাস্তবায়ন করা যায় — এটাই combinational logic design-এর একটা কেন্দ্রীয়, পুনরাবৃত্ত থিম।

6

একটা টয় CPU-র ১৬-বিট address space-কে ১৬টা সমান 4KB খণ্ডে ভাগ করে একটা 4-to-16 decoder দিয়ে chip-select বানানো হয়েছে (এই লেসনের দ্বিতীয় উদাহরণের মতোই)। Address 0xC205-এ কোন device (0-15 নম্বরের মধ্যে) সক্রিয় হবে, আর সেই device-এর নিজস্ব রেজিস্টার ম্যাপে অফসেট কত?

প্রয়োগ

শর্টকাট ব্যবহার করি — 0x1000 (= 4096 = 2^12) দিয়ে ভাগ করি।

0xC205÷0x1000=12 (ভাগফল), ভাগশেষ =0x2050xC205 \div 0x1000 = 12 \text{ (ভাগফল)}, \text{ ভাগশেষ } = 0x205

যাচাই করার জন্য বাইনারিতেও দেখি: 0xC205 = 1100 0010 0000 0101₂। উপরের ৪ বিট A15..A12 = 1100₂ = 12। ভাগফলের সাথে মিলে গেল।

উত্তর: device নম্বর 12 সক্রিয় হবে (decoder-এর D12 আউটপুট one-hot হয়ে উঠবে), আর সেই device-এর নিজস্ব রেজিস্টার ম্যাপে অফসেট 0x205 (বাকি ১২ বিট, A11..A0)।

এই প্রশ্নটা দেখায় কেন বাস্তব embedded system-এর memory map datasheet-এ প্রায়ই সরাসরি হেক্স রেঞ্জ (0xC000–0xCFFF: device 12) লেখা থাকে, বাইনারি ভাঙচুর ছাড়াই — কারণ 4KB-সারিবদ্ধ (aligned) memory map-এ ভাগ-ভাগশেষই decoder-এর আসল সিদ্ধান্তের সরাসরি reflection।

এরপর কী

এরপর কী — যখন এই ব্লকগুলো একসাথে একটা প্রোগ্রামযোগ্য যন্ত্র হয়ে ওঠে

আজকে আমরা শিখেছি কীভাবে একটা MUX বহু সিগন্যাল থেকে একটা বেছে নেয়, আর কীভাবে সেই একই ধারণা একটা universal function generator-এ পরিণত হয়। পরের লেসনে আমরা এই ঠিক এই কৌশলটাই ব্যবহার করব একটা সম্পূর্ণ নতুন ধরনের সার্কিট বানাতে — ALU (Arithmetic Logic Unit)।

ধারণাটা সহজ কিন্তু গভীর: যদি আমাদের কাছে ইতিমধ্যে থাকে একটা adder/subtractor (আগের লেসন থেকে), একটা bitwise logic circuit (AND/OR/XOR), আর একটা shifter — তাহলে এই সবগুলোর ফলাফল একসাথে, প্যারালালে গণনা করে একটা বড় output-selection MUX দিয়ে ঠিক একটা বেছে নিলেই, আমরা পাই এমন একটা সার্কিট যেটা একটা control code দিয়ে ভিন্ন ভিন্ন সময়ে ভিন্ন ভিন্ন কাজ করতে পারে — এই পুরো curriculum-এ এটাই প্রথমবার, ছোট পরিসরে হলেও, “programmable” হার্ডওয়্যারের স্বাদ।

আরও পড়ুন

  • Digital Design, Chapter 6 — Combinational Logic Design — M. Morris Mano, Michael D. Ciletti · MUX, decoder, encoder-এর প্রামাণ্য textbook আলোচনা
  • SN74LS138 3-Line to 8-Line Decoder/Demultiplexer — Datasheet — Texas Instruments · বাস্তব chip-এর enable logic ও cascading — এই লেসনের decoder অংশের ভিত্তি
  • Digital — a free digital logic designer and circuit simulator — Helmut Neemann · এই লেসনের Experiment/Build অংশের জন্য সুপারিশকৃত টুল