Error detection আর correction — parity, checksum, CRC আর Hamming

১ · বিট কেন উল্টে যায় — noise, interference আর burst

পর্ব ০৭-এ দেখেছেন, তারের ভেতর বা বাতাসে বিট যায় সংকেত হয়ে — ভোল্টেজের ওঠানামা, আলোর ঝলক বা রেডিও তরঙ্গ। প্রাপক সংকেত মেপে ঠিক করে “এটি ০ না ১”. সমস্যা হলো, সংকেত পথে একা থাকে না। তারের ইলেকট্রনের এলোমেলো নড়াচড়া থেকে আসে তাপজনিত noise; পাশের তারের সংকেত চুইয়ে আসে (crosstalk); মোটর, মাইক্রোওয়েভ ওভেন বা বজ্রপাত থেকে আসে বৈদ্যুতিক ঝাঁকুনি; বেতারে একই চ্যানেলে অন্য Wi-Fi বা দেয়ালে প্রতিফলিত তরঙ্গ। এগুলো সংকেতের সাথে মিশে গেলে প্রাপক কখনো কখনো ১-কে ০ পড়ে, ০-কে ১।

ভুলকে দুই ভাগে দেখা হয়:

• Single-bit error: একটি ডেটা-এককে (যেমন একটি byte বা frame) শুধু একটি বিট উল্টেছে। Noise ছোট আর ক্ষণিক হলে এমন হয়।
• Burst error: প্রথম ভুল বিট থেকে শেষ ভুল বিট পর্যন্ত দৈর্ঘ্যকে বলে burst-এর দৈর্ঘ্য। মাঝের সব বিট ভুল হতেই হবে এমন নয়। যেমন 0100 পাঠিয়ে 1101 পেলে প্রথম আর শেষ বিট ভুল, দৈর্ঘ্য ৪। দ্রুতগতির link-এ burst-ই বেশি দেখা যায়, কারণ ১ মাইক্রোসেকেন্ডের একটি ঝাঁকুনি ১ Gbit/s link-এ প্রায় ১০০০টি বিটের সময় জুড়ে থাকে।

ভুলের হারকে মাপা হয় BER (bit error rate) দিয়ে — গড়ে কত বিটে একটি ভুল। ধরুন BER = ১০^−৬ আর frame ১০০০ বিটের। ভুলগুলো স্বাধীন হলে frame-টি পুরো নির্ভুল পৌঁছানোর সম্ভাবনা (১ − ১০^−৬)^১০০০ ≈ ০.৯৯৯০, অর্থাৎ প্রায় প্রতি হাজারে একটি frame নষ্ট। ১২,০০০ বিটের বড় Ethernet frame হলে নষ্ট হবে প্রায় শতকরা ১.২টি। ফাইবারে BER সাধারণত এর চেয়ে বহু গুণ কম, কিন্তু বেতারে অনেক বেশি হতে পারে। তাই যত ভালো link-ই হোক, প্রাপককে জানতেই হবে কোন frame বিশ্বাসযোগ্য।

২ · Redundancy — ধরা বনাম সারানো, FEC বনাম ARQ

শুধু ডেটা পাঠালে প্রাপক কোনোভাবেই বুঝতে পারবে না ভুল হয়েছে কি না — কারণ যেকোনো বিট-নকশাই বৈধ ডেটা হতে পারে। তাই প্রেরক ডেটা থেকে হিসাব করে কিছু বাড়তি বিট জুড়ে দেয়। একে বলে redundancy (এখানে “বাড়তি তথ্য” অর্থে, পর্ব ০২-এর বাড়তি যন্ত্র বা পথ নয়)। ডেটা আর বাড়তি বিট মিলে যা পাঠানো হয়, তাকে বলে codeword. প্রাপক একই নিয়মে আবার হিসাব করে; না মিললে বোঝে কোথাও গোলমাল।

এখানে দুটি আলাদা লক্ষ্য:

ভুল ধরা পড়লে কী করা হবে, তার দুই নীতি:

• ARQ (Automatic Repeat reQuest): প্রাপক শুধু ভুল ধরে, ভালো frame পেলে ACK পাঠায়; ACK না পেলে প্রেরক আবার পাঠায়। কম redundancy, কিন্তু প্রতিটি ভুলের দাম অন্তত একটি round-trip সময়। পর্ব ১০-এ stop-and-wait, Go-Back-N আর Selective Repeat দেখবেন; TCP-ও (পর্ব ৩০) এই নীতিতে চলে।
• FEC (Forward Error Correction): প্রেরক আগেভাগেই এত redundancy দেয় যে প্রাপক নিজেই ভুল সারায় — ফেরত-পথ লাগে না। যেখানে আবার পাঠানো ব্যয়বহুল বা অসম্ভব — মঙ্গল গ্রহ থেকে ছবি (একমুখী যাত্রায় কয়েক মিনিট), সরাসরি টিভি সম্প্রচার, CD/DVD, ভিডিও কল — সেখানে FEC.

Redundancy-র দাম মাপা হয় code rate দিয়ে: m বিট ডেটার সাথে r বিট বাড়তি দিলে n = m + r, আর rate = m/n. Hamming(7,4)-এর rate ৪/৭ ≈ ০.৫৭; Ethernet-এর ১৫০০ বাইট payload-এ ৪ বাইট CRC — rate প্রায় ০.৯৯৭। বাস্তবে প্রায়ই দুটি একসাথে চলে: Wi-Fi বা 4G/5G-র রেডিও FEC দিয়ে বেশিরভাগ ভুল সারায়, যা বাকি থাকে তা CRC ধরে আর ARQ আবার পাঠায় (একে hybrid ARQ বলে)।

৩ · Hamming distance আর d_min — কতটা ধরা, কতটা সারানো যায় (প্রমাণসহ)

দুটি সমান দৈর্ঘ্যের বিট-নকশার Hamming distance হলো কতগুলো অবস্থানে তারা আলাদা। হিসাবের সহজ উপায়: দুটিকে XOR করে ১-এর সংখ্যা গোনা। যেমন 10001001 আর 10110001: XOR = 00111000, তিনটি ১ — তাই d = ৩। এর মানে, একটিকে আরেকটিতে বদলাতে ঠিক তিনটি বিট উল্টাতে হবে।

একটি code মানে বৈধ codeword-এর একটি তালিকা। সেই তালিকার যেকোনো দুটির মধ্যে সবচেয়ে কম দূরত্বকে বলে minimum distance, d_min. পুরো তত্ত্বটি এই এক সংখ্যায়:

প্রমাণ (detection): প্রেরক codeword c পাঠাল, পথে sটি বিট উল্টাল, যেখানে ১ ≤ s ≤ d_min − ১। প্রাপ্ত শব্দ w-এর সাথে c-র দূরত্ব s. যেকোনো অন্য বৈধ codeword c′-এর দূরত্ব c থেকে কমপক্ষে d_min, যা s-এর চেয়ে বড়। তাই w কোনো বৈধ codeword নয় — না c (কারণ s ≥ ১), না অন্য কোনো c′. প্রাপক “অবৈধ শব্দ” দেখে ভুল ধরে ফেলে। আর এর চেয়ে ভালো করা সম্ভব নয়: দূরত্ব ঠিক d_min এমন দুটি codeword আছে, তাদের একটির ঠিক সেই d_minটি বিট উল্টালে আরেকটি বৈধ codeword হয়ে যায় — প্রাপক টেরই পায় না।

প্রমাণ (correction): প্রাপক নিয়ম মানে — “প্রাপ্ত শব্দের সবচেয়ে কাছের codeword-কেই আসল ধরা হবে”। ধরা যাক ২t + ১ ≤ d_min আর ভুল হয়েছে সর্বোচ্চ t টি, অর্থাৎ d(c, w) ≤ t. Hamming distance ত্রিভুজ-অসমতা মানে, তাই যেকোনো অন্য codeword c′-এর জন্য

অর্থাৎ c-ই একমাত্র সবচেয়ে কাছের codeword, আর প্রাপক ঠিকটিই বেছে নেয়। ছবির ভাষায়: প্রতিটি codeword ঘিরে t ব্যাসার্ধের একটি “বল” আঁকুন; ২t + ১ ≤ d_min হলে বলগুলো একে অপরকে ছোঁয় না, তাই প্রতিটি প্রাপ্ত শব্দ বড়জোর একটি বলের ভেতরে পড়ে।

৪ · Parity — এক বিটের পাহারা, আর দুই মাত্রার parity

সবচেয়ে সরল কৌশল: ডেটার শেষে একটি parity বিট জোড়া, যাতে মোট ১-এর সংখ্যা জোড় হয় (even parity) বা বিজোড় হয় (odd parity). ASCII-তে ‘A’ = 1000001, এতে দুটি ১ — জোড়। Even parity-তে বাড়তি বিট ০, পাঠানো হয় 10000010; odd parity-তে বাড়তি বিট ১, পাঠানো হয় 10000011. প্রাপক ১ গোনে; even parity-তে বিজোড় পেলে ভুল।

কী ধরা পড়ে না? যেকোনো একটি বিট উল্টালে ১-এর সংখ্যার জোড়-বিজোড় বদলায় — ধরা পড়ে। কিন্তু দুটি বিট উল্টালে জোড়-বিজোড় আগের মতোই থাকে — ধরা পড়ে না। সাধারণভাবে বিজোড় সংখ্যক ভুল ধরা পড়ে, জোড় সংখ্যক পড়ে না। Burst error-এ জোড় সংখ্যক বিট উল্টানোর সম্ভাবনা প্রায় অর্ধেক, তাই নেটওয়ার্কে একা parity প্রায় অচল। পুরোনো serial লাইন আর memory-তে একসময় এর ব্যবহার ছিল ব্যাপক।

দুই মাত্রার parity — কোন বিট, তাও বলা যায়

ডেটাকে সারি আর কলামের একটি ছকে সাজিয়ে প্রতিটি সারির শেষে আর প্রতিটি কলামের নিচে একটি করে parity বিট দিলে পাওয়া যায় two-dimensional parity. একটি বিট উল্টালে তার সারি আর তার কলাম — দুটির parity-ই ভুল দেখাবে, আর দুটির ছেদবিন্দুই সেই বিট। প্রাপক বিটটি উল্টে দিলেই ভুল সারানো হয়ে গেল। নিচে ৩ × ৪ = ১২ বিট ডেটা নিয়ে ধাপে ধাপে দেখুন:

        c1 c2 c3 c4
row1     1  0  1  1
row2     0  1  1  0
row3     1  1  0  0

        c1 c2 c3 c4 │ P
row1     1  0  1  1 │ 1   three 1s -> 1
row2     0  1  1  0 │ 0   two 1s   -> 0
row3     1  1  0  0 │ 0   two 1s   -> 0

        c1 c2 c3 c4 │ P
row1     1  0  1  1 │ 1
row2     0  1  1  0 │ 0
row3     1  1  0  0 │ 0
────────────────────┼──
P        0  0  0  1 │ 1

        c1 c2 c3 c4 │ P
row1     1  0  1  1 │ 1
row2     0  1  0  0 │ 0
row3     1  1  0  0 │ 0
────────────────────┼──
P        0  0  0  1 │ 1

        c1 c2 c3 c4 │ P   recount
row1     1  0  1  1 │ 1   1  ok
row2     0  1  0  0 │ 0   1  FAIL
row3     1  1  0  0 │ 0   0  ok

        c1 c2 c3 c4 │ P
row1     1  0  1  1 │ 1
row2     0  1  1  0 │ 0   <- row 2 failed
row3     1  1  0  0 │ 0
────────────────────┼──
P        0  0  0  1 │ 1
recount  0  0  1  1     <- c3 failed
fix: flip (row2, c3) 0 -> 1

        c1 c2 c3 c4 │ P   recount
row1     1  0  1  1 │ 1   1  ok
row2     1  1  0  0 │ 0   0  ok  <- row looks fine!
row3     1  1  0  0 │ 0   0  ok
P        0  0  0  1
recount  1  0  1  1     <- c1, c3 fail: detected, not fixable

৫ · Internet checksum — যোগফল দিয়ে যাচাই

IP, TCP আর UDP যে checksum ব্যবহার করে, তার নিয়ম RFC 1071-এ ব্যাখ্যা করা আছে। ধারণাটি সেই bKash নম্বরের যোগফলের মতো, কিন্তু ১৬-বিট সংখ্যায়, আর একটি বিশেষ যোগে — one's complement যোগ:

1. ডেটাকে ১৬-বিটের word-এ ভাগ করুন (বাইট বিজোড় হলে শেষে একটি শূন্য বাইট ধরে নিন)।
2. সব word যোগ করুন। যোগফল ১৬ বিট ছাড়িয়ে গেলে বাড়তি carry-টি কেটে এনে নিচের দিকে আবার যোগ করুন — একে বলে end-around carry.
3. শেষ যোগফলের সব বিট উল্টে দিন (one's complement). এটিই checksum, যা header-এর নির্দিষ্ট ঘরে বসে।
4. প্রাপক checksum-সহ সব word একইভাবে যোগ করে। ভুল না থাকলে যোগফল হবে 0xFFFF (সব ১), অর্থাৎ তার complement ০।

পূর্ণ সমাধান করা উদাহরণ

প্রশ্ন: তিনটি ১৬-বিট word 0x1234, 0xF00F, 0xABCD-এর Internet checksum কত? প্রাপক কীভাবে যাচাই করবে?

  0x1234      0001 0010 0011 0100
+ 0xF00F    + 1111 0000 0000 1111
= 0x10243   1 0000 0010 0100 0011   (17 bits: carry out)
  wrap:       0000 0010 0100 0011 + 1 = 0x0244
+ 0xABCD    + 1010 1011 1100 1101
= 0xAE11      1010 1110 0001 0001   (no carry)
checksum = ~0xAE11 = 0101 0001 1110 1110 = 0x51EE

receiver: 0x1234 + 0xF00F + 0xABCD + 0x51EE
        = 0xAE11 + 0x51EE = 0xFFFF  ->  ~0xFFFF = 0x0000  OK

প্রথম যোগে ১৭তম বিটে একটি carry বেরিয়েছে; সেটি ফেলে না দিয়ে নিচে এনে যোগ করায় 0x0243 হলো 0x0244. শেষ যোগফল 0xAE11, তার সব বিট উল্টে checksum 0x51EE. প্রাপক চারটি word যোগ করে 0xFFFF পায় — সব ঠিক। পর্ব ০৩-এ (অংশ ৭) একটি আসল IPv4 header-এর checksum 0x9b1a এই নিয়মেই হিসাব করা হয়েছিল; অংশ ৭-এর C প্রোগ্রাম একই মান আবার বের করবে।

কেন এটি দুর্বল, তবু কেন টিকে আছে

• ক্রম বদল ধরা পড়ে না: যোগের ক্রম বদলালে যোগফল বদলায় না। দুটি ১৬-বিট word-এর জায়গা অদলবদল হলে checksum একই থাকে।
• পরস্পর কাটাকাটি: এক word-এর কোনো বিট ০ → ১ আর অন্য word-এর একই অবস্থানের বিট ১ → ০ হলে যোগফল অপরিবর্তিত।
• মাত্র ১৬ বিট: এলোমেলো বড় গোলমালে মোটামুটি ৬৫,৫৩৬-এ ১ সম্ভাবনায় ভুল ধরা পড়ে না। আবার one's complement-এ 0x0000 আর 0xFFFF দুটিই “শূন্য” — এই দুইয়ের মধ্যে বদলও চোখ এড়ায়।

তবু ইন্টারনেট এটি রেখেছে কারণ এটি software-এ খুব দ্রুত (শুধু যোগ), byte order-নির্ভর নয় (RFC 1071 দেখায় যে big-endian বা little-endian মেশিনে একইভাবে যোগ করা যায়), আর ছোট পরিবর্তনের পর পুরোটা আবার না যোগ করে শুধু পার্থক্য দিয়ে হালনাগাদ করা যায় (RFC 1624) — router প্রতিটি packet-এ TTL কমিয়ে ঠিক এটাই করে। আসল পাহারা link স্তরের CRC-র কাছে; checksum দ্বিতীয় স্তরের নিরাপত্তা জাল।

৬ · CRC — বহুপদী আর modulo-2 ভাগ

CRC (cyclic redundancy check) যোগ নয়, ভাগ ব্যবহার করে। ভাবুন, প্রেরক আর প্রাপক আগে থেকে একটি “ভাজক” ঠিক করে রেখেছে। প্রেরক ডেটা এমনভাবে সাজায় যে পাঠানো পুরো বিট-নকশাটি ভাজক দিয়ে নিঃশেষে বিভাজ্য হয়। প্রাপক ভাগ করে দেখে — ভাগশেষ ০ হলে ঠিক, না হলে ভুল। বিভাজ্যতার পরীক্ষা যোগের চেয়ে অনেক কঠিন শর্ত, তাই ভুল লুকানো অনেক কঠিন।

বহুপদী দৃষ্টিভঙ্গি

একটি বিট-নকশাকে পড়া হয় এমন একটি বহুপদী (polynomial) হিসেবে, যার সহগ শুধু ০ বা ১। 10011 মানে ১·x^৪ + ০·x^৩ + ০·x^২ + ১·x + ১ = x^৪ + x + ১। আর হিসাব হয় modulo-2 arithmetic-এ: ১ + ১ = ০, কোনো carry নেই, কোনো borrow নেই। ফলে যোগ আর বিয়োগ একই জিনিস — দুটোই বিট-বিট XOR.

প্রেরক আর প্রাপক একটি generator polynomial G(x) ঠিক করে, যার degree r (অর্থাৎ বিট-নকশায় r + ১টি বিট)। ডেটা M(x) হলে নিয়ম:

1. ডেটার শেষে r টি ০ জুড়ুন — অর্থাৎ x^r·M(x).
2. একে G(x) দিয়ে modulo-2 ভাগ করুন; ভাগশেষ R(x)-এ r টি বিট। এটিই CRC.
3. জোড়া ০-গুলোর জায়গায় R বসিয়ে পাঠান: T(x) = x^r·M(x) + R(x).

কেন T(x) নিঃশেষে বিভাজ্য? x^r·M(x) = Q(x)·G(x) + R(x), তাই T(x) = Q(x)·G(x) + R(x) + R(x) = Q(x)·G(x), কারণ modulo-2-তে R + R = ০। প্রাপক পুরো frame ভাগ করে ভাগশেষ ০ পেলে মেনে নেয়।

এবার পরীক্ষার সবচেয়ে চেনা উদাহরণ — ডেটা 1101011011, generator 10011 (x^৪ + x + ১, r = ৪):

G(x) = x^4 + x + 1  ->  10011   (r = 4)
M    = 1101011011
x^4 M = 11010110110000

        1
10011 ) 11010110110000
        10011
        -----
        01001

        11
10011 ) 11010110110000
        10011
        -----
         10011   1001 + next bit 1
         10011
         -----
         00000

        1100001
10011 ) 11010110110000
        10011
        -----
         10011
         10011
         -----
         00000
              10110   quotient gets 0000
              10011
              -----
              00101

        1100001010
10011 ) 11010110110000
        10011
        -----
         10011
         10011
         -----
         00000
              10110
              10011
              -----
              00101
                10100   quotient gets 0
                10011
                -----
                00111
                  1110   remainder

data  1101011011
CRC             1110
sent  11010110111110   (14 bits)

11010110111110 ÷ 10011
remainder = 0000  ->  accept

sent      11010110111110
received  11000110111110
received ÷ 10011 -> remainder = 0111  ->  reject

হাতের ভাগ যন্ত্রে মিলিয়ে নিন। নিচের simulator প্রতিটি অবস্থানে কোন ৫ বিটের সাথে কী XOR হলো তা ছাপে, তারপর প্রাপকের দিক থেকে ঠিক আর ভুল frame যাচাই করে। data আর gen বদলে নিজের প্রশ্নও চালাতে পারেন — Run চাপুন:

// CRC by modulo-2 long division: every XOR step is printed.
function crc(data, gen) {
  const r = gen.length - 1;                      // degree of G(x)
  const bits = (data + "0".repeat(r)).split(""); // append r zeros
  let quotient = "";
  for (let i = 0; i < data.length; i++) {
    const lead = bits[i];
    const divisor = lead === "1" ? gen : "0".repeat(gen.length);
    const win = bits.slice(i, i + gen.length).join("");
    for (let j = 0; j < gen.length; j++)       // XOR = subtraction mod 2
      bits[i + j] = bits[i + j] === divisor[j] ? "0" : "1";
    quotient += lead;
    console.log(`step ${String(i + 1).padStart(2)}: ${win} xor ${divisor} = ` +
                bits.slice(i, i + gen.length).join(""));
  }
  return { quotient, rem: bits.slice(-r).join("") };
}
function remainderOf(frame, gen) {             // receiver: divide whole frame
  const b = frame.split("");
  for (let i = 0; i + gen.length <= b.length; i++)
    if (b[i] === "1") for (let j = 0; j < gen.length; j++) b[i + j] = b[i + j] === gen[j] ? "0" : "1";
  return b.slice(-(gen.length - 1)).join("");
}
const data = "1101011011", gen = "10011";        // G(x) = x^4 + x + 1
const { quotient, rem } = crc(data, gen);
console.log(`quotient = ${quotient}, CRC (remainder) = ${rem}`);
const frame = data + rem;
console.log(`sent frame     = ${frame}  check -> ${remainderOf(frame, gen)}`);
const bad = frame.slice(0, 3) + (frame[3] === "1" ? "0" : "1") + frame.slice(4);
console.log(`bit 4 flipped  = ${bad}  check -> ${remainderOf(bad, gen)}`);

step  1: 11010 xor 10011 = 01001
step  2: 10011 xor 10011 = 00000
step  3: 00001 xor 00000 = 00001
step  4: 00010 xor 00000 = 00010
step  5: 00101 xor 00000 = 00101
step  6: 01011 xor 00000 = 01011
step  7: 10110 xor 10011 = 00101
step  8: 01010 xor 00000 = 01010
step  9: 10100 xor 10011 = 00111
step 10: 01110 xor 00000 = 01110
quotient = 1100001010, CRC (remainder) = 1110
sent frame     = 11010110111110  check -> 0000
bit 4 flipped  = 11000110111110  check -> 0111

CRC কোন ভুল নিশ্চিতভাবে ধরে — আর কেন

পথে ভুল হলে প্রাপক পায় T(x) + E(x), যেখানে E(x)-এর প্রতিটি ১ মানে একটি উল্টে যাওয়া বিট। T নিঃশেষে বিভাজ্য, তাই প্রাপকের ভাগশেষ = E(x)-এর ভাগশেষ। ভুল ধরা পড়ে না ঠিক তখনই, যখন G(x) দিয়ে E(x) নিঃশেষে বিভাজ্য। এই এক বাক্য থেকে সব ধর্ম বেরিয়ে আসে:

• সব single-bit error: E(x) = xⁱ. G-তে দুই বা ততোধিক পদ থাকলে (যেমন x^r আর ১) G কখনো xⁱ-কে ভাগ করতে পারে না।
• r বা তার কম দৈর্ঘ্যের সব burst: দৈর্ঘ্য b ≤ r হলে E(x) = xⁱ·B(x), যেখানে B-র degree b − ১ < r আর B-র শেষ পদ ১। G-তে ধ্রুবক পদ ১ থাকায় G-র সাথে x-এর কোনো সাধারণ উৎপাদক নেই; তাই G | E হলে G | B হতে হতো — কিন্তু ছোট degree-র শূন্য-নয় এমন বহুপদীকে বড় degree-র G ভাগ করতে পারে না।
• সব বিজোড় সংখ্যক ভুল, যদি (x + ১) দিয়ে G বিভাজ্য হয়: বিজোড় সংখ্যক পদ থাকলে E(১) = ১ (modulo ২)। G | E হলে E = G·Q, আর G(১) = ০ হওয়ায় E(১) = ০ হতো — বিরোধ। তাই এমন E ধরা পড়বেই।
• লম্বা burst: দৈর্ঘ্য r + ১ হলে না-ধরা পড়ার সম্ভাবনা ১/২^r−১, আরও লম্বা হলে ১/২^r (ভুলের নকশা এলোমেলো ধরে)। r = ৩২ হলে প্রায় ৪৩০ কোটিতে ১।

৭ · CRC-32, Ethernet-এর FCS আর C-তে হিসাব

Ethernet (IEEE 802.3) frame-এর শেষের ৪ বাইটের FCS হলো CRC-32 — generator-এর degree ৩২, hex-এ 0x04C11DB7 (x^৩২-এর পদটি লেখা হয় না)। হিসাব হয় destination MAC থেকে payload-এর শেষ পর্যন্ত; preamble ধরা হয় না। বাস্তব CRC-32-এ সরল ভাগের সাথে আরও তিনটি নিয়ম যুক্ত: শুরুর মান সব ১ (0xFFFFFFFF, যাতে সামনে কয়েকটি বাড়তি ০ যোগ হলেও ধরা পড়ে), প্রতিটি বাইটের বিট উল্টো ক্রমে (“reflected”, কারণ Ethernet প্রতিটি বাইটের কম মানের বিট আগে পাঠায়), আর শেষে ফলকে আবার সব বিট উল্টানো। এত নিয়মের কারণে একই নামের CRC-ও ভিন্ন ফল দিতে পারে — তাই মানদণ্ড হিসেবে একটি test vector ব্যবহার হয়: ASCII "123456789"-এর CRC-32 হতে হবে 0xCBF43926.

নিচের C প্রোগ্রাম দুটি কাজ করে: পর্ব ০৩-এর IPv4 header-এর Internet checksum হিসাব ও যাচাই (আর দুটি word অদলবদল করে checksum-কে বোকা বানানো), তারপর bit-by-bit CRC-32 দিয়ে test vector মেলানো:

#include <stdio.h>
#include <stdint.h>
#include <stddef.h>
/* Internet checksum (RFC 1071): one's complement of the one's complement sum */
static uint16_t inet_csum(const uint8_t *b, size_t n) {
    uint32_t s = 0;
    for (size_t k = 0; k + 1 < n; k += 2) s += (uint32_t)(b[k] << 8 | b[k + 1]);
    if (n & 1) s += (uint32_t)b[n - 1] << 8;          /* odd length: pad with 0 */
    while (s >> 16) s = (s & 0xffff) + (s >> 16);     /* end-around carry */
    return (uint16_t)~s;
}
/* CRC-32 as in Ethernet: reflected poly 0xEDB88320, init and final XOR 0xFFFFFFFF */
static uint32_t crc32(const uint8_t *b, size_t n) {
    uint32_t c = 0xFFFFFFFFu;
    for (size_t k = 0; k < n; k++) {
        c ^= b[k];
        for (int i = 0; i < 8; i++) c = (c >> 1) ^ (0xEDB88320u & (0u - (c & 1u)));
    }
    return c ^ 0xFFFFFFFFu;
}
int main(void) {
    uint8_t ip[20] = { 0x45,0x00,0x00,0x1e,0x1c,0x46,0x40,0x00,0x40,0x11,
                       0x00,0x00,0xc0,0xa8,0x01,0x0a,0xc0,0xa8,0x01,0x14 };
    uint16_t c = inet_csum(ip, sizeof ip);
    printf("IPv4 header checksum      = 0x%04x\n", c);
    ip[10] = (uint8_t)(c >> 8); ip[11] = (uint8_t)c;     /* store it */
    printf("receiver: csum of header  = 0x%04x (0 = OK)\n", inet_csum(ip, sizeof ip));
    for (int k = 2; k < 4; k++) { uint8_t t = ip[k]; ip[k] = ip[k + 2]; ip[k + 2] = t; }
    printf("after swapping two words  = 0x%04x (error NOT detected)\n", inet_csum(ip, sizeof ip));
    const uint8_t msg[] = "123456789";
    printf("CRC-32(\"123456789\")       = 0x%08x\n", crc32(msg, 9));
    printf("CRC-32(\"123456788\")       = 0x%08x\n", crc32((const uint8_t *)"123456788", 9));
    return 0;
}

IPv4 header checksum      = 0x9b1a
receiver: csum of header  = 0x0000 (0 = OK)
after swapping two words  = 0x0000 (error NOT detected)
CRC-32("123456789")       = 0xcbf43926
CRC-32("123456788")       = 0xbcf309b0

৮ · Hamming code (7,4) — নিজে নিজে ভুল সারানো

Richard Hamming ১৯৫০ সালে Bell System Technical Journal-এ একটি চমৎকার নকশা প্রকাশ করেন: ৪টি ডেটা-বিটের সাথে ৩টি parity বিট, মোট ৭ বিট, যা যেকোনো একটি বিটের ভুল খুঁজে ঠিক করে দেয়। কৌশল হলো অবস্থান নম্বর ১ থেকে ৭ ধরে parity বিটগুলোকে বসানো ২-এর ঘাতের অবস্থানে — ১, ২, ৪ — আর ডেটা বসানো বাকি ৩, ৫, ৬, ৭-এ। প্রতিটি parity বিট পাহারা দেয় সেই অবস্থানগুলো, যাদের নম্বরের বাইনারিতে সংশ্লিষ্ট বিটটি ১:

প্রাপক তিনটি পরীক্ষা আবার করে: প্রতিটি দলের সব বিট XOR করে পায় s1, s2, s4. এই তিন বিট মিলে syndrome (s4 s2 s1). কোনো ভুল না থাকলে syndrome ০০০। অবস্থান k-এর বিট উল্টালে ঠিক সেই পরীক্ষাগুলো ব্যর্থ হয়, যাদের দলে k আছে — অর্থাৎ k-এর বাইনারির ১-গুলো। তাই syndrome-এর বাইনারি মানই ভুল বিটের অবস্থান! ধাপে ধাপে দেখুন:

position :  1   2   3   4   5   6   7
role     :  p1  p2  d3  p4  d5  d6  d7

একটি সুন্দর সংক্ষেপ: syndrome = যেসব অবস্থানে ১ আছে, তাদের নম্বরগুলোর XOR. বৈধ codeword 0110011-এ ১ আছে ২, ৩, ৬, ৭-এ, আর ২ ⊕ ৩ ⊕ ৬ ⊕ ৭ = ০। কোনো একটি অবস্থান k উল্টালে ফল হয় ঠিক k. নিচের simulator এই কৌশলেই কাজ করে, আর কয়েকটি ভুলের নকশা চালিয়ে দেখায় — দুটি ভুলে কী হয়, সেটিও:

// Hamming(7,4): parity bits at positions 1, 2, 4 (even parity).
function encode(d) {                         // d = "d3 d5 d6 d7", e.g. "1011"
  const c = [0, 0, 0, +d[0], 0, +d[1], +d[2], +d[3]]; // index 1..7 used
  for (const p of [1, 2, 4]) {               // p covers positions whose number has bit p
    let x = 0;
    for (let k = 1; k <= 7; k++) if (k & p && k !== p) x ^= c[k];
    c[p] = x;
  }
  return c.slice(1).join("");
}
function syndrome(w) {                       // XOR of positions holding a 1
  let s = 0;
  for (let k = 1; k <= 7; k++) if (w[k - 1] === "1") s ^= k;
  return s;                                  // 0 = no error, else = error position
}
const flip = (w, pos) => w.slice(0, pos - 1) + (w[pos - 1] === "1" ? "0" : "1") + w.slice(pos);
const dataOf = (w) => w[2] + w[4] + w[5] + w[6];

const sent = encode("1011");
console.log(`data 1011 -> codeword ${sent} (positions 1..7)`);
for (const errs of [[], [6], [1], [2, 6]]) {
  let recv = sent;
  for (const p of errs) recv = flip(recv, p);
  const s = syndrome(recv);
  const fixed = s ? flip(recv, s) : recv;
  console.log(`errors at [${errs}] recv ${recv} syndrome ${s.toString(2).padStart(3, "0")}` +
              ` -> fixed ${fixed} data ${dataOf(fixed)}`);
}
for (const m of [4, 8, 11, 32, 64]) {        // smallest r with 2^r >= m + r + 1
  let r = 1;
  while (2 ** r < m + r + 1) r++;
  console.log(`m=${m} data bits need r=${r} check bits -> (${m + r},${m}) code`);
}

data 1011 -> codeword 0110011 (positions 1..7)
errors at [] recv 0110011 syndrome 000 -> fixed 0110011 data 1011
errors at [6] recv 0110001 syndrome 110 -> fixed 0110011 data 1011
errors at [1] recv 1110011 syndrome 001 -> fixed 0110011 data 1011
errors at [2,6] recv 0010001 syndrome 100 -> fixed 0011001 data 1001
m=4 data bits need r=3 check bits -> (7,4) code
m=8 data bits need r=4 check bits -> (12,8) code
m=11 data bits need r=4 check bits -> (15,11) code
m=32 data bits need r=6 check bits -> (38,32) code
m=64 data bits need r=7 check bits -> (71,64) code

সাধারণ নিয়ম: 2^r ≥ m + r + ১

m টি ডেটা-বিটের সাথে কয়টি parity বিট r লাগবে, যাতে যেকোনো একটি ভুল সারানো যায়? Codeword-এর দৈর্ঘ্য n = m + r. প্রাপককে n + ১টি আলাদা অবস্থা চিনতে হবে — “কোনো ভুল নেই” আর “অবস্থান ১…n-এর কোনো একটিতে ভুল”। r বিটের syndrome সর্বোচ্চ 2^rটি আলাদা মান নিতে পারে। তাই লাগবে 2^r ≥ m + r + ১। m = ৪ হলে r = ৩ (৮ ≥ ৮) — ঠিক সমান, তাই Hamming(7,4)-কে বলে “perfect” code: একটি syndrome-ও অপচয় হয় না। m = ৮ (এক বাইট) হলে r = ৩-এ ৮ ≥ ১২ মেলে না, r = ৪-এ ১৬ ≥ ১৩ — তাই (12,8). ৬৪ বিট ডেটায় r = ৭; এর সাথে আরও একটি সামগ্রিক parity বিট যোগ করে (72,64) code হয়, যা server-এর ECC memory-তে ব্যবহৃত SECDED (single error correction, double error detection)-এর পরিচিত রূপ।

৯ · আধুনিক FEC আর stack-এর কোন তলায় কোন পাহারা

Hamming code এক বিট সারায়, কিন্তু বেতার link-এ দরকার অনেক বেশি। Claude Shannon ১৯৪৮ সালে দেখিয়েছিলেন, প্রতিটি noisy channel-এর একটি capacity আছে (পর্ব ০৭), আর তার চেয়ে কম হারে পাঠালে যথেষ্ট ভালো code দিয়ে ভুলের সম্ভাবনা যত খুশি কমানো সম্ভব — কিন্তু সেই code কীভাবে বানাতে হবে, তা বলেননি। পরের কয়েক দশক সেই খোঁজ:

• Reed-Solomon (১৯৬০): বিট নয়, পুরো symbol (যেমন বাইট) ধরে কাজ করে, তাই burst-এ খুব শক্তিশালী — একটি বাইটের ৮টি বিট নষ্ট হলেও সেটি একটিমাত্র symbol-এর ভুল। CD-DVD, QR code (দাগ লাগলেও পড়া যায়), ডিজিটাল টিভি আর উচ্চগতির Ethernet-এ ব্যবহৃত।
• LDPC (low-density parity-check): Robert Gallager ১৯৬০-এর দশকের শুরুতে উদ্ভাবন করেন, কিন্তু তখনকার কম্পিউটারে decode করা কঠিন ছিল বলে প্রায় ভুলে যাওয়া হয়; ১৯৯০-এর দশকে আবার আবিষ্কৃত হয়। খুব বড় কিন্তু “পাতলা” parity-check ছক, আর বারবার আনুমানিক হিসাব (iterative decoding) দিয়ে Shannon-এর সীমার খুব কাছে পৌঁছায়। আধুনিক Wi-Fi (802.11n থেকে ঐচ্ছিক, পরে বহুল ব্যবহৃত), 10GBASE-T Ethernet, স্যাটেলাইট টিভি (DVB-S2) আর 5G-র ডেটা চ্যানেলে ব্যবহৃত; 5G-র নিয়ন্ত্রণ চ্যানেলে আবার polar code.

এবার পুরো stack একসাথে দেখুন। একটি ফাইল ডাউনলোডের পথে একাধিক পাহারা:

এত স্তর কেন? পর্ব ০৩-এ end-to-end principle দেখেছেন। এখানে তার সবচেয়ে বিখ্যাত উদাহরণ — Saltzer, Reed আর Clark-এর “careful file transfer”. Link CRC শুধু তারের ওপরের যাত্রা পাহারা দেয়। কিন্তু router-এর ভেতরে frame যাচাইয়ের পরে আর নতুন CRC বসানোর আগে packet থাকে memory-তে আর bus-এ; সেখানে কোনো বিট উল্টালে পরের link-এর CRC সেই ভুল ডেটার ওপরেই হিসাব হবে, আর “সঠিক” বলে পার হয়ে যাবে। Disk থেকে পড়ার ভুল বা software bug-ও কোনো link CRC ধরবে না। তাই সত্যিকারের নিশ্চয়তা দিতে পারে শুধু দুই প্রান্তের যাচাই — TCP checksum, আর তার চেয়েও শক্ত application-এর hash. নিচের স্তরের পাহারা তবু দরকারি, কিন্তু দক্ষতার জন্য: প্রতিটি hop-এ ভুল আগেভাগে ধরলে নষ্ট ডেটা পুরো পথ ঘুরে প্রাপক পর্যন্ত যায় না।

১০ · AI-এর যুগে CRC আর Hamming

CRC আর Hamming-এর অঙ্ক AI-কে দিলে উত্তর আসে নিমেষে, ধাপসহ, আত্মবিশ্বাসী ভঙ্গিতে — আর প্রায়ই কোথাও একটি বিট ভুল। একটি XOR ভুল হলে পরের সব ধাপ ভুল হয়, অথচ লেখা দেখতে নিখুঁত। এই বিষয়ে AI-এর সাধারণ ভুল:

AI-এর দেওয়া error-detection উত্তর গ্রহণের আগে — চেকলিস্ট

• CRC-তে generator-এর degree r অনুযায়ী r টি ০ জোড়া হয়েছে আর ভাগশেষে ঠিক r টি বিট আছে
• প্রাপকের দিক থেকে পুরো frame ভাগ করে ভাগশেষ ০ পেয়েছি (simulator বা নিজের হাতে)
• Hamming-এ অবস্থান ১ থেকে গোনা হয়েছে, parity বিট ১, ২, ৪-এ, আর even/odd parity স্পষ্ট বলা আছে
• CRC-32 implementation test vector 0xCBF43926 দিয়ে মিলিয়েছি
• “ধরে” আর “সারায়” আলাদা করা হয়েছে, আর কোনো দাবিতে CRC বা checksum-কে নিরাপত্তা বলা হয়নি
• RFC নম্বর (যেমন RFC 1071, RFC 1624) rfc-editor.org-এ শিরোনামসহ খুঁজে পেয়েছি