211service.com
Code zoektocht
In 1948 was de wereld nog een analoge plek. Candid Camera en Ed Sullivan waren net begonnen met hun lange series op tv; De radioshow van Jack Benny had tientallen miljoenen luisteraars. Maar slechte ontvangst was een feit van het leven. Elektromagnetische interferentie, fysieke obstakels tussen een zendmast en een ontvanger en andere bronnen van wat technici ruis noemen, verstoorden routinematig de monologen van Benny of de optredens van Sullivans gasten. In de meeste gebieden, voor ten minste sommige stations, legden mensen zich neer bij besneeuwde beelden of statische audio.
Claude Shannon, 1948
Datzelfde jaar publiceerde Claude Shannon, SM '40, PhD '40, echter een baanbrekend artikel waarin hij wiskundig bewees dat het zelfs in de aanwezigheid van veel ruis mogelijk was om informatie vrijwel foutloos te verzenden. Het was een analoge wereld, maar Shannons verbluffende conclusie was het resultaat van zijn vermogen om digitaal te denken. Informatie in elk medium, zo betoogde Shannon, kan worden weergegeven met binaire cijfers of bits - een woord dat zijn paper in de wereld introduceerde. Hoewel ruis in een communicatiekanaal de bits kan beschadigen, legt hij uit, zal het toevoegen van extra bits die gerelateerd zijn aan de originele bits door een bekend algoritme - een foutcorrigerende code - het mogelijk maken om de oorspronkelijke volgorde af te leiden.
Hoe luidruchtiger het kanaal, hoe meer extra informatie er moet worden toegevoegd om foutcorrectie mogelijk te maken. En hoe meer extra informatie is opgenomen, hoe langzamer de verzending zal zijn. Shannon liet zien hoe het kleinste aantal extra bits kan worden berekend dat een minimale fout kan garanderen, en dus de hoogste snelheid waarmee foutloze gegevensoverdracht mogelijk is. Maar hij kon niet zeggen hoe een praktisch codeerschema eruit zou kunnen zien.
Onderzoekers hebben er 45 jaar naar gezocht. Eindelijk, in 1993, kondigde een paar Franse ingenieurs een reeks codes aan - turbocodes - die datasnelheden bereikten die dicht bij de theoretische limiet van Shannon lagen. De eerste reactie was ongeloof, maar het daaropvolgende onderzoek bevestigde de beweringen van de onderzoekers. Het bleek ook een nog meer opzienbarend feit: codes die net zo goed waren als turbocodes, die zelfs op hetzelfde type wiskundige truc vertrouwden, waren meer dan 30 jaar eerder geïntroduceerd, in het MIT-doctoraat van Robert Gallager, SM ' 57, ScD '60. Na decennia van verwaarlozing hebben Gallagers codes eindelijk praktische toepassing gevonden. Ze worden gebruikt bij de overdracht van satelliet-tv en draadloze gegevens, en chips die zijn bedoeld om ze te decoderen, zijn te vinden in commerciële mobiele telefoons.
De geboorte van informatietheorie
Gallager kwam in 1956 naar het MIT, hetzelfde jaar dat Shannon zelf terugkeerde als professor, na 15 jaar bij Bell Labs. Maar het was niet het vooruitzicht om met Shannon samen te werken dat hem ertoe bracht MIT te verkiezen boven Yale, waar hij zich ook had aangemeld voor een graduate school. Ik zat in het leger – voor een zinloze opdracht – en ik had een hekel aan wat ik deed, zegt Gallager, die meer dan 40 jaar lesgaf aan het MIT na het behalen van zijn doctoraat en nog steeds afgestudeerde studenten adviseert als emeritus hoogleraar in het Research Lab of Elektronica. MIT begon een week eerder dan Yale. En ik wilde zo graag uit het leger dat dat eigenlijk mijn enige reden was om naar MIT te komen.
Gallager wist niet eens zeker of hij informatietheorie wilde studeren, de ontluikende nieuwe discipline die voortkwam uit Shannons paper uit 1948. Maar voordat hij bij het legersignaalkorps kwam, had ook Gallager een aantal jaren bij Bell Labs gewerkt, waar hij drie dagen per week in een klaslokaal doorbracht om de nieuwste ontwikkelingen op het gebied van elektrotechniek te leren. Hoewel hij Shannon nooit had ontmoet, hielp die ervaring hem de omvang van zijn prestatie te erkennen. Ik zag hem gewoon als een soort god, zegt Gallager.
Tegen de tijd dat Shannon aan de MIT-faculteit toetrad, was hij inderdaad een kleine beroemdheid. Al in 1953 had een artikel over informatietheorie in het tijdschrift Fortune gesteld: Het is misschien niet overdreven om te zeggen dat de vooruitgang van de mens in vrede en veiligheid in oorlog meer afhankelijk is van vruchtbare toepassingen van informatietheorie dan van fysieke demonstraties, hetzij in bommen of in energiecentrales, dat de beroemde vergelijking van Einstein werkt.
Wat tot de publieke verbeelding sprak, was het idee dat informatie in al zijn diversiteit - tekst, audio, video - kon worden teruggebracht tot louter reeksen van enen en nullen. Commerciële digitale apparaten bestonden nog niet, dus het verbaasde mensen dat 001001010101000101011101 een deel van een symfonie, of een deel van een film, of een kleur, of een regel uit een boek kon vertegenwoordigen. Maar zoals Shannon in zijn artikel opmerkte, had zijn Bell Labs-collega Ralph Hartley 20 jaar eerder een soortgelijke suggestie gedaan. Het aspect van het artikel dat Shannons collega-ingenieurs boeide – en nog steeds boeit, was de ingenieuze manier waarop hij bewees dat er een code moet zijn die foutloze gegevensoverdrachten kan produceren tot aan de capaciteit van een kanaal.
Om te begrijpen hoe een foutcorrigerende code werkt, kun je iemand overwegen die een vierbits bericht probeert te verzenden via een kanaal met veel ruis. Als de ruis ervoor zorgt dat een van de bits naar het tegenovergestelde kantelt, kan de ontvanger niet weten dat er een fout is opgetreden. Gewoon het bericht herhalen, zodat 0011 00110011 wordt, lost dat probleem op: nu, als een bit naar het tegenovergestelde verandert, weet de ontvanger dat er een fout is, omdat de twee versies van het bericht niet overeenkomen. Maar het is onmogelijk om te zeggen welke de juiste is. Een betere manier om het bericht te coderen zou kunnen zijn om de vier extra bits te gebruiken om informatie over de berichtbits weer te geven: het vijfde bit zou je bijvoorbeeld kunnen vertellen of de eerste twee bits van het bericht dezelfde of verschillende waarden hebben; de zesde bit zou hetzelfde kunnen doen voor bits drie en vier, de zevende voor bits één en drie, en de achtste voor bits twee en vier. Als een van de eerste vier bits wordt omgedraaid, kunnen de laatste vier het identificeren; als een van de laatste vier bits wordt omgedraaid, kunnen de andere drie voldoende informatie bevatten om dit goed te maken.
Het artikel van Shannon schuwt echter dergelijke overpeinzingen over hoe codes daadwerkelijk moeten worden geconstrueerd. In plaats daarvan benadert het het concept van foutcorrectie door de algemene eigenschappen van volledig willekeurig geselecteerde codes statistisch te analyseren. Om een idee te krijgen van zijn benadering, zou het kunnen helpen om te zien hoe deze kan worden toegepast op onze hypothetische acht-bits reeksen die vier-bits berichten coderen.
Er zijn 16 mogelijke vier-bits berichten, en de methode van Shannon zou elk van hen zijn eigen willekeurig gekozen acht-bits serienummer toewijzen - het codewoord. De ontvanger zou, net als de afzender, een codeboek hebben dat de 16 mogelijke vier-bits berichten correleert met de 16 willekeurige acht-bits codewoorden. Aangezien er 256 mogelijke reeksen van acht bits zijn, zijn er 240 die niet in het codeboek voorkomen. Iemand die een van die 240 sequenties ontvangt, weet dat er een fout in de gegevens is geslopen. Maar zolang de 16 toegestane codewoorden genoeg van elkaar verschillen, is er waarschijnlijk maar één die het dichtst bij de beschadigde reeks komt. Als bijvoorbeeld 00000001 en 11111110 beide geldige codewoorden zijn, maar 00000011 niet, dan kan iemand die de reeks 00000011 ontvangt, concluderen dat het bedoelde codewoord veel waarschijnlijker was 00000001 dan 11111110.
In het echte leven maakt niemand zich natuurlijk zorgen over het verzenden van berichten van slechts vier bits. Maar door statistische analyse te gebruiken, kon Shannon conclusies trekken over gecodeerde berichten van elke lengte, verzonden over kanalen met elke hoeveelheid ruis. Hij was in het bijzonder in staat om zowel de mate van verschil tussen willekeurig geselecteerde codewoorden als de waarschijnlijkheid dat een beschadigde reeks op slechts één van hen zou lijken, rigoureus te kwantificeren. Hoewel de kans dat twee reeksen van acht bits vergelijkbaar zijn relatief groot is, toonde Shannon aan dat naarmate codewoorden langer worden, de kans op overeenkomst exponentieel afneemt. Een van zijn meest opzienbarende resultaten was zelfs dat voor lange berichten de meeste willekeurig toegewezen codewoorden bijna net zo van elkaar zullen verschillen als mogelijk is. Dat betekent dat bijna elk coderingsschema - elke manier om die woorden te genereren - foutloze transmissie over een luidruchtig kanaal mogelijk zou maken met bijna de maximale snelheid.
Er was veel intuïtie voor nodig om te denken dat een perfect willekeurige code gemiddeld een behoorlijk goede code zou kunnen zijn, zegt David Forney, SM '63, ScD '65, een voormalig vice-president van de Codex Corporation en Motorola die in 1996 terugkeerde naar MIT als adjunct-hoogleraar. Dat blijkt de analyse drastisch te vereenvoudigen, want nu kun je een gemiddelde casusanalyse doen. Forney pauzeert even en voegt er dan aan toe: Om niet te zeggen dat het heel eenvoudig was: hij moest op zijn minst een paar stellingen bedenken, zo niet takken van de wiskunde. Maar Gallager is het daarmee eens. Over Shannons paper uit 1948 zegt hij: Nadat je het twee jaar hebt bestudeerd, lijkt het heel eenvoudig. Zoveel mensen zullen je zeggen: 'Het is echt heel eenvoudig.' En nadat je het begrijpt, is het dat ook.
Een onweerstaanbare uitdaging
Shannons wiskundige beschrijving van informatie had vele vertakkingen. Zijn artikel uit 1948 introduceerde ook het idee van datacompressie, of het weergeven van dezelfde informatie met minder bits; compressie zorgt ervoor dat programma's zoals WinZip of StuffIt bestanden verkleinen zodat ze de e-mailservers niet overbelasten, en het wordt gebruikt om ruimte op schijfstations te besparen. De informatietheorie zette ook de studie van cryptografie op een meer veilige wiskundige basis; inderdaad, Gallager gelooft dat het Shannons cryptografische werk in oorlogstijd bij Bell Labs was dat hem leidde tot zijn nieuwe heropvatting van communicatie.
Tegen de tijd dat Shannon terugkeerde naar het MIT, begon hij echter het gevoel te krijgen dat het enthousiasme rond zijn theorie zelfs de aanzienlijke verdiensten ervan overtrof. In een artikel uit 1956, genaamd The Bandwagon, citeerde hij pogingen om informatietheorie toe te passen op gebieden als biologie, psychologie, taalkunde, fundamentele fysica, economie, organisatietheorie en vele andere, en hij beloofde een toon van gematigdheid in deze situatie te brengen.
Shannons afkeer van de schijnwerpers grensde aan teruggetrokkenheid. Volgens Joel West '79, een professor aan de San José State University's College of Business die een boek schrijft over de ontwikkeling van informatietheorie, adviseerde Shannon slechts zeven afgestudeerde studenten tijdens zijn 22 jaar aan het MIT. Hij was nogal verlegen en teruggetrokken, dus als je hem als supervisor wilde hebben, moest je daar echt behoorlijk agressief in zijn, zegt Gallager. Ik was verlegen en ging ook met pensioen, en had niet genoeg zelfvertrouwen om zelfs maar naar binnen te gaan en met de man te praten.
Als leraar had Shannon weinig geduld met de verveling van het bekende. Hij was veel meer geïnteresseerd in het nieuwe dan in het oude, zegt Elwyn Berlekamp '62, SM '62, PhD '64, emeritus hoogleraar wiskunde aan de University of California, Berkeley, die (met Gallager) co-auteur was van Shannon's laatste gepubliceerde paper.
Hij gaf niet heel veel les, zegt Gallager. Maar toen hij lesgaf, was het alsof hij onderzoekstoespraken hield. Ik herinner me dat hij een keer een cursus gaf, ongeveer 25 lezingen gedurende de periode, en elke lezing was een nieuw onderzoeksresultaat. Hij zou ze de een na de ander doen en nooit nagelaten om met iets interessants op de proppen te komen. Het was echt een fantastische periode.
Shannon was naar mijn mening een beetje misplaatst in de academische wereld, zegt James L. Massey, SM '60, PhD '62, een informatietheoreticus en emeritus hoogleraar aan de ETH Zürich. Zijn echte genre was om een onafhankelijke onderzoeker te zijn en dingen op zijn eigen hoogst individualistische manier te doen.
Het kan ook zijn dat Shannon zich gewoon niet op haar gemak voelde met bewondering. Berlekamp herinnert zich dat de IEEE Information Theory Society Shannon in 1973 uitnodigde om een lezing te geven en de inaugurele Shannon Award in ontvangst te nemen in Israël. Ik heb nog nooit iemand gezien met meer vlinders dan hij, zegt hij. Vijf minuten voordat het gesprek begint, zit hij aan de bar en is hij behoorlijk depressief. Hij is echt bang om het podium op te gaan en iedereen teleur te stellen. Omdat ze natuurlijk God verwachten, wat waar is, en hij weet dat hij niet kan presteren zoals God.
Maar hoewel Shannon zelden een directe mentor was voor jonge studenten informatietheorie, had hij ze een onweerstaanbare uitdaging gegeven. Willekeurige codering zou in de praktijk nooit werken: de grootte van Shannons hypothetische codeboek verdubbelde met elk extra bit in het bericht. Het codeboek voor een enkel 1.000-bits gegevenspakket dat over internet reist, zou meer gegevens vereisen dan er atomen in het universum zijn. Maar elk praktischer coderingsmechanisme - zoals het herhalen van het oorspronkelijke bericht of het toevoegen van extra bits die berichtbits beschrijven - was het equivalent van een willekeurig codeerschema, in die zin dat het dezelfde codewoorden zou genereren. En door aan te tonen dat de overgrote meerderheid van willekeurige coderingsschema's capaciteit naderden, bood Shannon hoop dat een van de praktische schema's dat ook was.
Ongrijpbare codes
In plaats van een codeboek te gebruiken om codewoorden en berichten te matchen, zou een praktisch coderingsschema een manier bieden om het bericht rekenkundig uit de codewoorden te extraheren. Een reeks wiskundige bewerkingen zou, met een hoge waarschijnlijkheid van nauwkeurigheid, fouten kunnen identificeren en corrigeren in een mogelijk beschadigde bitreeks die via een kanaal met ruis wordt ontvangen.
Het is een van de eigenaardigheden van foutcorrigerende codes dat een goed coderingsalgoritme niet noodzakelijk een goed decoderingsalgoritme impliceert. Met behulp van statistische analyses die vergelijkbaar zijn met die van Shannon, konden codeertheoretici aantonen dat een bepaalde code capaciteit naderde - dat het het verschil tussen codewoorden zou maximaliseren. Maar dat betekende niet dat ze een efficiënte manier hadden om het te decoderen.
Tussen de publicatie van Shannons paper en het begin van de jaren negentig stelden onderzoekers steeds betere codes voor en ook steeds betere decoderingsalgoritmen. Maar een praktische capaciteitsnaderende code bleef ongrijpbaar. Er was een gezegde onder codeertheoretici, zegt Forney, dat bijna elke code goed is, behalve alle die we kunnen bedenken.
De codes die Gallager presenteerde in zijn proefschrift uit 1960 waren een poging om een deel van de willekeur van Shannons hypothetische systeem te behouden zonder de decoderingsefficiëntie op te offeren. Zoals veel eerdere codes, gebruikte Gallager's zogenaamde pariteitsbits, die aangeven of een andere groep bits even of oneven sommen heeft. Maar eerdere codes genereerden de pariteitsbits op een systematische manier: de eerste pariteitsbit zou kunnen aangeven of de som van berichtbits één tot en met drie even was; de volgende pariteitsbit zou hetzelfde kunnen doen voor berichtbits twee tot en met vier, de derde voor bits drie tot en met vijf, enzovoort. In de codes van Gallager was de correlatie tussen pariteitsbits en berichtbits daarentegen willekeurig: het eerste pariteitsbit zou bijvoorbeeld de som van berichtbits 4, 27 en 83 kunnen beschrijven; de volgende zou hetzelfde kunnen doen voor berichtbits 19, 42 en 65.
Gallager was in staat om wiskundig aan te tonen dat voor lange berichten zijn pseudo-willekeurige codes capaciteit naderden. Behalve dat we ook andere dingen wisten die de capaciteit naderden, zegt hij. Het was nooit de vraag welke codes goed waren. Het was altijd de vraag wat voor soort decoderingsalgoritmen je kon bedenken.
Daar brak Gallager door. Zijn codes maakten gebruik van iteratieve decodering, wat inhoudt dat de decoder de gegevens meerdere keren zou passeren, waardoor hij steeds verfijndere gissingen maakte over de identiteit van elk bit. Als de pariteitsbits bijvoorbeeld tripletten van bits beschrijven, dan zou betrouwbare informatie over twee willekeurige bits informatie over een derde kunnen overbrengen. Het iteratieve decoderingsalgoritme van Gallager wordt tegenwoordig het meest gebruikt, niet alleen om zijn eigen codes te decoderen, maar vaak ook om turbocodes te decoderen. Het heeft ook toepassing gevonden in het type statistische redenering dat in veel kunstmatige-intelligentiesystemen wordt gebruikt.
Iteratieve technieken omvatten het maken van een eerste schatting van wat een ontvangen bit zou kunnen zijn en het een gewicht geven op basis van hoe betrouwbaar het is, zegt Forney. Dan krijg je er misschien meer informatie over omdat het betrokken is bij pariteitscontroles met andere bits, en dat geeft je dus een betere schatting van de betrouwbaarheid ervan. Uiteindelijk, zegt Forney, moeten de gissingen samenkomen in de richting van een consistente interpretatie van alle bits in het bericht.
Hoewel Gallager de moed niet had kunnen opbrengen om Shannon te vragen zijn adviseur te worden, zegt hij dat hij tijdens het schrijven van zijn scriptie drie of vier keer met Shannon heeft gesproken. Behalve dat drie of vier keer praten met Claude hetzelfde was als vijftig keer praten met de meeste mensen, zegt hij. Hij was iemand die de ideeën heel, heel snel doorhad. Hij was niet geweldig in alle technische details. Maar om de structuur van iets te zien, om te zien waarom het zou moeten werken, en om te zien wat het beter zou kunnen maken - nou, hij was zeker de slimste persoon die ik ooit heb ontmoet.
Toch voorzag Shannon het succes van Gallagers codes niet. Ik herinner me dat hij ze interessant vond, maar ik had niet het gevoel dat hij er enthousiast over was, zegt Gallager. Hij begrijpt waarom. De codes van Gallager naderden de kanaalcapaciteit naarmate ze langer werden; maar naarmate ze langer werden, werd het decoderingsproces ook complexer - veel te complex voor de computers van die tijd. Codeeronderzoekers wisten natuurlijk dat computers zouden verbeteren. Maar niemand wist wiens codes die verbeteringen zouden begunstigen.
Niettemin nam MIT Gallager onmiddellijk aan als faculteitslid op basis van zijn proefschrift. In de daaropvolgende jaren, terwijl zijn eigen codeerschema in de vergetelheid wegkwijnde, onderwees en begeleidde hij een golf van briljante studenten - waaronder Massey, Forney en Berlekamp - wiens bijdragen aan de codeertheorie meer directe praktische implicaties hadden dan de zijne.
Gallager lijkt echter net zo onverstoorbaar door de lange verwaarlozing van zijn codes als door hun recente heropleving - misschien omdat hij altijd op de lange termijn keek. Hij heeft de gave om dingen uit te vinden die tientallen jaren sluimeren totdat mensen plotseling beseffen dat het best goed spul is, zegt Vincent Chan '71, MS '71, EE '72, PhD '74, een professor in de elektrotechniek die nog steeds door zijn bureau de deurplaat van het kantoor dat hij ooit met Shannon deelde. Chan herinnert zich een recent bezoek aan de laboratoria van een groot softwarebedrijf, waar een onderzoeker opschepte over een nieuwe compressietechniek waarmee videobestanden slechts een honderdste zoveel geheugen zouden innemen als nu. Chan voelde zich genoodzaakt erop te wijzen dat Gallager de techniek in 1974 had geïntroduceerd. Veel van deze ideeën nemen nogal wat tijd in beslag, zegt hij, en op het moment dat je erover nadenkt, zijn er heel veel opties . En je moet echt heel goed nadenken en misschien over een lange periode voordat je erachter komt welke de juiste is. Dat doet Bob veel.
Muriel Médard '89, '90, MS '91, ScD '95, een informatietheoreticus in het Research Lab of Electronics, is het daarmee eens. Bob rende niet rond om te proberen te publiceren en ervoor te zorgen dat hij niet werd gescoord, zegt ze. Zo herinnert Médard zich een gesprek tussen Gallager en een prominente jongere informatietheoreticus, die bij het beschrijven van zijn eigen werk een recent bewezen stelling aanhaalde waarop het zich baseerde. Bob begint dingen door te spitten, zoals hij dat doet, zegt Médard. Uiteindelijk produceerde hij een gescheurde kopie van een van zijn eigen papieren. Hij had dit piepkleine bewijs, zegt Médard. En het was als een voetnoot. Een dikke voetnoot, maar een voetnoot. ‘Hebben ze dat genoemd?’ ‘Ja, Bob, het is nu een belangrijke stelling.’
Tegenwoordig liggen de codes van Gallager ten grondslag aan de benaderingen die het dichtst in de buurt komen van de maximale gegevenssnelheid voor een bepaald communicatiekanaal - zelfs dichterbij dan turbocodes. Naast hun toepassingen in telecommunicatie, beginnen ze de oudere codes te vervangen die worden gebruikt om gegevens op schijfstations en andere opslagapparaten te beschermen.
Voor mensen als Forney, die aan het MIT zaten tijdens wat hij de gouden eeuw van de codeertheorie noemt, is het feit dat de uitdaging van Shannons artikel uit 1948 is aangegaan, enigszins bitterzoet. Degenen onder ons die coderen kennen en ervan houden, aarzelen om te zeggen dat het probleem volledig is opgelost, zegt Forney. Maar het is waar dat de meeste mensen zijn overgestapt op andere dingen.
Van 1950 tot 1965 was MIT het broeinest van de informatietheorie, zegt Joel West. Het was echt een gouden eeuw. 