Code Quest

I 1948 var verden stadig et analogt sted. Candid Camera og Ed Sullivan var lige begyndt på deres lange spil på tv; Jack Bennys radioprogram havde titusinder af lyttere. Men dårlig modtagelse var en kendsgerning. Elektromagnetisk interferens, fysiske forhindringer mellem et sendetårn og en modtager og andre kilder til, hvad ingeniører kalder støj, forstyrrede rutinemæssigt Bennys monologer eller Sullivans gæsters optrædener. I de fleste områder, for i det mindste nogle stationer, resignerede folk med snedækkede billeder eller statisk plaget lyd.

Claude Shannon, 1948

Samme år udgav Claude Shannon, SM '40, PhD '40, imidlertid et skelsættende papir, hvori han matematisk beviste, at selv i nærvær af meget støj var det muligt at transmittere information næsten uden fejl. Det var en analog verden, men Shannons fantastiske konklusion var resultatet af hans evne til at tænke digitalt. Information i ethvert medie, hævdede Shannon, kunne repræsenteres ved hjælp af binære cifre eller bits - et ord, som hans papir introducerede til verden. Mens støj i en kommunikationskanal kan ødelægge bitsene, forklarede han, at tilføje ekstra bits, der er relateret til de originale bits af en kendt algoritme - en fejlkorrigerende kode - vil gøre det muligt at udlede den originale sekvens.

Jo mere støjende kanalen er, jo mere ekstra information skal tilføjes for at muliggøre fejlkorrektion. Og jo mere ekstra information der er inkluderet, jo langsommere vil transmissionen være. Shannon viste, hvordan man beregner det mindste antal ekstra bits, der kunne garantere minimal fejl - og dermed den højeste hastighed, hvormed fejlfri datatransmission er mulig. Men han kunne ikke sige, hvordan et praktisk kodeskema kunne se ud.

Forskere brugte 45 år på at lede efter en. Endelig, i 1993, annoncerede et par franske ingeniører et sæt koder – turbokoder – der opnåede datahastigheder tæt på Shannons teoretiske grænse. Den første reaktion var vantro, men efterfølgende undersøgelse validerede forskernes påstande. Det viste sig også en endnu mere opsigtsvækkende kendsgerning: koder, der er lige så gode som turbokoder, som endda var afhængige af den samme type matematiske trick, var blevet introduceret mere end 30 år tidligere i MIT doktorafhandlingen af ​​Robert Gallager, SM ' 57, ScD '60. Efter årtiers forsømmelse har Gallagers koder endelig fundet praktisk anvendelse. De bruges til transmission af satellit-tv og trådløse data, og chips dedikeret til at afkode dem kan findes i kommercielle mobiltelefoner.

The Birth of Information Theory

Gallager kom til MIT i 1956 – samme år som Shannon selv vendte tilbage som professor efter 15 år på Bell Labs. Men det var ikke udsigten til at arbejde sammen med Shannon, der fik ham til at vælge MIT frem for Yale, hvor han også havde søgt ind på kandidatskolen. Jeg var i hæren – på en meningsløs opgave – og jeg hadede virkelig det, jeg lavede, siger Gallager, der underviste på MIT i mere end 40 år efter at have opnået sin doktorgrad og stadig rådgiver kandidatstuderende som professor emeritus i Research Lab i Elektronik. MIT startede en uge tidligere end Yale gjorde. Og jeg var så ivrig efter at komme ud af hæren, at det virkelig var min eneste grund til at komme til MIT.

Gallager var ikke engang sikker på, at han ville studere informationsteori, den spirende nye disciplin født af Shannons 1948-opgave. Men før han kom til Army Signal Corps, havde Gallager også arbejdet i flere år hos Bell Labs, hvor han tilbragte tre dage om ugen i et klasseværelse med at lære om de seneste fremskridt inden for elektroteknik. Selvom han aldrig havde mødt Shannon, hjalp denne oplevelse ham med at genkende omfanget af hans præstation. Jeg så ham bare som en slags gud, siger Gallager.

Da Shannon kom til MIT-fakultetet, var han faktisk en mindre berømthed. Så tidligt som i 1953 havde en artikel om informationsteori i magasinet Fortune erklæret: Det er måske ingen overdrivelse at sige, at menneskets fremskridt i fred og sikkerhed i krig afhænger mere af frugtbare anvendelser af informationsteori end af fysiske demonstrationer, enten i bomber. eller i kraftværker, at Einsteins berømte ligning virker.

Det, der fangede offentlighedens fantasi, var ideen om, at information i al dens mangfoldighed – tekst, lyd, video – kunne koges ned til blot sekvenser af 1'ere og 0'ere. Kommercielle digitale enheder eksisterede endnu ikke, så det blæste folk i tankerne, at 001001010101000101011101 kunne repræsentere en del af en symfoni, eller en del af en film, eller en farve eller en linje fra en bog. Men som Shannon påpegede i sit papir, havde hans Bell Labs-kollega Ralph Hartley fremsat et lignende forslag 20 år tidligere. Det aspekt af papiret, der fangede – og fortsætter med at fængsle – Shannons medingeniører var den geniale måde, hvorpå han beviste, at der skal være en eller anden kode, der er i stand til at producere fejlfri datatransmissioner helt op til en kanals kapacitet.

For at forstå, hvordan en fejlkorrigerende kode fungerer, skal du overveje en person, der forsøger at sende en fire-bit besked på tværs af en støjende kanal. Hvis støjen får en af ​​bits til at vende til det modsatte, har modtageren ingen mulighed for at vide, at der er opstået en fejl. Blot at gentage beskeden, så 0011 bliver 00110011, løser det problem: Hvis nu en bit vender til det modsatte, ved modtageren, at der er en fejl, fordi de to versioner af beskeden ikke stemmer overens. Men det er umuligt at sige, hvilken der er korrekt. En bedre måde at indkode meddelelsen på kan bruge de fire ekstra bits til at repræsentere information om meddelelsesbittene: den femte bit kan for eksempel fortælle dig, om de to første bits af meddelelsen har samme eller forskellige værdier; den sjette bit kunne gøre det samme for bit tre og fire, den syvende for bit et og tre, og den ottende for bit to og fire. Hvis en af ​​de første fire bits bliver vendt, kan de sidste fire identificere den; hvis en af ​​de sidste fire bits bliver vendt, kan de tre andre formidle nok information til at kompensere for det.

Shannons papir undlader imidlertid enhver sådan grublerier om, hvordan man faktisk konstruerer koder. I stedet nærmer den sig begrebet fejlkorrektion ved statistisk at analysere de generelle egenskaber af koder, der er valgt helt tilfældigt. For at få en fornemmelse af hans tilgang, kan det måske hjælpe at se, hvordan det kan anvendes på vores hypotetiske otte-bit sekvenser, der koder fire-bit beskeder.

Der er 16 mulige fire-bit beskeder, og Shannons metode vil tildele hver af dem sit eget tilfældigt udvalgte otte-bit serienummer - dets kodeord. Modtageren vil ligesom afsenderen have en kodebog, der korrelerer de 16 mulige fire-bit beskeder med de 16 tilfældige otte-bit kodeord. Da der er 256 mulige sekvenser af otte bit, er der 240, der ikke vises i kodebogen. En person, der modtager en af ​​disse 240 sekvenser, vil vide, at der har sneget sig en fejl ind i dataene. Men så længe de 16 tilladte kodeord er forskellige nok fra hinanden, er der sandsynligvis kun ét, der kommer tættest på den korrupte sekvens. For eksempel, hvis 00000001 og 11111110 begge er gyldige kodeord, men 00000011 ikke er det, så kan en person, der modtager sekvensen 00000011, konkludere, at det tilsigtede kodeord var meget mere sandsynligt at være 00000001 end 11111110.

I det virkelige liv er der selvfølgelig ingen, der er bekymrede for at sende beskeder på kun fire bit. Men ved at bruge statistisk analyse var Shannon i stand til at drage konklusioner om kodede beskeder af enhver længde, sendt over kanaler med enhver mængde støj. Især var han i stand til strengt at kvantificere både graden af ​​forskel mellem tilfældigt udvalgte kodeord og sandsynligheden for, at en korrupt sekvens kun ville ligne et af dem. Mens sandsynligheden for, at to otte-bit sekvenser vil være ens, er relativt høj, viste Shannon, at når kodeord bliver længere, falder chancerne for lighed eksponentielt. Faktisk var et af hans mest opsigtsvækkende resultater, at for lange beskeder vil de fleste tilfældigt tildelte kodeord være næsten lige så forskellige fra hinanden, som det er muligt for dem at være. Det betyder, at næsten ethvert kodningsskema - enhver måde at generere disse ord på - ville tillade fejlfri transmission på tværs af en støjende kanal ved nær den maksimale hastighed.

Det krævede en masse intuition at tro, at en helt tilfældig kode i gennemsnit kunne være en ret god kode, siger David Forney, SM '63, ScD '65, en tidligere vicepræsident for Codex Corporation og Motorola, som vendte tilbage til MIT i 1996 som adjungeret professor. Det viser sig, at det forenkler analysen drastisk, for nu kan man lave en gennemsnitlig case-analyse. Forney standser et øjeblik og tilføjer derefter: For ikke at sige, at det var helt enkelt: han var i det mindste nødt til at opfinde et par sætninger, hvis ikke grene af matematikken. Men Gallager er enig. Om Shannons papir fra 1948 siger han: Når du har studeret det i to år, virker det meget simpelt. Så mange mennesker vil fortælle dig: ’Det er virkelig meget simpelt.’ Og når du har forstået det, er det det.

En uimodståelig udfordring

Shannons matematiske beskrivelse af information havde mange forgreninger. Hans papir fra 1948 introducerede også ideen om datakomprimering eller at repræsentere den samme information med færre bits; komprimering er det, der lader programmer som WinZip eller StuffIt skrumpe filer ned, så de ikke overvælder e-mail-servere, og det bruges til at spare plads på diskdrev. Informationsteori satte også studiet af kryptografi på et mere sikkert matematisk grundlag; Galager mener faktisk, at det var Shannons kryptografiske arbejde i krigstid på Bell Labs, der førte ham til hans nye opfattelse af kommunikation.

Da Shannon vendte tilbage til MIT, var han imidlertid begyndt at føle, at entusiasmen omkring hans teori oversteg selv dens betydelige fordele. I en artikel fra 1956 kaldet The Bandwagon citerede han forsøg på at anvende informationsteori på områder som biologi, psykologi, lingvistik, fundamental fysik, økonomi, organisationsteorien og mange andre og påtog sig at indsprøjte en mådeholdenhed i denne situation.

Shannons afsky for rampelyset grænsede til tilbagetrækning. Ifølge Joel West '79, en professor ved San José State University's College of Business, som skriver en bog om udviklingen af ​​informationsteori, rådgav Shannon kun syv kandidatstuderende i løbet af sine 22 år på MIT. Han var ret genert og tilbagegående, så hvis man ville have ham som supervisor, skulle man virkelig være ret aggressiv omkring det, siger Gallager. Jeg var genert og trak mig også tilbage og havde ikke nok selvtillid til overhovedet at gå ind og tale med fyren.

Som lærer havde Shannon ringe tålmodighed til det velkendte. Han var meget mere interesseret i det nye end i det gamle, siger Elwyn Berlekamp '62, SM '62, PhD '64, professor emeritus i matematik ved University of California, Berkeley, som (sammen med Gallager) var medforfatter på Shannons endeligt offentliggjort papir.

Han underviste ikke ret meget, siger Gallager. Men når han underviste, var det som at holde forskningsforedrag. Jeg kan huske, at han engang holdt et kursus, som var på omkring 25 forelæsninger i løbet af semesteret, og hver forelæsning var et nyt forskningsresultat. Han ville gøre dem den ene efter den anden og undlod aldrig at finde på noget interessant. Det var en virkelig fantastisk periode.

Shannon var efter min mening en lille smule malplaceret i den akademiske verden, siger James L. Massey, SM '60, PhD '62, informationsteoretiker og professor emeritus ved ETH Zürich. Hans egentlige genre var at være en selvstændig forsker og gøre tingene på sin egen meget individualistiske måde.

Det kan også være, at Shannon simpelthen var utilpas med bespottelse. Berlekamp husker, da IEEE Information Theory Society inviterede Shannon til at holde et foredrag og modtage sin første Shannon Award i Israel i 1973. Jeg har aldrig set nogen med flere sommerfugle end ham, siger han. Fem minutter før snakken skal starte, er han i baren, og han er ret deprimeret. Han er virkelig bange for at gå på scenen og skuffe alle. For selvfølgelig forventer de Gud, hvilket er sandt, og han ved, at han ikke kan optræde som Gud.

Men hvis Shannon sjældent var en direkte mentor for unge studerende i informationsteori, havde han givet dem en uimodståelig udfordring. Tilfældig kodning ville aldrig fungere i praksis: Størrelsen af ​​Shannons hypotetiske kodebog blev fordoblet for hver ekstra bit i beskeden. Kodebogen til en enkelt 1.000-bit pakke med data, der rejser over internettet, ville kræve flere indtastninger, end der er atomer i universet. Men enhver mere praktisk kodningsmekanisme – som at gentage den originale besked eller tilføje ekstra bits, der beskrev beskedbits – svarede til et tilfældigt kodningsskema, idet det ville generere de samme kodeord. Og ved at demonstrere, at langt de fleste tilfældige kodningsskemaer var kapacitetsnærende, gav Shannon håb om, at en af ​​de praktiske også var det.

Undvigende koder

I stedet for at bruge en kodebog til at matche kodeord og meddelelser, ville et praktisk kodningsskema give en måde at udtrække meddelelsen fra kodeordene beregningsmæssigt. En række matematiske operationer kunne med stor sandsynlighed for nøjagtighed identificere og rette fejl i en muligvis korrupt bitsekvens modtaget over en støjende kanal.

Det er en af ​​de særlige kendetegn ved fejlkorrigerende koder, at en god indkodningsalgoritme ikke nødvendigvis indebærer en god afkodningsalgoritme. Ved at bruge statistiske analyser, der ligner Shannons, var kodningsteoretikere i stand til at vise, at en given kode nærmede sig kapacitet - at den ville maksimere forskellen mellem kodeord. Men det betød ikke, at de havde en effektiv måde at afkode det på.

Mellem udgivelsen af ​​Shannons papir og begyndelsen af ​​1990'erne foreslog forskere bedre og bedre koder og også bedre og bedre afkodningsalgoritmer. Men en praktisk kapacitetsnærende kode forblev uhåndgribelig. Der plejede at være et ordsprog blandt kodningsteoretikere, siger Forney, at næsten enhver kode er god - undtagen alle dem, vi kan komme i tanke om.

Koderne, som Gallager præsenterede i sin doktorafhandling fra 1960, var et forsøg på at bevare noget af tilfældigheden i Shannons hypotetiske system uden at ofre afkodningseffektiviteten. Ligesom mange tidligere koder brugte Gallager såkaldte paritetsbit, som angiver, om en anden gruppe af bit har lige eller ulige summer. Men tidligere koder genererede paritetsbittene på en systematisk måde: den første paritetsbit kunne indikere, om summen af ​​meddelelsesbits et til tre var lige; den næste paritetsbit kan gøre det samme for meddelelsesbit to til fire, den tredje for bit tre til fem, og så videre. I Gallagers koder var korrelationen mellem paritetsbit og meddelelsesbit derimod tilfældig: den første paritetsbit kan for eksempel beskrive summen af ​​meddelelsesbit 4, 27 og 83; den næste kan gøre det samme for meddelelsesbit 19, 42 og 65.

Gallager var i stand til matematisk at demonstrere, at for lange beskeder var hans pseudo-tilfældige koder kapacitetsnærende. Bortset fra, at vi vidste andre ting, der også var kapacitetsnærende, siger han. Det var aldrig et spørgsmål om, hvilke koder der var gode. Det var altid et spørgsmål om, hvilke slags afkodningsalgoritmer man kunne udtænke.

Det var her Gallager fik sit gennembrud. Hans koder brugte iterativ afkodning, hvilket betyder, at dekoderen ville passere gennem dataene flere gange og lave stadig mere raffinerede gæt om identiteten af ​​hver bit. Hvis f.eks. paritetsbittene beskrev tripletter af bit, så kunne pålidelig information om hvilke som helst to bits overføre information om en tredjedel. Gallagers iterative-dekodningsalgoritme er den, der oftest bruges i dag, ikke kun til at afkode sine egne koder, men også ofte til at afkode turbokoder. Det har også fundet anvendelse i den type statistiske ræsonnement, der bruges i mange kunstig intelligens-systemer.

Iterative teknikker involverer at lave et første gæt på, hvad en modtaget bit kan være og give den en vægt i forhold til, hvor pålidelig den er, siger Forney. Så får du måske mere information om det, fordi det er involveret i paritetstjek med andre bits, og så det giver dig et forbedret skøn over dets pålidelighed. I sidste ende, siger Forney, bør gættene konvergere mod en konsistent fortolkning af alle bits i beskeden.

Selvom Gallager ikke havde været i stand til at samle modet til at bede Shannon om at være hans rådgiver, siger han, at han talte med Shannon tre eller fire gange, mens han skrev sit speciale. Bortset fra, at det at tale med Claude tre-fire gange var som at tale med de fleste mennesker 50 gange, siger han. Han var en, der virkelig fangede ideerne meget, meget hurtigt. Han var ikke god til alle de tekniske detaljer. Men for at se strukturen af ​​noget, for at se, hvorfor det burde virke, og for at se, hvad der kunne gøre det bedre – ja, han var bestemt den klogeste person, jeg nogensinde har mødt.

Alligevel forudså Shannon ikke succesen med Gallagers koder. Min erindring er, at han syntes, de var interessante, men jeg havde ikke fornemmelsen af, at han var begejstret for dem, siger Gallager. Han forstår hvorfor. Gallagers koder nærmede sig kanalkapacitet, da de blev længere; men efterhånden som de blev længere, blev afkodningsprocessen også mere kompleks – alt for kompleks til datidens computere. Kodningsforskere vidste selvfølgelig, at computere ville blive bedre. Men ingen vidste, hvis koder disse forbedringer ville favorisere.

Ikke desto mindre hyrede MIT straks Gallager som fakultetsmedlem på grund af hans afhandling. I de efterfølgende år, mens hans eget kodningsskema sygnede hen i uklarhed, underviste og vejledte han en bølge af geniale studerende – inklusive Massey, Forney og Berlekamp – hvis bidrag til kodningsteori havde mere umiddelbare praktiske implikationer end hans egne.

Gallager virker dog lige så uforstyrret over den lange forsømmelse af hans koder, som han gør ved deres nylige genoplivning - måske fordi han altid tog det lange blik. Han har en evne til at opfinde ting, der ligger i dvale i ti år, indtil folk pludselig indser, at det er ret gode ting, siger Vincent Chan '71, MS '71, EE '72, PhD '74, en professor i elektroteknik, der stadig viser af hans skrivebord dørpladen fra kontoret, han engang delte med Shannon. Chan husker et nyligt besøg i laboratorierne hos en stor softwarevirksomhed, hvor en forsker pralede af en ny komprimeringsteknik, der ville gøre det muligt for videofiler kun at optage en hundrededel så meget hukommelse, som de gør nu. Chan følte sig forpligtet til at påpege, at Gallager havde introduceret teknikken i 1974. Mange af disse ideer tager en del tid at tænke igennem, siger han, og på det tidspunkt, hvor man tænker dem igennem, er der mange, mange muligheder . Og man skal virkelig tænke sig godt om og måske over længere tid, før man finder ud af, hvilken der er den rigtige. Bob gør det meget.

Muriel Médard '89, '90, MS '91, ScD '95, en informationsteoretiker i Research Lab of Electronics, er enig. Bob løb ikke rundt og prøvede at udgive og sikre sig, at han ikke blev scoopet, siger hun. For eksempel minder Médard om en samtale mellem Gallager og en fremtrædende yngre informationsteoretiker, som i sin beskrivelse af sit eget arbejde citerede et nyligt bevist teorem, som det stolede på. Bob begynder at rode i ting, som han gør, siger Médard. Til sidst fremstillede han en laset kopi af et af sine egne papirer. Han havde det her teensy-weensy lille bevis, siger Médard. Og det var som en fodnote. En tyk fodnote, men en fodnote. ’Har de navngivet det?’ ’Ja, Bob, det er en større sætning nu.’

I dag ligger Gallagers koder til grund for de tilgange, der kommer tættest på den maksimale datahastighed for en given kommunikationskanal – tættere på endda end turbokoder. Ud over deres applikationer inden for telekommunikation begynder de at erstatte de ældre koder, der bruges til at beskytte data i diskdrev og andre lagerenheder.

For folk som Forney, der var på MIT under det, han kalder kodningsteoriens gyldne tidsalder, er det noget bittersødt, at udfordringen fra Shannons papir fra 1948 er blevet imødekommet. De af os, der kender og elsker kodning, er tilbageholdende med at sige, at problemet er fuldstændig løst, siger Forney. Men det er rigtigt, at de fleste er gået over til andre ting.

Fra 1950 til 1965 var MIT arnestedet for informationsteori, siger Joel West. Det var virkelig en guldalder.

skjule