Bell Labs, 1947
Richard Hamming anslöt sig till Bell Telephone Laboratories 1946. Datorerna med reläer där kördes bara på vardagar, när tekniker kunde starta om dem efter fel. Helger stoppade maskinerna när något gick fel — vilket lämnade jobb i kö tills måndag.
Hamming var rasande. 'Om maskinen kan detektera ett fel,' tänkte han, 'varför kan den inte lokalisera det och korrigera det?' Denna frustration, kombinerad med djup förtrogenhet med binär aritmetik och paritetskontroller, skapade förutsättningarna.
Första insikten: Rektangulära koder
Hammings första idé: arrangera meddelandebitar i en m×n rektangel, lägg till en paritetskontroll för varje rad & varje kolumn. Ett enda fel producerar exakt ett misslyckat radkontroll & ett misslyckat kolonnkontroll. Deras skärningspunkt namnger fellets position.
Redundansförhållande: (m+1)(n+1) / mn. Kalkyl talar om att en kvadrat minimerar detta för fast meddelandestorlek. Men när m & n växer, blir ett dubbelfel mer troligt — en ingenjörsbedömning utan universellt svar.
Minimering av rektangulär redundans
En 4×4 rektangel bär 16 meddelandebitar med 4 radkontroller & 4 kolonnkontroller, plus 1 hörnparitetsbil = 9 kontrollbitar för 16 meddelandebitar.
Redundansförhållande: (m+1)(n+1) / mn = 25/16 ≈ 1.56.
För en 10×10 rektangel: 100 meddelandebitar, 121 totala bitar, redundans ≈ 1.21.
Syndromet som ett binärt nummer
Några veckor efter insikten om den rektangulära koden åkte Hamming mot New York genom New Jerseys lantliga landskap, återupprepade mentalt hans framgångar. Triangelkoden föll honom in — bättre redundans. Sedan kuben. Sedan 4-dimensionell, 5-dimensionell...
Varje extra dimension förbättrade redundansen. En hyperkub med sida 2 i n dimensioner använder endast n+1 paritetskontroller för 2^n hörn. Men var detta optimalt?
Räkneargumentet
n+1 paritetsbitar producerar ett syndrom: ett (n+1)-bitars binärt nummer. Det syndromet måste identifiera 2^n + 1 distinkta resultat: var & en av 2^n felpositionerna, plus det speciella 'inget fel'-resultatet.
2^(n+1) = 2·2^n — nästan tillräckligt. Av en faktor 2. Hamming lade problemet åt sidan.
Nyckelinsikten
Senare återvände Hamming med en ny idé: använd syndromet själv som ett binärt nummer som namnger fellets position. Position 1 = binär 001, position 2 = binär 010, position 3 = binär 011, osv. Reservera allt nollor för 'inget fel.'
Detta omvandlar syndromet från en utgång av paritetskontroller till en adress. Paritetskontrollerna är utformade för att producera exakt rätt adress när någon enskild bit flippar.
Utformning av (7,4) koden
För en 7-bitars kod (3 paritetsbitar, 4 meddelandebitar), positionerna 1 genom 7 i binär är: 001, 010, 011, 100, 101, 110, 111.
Paritetskontroll 1 täcker positioner där bit 0 = 1: positionerna 1, 3, 5, 7.
Paritetskontroll 2 täcker positioner där bit 1 = 1: positionerna 2, 3, 6, 7.
Paritetskontroll 3 täcker positioner där bit 2 = 1: positionerna 4, 5, 6, 7.
Paritetsbitar upptar potensen-av-2 positioner: 1, 2, 4. Meddelandebitar upptar resten: 3, 5, 6, 7.
Om bit 6 flippar, paritetskontroller 2 & 3 misslyckas (110 i binär = 6). Syndromet läses 110 = 6. Flippa position 6. Klart.
Enkelt fel korrigera, dubbelt fel detektera
Hamming-koden (7,4) korrigerar enkla fel. Men vad om två bitar flippar? Utan extra skydd tillämpar avkodaren syndromregeln & 'korrigerar' kodordet till det felaktiga meddelandet — en tyst felkorrigering.
SECDED: En till paritetsbil
Lägg till en enda paritetsbil p₀ täcka hela kodordet (alla 7 bitar). Nu har syndromet 4 poster: de ursprungliga 3 kontrollerna plus p₀.
``
glodlammalt syndrom ny p₀ betydelse
000 0 korrekt
000 1 fel endast i p₀
xxx 1 enkelt fel, gammalt syndrom namnger det
xxx 0 dubbelfel — flagga det
``
De fyra fallen är uttömmande. Ett dubbelfel flippar två bitar: det gamla syndromet läser inte 000 (båda bitarna tillsammans korrumperar två av dess kontroller), men p₀ flippar två gånger & återvänder till 0. Mönstret xxx + 0 är omöjligt att missa.
Varför SECDED fungerar
SECDED-regeln utnyttjar paritetens modulära struktur. Med jämn paritet förändras p₀ genom någon enskild flip. Någon dubbel flip lämnar p₀ oförändrad. Så p₀ räknar fel modulo 2.
Den geometriska bilden
Hamming anlände till samma plats från en annan riktning: analytisk geometri. Representera varje n-bitars sträng som en vertex av en n-dimensionell hyperkub. En enskild bitflip flyttar en punkt en kantlängd längs en axel. Två flips: två kanter. Måttet är Hammingavståndet.
Definiera en Hammingboll med radie t runt en kodord c: alla punkter inom t bitflips från c. För enkelfelskorrigering, t = 1.
Villkor för enkelfelskorrigering: bollar med radie 1 runt varje par av distinkta kodord får inte överlappa. Om de överlappar, kan ett mottaget ord i överlappningen tillhöra antingen kodord & avkodaren misslyckas.
Detta översätts direkt till minimumdistans: två bollar med radie 1 överlappar inte om & endast om kodorden är minst 3 isär (d_min ≥ 3).
Koden (7,4) uppnår d_min = 3. Hammings gräns: 2^7 / (1 + 7) = 16 = 2^4. Exakt 16 kodord. En perfekt kod: de 16 bollarna med radie 1 plattsätter {0,1}^7 utan luckor eller överlappningar.
Ingenjörsbedömningar
Hamming var explicit: felkorrigerande koder involverar ingenjörsbedömningar, inte ren matematik.
Meddelandelängd: längre meddelanden tillåter mer effektiv kodning (log n paritetsbitar för n meddelandebitar). Men längre meddelanden ackumulerar också mer brus, vilket ökar risken att ett dubbelfel smyger igenom som en falsk enkel korrigering.
Nivå av korrigering vs. detektering: byta en felkorrigering för två extra feldetekteringar. Det optimala delandet beror på kanalens bruskarcateristika.
Fältunderhållsvärde: när utrustning växer mer komplex kan fältteknikerna inte diagnostisera varje fel från första principerna. Ett självdiagnostiserande system minskar drastiskt den skicklighet som krävs för underhål. Hamming kallade detta en av de viktigaste fördelarna, ofta viktigare än den råa pålitlighetsvunsten.
Stil: Lyckan gynnar det förberedda sinnet
Hamming avslutade kapitel 12 med en direkt utmaning. Han beskrev upptäckten som kräver tre till sex månaders arbete, mest vid udda tillfällen medan han utförde sina huvuduppgifter på Bell Labs.
Han identifierade tre saker som gjorde det möjligt:
1. Beredskap: djup förtrogenhet med paritetskontroller, binär aritmetik, & gruppteori, före problemet dök upp.
2. Granska framgångar: regelbundet återupprepande tidigare lösningar för att internalisera deras stil. Triangelkoden föll honom in medan han mentalt granskade den rektangulära koden på en pendling.
3. Inte nöja sig med 'ser bra ut': han brände sina fingrar en gång genom att acceptera skenbara optimalitet. Han pushade tills han kunde bevisa att koden var bäst.