গুণ — shift-add, Booth-এর algorithm আর দ্রুত multiplier

১ · কাগজে-কলমে binary গুণ — partial product আর 2n বিট

স্কুলে ২৩ × ১২ কীভাবে গুণ করতেন মনে করুন: ২৩-কে প্রথমে ২ দিয়ে গুণ (৪৬), তারপর ১ দিয়ে গুণ করে এক ঘর বাঁয়ে সরিয়ে লেখা (২৩০), শেষে দুটি সারি যোগ (২৭৬)। প্রতিটি সারি হলো একটি partial product — আংশিক গুণফল। যাকে গুণ করা হচ্ছে (২৩) তার নাম multiplicand, আর যা দিয়ে গুণ (১২) তার নাম multiplier.

Binary-তে একই পদ্ধতি আরও সহজ, কারণ প্রতিটি অঙ্ক শুধু ০ বা ১. কোনো সংখ্যাকে ১ দিয়ে গুণ করলে সংখ্যাটিই থাকে, ০ দিয়ে গুণ করলে ০. তাই প্রতিটি partial product হয় multiplicand নিজে, নয়তো শূন্য। Hardware-এর ভাষায়: partial product = multiplicand-এর প্রতিটি বিট AND multiplier-এর একটি বিট. কোনো গুণের নামতা মুখস্থ লাগে না — একটি AND gate-ই ১ বিট × ১ বিটের গুণ। এরপর partial product-গুলোকে যথাস্থানে সরিয়ে (left shift) যোগ করলেই গুণফল।

একটি উদাহরণ: 1011 (১১) × 1101 (১৩). Multiplier-এর বিটগুলো ডান থেকে পড়ুন — 1, 0, 1, 1:

          1 0 1 1      multiplicand  = 11
        x 1 1 0 1      multiplier    = 13
        ---------
          1 0 1 1      bit 0 = 1 -> 1011, shift 0
        0 0 0 0        bit 1 = 0 -> 0000, shift 1
      1 0 1 1          bit 2 = 1 -> 1011, shift 2
    1 0 1 1            bit 3 = 1 -> 1011, shift 3
    ---------------
    1 0 0 0 1 1 1 1    product = 128 + 8 + 4 + 2 + 1 = 143

১১ × ১৩ = ১৪৩ — মিলে গেল। লক্ষ করুন, দুটি ৪ বিটের সংখ্যার গুণফল ৮ বিটের। এটা কাকতালীয় নয়।

এর একটি সরাসরি ফল আছে। C-তে দুটি int32_t গুণ করলে ফলও int32_t — অর্থাৎ ৬৪ বিটের আসল গুণফলের শুধু নিচের ৩২ বিট থাকে। ওপরের অর্ধেক হারিয়ে গেলে তাকেই বলি গুণের overflow. Unsigned-এ এটি নিয়মমাফিক wrap-around, কিন্তু signed int-এ C ভাষায় এটি undefined behaviour — বিস্তারিত পর্ব ০৫-এ (Integer-এর বিট-রূপ)। অংশ ৬-এ দেখবেন, hardware ওপরের অর্ধেকও দিতে পারে, আর সেটি দিয়েই overflow ধরা যায়।

তাহলে n বিটের গুণে মোট কাজ: n²টি AND (প্রতিটি partial product-এ n টি বিট, n টি সারি) আর n টি সারির যোগ। এই যোগ দুইভাবে করা যায় — সময়ে ছড়িয়ে (একটি adder দিয়ে প্রতি clock-এ একটি সারি; অংশ ২), অথবা জায়গায় ছড়িয়ে (অনেক adder একসাথে; অংশ ৫)। প্রথমটি সস্তা কিন্তু ধীর, দ্বিতীয়টি দ্রুত কিন্তু বড়। আর signed সংখ্যার জন্য একটি তৃতীয় কৌশল লাগে (অংশ ৩–৪)।

২ · Shift-and-add multiplier — একটি adder, n টি ধাপ

সবচেয়ে সরল hardware ঠিক কাগজের পদ্ধতির নকল করে: প্রতি clock cycle-এ একটি partial product যোগ। Patterson আর Hennessy-র পাঠ্যবইয়ে (RISC-V সংস্করণ) এর দুটি ধাপে উন্নতি দেখানো হয়; বিশ্ববিদ্যালয় আর চাকরির পরীক্ষায় এই দুটিই সবচেয়ে বেশি আসে। এখানে ৩২ বিটের গুণ ধরে বর্ণনা, উদাহরণে ৪ বিট।

উন্নত সংস্করণের চালাকিটা বুঝুন। প্রথম সংস্করণে ৬৪ বিটের adder লাগত, অথচ প্রতি ধাপে আসলে মাত্র ৩২টি বিটে নতুন কিছু যোগ হয় — বাকি বিটগুলো হয় শূন্য, নয়তো আর বদলাবে না। তাই multiplicand-কে বাঁয়ে না সরিয়ে উল্টো product-কে ডানে সরানো হয়: আপেক্ষিক অবস্থান একই থাকে, কিন্তু adder সবসময় একই ৩২টি বিটে কাজ করে। আর product যত ডানে সরে, multiplier-এর ব্যবহার হয়ে যাওয়া বিট তত বেরিয়ে যায় — ঠিক সেই খালি জায়গাতেই multiplier রাখা যায়। একটি register বাঁচল। যোগের carry-out হারাতে না দিতে product register আসলে এক বিট বেশি (৩২ বিটে ৬৫) — shift-এর সময় সেই carry বিট বাঁ দিক দিয়ে ঢোকে।

এখন সেই চেনা পরীক্ষার টেবিল। Multiplicand = 0110 (৬), multiplier = 0011 (৩), উত্তর হওয়া উচিত ১৮ = 0001 0010. প্রতিটি iteration-এ দুটি কাজ: ধাপ ১ — Product[0] দেখে যোগ বা কিছু না; ধাপ ২ — ডানে shift.

iter  step                     Mcand   Product (hi │ lo)
 0    initial values           0110    0000 │ 0011

hi = 0000, lo = multiplier 0011
Prod[0] = 1  -> next step will add

iter  step                     Mcand   Product (hi │ lo)
 0    initial values           0110    0000 │ 0011
 1    1a: hi = hi + Mcand      0110    0110 │ 0011
      2 : shift right          0110    0011 │ 0001

0000 + 0110 = 0110, carry 0
after shift Prod[0] = 1

iter  step                     Mcand   Product (hi │ lo)
 1    2 : shift right          0110    0011 │ 0001
 2    1a: hi = hi + Mcand      0110   01001 │ 0001
      2 : shift right          0110    0100 │ 1000

0011 + 0110 = 1001 (5 bits: 0 1001)
the carry bit (0) enters from the left on shift

iter  step                     Mcand   Product (hi │ lo)
 2    2 : shift right          0110    0100 │ 1000
 3    1 : no add (Prod[0]=0)   0110    0100 │ 1000
      2 : shift right          0110    0010 │ 0100

iter  step                     Mcand   Product (hi │ lo)
 3    2 : shift right          0110    0010 │ 0100
 4    1 : no add (Prod[0]=0)   0110    0010 │ 0100
      2 : shift right          0110    0001 │ 0010

Product = 0001 0010 = 16 + 2 = 18   (6 x 3 = 18)

adds performed : 2   (multiplier 0011 has two 1s)
iterations     : 4   (always n, here n = 4)
multiplier bits: all shifted out of lo

প্রথম সংস্করণে প্রতি iteration-এ তিনটি আলাদা কাজ (যোগ, multiplicand shift, multiplier shift) ছিল; প্রতিটি এক cycle নিলে ৩২ বিটের গুণে প্রায় ১০০ cycle. উন্নত সংস্করণে যোগ আর shift একই cycle-এ করা যায় (adder-এর আউটপুট সরাসরি এক ঘর সরিয়ে লেখা), তাই প্রায় ৩২ cycle. দুটি নকশার টেবিল পরীক্ষায় আলাদা — প্রথমটিতে কলাম থাকে “Multiplier, Multiplicand, Product”, উন্নতটিতে “Multiplicand, Product”. প্রশ্নে কোন সংস্করণ চাওয়া হয়েছে তা দেখে নিন।

নিচের simulator একই উন্নত নকশা চালায় আর পুরো টেবিল ছাপে — ৪ বিটে প্রতিটি ধাপ, ৮ বিটে প্রতি iteration-এর এক লাইন। নিজের সংখ্যা বসিয়ে পরীক্ষার টেবিল মিলিয়ে নিতে পারবেন:

// Refined shift-and-add multiplier (Patterson-Hennessy style):
// 2n-bit Product register, multiplier starts in its right half.
// Each iteration: if Product[0] = 1, add Multiplicand to the left half
// (with a carry bit), then shift the whole (carry:Product) right by 1.
const bin = (x, n) => x.toString(2).padStart(n, "0");
function multiply(mcand, mplier, n, full) {
  let hi = 0, lo = mplier, adds = 0;           // Product = hi:lo
  console.log("iter  step                         mcand     product");
  const row = (it, st, h, hw) => console.log(`${String(it).padStart(3)}   ${st.padEnd(27)}` +
    `  ${bin(mcand, n)}  ${bin(h, hw).padStart(n + 1)} ${bin(lo, n)}`);
  row(0, "initial values", hi, n);
  for (let i = 1; i <= n; i++) {
    const bit = lo & 1;
    if (bit) { hi += mcand; adds++; }          // hi may become n+1 bits
    if (full) row(i, bit ? "1a: Prod[0]=1 -> hi+=Mcand" : "1 : Prod[0]=0 -> no add", hi, n + 1);
    lo = (lo >> 1) | ((hi & 1) << (n - 1));    // shift carry:hi:lo right
    hi >>= 1;
    row(full ? "" : i, full ? "2 : shift Product right" : (bit ? "add, shift" : "shift only"), hi, n);
  }
  const p = hi * (1 << n) + lo;
  console.log(`${bin(mcand, n)} x ${bin(mplier, n)} = ${bin(hi, n)} ${bin(lo, n)} = ${p}` +
    `  (check ${mcand} x ${mplier} = ${mcand * mplier}, adds = ${adds})\n`);
}
multiply(0b0110, 0b0011, 4, true);
multiply(0b11010110, 0b00001011, 8, false);
multiply(0b11111111, 0b11111111, 8, false);

iter  step                         mcand     product
  0   initial values               0110   0000 0011
  1   1a: Prod[0]=1 -> hi+=Mcand   0110  00110 0011
      2 : shift Product right      0110   0011 0001
  2   1a: Prod[0]=1 -> hi+=Mcand   0110  01001 0001
      2 : shift Product right      0110   0100 1000
  3   1 : Prod[0]=0 -> no add      0110  00100 1000
      2 : shift Product right      0110   0010 0100
  4   1 : Prod[0]=0 -> no add      0110  00010 0100
      2 : shift Product right      0110   0001 0010
0110 x 0011 = 0001 0010 = 18  (check 6 x 3 = 18, adds = 2)

iter  step                         mcand     product
  0   initial values               11010110   00000000 00001011
  1   add, shift                   11010110   01101011 00000101
  2   add, shift                   11010110   10100000 10000010
  3   shift only                   11010110   01010000 01000001
  4   add, shift                   11010110   10010011 00100000
  5   shift only                   11010110   01001001 10010000
  6   shift only                   11010110   00100100 11001000
  7   shift only                   11010110   00010010 01100100
  8   shift only                   11010110   00001001 00110010
11010110 x 00001011 = 00001001 00110010 = 2354  (check 214 x 11 = 2354, adds = 3)

iter  step                         mcand     product
  0   initial values               11111111   00000000 11111111
  1   add, shift                   11111111   01111111 11111111
  2   add, shift                   11111111   10111111 01111111
  3   add, shift                   11111111   11011111 00111111
  4   add, shift                   11111111   11101111 00011111
  5   add, shift                   11111111   11110111 00001111
  6   add, shift                   11111111   11111011 00000111
  7   add, shift                   11111111   11111101 00000011
  8   add, shift                   11111111   11111110 00000001
11111111 x 11111111 = 11111110 00000001 = 65025  (check 255 x 255 = 65025, adds = 8)

৩ · Signed গুণ — চিহ্ন আলাদা করা বনাম Booth-এর algorithm

Shift-and-add শুধু unsigned সংখ্যায় সরাসরি ঠিক উত্তর দেয়। ৪ বিটে 1101-কে unsigned ধরলে ১৩, কিন্তু two's complement-এ −৩. 0111 × 1101 unsigned হিসাবে ৭ × ১৩ = ৯১ দেবে, অথচ আমরা চাই ৭ × (−৩) = −২১. Signed গুণের দুটি প্রচলিত পথ আছে।

পথ ১ — চিহ্ন আলাদা করে ঠিক করা। দুটি সংখ্যাকে ধনাত্মক করুন (ঋণাত্মক হলে two's complement নিয়ে), unsigned গুণ করুন, আর মূল দুটি চিহ্ন আলাদা হলে ফলকে ঋণাত্মক করুন। Patterson–Hennessy-র বই প্রথমে এই পথই দেখায়: চিহ্ন XOR করে মনে রাখা, ৩১ বিটের magnitude-এ গুণ। সরল, কিন্তু শুরুতে আর শেষে বাড়তি negation-এর ধাপ লাগে। (আরেকটি সূক্ষ্ম পথও আছে: multiplier-এর MSB-র ওজন two's complement-এ −2ⁿ⁻¹, তাই শেষ iteration-এ যোগের বদলে বিয়োগ করলে আর shift-কে arithmetic shift করলে সরাসরি signed ফল আসে।)

পথ ২ — Booth-এর পদ্ধতি। ১৯৫১ সালে লন্ডনের Birkbeck College-এ কাজ করার সময় Andrew D. Booth একটি পদ্ধতি প্রকাশ করেন, যা two's complement সংখ্যাকে কোনো চিহ্ন-সংশোধন ছাড়াই সরাসরি গুণ করে। Booth-এর algorithm-এ চারটি register বা ঘর:

• M — multiplicand (n বিট, স্থির)
• A — accumulator, শুরুতে ০ (n বিট; গুণফলের ওপরের অর্ধেক এখানে জমে)
• Q — multiplier (n বিট; শেষে গুণফলের নিচের অর্ধেক)
• Q₋₁ — Q-এর ডানে একটি বাড়তি বিট, শুরুতে ০

প্রতিটি ধাপে (মোট n বার) জোড়া (Q₀, Q₋₁) দেখুন:

এবার পূর্ণ উদাহরণ: ৭ × (−৩), ৪ বিটে। M = 0111, Q = 1101 (−৩), A = 0000, Q₋₁ = 0. A − M করতে A-র সাথে −M = 1001 যোগ করা হয়। উত্তর হওয়া উচিত −২১ = ৮ বিটে 1110 1011.

step  Q0 Q-1  operation     A     Q     Q-1
 0             initial      0000  1101   0

-M = 1001  (two's complement of 0111)
first pair (Q0, Q-1) = (1, 0)

step  Q0 Q-1  operation     A     Q     Q-1
 1     1  0   A = A - M     1001  1101   0
              shift         1100  1110   1

0000 + 1001 = 1001
shift: A's sign bit 1 is copied in from the left

step  Q0 Q-1  operation     A     Q     Q-1
 1            shift         1100  1110   1
 2     0  1   A = A + M     0011  1110   1
              shift         0001  1111   0

1100 + 0111 = 1 0011 -> keep 4 bits 0011
(carry out of A is dropped)

step  Q0 Q-1  operation     A     Q     Q-1
 2            shift         0001  1111   0
 3     1  0   A = A - M     1010  1111   0
              shift         1101  0111   1

0001 + 1001 = 1010

step  Q0 Q-1  operation     A     Q     Q-1
 3            shift         1101  0111   1
 4     1  1   none          1101  0111   1
              shift         1110  1011   1

A:Q = 1110 1011
    = -128 + 64 + 32 + 8 + 2 + 1 = -21   (7 x -3 = -21)

check: invert 1110 1011 -> 0001 0100, +1 -> 0001 0101 = 21
add/sub operations: 3   (sub, add, sub)

এবার দুটিই ঋণাত্মক: (−৪) × (−৬). M = 1100, −M = 0100, Q = 1010. উত্তর +২৪ = 0001 1000. হাতে টেবিল করলে (simulator-এর আউটপুট থেকে হুবহু):

step  Q0Q-1  operation   A     Q     Q-1
 1     00    shift       0000  0101   0
 2     10    A = A - M   0100  0101   0     (0000 + 0100)
 2           shift       0010  0010   1
 3     01    A = A + M   1110  0010   1     (0010 + 1100)
 3           shift       1111  0001   0
 4     10    A = A - M   0011  0001   0     (1111 + 0100 = 1 0011)
 4           shift       0001  1000   1
result A:Q = 0001 1000 = +24

নিচের tracer একই নিয়মে যেকোনো উদাহরণ চালায়, প্রতিটি ফল সাধারণ গুণের সাথে মেলায়, আর কয়টি যোগ-বিয়োগ লাগল তা গোনে। শেষের দিকে ৮ বিটের দুটি multiplier ইচ্ছা করে বাছা: একটিতে ১-এর একটি লম্বা সারি, অন্যটিতে ০ আর ১ পালাক্রমে। আর একটি উদাহরণ ইচ্ছা করে একটি ফাঁদ দেখায় — খুঁজে বের করুন:

// Booth's algorithm (radix-2), n-bit two's complement M and Q.
// Look at (Q0, Q-1): 10 -> A = A - M, 01 -> A = A + M, 00/11 -> nothing;
// then arithmetic shift right of A:Q:Q-1. After n steps, A:Q = M x Q.
const bin = (x, n) => (x & ((1 << n) - 1)).toString(2).padStart(n, "0");
function booth(m, q, n, show) {
  const mask = (1 << n) - 1, M = m & mask;
  let A = 0, Q = q & mask, Q_1 = 0, ops = 0;
  if (show) console.log(`M = ${bin(M, n)} (${m}), Q = ${bin(Q, n)} (${q})\nstep Q0Q-1  operation   A    Q    Q-1`);
  for (let i = 1; i <= n; i++) {
    const pair = `${Q & 1}${Q_1}`;
    let op = "none     ";
    if (pair === "10") { A = (A - M) & mask; op = "A = A - M"; ops++; }
    if (pair === "01") { A = (A + M) & mask; op = "A = A + M"; ops++; }
    if (show && op[0] === "A") console.log(`  ${i}    ${pair}    ${op}  ${bin(A, n)} ${bin(Q, n)}  ${Q_1}`);
    Q_1 = Q & 1;                                    // arithmetic shift right A:Q:Q-1
    Q = ((Q >> 1) | ((A & 1) << (n - 1))) & mask;
    A = ((A >> 1) | (A & (1 << (n - 1)))) & mask;
    if (show) console.log(`  ${i}    ${op[0] === "A" ? "  " : pair}    shift      ${bin(A, n)} ${bin(Q, n)}  ${Q_1}`);
  }
  let r = A * (1 << n) + Q;
  if (A >> (n - 1)) r -= 2 ** (2 * n);              // read A:Q as signed 2n bits
  console.log(`${String(m).padStart(4)} x ${String(q).padStart(4)} = ${bin(A, n)} ${bin(Q, n)} = ${r}` +
    `  check ${m * q} ${r === m * q ? "OK" : "WRONG"}, add/sub ops = ${ops}${show ? "\n" : ""}`);
}
booth(7, -3, 4, true);
booth(-4, -6, 4, true);
for (const [m, q] of [[-8, 7], [5, -8], [-7, -7]]) booth(m, q, 4, false);
booth(25, 0b01111100, 8, false);   // one run of 1s: 0111 1100
booth(25, 0b01010101, 8, false);   // worst case: alternating bits
booth(-100, -128, 8, false);

M = 0111 (7), Q = 1101 (-3)
step Q0Q-1  operation   A    Q    Q-1
  1    10    A = A - M  1001 1101  0
  1          shift      1100 1110  1
  2    01    A = A + M  0011 1110  1
  2          shift      0001 1111  0
  3    10    A = A - M  1010 1111  0
  3          shift      1101 0111  1
  4    11    shift      1110 1011  1
   7 x   -3 = 1110 1011 = -21  check -21 OK, add/sub ops = 3

M = 1100 (-4), Q = 1010 (-6)
step Q0Q-1  operation   A    Q    Q-1
  1    00    shift      0000 0101  0
  2    10    A = A - M  0100 0101  0
  2          shift      0010 0010  1
  3    01    A = A + M  1110 0010  1
  3          shift      1111 0001  0
  4    10    A = A - M  0011 0001  0
  4          shift      0001 1000  1
  -4 x   -6 = 0001 1000 = 24  check 24 OK, add/sub ops = 3

  -8 x    7 = 0011 1000 = 56  check -56 WRONG, add/sub ops = 2
   5 x   -8 = 1101 1000 = -40  check -40 OK, add/sub ops = 1
  -7 x   -7 = 0011 0001 = 49  check 49 OK, add/sub ops = 3
  25 x  124 = 00001100 00011100 = 3100  check 3100 OK, add/sub ops = 2
  25 x   85 = 00001000 01001101 = 2125  check 2125 OK, add/sub ops = 8
-100 x -128 = 00110010 00000000 = 12800  check 12800 OK, add/sub ops = 1

৪ · Booth কেন কাজ করে — প্রমাণ, সবচেয়ে খারাপ ক্ষেত্র আর radix-4 Booth

মূল ভাবনা: ১-এর সারি = দুটি ঘাতের বিয়োগফল। 0111 1100 = ১২৪. এটিকে পাঁচটি ঘাতের যোগ (৬৪ + ৩২ + ১৬ + ৮ + ৪) হিসেবে না দেখে দেখুন ১২৮ − ৪ হিসেবে। তাহলে M × ১২৪ = M × ১২৮ − M × ৪: একটি যোগ আর একটি বিয়োগ, দুটি shift-এর জায়গায়। দোকানে ৯৯৮ টাকার জিনিস কিনতে আপনি যেমন হাজার টাকার নোট দিয়ে ২ টাকা ফেরত নেন — একটি বড় লেনদেন আর একটি ছোট ফেরত, অনেকগুলো খুচরো নোটের বদলে।

এই অঙ্কের সারিকে বলে Booth recoding, আর {−1, 0, +1} অঙ্কের সংখ্যারূপকে signed-digit রূপ। যেমন 1101 (−৩) → (q_i−1 − q_i) ডান থেকে: −1, +1, −1, 0 → বাঁ থেকে লিখলে 0 −1 +1 −1 = −৪ + ২ − ১ = −৩. ✓

সবচেয়ে খারাপ ক্ষেত্র। d_i শূন্য নয় ঠিক তখন, যখন পাশাপাশি দুটি বিট আলাদা। 0101 0101-এর মতো পালাক্রমের প্যাটার্নে প্রতিটি জোড়াই আলাদা, তাই n টি কাজ — সাধারণ shift-and-add-এর চেয়েও বেশি (সেখানে শুধু ১-এর সংখ্যা, ৪টি)। গড়ে এলোমেলো সংখ্যায় দুই পদ্ধতিতেই প্রায় n/2 কাজ। তাহলে লাভ কোথায়? প্রথমত, signed সংখ্যা সরাসরি — এটিই আসল লাভ। দ্বিতীয়ত, যে পুরোনো যন্ত্রে শূন্যের ওপর দিয়ে shift দ্রুত আর যোগ ধীর ছিল, সেখানে ১-এর লম্বা সারিতে সময় বাঁচত (Booth-এর মূল প্রেরণা নিয়ে ভাবনার প্রশ্ন ১ দেখুন)। কিন্তু প্রতি ধাপে এক cycle-এর synchronous hardware-এ radix-2 Booth cycle কমায় না — n টি ধাপ লাগেই। গতি বাড়ায় এর পরের রূপ।

Radix-4 (modified) Booth — partial product অর্ধেক

১৯৬১ সালে O. L. MacSorley-র প্রকাশিত একটি প্রবন্ধে বহুল-পরিচিত এই উন্নতিটি — radix-4 Booth recoding — আছে: পাশাপাশি দুটি Booth অঙ্ক জুড়ে একটি ৪-ভিত্তিক (radix-4) অঙ্ক বানানো। d_2j + 2d_2j+1 = (q_2j−1 − q_2j) + 2(q_2j − q_2j+1) = q_2j−1 + q_2j − 2q_2j+1. অর্থাৎ পরস্পর-ঢাকা (overlapping) তিন বিট (q_2j+1, q_2j, q_2j−1) দেখে একটি অঙ্ক, যার মান −২ থেকে +২:

প্রতিটি অঙ্কের ওজন 4^j, তাই n বিটের multiplier থেকে মাত্র n/2টি partial product. আর ±2M বা ±M বানানো খুব সস্তা — একটি shift (তার বদলে দেওয়া) আর বিট উল্টানো; “+১” আলাদা করে partial product-এর সারিতে ঢুকিয়ে দেওয়া হয়। ৩M-এর মতো কঠিন মান কখনো লাগে না — এটিই radix-4 Booth-এর চতুরতা।

উদাহরণ: M = ১৩, Q = 0111 (৭). Q-এর ডানে q₋₁ = 0 বসান: 0111|0. ত্রয়ী j = 0: (q₁ q₀ q₋₁) = 110 → −1. ত্রয়ী j = 1: (q₃ q₂ q₁) = 011 → +2. তাই Q = 2 · 4 − 1 = ৭ ✓, আর গুণফল = −১৩ + ২ · ১৩ · ৪ = −১৩ + ১০৪ = ৯১ = ১৩ × ৭ ✓. চারটির বদলে দুটি partial product. অংশ ৫-এর কোডে ৮ বিটের উদাহরণসহ এই recoding চালিয়ে দেখা যাবে।

৫ · দ্রুত multiplier — array, Wallace tree আর Dadda tree

Sequential multiplier ৩২ বিটে ৩২ cycle নেয় — আজকের CPU-র জন্য অনেক ধীর। দ্রুত করার উপায়: সব partial product একসাথে তৈরি করে (n²টি AND gate, সব একই gate delay-তে) যোগটাকেও সমান্তরাল করা।

Array multiplier. সবচেয়ে সরল উপায়: n − 1 সারি adder, প্রতিটি সারি আগের যোগফলের সাথে পরের partial product যোগ করে — গুণের কাগজের ছবিটিই silicon-এ আঁকা। মোট প্রায় n²টি AND আর প্রায় n(n − 1)টি full adder. সারিগুলো যদি ripple adder হয়, প্রতিটি সারি আগেরটির carry-র জন্য অপেক্ষা করে। চালাক নকশায় মাঝের সারিগুলোর carry নিচের সারিতে পাঠানো হয় (carry-save ধাঁচে), আর শুধু শেষ সারিতে carry ছড়ায়; তখন critical path মোটামুটি (n − 2) টি carry-save সারি + একটি n বিটের ripple adder ≈ 2n − 2 full adder delay — সরল মডেলে delay n-এর সমানুপাতিক, O(n). নকশাটি খুব নিয়মিত (একই cell বারবার, তার শুধু পাশের cell পর্যন্ত), কিন্তু ৬৪ বিটে ১২৬ full adder delay অনেক।

মূল চাবি: 3:2 compressor. পর্ব ১১-এ (Adder) দেখেছেন, একটি carry-save adder তিনটি সংখ্যা নিয়ে দুটি সংখ্যা দেয় — প্রতিটি ঘরে একটি full adder তিনটি বিট যোগ করে sum বিট এক সংখ্যায় আর carry বিট এক ঘর বাঁয়ে আরেক সংখ্যায় রাখে। ঘরগুলো একে অপরের সাথে জোড়া নয়, তাই width যা-ই হোক, delay একটি full adder-এর। এই ভূমিকায় full adder-কে বলে 3:2 compressor: সমান ওজনের ৩টি বিট ঢোকে, ২টি বেরোয়, মোট মান একই থাকে।

Wallace tree (C. S. Wallace, ১৯৬৪). সব partial product-কে তিনটি তিনটি করে দলে ভাগ করুন, প্রতিটি দলকে একটি carry-save adder দিয়ে দুটিতে নামান — সব দল একসাথে, এক full adder delay-তে। দলের বাইরে বাড়তি এক-দুটি সারি থাকলে সেগুলো পরের স্তরে চলে যায়। প্রতি স্তরে সারি প্রায় ২/৩ হয়, তাই স্তর লাগে log_3/2 n-এর কাছাকাছি — O(log n). দুটি সারি বাকি থাকলে একটি দ্রুত carry-propagate adder (পর্ব ১১-এর prefix adder-এর মতো) শেষ যোগটি করে।

৮টি সারির হিসাব: ৮ = ৩ + ৩ + ২ → (২ + ২) + ২ = ৬; ৬ = ৩ + ৩ → ৪; ৪ = ৩ + ১ → ২ + ১ = ৩; ৩ → ২. অর্থাৎ ৮ → ৬ → ৪ → ৩ → ২, চারটি স্তর। ১৬টি সারিতে ১৬ → ১১ → ৮ → ৬ → ৪ → ৩ → ২, ছয়টি স্তর। সূত্র: পরের স্তরের সারি = 2⌊r/3⌋ + (r mod 3).

Dadda tree (L. Dadda, ১৯৬৫). একই স্তর-সংখ্যা, কিন্তু উল্টো দিক থেকে ভাবা: শেষে ২টি সারি চাই; তার আগের স্তরে সর্বোচ্চ ৩, তার আগে ৪, তারপর ৬, ৯, ১৩, ১৯, ২৮, ৪২, ৬৩… (প্রতিটি = ⌊আগেরটি × ৩/২⌋)। প্রতি স্তরে শুধু ততটুকুই কমানো হয় যতটুকু পরের লক্ষ্যে পৌঁছাতে লাগে। ফলে full adder কিছুটা কম লাগে, যদিও শেষ adder সাধারণত একটু চওড়া হয়। ১৬ সারিতে Dadda-র লক্ষ্য-ক্রম ১৬ → ১৩ → ৯ → ৬ → ৪ → ৩ → ২ — Wallace-এর মতোই ৬ স্তর।

নিচের stepper-এ একটি পুরো ছোট গাছ: ১০১১ × ১১০১-এর চারটি partial product (অংশ ১-এর উদাহরণ)। Wallace-এর হিসাবে ৪ → ৩ → ২, দুটি স্তর। প্রথম স্তরের ভেতরটা কলাম ধরে দেখুন:

bit       7 6 5 4 3 2 1 0
P0        0 0 0 0 1 0 1 1    = 11   (bit 0 of 1101 = 1)
P1        0 0 0 0 0 0 0 0    =  0   (bit 1 = 0)
P2        0 0 1 0 1 1 0 0    = 44   (bit 2 = 1, shift 2)
P3        0 1 0 1 1 0 0 0    = 88   (bit 3 = 1, shift 3)
                       total = 143   rows = 4

bit       7 6 5 4 3 2 1 0
P0        0 0 0 0 1 0 1 1
P1        0 0 0 0 0 0 0 0
P2        0 0 1 0 1 1 0 0
          -----------------
column 3: 1+0+1 = 10 -> sum 0, carry 1 to bit 4
column 2: 0+0+1 = 01 -> sum 1
column 5: 0+0+1 = 01 -> sum 1
S  = 0 0 1 0 0 1 1 1   (XOR of each column)
C  = 0 0 0 1 0 0 0 0   (majority, shifted left 1)

bit       7 6 5 4 3 2 1 0
S         0 0 1 0 0 1 1 1    = 39
C         0 0 0 1 0 0 0 0    = 16
P3        0 1 0 1 1 0 0 0    = 88   (passed through)
                       total = 39 + 16 + 88 = 143   rows = 3
check: P0 + P1 + P2 = 11 + 0 + 44 = 55 = 39 + 16

bit       7 6 5 4 3 2 1 0
S         0 0 1 0 0 1 1 1
C         0 0 0 1 0 0 0 0
P3        0 1 0 1 1 0 0 0
          -----------------
column 4: 0+1+1 = 10 -> sum 0, carry 1 to bit 5
S2        0 1 1 0 1 1 1 1    = 111
C2        0 0 1 0 0 0 0 0    =  32
                       total = 143   rows = 2

S2        0 1 1 0 1 1 1 1    = 111
C2      + 0 0 1 0 0 0 0 0    =  32
          -----------------
product   1 0 0 0 1 1 1 1    = 143   (11 x 13)

delay = AND (partial products)
      + 2 full-adder levels
      + one fast adder

এবার কোডে: প্রথমে radix-4 Booth recoder (অংশ ৪), তারপর ৮, ১৬, ৩২ আর ৬৪টি সারির জন্য Wallace আর Dadda-র স্তর গোনা, আর array নকশার carry-save সারির সংখ্যার সাথে তুলনা:

// (1) Radix-4 (modified) Booth recoding: overlapping triplets
//     (q[2i+1], q[2i], q[2i-1]) -> digit d_i in {-2..+2}, Q = sum d_i * 4^i
// (2) Carry-save reduction levels (Wallace / Dadda) vs a simple array.
const DIGIT = { "000": 0, "001": 1, "010": 1, "011": 2, "100": -2, "101": -1, "110": -1, "111": 0 };
function recode(m, q, n) {
  const bits = ((q & ((1 << n) - 1)) * 2).toString(2).padStart(n + 1, "0"); // append q[-1] = 0
  let sum = 0, line = [];
  for (let i = 0; i < n / 2; i++) {
    const t = bits.slice(n - 2 * i - 2, n - 2 * i + 1), d = DIGIT[t];
    const pp = d * m * 4 ** i;                                   // partial product
    line.push(`${t}->${d >= 0 ? "+" : ""}${d}: ${d}*${m}*4^${i} = ${pp}`);
    sum += pp;
  }
  console.log(`Q = ${bits.slice(0, n)} (${q}), M = ${m}, ${n / 2} partial products:\n  ` +
    line.join("\n  ") + `\n  sum = ${sum}, M*Q = ${m * q} ${sum === m * q ? "OK" : "WRONG"}`);
}
recode(13, 0b0111, 4);
recode(13, 0b01101110, 8);
recode(-9, -29, 8);
function wallace(rows) {                  // every full group of 3 rows -> 2 rows
  const seq = [rows];
  while (rows > 2) { rows = 2 * Math.floor(rows / 3) + (rows % 3); seq.push(rows); }
  return seq;
}
function dadda(rows) {                    // targets 2, 3, 4, 6, 9, 13, 19, 28, 42, 63 ...
  const d = [2]; while (d[d.length - 1] < rows) d.push(Math.floor(d[d.length - 1] * 1.5));
  return [rows, ...d.filter(x => x < rows).reverse()];
}
console.log("\nrows  Wallace sequence                       levels  Dadda targets              array depth");
for (const n of [8, 16, 32, 64]) {
  const w = wallace(n), dd = dadda(n);
  console.log(`${String(n).padStart(4)}  ${w.join(">").padEnd(38)} ${String(w.length - 1).padStart(4)}` +
    `    ${dd.join(">").padEnd(26)} ${String(n - 2).padStart(3)} CSA rows`);
}

Q = 0111 (7), M = 13, 2 partial products:
  110->-1: -1*13*4^0 = -13
  011->+2: 2*13*4^1 = 104
  sum = 91, M*Q = 91 OK
Q = 01101110 (110), M = 13, 4 partial products:
  100->-2: -2*13*4^0 = -26
  111->+0: 0*13*4^1 = 0
  101->-1: -1*13*4^2 = -208
  011->+2: 2*13*4^3 = 1664
  sum = 1430, M*Q = 1430 OK
Q = 11100011 (-29), M = -9, 4 partial products:
  110->-1: -1*-9*4^0 = 9
  001->+1: 1*-9*4^1 = -36
  100->-2: -2*-9*4^2 = 288
  111->+0: 0*-9*4^3 = 0
  sum = 261, M*Q = 261 OK

rows  Wallace sequence                       levels  Dadda targets              array depth
   8  8>6>4>3>2                                 4    8>6>4>3>2                    6 CSA rows
  16  16>11>8>6>4>3>2                           6    16>13>9>6>4>3>2             14 CSA rows
  32  32>22>15>10>7>5>4>3>2                     8    32>28>19>13>9>6>4>3>2       30 CSA rows
  64  64>43>29>20>14>10>7>5>4>3>2              10    64>63>42>28>19>13>9>6>4>3>2  62 CSA rows

আধুনিক CPU কয়েক cycle-এ গুণ করে কীভাবে? Booth-recoded partial product, Wallace/Dadda ধাঁচের গাছ (প্রায়ই 4:2 compressor দিয়ে, যা দুটি 3:2 একসাথে জোড়া) আর শেষে একটি দ্রুত adder — সব মিলিয়ে একটি ৬৪ বিটের multiplier এক cycle-এ শেষ হয় না, তাই এর মাঝে pipeline register বসিয়ে কয়েকটি ধাপে ভাগ করা হয়। বিভিন্ন স্বাধীন পরিমাপ আর vendor-এর optimization manual অনুযায়ী অনেক আধুনিক x86-64 core-এ ৬৪ বিটের integer গুণের latency প্রায় ৩–৪ cycle, আর যেহেতু multiplier pipelined, প্রতি cycle-এ একটি নতুন গুণ শুরু করা যায় — অর্থাৎ throughput প্রতি cycle-এ প্রায় একটি গুণ। ARM আর RISC-V-এর বড় core-এও সংখ্যাগুলো মোটামুটি একই পরিসরে, তবে core ভেদে আলাদা — নির্দিষ্ট chip-এর জন্য তার manual দেখুন। তুলনায়, ছোট microcontroller-এ গুণ কখনো এক cycle, কখনো ৩২ cycle-এর sequential multiplier, কখনো hardware-ই নেই।

৬ · গুণের instruction — নিচের অর্ধেক, ওপরের অর্ধেক

৩২ বিট × ৩২ বিট = ৬৪ বিট, অথচ একটি register ৩২ বিটের। ISA এই সমস্যা বিভিন্নভাবে সমাধান করে। এই কোর্সের মূল ISA RISC-V-এ base RV32I-তে কোনো গুণের instruction নেই; গুণ-ভাগ আসে ঐচ্ছিক M extension থেকে (instruction-গুলোর বিস্তারিত পর্ব ২৬-এ)। গুণের চারটি instruction:

নিচের অর্ধেকের জন্য একটিই instruction কেন? কারণ two's complement-এ গুণফলের নিচের n বিট signed বা unsigned — যেকোনো ব্যাখ্যায় একই। দুটি ব্যাখ্যার পার্থক্য প্রতিটি সংখ্যায় 2ⁿ-এর গুণিতক (যেমন 1101 unsigned ১৩, signed −৩; পার্থক্য ১৬)। (a + k·2ⁿ)(b + l·2ⁿ) খুললে বাড়তি সব পদ 2ⁿ-এর গুণিতক, যা নিচের n বিটে কোনো প্রভাব ফেলে না। কিন্তু ওপরের অর্ধেক বদলে যায় — তাই সেখানে তিনটি আলাদা instruction. RV64-এ একই নিয়ম ৬৪ বিটে (১২৮ বিটের ফল), আর ৩২ বিটের ফলের জন্য বাড়তি mulw.

অন্য ISA-তে। x86-64-এ এক-operand-এর mul r/m64 (unsigned) আর imul r/m64 (signed) RAX-কে operand দিয়ে গুণ করে পুরো ১২৮ বিট ফল দেয় RDX:RAX জোড়ায় — RDX-এ ওপরের অর্ধেক; ৩২ বিটে EDX:EAX. ওপরের অর্ধেক অর্থবহ হলে (ফল নিচের অর্ধেকে ধরেনি) CF আর OF flag ১ হয়। দুই বা তিন operand-এর imul শুধু নিচের অর্ধেক দেয় — compiler সাধারণ a*b-তে এটিই ব্যবহার করে। ARM-এর AArch64-এ mul নিচের ৬৪ বিট, smulh/umulh ১২৮ বিটের ওপরের ৬৪ বিট, আর smull/umull দুটি ৩২ বিট থেকে পুরো ৬৪ বিট; ৩২ বিটের ARM-এ SMULL/UMULL দুটি register-এ (RdLo, RdHi) পুরো ফল লেখে।

RISC-V spec একটি কৌশলও বলে: একই গুণের দুই অর্ধেক লাগলে পরপর mulh[[s]u] rdh, rs1, rs2 আর mul rdl, rs1, rs2 লিখুন (একই ক্রমে source register, আর rdh যেন rs1 বা rs2 না হয়) — তাহলে microarchitecture চাইলে দুটিকে একটি গুণে জুড়ে (fuse) দিতে পারে। ISA সরল থাকে, দ্রুত hardware-ও বাদ পড়ে না।

ওপরের অর্ধেক কেন লাগে? তিনটি বড় কারণ:

• Overflow ধরা: unsigned গুণে overflow ঠিক তখনই, যখন mulhu ≠ 0. Signed গুণে overflow ঠিক তখনই, যখন mulh-এর ফল নিচের অর্ধেকের sign bit-এর sign extension (সব ০ বা সব ১) নয়।
• বড় সংখ্যার হিসাব (multi-precision): RSA বা elliptic-curve cryptography-তে ২০৪৮ বিটের মতো সংখ্যা ৬৪ বিটের টুকরোয় ভেঙে গুণ হয়; প্রতিটি টুকরো-গুণের দুই অর্ধেকই লাগে।
• Fixed-point আর ধ্রুবক দিয়ে ভাগ: Q31 গুণ আসলে ওপরের অর্ধেক থেকে (অংশ ৮)। আর compiler x / 10-কে (unsigned ৩২ বিটে) (x * 0xCCCCCCCD) >> 35-এ বদলায় — অর্থাৎ mulhu তারপর shift; ভাগের চেয়ে অনেক দ্রুত (পর্ব ২২-এ ভাগ কেন ধীর)।

নিচের C প্রোগ্রাম চারটি RISC-V instruction-এর ফল ৬৪ বিটের মাঝের হিসাব দিয়ে বানায় — signed গুণে overflow যাতে না হয় (৩২ বিটের সংখ্যা ৬৪ বিটে গুণ করলে কখনো overflow হয় না), আর ঋণাত্মক সংখ্যা shift না করে আগে unsigned-এ রূপান্তর। তারপর ওপরের অর্ধেক দিয়ে overflow ধরে gcc-র নিজস্ব __builtin_mul_overflow-এর সাথে মেলায়, আর শেষে strength reduction-এর একটি যাচাই (অংশ ৭):

#include <stdio.h>
#include <stdint.h>

/* RV32M-style results from one 64-bit product (no signed overflow, no UB) */
static uint32_t mul(int32_t a, int32_t b)    { return (uint32_t)((uint64_t)(uint32_t)a * (uint32_t)b); }
static uint32_t mulhu(int32_t a, int32_t b)  { return (uint32_t)(((uint64_t)(uint32_t)a * (uint32_t)b) >> 32); }
static uint32_t mulh(int32_t a, int32_t b)   { return (uint32_t)((uint64_t)((int64_t)a * b) >> 32); }
static uint32_t mulhsu(int32_t a, int32_t b) { return (uint32_t)((uint64_t)((int64_t)a * (int64_t)(uint32_t)b) >> 32); }

int main(void) {
    int32_t t[][2] = { {100000, 50000}, {-7, 3}, {2147483647, 2}, {-2, -3}, {65536, 65536} };
    printf("         a      b | mul      mulh     mulhu    mulhsu   | s-ovf u-ovf builtin\n");
    for (int i = 0; i < 5; i++) {
        int32_t a = t[i][0], b = t[i][1], r;
        uint32_t lo = mul(a, b), hi = mulh(a, b), hu = mulhu(a, b);
        uint32_t sign = (lo >> 31) ? 0xFFFFFFFFu : 0u;   /* sign-extension of low half */
        int ovf = __builtin_mul_overflow(a, b, &r);       /* gcc's own signed check */
        printf("%10d %6d | %08X %08X %08X %08X | %-5s %-5s %d\n", (int)a, (int)b,
               (unsigned)lo, (unsigned)hi, (unsigned)hu, (unsigned)mulhsu(a, b),
               hi != sign ? "yes" : "no", hu != 0 ? "yes" : "no", ovf);
    }
    unsigned bad = 0;                                    /* x*10 == (x<<3)+(x<<1) ? */
    for (uint32_t x = 0, k = 0; k < 2000000u; k++, x += 2147u)
        if (x * 10u != (x << 3) + (x << 1)) bad++;
    printf("x*10 vs (x<<3)+(x<<1): 2000000 values, mismatches %u\n", bad);
    return 0;
}

         a      b | mul      mulh     mulhu    mulhsu   | s-ovf u-ovf builtin
    100000  50000 | 2A05F200 00000001 00000001 00000001 | yes   yes   1
        -7      3 | FFFFFFEB FFFFFFFF 00000002 FFFFFFFF | no    yes   0
2147483647      2 | FFFFFFFE 00000000 00000000 00000000 | yes   no    1
        -2     -3 | 00000006 00000000 FFFFFFFB FFFFFFFE | no    yes   0
     65536  65536 | 00000000 00000001 00000001 00000001 | yes   yes   1
x*10 vs (x<<3)+(x<<1): 2000000 values, mismatches 0

৭ · ধ্রুবক দিয়ে গুণ — strength reduction আর shift-add

যখন গুণের একটি সংখ্যা আগে থেকেই জানা (ধ্রুবক), তখন সাধারণ multiplier লাগে না। ধ্রুবকের binary রূপে যেখানে যেখানে ১, শুধু সেই shift-গুলো যোগ করলেই চলে: ১০ = 1010 = ৮ + ২, তাই x × 10 = (x << 3) + (x << 1). দামি কাজকে সস্তা কাজ দিয়ে বদলানোর এই compiler-কৌশলের নাম strength reduction. Booth-এর ধারণাও এখানে কাজে লাগে: x × 15 = (x << 4) − x, চারটি পদের তিনটি যোগের বদলে একটি বিয়োগ।

x86-64-এ compiler এর জন্য প্রায়ই LEA (load effective address) instruction ব্যবহার করে — এটি আসলে ঠিকানা হিসাবের জন্য, কিন্তু base + index × (১, ২, ৪ বা ৮) একটি instruction-এ করতে পারে বলে ছোট গুণের দারুণ হাতিয়ার। উদাহরণ (gcc -O2, x86-64, int f(int x){ return x*10; }-এর মতো ফাংশনে সাধারণত যা দেখা যায়):

# x86-64 (Intel syntax), gcc -O2:  int f(int x) { return x * 10; }
f:
    lea   eax, [rdi + rdi*4]   # eax = x + 4x = 5x
    add   eax, eax             # eax = 10x
    ret

# RISC-V, gcc -O2: depending on compiler version and -mtune,
# either a plain mul or a shift-add sequence like this one:
f:
    slli  a5, a0, 2            # a5 = 4x
    add   a0, a5, a0           # a0 = 5x
    slli  a0, a0, 1            # a0 = 10x
    ret

Compiler কখন shift-add বাছবে আর কখন সরাসরি গুণ, তা নির্ভর করে target CPU-র গুণের latency কত আর shift-add sequence কত লম্বা হবে তার ওপর। যে CPU-তে গুণ ৩ cycle, সেখানে চার-পাঁচটি instruction-এর sequence লাভজনক নাও হতে পারে; যে microcontroller-এ গুণের hardware নেই (যেমন M extension ছাড়া RV32I), সেখানে shift-add প্রায় সবসময় লাভ। তাই নিজের হাতে x*10-কে shift-এ লেখার দরকার নেই — x*10 লিখলে compiler সেরাটা বাছবে, আর কোড পড়তেও সহজ থাকে। অংশ ৬-এর C প্রোগ্রামের শেষ লাইন দেখিয়েছে, unsigned গণিতে দুটি রূপ সব ২০ লাখ মানেই একই — overflow হলেও, কারণ দুই পাশই mod 2³²-এ হিসাব।

Hardware-এ ধ্রুবক গুণ। DSP filter বা video codec-এর chip-এ অনেক গুণ নির্দিষ্ট ধ্রুবক দিয়ে (filter-এর coefficient বা সহগ)। সেখানে পূর্ণ multiplier না বসিয়ে শুধু ধ্রুবকের ১-এর ঘরগুলোর shift (তারের সংযোগ, gate লাগে না) আর কয়েকটি adder বসানো হয়। ধ্রুবকটিকে Booth-এর মতো {−1, 0, +1} অঙ্কে লিখলে (যাকে canonical signed digit বলে, যেখানে পাশাপাশি দুটি অশূন্য অঙ্ক থাকে না) adder আরও কমে। অনেকগুলো ধ্রুবক একই ইনপুট দিয়ে গুণ হলে মাঝের ফল ভাগাভাগি করা যায় — এটি একটি সক্রিয় গবেষণার বিষয়, যার নাম multiple constant multiplication বা একাধিক ধ্রুবকের গুণ।

৮ · Fixed-point গুণ — Q15, Q31 আর rounding

অনেক DSP chip, অডিও প্রসেসিং আর ছোট microcontroller-এ floating-point hardware থাকে না বা ধীর। সেখানে ভগ্নাংশ রাখা হয় fixed-point রূপে: একটি সাধারণ integer, কিন্তু আমরা মনে মনে ধরে নিই binary point একটি নির্দিষ্ট জায়গায়। সবচেয়ে প্রচলিত Q format:

• Q15 (Q1.15 নামেও লেখা হয়): ১৬ বিটের signed integer N মানে N / 2¹⁵. পরিসর −১ থেকে 1 − 2⁻¹⁵ ≈ ০.৯৯৯৯৭; ধাপ (১ LSB) 2⁻¹⁵ ≈ ০.০০০০৩০৫. যেমন 0x4000 = ১৬৩৮৪ = ০.৫.
• Q31: ৩২ বিটে একই ধারণা, N / 2³¹.

গুণের নিয়ম। দুটি Q15 গুণ করলে (a/2¹⁵)(b/2¹⁵) = ab/2³⁰: ৩২ বিটের গুণফল Q30 রূপে। Q15-এ ফিরতে ১৫ ঘর ডানে shift. শুধু shift করলে ভগ্নাংশ কেটে যায় (truncation, যা arithmetic shift-এ সবসময় −∞-এর দিকে যায় — গড়ে আধা LSB ঋণাত্মক ঝোঁক); কাছের মানে rounding-এর জন্য shift-এর আগে 2¹⁴ যোগ করুন।

Worked example (Q15): 0.3 x 0.7
0.3 -> round(0.3 x 32768) =  9830 = 0x2666
0.7 -> round(0.7 x 32768) = 22938 = 0x599A
product (32 bit, Q30)     = 9830 x 22938 = 225480540 = 0x0D708F5C
truncate: 225480540 >> 15           = 6881
round   : (225480540 + 16384) >> 15 = 6881
result  : 6881 / 32768 = 0.2099915...   (exact 0.21, error ~ 0.0000085 < 1 LSB)

special case: -1 x -1 = 0x8000 x 0x8000 -> (1073741824 >> 15) = 32768
              does not fit in Q15 (max 32767) -> saturate to 0x7FFF

এখানে truncation আর rounding একই ফল দিয়েছে, কারণ বাদ পড়া ভগ্নাংশ ছিল আধা LSB-র কম; হাজার হাজার গুণ পরপর হলে (যেমন filter-এ) truncation-এর ঝোঁক জমে চোখে পড়ার মতো ভুল হয়, তাই DSP-তে rounding সাধারণ। আর −১ × −১-এর বিশেষ ক্ষেত্র: +১ Q15-এ ধরে না, তাই DSP instruction-গুলো ফলকে সবচেয়ে বড় মানে আটকে দেয় — saturating arithmetic. Q31-এ: ৬৪ বিটের গুণফল Q62, ৩১ ঘর ডানে shift — অর্থাৎ ওপরের ৩২ বিট (mulh) এক ঘর বাঁয়ে সরানো। এজন্যই ARM-এর DSP/NEON instruction-সেটে “doubling multiply high”-ধরনের instruction (যেমন SQDMULH) আছে: গুণ, দ্বিগুণ, ওপরের অর্ধেক, saturation — এক instruction-এ। অনেক DSP প্রসেসরের মূল একক হলো MAC (multiply-accumulate): প্রতি cycle-এ একটি গুণ আর চওড়া accumulator-এ যোগ।

৯ · AI-এর যুগে গুণের hardware

AI টুল Booth-এর নিয়ম ঠিক বলে, কিন্তু trace করতে গিয়ে প্রায়ই ভুল করে — বিশেষ করে arithmetic shift, বিয়োগের two's complement আর শেষ ফল পড়ায়। কয়েকটি সাধারণ ভুল:

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

• −M-এর two's complement নিজে বের করে মিলিয়েছি
• প্রতিটি shift arithmetic কি না (A ঋণাত্মক হলে বাঁয়ে ১ ঢুকেছে কি না) দেখেছি
• শেষ ফল ২n বিটের signed সংখ্যা হিসেবে পড়ে সাধারণ গুণের সাথে মিলিয়েছি
• সীমার ক্ষেত্র চালিয়েছি: M = −2ⁿ⁻¹, Q = −2ⁿ⁻¹, পালাক্রমের বিট, সব ১
• Wallace/Dadda-র স্তর আর গুণের latency-র দাবি সূত্র, কোড বা CPU-র manual দিয়ে মিলিয়েছি — কোনো বানানো chip-spec গ্রহণ করিনি
• AI-এর দেওয়া Verilog multiplier testbench দিয়ে সব (বা অনেক এলোমেলো) ইনপুটে simulate করেছি