Bell Labs, 1947
Richard Hamming sloot zich in 1946 aan bij Bell Telephone Laboratories. De relaiscomputers daar werkten alleen op weekdagen, wanneer technici ze na fouten opnieuw konden starten. In het weekend stopten de machines wanneer iets fout ging — waardoor taken tot maandag in de wachtrij bleven staan.
Hamming was furieus. 'Als de machine een fout kan detecteren,' dacht hij, 'waarom kan het deze niet lokaliseren en corrigeren?' Deze frustratie, gecombineerd met diepe kennis van binaire rekenkunde en pariteitscontroles, zette het podium klaar.
Eerste inzicht: Rechthoekige codes
Hammings eerste idee: rangschik berichtbits in een m×n rechthoek, voeg een pariteitscontrole toe aan elke rij & elke kolom. Een enkele fout levert precies één falende rijcontrole & één falende kolomcontrole op. Hun kruispunt benoemt de foutpositie.
Redundantieverhouding: (m+1)(n+1) / mn. Calculus vertelt je dat een vierkant dit minimaliseert voor vaste berichtgrootte. Maar naarmate m & n groeien, wordt een dubbele fout waarschijnlijker — een technisch oordeel zonder universeel antwoord.
Rechthoekige redundantie minimaliseren
Een 4×4 rechthoek draagt 16 berichtbits met 4 rijcontroles & 4 kolomcontroles, plus 1 hoekpariteitsbit = 9 controlbits voor 16 berichtbits.
Redundantieverhouding: (m+1)(n+1) / mn = 25/16 ≈ 1,56.
Voor een 10×10 rechthoek: 100 berichtbits, 121 totale bits, redundantie ≈ 1,21.
Het syndroom als binair getal
Een paar weken na het rechthoekige code-inzicht reed Hamming naar New York door New Jersey landbouwland, en dacht mentaal zijn successen na. De driehoekscode viel hem in — beter redundantie. Daarna de kubus. Daarna 4-dimensionaal, 5-dimensionaal...
Elke extra dimensie verbeterde redundantie. Een hyperkubus van zijde 2 in n dimensies gebruikt slechts n+1 pariteitscontroles voor 2^n hoekpunten. Maar was dit optimaal?
Het telargument
n+1 pariteitscontroles produceren een syndroom: een (n+1)-bits binair getal. Dat syndroom moet 2^n + 1 verschillende uitkomsten identificeren: elk van de 2^n foutposities, plus de speciale 'geen fout'-uitkomst.
2^(n+1) = 2·2^n — bijna genoeg. Scheelt een factor 2. Hamming stelde het probleem ter zijde.
Het sleutelinzicht
Later keerde Hamming terug met een nieuw idee: gebruik het syndroom zelf als binair getal dat de foutpositie benoemt. Positie 1 = binair 001, positie 2 = binair 010, positie 3 = binair 011, enz. Reserveer alles-nullen voor 'geen fout.'
Dit transformeert het syndroom van een uitvoer van pariteitscontroles in een adres. De pariteitscontroles zijn ontworpen om precies het juiste adres op te leveren wanneer een willekeurige bit omkeert.
Het (7,4)-code ontwerpen
Voor een 7-bit code (3 pariteitscontroles, 4 berichtbits), posities 1 tot en met 7 in binair zijn: 001, 010, 011, 100, 101, 110, 111.
Pariteitscontrole 1 dekt posities waar bit 0 = 1: posities 1, 3, 5, 7.
Pariteitscontrole 2 dekt posities waar bit 1 = 1: posities 2, 3, 6, 7.
Pariteitscontrole 3 dekt posities waar bit 2 = 1: posities 4, 5, 6, 7.
Pariteitscontroles nemen machten-van-2-posities in: 1, 2, 4. Berichtbits nemen de rest in: 3, 5, 6, 7.
Als bit 6 omkeert, falen pariteitscontroles 2 & 3 (110 in binair = 6). Het syndroom leest 110 = 6. Keer positie 6 om. Klaar.
Enkele fout corrigeren, dubbele fout detecteren
De (7,4) Hamming-code corrigeert enkele fouten. Maar wat gebeurt er als twee bits omkeren? Zonder extra bescherming past de decoder de syndroomregel toe en 'corrigeert' het codewoord naar het verkeerde bericht — een stille verkeerde correctie.
SECDED: één extra pariteitsbit
Voeg een enkel pariteitsbit p₀ toe dat het hele codewoord dekt (alle 7 bits). Nu heeft het syndroom 4 vermeldingen: de originele 3 controles plus p₀.
``
oud syndroom nieuwe p₀ betekenis
000 0 correct
000 1 fout alleen in p₀
xxx 1 enkele fout, oud syndroom benoemt het
xxx 0 dubbele fout — markeer het
``
De vier gevallen zijn exhaustief. Een dubbele fout keert twee bits om: het oude syndroom leest niet 000 (beide bits samen corrupteren samen twee van zijn controles), maar p₀ keert twee keer om en keert terug naar 0. Het patroon xxx + 0 is ondubbelzinnig.
Waarom SECDED werkt
De SECDED-regel exploiteert de modulaire structuur van pariteit. Met even pariteit verandert elke enkele omkering p₀. Elke dubbele omkering laat p₀ onveranderd. Dus p₀ telt fouten modulo 2.
Het geometrische beeld
Hamming bereikte dezelfde plaats vanuit een ander hoek: analytische geometrie. Representeer elke n-bit string als een hoekpunt van een n-dimensionale hyperkubus. Een enkele bitomkering verplaatst een punt één randlengte langs één as. Twee omkeringen: twee randen. De metriek is Hamming-afstand.
Definieer een Hamming-bal van straal t rond een codewoord c: alle punten binnen t bitomkeringen van c. Voor enkele-fout correctie, t = 1.
Voorwaarde voor enkele-fout correctie: ballen van straal 1 rond elk paar verschillende codewoorden mogen elkaar niet overlappen. Als ze overlappen, kan een ontvangen woord in de overlap tot beide codewoorden behoren en faalt de decoder.
Dit vertaalt zich direct naar minimale afstand: twee ballen van straal 1 overlappen niet dan en slechts dan als de codewoorden minstens 3 uit elkaar liggen (d_min ≥ 3).
De (7,4)-code bereikt d_min = 3. Hammings grens: 2^7 / (1 + 7) = 16 = 2^4. Exact 16 codewoorden. Een perfecte code: de 16 ballen van straal 1 tegelen {0,1}^7 zonder gaten of overlappen.
Technische oordelen
Hamming was expliciet: foutcorrigerende codes omvatten technische oordelen, niet zuivere wiskunde.
Berichtlengte: langere berichten staan efficiëntere codering toe (log n pariteitscontroles voor n berichtbits). Maar langere berichten accumuleren ook meer ruis, wat het risico verhoogt dat een dubbele fout als valse enkele correctie door glipt.
Correctie- versus detectieniveau: handel één foutcorrectie om voor twee extra foutdetecties. De optimale splitsing hangt af van de ruiskenmerken van het kanaal.
Waarde van veldherstel: naarmate apparatuur complexer wordt, kunnen veldtechnici niet elke fout uit eerste principes diagnose. Een zelf-diagnose systeem vermindert dramatisch de vaardigheid die voor onderhoud vereist is. Hamming noemde dit een van de belangrijkste voordelen, vaak belangrijker dan de ruwe betrouwbaarheidswinst.
Stijl: Geluk begünstigt de voorbereide geest
Hamming sloot Hoofdstuk 12 af met een directe uitdaging. Hij beschreef de ontdekking als drie tot zes maanden werk, meestal op ongebruikelijke momenten terwijl hij zijn belangrijkste taken bij Bell Labs vervulde.
Hij identificeerde drie dingen die het mogelijk maakten:
1. Voorbereiding: diepe kennis van pariteitscontroles, binaire rekenkunde, & groepstheorie, voordat het probleem verscheen.
2. Successen herzien: gewoontelijk voorbije oplossingen intern maken. De driehoekscode viel hem in terwijl hij de rechthoekige code mentaal herzag op een woonwerk.
3. Zich niet tevreden stellen met 'ziet er goed uit': hij had eenmaal zijn vingers gebrand door schijnbare optimaliteit te accepteren. Hij hield aan tot hij kon bewijzen dat de code het beste was.