Khoảng cách trong Không gian Nhị phân
Đóng góp kỹ thuật nổi tiếng nhất của Richard Hamming: mã sửa lỗi. Ý tưởng hình học phía sau chúng sâu sắc hơn bất kỳ mã cụ thể nào.
Khoảng cách Hamming
Cho hai chuỗi nhị phân có độ dài bằng nhau, khoảng cách Hamming d(u, v) đếm các vị trí khác nhau:
``
u = 1 0 1 1 0
v = 1 1 1 0 0
↑ ↑
d(u,v) = 2
``
Điều này thỏa mãn cả ba tiên đề metric: d(u,v) ≥ 0; d(u,v) = 0 nếu và chỉ nếu u = v; d(u,v) = d(v,u); d(u,w) ≤ d(u,v) + d(v,w). Không gian nhị phân n chiều với khoảng cách Hamming tạo thành một không gian metric hợp lệ.
Hình học có thể hình dung rõ ràng trong các chiều thấp. Tất cả các chuỗi 3-bit nằm ở 8 đỉnh của một khối lập phương. Các đỉnh kề cạnh khác nhau trong chính xác 1 bit; các đỉnh đối diện mặt khác nhau 2; các đỉnh đối cực (ví dụ: 000 và 111) khác nhau 3.
Tính toán Khoảng cách Hamming
Trọng số Hamming wt(v) đếm số lượng 1 trong v. Khoảng cách liên quan đến trọng số thông qua XOR:
d(u, v) = wt(u XOR v)
Ví dụ: u = 10110, v = 11100. XOR = 01010. Trọng số = 2. Vậy d(u,v) = 2.
Sửa lỗi thông qua Đóng gói Hình cầu
Một mã nhị phân C ⊆ {0,1}^n bao gồm các từ mã được chọn. Khi một từ mã được truyền qua một kênh nhiễu, một số bit có thể bị lật. Người nhận nhận được một chuỗi bị hỏng và phải khôi phục chuỗi gốc.
Định nghĩa một quả cầu Hamming có bán kính t tâm tại từ mã c:
B(c, t) = { v ∈ {0,1}^n : d(c, v) ≤ t }
Để sửa lên đến t lỗi, các quả cầu B(c, t) xung quanh mỗi cặp từ mã không được chồng lấp. Nếu chúng chồng lấp, một từ được nhận có thể nằm trong hai quả cầu và bộ giải mã không thể xác định từ mã nào được gửi.
Khoảng cách tối thiểu d_min của một mã chi phối mọi thứ:
- Phát hiện lên đến d_min − 1 lỗi - Sửa lên đến ⌊(d_min − 1) / 2⌋ lỗi
Mã Hamming (7,4): n = 7 bits, k = 4 data bits, d_min = 3. Sửa 1 lỗi. Phát hiện 2.
Bao nhiêu Từ mã vừa vặn?
Một mã độ dài n có thể chứa bao nhiêu từ mã mà vẫn có thể sửa t lỗi? Mỗi từ mã 'sở hữu' một quả cầu bán kính t. Tất cả các quả cầu với nhau phải vừa vặn bên trong {0,1}^n, có 2^n điểm.
Thể tích của một quả cầu Hamming có bán kính t trong {0,1}^n:
Vol(n,t) = Σ_{i=0}^{t} C(n, i)
Giới hạn Hamming (giới hạn đóng gói hình cầu) tuân theo trực tiếp: một mã sửa t lỗi thỏa mãn
M · Vol(n,t) ≤ 2^n
trong đó M = số lượng từ mã. Vậy M ≤ 2^n / Vol(n,t).
Đối với mã Hamming (7,4): n=7, t=1. Vol(7,1) = C(7,0) + C(7,1) = 1 + 7 = 8. Giới hạn: M ≤ 128 / 8 = 16. Mã (7,4) đạt được M = 2^4 = 16: một mã hoàn hảo, có nghĩa là các quả cầu lát gạch {0,1}^7 mà không có khoảng trống.
√n so với n
Hamming đã sử dụng một đối số phép đi bộ ngẫu nhiên để làm cho giá trị của tầm nhìn tầm xa chính xác. Đối số chuyển đổi một tuyên bố mơ hồ — 'tầm nhìn giúp đỡ' — thành một thực tế hình học về khoảng cách.
Phép đi bộ ngẫu nhiên đối xứng trên ℤ
Ở mỗi bước, di chuyển +1 hoặc −1 với xác suất bằng nhau. Sau n bước, độ dịch chuyển kỳ vọng từ gốc: E[|X_n|] ≈ √n.
Điều này tuân theo phương sai: Var(X_n) = n (các bước độc lập, mỗi bước ±1 phương sai 1). Độ lệch chuẩn = √n.
Phép đi bộ Có hướng
Ở mỗi bước, di chuyển +1 với xác suất p > 1/2 (thiên vị hướng tới một mục tiêu). Sau n bước, vị trí kỳ vọng: E[X_n] = n(2p−1). Đối với p = 1 (hoàn toàn có hướng): E[X_n] = n.
Sự tương phản: trôi ngẫu nhiên tỷ lệ như √n; tiến bộ có hướng tỷ lệ như n.
Phiên dịch của Hamming
Trong sự nghiệp nghiên cứu, mỗi ngày làm việc đại diện cho một bước. Không có tầm nhìn rõ ràng về những gì quan trọng, công việc trôi dạt theo nhiều hướng: sau n ngày, tiến bộ ròng ≈ √n. Với tầm nhìn tầm xa kết hợp, nỗ lực căn chỉnh: sau n ngày, tiến bộ ròng ≈ n. Tỷ lệ n / √n = √n tăng mà không có giới hạn.
Tỷ lệ √n
Phép đi bộ có hướng không yêu cầu độ chính xác hoàn hảo. Bất kỳ thiên vị liên tục nào hướng tới một mục tiêu đều chuyển đổi trôi ngẫu nhiên √n thành thứ gì đó gần gũi hơn với tiến bộ n.
Giới hạn của Mô hình
Một mô hình dự đoán 100x sản lượng từ tầm nhìn xứng đáng được xem xét kỹ lưỡng. Một số thứ nó bỏ qua:
1. Chiều: sự nghiệp hoạt động trong không gian chiều cao, không phải ℤ. Hình học của phép đi bộ ngẫu nhiên trong ℝ^d thay đổi đáng kể với d.
2. Tương quan: các bước nghiên cứu tương quan — công việc hôm nay xây dựng trên công việc hôm qua. Các phép đi bộ có tương quan hoạt động khác biệt với các bước i.i.d.
3. Tầm nhìn bản thân có thể sai: một phép đi bộ có hướng hướng tới một tập hợp hút sai là tệ hơn trôi dạt.
Thời gian Tăng đôi
Hamming mở khóa học của anh ấy bằng tuyên bố rằng kiến thức kỹ thuật tăng đôi khoảng 17 năm. Tuyên bố đó có một cấu trúc toán học chính xác: tăng trưởng hàm số mũ.
Mô hình Tăng trưởng Hàm số mũ
y(t) = a · e^(b·t)
trong đó a = số lượng ban đầu tại t = 0, b = tỷ lệ tăng trưởng (trên một đơn vị thời gian), e ≈ 2.718.
Thời gian tăng đôi D: thời gian để y tăng đôi.
2a = a · e^(b·D) → 2 = e^(b·D) → ln(2) = b·D → D = ln(2) / b
ln(2) ≈ 0.693. Đối với b = 0.693/17 ≈ 0.0408 trên năm, thời gian tăng đôi = 17 năm.
Bán rã
Bán rã H: thời gian để y suy giảm xuống một nửa giá trị của nó (b < 0).
H = ln(2) / |b|
Công thức tương tự theo cả hai hướng. Một kỹ năng với bán rã 5 năm: sau 5 năm, một nửa giá trị thị trường của nó biến mất. Sau 10 năm: còn lại một phần tư. Sau 20 năm: còn lại ít hơn 7%.
Sự tăng đôi Kiến thức
Nếu kiến thức kỹ thuật tăng đôi 17 năm một lần, một sinh viên tốt nghiệp ở tuổi 22 phải đối mặt với một bộ cảnh kiến thức được thay đổi ở tuổi 56 — sự nghiệp 34 năm trải dài hai lần tăng đôi đầy đủ.
Bán rã của Chuyên môn
Mô hình hàm số mũ tương tự cũng áp dụng cho suy giảm. Một kỹ năng cụ thể (ví dụ: thành thạo một kiến trúc chip cụ thể, một API không được dùng nữa, một thuật toán bị thay thế) mất giá trị theo thời gian khi lĩnh vực tiến lên.
Nếu bán rã của một kỹ năng chuyên biệt H = 5 năm, thì sau t năm phần nhỏ của giá trị ban đầu còn lại: f(t) = (1/2)^(t/H) = 2^(−t/H).
Sau một bán rã (5 năm): còn lại 50%. Hai bán rã (10 năm): 25%. Ba (15 năm): 12.5%. Bốn (20 năm): 6.25%.
Ý nghĩa của Hamming: giá trị của việc học cách học được tích lũy tích cực với cùng một số mũ mà kiến thức chuyên biệt suy giảm. Đầu tư vào chiến lược học tập, khung bài toán, & lý luận có thể chuyển giao bảo tồn giá trị trong các chu kỳ bán rã.
Hình học, Sửa lỗi, & Sự nghiệp
Ba cấu trúc hình học từ bài học này dường như không liên kết. Chúng kết nối.
Khoảng cách Hamming chính thức hóa chi phí lỗi và sự dư thừa cần thiết để phục hồi từ nó. Mọi hệ thống giao tiếp, mọi cơ sở mã, mọi phần thân kiến thức cần đủ sự dư thừa để các lỗi đơn lẻ không làm hỏng tổng thể.
Đối số √n so với n chuyển đổi tầm nhìn thành một thực tế hình học: trôi dạt tỷ lệ như khoảng cách từ một điểm xuất phát, chuyển động có hướng tỷ lệ như độ dịch chuyển hướng tới một mục tiêu. Sự dư thừa trong chiến lược sự nghiệp — giữ mở nhiều dòng điều tra — đệm chống lại những sai lầm tình cờ.
Tăng trưởng hàm số mũ & suy giảm chi phối cả biên giới mở rộng và bán rã của những gì bạn biết hôm nay. Khoản đầu tư ổn định duy nhất: học cách học, được tích lũy theo cùng một thang thời gian mà kiến thức chuyên biệt suy giảm.