Subtractor আর Comparator — একই Adder-এর দ্বিতীয় জীবন

আগে এটা বুঝি

computer-representation/signed-integers লেসনে আমরা প্রমাণ করেছিলাম:

$a - b = a + (\sim b + 1)$

আর একটা এক-লাইনের circuit-diagram দিয়ে ইঙ্গিত দিয়েছিলাম — একটা XOR gate দিয়ে b-কে conditionally invert করে, একটা control সংকেত দিয়ে carry-in-এ 1 বসিয়ে দিলে, একই adder যোগ আর বিয়োগ দুটোই করে ফেলে। সেই লেসনে বলা হয়েছিল: “এই সরলীকরণ Level 2-এ পুরো circuit হিসেবে বানাব।”

আজ সেই প্রতিশ্রুতি পূরণের দিন।

আর শুধু বিয়োগ না — আগের লেসনের full-adder চেইন পুনর্ব্যবহার করে আমরা comparator বানাব (A \< B, A = B, A > B), আর দেখব CPU-র status register-এর zero/carry/overflow flag ঠিক কোন circuit থেকে আসে — যেটা computer-representation/integer-overflow লেসনে “এই hardware mechanism Level 2-তে দেখব” বলে প্রতিশ্রুতি দেওয়া হয়েছিল।

এই লেসনের মূল বার্তা: নতুন কোনো arithmetic hardware লাগবে না। শুধু আগের লেসনের adder-এর চারপাশে কিছু XOR আর তারের পুনর্বিন্যাস — আর একটা সম্পূর্ণ ALU-এর arithmetic অংশ তৈরি।

মূল ধারণা

Adder/Subtractor combined circuit

শুরু করি একদম মূল সমীকরণ থেকে। n-bit two’s complement-এ:

$A - B = A + \overline{B} + 1$

তিনটা জিনিস দরকার:

প্রতিটা Bᵢ-কে invert করার একটা উপায় — conditionally, কারণ addition mode-এ invert করা চলবে না
adder chain-এর সবচেয়ে প্রথম (bit0) full-adder-এর Cin-এ +1 বসানোর একটা উপায়
দুইটাই একটা মাত্র control সিগন্যাল দিয়ে চালানো

Conditional invert — XOR-এর দ্বিতীয় ব্যবহার

X ⊕ 0 = X আর X ⊕ 1 = ~X — একটা XOR gate নিজেই একটা “controllable inverter”। প্রতিটা Bᵢ-র সাথে একটা control সিগন্যাল (sub) XOR করে দিলে:

sub = 0 → Bᵢ ⊕ 0 = Bᵢ (অপরিবর্তিত)
sub = 1 → Bᵢ ⊕ 1 = ~Bᵢ (invert)

আর সেই একই sub সিগন্যাল bit0-এর Cin-এও লাগিয়ে দিলে: sub=0 → Cin=0 (সাধারণ addition), sub=1 → Cin=1 (সেই +1, যা ~B+1 সম্পূর্ণ করে)।

  sub ──┬──────────┬──────────┬──────────┬───────────────┐
        │           │           │           │                │
        ▼B3         ▼B2         ▼B1         ▼B0                │
      ┌───┐       ┌───┐       ┌───┐       ┌───┐               │
      │XOR│       │XOR│       │XOR│       │XOR│               │
      └─┬─┘       └─┬─┘       └─┬─┘       └─┬─┘               │
        │B3'         │B2'         │B1'         │B0'               │
        ▼             ▼             ▼             ▼               │
      ┌────┐ C3     ┌────┐ C2     ┌────┐ C1     ┌────┐  Cin ◄─────┘
Cout◄─┤ FA3│◄───────┤ FA2│◄───────┤ FA1│◄───────┤ FA0│
      └─┬┬─┘        └─┬┬─┘        └─┬┬─┘        └─┬┬─┘
       A3│            A2│            A1│            A0│
         ▼              ▼              ▼              ▼
         S3             S2             S1             S0

৪-bit combined adder/subtractor — একটাই control সিগন্যাল (sub) দুই জায়গায় ব্যবহার হচ্ছে।

প্রতিটা FAᵢ ঠিক আগের লেসনের full-adder — কোনো পরিবর্তন নেই। পার্থক্য শুধু: B input-এর সামনে একটা XOR gate-এর সারি, আর Cin-টা এখন hardwired 0 না — sub সিগন্যাল দিয়ে চালিত।

হাতে-কলমে যাচাই — `sub = 1`-এ `5 - 3`

A = 0101 (৫), B = 0011 (৩), sub = 1।

প্রথমে B' = B ⊕ sub (প্রতিটা bit 1 দিয়ে XOR, অর্থাৎ invert): B' = ~0011 = 1100।

এখন A + B' + Cin(=1) — ঠিক আগের লেসনের full-adder chain দিয়ে:

bit	Aᵢ	Bᵢ’	Cin	Sum	Cout
0	1	0	1	0	1
1	0	0	1	1	0
2	1	1	0	0	1
3	0	1	1	0	1

Sum bits (bit3→bit0): 0010 = 2। আর 5 - 3 = 2 ✓। চূড়ান্ত Cout = 1 — এর অর্থ একটু পরেই আসছে (comparator অংশে)।

Equality comparator — সবচেয়ে সরল তুলনা

A = B কি না জানতে subtractor লাগবেই এমন না। প্রতিটা bit জোড়া মিলছে কি না সরাসরি চেক করা যায়: Aᵢ = Bᵢ ঠিক তখনই যখন Aᵢ আর Bᵢ-এর XNOR (~(Aᵢ ⊕ Bᵢ)) 1। সব bit-এ মিললেই পুরো সংখ্যা সমান — একটা AND দিয়ে সব XNOR মিলিয়ে দিন।

$EQ = \prod_{i=0}^{n-1} \overline{A_i \oplus B_i}$

A0,B0 ──►[XNOR]──┐
A1,B1 ──►[XNOR]──┤
                  ├──►[AND4]──► EQ  (1 iff A == B)
A2,B2 ──►[XNOR]──┤
A3,B3 ──►[XNOR]──┘

৪-bit equality comparator — প্রতিটা bit জোড়ায় XNOR, তারপর একটা বড় AND।

২-bit উদাহরণে যাচাই: A=10, B=10 → XNOR(1,1)=1, XNOR(0,0)=1 → AND=1 → EQ=1 ✓। A=10, B=11 → XNOR(1,1)=1, XNOR(0,1)=0 → AND=0 → EQ=0 ✓ (শেষ bit-এ অমিল)।

Magnitude comparator — subtractor-এর পুনর্ব্যবহার

A \< B, A = B, A > B জানতে এবার সত্যিই subtractor কাজে লাগে — D = A - B কম্পিউট করে তার carry-out আর sign bit পড়লেই যথেষ্ট, কোনো নতুন circuit ছাড়াই।

Unsigned নিয়ম — carry-out সরাসরি বলে দেয়

আগের হাতে-কলমে করা 5 - 3 উদাহরণে final Cout = 1 পেয়েছিলাম। আরেকটা উদাহরণ করি, উল্টো দিকে — 3 - 5 (unsigned-এ 3 \< 5, তাই borrow হওয়ার কথা):

A=0011, B=0101, sub=1। B' = ~0101 = 1010।

bit	Aᵢ	Bᵢ’	Cin	Sum	Cout
0	1	0	1	0	1
1	1	1	1	1	1
2	0	0	1	1	0
3	0	1	0	1	0

Sum = 1110 = 14, final Cout = 0।

যাচাই: 3 - 5 = -2, আর -2 \bmod 16 = 14 ✓ (mod 2ⁿ reduction, ঠিক আগের লেসনের wraparound)। আর এবার Cout = 0।

প্যাটার্ন স্পষ্ট:

	`5 - 3` (`5 ≥ 3`)	`3 - 5` (`3 \< 5`)
final Cout	1	0
ব্যাখ্যা	কোনো borrow লাগেনি	borrow লেগেছে

$\text{Cout} = 1 \iff \text{কোনো borrow নেই} \iff A \ge B \text{ (unsigned)}$

এটাই carry flag-এর ভিত্তি (পরের সেকশনে বিস্তারিত)।

Signed নিয়ম — sign bit একা যথেষ্ট না

স্বাভাবিক অনুমান: D = A - B-এর sign bit (Dₙ₋₁) দেখলেই A \< B (signed) বোঝা যাবে — D ঋণাত্মক মানে A \< B। এটা প্রায়ই সত্যি, কিন্তু সবসময় না — যখন D নিজেই representable range ছাড়িয়ে যায় (signed overflow), sign bit বিভ্রান্তিকর হয়ে যায়। উদাহরণ দিয়ে দেখাব ঠিক পরের সেকশনে, overflow flag আলোচনার পরপরই — কারণ সঠিক নিয়মের জন্য overflow flag-ও লাগবে।

ভেতরে কী ঘটছে

ALU status flag — এবার সরাসরি circuit থেকে

computer-representation/integer-overflow লেসনে বলা হয়েছিল compiler-এর __builtin_add_overflow “hardware-এর carry/overflow flag সরাসরি পড়ে”। এখানে আমরা সেই flag-গুলো কোথা থেকে আসে সেটা circuit আকারে দেখব। চারটা classic flag — x86-এর নামকরণ অনুসরণ করছি (ZF, CF, SF, OF), কারণ এগুলোই সবচেয়ে প্রচলিত।

Zero flag (ZF)

সহজ — sum-এর সব bit 0 কি না। একটা NOR (বা সব bit OR করে, তারপর invert):

$ZF = \overline{S_{n-1} + S_{n-2} + \cdots + S_0}$

Subtractor-এর সাথে মিলিয়ে: ZF = 1 ঠিক তখনই যখন A - B = 0, অর্থাৎ A = B। (লক্ষ্য করুন — এটাও equality comparator-এরই আরেকটা রূপ, subtractor-এর ফলাফল থেকে “বিনামূল্যে” পাওয়া, কিন্তু আগের সেকশনের direct XNOR-tree-এর চেয়ে ধীর, কারণ এটা পুরো subtraction শেষ হওয়া পর্যন্ত অপেক্ষা করে।)

Carry flag (CF)

আগের সেকশনেই derive করা হয়েছে — subtractor-এর final Cout।

$CF_{\text{(এই adder-এর convention)}} = \text{Cout}_{n-1}$

CF = 1 মানে “কোনো borrow লাগেনি”, A \ge B (unsigned)।

সাবধান — architecture-ভেদে polarity উল্টো

এই লেসনে আমরা Cout সরাসরি “no borrow” অর্থে ব্যবহার করছি — এটা ARM-এর convention (ARM-এ SUBS-এর পর C=1 মানে borrow হয়নি, ঠিক আমাদের circuit-এর raw output)। x86 এর উল্টো সংজ্ঞা ব্যবহার করে — x86-এ CF=1 মানে borrow হয়েছে (x86_CF = ~Cout)। একই hardware সত্য, শুধু কোন polarity-কে “carry flag” নাম দেওয়া হয়েছে তার convention আলাদা। এটা ভুলে গেলে ARM ↔ x86 assembly পোর্ট করার সময় borrow logic উল্টে যাওয়ার bug হয় — ঠিক যেমন signed-integers লেসনে char signed/unsigned platform-ভেদে বদলানোর কারণে bug হতো।

Overflow flag (OF) — সবচেয়ে সূক্ষ্ম, সবচেয়ে গুরুত্বপূর্ণ

এইটাই সেই hardware mechanism যেটার প্রতিশ্রুতি ছিল। এটা detect করে signed overflow — যখন গাণিতিক সত্যিকারের ফলাফল representable range-এ আঁটে না।

$OF = C_{n-1} \oplus C_n$

অর্থাৎ: সবচেয়ে গুরুত্বপূর্ণ bit-এ ঢোকা carry (Cₙ₋₁, MSB-position-এর full-adder-এর Cin) XOR সবচেয়ে গুরুত্বপূর্ণ bit থেকে বের হওয়া carry (Cₙ, যেটাই চূড়ান্ত Cout)।

কেন এটা কাজ করে — স্বজ্ঞা: MSB-এর ওজন two’s complement-এ ঋণাত্মক (-2^(n-1), signed-integers লেসন মনে করুন), বাকি সব bit-এর ওজন ধনাত্মক। একটা “স্বাভাবিক” carry (Cₙ₋₁ থেকে Cₙ পর্যন্ত অপরিবর্তিত থাকা, দুটোই 0 অথবা দুটোই 1) মানে সেই carry hardware সঠিকভাবে সামলে নিয়েছে। কিন্তু যদি Cₙ₋₁ ≠ Cₙ হয়, তার মানে MSB position-এ একটা carry “ঢুকেছে কিন্তু বের হয়নি” (বা উল্টো) — sign bit ভুল মান পেয়ে গেছে, প্রকৃত গাণিতিক ফলাফলের চেয়ে ভিন্ন চিহ্নে।

গুরুত্বপূর্ণ — একই সূত্র addition আর subtraction দুটোতেই: যেহেতু combined circuit-এ subtraction আসলে ভেতরে addition-ই (A + ~B + 1), এই OF সূত্র কোনো পরিবর্তন ছাড়াই দুই ক্ষেত্রেই কাজ করে — subtraction-এর জন্য আলাদা কোনো overflow-detection circuit লাগে না।

যাচাই ১ — addition overflow। 4-bit signed, A=5(0101), B=3(0011), sub=0 (addition)। 5+3=8, কিন্তু signed ৪-bit range -8–7 — 8 আঁটে না।

  0101
+ 0011
------
bit0: 1+1=0, carry1
bit1: 0+1+1=0, carry1
bit2: 1+0+1=0, carry1
bit3: 0+0+1=1, carry_out0

Cₙ₋₁ (bit3-এ ঢোকা carry, bit2 থেকে) =1। Cₙ (চূড়ান্ত Cout) =0। OF = 1 ⊕ 0 = 1 — overflow সঠিকভাবে ধরা পড়েছে। Sum =1000, signed পড়লে -8 — সম্পূর্ণ ভুল (আসল উত্তর +8 হওয়ার কথা, চিহ্নই উল্টে গেছে)।

যাচাই ২ — subtraction overflow। A=-8(1000), B=1(0001), sub=1। -8-1=-9, range-এর বাইরে (-8-এর চেয়ে ছোট)।

B' = ~0001 = 1110, Cin=1:

bit0: A=0,B'=0,Cin=1 → sum=1, carry=0
bit1: A=0,B'=1,Cin=0 → sum=1, carry=0
bit2: A=0,B'=1,Cin=0 → sum=1, carry=0
bit3: A=1,B'=1,Cin=0 → sum=0, carry_out=1

Cₙ₋₁ (bit3-এ ঢোকা, bit2 থেকে) =0। Cₙ (final Cout) =1। OF = 0 ⊕ 1 = 1 — overflow সঠিকভাবে ধরা পড়েছে এখানেও। Sum =0111 (+7), সম্পূর্ণ ভুল sign (আসল উত্তর -9, negative)।

এবার signed comparison-এর সঠিক নিয়ম

দ্বিতীয় উদাহরণটাই দেখায় কেন শুধু sign bit যথেষ্ট না: D = 0111, sign bit =0 (positive-এর মতো দেখাচ্ছে!), অথচ প্রকৃত উত্তর -9, ঋণাত্মক। sign bit মিথ্যা বলছে, কারণ overflow ঘটেছে।

সঠিক নিয়ম — sign bit-কে overflow flag দিয়ে “correct” করে নেওয়া:

$A \lt B \text{ (signed)} \iff SF \oplus OF = 1$

আমাদের উদাহরণে: SF=0, OF=1 → SF⊕OF=1 → A \lt B — সঠিক (-8 \lt 1)! Overflow ঘটেছিল বলেই raw sign bit উল্টে গিয়েছিল, আর OF দিয়ে XOR করে সেটা ঠিক করে দিলাম।

Flag	Circuit	কী বোঝায়
ZF	সব sum bit-এর NOR	`A = B`
CF	subtractor-এর final Cout	`A \ge B` (unsigned)
SF	sum-এর MSB (`Sₙ₋₁`)	raw sign — একা অবিশ্বস্ত
OF	`Cₙ₋₁ ⊕ Cₙ`	signed overflow ঘটেছে কি না
SF ⊕ OF	—	`A \lt B` (signed), সঠিক, overflow-corrected

চারটা flag আর তাদের ব্যবহার — একনজরে।

একটা subtract circuit → চারটা flag → দুই ধরনের তুলনা

A, B, sub=1combined circuit-এর input
B' = B ⊕ sub, Cin = subXOR array + carry-in নিয়ন্ত্রণ
A + B' + Cinপুরনো full-adder chain, অপরিবর্তিত
Sum bits, Cₙ₋₁, Cₙraw circuit output
ZF, CF, SF, OFসরাসরি ফাংশন এই output-গুলোর
unsigned: CF | signed: ZF, SF⊕OFএকই flag-set, দুই ভিন্ন পাঠ

উদাহরণ

সম্পূর্ণ ALU flag রেজিস্টার — একটা বাস্তব দৃশ্য

ধরুন একটা 4-bit CPU-তে CMP A, B instruction চালানো হলো (অনেক ISA-তে CMP আসলে একটা subtract, শুধু result বাদ দিয়ে flag রাখে)। A = 1000 (8 unsigned / -8 signed), B = 0001 (1 উভয় ক্ষেত্রেই)।

Subtractor চালিয়ে (এই লেসনের আগের হাতে-কলমে করা হিসাব থেকে): Sum = 0111, final Cout = 1, Cₙ₋₁ = 0।

Flag	মান	হিসাব
ZF	0	Sum ≠ 0
CF	1	final Cout = 1
SF	0	Sum-এর MSB = 0
OF	1	`Cₙ₋₁(0) ⊕ Cₙ(1) = 1`

Unsigned পাঠ: CF=1 → A \ge B → 8 \ge 1 ✓ সঠিক।

Signed পাঠ: SF⊕OF = 0⊕1 = 1 → A \lt B → -8 \lt 1 ✓ সঠিক।

একই bit pattern, একই circuit output, দুইটা flag-combination পড়ে দুইটা সম্পূর্ণ ভিন্ন কিন্তু দুইটাই সঠিক সিদ্ধান্ত — ঠিক computer-representation/signed-integers লেসনের কেন্দ্রীয় থিমের চূড়ান্ত রূপ: একটা bit pattern একটা equivalence class, “signed” বনাম “unsigned” শুধু কোন representative আর কোন flag পড়া হচ্ছে তার নিয়ম।

এই তথ্যের উপর ভিত্তি করেই compiler if (a \lt b) থেকে সঠিক জাম্প instruction বাছে — signed a, b-এর জন্য JL (SF≠OF-এ jump), unsigned-এর জন্য JB/JC (CF=1-এ jump)। দুইটা আলাদা instruction, কিন্তু একই CMP-এর ফলাফল থেকে, শুধু ভিন্ন flag পড়ে।

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

EXPERIMENT

Combined adder/subtractor + সব flag Python-এ simulate করুন

Python 3· ২০ মিনিট

# alu_flags.py
def full_adder(a, b, cin):
    p = a ^ b
    s = p ^ cin
    cout = (a & b) | (cin & p)
    return s, cout


def adder_subtractor(a_bits, b_bits, sub):
    """sub=0: A+B ।  sub=1: A-B (two's complement)।"""
    n = len(a_bits)
    b_prime = [b ^ sub for b in b_bits]
    sums, carries = [], [sub]          # Cin(bit0) = sub
    c = sub
    for i in range(n):
        s, c = full_adder(a_bits[i], b_prime[i], c)
        sums.append(s)
        carries.append(c)
    cn_minus_1 = carries[-2]           # MSB-তে ঢোকা carry
    cn = carries[-1]                   # MSB থেকে বের হওয়া carry (final Cout)
    zf = 1 if all(s == 0 for s in sums) else 0
    cf = cn
    sf = sums[-1]
    of = cn_minus_1 ^ cn
    return sums, dict(ZF=zf, CF=cf, SF=sf, OF=of)


def to_bits(n, width):
    return [(n >> i) & 1 for i in range(width)]

def from_bits(bits):
    return sum(b << i for i, b in enumerate(bits))

def to_signed(u, width):
    return u - (1 << width) if u >= (1 << (width - 1)) else u


WIDTH = 4
mismatches = 0
for a in range(2 ** WIDTH):
    for b in range(2 ** WIDTH):
        a_bits, b_bits = to_bits(a, WIDTH), to_bits(b, WIDTH)

        # ── subtraction ──
        sums, flags = adder_subtractor(a_bits, b_bits, sub=1)
        result_u = from_bits(sums)

        expected_u = (a - b) % (2 ** WIDTH)          # unsigned wraparound
        a_s, b_s = to_signed(a, WIDTH), to_signed(b, WIDTH)
        true_diff = a_s - b_s
        expected_overflow = not (-(2**(WIDTH-1)) <= true_diff <= 2**(WIDTH-1)-1)

        # ── unsigned তুলনা: CF দিয়ে ──
        cf_says_ge = (flags['CF'] == 1)
        actual_ge_u = (a >= b)

        # ── signed তুলনা: SF ⊕ OF দিয়ে ──
        lt_signed = flags['SF'] ^ flags['OF']
        actual_lt_s = (a_s \< b_s)

        ok = (result_u == expected_u and
              flags['OF'] == (1 if expected_overflow else 0) and
              cf_says_ge == actual_ge_u and
              lt_signed == (1 if actual_lt_s else 0) and
              flags['ZF'] == (1 if a == b else 0))

        if not ok:
            mismatches += 1
            print(f"  MISMATCH a={a} b={b}: flags={flags}")

print(f"width={WIDTH}: {2**WIDTH}×{2**WIDTH} = {(2**WIDTH)**2} case, mismatch={mismatches}")

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

width=4: 4×4... 16×16 = 256 case, mismatch=0

সবগুলো case মেলা মানে: একটা মাত্র circuit (adder_subtractor) — unsigned subtraction, unsigned comparison (CF), signed overflow detection (OF), আর signed comparison (SF⊕OF) — চারটা সম্পূর্ণ ভিন্ন প্রশ্নের সঠিক উত্তর একসাথে দিচ্ছে, বিনা কোনো বাড়তি arithmetic hardware ছাড়াই।

নিজে বাড়ান: WIDTH=8 করে চালান (256×256=65536 case, এখনো দ্রুত), আর equality_comparator(a_bits, b_bits) ফাংশন আলাদাভাবে লিখে দেখান সেটা ZF-এর সাথে সবসময় মেলে — কিন্তু কোনো subtraction না করেই।

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

একই circuit function যোগ, বিয়োগ, unsigned comparison, আর signed comparison — সব সঠিকভাবে করে, শুধু আলাদা flag পড়ে। ZF/CF/SF/OF সবগুলোই Python-এর নিজস্ব signed/unsigned arithmetic-এর সাথে exhaustively মেলে।

EXPERIMENT

আসল x86 flag দেখুন — inline assembly দিয়ে

Linux/macOS (x86-64), gcc· ১৫ মিনিট

// flags_check.c
#include <stdio.h>
#include <stdint.h>

int main(void) {
    int32_t a = -8, b = 1;
    unsigned char zf, cf, sf, of;

    __asm__ volatile (
        "cmpl %2, %3\n\t"
        "setz %0\n\t"      // ZF
        "setc %1\n\t"      // CF (x86 convention — মনে রাখুন, borrow হলে ১!)
        : "=r"(zf), "=r"(cf)
        : "r"(b), "r"(a)
        : "cc"
    );

    __asm__ volatile (
        "cmpl %2, %3\n\t"
        "sets %0\n\t"      // SF
        "seto %1\n\t"      // OF
        : "=r"(sf), "=r"(of)
        : "r"(b), "r"(a)
        : "cc"
    );

    printf("a=%d, b=%d (signed a \< b: %s)\n", a, b, (a \< b) ? "true" : "false");
    printf("ZF=%d  CF(x86, borrow দিলে ১)=%d  SF=%d  OF=%d\n", zf, cf, sf, of);
    printf("এই লেসনের convention-এ CF(no-borrow) = %d\n", !cf);
    return 0;
}

gcc -O0 -o flags_check flags_check.c
./flags_check

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

a=-8, b=1 (signed a \< b: true)
ZF=0  CF(x86, borrow দিলে ১)=0  SF=0  OF=1
এই লেসনের convention-এ CF(no-borrow) = 1

লক্ষ্য করুন — x86 CF=0 (কোনো borrow নেই, কারণ x86-এ cmp a, b আসলে a - b করে, আর -8 - 1 unsigned interpretation-এ a-কে বিশাল ধনাত্মক সংখ্যা হিসেবে পড়া হয় যা b-এর চেয়ে বড়, তাই কোনো borrow লাগেনি x86-এর হিসাবে) — এই লেসনের convention-এ সেটাই CF(no-borrow)=1, ঠিক আমাদের হাতে-কলমে করা হিসাবের সাথে মিলছে। আর SF=0, OF=1 হুবহু এই লেসনের “যাচাই ২” অংশের সাথে মিলে যাচ্ছে — এই লেসনের প্রতিটা হাতে করা হিসাব একটা real CPU-তে reproduce হচ্ছে।

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

এই লেসনের ZF/CF/SF/OF তাত্ত্বিক না — সত্যিকারের x86 CPU-তে ঠিক এই flag-গুলোই প্রতিটা CMP instruction-এর পর সেট হয়, আর আমাদের হাতে করা হিসাবের সাথে হুবহু মেলে।

নিজে বানান

BUILD IT

সম্পূর্ণ ৪-bit ALU (Add, Sub, Compare, Flags)

Python · ●●●○○

আগের লেসনের full_adder পুনর্ব্যবহার করে adder_subtractor(a, b, sub) লিখুন
সব চারটা flag (ZF, CF, SF, OF) বের করার ফাংশন যোগ করুন
compare_unsigned(a, b) আর compare_signed(a, b) — দুটোই ফেরত দিক '<', '==', বা '>'
একটা equality_comparator(a_bits, b_bits) আলাদাভাবে (subtractor ছাড়া) লিখুন, ZF-এর সাথে মিলিয়ে verify করুন
সব ১৬×১৬ input জোড়ায় exhaustively test করে Python-এর নিজস্ব <, ==, >-এর সাথে মিলান

"""
mini_alu.py — একই adder circuit থেকে সম্পূর্ণ arithmetic + comparison ALU
চালান: python mini_alu.py
"""
WIDTH = 4

def full_adder(a, b, cin):
    p = a ^ b
    return p ^ cin, (a & b) | (cin & p)

def to_bits(n, width=WIDTH):
    return [(n >> i) & 1 for i in range(width)]

def from_bits(bits):
    return sum(b << i for i, b in enumerate(bits))

def to_signed(u, width=WIDTH):
    return u - (1 << width) if u >= (1 << (width - 1)) else u


def adder_subtractor(a, b, sub):
    a_bits, b_bits = to_bits(a), to_bits(b)
    b_prime = [x ^ sub for x in b_bits]
    c = sub
    sums, cn_minus_1 = [], 0
    for i in range(WIDTH):
        s, c_new = full_adder(a_bits[i], b_prime[i], c)
        sums.append(s)
        if i == WIDTH - 1:
            cn_minus_1 = c
        c = c_new
    result = from_bits(sums)
    flags = dict(
        ZF=1 if result == 0 else 0,
        CF=c,                          # এই লেসনের convention: 1 = no-borrow / carry generated
        SF=sums[-1],
        OF=cn_minus_1 ^ c,
    )
    return result, flags


def equality_comparator(a, b):
    """subtractor ছাড়াই — সরাসরি XNOR + AND"""
    a_bits, b_bits = to_bits(a), to_bits(b)
    return 1 if all(x == y for x, y in zip(a_bits, b_bits)) else 0


def compare_unsigned(a, b):
    _, flags = adder_subtractor(a, b, sub=1)
    if flags['ZF']:
        return '=='
    return '>=' if flags['CF'] else '<'


def compare_signed(a, b):
    _, flags = adder_subtractor(a, b, sub=1)
    if flags['ZF']:
        return '=='
    lt = flags['SF'] ^ flags['OF']
    return '<' if lt else '>'


if __name__ == "__main__":
    mismatches = 0
    for a in range(2 ** WIDTH):
        for b in range(2 ** WIDTH):
            # add সঠিকতা
            add_result, _ = adder_subtractor(a, b, sub=0)
            if add_result != (a + b) % (2 ** WIDTH):
                print(f"ADD MISMATCH {a}+{b}"); mismatches += 1

            # unsigned comparison
            u_cmp = compare_unsigned(a, b)
            u_expected = '==' if a == b else ('>=' if a >= b else '<')
            if u_cmp != u_expected:
                print(f"UCMP MISMATCH {a} vs {b}: got {u_cmp}, want {u_expected}")
                mismatches += 1

            # signed comparison
            a_s, b_s = to_signed(a), to_signed(b)
            s_cmp = compare_signed(a, b)
            s_expected = '==' if a_s == b_s else ('\<' if a_s \< b_s else '>')
            if s_cmp != s_expected:
                print(f"SCMP MISMATCH {a_s} vs {b_s}: got {s_cmp}, want {s_expected}")
                mismatches += 1

            # equality comparator বনাম ZF
            eq = equality_comparator(a, b)
            _, flags = adder_subtractor(a, b, sub=1)
            if eq != flags['ZF']:
                print(f"EQ MISMATCH {a} vs {b}"); mismatches += 1

    print(f"\nমোট {2**WIDTH * 2**WIDTH} জোড়া, mismatch = {mismatches}")

    # ── কয়েকটা নির্দিষ্ট উদাহরণ ছাপা ──
    for a, b in [(5, 3), (3, 5), (8, 1), (0, 0)]:
        r, f = adder_subtractor(a, b, sub=1)
        print(f"{a:2d} - {b:2d} = {r:2d}   flags={f}   "
              f"unsigned:{compare_unsigned(a,b):>3}   signed:{compare_signed(a,b):>3}")

প্রত্যাশিত output (শেষ অংশ):

মোট 256 জোড়া, mismatch = 0

 5 -  3 =  2   flags={'ZF': 0, 'CF': 1, 'SF': 0, 'OF': 0}   unsigned: >=   signed:   >
 3 -  5 = 14   flags={'ZF': 0, 'CF': 0, 'SF': 1, 'OF': 0}   unsigned:  <   signed:   <
 8 -  1 =  7   flags={'ZF': 0, 'CF': 1, 'SF': 0, 'OF': 1}   unsigned: >=   signed:   <
 0 -  0 =  0   flags={'ZF': 1, 'CF': 1, 'SF': 0, 'OF': 0}   unsigned:  ==   signed:  ==

শেষের 8 - 1 case-টা লক্ষ্য করুন — unsigned: >= (৮ ≥ ১, সঠিক) কিন্তু signed: \< (-8 \< 1, সঠিক, OF=1 overflow-এর কারণে sign bit উল্টে গিয়েছিল) — এই লেসনের example section-এর হাতে করা হিসাবের সাথে হুবহু মেলে।

নিজে বাড়ান:

WIDTH=8 বা 16-এ scale করুন, আর CPython-এর নেটিভ \<, ==, >-এর সাথে ১০,০০০টা random pair দিয়ে fuzz-test করুন
একটা branch(condition, flags) ফাংশন লিখুন যা x86-এর মতো condition code (JL, JLE, JG, JGE, JB, JA, JE, JNE) simulate করে flag থেকে
min(a, b, signed=True/False) আর max(...) লিখুন শুধু এই compare ফাংশন দুটো ব্যবহার করে, কোনো নতুন logic ছাড়া
Overflow flag বাদ দিয়ে শুধু sign bit দিয়ে signed comparison করলে কোন কোন input-এ ভুল হয়, সেই সব case আলাদা করে list করুন — এটাই প্রমাণ করবে কেন OF বাদ দেওয়া যায় না

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

যেখানে এই circuit প্রতি সেকেন্ডে কোটিবার চলছে

x86-এর CMP instruction। আক্ষরিকভাবে একটা SUB, শুধু ফলাফল register-এ না লিখে flag-এ রেখে দেয়। if, while, for — compiler-জেনারেটেড প্রতিটা তুলনা শেষ পর্যন্ত CMP + Jcc-এ নামে।

ARM-এর CMP/SUBS। একই ধারণা, flag polarity ভিন্ন (এই লেসনে আলোচিত)। SUBS (S = “set flags”) ঠিক এই লেসনের adder-subtractor circuit, flag output সহ।

RISC-V-এর ভিন্ন দর্শন — flag রেজিস্টারই নেই। RISC-V ইচ্ছাকৃতভাবে কোনো condition-flag register রাখেনি — বদলে SLT/SLTU (set-less-than) instruction সরাসরি একটা register-এ 0/1 লেখে, তারপর BEQ/BNE/BLT সরাসরি দুইটা register তুলনা করে branch নেয়। ভেতরে এই একই comparator circuit চলে, কিন্তু flag স্টেট রাখা হয় না — কারণ flag register pipeline-এ একটা hidden dependency তৈরি করে (out-of-order execution-এর জন্য mাথাব্যথা), যেটা RISC-V ডিজাইনাররা এড়াতে চেয়েছেন।

Constant-time comparison — cryptography-তে। পাসওয়ার্ড hash বা HMAC verify করার সময় সাধারণ if (a == b) loop বিপজ্জনক — প্রথম অমিল bit-এই early-exit করে, আর সেই timing পার্থক্য দিয়ে আক্রমণকারী bit-by-bit পাসওয়ার্ড অনুমান করতে পারে (timing attack)। নিরাপদ তুলনা তাই ঠিক এই লেসনের equality comparator-এর দর্শন অনুসরণ করে — সব bit-ই সবসময় পরীক্ষা করা হয়, কোনো early exit ছাড়া (software-এ XOR করে সব byte-এর ফলাফল OR করে একবারে চেক করা)। Level 10-এ এটা বিস্তারিত আসবে।

Database index/B-tree key comparison। প্রতিটা B-tree node-এ key খুঁজতে যে comparison হয়, শেষ পর্যন্ত এই একই magnitude comparator circuit — string comparison হলেও ভেতরে byte-wise integer comparison।

Checksum/hash verification। TCP checksum, file hash যাচাই — “গণনা করা মান == প্রত্যাশিত মান” এই একই equality comparator প্যাটার্ন।

Branch prediction hardware। CPU speculative execution-এ condition flag-এর ফলাফল আগে থেকে অনুমান করে — Level 3-এ branch predictor আলোচনায় দেখবেন প্রেডিক্টর আসলে predict করছে এই লেসনের flag output-গুলোই (বিশেষত ZF, SF⊕OF) branch নেওয়া হবে কি না তার ভিত্তিতে।

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

“Subtractor বানাতে শুধু B-এর প্রতিটা bit XOR দিয়ে invert করলেই যথেষ্ট, carry-in বদলানোর দরকার নেই।”

এটা এই লেসনের সবচেয়ে সহজে-verify-করা ভুল।

5 - 3 করি শুধু B invert করে (~B), কিন্তু Cin=0 রেখে (ভুল পদ্ধতি): A=0101, ~B=1100, Cin=0।

  0101
+ 1100
------
  0001    (= 1, ভুল! সঠিক উত্তর 2)

ফলাফল 1, কিন্তু 5-3=2। সবসময় ঠিক এক কম — কারণ A+~B = A + (2^n-1-B) = (A-B-1) + 2^n, অর্থাৎ mod 2ⁿ-এ এটা A-B-1, A-B না। এটাই one’s complement subtraction-এর সমস্যা যা signed-integers লেসনে আলোচিত হয়েছিল — “off by one” সবসময়।

Cin=1 (carry-in-এ sub সংকেত বসিয়ে) সঠিক উত্তর 2 দেয় (এই লেসনের প্রথম হাতে-কলমে করা উদাহরণ)। সেই +1-টাই one’s-complement থেকে two’s-complement বানায় — একটা মাত্র তার সংযোগ ভুলে গেলে পুরো subtractor ভুল ফলাফল দেবে, প্রতিটা input-এ, নিয়মিতভাবে এক কম।

“একই bit pattern তুলনা করলে unsigned আর signed পাঠ থেকে সবসময় একই ফলাফল (< বা ≥) আসবে — শুধু 'লেবেল' আলাদা।”

এই লেসনের example section-এ সরাসরি বিপরীত প্রমাণ দেওয়া হয়েছে।

A = 1000, B = 0001 — এই একই bit pattern জোড়া নিন। Circuit একবারই চলে, flag একবারই বের হয় (CF=1, SF=0, OF=1)। কিন্তু:

Unsigned পাঠে (8 বনাম 1): CF=1 → A \ge B → 8 \ge 1 — true
Signed পাঠে (-8 বনাম 1): SF⊕OF=1 → A \lt B → -8 \lt 1 — true

দুইটাই “true” কিন্তু বিপরীত দিকে — একটা বলছে A বড় বা সমান, আরেকটা বলছে A ছোট। কোনটা “সঠিক” তা নির্ভর করে সেই bit pattern-কে আপনি কীভাবে interpret করছেন তার উপর — ঠিক signed-integers লেসনের কেন্দ্রীয় থিম আবার এখানে।

Practical বিপদ: যদি কোনো ভাষায় (C-তে common) একটা unsigned আর একটা signed ভ্যারিয়েবল ভুলবশত তুলনা করা হয় (implicit conversion-এর ফাঁদে), compiler নীরবে একটাকে অন্যটার টাইপে রূপান্তর করে — আর সেই মুহূর্তে ঠিক এই দুই flag-সেটের মধ্যে “ভুল” সেটটা পড়া হয়ে যেতে পারে। GCC/Clang-এর -Wsign-compare ফ্ল্যাগ ঠিক এই বিপদ সনাক্ত করে।

“Equality check-এর জন্যও subtractor-ই সবচেয়ে স্বাভাবিক পথ, যেহেতু A-B=0 iff A=B।”

গাণিতিকভাবে সত্যি, কিন্তু engineering-এ ভুল পছন্দ।

Subtractor দিয়ে equality চেক করলে — পুরো n-bit carry chain শেষ না হওয়া পর্যন্ত ZF নির্ভরযোগ্য না, তাই delay O(n) (আগের লেসনের ripple-carry বিশ্লেষণ প্রযোজ্য)।

সরাসরি XNOR+AND ব্যবহার করলে — প্রতিটা bit জোড়া স্বাধীনভাবে (সমান্তরালে) তুলনা হয়, কোনো bit অন্য bit-এর ফলাফলের জন্য অপেক্ষা করে না। Delay শুধু final AND-tree-এর গভীরতা, O(\log n)।

সংখ্যা দিয়ে: ৬৪-bit-এ subtractor-based equality-র worst-case delay ripple-carry-র মতোই ~১২৮ gate-delay হতে পারে (আগের লেসনের হিসাব), যেখানে XNOR+AND-tree-এর delay মাত্র \log_2(64) ≈ 6 স্তর।

নিয়ম: “একই hardware দিয়ে সব কাজ করা যায়” (এই লেসনের প্রধান থিম) আর “সবসময় সেই একই hardware ব্যবহার করা উচিত” — দুইটা আলাদা দাবি। Reuse তখনই ভালো যখন cost গ্রহণযোগ্য; equality-র মতো frequent, latency-sensitive অপারেশনে dedicated, সমান্তরাল circuit-ই সঠিক প্রকৌশল সিদ্ধান্ত।

“Carry flag (CF) সব architecture-এ একই polarity বহন করে — 'CF=1' সবসময় 'carry হয়েছে' বোঝায়।”

Addition-এ এটা সাধারণত সত্যি (সব architecture-এই CF=1 মানে “একটা carry উপচে পড়েছে”)। কিন্তু subtraction-এ convention architecture-ভেদে উল্টে যায় — এই লেসনে আগেই দেখানো হয়েছে:

ARM: SUBS-এর পর C=1 মানে কোনো borrow হয়নি (raw adder circuit-এর Cout সরাসরি)
x86: SUB/CMP-এর পর CF=1 মানে borrow হয়েছে (x86_CF = ~Cout)

এই পার্থক্যটা ঐতিহাসিক — বিভিন্ন CPU লাইনেজ ভিন্ন সময়ে ভিন্ন convention বেছে নিয়েছিল, আর সেটা আজও রয়ে গেছে backward compatibility-র কারণে। যদি কেউ hand-written assembly বা inline-asm ARM থেকে x86-এ (বা উল্টো) “সরাসরি অনুবাদ” করার চেষ্টা করে বিনা এই polarity-র কথা মাথায় না রেখে, borrow-নির্ভর প্রতিটা conditional branch উল্টো দিকে চলে যাবে — একটা নীরব, খুঁজে পেতে কষ্টকর bug।

নিয়ম: ISA manual পড়ার সময় সবসময় precisely চেক করুন flag-এর সংজ্ঞা কোন direction-এ — “carry” শব্দটা একা যথেষ্ট তথ্য দেয় না।

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

৪-bit combined adder/subtractor circuit-এ A=0110 (৬), B=0010 (২), sub=1। প্রতিটা bit-এর Sum আর Cout হাতে বের করে ফলাফল আর সব চারটা flag (ZF, CF, SF, OF) বের করুন।

প্রয়োগ

B' = ~0010 = 1101, Cin(bit0) = sub = 1।

bit	Aᵢ	Bᵢ’	Cin	Sum	Cout
0	0	1	1	0	1
1	1	0	1	0	1
2	1	1	1	1	1
3	0	1	1	0	1

Sum (bit3→bit0) = 0100 = 4। যাচাই: 6 - 2 = 4 ✓।

Flag:

ZF = 0 (sum ≠ 0)
CF = Cout₃ = 1 (কোনো borrow নেই — সঠিক, 6 \ge 2)
SF = Sum₃ = 0
OF = Cₙ₋₁ ⊕ Cₙ = Cout₂ ⊕ Cout₃ = 1 ⊕ 1 = 0 (কোনো overflow না — সঠিক, 6-2=4 ৪-bit signed range -8–7-এ আরামে আঁটে)

উভয় পাঠ: unsigned 6 \ge 2 (CF=1) ✓। signed SF⊕OF = 0⊕0=0 → A \ge B → 6 \ge 2 ✓। এখানে unsigned আর signed পাঠ একমত — কারণ কোনো overflow ঘটেনি, উভয় সংখ্যাই ছোট, positive range-এ। Q4 (নিচে) দেখাবে overflow ঘটলে এই একমত হওয়াটা ভেঙে যায়।

Equality comparator-এ XNOR ব্যবহার করা হয়, XOR না। কেন XOR দিয়ে সরাসরি এই কাজ করা যাবে না, আর যদি ভুলবশত XOR ব্যবহার করে সব bit-এর ফলাফল AND করা হয়, কী ভুল ফলাফল আসবে?

যুক্তি

XOR(Aᵢ, Bᵢ) = 1 ঠিক তখন যখন Aᵢ ≠ Bᵢ — অর্থাৎ XOR “অমিল” সনাক্ত করে, “মিল” না। আমরা চাই এমন একটা সংকেত যেটা 1 হবে যখন Aᵢ = Bᵢ (মিল) — সেটাই XOR-এর উল্টো, অর্থাৎ XNOR (~(Aᵢ ⊕ Bᵢ))।

যদি ভুলবশত XOR ব্যবহার করে সেই ফলাফলগুলো AND করা হয়:

EQ_wrong = ∏(Aᵢ ⊕ Bᵢ)

এটা 1 হবে ঠিক তখনই যখন প্রতিটা bit position-এ Aᵢ ≠ Bᵢ — অর্থাৎ A আর B-এর প্রতিটা bit বিপরীত (একে অপরের bitwise complement)। এটা প্রায় সবসময় 0 হবে (কারণ দুইটা random সংখ্যার সব bit-ই বিপরীত হওয়া বিরল), এমনকি A = B হলেও সবসময় 0 (কারণ A=B হলে প্রতিটা bit-এ Aᵢ=Bᵢ, তাই Aᵢ⊕Bᵢ=0 সব জায়গায়, আর AND of all-zero =0)।

তাই এই ভুল circuit-টা প্রায় সবসময় “not equal” বলবে, এমনকি যখন আসলে equal। XOR+AND মূলত detect করে “সম্পূর্ণ bitwise complement” (A = ~B), “equal” না — সম্পূর্ণ ভিন্ন, প্রায় অপ্রাসঙ্গিক একটা function।

সঠিক নিয়ম মনে রাখার সহজ উপায়: XNOR-ই “সমতা” gate — নামেই আছে “N” (NOT), আর NOT + XOR মিলে “না-ভিন্ন”, অর্থাৎ “একই”।

4-bit-এ A = 0111 (7), B = 1000 — unsigned পাঠে B=8, signed পাঠে B=-8। sub=1 দিয়ে A - B circuit চালিয়ে OF আর উভয় ধরনের comparison ফলাফল বের করুন।

প্রয়োগ

B' = ~1000 = 0111, Cin=1।

bit	Aᵢ	Bᵢ’	Cin	Sum	Cout
0	1	1	1	1	1
1	1	1	1	1	1
2	1	1	1	1	1
3	0	0	1	1	0

Sum = 1111 = 15 (unsigned পাঠে)। Cₙ₋₁ = Cout₂ = 1, Cₙ = Cout₃ = 0। OF = 1 ⊕ 0 = 1।

যাচাই — গাণিতিকভাবে কী হওয়ার কথা:

Unsigned: 7 - 8 = -1, কিন্তু unsigned world-এ ঋণাত্মক সম্ভব না — mod 16 reduce হয়ে 15। আমাদের সার্কিটও 15 দিয়েছে ✓। CF = Cout₃ = 0 → borrow হয়েছে → 7 \lt 8 (unsigned) ✓ সঠিক।

Signed: B = -8 (যেহেতু 1000 signed-এ -8)। A - B = 7 - (-8) = 15। কিন্তু ৪-bit signed range -8–7, 15 আঁটে না — overflow প্রত্যাশিত, আর OF=1 ঠিক সেটাই ধরেছে ✓।

SF = Sum₃ = 1 (raw sign negative-এর মতো দেখাচ্ছে)। কিন্তু OF=1 (overflow), তাই raw SF অবিশ্বস্ত। সঠিক নিয়ম: SF ⊕ OF = 1 ⊕ 1 = 0 → A \ge B (signed)। যাচাই: 7 \ge -8 — ✓ সঠিক, যদিও raw SF=1 (যেটা ভুলভাবে A \lt B বলত যদি আমরা শুধু SF পড়তাম)।

এই প্রশ্নটাই দেখায় কেন OF উপেক্ষা করা যায় না — যদি কেউ সরাসরি SF পড়ে সিদ্ধান্ত নিত (SF=1 মানে ঋণাত্মক, তাই A \lt B), সেটা ভুল উত্তর দিত (A \lt B বলত, যেখানে প্রকৃতপক্ষে A \ge B)। শুধু SF \oplus OF ব্যবহার করলেই সঠিক উত্তর আসে।

কেন signed comparison-এর নিয়ম SF \oplus OF — শুধু OF বাদ দিয়ে সবসময় SF পড়লে কোন ধরনের input-এ ভুল হবে সেটা describe করুন (নির্দিষ্ট সংখ্যা লাগবে না, শুধু কাঠামোগত ব্যাখ্যা)।

যুক্তি

SF (raw sign bit) নির্ভরযোগ্য শুধু তখনই যখন A - B-এর প্রকৃত গাণিতিক ফলাফল representable range-এর ভেতরে আঁটে — তখন OF = 0, আর SF \oplus 0 = SF, তাই raw sign bit-ই সরাসরি সঠিক উত্তর।

কিন্তু যখন A - B-এর প্রকৃত মান range ছাড়িয়ে যায় (OF=1), hardware সেই “সত্যিকারের” মান representable range-এ wrap করে ফেলে (mod 2ⁿ reduction, ঠিক unsigned-integers লেসনের wraparound-এর মতো, শুধু signed interpretation-এ)। এই wrap-এর ফলে result-এর sign bit উল্টে যায় প্রকৃত mathematical sign-এর তুলনায় — একটা truly-negative ফলাফল positive-এর মতো দেখাতে পারে (Q3-এর উদাহরণ), বা উল্টো।

তাই: যখনই OF=1, raw SF উল্টো তথ্য দিচ্ছে — সঠিক sign আসলে SF-এর বিপরীত। SF \oplus OF ঠিক এই “উল্টো হলে আবার উল্টাও” logic বাস্তবায়ন করে: OF=0 হলে SF অপরিবর্তিত থাকে (ইতিমধ্যে সঠিক), OF=1 হলে SF invert হয়ে যায় (ভুল sign সংশোধন হয়)।

কাঠামোগত সংক্ষেপ: OF=1 হওয়ার শর্তই হলো “দুইটা operand-এর sign এমন combination যেখানে ফলাফলের true sign representation-এর বাইরে চলে যায়” — ঠিক সেই ক্ষেত্রেই raw sign bit বিভ্রান্তিকর, আর ঠিক সেই ক্ষেত্রেই OF “১” হয়ে সংশোধনটা trigger করে। দুইটা একসাথে ডিজাইন করা — একটা অন্যটাকে সংশোধন করার জন্যই।

আপনাকে একটা নতুন comparator instruction ডিজাইন করতে বলা হয়েছে যেটা তিনটা সম্ভাব্য ফলাফল (\lt, =, >) একটা মাত্র ২-bit output-এ এনকোড করবে, আর সেটা unsigned আর signed — দুই মোডেই কাজ করবে, একটা mode-select input দিয়ে। এই লেসনের কোন building block গুলো ব্যবহার করবেন, আর mode-select সিগন্যাল circuit-এর কোথায় কোথায় প্রভাব ফেলবে?

ডিজাইন

Building block:

এই লেসনের combined adder/subtractor (sub=1 স্থির, কারণ comparator সবসময় বিয়োগ করে) — A, B থেকে Sum, Cₙ₋₁, Cₙ বের করতে
ZF (সব sum bit-এর NOR) — = নির্ণয়ে
CF = Cₙ (unsigned mode-এ) — \ge/\lt নির্ণয়ে
SF = Sumₙ₋₁, OF = Cₙ₋₁ ⊕ Cₙ — signed mode-এ

Mode-select (is_signed) circuit-এর প্রভাব — শুধু একটা জায়গায়, চূড়ান্ত সিদ্ধান্তের multiplexer-এ:

গুরুত্বপূর্ণ পর্যবেক্ষণ — Sum, Cₙ₋₁, Cₙ গণনা করার আগে mode-select-এর কোনো ভূমিকা নেই। Adder/subtractor circuit নিজে signed/unsigned জানেই না (ঠিক আগের লেসনে দেখানো হয়েছিল — একই bit-level operation)। পার্থক্যটা শুধু flag পড়ার নিয়মে:

lt_signal = is_signed ? (SF ⊕ OF) : (NOT CF)
gt_signal = NOT ZF AND NOT lt_signal
eq_signal = ZF

output = eq_signal ? "="  :  (lt_signal ? "<" : ">")

তাই ডিজাইনে দরকার শুধু: একটা adder/subtractor (mode-নিরপেক্ষ), চারটা flag বের করার ছোট circuit (mode-নিরপেক্ষ), আর শেষে একটা ২-input multiplexer যেটা is_signed দিয়ে NOT CF বনাম SF⊕OF-এর মধ্যে বাছে।

মূল nকশা-সিদ্ধান্ত: ভারী arithmetic hardware (adder চেইন) সম্পূর্ণ mode-নিরপেক্ষ রাখা, mode-dependent সিদ্ধান্ত শুধু সবার শেষে, একটা ছোট, সস্তা multiplexer-এ ঠেলে দেওয়া — এটাই পুরো লেসনের কৌশলগত পাঠ পুনরাবৃত্ত: ব্যয়বহুল hardware শেয়ার করুন, সস্তা সিদ্ধান্ত শুধু আলাদা রাখুন।

এরপর কী

Level 2-এর প্রথম মাইলফলক

তিনটা লেসনে আমরা একটা সম্পূর্ণ arithmetic core বানিয়ে ফেললাম: minimization technique (gate cost কমানো), adder (যোগ), আর এখন subtractor+comparator (বিয়োগ, তুলনা, flag) — সব মিলিয়ে একটা mini-ALU-র arithmetic অংশ সম্পূর্ণ। এই তিনটা লেসনের প্রতিটা দাবিই — majority function, generate/propagate, OF সূত্র — Python দিয়ে exhaustively যাচাই করা হয়েছে, কোনো “বিশ্বাস করে নিন” নেই।

কিন্তু এখনো একটা বড় ফাঁক আছে: আমাদের circuit শুধু একটামাত্র operation করে যেকোনো মুহূর্তে (হয় add, নাহয় subtract) — কোনো memory নেই, কোনো “আগের ফলাফল মনে রাখা” নেই। একটা real CPU-কে বহু operation-এর মধ্যে বাছাই করতে হয় (multiplexer), আর মাঝে মাঝে মনে রাখতে হয় (flip-flop, register) — যেগুলো combinational circuit না, sequential circuit, কারণ তাদের output শুধু বর্তমান input না, অতীতের উপরও নির্ভর করে।

পরের লেসনগুলোতে (অন্য agent-দের লেখা) multiplexer, decoder, আর তারপর flip-flop/register দিয়ে ঠিক সেই “মনে রাখা” ক্ষমতা যোগ হবে — যেখান থেকে এই ALU একটা সম্পূর্ণ CPU datapath-এর অংশ হয়ে উঠবে।

Subtractor আর Comparator — একই Adder-এর দ্বিতীয় জীবন

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

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

আগে এটা বুঝি

মূল ধারণা

Adder/Subtractor combined circuit

Conditional invert — XOR-এর দ্বিতীয় ব্যবহার

হাতে-কলমে যাচাই — `sub = 1`-এ `5 - 3`

Equality comparator — সবচেয়ে সরল তুলনা

Magnitude comparator — subtractor-এর পুনর্ব্যবহার

Unsigned নিয়ম — carry-out সরাসরি বলে দেয়

Signed নিয়ম — sign bit একা যথেষ্ট না

ভেতরে কী ঘটছে

ALU status flag — এবার সরাসরি circuit থেকে

Zero flag (ZF)

Carry flag (CF)

Overflow flag (OF) — সবচেয়ে সূক্ষ্ম, সবচেয়ে গুরুত্বপূর্ণ

এবার signed comparison-এর সঠিক নিয়ম

উদাহরণ

সম্পূর্ণ ALU flag রেজিস্টার — একটা বাস্তব দৃশ্য

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

Combined adder/subtractor + সব flag Python-এ simulate করুন

আসল x86 flag দেখুন — inline assembly দিয়ে

নিজে বানান

সম্পূর্ণ ৪-bit ALU (Add, Sub, Compare, Flags)

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

যেখানে এই circuit প্রতি সেকেন্ডে কোটিবার চলছে

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

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

এরপর কী

Level 2-এর প্রথম মাইলফলক

আরও পড়ুন

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

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

◔আগে এটা বুঝিWhy this matters

◆মূল ধারণাCore concept

Adder/Subtractor combined circuit

Conditional invert — XOR-এর দ্বিতীয় ব্যবহার

হাতে-কলমে যাচাই — sub = 1-এ 5 - 3

Equality comparator — সবচেয়ে সরল তুলনা

Magnitude comparator — subtractor-এর পুনর্ব্যবহার

Unsigned নিয়ম — carry-out সরাসরি বলে দেয়

Signed নিয়ম — sign bit একা যথেষ্ট না

⚙ভেতরে কী ঘটছেUnder the hood

ALU status flag — এবার সরাসরি circuit থেকে

Zero flag (ZF)

Carry flag (CF)

Overflow flag (OF) — সবচেয়ে সূক্ষ্ম, সবচেয়ে গুরুত্বপূর্ণ

এবার signed comparison-এর সঠিক নিয়ম

▶উদাহরণExample

সম্পূর্ণ ALU flag রেজিস্টার — একটা বাস্তব দৃশ্য

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

Combined adder/subtractor + সব flag Python-এ simulate করুন

আসল x86 flag দেখুন — inline assembly দিয়ে

⚒নিজে বানানBuild it yourself

সম্পূর্ণ ৪-bit ALU (Add, Sub, Compare, Flags)

◉বাস্তব সিস্টেমেReal-world usage

যেখানে এই circuit প্রতি সেকেন্ডে কোটিবার চলছে

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

?বুঝেছেন কি না দেখুনCheck understanding

→এরপর কীNext step

Level 2-এর প্রথম মাইলফলক

আরও পড়ুন

আগে এটা বুঝি

মূল ধারণা

হাতে-কলমে যাচাই — `sub = 1`-এ `5 - 3`

ভেতরে কী ঘটছে

উদাহরণ

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

নিজে বানান

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

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

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

এরপর কী