Information Theory Basics — তথ্যের একক কী

আগে এটা বুঝি

একটা বিজ্ঞাপন (এই ধরনের দাবি বাস্তবেই মাঝে মাঝে দেখা যায়):

“আমাদের নতুন কম্প্রেসর যেকোনো ফাইলকে মাত্র ১ বাইটে সংকুচিত করে — নিশ্চিত গ্যারান্টি, ১০০% lossless!”

mathematics/combinatorics-এর pigeonhole principle দিয়েই এটা তাৎক্ষণিকভাবে খণ্ডন করা যায়: n-bit-এর সম্ভাব্য ফাইল আছে 2^nটা। 1-byte আউটপুটের সম্ভাব্য মান মাত্র 256টা। যদি n > 8 হয় (যেকোনো বাস্তব ফাইল), 2^n \> 256 — তাই একাধিক আলাদা ইনপুট ফাইলকে একই ১-বাইট আউটপুটে ম্যাপ করতেই হবে। Decompress করলে কোনটা ফেরত আসবে? দুটো ইনপুটই একরকম compress হলে, decompression কখনোই দুটো আলাদা original ফাইল নির্ভুলভাবে ফেরত দিতে পারবে না। কোনো lossless কম্প্রেসর সব ইনপুটকে সংকুচিত করতে পারে না — কাউকে সংকুচিত করলে কাউকে বড় করতেই হবে।

কিন্তু বাস্তবে zip, gzip, PNG — এগুলো তো সত্যিই কাজ করে, বেশিরভাগ বাস্তব ফাইলে চমৎকার সংকোচন দেয়! তাহলে আসল সীমাটা কোথায়?

উত্তর নির্ভর করে ডেটার statistics-এর উপর — আপনার ডেটা কতটা “predictable”, কতটা “surprising”। ১৯৪৮ সালে Claude Shannon এই সীমাটার সঠিক গাণিতিক সূত্র দিয়েছিলেন — একটা একক সংখ্যা যাকে বলা হয় entropy, যা বলে দেয় একটা ডেটা-উৎস গড়ে কত bit “বহন করে”, আর তাই optimal compression-এর তাত্ত্বিক সীমা ঠিক কোথায়।

মূল ধারণা

Self-information — একটা ঘটনার “বিস্ময়” মাপা

শুরু করি একটা একক ঘটনা দিয়ে। যদি একটা ঘটনা x-এর সম্ভাবনা p(x) হয়, তার self-information (বা “surprisal”):

$I(x) = -\log_2 p(x) \quad \text{একক: bit}$

অন্তর্দৃষ্টি:

p(x) = 1 (নিশ্চিত ঘটনা) ⟹ I(x) = -log₂1 = 0 — কোনো নতুন তথ্য নেই, কারণ আগে থেকেই জানা ছিল কী ঘটবে
p(x) ছোট (বিরল ঘটনা) ⟹ I(x) বড় — একটা বিরল ঘটনা ঘটলে অনেক বেশি “খবর” বহন করে
p(x) = 1/2 ⟹ I(x) = 1 bit — একটা ন্যায্য কয়েনের একটা ফলাফল ঠিক ১ bit তথ্য বহন করে

Shannon Entropy — গড় বিস্ময়

একটা random variable X-এর entropy হলো তার self-information-এর প্রত্যাশিত মান (expectation):

$H(X) = -\sum_{x} p(x) \log_2 p(x) = \mathbb{E}[I(X)]$

এই সূত্রটাই পুরো information theory-র ভিত্তি — mathematics/probability-র expectation ধারণার একটা সরাসরি প্রয়োগ।

চারটা হাতে-হিসাব করা উদাহরণ

১. ন্যায্য কয়েন (p(H)=p(T)=0.5):

$H = -\big(0.5\log_2 0.5 + 0.5\log_2 0.5\big) = -\big(0.5 \cdot (-1) + 0.5\cdot(-1)\big) = 1 \text{ bit}$

সবচেয়ে বেশি সম্ভাব্য entropy একটা দুই-ফলাফলের উৎসের জন্য — সম্পূর্ণ অনিশ্চিত, প্রতিটা ফলাফলে ঠিক ১ bit তথ্য।

২. পক্ষপাতদুষ্ট কয়েন (p(H)=0.9, p(T)=0.1):

$H = -\big(0.9\log_2 0.9 + 0.1\log_2 0.1\big) = -\big(0.9\cdot(-0.152) + 0.1\cdot(-3.322)\big) \approx 0.469 \text{ bit}$

1-এর চেয়ে অনেক কম — কারণ ফলাফল বেশিরভাগ সময় predictable (প্রায় নিশ্চিতভাবেই H), তাই গড়ে কম “নতুন তথ্য” পাওয়া যায়।

৩. ন্যায্য ছয়-পার্শ্বীয় পাশা (p = 1/6 প্রতিটা ফলাফলে):

$H = -\sum_{i=1}^{6} \frac{1}{6}\log_2\frac{1}{6} = \log_2 6 \approx 2.585 \text{ bit}$

৪. চরম ক্ষেত্র — একটা নিশ্চিত ফলাফল (p=1 একটাতে, বাকি সব 0):

$H = -\big(1 \cdot \log_2 1\big) = 0 \text{ bit}$

(0 · log₂0-এর জন্য convention: 0 log 0 = 0, limit হিসেবে, কারণ \lim_{p\to 0} p\log p = 0।)

উৎস	Distribution	H(X) (bit)	ব্যাখ্যা
নিশ্চিত ঘটনা	`p=1` একটাতে	0	কোনো অনিশ্চয়তা নেই
পক্ষপাতদুষ্ট কয়েন	`0.9 / 0.1`	0.469	মোটামুটি predictable
ন্যায্য কয়েন	`0.5 / 0.5`	1.000	সর্বোচ্চ entropy, ২ outcome
ন্যায্য পাশা	`1/6` × ৬	2.585	সর্বোচ্চ entropy, ৬ outcome

Entropy uncertainty-র সাথে বাড়ে — সবচেয়ে বেশি entropy uniform distribution-এ।

মূল ধারণা

Entropy আসলে কী মাপে — Optimal Encoding-এর সীমা

Entropy-র সবচেয়ে গুরুত্বপূর্ণ ব্যাখ্যা: এটা optimal (সবচেয়ে সংক্ষিপ্ত সম্ভাব্য, গড়ে) lossless encoding-এ প্রতি symbol কত bit লাগবে, তার তাত্ত্বিক সীমা।

Source coding theorem (Shannon, 1948)

যেকোনো lossless code-এর গড় codeword-দৈর্ঘ্য L̄-এর জন্য: $\bar{L} \ge H(X)$ আর যথেষ্ট লম্বা block-এ (একাধিক symbol একসাথে এনকোড করলে) H(X)-এর যত কাছে খুশি পৌঁছানো সম্ভব — অর্থাৎ H(X) হলো \inf \bar{L}, achievable একটা সীমা, শুধু তাত্ত্বিক নিম্নসীমা না।

তাৎপর্য — দুই দিক থেকে:

নিম্নসীমা: কোনো clever algorithm এর নিচে গড় bit/symbol নামাতে পারবে না — এটাই আমাদের ইন্ট্রোর pigeonhole যুক্তিটার সূক্ষ্ম, পরিমাণগত সংস্করণ। 2 outcome-এর একটা ৯০/১০ পক্ষপাতদুষ্ট উৎসকে কেউ গড়ে 0.469-এর কম bit/symbol-এ কখনো এনকোড করতে পারবে না, যতই চতুর হোক।
অর্জনযোগ্যতা: entropy কোনো অপ্রাপ্য আদর্শ না — বাস্তব algorithm (Huffman coding, arithmetic coding) তার কাছাকাছি পৌঁছায়।

computer-representation/serialization-binary-formats-এ আমরা দেখেছি fixed-width encoding (যেমন প্রতিটা character-এ ঠিক ৮ bit বরাদ্দ, ASCII-র মতো) কেন অপচয়ী যখন symbol-এর probability uniform না — এখন আমরা জানি ঠিক কতটা অপচয়ী: 8-bit fixed encoding একটা উৎসের জন্য কাজ করে যদি সেই উৎসের entropy 8-এর কাছাকাছি হয় (যেমন uniform random byte), কিন্তু ইংরেজি টেক্সট-এর মতো skewed distribution-এ (কিছু character অনেক বেশি ঘন ঘন আসে — e, t, a) প্রকৃত entropy প্রতি character-এ \approx 4$–$5 bit-এর কাছাকাছি — fixed 8-bit encoding প্রায় দ্বিগুণ জায়গা নষ্ট করছে।

ভেতরে কী ঘটছে

Huffman Coding — Entropy-এর কাছাকাছি পৌঁছানোর একটা construction

Huffman coding একটা greedy algorithm যা symbol-frequency থেকে একটা prefix-free binary code বানায় — কোনো codeword আরেকটার শুরু (prefix) না, তাই delimiter ছাড়াই unambiguous ভাবে decode করা যায়।

Algorithm — সংক্ষেপে

প্রতিটা symbol একটা leaf node, weight = তার frequency/probability
সবচেয়ে কম দুইটা weight-এর node তুলে একটা নতুন parent বানাও, weight = দুইটার যোগফল; parent-কে আবার pool-এ ফেরত দাও
একটা মাত্র tree অবশিষ্ট না থাকা পর্যন্ত repeat করো
Root থেকে leaf পর্যন্ত path (বাম=0, ডান=1) হলো সেই symbol-এর codeword

অন্তর্দৃষ্টি: ঘন ঘন symbol root-এর কাছে থাকে (ছোট path, ছোট codeword), বিরল symbol গভীরে থাকে (বড় path, বড় codeword) — ঠিক -log₂p(x)-এর সাথে সামঞ্জস্যপূর্ণ একটা প্যাটার্ন।

সম্পূর্ণ সাংখ্যিক উদাহরণ

চারটা symbol: A(p=0.5), B(p=0.25), C(p=0.125), D(p=0.125)।

Huffman tree নির্মাণ: সবচেয়ে ছোট দুইটা (C=0.125, D=0.125) মিলে CD(0.25)। এবার সবচেয়ে ছোট দুইটা (B=0.25, CD=0.25) মিলে BCD(0.5)। শেষে (A=0.5, BCD=0.5) মিলে root (1.0)।

ফলাফল codeword: A=0 (1 bit), B=10 (2 bit), C=110 (3 bit), D=111 (3 bit)।

গড় codeword দৈর্ঘ্য:

$\bar{L} = 0.5(1) + 0.25(2) + 0.125(3) + 0.125(3) = 0.5+0.5+0.375+0.375 = 1.75 \text{ bit}$

Entropy তুলনা:

$H = -\big(0.5\log_2 0.5 + 0.25\log_2 0.25 + 0.125\log_2 0.125 + 0.125\log_2 0.125\big)$ $= 0.5(1) + 0.25(2) + 0.125(3) + 0.125(3) = 1.75 \text{ bit}$

L̄ = H — হুবহু মিলে গেল! এই বিশেষ উদাহরণে probability-গুলো সব ঠিক 2-এর ঋণাত্মক পূর্ণসংখ্যা ঘাত (1/2, 1/4, 1/8, 1/8) — তখন Huffman coding ঠিক entropy অর্জন করে, কোনো অপচয় ছাড়াই। সাধারণভাবে (probability যখন 2-এর ঘাত না) Huffman-এর L̄ entropy-র থেকে সামান্য বেশি হয় (প্রমাণযোগ্য: H ≤ L̄ \< H + 1), কিন্তু কখনোই কম না — source coding theorem-এর নিম্নসীমা ভাঙা যায় না।

                    (1.0)
                   /     \
              A(0.5)      (0.5) BCD
              code=0      /        \
                     B(0.25)      (0.25) CD
                     code=10      /          \
                              C(0.125)      D(0.125)
                              code=110      code=111

Huffman tree — frequent symbol root-এর কাছে, rare symbol গভীরে।

বাস্তব ব্যবহার

DEFLATE (zip/gzip-এর ভেতরে, LZ77 dictionary-matching-এর পরের entropy-coding ধাপ হিসেবে), JPEG (DCT quantization-এর পরের ধাপ), MP3 — সবগুলোই তাদের pipeline-এর শেষে একটা Huffman-জাতীয় stage ব্যবহার করে, কারণ আগের ধাপগুলো ডেটাকে ইতিমধ্যে “skewed” (কিছু মান বেশি ঘন ঘন) করে ফেলেছে, আর Huffman সেই skew-কে বাস্তব bit-সাশ্রয়ে রূপান্তর করে। আধুনিক codec (zstd, Brotli) প্রায়ই Huffman-এর বদলে arithmetic/range coding ব্যবহার করে, যা non-integer bit-length-ও এনকোড করতে পারে (Huffman-এর সীমাবদ্ধতা — একটা codeword সবসময় পূর্ণ সংখ্যক bit, তাই p=0.9-এর মতো entropy 0.469-এর কাছাকাছি কখনো পৌঁছাতে পারে না একক-symbol কোডিং-এ; arithmetic coding পারে)।

উদাহরণ

Mutual Information — দুইটা variable কতটা “জড়িত”

দুইটা random variable X, Y-এর মধ্যে mutual information:

$I(X;Y) = H(X) - H(X \mid Y)$

মানে: “Y-কে জানলে X সম্পর্কে অনিশ্চয়তা কতটা কমে।” H(X|Y) (conditional entropy) হলো Y জানা থাকা অবস্থায় X-এর গড় অবশিষ্ট অনিশ্চয়তা।

বৈশিষ্ট্য:

Symmetric: I(X;Y) = I(Y;X) — Y থেকে X সম্পর্কে যা জানা যায়, ঠিক ততটাই X থেকে Y সম্পর্কে জানা যায়
I(X;Y) = 0 ⟺ X, Y স্বাধীন (independent) — একটা জানলে অন্যটা সম্পর্কে কিছুই নতুন জানা যায় না
I(X;Y) সর্বোচ্চ হয় যখন একটা থেকে অন্যটা সম্পূর্ণ নির্ধারিত হয়

ব্যবহারিক প্রয়োগ: feature selection-এ (ML-এ কোন input feature আসলে output predict করতে সাহায্য করে তা মাপা — শুধু linear correlation না, যেকোনো ধরনের সম্পর্ক ধরতে পারে, যা Pearson correlation পারে না)।

Channel Capacity ও Noisy-Channel Coding Theorem

এতক্ষণ আমরা ধরে নিয়েছি ডেটা নিখুঁতভাবে পৌঁছায়। বাস্তবে channel-এ noise থাকে — networking-এর প্রতিটা লিংকে bit flip হতে পারে।

Binary symmetric channel — সরলতম মডেল

প্রতিটা bit পাঠানো হলে, probability p-তে সেটা flip হয়ে যায় (0→1 বা 1→0), বাকি 1-p probability-তে অপরিবর্তিত থাকে।

Channel capacity

$C = \max_{p(x)} I(X;Y)$

— input distribution বেছে নেওয়ার সর্বোচ্চ সম্ভাব্য mutual information, bit/channel-use এককে। এটা একটা channel-এর একটা স্থির, অন্তর্নিহিত ধর্ম (hardware/medium-এর noise level দিয়ে নির্ধারিত)।

Noisy-channel coding theorem (Shannon, 1948)

যদি transmission rate C-এর কম হয়, এমন একটা code (হয়তো অনেক লম্বা block-এর) অস্তিত্বে আছে যা error probability যেকোনো ছোট মানের কাছাকাছি নামাতে পারে। যদি rate C-এর বেশি হয়, নির্ভরযোগ্য যোগাযোগ অসম্ভব, যত চতুর code-ই ব্যবহার করুন না কেন।

এটা আরেকটা চমকপ্রদ ফলাফল — noise থাকা সত্ত্বেও সম্পূর্ণ নির্ভুল (error probability arbitrarily ছোট) যোগাযোগ সম্ভব, যতক্ষণ rate capacity-র নিচে থাকে। মূল্য: বেশি redundancy (কোডিং), যা কার্যকর throughput কিছুটা কমায় কিন্তু error-rate নাটকীয়ভাবে কমায়।

checksum বনাম error-correcting code

networking/ethernet-link-layer-এ আমরা CRC32 (Frame Check Sequence) দেখেছি — এটা corruption সনাক্ত করে (checksum), কিন্তু সংশোধন করে না। যদি CRC ভুল, receiver শুধু frame ফেলে দেয় আর retransmission চায়।

Error-correcting code (Hamming code, Reed-Solomon, LDPC — আধুনিক Wi-Fi, 5G, স্যাটেলাইট যোগাযোগে ব্যবহৃত) অতিরিক্ত redundancy যোগ করে যাতে receiver শুধু error সনাক্ত না, সংশোধনও করতে পারে — retransmission ছাড়াই। এটাই noisy-channel coding theorem-এর সরাসরি প্রকৌশলগত ফলাফল: channel capacity-র নিচে থাকলে, যথেষ্ট redundancy দিয়ে error সংশোধনযোগ্য।

বাস্তব উদাহরণ: Voyager স্পেস প্রোবগুলো বিলিয়ন কিলোমিটার দূর থেকে অত্যন্ত দুর্বল সিগন্যালে (extremely noisy channel) ডেটা পাঠায় — convolutional আর Reed-Solomon coding ব্যবহার করে channel capacity-র কাছাকাছি রেট বজায় রাখে, ৪০ বছরেরও বেশি সময় ধরে।

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

EXPERIMENT

Entropy হিসাব করে ও Huffman code বানিয়ে তত্ত্বকে সংখ্যায় যাচাই করা

Python 3 (কোনো library লাগে না)· ২০ মিনিট

import heapq
import math
from collections import Counter


def entropy(freqs):
    total = sum(freqs.values())
    h = 0.0
    for count in freqs.values():
        p = count / total
        h -= p * math.log2(p)
    return h


def huffman_codes(freqs):
    # heap-এর প্রতিটা entry: (weight, unique_id, symbol_or_None, left, right)
    heap = []
    counter = 0
    for sym, w in freqs.items():
        heapq.heappush(heap, (w, counter, sym, None, None))
        counter += 1

    while len(heap) > 1:
        w1, _, s1, l1, r1 = heapq.heappop(heap)
        w2, _, s2, l2, r2 = heapq.heappop(heap)
        merged = (w1 + w2, counter, None, (w1, s1, l1, r1), (w2, s2, l2, r2))
        heapq.heappush(heap, merged)
        counter += 1

    codes = {}
    def walk(node, prefix):
        w, _, sym, left, right = node
        if sym is not None:
            codes[sym] = prefix or "0"     # একক-symbol edge case
            return
        walk(left, prefix + "0")
        walk(right, prefix + "1")
    walk(heap[0], "")
    return codes


def analyze(name, freqs):
    total = sum(freqs.values())
    h = entropy(freqs)
    codes = huffman_codes(freqs)
    avg_len = sum((freqs[s] / total) * len(codes[s]) for s in freqs)

    print(f"\n{name}")
    print(f"  {'symbol':<8}{'p(x)':>8}{'code':>10}{'len':>6}")
    for s in sorted(freqs, key=lambda s: -freqs[s]):
        p = freqs[s] / total
        print(f"  {s!r:<8}{p:>8.3f}{codes[s]:>10}{len(codes[s]):>6}")
    print(f"  Entropy H(X)      = {h:.4f} bit/symbol")
    print(f"  Huffman avg L̄     = {avg_len:.4f} bit/symbol")
    print(f"  Overhead (L̄ - H)  = {avg_len - h:.4f} bit/symbol")


# উদাহরণ ১ — probability 2-এর ঘাত (Huffman = entropy, হুবহু)
analyze("Powers-of-2 distribution", {"A": 500, "B": 250, "C": 125, "D": 125})

# উদাহরণ ২ — একদম বাস্তব ইংরেজি বর্ণের frequency-র কাছাকাছি একটা toy distribution
analyze("English-এর মতো skewed distribution",
        {"e": 130, "t": 90, "a": 80, "o": 75, "i": 70, "n": 68,
         "s": 63, "h": 60, "r": 60, "z": 1, "q": 1, "x": 2})

# উদাহরণ ৩ — uniform distribution (সর্বোচ্চ entropy, ৮টা symbol)
analyze("Uniform 8-symbol", {chr(65+i): 1 for i in range(8)})

প্রত্যাশিত আউটপুট (সংক্ষিপ্ত, প্রথম আর তৃতীয় উদাহরণ):

Powers-of-2 distribution
  symbol      p(x)      code   len
  'A'        0.500         0     1
  'B'        0.250        10     2
  'C'        0.125       110     3
  'D'        0.125       111     3
  Entropy H(X)      = 1.7500 bit/symbol
  Huffman avg L̄     = 1.7500 bit/symbol
  Overhead (L̄ - H)  = 0.0000 bit/symbol

Uniform 8-symbol
  ...
  Entropy H(X)      = 3.0000 bit/symbol
  Huffman avg L̄     = 3.0000 bit/symbol
  Overhead (L̄ - H)  = 0.0000 bit/symbol

লক্ষ্য করুন: প্রথম আর তৃতীয় উদাহরণে overhead ঠিক 0 — কারণ উভয় ক্ষেত্রেই প্রতিটা probability 2-এর ঋণাত্মক পূর্ণসংখ্যা ঘাত। দ্বিতীয় (skewed, বাস্তব-ঘেঁষা) উদাহরণে overhead সাধারণত ছোট কিন্তু অ-শূন্য — Huffman সেখানে entropy-র কাছাকাছি পৌঁছায়, ঠিক অর্জন করে না, কারণ probability-গুলো 2-এর ঘাত না।

নোট

z, q-এর মতো বিরল symbol-এর codeword length-এর দিকে তাকান — এগুলো সবচেয়ে লম্বা codeword পায় (গভীরতম leaf), ঠিক তাদের বড় self-information (-log₂p)-এর সাথে সামঞ্জস্যপূর্ণ। e-এর মতো ঘন ঘন symbol সবচেয়ে ছোট codeword পায়। এটাই আক্ষরিকভাবে Morse code-এর মূল ডিজাইন-নীতি (E = single dot, Q = দীর্ঘ প্যাটার্ন) — Samuel Morse Shannon-এর ১০০ বছরেরও বেশি আগে, পরিসাংখ্যিক অন্তর্দৃষ্টি দিয়েই একই সিদ্ধান্তে পৌঁছেছিলেন।

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

একটা নির্বিচার symbol-frequency table নিয়ে entropy সূত্র আর Huffman algorithm হাতে-কলমে চালালে দেখা যায় Huffman-এর গড় codeword-দৈর্ঘ্য entropy-র কতটা কাছাকাছি পৌঁছায় — source coding theorem-এর নিম্নসীমা বাস্তবে কীভাবে প্রায়-অর্জিত হয়।

নিজে বানান

BUILD IT

একটা তথ্যের-উৎস 'password strength' মিটার — entropy দিয়ে

Python · ●●○○○

একটা password-এর character-set আর দৈর্ঘ্য থেকে সম্ভাব্য combination সংখ্যা হিসাব করুন
সেই সংখ্যা থেকে মোট entropy (bit) বের করুন — log₂(সম্ভাব্য combination)
বিভিন্ন password policy তুলনা করুন — দৈর্ঘ্য বনাম character-set বৈচিত্র্যের প্রভাব
Cross-entropy loss-এর সাথে সংযোগ ব্যাখ্যা করে একটা মন্তব্য যোগ করুন

Password strength “entropy” (bit-এ) দিয়ে মাপা একটা বাস্তব, প্রতিদিনের information-theory প্রয়োগ — একটা truly random password uniform distribution থেকে আসে (প্রতিটা সম্ভাব্য password সমান সম্ভাব্য), তাই তার entropy সর্বোচ্চ, log₂(\text{মোট সম্ভাব্য password সংখ্যা}) সূত্র সরাসরি প্রযোজ্য।

import math

def password_entropy_bits(length, charset_size):
    """একটা uniform-random password-এর জন্য মোট entropy — bit।"""
    total_combinations = charset_size ** length
    return math.log2(total_combinations)


def crack_time_estimate(entropy_bits, guesses_per_second=1e10):
    """গড়ে অর্ধেক search space চেক করার পরে পাওয়া যায় ধরে নিয়ে।"""
    total_guesses = 2 ** entropy_bits
    seconds = (total_guesses / 2) / guesses_per_second
    years = seconds / (3600 * 24 * 365)
    return years


policies = [
    ("৮ অক্ষর, শুধু lowercase",        8,  26),
    ("৮ অক্ষর, lowercase+digit",       8,  36),
    ("৮ অক্ষর, lower+upper+digit+সিম্বল", 8,  94),
    ("১২ অক্ষর, শুধু lowercase",       12, 26),
    ("১২ অক্ষর, lower+upper+digit+সিম্বল", 12, 94),
    ("চারটা এলোমেলো ডিকশনারি শব্দ (২০০০-শব্দ তালিকা থেকে)", 4, 2000),
]

print(f"{'নীতি':<48}{'entropy (bit)':>15}{'crack সময় (বছর)':>20}")
for name, length, charset in policies:
    if "শব্দ" in name:
        # শব্দ-ভিত্তিক password: charset আসলে "শব্দ-তালিকার আকার", length = কয়টা শব্দ
        h = math.log2(charset ** length)
    else:
        h = password_entropy_bits(length, charset)
    years = crack_time_estimate(h)
    print(f"{name:<48}{h:>15.1f}{years:>20,.2e}")

প্রত্যাশিত আউটপুট-প্যাটার্ন (আনুমানিক):

নীতি                                            entropy (bit)    crack সময় (বছর)
৮ অক্ষর, শুধু lowercase                                   37.6            1.35e-02
৮ অক্ষর, lowercase+digit                                  41.4            1.94e-01
৮ অক্ষর, lower+upper+digit+সিম্বল                          52.4            2.56e+02
১২ অক্ষর, শুধু lowercase                                  56.4            5.94e+03
১২ অক্ষর, lower+upper+digit+সিম্বল                         78.6            2.85e+09
চারটা এলোমেলো ডিকশনারি শব্দ (২০০০-শব্দ তালিকা থেকে)              43.9            1.19e+00

গুরুত্বপূর্ণ পর্যবেক্ষণ: ১২ অক্ষর, শুধু lowercase (entropy 56.4) ৮ অক্ষর, সব character-type (entropy 52.4)-এর চেয়ে বেশি নিরাপদ — যদিও অনেক password-policy শুধু “special character যোগ করুন” জোর দেয়, দৈর্ঘ্য প্রায়ই বেশি কার্যকর, কারণ entropy length × log₂(charset) — দৈর্ঘ্য বাড়ানো linear ভাবে entropy বাড়ায়, আর charset বাড়ানো শুধু log-scale-এ। এই কারণেই XKCD-র বিখ্যাত “correct horse battery staple” পরামর্শ (চারটা এলোমেলো সাধারণ শব্দ) প্রায়ই একটা জটিল ৮-অক্ষরের password-এর চেয়ে শক্তিশালী এবং সহজে মনে রাখার যোগ্য — উপরের টেবিলেই দেখা যাচ্ছে সেটা ৮ অক্ষর সব character-type-এর কাছাকাছি entropy দেয়, সম্পূর্ণ ভিন্ন ব্যবহার-অভিজ্ঞতায়।

Cross-entropy-র দিকে একটা forward-pointer

এই মিটারটা ধরে নেয় password সত্যিই uniform random — বাস্তবে মানুষ predictable password বাছে (password123, qwerty), যার প্রকৃত entropy তাত্ত্বিক সর্বোচ্চের চেয়ে অনেক কম (কারণ probability distribution uniform না, কিছু password অনেক বেশি সম্ভাব্য)। একটা ভালো password-strength model আসলে একটা probability distribution শিখে নেয় (কোন password-প্যাটার্ন মানুষ বেশি ব্যবহার করে) আর সেই distribution-এর সাপেক্ষে entropy মাপে — এটাই ঠিক পরের অনুচ্ছেদে আসা cross-entropy-র ধারণার একটা ঝলক।

নিজে বাড়ান:

একটা real-world leaked-password-frequency dataset (conceptually) ব্যবহার করে actual entropy বনাম theoretical maximum entropy তুলনা করুন
crack_time_estimate-এ rate limiting (যেমন প্রতি সেকেন্ডে ১০টা try, online attack-এর মতো) যোগ করে দেখুন সংখ্যা কতটা বদলায়
Huffman coding function (Experiment section থেকে) ব্যবহার করে একটা password-generator বানান যা ঠিক targeted entropy achieve করে

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

Entropy যেখানে বাস্তবে সিদ্ধান্ত নেয়

লসলেস কম্প্রেশন — zip, gzip, PNG। DEFLATE (LZ77 + Huffman) প্রথমে repetition খুঁজে বের করে (LZ77), তারপর অবশিষ্ট skewed distribution-এ Huffman প্রয়োগ করে। আধুনিক zstd/Brotli আরও কাছে পৌঁছায় entropy-র, arithmetic/range coding দিয়ে।

Video/audio codec — JPEG, MP3, H.264। Transform (DCT) এর পরে quantized coefficient-গুলো highly skewed (বেশিরভাগ ছোট/শূন্য) — সেই skew-এর উপর entropy coding (Huffman বা CABAC) প্রয়োগ করাই চূড়ান্ত compression ধাপ।

নেটওয়ার্ক error correction। networking-এর checksum (CRC, ethernet-link-layer-এ দেখা) আর deep-space/satellite communication-এর Reed-Solomon/LDPC কোডিং — দুইটাই noisy-channel coding theorem-এর প্রকৌশলগত প্রয়োগ, যদিও ভিন্ন লক্ষ্যে (detect-only বনাম correct)। ৫G, Wi-Fi 6 তাদের modulation/coding scheme (MCS) index বেছে নেয় measured channel condition অনুযায়ী — signal দুর্বল হলে বেশি redundant coding (কম কার্যকর rate, কিন্তু বেশি reliable), যা সরাসরি channel capacity-র estimate-এর উপর ভিত্তি করে।

পাসওয়ার্ড ও cryptographic key strength। একটা truly random 256-bit AES key-র entropy ঠিক 256 bit (uniform distribution)। মানুষের বাছা password-এর প্রকৃত entropy তার length-থেকে-পাওয়া তাত্ত্বিক সর্বোচ্চের চেয়ে অনেক কম, কারণ মানুষ predictable প্যাটার্ন বাছে — password strength meter (build section-এ যা বানিয়েছি তার বাস্তব সংস্করণ) এটাই মাপার চেষ্টা করে।

Database/columnar storage compression। Parquet, ORC-এর মতো columnar format প্রতিটা column-এর ডেটা-distribution দেখে ভিন্ন এনকোডিং বেছে নেয় (dictionary encoding কম-cardinality column-এ, run-length encoding repetitive column-এ, bit-packing ছোট-range integer-এ) — মূলত প্রতিটা column-এর entropy অনুমান করে সবচেয়ে কার্যকর representation বেছে নেওয়া।

Machine learning — cross-entropy loss। একটা classifier যখন একটা input-এর জন্য class probability predict করে (q), আর প্রকৃত label distribution p (সাধারণত এক-hot, একটা class-এ 1, বাকিতে 0), তখন training loss প্রায়ই cross-entropy:

$H(p, q) = -\sum_x p(x) \log q(x)$

এটা মাপে মডেলের prediction q প্রকৃত distribution p-থেকে কতটা “দূরে” — q = p হলে cross-entropy H(p)-এর (self-entropy) সমান হয়ে যায়, সর্বনিম্ন সম্ভাব্য মান। Cross-entropy কমানো (gradient descent দিয়ে) মানে মডেলের predicted distribution-কে সত্যিকারের distribution-এর কাছাকাছি আনা — এই module-এরই পরবর্তী “AI/ML foundations” লেসনে এটা বিস্তারিত ফিরে আসবে, যেখানে neural network training-এর গাণিতিক ভিত্তি হিসেবে entropy-র এই সরাসরি প্রয়োগ কেন্দ্রীয় ভূমিকা রাখবে।

Bioinformatics। DNA/protein sequence alignment-এ একটা position-এর “conservation” (কতটা predictable সেই position-এর অক্ষর, বিভিন্ন প্রজাতির মধ্যে) entropy দিয়ে মাপা হয় — কম entropy মানে সেই position বিবর্তনে কম বদলেছে, প্রায়ই functionally গুরুত্বপূর্ণ।

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

“Entropy মাপে একটা নির্দিষ্ট ফাইলের 'সাইজ' — যেমন একটা 1MB ফাইলের একটা নির্দিষ্ট entropy আছে।”

সূক্ষ্ম কিন্তু গুরুত্বপূর্ণ ভুল। Entropy একটা probability distribution/উৎসের ধর্ম, একটা নির্দিষ্ট ফাইলের না। যখন আমরা বলি “এই ফাইলের entropy X”, আসলে বোঝাই “এই ফাইল যে distribution থেকে এসেছে বলে আমরা মডেল করছি, তার entropy X” — একটা assumption-নির্ভর estimate, ফাইলের অন্তর্নিহিত সত্য না।

বাস্তব compressor (zip, gzip) একটা নির্দিষ্ট ফাইলের symbol-frequency থেকে distribution অনুমান করে, তারপর সেই অনুমানের ভিত্তিতে encode করে। দুইটা ভিন্ন কম্প্রেসর একই ফাইলে ভিন্ন সাইজ দিতে পারে, কারণ তাদের distribution-model ভিন্ন (কতটা context/correlation ধরে)।

আরও গভীর সূক্ষ্মতা: এই lesson-এর সূত্রগুলো ধরে নেয় symbol-গুলো IID (independent, identically distributed) — একটা memoryless source। কিন্তু ইংরেজি টেক্সট memoryless না — q-এর পরে প্রায় সবসময় u আসে, যা zeroth-order (একক-character) entropy হিসাব ধরতে পারে না। এই কারণেই gzip (যা LZ77 দিয়ে repetition/context ধরে) একটা naive per-character Huffman encoder-এর চেয়ে অনেক ভালো compression দেয় বাস্তব টেক্সটে — এটা উচ্চতর-order (context-aware) entropy-র কাছাকাছি পৌঁছায়, শুধু single-symbol entropy-র না।

“একটা যথেষ্ট চতুর algorithm দিয়ে যেকোনো ডেটা আরও সংকুচিত করা সবসময় সম্ভব।”

না — এটাই এই lesson-এর ইন্ট্রোর pigeonhole যুক্তির সরাসরি খণ্ডন। কোনো universal lossless compressor নেই যা সব সম্ভাব্য ইনপুট সংকুচিত করে — কাউকে ছোট করলে (pigeonhole অনুযায়ী) কাউকে বড় করতেই হবে। Source coding theorem একই কথা পরিমাণগতভাবে বলে: একটা নির্দিষ্ট distribution-এর জন্য গড় codeword-length H(X)-এর নিচে নামানো অসম্ভব।

এই কারণেই already-compressed ফাইল (যেমন একটা .zip ফাইল বা random noise) আবার compress করলে সাধারণত সাইজ বাড়ে — ইতিমধ্যেই কাছাকাছি entropy-তে পৌঁছে যাওয়া ডেটায় আর redundancy অবশিষ্ট নেই, compressor এর নিজের header/metadata overhead যোগ করে আসলে সাইজ বাড়িয়ে দেয়।

“উচ্চ entropy মানেই 'খারাপ' — বেশি randomness, বেশি বিশৃঙ্খলা।”

প্রসঙ্গ নির্ধারণ করে ভালো/খারাপ, entropy নিজে মূল্য-নিরপেক্ষ একটা সংখ্যা মাত্র।

Cryptographic key-তে উচ্চ entropy কাঙ্ক্ষিত — একটা predictable (কম-entropy) key সহজে guess করা যায়, তাই key generation-এ আমরা সর্বোচ্চ সম্ভাব্য entropy চাই (uniform random bit)।

Compression-এ কম entropy কাঙ্ক্ষিত — কম entropy মানে predictable ডেটা, predictable ডেটা কম bit-এ এনকোডযোগ্য। একটা ভালো compressor আসলে ডেটার observed entropy কমায় না (সেটা ডেটার অন্তর্নিহিত ধর্ম) — বরং সেই ডেটাকে তার প্রকৃত entropy-র কাছাকাছি একটা representation-এ রূপান্তর করে, fixed-width representation-এর অপচয় সরিয়ে।

তাই “উচ্চ entropy” নিজে ভালো বা খারাপ না — key-তে চাই, redundancy-তে চাই না। প্রসঙ্গটাই নির্ধারণ করে কোনটা কাম্য।

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

একটা weighted die-তে p(1)=0.5, p(2)=0.25, p(3)=p(4)=p(5)=p(6)=0.0625 (বাকি চারটা সমান ভাগে)। এই die-এর entropy হিসাব করুন, আর ন্যায্য die-র (log₂6 ≈ 2.585) সাথে তুলনা করুন।

প্রয়োগ

$H = -\Big[0.5\log_2 0.5 + 0.25\log_2 0.25 + 4 \times (0.0625 \log_2 0.0625)\Big]$

প্রতিটা অংশ হিসাব করি:

0.5 log₂0.5 = 0.5 × (-1) = -0.5
0.25 log₂0.25 = 0.25 × (-2) = -0.5
0.0625 log₂0.0625 = 0.0625 × (-4) = -0.25, চারটা মিলিয়ে -1.0

$H = -\big[-0.5 - 0.5 - 1.0\big] = 2.0 \text{ bit}$

তুলনা: weighted die-র entropy 2.0 bit, ন্যায্য die-র 2.585 bit-এর চেয়ে কম — প্রত্যাশিত, কারণ weighted die বেশি predictable (1 অর্ধেক সময় আসবে)। এটা সরাসরি এই lesson-এর মূল নীতির সাথে সামঞ্জস্যপূর্ণ: uniform distribution সর্বোচ্চ entropy দেয়, যেকোনো পক্ষপাত সেটা কমায়।

ব্যবহারিক অর্থ: এই die-এর outcome-গুলো optimal encoding-এ গড়ে মাত্র 2.0 bit/roll লাগবে (fixed 3-bit encoding, ⌈log₂6⌉=3, ব্যবহারের বদলে) — 1 outcome-কে ছোট codeword দিয়ে, বাকিগুলোকে লম্বা codeword দিয়ে (Huffman-এর মতো একটা কোড বানালে)।

Source coding theorem বলে L̄ ≥ H(X)। ব্যাখ্যা করুন কেন এই সীমা “তথ্য হারানো” রোধ করার সাথে সরাসরি যুক্ত — যদি কেউ H(X)-এর নিচে গড় codeword-length দাবি করে একটা lossless encoder বানাতে চায়, ঠিক কী ভেঙে পড়বে?

যুক্তি

প্রতিটা symbol x-কে decode করতে হলে receiver-কে তার codeword থেকে নির্ভুলভাবে x পুনর্গঠন করতে হবে — অর্থাৎ codeword-এর দৈর্ঘ্য কমপক্ষে ততটুকু তথ্য বহন করতে হবে যতটুকু x-কে চিহ্নিত করতে দরকার।

সবচেয়ে দক্ষ (Shannon-optimal) স্কিমে একটা symbol x-এর codeword-এর দৈর্ঘ্য হওয়া উচিত ঠিক তার self-information -log₂p(x)-এর কাছাকাছি — বিরল symbol (কম p(x), বেশি self-information) বেশি bit পায়, ঘন ঘন symbol কম bit পায়। এই বরাদ্দের গড়ই H(X)।

যদি কেউ H(X)-এর নিচে গড় length দাবি করে, তার মানে কিছু symbol-কে তাদের self-information-এর চেয়ে কম bit দেওয়া হচ্ছে। Prefix-free কোডের একটা মৌলিক সীমাবদ্ধতা (Kraft inequality, \sum 2^{-\ell_i} \le 1, যেখানে ℓᵢ হলো i-তম codeword-এর দৈর্ঘ্য) নিশ্চিত করে যে এই “বাজেট” সীমিত — একটা codeword ছোট করলে বাধ্যতামূলকভাবে অন্য কোনো codeword-কে যথেষ্ট লম্বা করতে হবে (বা দুইটা codeword একই prefix share করা শুরু করবে, যা ambiguity তৈরি করে — decoder জানবে না কোথায় একটা codeword শেষ আর পরেরটা শুরু)।

তাই H(X)-এর নিচে গড় length দাবি করা মানে হয় (ক) কিছু codeword-এ ambiguity ঢুকিয়ে ফেলা (আর তখন এটা আর lossless না — decode করলে ভুল বা একাধিক সম্ভাব্য symbol আসতে পারে), অথবা (খ) গাণিতিকভাবে অসম্ভব একটা দাবি করা, যা Kraft inequality-র বিরুদ্ধে যায়। “কম bit

lossless” এই দুইটা একসাথে H(X)-এর নিচে অর্জনযোগ্য না — এই সীমাটাই source coding theorem-এর মূল বিষয়বস্তু।

পাঁচটা symbol: A(p=0.4), B(p=0.2), C(p=0.2), D(p=0.1), E(p=0.1)। Huffman tree হাতে বানান (merge-এর ক্রম দেখান), তারপর গড় codeword length বের করে entropy-র সাথে তুলনা করুন।

প্রয়োগ

Merge ধাপগুলো (সবসময় সবচেয়ে ছোট দুইটা merge করি):

D(0.1) + E(0.1) → DE(0.2)
এখন pool: A(0.4), B(0.2), C(0.2), DE(0.2)। সবচেয়ে ছোট দুইটা — তিনটাই 0.2 (tie, যেকোনো দুইটা বেছে নেওয়া যায়, ফলাফল সমান গড় length দেবে) — ধরি B(0.2) + C(0.2) → BC(0.4)
এখন pool: A(0.4), DE(0.2), BC(0.4)। সবচেয়ে ছোট দুইটা — DE(0.2)
- একটা 0.4 — ধরি DE(0.2) + A(0.4) → ADE(0.6)
শেষে: BC(0.4) + ADE(0.6) → root(1.0)

Codeword বের করা (root থেকে path):

root → BC(0) অথবা ADE(1)
BC → B(00) অথবা C(01)
ADE → DE(10) অথবা A(11)
DE → D(100) অথবা E(101)

তাহলে: A=11 (2 bit), B=00 (2 bit), C=01 (2 bit), D=100 (3 bit), E=101 (3 bit)।

গড় length:

$\bar{L} = 0.4(2) + 0.2(2) + 0.2(2) + 0.1(3) + 0.1(3) = 0.8+0.4+0.4+0.3+0.3 = 2.2 \text{ bit}$

Entropy:

$H = -\big[0.4\log_2 0.4 + 0.2\log_2 0.2 \times 2 + 0.1 \log_2 0.1 \times 2\big]$

$= -\big[0.4(-1.322) + 0.4(-2.322) + 0.2(-3.322)\big] = -\big[-0.529 - 0.929 - 0.664\big] \approx 2.122 \text{ bit}$

তুলনা: L̄ = 2.2, H ≈ 2.122 — খুব কাছাকাছি কিন্তু হুবহু না (overhead ≈ 0.078 bit/symbol), কারণ probability-গুলো 2-এর ঋণাত্মক পূর্ণসংখ্যা ঘাত না (0.4, 0.1 — এগুলো কোনোটাই 1/2, 1/4, 1/8... না)। এটাই সাধারণ ক্ষেত্র — Huffman প্রায় সবসময় entropy-র কাছাকাছি পৌঁছায়, হুবহু অর্জন করে শুধু বিশেষ (power-of-2 probability) ক্ষেত্রে।

I(X;Y) = 0 হওয়ার মানে কী, আর networking-এর প্রেক্ষাপটে এমন একটা বাস্তব উদাহরণ দিন যেখানে দুইটা measurement-এর mutual information প্রায় শূন্য হওয়া প্রত্যাশিত।

যুক্তি

I(X;Y) = H(X) - H(X|Y) = 0 মানে H(X|Y) = H(X) — Y জানার পরেও X সম্পর্কে অনিশ্চয়তা একটুও কমে না। এটা ঠিক তখনই ঘটে যখন X আর Y statistically independent — একটা জানা অন্যটা সম্পর্কে কিছুই বলে না।

Networking উদাহরণ: ধরুন X = একটা নির্দিষ্ট packet-এর TCP sequence number-এর সর্বশেষ bit (parity-জাতীয় কিছু), আর Y = সেই একই মুহূর্তে একটা সম্পূর্ণ ভিন্ন, unrelated network-এ (যেমন একটা ভিন্ন মহাদেশের একটা ISP-র) কোনো ভিন্ন ব্যবহারকারীর ping latency। এই দুইটার মধ্যে গাণিতিকভাবে কোনো কার্যকারণ বা পরিসাংখ্যিক সম্পর্ক নেই — একটা জানলে অন্যটা সম্পর্কে predict করার ক্ষমতা বাড়ে না, তাই I(X;Y) \approx 0।

বিপরীত, non-zero উদাহরণ (তুলনার জন্য): একটা TCP connection-এর RTT (round-trip time) আর সেই connection-এর congestion window size — এই দুইটা সরাসরি সম্পর্কিত (networking/congestion-control-এর AIMD algorithm RTT দেখেই window সমন্বয় করে), তাই তাদের mutual information উল্লেখযোগ্যভাবে বেশি — একটা জানলে অন্যটা সম্পর্কে অনেক কিছু অনুমান করা যায়।

মূল পার্থক্য: mutual information শূন্য মানে কোনো ব্যবহারযোগ্য সম্পর্ক নেই, positive mutual information মানে একটা measurement অন্যটা সম্পর্কে ভবিষ্যদ্বাণীমূলক তথ্য বহন করে — এই ধারণাটাই network diagnostics/anomaly-detection-এ ব্যবহার হয় দুইটা metric আসলেই সম্পর্কিত কি না তা যাচাই করতে, শুধু coincidence কি না তার বিপরীতে।

আপনি একটা IoT sensor network ডিজাইন করছেন — প্রতিটা sensor প্রতি সেকেন্ডে একটা temperature reading পাঠায়, একটা অত্যন্ত dweak/noisy wireless link দিয়ে (limited bandwidth, উচ্চ bit-error-rate)। Entropy, source coding, আর channel capacity-র জ্ঞান ব্যবহার করে ডিজাইনের দুইটা সিদ্ধান্ত justify করুন: (ক) raw reading-এর বদলে পরিবর্তনের পার্থক্য (delta) পাঠানো, (খ) error-correcting code ব্যবহার করা বনাম শুধু checksum + retransmission।

ডিজাইন

(ক) Delta encoding — কেন এটা entropy কমায়:

তাপমাত্রা সাধারণত ধীরে বদলায় — পরপর দুই reading প্রায়ই খুব কাছাকাছি (যেমন 24.1°C থেকে 24.3°C)। যদি raw reading পাঠানো হয়, প্রতিটা মান তুলনামূলকভাবে uniform-এর কাছাকাছি একটা range-এ ছড়ানো থাকতে পারে (উচ্চ entropy, কারণ নির্দিষ্ট কোনো মান বিশেষভাবে predictable না নিজে নিজে)। কিন্তু delta (reading[t] - reading[t-1]) প্রায় সবসময় ছোট (±0.1–0.5°C-এর মতো একটা সংকীর্ণ range-এ কেন্দ্রীভূত) — এই delta-distribution অনেক বেশি skewed/peaked (0-এর কাছাকাছি মান বেশি সম্ভাব্য), তাই তার entropy raw reading-এর চেয়ে উল্লেখযোগ্যভাবে কম।

Source coding theorem অনুযায়ী কম entropy মানে কম গড় bit/reading দরকার optimal encoding-এ — তাই delta + entropy coding (Huffman বা arithmetic) ব্যবহার করলে raw reading-এর তুলনায় উল্লেখযোগ্য bandwidth সাশ্রয় হয়, বিশেষভাবে সেই limited-bandwidth link-এর জন্য গুরুত্বপূর্ণ। এটাই ঠিক real-world sensor telemetry protocol (differential encoding) আর time-series database (delta-of-delta encoding, যেমন Gorilla/Facebook-এর TSDB) যা ব্যবহার করে।

(খ) Error-correcting code বনাম checksum + retransmit:

Channel অত্যন্ত noisy (উচ্চ bit-error-rate) — noisy-channel coding theorem বলে reliable communication তখনও সম্ভব যতক্ষণ transmission rate channel capacity C-র নিচে থাকে, কিন্তু capacity নিজেই noise level অনুযায়ী কম, তাই আমাদের হয় rate কমাতে হবে (কম data পাঠানো) অথবা যথেষ্ট redundancy যোগ করে সেই নিচু capacity-র মধ্যে reliable থাকতে হবে।

Checksum-only + retransmit পদ্ধতিতে (networking-এর সাধারণ TCP-স্টাইল) প্রতিটা corrupted frame আবার পাঠাতে হয় — কিন্তু যদি bit-error-rate বেশি হয়, retransmission-ও একই high-error channel দিয়ে যায়, তাই বারবার fail করতে পারে (retransmission storm), effective throughput severely কমে যেতে পারে — এমনকি প্রতিটা retry-ও উল্লেখযোগ্য probability-তে আবার fail করবে।

Error-correcting code (FEC — forward error correction) প্রতিটা frame-এ অতিরিক্ত redundant bit যোগ করে যাতে receiver স্বাধীনভাবে (retransmission ছাড়াই) নির্দিষ্ট সংখ্যক bit-error সংশোধন করতে পারে — extra bandwidth ব্যয় হয় প্রতিটা frame-এ, কিন্তু retransmission-এর round-trip latency এবং storm-ঝুঁকি এড়ানো যায়। একটা wireless sensor network-এ (যেখানে round-trip retry ব্যয়বহুল — battery drain, latency) এই trade-off প্রায়ই FEC-এর পক্ষে যায়, ঠিক যেভাবে বাস্তব low-power wireless standard (LoRaWAN, Zigbee-এর কিছু mode) FEC ব্যবহার করে।

সংক্ষেপে ডিজাইন সিদ্ধান্ত: delta encoding কমায় কত bit পাঠাতে হবে (source coding-এর প্রশ্ন); FEC নিশ্চিত করে সেই bit-গুলো নির্ভুলভাবে পৌঁছায় একটা noisy channel-এও, retransmission-এর ব্যয় ছাড়া (channel coding-এর প্রশ্ন) — দুইটা সম্পূর্ণ স্বতন্ত্র কিন্তু পরিপূরক তথ্য-তাত্ত্বিক সিদ্ধান্ত, এই lesson-এর দুইটা মূল উপপাদ্য (source coding theorem, noisy-channel coding theorem) সরাসরি প্রয়োগ।

এরপর কী

এই লেসন দিয়ে আমরা এই module-এর “গাণিতিক ভিত্তি” অংশের একটা গুরুত্বপূর্ণ পর্যায় শেষ করলাম — computation-এর সীমা (decidability, complexity), computation-এর মডেল (Hoare logic, lambda calculus, type theory), আর এখন তথ্যের নিজস্ব সীমা (entropy, channel capacity)।

এই সবগুলো ধারণা পরবর্তী লেসনগুলোতে একসাথে মিলবে — “AI/ML foundations from first principles”-এ আপনি দেখবেন cross-entropy loss (এই লেসনের সরাসরি সম্প্রসারণ), gradient-based optimization, আর neural network-এর তাত্ত্বিক ভিত্তি কীভাবে probability আর information theory-র উপর দাঁড়িয়ে। তারপর module-টা একটা ভিন্ন দিকে বাঁক নেবে — তত্ত্ব থেকে গবেষণা-পদ্ধতি-তে: কীভাবে academic paper পড়তে হয়, hypothesis তৈরি করতে হয়, আর নিজের experiment design করে ফলাফল বিশ্বাসযোগ্যভাবে report করতে হয়।

Information Theory Basics — তথ্যের একক কী

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

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

আগে এটা বুঝি

মূল ধারণা

Self-information — একটা ঘটনার “বিস্ময়” মাপা

Shannon Entropy — গড় বিস্ময়

চারটা হাতে-হিসাব করা উদাহরণ

মূল ধারণা

Entropy আসলে কী মাপে — Optimal Encoding-এর সীমা

Source coding theorem (Shannon, 1948)

ভেতরে কী ঘটছে

Huffman Coding — Entropy-এর কাছাকাছি পৌঁছানোর একটা construction

Algorithm — সংক্ষেপে

সম্পূর্ণ সাংখ্যিক উদাহরণ

উদাহরণ

Mutual Information — দুইটা variable কতটা “জড়িত”

Channel Capacity ও Noisy-Channel Coding Theorem

Binary symmetric channel — সরলতম মডেল

Channel capacity

Noisy-channel coding theorem (Shannon, 1948)

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

Entropy হিসাব করে ও Huffman code বানিয়ে তত্ত্বকে সংখ্যায় যাচাই করা

নিজে বানান

একটা তথ্যের-উৎস 'password strength' মিটার — entropy দিয়ে

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

Entropy যেখানে বাস্তবে সিদ্ধান্ত নেয়

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

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

এরপর কী

আরও পড়ুন

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

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

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

◆মূল ধারণাCore concept

Self-information — একটা ঘটনার “বিস্ময়” মাপা

Shannon Entropy — গড় বিস্ময়

চারটা হাতে-হিসাব করা উদাহরণ

◆মূল ধারণাCore concept

Entropy আসলে কী মাপে — Optimal Encoding-এর সীমা

Source coding theorem (Shannon, 1948)

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

Huffman Coding — Entropy-এর কাছাকাছি পৌঁছানোর একটা construction

Algorithm — সংক্ষেপে

সম্পূর্ণ সাংখ্যিক উদাহরণ

▶উদাহরণExample

Mutual Information — দুইটা variable কতটা “জড়িত”

Channel Capacity ও Noisy-Channel Coding Theorem

Binary symmetric channel — সরলতম মডেল

Channel capacity

Noisy-channel coding theorem (Shannon, 1948)

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

Entropy হিসাব করে ও Huffman code বানিয়ে তত্ত্বকে সংখ্যায় যাচাই করা

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

একটা তথ্যের-উৎস 'password strength' মিটার — entropy দিয়ে

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

Entropy যেখানে বাস্তবে সিদ্ধান্ত নেয়

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

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

→এরপর কীNext step

আরও পড়ুন

আগে এটা বুঝি

মূল ধারণা

মূল ধারণা

ভেতরে কী ঘটছে

উদাহরণ

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

নিজে বানান

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

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

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

এরপর কী