1. مقدمة: معجزتان هندسيتان يوميتان لإحياء المعلومات الرقمية

سواء في أعماق الفضاء بين النجوم أو أمام كاميرا هاتفك الذكي، تحقق الهندسة الرقمية الحديثة يومياً ما يبدو وكأنه يتحدى الحدس الفيزيائي: إعادة بناء المعلومات الرقمية بدقة 100% بتاً تلو الآخر من إشارات أو وسائط تعرضت للتشويه الشديد بسبب الضجيج الحراري أو التلف المادي.

المعجزة الأولى: فوياجر 1 و2 يرسلان صوراً عبر 24 مليار كيلومتر بقدرة $10^{-16}\text{ واط}$

انطلقت مركبتا فوياجر 1 وفوياجر 2 (Voyager 1 & 2) عام 1977 لتصوير المشتري وزحل وأورانوس ونبتون، وتبحران اليوم في الفضاء بين النجوم على بُعد يتجاوز 24 مليار كيلومتر من الأرض. يعمل جهاز الإرسال اللاسلكي على متن فوياجر بقدرة $23\text{ واط}$ فقط — أي أقل من مصباح ثلاجة منزلي. وعندما تصل هذه الموجة إلى هوائيات شبكة الفضاء العميق (DSN) التابعة لناسا بقطر 70 متراً على الأرض، تكون القدرة المستقبلة قد تضاءلت إلى نحو $10^{-16}\text{ واط}$ ($0.1\text{ أتواط}$)، غارقةً بالكامل في الضجيج الحراري (Thermal Noise). ومع ذلك، أرسلت فوياجر صوراً ملونة فائقة النقاء بصفر من أخطاء البتات.

المعجزة الثانية: رمز QR مغطى بنسبة $30\%$ ببقعة قهوة أو شعار شركة

وبالمثل، عندما توجه كاميرا هاتفك نحو رمز استجابة سريعة (QR Code) لطخته القهوة أو غطى شعار تجاري ما يصل إلى $30\%$ من مساحته الوسطى، يستعيد هاتفك الرابط أو بيانات الدفع في أقل من $10\text{ مللي ثانية}$ مع صفر أخطاء في البتات (Zero Bit Errors).

  flowchart TD
    subgraph Voyager["اتصالات الفضاء العميق (فوياجر 1 و2)"]
        V1["بيانات صورة الكوكب (k بت)"] --> V2["ترميز متسلسل (كود RS خارجي + كود تلافيفي/LDPC داخلي)"]
        V2 --> V3["مرسل 23 واط عبر مليارات الكيلومترات (استقبال 10⁻¹⁶ واط)"]
        V3 --> V4["ضجيج غاوسي أبيض (AWGN) وانقلاب البتات"]
        V4 --> V5["فك تشفير فيتربي الناعم / انتشار المعتقد + ريد-سولومون"]
        V5 --> V6["صورة كوكبية فائقة الوضوح (صفر أخطاء)"]
    end
    subgraph QR["المسح اليومي السريع لرموز QR"]
        Q1["الرابط / البيانات (k بايت)"] --> Q2["ترميز ريد-سولومون على حقل GF(2⁸) (n بايت)"]
        Q2 --> Q3["بقعة قهوة أو شعار يتلف 30% من الوحدات"]
        Q3 --> Q4["حساب المتلازمات + خوارزمية بيرليكامب-ماسي"]
        Q4 --> Q5["بحث تشين + صيغة فورني (10 مللي ثانية)"]
        Q5 --> Q6["إعادة بناء البيانات بدقة 100%"]
    end

كيف يكون ذلك ممكناً رياضياً؟ تكمن الإجابة في نظرية المعلومات لكلود شانون (1948) والجبر المجرد لرموز تصحيح الأخطاء (Error-Correcting Codes, ECC).

2. ثورة كلود شانون (1948) ومبرهنة ترميز القناة المشوشة

2.1 لماذا يفشل ترميز التكرار الساذج ($0 \to 00000$)

عندما $n \to \infty$، فإن $P_e^{(n)} \to 0$، لكن في الوقت نفسه ينهار معدل الكود إلى الصفر: $R = k/n = 1/n \to 0$.

2.2 مبرهنة شانون وحد شانون النهائي ($-1.59\,\text{dB}$)

في عام 1948، أثبت كلود شانون في بحثه الشهير “A Mathematical Theory of Communication” مبرهنة ترميز القناة المشوشة:

مبرهنة (ترميز القناة المشوشة لشانون، 1948): لكل قناة عديمة الذاكرة سعة قناة موجبة $C > 0$ تحددها خصائص الضجيج:

• للقناة الثنائية المتماثلة (BSC) مع دالة الإنتروبيا الثنائية $H_2(p) = -p\log_2 p - (1-p)\log_2(1-p)$: $$C_{\text{BSC}}(p) = 1 - H_2(p) = 1 + p\log_2 p + (1-p)\log_2(1-p) \quad [\text{bits / channel use}]$$
• لقناة الضجيج الغاوسي الأبيض المضاف (AWGN) بعرض نطاق $B$ وقدرة إشارة $S$ وضجيج $N = N_0 B$ (مبرهنة شانون-هارتلي): $$C_{\text{AWGN}} = B \log_2\!\left(1 + \frac{S}{N}\right) = B \log_2\!\left(1 + \frac{S}{N_0 B}\right) \quad [\text{bits / s}]$$

لأي معدل إرسال $R < C$، توجد أكواد كتلية بطول $n \to \infty$ تجعل احتمال خطأ فك التشفير صغيراً إلى أقصى حد مطلوب ($P_e \to 0$)!

3. الاختراق الهندسي لريتشارد هامينغ (1950): مسافة هامينغ والكود التام $[7, 4, 3]$

3.1 مسافة هامينغ $d_H(\mathbf{u}, \mathbf{v})$ وحد تعبئة الكرات

لكود $\mathcal{C} \subset \mathbb{F}_q^n$ ذي مسافة دنيا $d_{\min} = \min_{\mathbf{u}\neq\mathbf{v}} d_H(\mathbf{u},\mathbf{v})$، تثبت هندسة كرات هامينغ غير المتقاطعة ذات نصف القطر $t$ قدرة الكود على:

• اكتشاف $d_{\min} - 1$ من الأخطاء؛
• تصحيح $e = d_{\min} - 1$ من المحو (Erasures) في مواقع معروفة؛
• تصحيح $t = \lfloor(d_{\min} - 1)/2\rfloor$ من الأخطاء العشوائية في مواقع غير معروفة: $$\mathbf{d_{\min} \ge 2t + e + 1}, \qquad |\mathcal{C}| \cdot \sum_{i=0}^{t} \binom{n}{i} (q-1)^i \le q^n \quad \text{(حد هامينغ)}$$

3.2 كود هامينغ التام $(7,4)$ وفك التشفير بالمتلازمة (Syndrome Decoding)

متجه المتلازمة ذو 3 بتات $\mathbf{s} = \mathbf{H}\mathbf{y}^T = \mathbf{H}(\mathbf{c} + \mathbf{e})^T = \mathbf{H}\mathbf{e}^T \pmod 2$ يستخرج مباشرة عمود المصفوفة $\mathbf{H}$ المقابل للبت المنقلب: فعند ترتيب الأعمدة ثنائياً من $1$ إلى $7$، تعطي المتلازمة $\mathbf{s}$ مباشرةً الفهرس الثنائي $(1 \dots 7)$ للبت التالف! وتحمي هذه الدائرة اليوم جميع ذواكر الخوادم ECC DRAM.

4. تحفة ريد وسولومون (1960): أكواد ريد-سولومون على حقول غالوا $\mathbb{F}_{2^m}$

4.1 حقول غالوا $\text{GF}(2^8)$ ومناعة ضد الأخطاء الانفجارية (Burst Errors)

للتغلب على الأخطاء المتتابعة (خدوش الأقراص، بقع رموز QR)، جمع إيرفينغ ريد وغوستاف سولومون (1960) كل بايت ($m=8$ بتات) كرمز واحد في حقل غالوا المنتهي $\text{GF}(2^8) = \mathbb{F}_2[x]/(x^8 + x^4 + x^3 + x^2 + 1)$. حتى لو تلفت البتات الثمانية داخل بايت واحد، فإن ذلك يُعد في $\text{GF}(2^8)$ خطأً في رمز واحد فقط!

4.2 استيفاء كثيرات الحدود وتحقيق حد سينغلتون MDS ($d_{\min} = n - k + 1$)

وهكذا، تسمح $n - k$ بايتات تكافؤ باستعادة ما يصل إلى $e = n - k$ من المحو (RAID-6 والتخزين السحابي) أو تصحيح ما يصل إلى $t = \lfloor(n-k)/2\rfloor$ من أخطاء البايتات غير معروفة الموقع (رموز QR حتى 30% في المستوى H؛ وكود $[255, 223]$ في فوياجر) باستخدام كثيرة الحدود المولدة $g(x) = \prod_{i=1}^{2t}(x - \alpha^i)$، وخوارزمية بيرليكامب-ماسي / إقليدس ($\Lambda(x)S(x) \equiv \Omega(x) \pmod{x^{2t}}$)، وبحث تشين، وصيغة فورني.

5. الاقتراب من حد شانون: أكواد LDPC (1962) وTurbo (1993) والأكواد القطبية Polar (2009)

1. أكواد LDPC لروبرت غالاغر (1962): تستخدم مصفوفة تكافؤ متناثرة $\mathbf{H}$ ومخطط تانر ثنائي التجزئة (Tanner Graph). عبر التبادل التكراري لنسب الأرجحية اللوغاريتمية الناعمة $L(c_i) = \ln\frac{P(c_i=0|y_i)}{P(c_i=1|y_i)}$ بواسطة انتشار المعتقد (Belief Propagation / Sum-Product)، تقترب أكواد LDPC إلى مسافة $0.0045\,\text{dB}$ فقط من حد شانون (قنوات بيانات 5G NR، وWi-Fi 6/7، وأقراص 3D NAND SSD).
2. الأكواد القطبية لإردال أريكان (Polar Codes, 2009): بتطبيق تحويل كرونيكر $\mathbf{G}_N = \mathbf{B}_N \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}^{\otimes m}$ تكرارياً، يؤدي استقطاب القناة (Channel Polarization) عند $N \to \infty$ إلى تقارب نسبة $C = I(W)$ من القنوات الفرعية نحو السعة $1$ (خالية من الضجيج، تحمل بتات المعلومات) ونسبة $1 - C$ نحو السعة $0$ (البتات المجمدة / Frozen Bits $= 0$)، لتكون أول أكواد بتعقيد $O(N \log N)$ تحقق سعة شانون ببرهان رياضي صارم (قنوات التحكم في 5G NR).

  flowchart TD
    subgraph CapAR["الأكواد الحديثة التي تبلغ سعة شانون"]
        L1["أكواد LDPC (مخطط تانر ثنائي التجزئة المتناثر)"] --> L2["تبادل تكراري لرسائل LLR الناعمة"]
        L2 --> L3["انتشار المعتقد Sum-Product (على بعد 0.0045 dB من حد شانون)"]
        P1["الأكواد القطبية Polar (تحويل كرونيكر G_N = B_N F^{⊗m})"] --> P2["استقطاب القناة إلى W⁻ (متدهورة) و W⁺ (محسنة)"]
        P2 --> P3["نسبة C ← سعة 1 (بتات بيانات)، نسبة 1-C ← سعة 0 (بتات مجمدة)"]
    end

جدول مقارنة شامل لعائلات رموز تصحيح الأخطاء

6. تطبيق بايثون الكامل: كود هامينغ $(7,4)$ وريد-سولومون على $\text{GF}(2^8)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

from typing import List

def hamming74_demo() -> None:
    G = [[1,0,0,0,1,1,0], [0,1,0,0,1,0,1], [0,0,1,0,0,1,1], [0,0,0,1,1,1,1]]
    H = [[1,1,0,1,1,0,0], [1,0,1,1,0,1,0], [0,1,1,1,0,0,1]]
    msg = [1, 0, 1, 1]
    c = [sum(msg[i] * G[i][j] for i in range(4)) % 2 for j in range(7)]
    y = c.copy()
    y[2] ^= 1
    s = [sum(H[r][col] * y[col] for col in range(7)) % 2 for r in range(3)]
    err_idx = next(col for col in range(7) if [H[r][col] for r in range(3)] == s)
    y[err_idx] ^= 1
    print(f"[Hamming (7,4)] Syndrome={s} -> Flipped idx={err_idx}, Recovered={y[:4] == msg}")

class GF256:
    def __init__(self, poly: int = 0x11D) -> None:
        self.exp, self.log = [0] * 512, [0] * 256
        v = 1
        for i in range(255):
            self.exp[i] = self.exp[i + 255] = v
            self.log[v] = i
            v <<= 1
            if v & 0x100:
                v ^= poly

    def mul(self, a: int, b: int) -> int:
        return 0 if (a == 0 or b == 0) else self.exp[self.log[a] + self.log[b]]

    def inv(self, a: int) -> int:
        return self.exp[255 - self.log[a]]

    def power(self, a: int, p: int) -> int:
        return 1 if p == 0 else (0 if a == 0 else self.exp[(self.log[a] * p) % 255])

    def eval_poly(self, coeffs: List[int], x: int) -> int:
        res = 0
        for c in reversed(coeffs):
            res = self.mul(res, x) ^ c
        return res

    def solve(self, A: List[List[int]], b: List[int]) -> List[int]:
        n = len(b)
        M = [row[:] + [b[i]] for i, row in enumerate(A)]
        for col in range(n):
            piv = next(r for r in range(col, n) if M[r][col] != 0)
            M[col], M[piv] = M[piv], M[col]
            inv_p = self.inv(M[col][col])
            for j in range(col, n + 1):
                M[col][j] = self.mul(M[col][j], inv_p)
            for r in range(n):
                if r != col and M[r][col] != 0:
                    f = M[r][col]
                    for j in range(col, n + 1):
                        M[r][j] ^= self.mul(f, M[col][j])
        return [M[i][n] for i in range(n)]

def rs_demo() -> None:
    gf = GF256()
    text = "VOYAGER-1"
    k, t = len(text), 3
    n = k + 2 * t
    pts = [gf.exp[i] for i in range(n)]
    cw = [gf.eval_poly([ord(c) for c in text], x) for x in pts]
    rx = cw.copy()
    rx[1] ^= 0xFF; rx[6] ^= 0xA5; rx[13] ^= 0x3C
    A = [[gf.power(pts[i], d) for d in range(k + t)] + [gf.mul(rx[i], gf.power(pts[i], d)) for d in range(t)] for i in range(n)]
    b = [gf.mul(rx[i], gf.power(pts[i], t)) for i in range(n)]
    sol = gf.solve(A, b)
    E = sol[k + t:] + [1]
    err_pos = [i for i, x in enumerate(pts) if gf.eval_poly(E, x) == 0]
    valid = [(pts[i], rx[i]) for i in range(n) if i not in err_pos][:k]
    rec = gf.solve([[gf.power(x, d) for d in range(k)] for x, _ in valid], [y for _, y in valid])
    print(f"[RS(15,9) over GF(2^8)] Located Errors={err_pos}, Recovered='{''.join(chr(c) for c in rec)}'")

if __name__ == "__main__":
    hamming74_demo()
    rs_demo()

7. خاتمة

من حد شانون $-1.59\,\text{dB}$ (1948) إلى هندسة هامينغ (1950)، واستيفاء كثيرات الحدود لريد-سولومون على حقول غالوا $\mathbb{F}_{2^m}$ (1960)، وصولاً إلى انتشار المعتقد في LDPC واستقطاب القنوات لدى أريكان — تُجسد نظرية الترميز انتصار الرياضيات البحتة على الضجيج الحراري والإنتروبيا الفيزيائية للكون.