Jarak dalam Ruang Biner
Kontribusi teknis Richard Hamming yang paling terkenal: kode koreksi kesalahan. Ide geometris di balik mereka lebih dalam daripada kode apa pun.
Jarak Hamming
Diberikan dua string biner sepanjang yang sama, jarak Hamming d(u, v) menghitung posisi di mana mereka berbeda:
``
u = 1 0 1 1 0
v = 1 1 1 0 0
↑ ↑
d(u,v) = 2
``
Ini memuati semua tiga axiom metrik: d(u,v) ≥ 0; d(u,v) = 0 jika dan hanya jika u = v; d(u,v) = d(v,u); d(u,w) ≤ d(u,v) + d(v,w). n-bidang biner dengan jarak Hamming membentuk ruang metrik yang valid.
Geometri dapat dilihat dengan jelas dalam dimensi rendah. Semua 3-bit string hidup di 8 titik sudut kubus. String titik tetangga di sepanjang tepi berbeda dalam 1 bit; string titik diagonal wajah berbeda dalam 2; string titik antipodal (mis. 000 dan 111) berbeda dalam 3.
Menghitung Jarak Hamming
Berat Hamming wt(v) menghitung jumlah 1 dalam v. Jarak berkaitan dengan berat melalui XOR:
d(u, v) = wt(u XOR v)
Contoh: u = 10110, v = 11100. XOR = 01010. Berat = 2. Jadi d(u,v) = 2.
Koreksi Kesalahan melalui Pemasakan Bola
Sebuah kode biner C ⊆ {0,1}^n terdiri dari codeword yang dipilih. Ketika codeword mengirimkan melalui saluran bising, beberapa bit mungkin berganti.
Definisikan lingkaran Hamming dari jari-jari t yang berpusat pada codeword c:
B(c, t) = { v ∈ {0,1}^n : d(c, v) ≤ t }
Untuk memperbaiki hingga t kesalahan, bola B(c, t) di sekitar setiap pasang kata kunci tidak boleh saling tumpang tindih. Jika mereka tumpang tindih, sebuah kata kunci yang diterima mungkin terletak di dua bola dan decoder tidak dapat menentukan kata kunci yang dikirimkan.
Jarak minimum d_min dari sebuah kode mengatur segalanya:
- Deteksi hingga d_min − 1 kesalahan - Perbaiki hingga ⌊(d_min − 1) / 2⌋ kesalahan
Kode Hamming (7,4): n = 7 bit, k = 4 bit data, d_min = 3. Dapat memperbaiki 1 kesalahan. Deteksi 2.
Berapa Banyak Kata Kunci yang Bisa Masuk?
Berapa banyak kata kunci yang dapat diisi dalam kode panjang-n sambil memperbaiki t kesalahan? Setiap kata kunci 'miliki' bola dengan jari-jari t. Semua bola bersama harus masuk ke dalam {0,1}^n, yang memiliki 2^n titik.
Volume dari bola Hamming dengan jari-jari t di {0,1}^n:
Vol(n,t) = Σ_{i=0}^{t} C(n, i)
Batas Hamming (batas pengemasan bola) langsung mengikuti: sebuah kode yang dapat memperbaiki t kesalahan harus memenuhi
M · Vol(n,t) ≤ 2^n
di mana M = jumlah kata kunci. Jadi M ≤ 2^n / Vol(n,t).
Untuk kode Hamming (7,4): n=7, t=1. Vol(7,1) = C(7,0) + C(7,1) = 1 + 7 = 8. Batas: M ≤ 128 / 8 = 16. Kode (7,4) mencapai M = 2^4 = 16: sebuah kode sempurna, artinya bola-bola tersebut mengisi {0,1}^7 tanpa ruang yang tidak terpakai.
√n vs n
Hamming menggunakan argumen jalan acak untuk membuat nilai visi jangka panjang menjadi tepat. Argumen itu mengonversi klaim yang kabur — 'visi membantu' — menjadi fakta geometri tentang jarak.
Jalan Acak Simetri di ℤ
Setiap langkah, pindah +1 atau −1 dengan probabilitas sama. Setelah n langkah, diharapkan penggeseran dari asal: E[|X_n|] ≈ √n.
Ini mengikuti varian: Var(X_n) = n (langkah independen, masing-masing ±1 varian 1). Deviasi standar = √n.
Jalan Terarah
Setiap langkah, pindah +1 dengan probabilitas p > 1/2 (biaskan ke tujuan). Setelah n langkah, posisi diharapkan: E[X_n] = n(2p−1). Untuk p = 1 (sangat terarah): E[X_n] = n.
Kontras: goyangan acak berkembang sebanding dengan √n; kemajuan terarah berkembang sebanding dengan n.
Penerjemahan Hamming
Dalam karier penelitian, setiap hari bekerja mewakili satu langkah. Tanpa visi jangka panjang yang jelas, pekerjaan mengambang ke berbagai arah: setelah n hari, kemajuan bersih ≈ √n. Dengan visi jangka panjang yang kohesif, usaha terpusat: setelah n hari, kemajuan bersih ≈ n. Rasio n / √n = √n tumbuh tanpa batas.
Rasio √n
Jalan terarah tidak memerlukan sasaran yang sempurna. Bias yang konsisten ke tujuan mengonversi goyangan acak menjadi sesuatu yang lebih dekat dengan n kemajuan.
Batasan Model
Sebuah model yang memprediksi output 100x dari visi layak diteliti. Beberapa hal yang diabaikannya:
1. Dimensi: karier beroperasi dalam ruang dimensi tinggi, bukan ℤ. Geometri jalan acak dalam ℝ^d berubah secara signifikan dengan d.
2. Korelasi: langkah riset saling berkorelasi — kerja hari ini didasarkan pada kerja kemarin. Langkah-langkah yang berkorelasi berbeda dari langkah yang saling independen dan identik.
3. Visi itu mungkin salah: jalan tertuju ke magnet yang salah jauh lebih buruk daripada jalan acak.
Waktu Duplikat
Hamming membuka kelasnya dengan klaim bahwa pengetahuan teknis meningkat secara eksponensial setiap 17 tahun. Klaim tersebut memiliki struktur matematika yang tepat: pertumbuhan eksponensial.
Model Pertumbuhan Eksponensial
y(t) = a · e^(b·t)
di mana a = jumlah awal pada t = 0, b = laju pertumbuhan (per unit waktu), e ≈ 2.718.
Waktu Duplikat D: waktu untuk y menjadi dua kali lipat.
2a = a · e^(b·D) → 2 = e^(b·D) → ln(2) = b·D → D = ln(2) / b
ln(2) ≈ 0.693. Untuk b = 0.693/17 ≈ 0.0408 per tahun, waktu duplikat = 17 tahun.
Setengah Hidup
Setengah Hidup H: waktu untuk y menurun menjadi setengah nilainya (b < 0).
H = ln(2) / |b|
Formula yang sama dalam kedua arah. Keterampilan dengan setengah hidup 5 tahun: setelah 5 tahun, setengah nilai pasar hilang. Setelah 10 tahun: masih 1/4. Setelah 20 tahun: kurang dari 7% tetap ada.
Duplikasi Pengetahuan
Jika pengetahuan teknis meningkat dua kali setiap 17 tahun, seorang mahasiswa yang lulus pada usia 22 tahun menghadapi lanskap pengetahuan yang berubah pada usia 56 tahun — sebuah karier 34 tahun menutupi dua penggandaan penuh.
Setengah Hidup Keterampilan
Model eksponensial yang sama berlaku untuk pengurangan nilai. Keterampilan khusus (mis. keahlian dalam arsitektur chip tertentu, API yang sudah usang, algoritma yang ditinggalkan) kehilangan nilai seiring waktu karena bidang tersebut bergerak maju.
Jika setengah hidup keterampilan khusus H = 5 tahun, maka setelah t tahun fraksi dari nilai asli yang tetap: f(t) = (1/2)^(t/H) = 2^(−t/H).
Setelah satu setengah hidup (5 tahun): 50% tetap ada. Dua setengah hidup (10 tahun): 25%. Tiga (15 tahun): 12,5%. Empat (20 tahun): 6,25%.
Implikasi Hamming: nilai belajar bagaimana belajar mengalami peningkatan yang positif dengan eksponen yang sama yang mengurangi pengetahuan khusus. Investasi dalam strategi belajar, kerangka kerja masalah, dan alasan berpikir yang dapat diterapkan mempertahankan nilai melintasi siklus setengah hidup.
Geometri, Koreksi Kesalahan, & Karier
Tiga struktur geometri dari les ini tampaknya terpisah. Mereka terhubung.
Jarak Hamming mem Formalisasi biaya kesalahan dan kelebihan jumlah yang diperlukan untuk kembali dari itu. Setiap sistem komunikasi, setiap basis kode, setiap tubuh pengetahuan membutuhkan cukup kelebihan jumlah sehingga kesalahan individu tidak memusnahkan seluruhnya.
Argumen √n vs n menerjemahkan visi menjadi fakta geometri: arah berubah sebagai jarak dari titik awal, gerakan terarah sebagai perubahan posisi menuju tujuan. Kebutuhan redundansi dalam strategi karier - menjaga beberapa jalur penelitian terbuka - membuffer terhadap jalan yang salah secara berkala.
Pertumbuhan dan pengurangan eksponensial mengatur baik batas depan yang berkembang maupun setengah hidup pengetahuan yang Anda miliki saat ini. Investasi stabil satu-satunya: belajar cara belajar, yang mengalami penggandaan pada skala waktu yang sama dengan penurunan pengetahuan yang spesialis.