Abstand im binären Raum
Richard Hammings berühmtester technischer Beitrag: fehlerkorrigierende Codes. Die geometrische Idee dahinter geht tiefer als jeder spezifische Code.
Hamming-Abstand
Bei zwei Binärstrings gleicher Länge zählt der Hamming-Abstand d(u, v) die Positionen, an denen sie sich unterscheiden:
``
u = 1 0 1 1 0
v = 1 1 1 0 0
↑ ↑
d(u,v) = 2
``
Dies erfüllt alle drei metrischen Axiome: d(u,v) ≥ 0; d(u,v) = 0 gdw u = v; d(u,v) = d(v,u); d(u,w) ≤ d(u,v) + d(v,w). Der binäre n-Raum mit Hamming-Abstand bildet einen gültigen metrischen Raum.
Die Geometrie lässt sich in niedrigen Dimensionen klar visualisieren. Alle 3-Bit-Strings befinden sich an den 8 Ecken eines Würfels. Kantenbenachbarte Ecken unterscheiden sich in genau 1 Bit; Flächendiagonale Ecken unterscheiden sich in 2; antipodal Ecken (z.B. 000 und 111) unterscheiden sich in 3.
Hamming-Abstand berechnen
Hamming-Gewicht wt(v) zählt die Anzahl der 1en in v. Der Abstand bezieht sich auf das Gewicht über XOR:
d(u, v) = wt(u XOR v)
Beispiel: u = 10110, v = 11100. XOR = 01010. Gewicht = 2. Also d(u,v) = 2.
Fehlerkorrektur durch Kugelpackung
Ein Binärcode C ⊆ {0,1}^n besteht aus ausgewählten Codewörtern. Wenn ein Codewort über einen verrauschten Kanal übertragen wird, können einige Bits umkippen. Der Empfänger erhält einen beschädigten String und muss das Original wiederherstellen.
Definieren Sie einen Hamming-Ball mit Radius t um Codewort c:
B(c, t) = { v ∈ {0,1}^n : d(c, v) ≤ t }
Um bis zu t Fehler zu korrigieren, dürfen sich die Bälle B(c, t) um jedes Codewort-Paar nicht überschneiden. Falls sie sich überschneiden, könnte ein empfangenes Wort in zwei Bällen liegen und der Decoder kann nicht bestimmen, welches Codewort gesendet wurde.
Der Mindestabstand d_min eines Codes bestimmt alles:
- Bis zu d_min − 1 Fehler erkennen - Bis zu ⌊(d_min − 1) / 2⌋ Fehler korrigieren
Hamming-(7,4)-Code: n = 7 Bits, k = 4 Datenbits, d_min = 3. Korrigiert 1 Fehler. Erkennt 2.
Wie viele Codewörter passen?
Wie viele Codewörter kann ein Code der Länge n enthalten und trotzdem t Fehler korrigieren? Jedes Codewort 'besitzt' einen Ball mit Radius t. Alle Bälle zusammen müssen in {0,1}^n passen, das 2^n Punkte hat.
Volumen eines Hamming-Balls mit Radius t in {0,1}^n:
Vol(n,t) = Σ_{i=0}^{t} C(n, i)
Die Hamming-Grenze (Kugelpackungs-Grenze) folgt direkt: ein Code, der t Fehler korrigiert, erfüllt
M · Vol(n,t) ≤ 2^n
wobei M = Anzahl der Codewörter. Also M ≤ 2^n / Vol(n,t).
Für den Hamming-(7,4)-Code: n=7, t=1. Vol(7,1) = C(7,0) + C(7,1) = 1 + 7 = 8. Grenze: M ≤ 128 / 8 = 16. Der (7,4)-Code erreicht M = 2^4 = 16: ein perfekter Code, das heißt, die Bälle kacheln {0,1}^7 ohne Lücken.
√n vs n
Hamming nutzte ein Zufallswalk-Argument, um den Wert einer langfristigen Vision präzise zu machen. Das Argument konvertiert eine vage Aussage — „Vision hilft" — in eine geometrische Tatsache über Abstände.
Symmetrischer Zufallswalk auf ℤ
Bei jedem Schritt um +1 oder −1 mit gleicher Wahrscheinlichkeit bewegen. Nach n Schritten, erwartete Verschiebung vom Ursprung: E[|X_n|] ≈ √n.
Dies folgt aus der Varianz: Var(X_n) = n (Schritte unabhängig, jeder ±1 mit Varianz 1). Standardabweichung = √n.
Gerichteter Walk
Bei jedem Schritt mit Wahrscheinlichkeit p > 1/2 um +1 bewegen (Neigung zu einem Ziel). Nach n Schritten, erwartete Position: E[X_n] = n(2p−1). Für p = 1 (vollständig gerichtet): E[X_n] = n.
Der Kontrast: zufällige Drift skaliert als √n; gerichteter Fortschritt skaliert als n.
Hammings Übersetzung
In einer Forschungskarriere repräsentiert jeder Arbeitstag einen Schritt. Ohne eine klare Vision, was zählt, treibt die Arbeit in viele Richtungen: nach n Tagen, Nettofortschritt ≈ √n. Mit einer kohärenten langfristigen Vision, Anstrengung richtet sich aus: nach n Tagen, Nettofortschritt ≈ n. Das Verhältnis n / √n = √n wächst ohne Grenze.
Das √n-Verhältnis
Der gerichtete Walk erfordert keine perfekte Zielgenauigkeit. Jede anhaltende Neigung zu einem Ziel konvertiert √n Drift in einen dem n Fortschritt ähnlicheren Wert.
Grenzen des Modells
Ein Modell, das 100x Ausgang aus Vision vorhersagt, verdient Überprüfung. Es lässt mehrere Dinge weg:
1. Dimensionalität: Karrieren finden in hochdimensionalem Raum statt, nicht in ℤ. Die Geometrie eines Zufallswalk in ℝ^d ändert sich deutlich mit d.
2. Korrelation: Forschungsschritte korrelieren — heutige Arbeit baut auf gestrige auf. Korrelierte Walks verhalten sich anders als i.i.d.-Schritte.
3. Die Vision selbst könnte falsch sein: ein gerichteter Walk zu einem falschen Attraktor ist schlimmer als Drift.
Verdoppelungszeit
Hamming eröffnete seinen Kurs mit der Aussage, dass sich technisches Wissen ungefähr alle 17 Jahre verdoppelt. Diese Aussage hat eine präzise mathematische Struktur: exponentielles Wachstum.
Exponentielles Wachstumsmodell
y(t) = a · e^(b·t)
wobei a = Anfangsmenge bei t = 0, b = Wachstumsrate (pro Zeiteinheit), e ≈ 2.718.
Verdoppelungszeit D: die Zeit für y, sich zu verdoppeln.
2a = a · e^(b·D) → 2 = e^(b·D) → ln(2) = b·D → D = ln(2) / b
ln(2) ≈ 0.693. Für b = 0.693/17 ≈ 0.0408 pro Jahr, Verdoppelungszeit = 17 Jahre.
Halbwertzeit
Halbwertzeit H: Zeit für y, auf die Hälfte ihres Wertes zu zerfallen (b < 0).
H = ln(2) / |b|
Die gleiche Formel in beide Richtungen. Eine Fertigkeit mit 5-jähriger Halbwertzeit: nach 5 Jahren, die Hälfte ihres Marktwerts weg. Nach 10 Jahren: ein Viertel bleibt. Nach 20 Jahren: weniger als 7% bleibt.
Wissensverdopplung
Wenn sich technisches Wissen alle 17 Jahre verdoppelt, sieht sich ein Student, der mit 22 Jahren graduiert, mit 56 Jahren einer transformierten Wissenslandschaft gegenüber — eine 34-jährige Karriere umfasst zwei volle Verdopplungen.
Halbwertzeit der Expertise
Dasselbe exponentielle Modell gilt für den Zerfall. Eine spezifische Fertigkeit (z.B. Beherrschung einer bestimmten Chip-Architektur, einer veralteten API, eines überholten Algorithmus) verliert im Laufe der Zeit an Wert, wenn sich das Feld weiterentwickelt.
Wenn die Halbwertzeit einer spezialisierten Fertigkeit H = 5 Jahre ist, dann bleibt nach t Jahren der Bruchteil des ursprünglichen Wertes: f(t) = (1/2)^(t/H) = 2^(−t/H).
Nach einer Halbwertzeit (5 Jahre): 50% bleibt. Zwei Halbwertzeiten (10 Jahre): 25%. Drei (15 Jahre): 12,5%. Vier (20 Jahre): 6,25%.
Hammings Implikation: Der Wert des Lernens wie man lernt wächst exponentiell mit dem gleichen Exponenten, mit dem sich Spezialwissen abbaut. Investition in Lernstrategie, Problemformulierung & transferables Denken bewahrt Wert über Halbwertzeit-Zyklen hinweg.
Geometrie, Fehlerkorrektur & Karriere
Die drei geometrischen Strukturen aus dieser Lektion erscheinen zusammenhanglos. Sie verbinden sich.
Der Hamming-Abstand formalisiert die Kosten von Fehlern und die Redundanz, die benötigt wird, um sich davon zu erholen. Jedes Kommunikationssystem, jede Codebasis, jeder Wissenskorpus benötigt genug Redundanz, dass Einzelfehler das Ganze nicht beschädigen.
Das √n vs n Argument übersetzt Vision in eine geometrische Tatsache: Drift skaliert als Abstand vom Ausgangspunkt, gerichtete Bewegung skaliert als Verschiebung zu einem Ziel. Redundanz in der Karrierestrategie — mehrere Forschungslinien offen halten — puffert gegen gelegentliche Fehltritte.
Exponentielles Wachstum & Zerfall bestimmen sowohl die expandierende Grenze als auch die Halbwertzeit dessen, was Sie heute wissen. Die einzige stabile Investition: Lernen wie man lernt, das sich auf der gleichen Zeitskala zusammensetzt, auf der sich Spezialwissen abbaut.