211service.com
Code Quest
1948 var världen fortfarande en analog plats. Candid Camera och Ed Sullivan hade precis börjat sina långa körningar på TV; Jack Bennys radioprogram hade tiotals miljoner lyssnare. Men dåligt mottagande var ett faktum. Elektromagnetiska störningar, fysiska hinder mellan ett sändningstorn och en mottagare och andra källor till vad ingenjörer kallar brus störde rutinmässigt Bennys monologer eller uppträdanden av Sullivans gäster. I de flesta områden, för åtminstone vissa stationer, resignerade människor för snöiga bilder eller statiskt plågat ljud.
Claude Shannon, 1948
Samma år publicerade dock Claude Shannon, SM '40, PhD '40, en landmärkeuppsats där han matematiskt bevisade att även i närvaro av mycket brus var det möjligt att överföra information praktiskt taget utan fel. Det var en analog värld, men Shannons fantastiska slutsats var resultatet av hans förmåga att tänka digitalt. Information i vilket medium som helst, hävdade Shannon, kunde representeras med binära siffror, eller bitar – ett ord som hans tidning introducerade till världen. Medan brus i en kommunikationskanal kan korrumpera bitarna, förklarade han, att lägga till extra bitar som är relaterade till de ursprungliga bitarna av någon känd algoritm – en felkorrigerande kod – kommer att göra det möjligt att härleda den ursprungliga sekvensen.
Ju bullrigare kanal är, desto mer extra information måste läggas till för att göra felkorrigering möjlig. Och ju mer extra information som ingår, desto långsammare blir överföringen. Shannon visade hur man beräknar det minsta antalet extra bitar som kan garantera minimalt fel - och därmed den högsta hastigheten med vilken felfri dataöverföring är möjlig. Men han kunde inte säga hur ett praktiskt kodningsschema kan se ut.
Forskare ägnade 45 år åt att leta efter en. Slutligen, 1993, tillkännagav ett par franska ingenjörer en uppsättning koder – turbokoder – som uppnådde datahastigheter nära Shannons teoretiska gräns. Den första reaktionen var misstro, men efterföljande undersökning validerade forskarnas påståenden. Det visade sig också ett ännu mer häpnadsväckande faktum: koder lika bra som turbokoder, som till och med förlitade sig på samma typ av matematiska trick, hade introducerats mer än 30 år tidigare, i MIT doktorsavhandlingen av Robert Gallager, SM ' 57, ScD '60. Efter årtionden av försummelse har Gallagers koder äntligen funnit praktisk tillämpning. De används för överföring av satellit-TV och trådlös data, och chips som är avsedda för att avkoda dem kan hittas i kommersiella mobiltelefoner.
The Birth of Information Theory
Gallager kom till MIT 1956 – samma år som Shannon själv återvände som professor, efter 15 år på Bell Labs. Men det var inte möjligheten att arbeta med Shannon som fick honom att välja MIT framför Yale, där han också hade sökt till forskarskolan. Jag var i armén – på ett meningslöst uppdrag – och jag hatade verkligen det jag gjorde, säger Gallager, som undervisade vid MIT i mer än 40 år efter att ha tagit sin doktorsexamen och fortfarande råder doktorander som professor emeritus i Research Lab Elektronik. MIT startade en vecka tidigare än Yale gjorde. Och jag var så angelägen om att komma ur armén att det verkligen var min enda anledning till att komma till MIT.
Gallager var inte ens säker på att han ville studera informationsteori, den spirande nya disciplin som föddes av Shannons uppsats från 1948. Men innan han började på Army Signal Corps, hade Gallager också arbetat i flera år på Bell Labs, där han tillbringade tre dagar i veckan i ett klassrum och lärde sig om de senaste framstegen inom elektroteknik. Även om han aldrig hade träffat Shannon, hjälpte den erfarenheten honom att inse omfattningen av hans prestation. Jag såg honom bara som en slags gud, säger Gallager.
När Shannon började på MIT-fakulteten var han faktiskt en mindre kändis. Redan 1953 hade en artikel om informationsteori i tidskriften Fortune deklamerat, Det kanske inte är någon överdrift att säga att människans framsteg i fred och säkerhet i krig beror mer på fruktbara tillämpningar av informationsteori än på fysiska demonstrationer, antingen i bomber. eller i kraftverk, att Einsteins berömda ekvation fungerar.
Det som fångade allmänhetens fantasi var tanken att information i all dess mångfald – text, ljud, video – kunde kokas ner till bara sekvenser av 1:or och 0:or. Kommersiella digitala enheter existerade ännu inte, så det blåste folks sinnen att 001001010101000101011101 kunde representera en del av en symfoni, eller en del av en film, eller en färg, eller en linje från en bok. Men som Shannon påpekade i sin tidning, hade hans Bell Labs-kollega Ralph Hartley gjort ett liknande förslag 20 år tidigare. Den aspekt av tidningen som fängslade – och fortsätter att fängsla – Shannons medingenjörer var det geniala sättet han bevisade att det måste finnas någon kod som kan producera felfria dataöverföringar ända upp till en kanals kapacitet.
För att förstå hur en felkorrigerande kod fungerar, överväg någon som försöker skicka ett fyrabitars meddelande över en bullrig kanal. Om bruset får en av bitarna att vända till sin motsats, har mottagaren inget sätt att veta att ett fel har inträffat. Att bara upprepa meddelandet, så att 0011 blir 00110011, löser det problemet: nu, om en bit vänder till sin motsats, vet mottagaren att det finns ett fel, eftersom de två versionerna av meddelandet inte matchar. Men det är omöjligt att säga vilken som är rätt. Ett bättre sätt att koda meddelandet kan använda de fyra extra bitarna för att representera information om meddelandebitarna: den femte biten kan till exempel berätta om de två första bitarna i meddelandet har samma eller olika värden; den sjätte biten kunde göra samma sak för bit tre och fyra, den sjunde för bit ett och tre och den åttonde för bit två och fyra. Om en av de fyra första bitarna vänds, kan de fyra sista identifiera den; om en av de fyra sista bitarna vänds kan de andra tre förmedla tillräckligt med information för att kompensera för det.
Shannons papper undviker dock alla sådana idisslande om hur man faktiskt konstruerar koder. Istället närmar det sig konceptet med felkorrigering genom att statistiskt analysera de allmänna egenskaperna hos koder som är valda helt slumpmässigt. För att få en känsla av hans tillvägagångssätt kan det hjälpa att se hur det kan tillämpas på våra hypotetiska åttabitarssekvenser som kodar fyrabitarsmeddelanden.
Det finns 16 möjliga fyra-bitars meddelanden, och Shannons metod skulle tilldela var och en av dem sitt eget slumpmässigt utvalda åttabitars serienummer - dess kodord. Mottagaren, liksom avsändaren, skulle ha en kodbok som korrelerar de 16 möjliga fyrabitarsmeddelandena med de 16 slumpmässiga åttabitarskodorden. Eftersom det finns 256 möjliga sekvenser om åtta bitar, finns det 240 som inte visas i kodboken. Någon som tar emot en av dessa 240 sekvenser kommer att veta att ett fel har smugit sig in i datan. Men så länge de 16 tillåtna kodorden skiljer sig tillräckligt mycket från varandra, finns det sannolikt bara ett som kommer närmast den korrupta sekvensen. Till exempel, om 00000001 och 11111110 båda är giltiga kodord men 00000011 inte är det, kan någon som tar emot sekvensen 00000011 dra slutsatsen att det avsedda kodordet var mycket mer sannolikt att vara 00000001 än 11111110.
I verkligheten är det naturligtvis ingen som är orolig för att sända meddelanden på bara fyra bitar. Men genom att använda statistisk analys kunde Shannon dra slutsatser om kodade meddelanden av vilken längd som helst, skickade över kanaler med vilken mängd brus som helst. I synnerhet kunde han noggrant kvantifiera både graden av skillnad mellan slumpmässigt valda kodord och sannolikheten för att en korrupt sekvens skulle likna endast ett av dem. Medan sannolikheten att två åttabitarssekvenser kommer att vara lika är relativt hög, visade Shannon att när kodord blir längre, minskar chanserna för likhet exponentiellt. Faktum är att ett av hans mest häpnadsväckande resultat var att för långa meddelanden kommer de flesta slumpmässigt tilldelade kodord att vara nästan så olika från varandra som det är möjligt för dem att vara. Det betyder att nästan vilket kodningsschema som helst – vilket som helst sätt att generera dessa ord – skulle tillåta felfri överföring över en bullrig kanal nära den maximala hastigheten.
Det krävdes mycket intuition att tro att en helt slumpmässig kod i genomsnitt kan vara en ganska bra kod, säger David Forney, SM '63, ScD '65, en tidigare vicepresident för Codex Corporation och Motorola som återvände till MIT 1996 som adjungerad professor. Det visar sig att det drastiskt förenklar analysen, för nu kan du göra en genomsnittlig fallanalys. Forney pausar ett ögonblick och tillägger sedan: För att inte säga att det var helt enkelt: han var tvungen att uppfinna åtminstone några satser, om inte grenar av matematiken. Men Gallager håller med. Om Shannons uppsats från 1948 säger han: Efter att du studerat det i två år verkar det väldigt enkelt. Så många människor kommer att säga till dig: 'Det är verkligen väldigt enkelt.' Och när du har förstått det är det så.
En oemotståndlig utmaning
Shannons matematiska beskrivning av information hade många konsekvenser. Hans papper från 1948 introducerade också idén om datakomprimering, eller att representera samma information med färre bitar; komprimering är det som låter program som WinZip eller StuffIt krympa filer så att de inte överbelasta e-postservrar, och det används för att spara utrymme på hårddiskar. Informationsteorin satte också studiet av kryptografi på en säkrare matematisk grund; Galager tror faktiskt att det var Shannons kryptografiska arbete under krigstid på Bell Labs som ledde honom till hans nya uppfattning om kommunikation.
När Shannon återvände till MIT hade han dock börjat känna att entusiasmen kring hans teori översteg till och med dess betydande förtjänster. I en artikel från 1956 kallad The Bandwagon, citerade han försök att tillämpa informationsteori på områden som biologi, psykologi, lingvistik, fundamental fysik, ekonomi, organisationsteorin och många andra och åtog sig att injicera en ton om måttfullhet i denna situation.
Shannons avsmak för rampljuset gränsade till ensamhet. Enligt Joel West '79, en professor vid San José State Universitys College of Business som skriver en bok om utvecklingen av informationsteori, gav Shannon endast råd till sju doktorander under sina 22 år vid MIT. Han var ganska blyg och pensionär, så om man ville få honom som handledare fick man verkligen vara ganska aggressiv, säger Gallager. Jag var blyg och pensionerade mig också och hade inte tillräckligt med självförtroende för att ens gå in och prata med killen.
Som lärare hade Shannon lite tålamod för de bekantas trötta. Han var mycket mer intresserad av det nya än av det gamla, säger Elwyn Berlekamp '62, SM '62, PhD '64, professor emeritus i matematik vid University of California, Berkeley, som (med Gallager) var medförfattare till Shannons slutgiltigt publicerat dokument.
Han undervisade inte så mycket, säger Gallager. Men när han undervisade var det som att hålla forskningssamtal. Jag minns en gång han höll en kurs, som var cirka 25 föreläsningar under terminen, och varje föreläsning var ett nytt forskningsresultat. Han skulle göra dem en efter en och misslyckades aldrig med att komma på något intressant. Det var en riktigt fantastisk period.
Shannon var, enligt min mening, lite malplacerad i akademin, säger James L. Massey, SM ’60, PhD ’62, informationsteoretiker och professor emeritus vid ETH Zürich. Hans verkliga genre var att vara en oberoende forskare och göra saker på sitt eget högst individualistiska sätt.
Det kan också vara så att Shannon helt enkelt var obekväm med beundran. Berlekamp minns när IEEE Information Theory Society bjöd in Shannon att hålla en föreläsning och ta emot sitt första Shannon Award i Israel 1973. Jag har aldrig sett någon med fler fjärilar än honom, säger han. Fem minuter innan samtalet ska börja är han i baren och han är ganska deprimerad. Han är verkligen rädd för att gå upp på scenen och göra alla besvikna. För naturligtvis förväntar de sig Gud, vilket är sant, och han vet att han inte kan prestera som Gud.
Men om Shannon sällan var en direkt mentor till unga studenter inom informationsteori, hade han ställt dem till en oemotståndlig utmaning. Slumpmässig kodning skulle aldrig fungera i praktiken: storleken på Shannons hypotetiska kodbok fördubblades för varje ytterligare bit i meddelandet. Kodboken för ett enda 1 000-bitars paket med data som färdas över Internet skulle kräva fler poster än det finns atomer i universum. Men vilken mer praktisk kodningsmekanism som helst – som att upprepa det ursprungliga meddelandet eller lägga till extra bitar som beskrev meddelandebitar – var motsvarigheten till något slumpmässigt kodningsschema, eftersom det skulle generera samma kodord. Och genom att visa att de allra flesta slumpmässiga kodningsscheman var kapacitetsnärmande, gav Shannon hopp om att ett av de praktiska också var det.
Gäckande koder
Istället för att använda en kodbok för att matcha kodord och meddelanden, skulle ett praktiskt kodningsschema tillhandahålla ett sätt att extrahera meddelandet från kodorden beräkningsmässigt. En serie matematiska operationer skulle, med hög sannolikhet för noggrannhet, kunna identifiera och korrigera fel i en eventuellt korrupt bitsekvens som tas emot över en brusig kanal.
Det är en av särdragen med felkorrigerande koder att en bra kodningsalgoritm inte nödvändigtvis innebär en bra avkodningsalgoritm. Med hjälp av statistiska analyser som liknar Shannons, kunde kodningsteoretiker visa att en given kod var kapacitetsnärmande - att den skulle maximera skillnaden mellan kodord. Men det betydde inte att de hade ett effektivt sätt att avkoda det.
Mellan publiceringen av Shannons artikel och början av 1990-talet föreslog forskare bättre och bättre koder och även bättre och bättre avkodningsalgoritmer. Men en praktisk kapacitetsnärmande kod förblev svårfångad. Det brukade finnas ett talesätt bland kodningsteoretiker, säger Forney, att nästan vilken kod som helst är bra – förutom alla de vi kan tänka oss.
Koderna som Gallager presenterade i sin doktorsavhandling från 1960 var ett försök att bevara en del av slumpmässigheten i Shannons hypotetiska system utan att offra avkodningseffektiviteten. Liksom många tidigare koder använde Gallager så kallade paritetsbitar, som indikerar om någon annan grupp av bitar har jämna eller udda summor. Men tidigare koder genererade paritetsbitarna på ett systematiskt sätt: den första paritetsbiten kan indikera om summan av meddelandebitarna ett till tre var jämnt; nästa paritetsbit kan göra samma sak för meddelandebitar två till fyra, den tredje för bitar tre till fem, och så vidare. I Gallagers koder, däremot, var korrelationen mellan paritetsbitar och meddelandebitar slumpmässig: den första paritetsbiten kan beskriva, säg, summan av meddelandebitarna 4, 27 och 83; nästa kan göra samma sak för meddelandebitarna 19, 42 och 65.
Gallager kunde matematiskt visa att för långa meddelanden var hans pseudo-slumpmässiga koder kapacitetsnärmande. Förutom att vi visste andra saker som var kapacitetsnärmande också, säger han. Det var aldrig en fråga om vilka koder som var bra. Det var alltid en fråga om vilka typer av avkodningsalgoritmer man kunde tänka ut.
Det var där Gallager fick sitt genombrott. Hans koder använde iterativ avkodning, vilket innebar att avkodaren skulle passera genom data flera gånger, vilket gjorde allt mer raffinerade gissningar om identiteten för varje bit. Om, till exempel, paritetsbitarna beskrev tripletter av bitar, kan tillförlitlig information om två godtyckliga bitar förmedla information om en tredje. Gallagers iterativa avkodningsalgoritm är den som används oftast idag, inte bara för att avkoda sina egna koder utan, ofta, för att avkoda turbokoder också. Det har också funnit tillämpning i den typ av statistiska resonemang som används i många artificiell intelligenssystem.
Iterativa tekniker innebär att göra en första gissning av vad en mottagen bit kan vara och ge den en vikt efter hur pålitlig den är, säger Forney. Då kanske du får mer information om det eftersom det är inblandat i paritetskontroller med andra bitar, och så det ger dig en förbättrad uppskattning av dess tillförlitlighet. I slutändan, säger Forney, bör gissningarna konvergera mot en konsekvent tolkning av alla bitar i meddelandet.
Även om Gallager inte hade kunnat ta modet att be Shannon att vara hans rådgivare, säger han att han pratade med Shannon tre eller fyra gånger medan han skrev sin avhandling. Förutom att prata med Claude tre eller fyra gånger var som att prata med de flesta 50 gånger, säger han. Han var någon som verkligen fångade idéerna väldigt, väldigt snabbt. Han var inte bra på alla tekniska detaljer. Men för att se strukturen på något, för att se varför det borde fungera och för att se vad som kan göra det bättre – ja, han var verkligen den smartaste personen jag någonsin träffat.
Ändå förutsåg inte Shannon framgången med Gallagers koder. Jag minns att han tyckte att de var intressanta, men jag hade inte en känsla av att han var upphetsad av dem, säger Gallager. Han förstår varför. Gallagers koder närmade sig kanalkapacitet när de blev längre; men när de blev längre, blev avkodningsprocessen också mer komplex – alldeles för komplex för dåtidens datorer. Kodningsforskare visste förstås att datorer skulle förbättras. Men ingen visste vems koder dessa förbättringar skulle gynna.
Icke desto mindre anställde MIT omedelbart Gallager som fakultetsmedlem på grund av sin avhandling. Under de efterföljande åren, medan hans eget kodningsschema försvann i dunkel, undervisade och handlade han en våg av briljanta studenter – inklusive Massey, Forney och Berlekamp – vars bidrag till kodningsteorin hade mer omedelbara praktiska konsekvenser än hans egna.
Gallager verkar dock lika oberörd av den långa försummelsen av sina koder som han gör av deras senaste väckelse – kanske för att han alltid antog långsikten. Han har en förmåga att uppfinna saker som ligger och vilar i tiotals år tills folk plötsligt inser att det är ganska bra grejer, säger Vincent Chan '71, MS '71, EE '72, PhD '74, en professor i elektroteknik som fortfarande visar upp hans skrivbord dörrskylten från kontoret han en gång delade med Shannon. Chan minns ett besök nyligen i ett stort mjukvaruföretags labb, där en forskare skröt med en ny komprimeringsteknik som skulle göra det möjligt för videofiler att ta upp bara en hundradel så mycket minne som de gör nu. Chan kände sig tvungen att påpeka att Gallager hade introducerat tekniken 1974. Många av dessa idéer tar ganska lång tid att tänka igenom, säger han, och när man tänker igenom dem finns det många, många alternativ. . Och man måste verkligen tänka mycket noga och kanske över en längre tid innan man kommer på vilken som är den rätta. Bob gör det mycket.
Muriel Médard ’89, ’90, MS ’91, ScD ’95, en informationsteoretiker vid Research Lab of Electronics, håller med. Bob sprang inte runt och försökte publicera och se till att han inte blev scooped, säger hon. Till exempel minns Médard ett samtal mellan Gallager och en framstående yngre informationsteoretiker, som i sin beskrivning av sitt eget arbete citerade en nyligen bevisad teorem som den förlitade sig på. Bob börjar rota igenom saker, som han gör, säger Médard. Så småningom tog han fram en trasig kopia av ett av sina egna papper. Han hade det här teensy-weensy lilla beviset, säger Médard. Och det var som en fotnot. En tjock fotnot, men en fotnot. ’Döpte de det till?’ ’Ja, Bob, det är ett stort teorem nu.’
Idag ligger Gallagers koder till grund för de tillvägagångssätt som kommer närmast den maximala datahastigheten för en given kommunikationskanal – närmare än turbokoder. Förutom deras applikationer inom telekommunikation, börjar de ersätta de äldre koder som används för att skydda data i hårddiskar och andra lagringsenheter.
För personer som Forney, som var på MIT under vad han kallar kodningsteorin för guldåldern, är det lite bitterljuvt att utmaningen från Shannons tidning från 1948 har möts. De av oss som kan och älskar kodning är ovilliga att säga att problemet är helt löst, säger Forney. Men det är sant att de flesta har gått vidare till andra saker.
Från 1950 till 1965 var MIT grogrund för informationsteorin, säger Joel West. Det var verkligen en guldålder. 