المسافة في الفضاء الثنائي
أشهر مساهمة تقنية لريتشارد هامينج: أكواد تصحيح الأخطاء. الفكرة الهندسية وراءها تتجاوز أي رمز محدد.
مسافة هامينج
بحساب سلسلتي ثنائيتين متساويتي الطول، تحسب مسافة هامينج d(u, v) المواضع التي تختلف فيها:
``
u = 1 0 1 1 0
v = 1 1 1 0 0
↑ ↑
d(u,v) = 2
``
هذا يستوفي جميع البديهيات الثلاث للمتري: d(u,v) ≥ 0؛ d(u,v) = 0 إذا و فقط إذا u = v؛ d(u,v) = d(v,u)؛ d(u,w) ≤ d(u,v) + d(v,w). الفضاء الثنائي n مع مسافة هامينج يشكل فضاء متري صحيح.
تتجسد الهندسة بوضوح في الأبعاد المنخفضة. جميع السلاسل الثنائية ذات 3 بتات تقع عند رؤوس المكعب الثمانية. الرؤوس المجاورة على الحافة تختلف بدقة في 1 بت؛ رؤوس قطر الوجه تختلف في 2؛ الرؤوس المتقابلة (مثل 000 و 111) تختلف في 3.
حساب مسافة هامينج
وزن هامينج wt(v) يحسب عدد 1 في v. ترتبط المسافة بالوزن عبر XOR:
d(u, v) = wt(u XOR v)
مثال: u = 10110, v = 11100. XOR = 01010. الوزن = 2. إذن d(u,v) = 2.
تصحيح الأخطاء عبر تجميع المجالات
يتكون الرمز الثنائي C ⊆ {0,1}^n من رموز مختارة. عندما ينقل رمز على قناة مشوشة، قد تنقلب بعض البتات. يستقبل المتلقي سلسلة تالفة ويجب عليه استعادة الأصل.
عرّف كرة هامينج بنصف قطر t مركزها رمز c:
B(c, t) = { v ∈ {0,1}^n : d(c, v) ≤ t }
لتصحيح حتى t أخطاء، يجب ألا تتقاطع الكرات B(c, t) حول كل زوج رموز. إذا تقاطعت، قد تقع كلمة مستقبلة في كرتين والمفكك لا يستطيع تحديد أي رمز أُرسل.
تحكم المسافة الدنيا d_min للرمز كل شيء:
- الكشف عن حتى d_min − 1 أخطاء - تصحيح حتى ⌊(d_min − 1) / 2⌋ أخطاء
رمز هامينج (7,4): n = 7 بتات، k = 4 بتات بيانات، d_min = 3. يصحح خطأ واحد. يكشف 2.
كم رمز يناسب؟
كم رمز يمكن أن يحتويه رمز طول n بينما يصحح تصحيح أخطاء t؟ كل رمز 'يمتلك' كرة بنصف قطر t. يجب أن تناسب جميع الكرات معاً داخل {0,1}^n، والتي تحتوي على 2^n نقطة.
حجم كرة هامينج بنصف قطر t في {0,1}^n:
Vol(n,t) = Σ_{i=0}^{t} C(n, i)
يتبع حد هامينج (حد تجميع المجالات) مباشرة: رمز يصحح t أخطاء يستوفي
M · Vol(n,t) ≤ 2^n
حيث M = عدد الرموز. إذن M ≤ 2^n / Vol(n,t).
لرمز هامينج (7,4): n=7, t=1. Vol(7,1) = C(7,0) + C(7,1) = 1 + 7 = 8. الحد: M ≤ 128 / 8 = 16. يحقق رمز (7,4) M = 2^4 = 16: رمز كامل، يعني أن الكرات تغطي {0,1}^7 بدون فراغات.
√n مقابل n
استخدم هامينج حجة المشي العشوائي لجعل قيمة الرؤية طويلة المدى دقيقة. تحول الحجة الدعوى الغامضة — 'الرؤية تساعد' — إلى حقيقة هندسية عن المسافات.
المشي العشوائي المتماثل على ℤ
في كل خطوة، تحرك +1 أو −1 بنسبة متساوية. بعد n خطوة، الإزاحة المتوقعة من الأصل: E[|X_n|] ≈ √n.
هذا يتبع من التباين: Var(X_n) = n (الخطوات مستقلة، كل منها ±1 تباين 1). الانحراف المعياري = √n.
المشي الموجه
في كل خطوة، تحرك +1 باحتمال p > 1/2 (انحياز نحو هدف). بعد n خطوة، الموضع المتوقع: E[X_n] = n(2p−1). لـ p = 1 (موجه بالكامل): E[X_n] = n.
التباين: الانجراف العشوائي يتسع كـ √n؛ التقدم الموجه يتسع كـ n.
ترجمة هامينج
في مسيرة البحث، يمثل كل يوم عمل خطوة واحدة. بدون رؤية واضحة لما يهم، ينجرف العمل في اتجاهات عديدة: بعد n يوم، التقدم الصافي ≈ √n. برؤية متماسكة طويلة المدى، ينحاز الجهد: بعد n يوم، التقدم الصافي ≈ n. النسبة n / √n = √n تنمو بدون حد.
نسبة √n
لا يتطلب المشي الموجه هدفاً مثالياً. أي انحياز مستمر نحو هدف يحول انجراف √n إلى شيء أقرب إلى تقدم n.
حدود النموذج
نموذج يتنبأ بـ 100x المخرجات من الرؤية يستحق الفحص. عدة أشياء يحذفها:
1. البعدية: المسيرات تعمل في فضاء عالي الأبعاد، وليس ℤ. تتغير هندسة المشي العشوائي بشكل كبير مع d.
2. الارتباط: خطوات البحث مرتبطة — عمل اليوم يبني على عمل الأمس. المشي المترابط يتصرف بشكل مختلف عن الخطوات المستقلة.
3. قد تكون الرؤية خاطئة: مشي موجه نحو جاذب خاطئ أسوأ من الانجراف.
وقت المضاعفة
فتح هامينج دورته بادعاء أن المعرفة التقنية تتضاعف تقريباً كل 17 سنة. هذا الادعاء له بنية رياضية دقيقة: النمو الأسي.
نموذج النمو الأسي
y(t) = a · e^(b·t)
حيث a = الكمية الأولية عند t = 0, b = معدل النمو (لكل وحدة زمن), e ≈ 2.718.
وقت المضاعفة D: الوقت الذي يتضاعف فيه y.
2a = a · e^(b·D) → 2 = e^(b·D) → ln(2) = b·D → D = ln(2) / b
ln(2) ≈ 0.693. لـ b = 0.693/17 ≈ 0.0408 في السنة، وقت المضاعفة = 17 سنة.
نصف العمر
نصف العمر H: الوقت الذي ينخفض فيه y إلى نصف قيمته (b < 0).
H = ln(2) / |b|
نفس الصيغة في كلا الاتجاهين. مهارة بنصف عمر 5 سنوات: بعد 5 سنوات، نصف قيمتها السوقية اختفى. بعد 10 سنوات: يبقى ربع. بعد 20 سنة: أقل من 7% يبقى.
مضاعفة المعرفة
إذا كانت المعرفة التقنية تتضاعف كل 17 سنة، يواجه الطالب الذي تخرج في سن 22 منظراً معرفياً متحولاً بحلول سن 56 — تمتد مسيرة 34 سنة عبر مضاعفتين كاملتين.
نصف عمر الخبرة
ينطبق نفس النموذج الأسي على الاضمحلال. تفقد مهارة محددة (مثلاً إتقان معمارية شريحة معينة، واجهة برمجية مستهلكة، خوارزمية متجاوزة) قيمتها بمرور الوقت مع تقدم الحقل.
إذا كان نصف عمر مهارة متخصصة H = 5 سنوات، ثم بعد t سنة الكسر من القيمة الأصلية الباقية: f(t) = (1/2)^(t/H) = 2^(−t/H).
بعد نصف عمر واحد (5 سنوات): 50% باقٍ. نصفا عمر (10 سنوات): 25%. ثلاثة (15 سنة): 12.5%. أربعة (20 سنة): 6.25%.
مضمون هامينج: تتضاعف قيمة التعلم كيف تتعلم بإيجابية مع نفس الأس الذي تتحلل فيه المعرفة المتخصصة. الاستثمار في استراتيجية التعلم وإطار المشاكل و المنطق القابل للنقل يحافظ على القيمة عبر دورات نصف العمر.
الهندسة، تصحيح الأخطاء، & المسيرة
تبدو الهياكل الهندسية الثلاثة من هذا الدرس منفصلة. إنها تتصل.
مسافة هامينج تشكل تكلفة الخطأ و الزيادة المطلوبة للتعافي منه. كل نظام اتصال، كل مجموعة أكواد، كل جسم معرفة يحتاج زيادة كافية بحيث الأخطاء المفردة لا تفسد الكل.
حجة √n مقابل n تترجم الرؤية إلى حقيقة هندسية: يتسع الانجراف كمسافة من نقطة البداية، الحركة الموجهة تتسع كإزاحة نحو هدف. الزيادة في إستراتيجية المسيرة — إبقاء عدة خطوط تحقيق مفتوحة — تحمي من الانعطافة الخاطئة العرضية.
النمو الأسي و الاضمحلال يحكمان كل من الحدود الموسعة و نصف عمر ما تعرفه اليوم. الاستثمار الثابت الوحيد: التعلم كيف تتعلم، الذي يتضاعف على نفس الجدول الزمني الذي تتحلل فيه المعرفة المتخصصة.