Дистанція в Бінарному Просторі
Найвідоміший технічний внесок Річарда Хеммінга: коди, що виправляють помилки. Геометрична ідея за ними лежить глибше, ніж будь-який конкретний код.
Дистанція Хеммінга
Дано два рядки бітів однакової довжини, дистанція Хеммінга 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-бітні рядки живуть у 8 вершинах куба. Суміжні по ребру вершини відрізняються рівно на 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. Виправляє 1 помилку. Виявляє 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 суттєво змінюється з 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 років охоплює два повних подвоєння.
Напів-Життя Експертизи
Та ж експоненціальна модель застосовується до розпаду. Конкретна навичка (напр. майстерність певної архітектури чипу, застарілого API, застарілого алгоритму) втрачає цінність протягом часу, оскільки поле рухається далі.
Якщо напів-життя спеціалізованої навички H = 5 років, то після t років частка оригінальної цінності, що залишилась: f(t) = (1/2)^(t/H) = 2^(−t/H).
Після одного напів-життя (5 років): залишилось 50%. Два напів-життя (10 років): 25%. Три (15 років): 12.5%. Чотири (20 років): 6.25%.
Імплікація Хеммінга: цінність навчання як навчатися складається позитивно з тим же показником, з яким спеціалізоване знання розпадається. Інвестування в стратегію навчання, формування проблем, & передаваний розум зберігає цінність через цикли напів-життя.
Геометрія, Виправлення Помилок, & Кар'єра
Три геометричні структури з цього уроку здаються несвязаними. Вони пов'язані.
Дистанція Хеммінга формалізує вартість помилки та надлишковість, необхідну для відновлення від неї. Кожна система комунікації, кожна база коду, кожне тіло знань потребує достатньої надлишковості, щоб окрема помилка не скоррумпувала ціле.
Аргумент √n проти n перетворює бачення на геометричний факт: дрейф масштабується як дистанція від початкової точки, спрямований рух масштабується як зміщення до мети. Надлишковість у стратегії кар'єри — тримання багатьох ліній запиту відкритими — буферизує проти випадкового неправильного повороту.
Експоненціальне зростання & розпад регулюють як розширюючу границю так і напів-життя того, що ви знаєте сьогодні. Єдина стійка інвестиція: навчання того, як навчатися, яке складається на тому ж часовій шкалі, на якій спеціалізоване знання розпадається.