211service.com
Codice Quest
Nel 1948, il mondo era ancora un luogo analogico. Candid Camera e Ed Sullivan stavano appena iniziando la loro lunga corsa in TV; Il programma radiofonico di Jack Benny ha avuto decine di milioni di ascoltatori. Ma la cattiva ricezione era un dato di fatto. L'interferenza elettromagnetica, gli ostacoli fisici tra una torre di trasmissione e un ricevitore e altre fonti di ciò che gli ingegneri chiamano rumore di routine hanno interrotto i monologhi di Benny o le esibizioni degli ospiti di Sullivan. Nella maggior parte delle aree, almeno per alcune stazioni, le persone si sono rassegnate a immagini innevate o audio disturbato dall'elettricità statica.
Claude Shannon, 1948
Quello stesso anno, tuttavia, Claude Shannon, SM '40, PhD '40, pubblicò un documento fondamentale in cui dimostrava matematicamente che anche in presenza di molto rumore, era possibile trasmettere informazioni praticamente senza errori. Era un mondo analogico, ma la straordinaria conclusione di Shannon era il risultato della sua capacità di pensare in modo digitale. Le informazioni in qualsiasi mezzo, sosteneva Shannon, potevano essere rappresentate usando cifre binarie, o bit, una parola che il suo articolo ha introdotto al mondo. Mentre il rumore in un canale di comunicazione può corrompere i bit, ha spiegato, aggiungendo bit extra che sono correlati ai bit originali da un algoritmo noto, un codice di correzione degli errori, sarà possibile dedurre la sequenza originale.
Più rumoroso è il canale, più informazioni aggiuntive devono essere aggiunte per rendere possibile la correzione degli errori. E più informazioni extra sono incluse, più lenta sarà la trasmissione. Shannon ha mostrato come calcolare il minor numero di bit extra in grado di garantire un errore minimo e, quindi, la massima velocità con cui è possibile la trasmissione di dati senza errori. Ma non poteva dire come potrebbe essere uno schema di codifica pratico.
I ricercatori hanno trascorso 45 anni a cercarne uno. Alla fine, nel 1993, una coppia di ingegneri francesi ha annunciato una serie di codici - codici turbo - che hanno raggiunto velocità di trasmissione dati vicine al limite teorico di Shannon. La reazione iniziale è stata di incredulità, ma le successive indagini hanno convalidato le affermazioni dei ricercatori. Risultò anche un fatto ancora più sorprendente: codici buoni quanto i codici turbo, che si basavano persino sullo stesso tipo di trucco matematico, erano stati introdotti più di 30 anni prima, nella tesi di dottorato del MIT di Robert Gallager, SM ' 57, ScD '60. Dopo decenni di abbandono, i codici di Gallager hanno finalmente trovato applicazione pratica. Sono utilizzati nella trasmissione della TV satellitare e dei dati wireless e i chip dedicati alla loro decodifica possono essere trovati nei telefoni cellulari commerciali.
La nascita della teoria dell'informazione
Gallager arrivò al MIT nel 1956, lo stesso anno in cui Shannon stesso tornò come professore, dopo 15 anni ai Bell Labs. Ma non è stata la prospettiva di lavorare con Shannon che lo ha portato a scegliere il MIT a Yale, dove aveva anche fatto domanda per la scuola di specializzazione. Ero nell'esercito, per un incarico insignificante, e odiavo davvero quello che stavo facendo, dice Gallager, che ha insegnato al MIT per più di 40 anni dopo aver conseguito il dottorato e ancora consiglia gli studenti laureati come professore emerito nel Research Lab di Elettronica. Il MIT è iniziato una settimana prima di Yale. Ed ero così ansioso di lasciare l'esercito che quella era davvero la mia unica ragione per venire al MIT.
Gallager non era nemmeno sicuro di voler studiare la teoria dell'informazione, la nuova disciplina nascente dall'articolo di Shannon del 1948. Ma prima di entrare a far parte dell'Army Signal Corps, anche Gallager aveva lavorato per diversi anni ai Bell Labs, dove trascorreva tre giorni alla settimana in un'aula imparando gli ultimi progressi nell'ingegneria elettrica. Sebbene non avesse mai incontrato Shannon, quell'esperienza lo ha aiutato a riconoscere la portata del suo successo. L'ho visto solo come una specie di dio, dice Gallager.
In effetti, quando Shannon si unì alla facoltà del MIT, era una celebrità minore. Già nel 1953, un articolo sulla teoria dell'informazione sulla rivista Fortune aveva declamato: Non è esagerato dire che il progresso dell'uomo in pace e la sicurezza in guerra dipendono più da fruttuose applicazioni della teoria dell'informazione che da dimostrazioni fisiche, sia nelle bombe o nelle centrali elettriche, che la famosa equazione di Einstein funziona.
Ciò che ha catturato l'immaginazione del pubblico è stata l'idea che l'informazione in tutta la sua diversità – testo, audio, video – potesse essere ridotta a semplici sequenze di 1 e 0. I dispositivi digitali commerciali non esistevano ancora, quindi ha fatto impazzire le persone che 001001010101000101011101 potesse rappresentare parte di una sinfonia, o parte di un film, o un colore, o una riga di un libro. Ma come ha sottolineato Shannon nel suo articolo, il suo collega dei Bell Labs Ralph Hartley aveva avanzato un suggerimento simile 20 anni prima. L'aspetto del documento che ha affascinato, e continua ad affascinare, i colleghi ingegneri di Shannon è stato il modo ingegnoso in cui ha dimostrato che deve esistere un codice in grado di produrre trasmissioni di dati prive di errori fino alla capacità di un canale.
Per capire come funziona un codice di correzione degli errori, prendi in considerazione qualcuno che sta cercando di inviare un messaggio a quattro bit attraverso un canale rumoroso. Se il rumore fa sì che uno dei bit si capovolga nel suo opposto, il ricevitore non ha modo di sapere che si è verificato un errore. La semplice ripetizione del messaggio, in modo che 0011 diventi 00110011, risolve il problema: ora, se un bit si capovolge nel suo opposto, il ricevitore sa che c'è un errore, perché le due versioni del messaggio non corrispondono. Ma è impossibile dire quale sia corretto. Un modo migliore per codificare il messaggio potrebbe utilizzare i quattro bit extra per rappresentare le informazioni sui bit del messaggio: il quinto bit, ad esempio, potrebbe dirti se i primi due bit del messaggio hanno lo stesso valore o valori diversi; il sesto bit potrebbe fare lo stesso per i bit tre e quattro, il settimo per i bit uno e tre e l'ottavo per i bit due e quattro. Se uno dei primi quattro bit viene capovolto, gli ultimi quattro possono identificarlo; se uno degli ultimi quattro bit viene capovolto, gli altri tre possono trasmettere informazioni sufficienti per compensarlo.
L'articolo di Shannon, tuttavia, evita tali elucubrazioni su come costruire effettivamente i codici. Si avvicina invece al concetto di correzione degli errori analizzando statisticamente le proprietà generali di codici selezionati interamente a caso. Per avere un'idea del suo approccio, potrebbe essere utile vedere come potrebbe essere applicato alle nostre ipotetiche sequenze a otto bit che codificano messaggi a quattro bit.
Ci sono 16 possibili messaggi a quattro bit e il metodo di Shannon assegnerebbe a ciascuno di essi il proprio numero di serie a otto bit selezionato casualmente, la sua parola in codice. Il destinatario, come il mittente, avrebbe un codebook che correla i 16 possibili messaggi a quattro bit con le 16 parole di codice a otto bit casuali. Poiché ci sono 256 possibili sequenze di otto bit, ce ne sono 240 che non compaiono nel codebook. Qualcuno che riceve una di quelle 240 sequenze saprà che un errore si è insinuato nei dati. Ma finché le 16 parole in codice consentite sono abbastanza diverse l'una dall'altra, è probabile che ce ne sia solo una che si avvicina di più alla sequenza corrotta. Ad esempio, se 00000001 e 11111110 sono entrambe parole in codice valide ma 00000011 non lo è, allora qualcuno che riceve la sequenza 00000011 può concludere che la parola in codice prevista era molto più probabile che fosse 00000001 rispetto a 11111110.
Nella vita reale, ovviamente, nessuno si preoccupa di trasmettere messaggi di soli quattro bit. Ma utilizzando l'analisi statistica, Shannon è stata in grado di trarre conclusioni sui messaggi codificati di qualsiasi lunghezza, inviati su canali con qualsiasi quantità di rumore. In particolare, è stato in grado di quantificare rigorosamente sia il grado di differenza tra le parole in codice selezionate casualmente sia la probabilità che una sequenza corrotta assomigli solo a una di esse. Sebbene la probabilità che due sequenze a otto bit siano simili è relativamente alta, Shannon ha dimostrato che man mano che le parole in codice si allungano, le possibilità di somiglianza diminuiscono in modo esponenziale. In effetti, uno dei suoi risultati più sorprendenti è stato che per i messaggi lunghi, la maggior parte delle parole in codice assegnate casualmente saranno diverse l'una dall'altra quasi quanto è possibile che lo siano. Ciò significa che quasi qualsiasi schema di codifica, qualsiasi modo di generare quelle parole, consentirebbe una trasmissione senza errori attraverso un canale rumoroso vicino alla velocità massima.
Ci è voluta molta intuizione per pensare che un codice perfettamente casuale potesse essere in media un codice abbastanza buono, afferma David Forney, SM '63, ScD '65, un ex vicepresidente della Codex Corporation e Motorola che è tornato al MIT nel 1996 come professore a contratto. Si scopre che ciò semplifica drasticamente l'analisi, perché ora puoi fare un'analisi del caso medio. Forney si ferma un attimo, poi aggiunge, Per non dire che era del tutto semplice: doveva inventare almeno qualche teorema, se non rami della matematica. Ma Gallager è d'accordo. Dell'articolo di Shannon del 1948, dice: Dopo averlo studiato per due anni, sembra molto semplice. Così tante persone ti diranno: 'È davvero molto semplice'. E dopo averlo capito, lo è.
Una sfida irresistibile
La descrizione matematica delle informazioni di Shannon ha avuto molte ramificazioni. Il suo articolo del 1948 introdusse anche l'idea della compressione dei dati, o della rappresentazione delle stesse informazioni con meno bit; la compressione è ciò che consente a programmi come WinZip o StuffIt di ridurre i file in modo da non sovraccaricare i server di posta elettronica e viene utilizzata per risparmiare spazio nelle unità disco. La teoria dell'informazione pone anche lo studio della crittografia su basi matematiche più sicure; in effetti, Gallager crede che sia stato il lavoro crittografico di Shannon ai Bell Labs in tempo di guerra che lo ha portato alla sua nuova concezione della comunicazione.
Quando Shannon tornò al MIT, tuttavia, aveva cominciato a sentire che l'entusiasmo che circondava la sua teoria superava anche i suoi considerevoli meriti. In un articolo del 1956 intitolato The Bandwagon, citava i tentativi di applicare la teoria dell'informazione a campi come la biologia, la psicologia, la linguistica, la fisica fondamentale, l'economia, la teoria dell'organizzazione e molti altri e si impegnava a iniettare una nota di moderazione in questa situazione.
Il disgusto di Shannon per le luci della ribalta rasentava la solitudine. Secondo Joel West '79, professore al College of Business della San José State University che sta scrivendo un libro sullo sviluppo della teoria dell'informazione, Shannon ha consigliato solo sette studenti laureati durante i suoi 22 anni al MIT. Era piuttosto timido e riservato, quindi se volevi prenderlo come supervisore, dovevi davvero essere piuttosto aggressivo al riguardo, dice Gallager. Ero anche timido e riservato, e non avevo abbastanza fiducia in me stesso nemmeno per entrare e parlare con il ragazzo.
Come insegnante, Shannon aveva poca pazienza per la noia del familiare. Era molto più interessato al nuovo che al vecchio, dice Elwyn Berlekamp '62, SM '62, PhD '64, professore emerito di matematica all'Università della California, Berkeley, che (con Gallager) è stato coautore del libro di Shannon documento finale pubblicato.
Non ha insegnato molto, dice Gallager. Ma quando insegnava, era come tenere discorsi di ricerca. Ricordo che una volta tenne un corso, che era di circa 25 lezioni durante il semestre, e ogni lezione era un nuovo risultato di ricerca. Li faceva uno dopo l'altro e non mancava mai di inventare qualcosa di interessante. È stato un periodo davvero fantastico.
Shannon era, a mio parere, un po' fuori posto nel mondo accademico, afferma James L. Massey, SM '60, PhD '62, teorico dell'informazione e professore emerito all'ETH di Zurigo. Il suo vero genere era quello di essere un ricercatore indipendente e fare le cose nel suo modo altamente individualistico.
Può anche darsi che Shannon fosse semplicemente a disagio con l'adulazione. Berlekamp ricorda quando l'IEEE Information Theory Society invitò Shannon a tenere una conferenza e a ricevere il suo Shannon Award inaugurale in Israele nel 1973. Non ho mai visto nessuno con più farfalle di lui, dice. Cinque minuti prima dell'inizio del discorso, è al bar ed è piuttosto depresso. Ha davvero paura di salire sul palco e deludere tutti. Perché ovviamente si aspettano Dio, il che è vero, e lui sa che non può agire come Dio.
Ma se Shannon era raramente un mentore diretto per i giovani studenti di teoria dell'informazione, aveva posto loro una sfida irresistibile. La codifica casuale non funzionerebbe mai in pratica: la dimensione dell'ipotetico codebook di Shannon raddoppiava con ogni bit aggiuntivo nel messaggio. Il codice per un singolo pacchetto di dati da 1.000 bit che viaggia su Internet richiederebbe più voci di quanti siano gli atomi nell'universo. Ma qualsiasi meccanismo di codifica più pratico, come la ripetizione del messaggio originale o l'aggiunta di bit extra che descrivessero i bit del messaggio, era l'equivalente di uno schema di codifica casuale, in quanto generava le stesse parole di codice. E dimostrando che la stragrande maggioranza degli schemi di codifica casuale si avvicinava alla capacità, Shannon offriva la speranza che lo fosse anche uno di quelli pratici.
Codici Elusivi
Invece di utilizzare un codice per abbinare parole in codice e messaggi, uno schema di codifica pratico fornirebbe un modo per estrarre il messaggio dalle parole in codice in modo computazionale. Una serie di operazioni matematiche potrebbe, con un'elevata probabilità di accuratezza, identificare e correggere errori in una sequenza di bit eventualmente corrotta ricevuta su un canale rumoroso.
È una delle peculiarità dei codici di correzione degli errori che un buon algoritmo di codifica non implica necessariamente un buon algoritmo di decodifica. Utilizzando analisi statistiche simili a quelle di Shannon, i teorici della codifica sono stati in grado di dimostrare che un dato codice si avvicinava alla capacità, che avrebbe massimizzato la differenza tra le parole del codice. Ma ciò non significava che avessero un modo efficiente per decodificarlo.
Tra la pubblicazione dell'articolo di Shannon e i primi anni '90, i ricercatori hanno proposto codici sempre migliori e anche algoritmi di decodifica sempre migliori. Ma un codice pratico che si avvicinasse alla capacità rimaneva inafferrabile. C'era un detto tra i teorici del codice, dice Forney, che quasi tutti i codici sono buoni, tranne tutti quelli che ci vengono in mente.
I codici presentati da Gallager nella sua tesi di dottorato del 1960 erano un tentativo di preservare parte della casualità dell'ipotetico sistema di Shannon senza sacrificare l'efficienza di decodifica. Come molti codici precedenti, Gallager usava i cosiddetti bit di parità, che indicano se qualche altro gruppo di bit ha somme pari o dispari. Ma i codici precedenti generavano i bit di parità in modo sistematico: il primo bit di parità poteva indicare se la somma dei bit di messaggio da uno a tre era pari; il successivo bit di parità potrebbe fare lo stesso per i bit del messaggio da due a quattro, il terzo per i bit da tre a cinque e così via. Nei codici di Gallager, al contrario, la correlazione tra bit di parità e bit di messaggio era casuale: il primo bit di parità potrebbe descrivere, ad esempio, la somma dei bit di messaggio 4, 27 e 83; il successivo potrebbe fare lo stesso per i bit di messaggio 19, 42 e 65.
Gallager è stato in grado di dimostrare matematicamente che per i messaggi lunghi, i suoi codici pseudo-casuali si avvicinavano alla capacità. Tranne che sapevamo anche altre cose che si avvicinavano alla capacità, dice. Non era mai una questione di quali codici fossero buoni. Era sempre una questione di che tipo di algoritmi di decodifica si poteva escogitare.
Fu lì che Gallager fece la sua svolta. I suoi codici usavano la decodifica iterativa, il che significa che il decodificatore avrebbe passato i dati più volte, facendo ipotesi sempre più raffinate sull'identità di ciascun bit. Se, ad esempio, i bit di parità descrivevano triplette di bit, allora informazioni affidabili su due bit qualsiasi potrebbero trasmettere informazioni su un terzo. L'algoritmo di decodifica iterativa di Gallager è quello più comunemente usato oggi, non solo per decodificare i propri codici ma, spesso, anche per decodificare i codici turbo. Ha anche trovato applicazione nel tipo di ragionamento statistico utilizzato in molti sistemi di intelligenza artificiale.
Le tecniche iterative implicano fare una prima ipotesi su cosa potrebbe essere un bit ricevuto e dargli un peso in base a quanto è affidabile, dice Forney. Quindi forse ottieni maggiori informazioni a riguardo perché è coinvolto nei controlli di parità con altri bit e quindi questo ti dà una stima migliore della sua affidabilità. In definitiva, afferma Forney, le ipotesi dovrebbero convergere verso un'interpretazione coerente di tutti i bit del messaggio.
Sebbene Gallager non sia stato in grado di trovare il coraggio di chiedere a Shannon di essere il suo consigliere, dice di aver parlato con Shannon tre o quattro volte mentre scriveva la sua tesi. Tranne che parlare con Claude tre o quattro volte era come parlare con la maggior parte delle persone 50 volte, dice. Era qualcuno che ha davvero catturato le idee molto, molto velocemente. Non era eccezionale in tutti i dettagli tecnici. Ma per vedere la struttura di qualcosa, per capire perché dovrebbe funzionare e per vedere cosa potrebbe renderlo migliore, beh, era sicuramente la persona più intelligente che abbia mai incontrato.
Tuttavia, Shannon non prevedeva il successo dei codici di Gallager. Il mio ricordo è che pensava che fossero interessanti, ma non avevo la sensazione che fosse eccitato da loro, dice Gallager. Capisce perché. I codici di Gallager si avvicinavano alla capacità del canale man mano che si allungavano; ma man mano che si allungavano, anche il processo di decodifica diventava più complesso, troppo complesso per i computer dell'epoca. I ricercatori di codifica sapevano, ovviamente, che i computer sarebbero migliorati. Ma nessuno sapeva di chi fossero i codici che quei miglioramenti avrebbero favorito.
Tuttavia, il MIT assunse immediatamente Gallager come membro di facoltà sulla base della sua tesi. Negli anni successivi, mentre il suo schema di codifica languiva nell'oscurità, insegnò e fece da mentore a un'ondata di studenti brillanti, tra cui Massey, Forney e Berlekamp, i cui contributi alla teoria dei codici ebbero implicazioni pratiche più immediate del suo.
Gallager, tuttavia, non sembra turbato dal lungo abbandono dei suoi codici quanto dal loro recente revival, forse perché ha sempre avuto una visione lungimirante. Ha l'abilità di inventare cose che restano dormienti per decine di anni fino a quando la gente improvvisamente si rende conto che è roba piuttosto buona, dice Vincent Chan '71, MS '71, EE '72, PhD '74, un professore di ingegneria elettrica che ancora mostra di la sua scrivania la targa dell'ufficio che una volta condivideva con Shannon. Chan ricorda una recente visita ai laboratori di un'importante società di software, dove un ricercatore si vantava di una nuova tecnica di compressione che avrebbe consentito ai file video di occupare solo un centesimo della memoria di quanto fanno ora. Chan si è sentito obbligato a sottolineare che Gallager aveva introdotto la tecnica nel 1974. Molte di queste idee richiedono un po' di tempo per essere riflesse, dice, e nel momento in cui le stai pensando, ci sono molte, molte opzioni . E devi davvero pensare molto attentamente e forse per un lungo periodo di tempo prima di capire qual è quello giusto. Bob lo fa spesso.
Muriel Médard '89, '90, MS '91, ScD '95, un teorico dell'informazione nel Research Lab of Electronics, è d'accordo. Bob non correva in giro cercando di pubblicare e assicurarsi di non essere preso in giro, dice. Ad esempio, Médard ricorda una conversazione tra Gallager e un eminente teorico dell'informazione più giovane, che nel descrivere il proprio lavoro ha citato un teorema recentemente dimostrato su cui si basava. Bob inizia a rovistare tra le cose, come fa lui, dice Médard. Alla fine ha prodotto una copia sbrindellata di uno dei suoi documenti. Aveva questa piccola prova da ragazzina, dice Médard. Ed era come una nota a piè di pagina. Una nota a piè di pagina, ma una nota a piè di pagina. 'L'hanno chiamato?' 'Sì, Bob, è un teorema importante ora.'
Oggi, i codici di Gallager sono alla base degli approcci che si avvicinano di più alla velocità dati massima per un determinato canale di comunicazione, persino più vicino dei codici turbo. Oltre alle loro applicazioni nelle telecomunicazioni, stanno iniziando a sostituire i vecchi codici utilizzati per proteggere i dati nelle unità disco e in altri dispositivi di archiviazione.
Per persone come Forney, che erano al MIT durante quella che lui chiama l'età d'oro della teoria dei codici, il fatto che la sfida lanciata dall'articolo di Shannon del 1948 sia stata vinta è un po' agrodolce. Quelli di noi che conoscono e amano la programmazione sono riluttanti a dire che il problema è stato completamente risolto, afferma Forney. Ma è vero che la maggior parte delle persone è passata ad altre cose.
Dal 1950 al 1965, il MIT è stato il focolaio della teoria dell'informazione, afferma Joel West. Era davvero un'età dell'oro. 