Error-correcting code — parity, Hamming code আর Hamming distance

১ · Channel আর error — বিট কেন উল্টে যায়

বাজারঘরের জেলা-গুদাম থেকে প্রধান সার্ভারে প্রতি মিনিটে অর্ডারের ডেটা যায়: অর্ডার নম্বর, পণ্যের কোড, পরিমাণ, টাকার অঙ্ক। পথে বৈদ্যুতিক গোলমাল, দুর্বল বেতার সংকেত বা মেমরির একটি কোষের সমস্যায় কোনো বিট 0 থেকে 1 বা 1 থেকে 0 হয়ে যেতে পারে। পরিমাণ “2”-এর বদলে “3” হলে ভুল পণ্য যায়। গণিতে এই পথের সবচেয়ে সরল মডেল নিচেরটি।

n-বিটের একটি block-এ কয়টি বিট উল্টায়, তা একটি binomial distribution মানে (পর্ব ৪০): ঠিক k-টি উল্টানোর সম্ভাবনা C(n, k) p^k(1 − p)^n−k. উদাহরণের জন্য ধরি p = 0.01 (কাল্পনিক মান; বাস্তব তার, বেতার বা মেমরিতে এটি অনেক ছোট থেকে বেশ বড় পর্যন্ত হয়)। তাহলে একটি ৮-বিটের byte:

প্রায় ৮% byte নষ্ট হয়, কিন্তু নষ্টগুলোর বেশিরভাগে মাত্র একটি বিট উল্টেছে। তাই “একটি error শোধরানো” code-ই বিরাট লাভ দেয়। এখন code-এর ভাষা ঠিক করি।

পর্ব ৬৮ “Prefix code আর Huffman coding”-এ উল্টো কাজ করেছিলাম: উৎসের redundancy ছেঁটে বিট কমানো। বাস্তবে দুটোই চলে: আগে সংকোচন, তারপর channel-এর জন্য হিসাব করা redundancy যোগ। Shannon দেখান এই দুই কাজ আলাদা করে সর্বোত্তমভাবে করা যায় (§৭)।

২ · সবচেয়ে সরল দুটি code — repetition আর parity

Repetition code আর majority

Repetition code R_n (n বিজোড়) প্রতিটি বিট n বার পাঠায়: 0 → 00…0, 1 → 11…1. গ্রাহক majority vote নেয়: বেশিরভাগ বিট যা, সেটাই। R₃-এ 1 পাঠালে 111; একটি বিট উল্টে 101 এলেও majority 1.

প্রমাণ: majority ভুল বিট বেছে নেয় ⇔ উল্টানো বিট অক্ষত বিটের চেয়ে বেশি ⇔ k > n − k ⇔ k ≥ (n + 1)/2 (n বিজোড়)। আলাদা k-এর ঘটনা disjoint, তাই সম্ভাবনা যোগ হয়। ∎ R₃-এ এটি 3p²(1 − p) + p³ = 3p² − 2p³; p = 0.1 হলে 0.028, অর্থাৎ error প্রায় সাড়ে তিন গুণ কমল। দাম: rate 1/3, তিন গুণ বিট পাঠাতে হয়।

n বাড়ালে ব্যর্থতা দ্রুত শূন্যের দিকে যায়। কতটা দ্রুত? উল্টানো বিটের সংখ্যার গড় np < n/2, আর গড় থেকে n/2 পর্যন্ত সরে যাওয়ার সম্ভাবনা n-এর সঙ্গে ঘাতের হারে কমে: এটাই পর্ব ৪১-এর Chernoff bound-এর বক্তব্য। কিন্তু rate 1/n শূন্যে নামে। “কম error আর ভালো rate একসঙ্গে পাওয়া যায় কি?” এই প্রশ্নই পুরো পর্বকে চালায়।

Parity code — শুধু ধরা

Parity check code k বিটের শেষে একটি parity bit বসায়, যাতে মোট 1-এর সংখ্যা জোড় হয় (even parity). যেমন 1011001-এর চারটি 1, তাই parity বিট 0, পাঠানো হয় 10110010. Rate k/(k + 1), খুবই ভালো। “জোড় না বিজোড়” প্রশ্নটি XOR দিয়ে লেখা যায়: parity বিট = সব data বিটের XOR (পর্ব ৬৯-এর Boolean function).

1. একটি বিট উল্টালে 1-এর সংখ্যা ঠিক এক বাড়ে বা কমে, তাই তার জোড়-বিজোড় অবস্থা বদলায়। — ±1-এ parity বদলায়
2. e-টি আলাদা বিট উল্টালে এই বদল e বার ঘটে; শুরুতে সংখ্যা জোড়, তাই শেষে জোড় ⇔ e জোড়। — e বার বদল, induction
3. গ্রাহক শুধু মোট parity দেখে, তাই e বিজোড় হলে “error”, e জোড় হলে “ঠিক আছে” বলে। আর অবস্থান 1-এ একটি error আর অবস্থান 5-এ একটি error একই বিজোড় parity দেখায়, তাই অবস্থান বলা যায় না। ∎

এর সঙ্গে আছে পর্ব ২৬-এর check digit (ISBN, ব্যাংক কার্ড) আর CRC, যারা আরও বেশি ধরনের error ধরে, কিন্তু শোধরায় না। ধরা পড়লে নেটওয়ার্ক সাধারণত আবার পাঠাতে বলে।

নিচের ব্লক BSC-তে p = 0.1 নিয়ে R₁, R₃, R₅, R₇-এর ব্যর্থতা সূত্রে আর ২০,০০০টি করে seed-বাঁধা simulation-এ মেলায়, তারপর ৮-বিটের parity code-এর ধরা-না-ধরার সম্ভাবনা গোনে। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

import random
from math import comb
def rep_fail_exact(n, p):              # majority wrong: more than n//2 flips
    return sum(comb(n, k) * p**k * (1 - p)**(n - k) for k in range(n // 2 + 1, n + 1))
def rep_fail_sim(n, p, trials):
    bad = 0
    for _ in range(trials):
        flips = sum(random.random() < p for _ in range(n))
        bad += flips > n // 2           # majority decoding picks the wrong bit
    return bad / trials
random.seed(72); p = 0.1; T = 20000
print(f"BSC p = {p}, {T} simulated blocks each")
for n in (1, 3, 5, 7):
    print(f"R{n}: rate 1/{n}  exact {rep_fail_exact(n, p):.5f}  sim {rep_fail_sim(n, p, T):.5f}")
# even-parity code on 8 bits: an error slips through iff an even number (>= 2) flip
undetected = sum(comb(8, k) * p**k * (1 - p)**(8 - k) for k in range(2, 9, 2))
detected = sum(comb(8, k) * p**k * (1 - p)**(8 - k) for k in range(1, 9, 2))
print(f"parity-8: detected {detected:.4f}  undetected {undetected:.4f}")
word = [1, 0, 1, 1, 0, 0, 1]
sent = word + [sum(word) % 2]          # parity bit makes the weight even
for flips in ([2], [2, 5], [0, 3, 6]):
    r = sent[:]
    for i in flips:
        r[i] ^= 1
    print(len(flips), "flip(s): parity check says", "error" if sum(r) % 2 else "OK")

BSC p = 0.1, 20000 simulated blocks each
R1: rate 1/1  exact 0.10000  sim 0.10170
R3: rate 1/3  exact 0.02800  sim 0.02880
R5: rate 1/5  exact 0.00856  sim 0.00915
R7: rate 1/7  exact 0.00273  sim 0.00260
parity-8: detected 0.4161  undetected 0.1534
1 flip(s): parity check says error
2 flip(s): parity check says OK
3 flip(s): parity check says error

৩ · Hamming distance আর minimum distance

যেমন d(1011, 1001) = 1, d(0000, 1111) = 4. পর্ব ৩৬-এ Gray code-এ পরপর দুটি শব্দের Hamming distance 1 দেখেছেন, আর পর্ব ৫৭-এর hypercube Q_n-এ d(x, y) ঠিক x থেকে y-তে সবচেয়ে ছোট পথের edge-সংখ্যা। “দূরত্ব” নামটি যথার্থ কি না, তা প্রমাণ করা দরকার।

1. (ক) আর (খ) সংজ্ঞা থেকে সরাসরি: সংখ্যাটি গণনা, তাই অঋণাত্মক; শূন্য মানে কোথাও অমিল নেই; “x_i ≠ y_i” আর “y_i ≠ x_i” একই শর্ত। — সংজ্ঞা
2. (গ) এমন একটি অবস্থান i নিন, যেখানে x_i ≠ z_i. বিট মাত্র দুটি মান নেয়, তাই y_i হয় x_i-এর সমান, নয় z_i-এর সমান, দুটোর সমান হতে পারে না। ফলে x_i ≠ y_i অথবা y_i ≠ z_i. — দুই মানের ক্ষেত্র ভাগ
3. অর্থাৎ d(x, z)-তে গোনা প্রতিটি অবস্থান d(x, y) বা d(y, z)-এর অন্তত একটিতে গোনা হয়। সব অবস্থানে যোগ করলে d(x, z) ≤ d(x, y) + d(y, z). ∎ — গণনা

এখন মূল দুটি উপপাদ্য। গ্রাহক শব্দ r পায়; পাঠানো হয়েছিল codeword c, আর error-pattern e = r ⊕ c, যার weight হলো উল্টানো বিটের সংখ্যা। Nearest-codeword decoding মানে r-এর সবচেয়ে কাছের codeword বেছে নেওয়া। p < 1/2 হলে কম বিট উল্টানো বেশি সম্ভাব্য, তাই এটিই সবচেয়ে সম্ভাব্য পাঠানো শব্দ বেছে নেয়।

1. (ক, ⇐) 1 ≤ w(e) ≤ s হলে 1 ≤ d(r, c) ≤ s < d(C), তাই r অন্য কোনো codeword হতে পারে না, আবার c-ও নয়; গ্রাহক দেখে r ∉ C, অর্থাৎ error ধরা পড়ে। — দূরত্ব d-এর কম
2. (ক, ⇒) d(C) ≤ s হলে দুটি codeword c, c′ আছে, d(c, c′) ≤ s. c পাঠালে e = c ⊕ c′ error (weight ≤ s) ঘটলে গ্রাহক পায় c′, একটি বৈধ codeword; error ধরা পড়ে না। — পাল্টা-উদাহরণ
3. (খ, ⇐) ধরুন d(r, c) ≤ t, আর কোনো c′ ≠ c-এর জন্য d(r, c′) ≤ d(r, c). তাহলে triangle inequality অনুযায়ী d(c, c′) ≤ d(c, r) + d(r, c′) ≤ 2t < d(C), বিরোধ। তাই c-ই একমাত্র সবচেয়ে কাছের। — উপপাদ্য ৩.২
4. (খ, ⇒) d(C) = d ≤ 2t হলে c, c′ নিন, d(c, c′) = d. যে d অবস্থানে তারা আলাদা, তার ⌈d/2⌉টিতে c-কে উল্টে r বানান। তাহলে d(r, c) = ⌈d/2⌉ ≤ t, অথচ d(r, c′) = ⌊d/2⌋ ≤ d(r, c): c′ অন্তত সমান কাছে, তাই decoder c পাবে এমন নিশ্চয়তা নেই। ∎ — মাঝের শব্দ

সাবধান: d − 1টি ধরা অথবা t-টি শোধরানো, একসঙ্গে দুটো নয়। d = 3-এর code দুটি error ধরতে পারে, কিন্তু তখন তাকে শোধরানোর চেষ্টা বাদ দিতে হয়; শোধরানোর মোডে দুটি error তাকে ভুল codeword-এ নিয়ে যায় (§৬)। সাধারণ রূপ: একসঙ্গে t-টি শোধরানো আর মোট s-টি (s ≥ t) পর্যন্ত ধরা যায় ⇔ d ≥ t + s + 1; প্রমাণ একই ধাঁচের। R₃ = {000, 111}-এ d = 3, তাই একটি শোধরায়। নিচের ছবিতে Q₃-এর ঘনকে এর জ্যামিতি দেখুন।

৪ · Hamming bound, perfect code আর অন্য সীমা

ছবির বলগুলো একটি গণনার জন্ম দেয়। কেন্দ্র x আর ব্যাসার্ধ t-এর Hamming ball B(x, t) = {y : d(x, y) ≤ t}. x থেকে ঠিক i দূরত্বের শব্দ পেতে n অবস্থান থেকে i-টি উল্টানোর জায়গা বাছতে হয়, তাই (পর্ব ৩৪)

V(n, t) = |B(x, t)| = C(n, 0) + C(n, 1) + ⋯ + C(n, t),

যা কেন্দ্রের ওপর নির্ভর করে না।

1. দুটি আলাদা codeword c, c′-এর বল B(c, t) আর B(c′, t) disjoint: কোনো y দুটিতেই থাকলে d(c, c′) ≤ d(c, y) + d(y, c′) ≤ 2t < d(C), বিরোধ। — triangle inequality
2. M-টি disjoint বল, প্রতিটিতে V(n, t)টি শব্দ, সবই {0, 1}ⁿ-এর ভেতরে, যেখানে মোট 2ⁿটি শব্দ। তাই M · V(n, t) ≤ 2ⁿ. ∎ — disjoint সেটের যোগ

ছবির R₃ perfect: 2 · (1 + 3) = 8 = 2³. যেকোনো বিজোড় n-এ R_n-ও perfect (প্রমাণ: C(n, i) = C(n, n − i) দিয়ে V(n, (n − 1)/2) = 2ⁿ⁻¹). এগুলো “তুচ্ছ” perfect code. অতুচ্ছ উদাহরণ দুটি পরিবার: §৬-এর Hamming code আর Golay-এর (23, 12) code, যাতে t = 3: 2¹²(1 + 23 + 253 + 1771) = 2¹² · 2048 = 2²³. নিচের stepper n = 7, t = 1-এর গণনাটি ধাপে ধাপে দেখায়।

1space: 2^7 = 128 words2V(7,1) = 1 + C(7,1) = 83d = 3 ≥ 2·1+1: disjoint4M ≤ 128 / 8 = 165Hamming(7,4): 16 × 8 = 1286t = 2: V = 29, M ≤ 4

আরেকটি ওপরের সীমা আরও সরল যুক্তিতে আসে।

1. প্রতিটি codeword থেকে প্রথম d − 1টি বিট মুছে দৈর্ঘ্য n − d + 1-এর শব্দ বানান। — puncturing
2. দুটি আলাদা codeword অন্তত d অবস্থানে আলাদা; মোছা হয়েছে মাত্র d − 1টি অবস্থান, তাই ছাঁটা শব্দ দুটিও অন্তত একটি অবস্থানে আলাদা। — minimum distance
3. অতএব ছাঁটার ফাংশনটি one-to-one, আর দৈর্ঘ্য n − d + 1-এর শব্দ মাত্র 2^n−d+1টি; পর্ব ৩২-এর pigeonhole অনুযায়ী M ≤ 2^n−d+1. ∎

Repetition code (k = 1, d = n) ঠিক এই সীমায় বসে। Hamming(7,4)-এ 4 < 7 − 3 + 1 = 5, তাই binary-তে Hamming bound বেশি কড়া। বড় alphabet-এ (যেমন GF(2⁸)-এর উপাদানকে চিহ্ন ধরলে) Reed–Solomon code Singleton-এ সমতা দেয়; এমন code-কে MDS বলে (§৭)।

ওপরের সীমা বলে “এর বেশি অসম্ভব”; নিচের সীমা বলে “অন্তত এতটুকু সম্ভব”।

প্রমাণ (greedy): একটি একটি করে শব্দ নিন, যা আগে নেওয়া সবার থেকে অন্তত d দূরে। যখন আর নেওয়া যায় না, তখন প্রতিটি শব্দ কোনো নেওয়া শব্দের d − 1 দূরত্বের মধ্যে, অর্থাৎ M-টি বল B(c, d − 1) মিলে পুরো space ঢাকে: M · V(n, d − 1) ≥ 2ⁿ. ∎ n = 7, d = 3-এ নিশ্চয়তা M ≥ 128/29 ≈ 4.41, অর্থাৎ অন্তত 5টি codeword; Hamming bound বলে বড়জোর 16, আর Hamming code 16-ই দেয়। দুই সীমার মাঝখানে সবচেয়ে ভালো code কোথায়, বড় n-এ তা আজও পুরোপুরি জানা নেই।

নিচের ব্লক ছোট কয়েকটি code-এর minimum distance brute force-এ গোনে আর Hamming ও Singleton সীমা মেলায়; Golay-এর সমতা আর GV-র সংখ্যাও দেখায়।

from itertools import combinations, product
from math import comb
def dist(x, y):
    return sum(a != b for a, b in zip(x, y))
def span(rows):                        # all XOR-combinations of the rows
    out = set()
    for bits in product((0, 1), repeat=len(rows)):
        c = 0
        for r, b in zip(rows, bits):
            if b:
                c ^= int(r, 2)
        out.add(format(c, f"0{len(rows[0])}b"))
    return out
def report(name, C):
    n, M = len(next(iter(C))), len(C)
    d = min(dist(x, y) for x, y in combinations(C, 2))
    t = (d - 1) // 2
    ball = sum(comb(n, i) for i in range(t + 1))
    tag = " PERFECT" if M * ball == 2**n else ""
    print(f"{name}: n={n} M={M} d={d}, detect {d-1}, correct {t}")
    print(f"   M*V={M * ball} vs 2^n={2**n}{tag}; Singleton M <= {2**(n-d+1)}")
report("R3", {"000", "111"})
report("R5", {"00000", "11111"})
report("parity-4", {"".join(w) for w in product("01", repeat=4) if w.count("1") % 2 == 0})
report("Ham(7,4)", span(["1110000", "1001100", "0101010", "1101001"]))
report("exam C", {"00000", "01011", "10101", "11110"})
print("Golay(23,12), t=3:", 2**12 * sum(comb(23, i) for i in range(4)) == 2**23)
print("GV n=7 d=3: some code has M >=", 2**7 / sum(comb(7, i) for i in range(3)))

R3: n=3 M=2 d=3, detect 2, correct 1
   M*V=8 vs 2^n=8 PERFECT; Singleton M <= 2
R5: n=5 M=2 d=5, detect 4, correct 2
   M*V=32 vs 2^n=32 PERFECT; Singleton M <= 2
parity-4: n=4 M=8 d=2, detect 1, correct 0
   M*V=8 vs 2^n=16; Singleton M <= 8
Ham(7,4): n=7 M=16 d=3, detect 2, correct 1
   M*V=128 vs 2^n=128 PERFECT; Singleton M <= 32
exam C: n=5 M=4 d=3, detect 2, correct 1
   M*V=24 vs 2^n=32; Singleton M <= 8
Golay(23,12), t=3: True
GV n=7 d=3: some code has M >= 4.413793103448276

৫ · Linear code — matrix দিয়ে code

এলোমেলো code-এ M-টি codeword-এর তালিকা রাখতে আর প্রতিটি প্রাপ্ত শব্দকে সবার সঙ্গে মেলাতে হয়; k = 50 হলে তালিকায় 2⁵⁰টি শব্দ, অচল। বীজগণিত এখানে বাঁচায়। {0, 1}-এ ⊕ (XOR, অর্থাৎ যোগ mod 2) আর AND (গুণ) নিয়ে GF(2), সবচেয়ে ছোট finite field (পর্ব ৩০; ring আর field-এর গভীর কাঠামো পর্ব ৭১ “Ring আর field — modular ring, polynomial আর GF(2ⁿ)”-এ)। তাহলে {0, 1}ⁿ একটি vector space: শব্দ যোগ হয় ঘরে ঘরে XOR দিয়ে।

1. আলাদা c, c′ ∈ C-এর জন্য d(c, c′) = w(c ⊕ c′), আর c ⊕ c′ একটি শূন্য-নয় codeword (linear). তাই প্রতিটি দূরত্ব কোনো শূন্য-নয় codeword-এর weight. — সংজ্ঞা ৩.১
2. উল্টো দিকে, শূন্য-নয় c-এর weight w(c) = d(c, 0), আর 0 ∈ C, তাই প্রতিটি weight কোনো দুই codeword-এর দূরত্ব। দুই সেট সমান, তাই সর্বনিম্নও সমান। ∎ — উভয় দিক

লাভ: d বের করতে M(M − 1)/2টি জোড়ার বদলে M − 1টি weight দেখলেই চলে।

uG মানে u-তে যেসব অবস্থানে 1, G-এর সেই সারিগুলোর XOR (পর্ব ১৯-এর matrix গুণ, যোগটা শুধু mod 2). Syndrome-এর জাদু এক লাইনে: r = c ⊕ e হলে s = Hc^T ⊕ He^T = He^T. Syndrome শুধু error-এর ওপর নির্ভর করে, কোন codeword পাঠানো হয়েছিল তার ওপর নয়। তাই decoder একটি ছোট table রাখে: প্রতিটি syndrome-এর জন্য সবচেয়ে কম weight-এর error. একে syndrome decoding বলে। (Group-এর ভাষায় C হলো ({0, 1}ⁿ, ⊕)-এর একটি subgroup, আর একই syndrome-এর শব্দগুলো C-এর একটি coset; coset যে space-কে ভাগ করে, তা পর্ব ৫৫-এর partition, আর পর্ব ৭০ “Group — symmetry, cyclic group আর Lagrange-এর উপপাদ্য”-এ এর সাধারণ রূপ।)

প্রমাণ: c-এর যেসব অবস্থানে 1, Hc^T ঠিক H-এর সেই column-গুলোর যোগ। তাই weight w-এর codeword আছে ⇔ H-এর কোনো w-টি column-এর যোগ শূন্য। উপপাদ্য ৫.২ বাকিটা দেয়। ∎

৬ · Hamming(7,4) — syndrome বলে দেয় কোন বিট ভুল

উপপাদ্য ৫.৪ একটি নকশার নির্দেশ দেয়: d ≥ 3 চাইলে H-এর কোনো column শূন্য হবে না (নইলে weight 1-এর codeword) আর কোনো দুটি column সমান হবে না (নইলে তাদের যোগ শূন্য, weight 2). ৩ সারির column শূন্য-নয় এমন মাত্র 2³ − 1 = 7টি। সবকটি নিন, আর j-তম column-এ j-এর binary রূপ বসান:

অবস্থান 1, 2, 4 (২-এর ঘাত) parity বিট p₁, p₂, p₄; অবস্থান 3, 5, 6, 7-এ data বিট d₁, d₂, d₃, d₄. H-এর প্রতিটি সারি বলে কোন অবস্থানগুলোর XOR শূন্য হতে হবে: p₁ দেখে অবস্থান 1, 3, 5, 7 (যাদের binary রূপে ১-এর বিট 1); p₂ দেখে 2, 3, 6, 7; p₄ দেখে 4, 5, 6, 7. Richard Hamming-এর ১৯৫০ সালের প্রবন্ধে বর্ণিত বিন্যাস এটাই। Data-র চারটি একক শব্দ encode করলে G-এর সারি: d₁ → 1110000, d₂ → 1001100, d₃ → 0101010, d₄ → 1101001.

1. কোনো column শূন্য নয়, তাই weight 1-এর codeword নেই; সব column আলাদা, তাই দুটির যোগ শূন্য নয়, weight 2-এর codeword নেই। — উপপাদ্য ৫.৪
2. Column 1, 2, 3 = 001, 010, 011, যোগ 000; তাই 1110000 একটি weight-3 codeword (এটি G-এর প্রথম সারি)। অতএব d = 3. — উপপাদ্য ৫.৪
3. H-এর তিনটি সারি স্বাধীন (column 1, 2, 4 একক ভেক্টর), তাই parity শর্ত তিনটি আর dimension k = 7 − 3 = 4, M = 16. 16 · V(7, 1) = 16 · 8 = 128 = 2⁷: perfect. — উপপাদ্য ৪.১-এ সমতা
4. e = অবস্থান j-তে একটি 1 হলে syndrome He^T = H-এর j-তম column = j-এর binary রূপ। ∎ — syndrome-এর সূত্র

বাজারঘরের একটি অর্ডারের পরিমাণ-কোড 1011 পাঠানো যাক।

1data d1 d2 d3 d4 = 10112pos 3,5,6,7 ← 1,0,1,13p1 = c3 ⊕ c5 ⊕ c74p2 = c3 ⊕ c6 ⊕ c75p4 = c5 ⊕ c6 ⊕ c76codeword = 0110011

পথে অবস্থান 5-এর বিটটি উল্টে গেল। গ্রাহক কী করে?

1r = 01101112s1 = r1 ⊕ r3 ⊕ r5 ⊕ r73s2 = r2 ⊕ r3 ⊕ r6 ⊕ r74s4 = r4 ⊕ r5 ⊕ r6 ⊕ r75s = 101 → flip bit 56data = r3 r5 r6 r7

নিচের ব্লক একই encoder আর decoder লেখে, তারপর সব 16 × 7 = 112টি একক error আর সব 16 × 21 = 336টি দ্বৈত error পরীক্ষা করে।

from itertools import product, combinations
G = ["1110000", "1001100", "0101010", "1101001"]   # rows for data bits d1..d4
def encode(data):                      # XOR of the rows picked by the data bits
    c = 0
    for bit, row in zip(data, G):
        if bit == "1":
            c ^= int(row, 2)
    return format(c, "07b")
def syndrome(r):                       # XOR of the positions (1..7) holding a 1
    s = 0
    for pos, bit in enumerate(r, start=1):
        if bit == "1":
            s ^= pos
    return s
def flip(w, i):
    return w[:i] + ("1" if w[i] == "0" else "0") + w[i + 1:]
def decode(r):
    s = syndrome(r)
    if s:
        r = flip(r, s - 1)             # syndrome = position of the error
    return r[2] + r[4] + r[5] + r[6]   # data sits at positions 3, 5, 6, 7
c = encode("1011"); r = flip(c, 4)
print("1011 ->", c, "| received", r, "syndrome", format(syndrome(r), "03b"), "->", decode(r))
code = {encode("".join(d)): "".join(d) for d in product("01", repeat=4)}
print("codewords:", len(code), "weights:", sorted({w.count("1") for w in code}))
ok1 = all(decode(flip(c, i)) == d for c, d in code.items() for i in range(7))
print("all 16 x 7 single errors corrected:", ok1)
bad2 = sum(decode(flip(flip(c, i), j)) != d
           for c, d in code.items() for i, j in combinations(range(7), 2))
print("double errors decoded wrongly:", bad2, "of", 16 * 21)

1011 -> 0110011 | received 0110111 syndrome 101 -> 1011
codewords: 16 weights: [0, 3, 4, 7]
all 16 x 7 single errors corrected: True
double errors decoded wrongly: 336 of 336

সাধারণভাবে r-টি parity বিটে H-এর column হিসেবে 2^r − 1টি শূন্য-নয় ভেক্টর বসানো যায়, তাই Hamming code-এর দৈর্ঘ্য n = 2^r − 1 আর k = n − r: (7, 4), (15, 11), (31, 26), … প্রতিটিই perfect, কারণ 2^k(1 + n) = 2^n−r · 2^r = 2ⁿ. k-বিট data-র জন্য একটি error শোধরাতে কয়টি parity বিট লাগে? সব একক error আর “error নেই” আলাদা করতে 2^r ≥ k + r + 1 লাগে, আর Hamming-এর নির্মাণ দেখায় সেটাই যথেষ্ট।

৭ · SECDED, বাস্তবের code আর Shannon-এর সীমা

একটি বিট বেশি, অনেক নিরাপত্তা বেশি

Hamming(7,4)-এর শেষে পুরো শব্দের একটি parity বিট যোগ করলে extended Hamming code (8,4) পাওয়া যায়। weight 3-এর codeword weight 4 হয়, weight 4 আর 0 যেমন ছিল থাকে, আর 7 হয় 8; তাই সব codeword-এর weight জোড় আর d = 4 (প্রমাণ অনুশীলন ১-এ)। উপপাদ্য ৩.৩-এর সাধারণ রূপে t = 1, s = 2: d ≥ 1 + 2 + 1 = 4. তাই code-টি একসঙ্গে একটি error শোধরায় আর দুটি error ধরে, এর নাম SECDED (single error correction, double error detection). Decoder-এর নিয়ম:

from itertools import product, combinations
G = ["1110000", "1001100", "0101010", "1101001"]
def encode8(data):                     # Hamming(7,4) word + overall parity bit
    c = 0
    for bit, row in zip(data, G):
        if bit == "1":
            c ^= int(row, 2)
    w = format(c, "07b")
    return w + str(w.count("1") % 2)
def secded(r):                         # returns (verdict, corrected word)
    s = 0
    for pos, bit in enumerate(r[:7], start=1):
        if bit == "1":
            s ^= pos
    odd = r.count("1") % 2             # overall parity of all 8 bits
    if s == 0 and not odd:
        return "ok", r
    if odd:                            # odd number of flips: assume one, fix it
        i = s - 1 if s else 7          # s = 0 means the parity bit itself
        return "fixed", r[:i] + str(1 - int(r[i])) + r[i + 1:]
    return "double", r                 # even flips, s != 0: detect, do not fix
def flips(w, idx):
    return "".join(str(1 - int(b)) if i in idx else b for i, b in enumerate(w))
code = [encode8("".join(d)) for d in product("01", repeat=4)]
print("weights:", sorted({c.count("1") for c in code}), "| 1011 ->", encode8("1011"))
for k in (1, 2, 3):
    tally = {}
    for c in code:
        for idx in combinations(range(8), k):
            v, out = secded(flips(c, idx))
            key = v + ("" if v != "fixed" else (" right" if out == c else " wrong"))
            tally[key] = tally.get(key, 0) + 1
    print(k, "error(s):", dict(sorted(tally.items())))

weights: [0, 4, 8] | 1011 -> 01100110
1 error(s): {'fixed right': 128}
2 error(s): {'double': 448}
3 error(s): {'fixed wrong': 896}

বাস্তবে কোথায়

সার্ভারের ECC memory-তে প্রতি 64 data বিটে 8টি check বিটের (72, 64) SECDED বিন্যাস বহুল প্রচলিত বলে বর্ণিত; 2⁷ = 128 ≥ 64 + 7 + 1, তাই একক error-এর জন্য 7টি, আর দ্বৈত error ধরতে আরও 1টি। হার্ডওয়্যারের দিক Computer Architecture কোর্সের পর্ব ৪৯-এ। নেটওয়ার্কে সাধারণত CRC দিয়ে error ধরে আবার পাঠানো হয়; parity, checksum, CRC আর Hamming-এর ব্যবহারিক দিক Computer Networks কোর্সের পর্ব ৯-এ, আর ASCII-র সঙ্গে parity বিট Computer Fundamentals কোর্সের পর্ব ১৮-এ। CD, DVD আর QR code-এ Reed–Solomon code ব্যবহৃত হয় বলে বহুল নথিভুক্ত: তার চিহ্ন বিট নয়, GF(2⁸)-এর উপাদান (একটি byte), তাই একটি আঁচড়ে পরপর অনেক বিট নষ্ট হলেও তা অল্প কয়েকটি চিহ্নের error, আর code Singleton bound-এ সমতা দেয়। QR code-এ L, M, Q, H নামের চারটি সুরক্ষা-স্তর আছে, যা মোটামুটি ৭% থেকে ৩০% পর্যন্ত চিহ্ন-ক্ষতি সামলাতে পারে বলে মানদণ্ডে বর্ণিত।

Shannon-এর channel coding উপপাদ্য

Repetition code-এ error কমাতে rate শূন্যে নামাতে হয়েছিল। এটা কি অনিবার্য? Claude Shannon-এর ১৯৪৮ সালের প্রবন্ধ “A Mathematical Theory of Communication” বলে, না। BSC(p)-র channel capacity

C = 1 − H₂(p), যেখানে H₂(p) = −p log₂ p − (1 − p) log₂(1 − p),

আর H₂ হলো পর্ব ৬৮-এর entropy, দুই ফলের জন্য। উপপাদ্য (এখানে প্রমাণ নয়, শুধু বক্তব্য): যেকোনো rate R < C-এ এমন code আছে, যার decoding-ভুলের সম্ভাবনা n বাড়ালে যত খুশি ছোট হয়; R > C-এ তা অসম্ভব। p = 0.01-এ C ≈ 0.919, p = 0.1-এ C ≈ 0.531 (scratch-এ গোনা)। মজার তুলনা: Hamming(7,4)-এর rate 4/7 ≈ 0.571, যা p = 0.1-এর capacity-র চেয়ে বেশি; সেই channel-এ এই rate-এ কোনো code দিয়েই error যত খুশি কমানো যাবে না। Shannon-এর প্রমাণ এলোমেলো code বেছে গড় নেয় (পর্ব ৪৩-এর probabilistic method-এর ধাঁচ), তাই এটি অস্তিত্ব দেখায়, কোনো নির্দিষ্ট code নয়।

৮ · পরীক্ষার অঙ্ক আর একটি ভুল প্রমাণ

অঙ্ক ১: একটি code বিশ্লেষণ

C = {00000, 01011, 10101, 11110}. (ক) d(C) কত? (খ) কয়টি error ধরে, কয়টি শোধরায়? (গ) C কি linear? (ঘ) Perfect কি না।

1. (ক) ছয়টি জোড়ার দূরত্ব: 3, 3, 4, 4, 3, 3. তাই d = 3.
2. (খ) d − 1 = 2টি ধরে, অথবা ⌊(3 − 1)/2⌋ = 1টি শোধরায়।
3. (গ) 01011 ⊕ 10101 = 11110, আর যেকোনো শব্দ নিজের সঙ্গে XOR করলে 00000; চারটি শব্দ XOR-এ বদ্ধ, তাই linear, k = 2. শূন্য-নয় weight 3, 3, 4: সর্বনিম্ন 3, (ক)-এর সঙ্গে মেলে (উপপাদ্য ৫.২)।
4. (ঘ) M · V(5, 1) = 4 × 6 = 24 < 32: perfect নয়; Hamming bound বলে দৈর্ঘ্য 5-এ single-error-correcting code-এ বড়জোর ⌊32/6⌋ = 5টি codeword. (§৪-এর কোডে মেলানো।)

অঙ্ক ২: কয়টি parity বিট

k = 8, 11, 32, 64 data বিটে একক error শোধরাতে সর্বনিম্ন কয়টি parity বিট r লাগে? SECDED-এ কয়টি?

1. শর্ত 2^r ≥ k + r + 1. k = 8: r = 3-এ 8 < 12, r = 4-এ 16 ≥ 13, তাই 4. k = 11: 16 ≥ 16, 4 (সমতা, তাই (15, 11) perfect).
2. k = 32: r = 5-এ 32 < 38, r = 6-এ 64 ≥ 39, তাই 6. k = 64: r = 6-এ 64 < 71, r = 7-এ 128 ≥ 72, তাই 7.
3. SECDED-এ একটি করে বেশি: 5, 5, 7, 8. শেষেরটিই (72, 64). (scratch-এ লুপ দিয়ে মেলানো।)

অঙ্ক ৩: repetition-এর হিসাব আর Hamming decode

(ক) p = 0.1-এ R₅-এর ব্যর্থতা: 3, 4 বা 5টি উল্টাতে হবে: 10p³(1 − p)² + 5p⁴(1 − p) + p⁵ = 0.0081 + 0.00045 + 0.00001 = 0.00856 (§২-এর কোডে একই)। (খ) Hamming(7,4)-এ প্রাপ্ত 1011011. 1-ওয়ালা অবস্থান 1, 3, 4, 6, 7; তাদের XOR 1 ⊕ 3 ⊕ 4 ⊕ 6 ⊕ 7 = 7, তাই অবস্থান 7 উল্টে 1011010, data (অবস্থান 3, 5, 6, 7) = 1010. যাচাই: 1010-এর encoding G-এর সারি 1 ⊕ সারি 3 = 1011010.

প্রমাণের ভুল ধরুন: “Hamming bound মানলেই code আছে”

একজন লিখলেন: “দৈর্ঘ্য 4, d = 3, M = 3 চাই। t = 1, V(4, 1) = 5, আর 3 × 5 = 15 ≤ 16. Hamming bound মানে, তাই এমন code আছে।”

ভুল কোথায়: উপপাদ্য ৪.১ একটি প্রয়োজনীয় শর্ত: code থাকলে অসমতা সত্য। উল্টো দিক (“অসমতা সত্য হলে code আছে”) কোথাও প্রমাণ হয়নি; এটি converse গুলিয়ে ফেলা। সত্যিই এমন code নেই: 0000 নিলে অন্য দুটি codeword-এর weight অন্তত 3, অর্থাৎ 0000 থেকে দূরত্ব ≥ 3, তাই তারা 1110, 1101, 1011, 0111, 1111-এর মধ্যে; এদের যেকোনো দুটির দূরত্ব বড়জোর 2. সব 4-বিট শব্দের brute force-এও সর্বোচ্চ M = 2 আসে (scratch-এ মেলানো)। অস্তিত্বের নিশ্চয়তা চাইলে Gilbert–Varshamov লাগে, আর এখানে তা দেয় 16/V(4, 2) = 16/11, অর্থাৎ M ≥ 2.

(যুক্তিতে “শূন্য শব্দ নিলে” বলা চলে, কারণ যেকোনো code-এর সব শব্দে একই শব্দ x XOR করলে দূরত্ব বদলায় না, আর একটি codeword শূন্য হয়ে যায়।)

৯ · AI-এর যুগে — code-এর হিসাব যাচাই

AI সহকারী Hamming code-এর ধারণা ঠিকঠাক বোঝায়, কিন্তু অবস্থান-গণনা, শর্ত আর সীমার দিকনির্ণয়ে নিয়মিত ভুল করে। কয়েকটি পরিচিত ভুল আর ধরার উপায়:

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

• অবস্থান-গণনা 1 থেকে, আর প্রতিটি একক error-এর syndrome আলাদা
• d, ধরার আর শোধরানোর সংখ্যা উপপাদ্য ৩.৩ দিয়ে নিজে মিলিয়েছি
• সীমার উপপাদ্য “প্রয়োজনীয়” না “যথেষ্ট”, তা গুলিয়ে যায়নি
• সম্ভাবনার সূত্র ছোট n-এ হাতে আর seed-বাঁধা simulation-এ মিলেছে
• ছোট code-এ brute force দিয়ে d আর M নিজে চালিয়ে দেখেছি
• মানদণ্ড, সাল আর নামের দাবি মূল উৎসে মিলিয়েছি

Code-এর হিসাব যাচাই সহজ, কারণ space ছোট হলে সব error-pattern গুনে ফেলা যায়: ৭ বিটে মাত্র 128টি শব্দ। দাবি যত বড়ই হোক, ছোট ক্ষেত্রে পূর্ণ গণনা তাকে পরীক্ষা করতে পারে।