Mesafe İkili Uzayda
Richard Hamming'in en ünlü teknik katkısı: hata düzeltme kodları. Arka planında herhangi bir özel koddan daha derinde bir geometrik fikir vardır.
Hamming Mesafesi
İki eşit uzunlukta ikili dizesi olan u ve v için, Hamming mesafesi d(u, v) farklı olan pozisyonları sayar:
``
u = 1 0 1 1 0
v = 1 1 1 0 0
↑ ↑
d(u,v) = 2
``
Bu, d(u,v) ≥ 0; d(u,v) = 0 iff u = v; d(u,v) = d(v,u); d(u,w) ≤ d(u,v) + d(v,w) olan üç metrik axioma karşılar. İkili n-uzayında Hamming mesafesi geçerli bir metrik uzay oluşturur.
Geometri düşük boyutlarda açıkça görüntülenir. Tüm 3-bitsli dizeler, kübün 8 köşesinde yaşar. Kenar-adya köşeler 1 bitte farklıdır; yüzey-diagonal köşeler 2; antipodal köşeler (ör. 000 ve 111) 3 farklıdır.
Hamming Mesafesi Hesaplamak
Hamming ağırlığı wt(v) v'deki 1'leri sayar. Mesafe ağırlıkla XOR aracılığıyla ilişkilendirilir:
d(u, v) = wt(u XOR v)
Örnek: u = 10110, v = 11100. XOR = 01010. Ağırlık = 2. Bu nedenle d(u,v) = 2.
Hata Düzeltme ile Küre Paketlenmesi
Bir ikili kod C, {0,1}^n içindeki seçilen kod kelimelerinden oluşur. Bir kod kelimesi bir kaba iletişimde, bazı bitler tersinebilir. Alıcı, orijinalı geri kazanmak için çöplenmiş bir dize alır.
Bir Hamming topu kod kelimesi etrafındaki yarıçap t ile tanımlayın:
B(c, t) = { v ∈ {0,1}^n : d(c, v) ≤ t }
Hata düzeltme için t hata, her iki kod sözcüğün etrafında B(c, t) olan top topluluklarının kesişmemesi gerekir. Eğer kesişirse, alınan kelime iki top içinde yer alabilir ve decoder hata düzeltme yapılamadığını belirleyemez.
Bir kodun minimum mesafesi d_min her şeyi yönetir:
- d_min − 1 hata tespit edebilir - ⌊(d_min − 1) / 2⌋ hata düzeltebilir
Hamming (7,4) kodu: n = 7 bit, k = 4 veri biti, d_min = 3. 1 hata düzeltir. 2 tanınır.
Ne kadar kod sözcüğü sığar?
n uzunluğundaki bir kodu, hala t hata düzeltmeyi sağlayacak şekilde ne kadar kod sözcüğü barındırabilir? Her kod sözcüğü 'sahip' olduğu t yarıçaplı bir küreyi yönetir. Tüm küreler birlikte {0,1}^n içinde sığmalıdır, bu 2^n nokta içerir.
n uzunluğundaki Hamming kürenin yarıçap t olan hacmi:
Vol(n,t) = Σ_{i=0}^{t} C(n, i)
Hamming bağından (küre paketleme bağından) doğrudan takip edilir: t hata düzeltmeyi sağlayan bir kod
M · Vol(n,t) ≤ 2^n
nokta sayısı M = kod sözcüğü sayısı. Bu yüzden M ≤ 2^n / Vol(n,t).
Hamming (7,4) kodu için: n=7, t=1. Vol(7,1) = C(7,0) + C(7,1) = 1 + 7 = 8. Bağ: M ≤ 128 / 8 = 16. (7,4) kodu M = 2^4 = 16 sağlar: bir mükemmel kod yani küreler {0,1}^7'yi tamamlar ve boşluk bırakmaz.
√n karşılaştırması
Hamming, uzun vadeli görüşün değerini kesinleştirmek için bir rastgele yürüyüş argümanı kullandı. Argüman, 'görüş yardımcı olur' şeklinde bir belirsiz iddiayı, mesafelerle ilgili geometrik bir gerçeklikte dönüştürdü.
Z sembolü üzerinde simetrik rastgele yürüyüş
Her adımda +1 veya -1 eşit olasılıkla hareket et. n adım sonra, başlangıç noktasından beklenen sapma: E[|X_n|] ≈ √n.
Bu, varyansından takip edilir: Var(X_n) = n (her adım bağımsız, her biri ±1 varyans 1). Standart sapma = √n.
Yönlendirilmiş Yürüyüş
Her adımda, +1'e yönelik bir hedefe yatkınlık ile p > 1/2 olasılığıyla hareket et. n adım sonra, beklenen pozisyon: E[X_n] = n(2p−1). p = 1 (tamamen yönlendirilmiş) için: E[X_n] = n.
Karşılaştırma: rastgele sapma √n ölçüsünde; yönlendirilmiş ilerleme n ölçüsünde.
Hamming'in Çevirisi
Araştırmaya adanmış bir kariyerde, her iş günü bir adım temsil eder. Belirsiz bir vizyon olmadan, çalışma birçok yönde sallanır: n gün sonra, net ilerleme ≈ √n. Birleşik uzun vadeli bir vizyonla, çaba hizalanır: n gün sonra, net ilerleme ≈ n. n / √n = √n oranı sınırsız olarak artar.
√n Oranı
Yönlendirilmiş yürüyüş, mükemmel bir hedefe yönelik gerektirmez. Hedefe yönelik bir eğilim, √n sapma yerine n ilerlemeye daha yakın bir şeyle dönüştürür.
Modelin Sınırları
Görüşün 100x çıktısı öngördüğü bir model haklı olarak şüpheyle karşılanır. Modelin kaçınılan bazı şeyleri içerir:
1. Boyutluluk: Kariyerler, ℤ değil, ℝ^d gibi yüksek boyutlu uzaylarda çalışır. Rastgele yürüyüşün geometriği d'nin artmasıyla önemli ölçüde değişir.
2. Korelasyon: Araştırmalar adım adım ilgilidir - bugünkü çalışma dünkü üzerine inşa edilir. Bağımlı adımlarla karşılaştırıldığında, korelasyonlu yürüyüşler farklı şekilde davranır.
3. Görüşün kendisi yanlış olabilir: Yanlış bir çekiciye doğru yönlendirilmiş bir yürüyüş, dalgalanmadan daha kötüdür.
Çiftlenme Süresi
Hamming, teknik bilgilerin yaklaşık olarak her 17 yılda bir çiftlendiğini öne sürdü. Bu iddiaya, eksponansiyel büyümeye dayalı kesin matematik bir yapı vardır.
Eksponansiyel Büyüme Modeli
y(t) = a · e^(b·t)
a = t = 0 olan başlangıç miktarı, b = büyüme oranı (birim zaman başına), e ≈ 2.718.
Çiftlenme süresi D: y'nin ne zaman iki katına çıkacağı zaman.
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 per year için, çiftlenme süresi = 17 yıl.
Yarı Yaşam Süresi
Yarı yaşam süresi H: y'nin değerinin yarısına düşmesine ne kadar zaman aldığı (b < 0).
H = ln(2) / |b|
Aynı formül iki yönde de kullanılır. 5 yıllık ömrü olan bir becerinin, 5 yıl sonra yarı değeri gitmiş. 10 yıl sonra: kalan değer çeyrek. 20 yıl sonra: emtia değerinin %7'den azı kalır.
Bilgi Çiftlenmesi
Eğer teknik bilgi her 17 yılda bir iki katlanır, 22 yaşında mezuniyetle başlayan bir öğrenci, 56 yaşında olan bilgi manzarasını değiştirir - 34 yıllık bir kariyer, iki tam çiftlemeyi kapsar.
Uzmanlık Yarı Ömrü
Eksponansiyel model, düşme için de uygulandığı gibi, belirli bir becerinin (ör. belirli bir çip mimarisine hakim olma, kullanımdan kalkan API, geçmişte kullanılan bir algoritma) zamanla alanın ilerlemesiyle değerini kaybetmesi.
Eğer H = 5 yıl olan özel bir becerinin yarı ömrü, t yıl sonra orijinal değerinin kalan kısmı: f(t) = (1/2)^(t/H) = 2^(-t/H).
Bir yarı ömür (5 yıl) sonra: %50 kalmış. İki yarı ömür (10 yıl): %25. Üç yarı ömür (15 yıl): %12.5. Dört yarı ömür (20 yıl): %6.25.
Hamming'in implication: öğrenme stratejisi üzerinde yatırım yapılan değer, aynı eksende özel bilgi değerini eritenler kadar pozitif olarak katlanır. Probleme çerçevesi ve aktarılabilir düşünme stratejisi yatırımı, yarı ömür döngüleri boyunca değerini korur.
Geometri, Hata Düzeltme ve Kariyer
Bu dersin üç geometrik yapısı ayrılmış gibi görünüyor. Birbirine bağlanıyor.
Hamming mesafesi hata maliyetini formalize eder ve hatalardan kurtulmak için gereken yeterlilikte gereksinimlerini belirtir. Her iletişim sistemi, her kod tabanı, her bilgi kütüphanesi, hataların bütünü bozmasını önlemek için yeterli gereksinimlere sahip olmalıdır.
√n'ye karşı n argümanı vizyonu geometrik bir gerçeğe çevirir: sapma, başlangıç noktasından uzaklık olarak ölçülür, yönlendirilmiş hareket ise hedefe yönelik bir hedefe doğru ilerleme olarak ölçülür. Kariyer stratejisi açısından gereksinim olan gereklilikler - yanlış yönlendirmelere karşı koruma sağlar.
Eksponansiyel büyüme ve azalma hem genişleyen önleyi hem de bugünkü bilgilerin yarı ömrünü yönetir. Stabil yatırım: öğrenme nasıl öğrenildiğini öğrenmek, bu bilgiyi aynı zaman diliminde speküle eden uzmanlık bilgisi erimesi oranında katlanır.