L’ALGORITMO DI VITERBI
Da profugo a padre dei cellulari: una vita straordinaria quella di Andrea Viterbi, ingegnere, scienziato, imprenditore, ma soprattutto apripista degli studi che hanno guidato l’evoluzione delle telecomunicazioni dall’analogico al digitale. È suo l’algoritmo che sta alla base della trasmissione dati del GSM (lo standard di telefonia mobile attualmente più diffuso al mondo) e della tecnologia CDMA, ma suo è anche lo studio sui sistemi telemetrici che ha permesso il lancio dei primi satelliti Explorer. La formula che l’ha reso famoso è una sorta di scudo matematico contro le interferenze che ancora oggi consente a milioni di cellulari di comunicare tra loro. Con la sua indole schiva e aliena da esibizionismi, ci racconta la lunga ed emozionante avventura di un rifugiato ebreo italiano in America.
di Anna Guida
Era il 27 agosto 1939 quando Andrea, quattro anni e mezzo, mise piede per la prima volta negli Stati Uniti, al termine di una traversata lunga 12 giorni. Una scelta obbligata per la famiglia di Achille Viterbi, oculista ebreo bergamasco cui le leggi razziali stavano progressivamente negando lavoro e diritti. Cinque giorni dopo, il primo settembre, l’invasione nazista della Polonia avrebbe segnato l’inizio della II guerra mondiale. E a molti ebrei italiani rimasti in patria sarebbe toccato un destino ben peggiore.
D. Cominciamo da lontano. Dalla sua infanzia a Boston.
R. Furono anni durissimi, soprattutto per i miei genitori. Mio padre nel marzo 1939 era stato licenziato a causa delle leggi razziali dalla posizione di Primario di Oftalmologia agli Ospedali Riuniti di Bergamo, al culmine di una brillante carriera. Arrivato a Boston, si trovò a quasi sessant’anni senza un lavoro in un paese straniero di cui non conosceva la lingua. Sostenuto da mia madre, riuscì a crearsi una modesta pratica in città curando gli occhi degli immigranti italiani. Mia mamma, una donna dagli agiati trascorsi borghesi, per arrotondare lo stipendio di papà si mise a fare la sarta. Per me, che avevo solo quattro anni, ambientarmi in quel nuovo mondo fu molto più semplice. Quasi un gioco.
D. Pensa che la consapevolezza delle discriminazioni e delle ingiustizie subite dalla sua famiglia sia stato un fattore motivazionale in più nella sua brillante carriera scolastica, universitaria, e poi professionale?
R. Queste considerazioni, che sono in grado di affrontare con lucidità a distanza di mezzo secolo, non mi erano certamente chiare negli anni della mia infanzia e gioventù. Certamente sapevo di essere diverso dai miei compagni e in più di fare parte di una comunità minuscola di ebrei italiani, e quindi non facilmente accettati né dai milioni di ebrei provenienti dall’Europa orientale e centrale né dai milioni di emigrati italiani, cattolici e in prevalenza meridionali. Questa consapevolezza mi portò a concentrarmi molto sugli studi e a far di tutto per diventare pienamente americano.
Ma non posso dire che feci tutto questo per un sentimento di “rivalsa”. Ero guidato più che altro dalla determinazione e dalla passione. Soprattutto per la matematica: già a 10 anni sognavo di diventare ingegnere!
Fino al termine del liceo ebbi come principale maestro mio padre, un uomo di grande cultura e ampia visione. Insieme a mia madre, mi instillò le basi della cultura italiana. Le nostre risorse economiche erano molto limitate, ma grazie agli eccellenti risultati conseguiti all’esame finale del liceo mi conquistai una borsa di studio e l’ingresso al Massachusetts Institute of Technology, considerato allora e oggi il tempio dell’innovazione tecnologica. Entrai in contatto con geniali precursori dell’informatica come Norbert Wiener e Claude Shannon. In particolare cominciai a interessarmi agli studi di quest’ultimo, come la “teoria matematica delle comunicazioni” o il concetto di spread spectrum (spettro allargato).
D. Nel 1957, la laurea in ingegneria elettronica. E poi?
R. Entrai al Jet Propulsion Laboratory di Pasadena e, quindi, anche in quella speciale declinazione della guerra fredda che fu, in quegli anni, la lotta per la leadership spaziale. Il nostro gruppo di ricerca passò presto sotto il controllo della NASA. Contribuii al lancio del primo satellite Usa, Explorer, risolvendo due importanti problemi di comunicazione: la debolezza dei segnali ricevuti dal satellite, dovuta alla distanza, e il continuo cambiamento della loro frequenza, prodotto dal movimento orbitale. Fu qui che cominciò la mia “ossessione” per la comunicazione digitale e che decisi di farne l’argomento della mia tesi di dottorato, discussa alla University of Southern California (USC) nel 1962.
D. Fu poi la UCLA, altra grande università di Los Angeles, a offrirle subito dopo la possibilità di intraprendere la carriera accademica?
R. Sì, nel 1963 la UCLA mi affidò il corso di comunicazione digitale e teoria dell’informazione. Proprio dalle sinergie di quegli anni tra attività di ricerca e di insegnamento nacque “l’algoritmo probabilistico non sequenziale” che prese il mio nome.
D. Come nacque questa sua intuizione?
R. Come spesso accade nella ricerca scientifica, ciò che si trova non è necessariamente ciò che si stava cercando. L’algoritmo nacque da un’esigenza di semplificazione, anche a scopo didattico, di una teoria a cui stavo lavorando.
Fu originariamente concepito per la trasmissione dati nello spazio, dove bisogna tener conto di condizioni avverse che possono produrre variazioni casuali del segnale. Questo problema viene normalmente affrontato utilizzando codici che introducono un’opportuna ridondanza per proteggere i segnali da confusione. Una classe importante è costituita dai cosiddetti codici convoluzionali, in cui si prevede che i dati originali vengano trasformati e ripetuti tramite un’opportuna operazione matematica. Poiché la codifica convoluzionale rende il flusso di dati particolarmente interdipendente, la decodifica richiede calcoli molto complessi. L’algoritmo di Viterbi interviene proprio in fase di decodifica per determinare quale sequenza di dati trasmessi sia la più probabile causa del flusso osservato in uscita. Calcola la probabilità dei diversi flussi in ingresso in modo ricorsivo, eliminando in blocco, ad ogni passo, quelli di probabilità minore. Permette quindi una notevole riduzione della complessità delle operazioni di calcolo necessarie.
D. Come fu accolto dalla comunità scientifica?
R. All’epoca, sembrò un’intuizione molto potente, ma nessuno riusciva a immaginare che avrebbe trovato applicazione anche fuori dall’ambito aerospaziale. Invece, siccome il modello stocastico cui si applica è sufficientemente generale da adeguarsi alla descrizione di fenomeni di diverso genere, man mano che lo sviluppo scientifico-tecnologico lo permetteva, l’uso dell’algoritmo si è esteso a molti altri campi: le telecomunicazioni, la biologia computazionale, la linguistica computazionale, il riconoscimento vocale.
D. Fu lei stesso a intravedere le grandi potenzialità della sua scoperta e a dedicarsi allo sviluppo di alcune sue applicazioni commerciali. Forse si può dire che lei mostrò una dote di cui scienziati e ricercatori sono spesso sprovvisti: la capacità di tramutare le scoperte scientifiche in “prodotti”, in applicazioni suscettibili di sfruttamento economico. Mi sbaglio?
R. Per indole, non riesco a fermarmi allo stadio della formulazione teorica: ogni volta che raggiungo un risultato scientifico per me comincia un’altra sfida, quella di tramutare l’idea innovativa in tecnologia, prodotto. Fu questa esigenza a spingermi verso l’attività imprenditoriale: nel 1968 fondai la società Linkabit, insieme a due colleghi “accademici”, Irwin Jacobs e Leonard Kleinrock. La Linkabit sviluppava studi e simulazioni riguardanti l’algoritmo di Viterbi per conto di agenzie governative, e col tempo si procurò importanti commesse. Negli anni ‘70, vinse un appalto per la realizzazione delle apparecchiature per le comunicazioni radio tra le stazioni di terra e l’intera flotta dello U.S. Air Force’s Strategic Air Command. La tecnologia sviluppata dalla Linkabit per questa commessa fece da precursore alle attuali “Wireless Wide Area Networks” nonché ai modem WiFi attualmente implementati nei computer portatili.
D. Poi ancora un’altra sfida: la Qualcomm.
R. Nel 1985 fondai con Jacobs e altri cinque collaboratori della Linkabit un’altra società, la Qualcomm, una delle aziende leader nel settore delle comunicazioni wireless, nota agli utenti della rete per aver prodotto Eudora, noto programma di posta elettronica. Alla Qualcomm, mi trovai ad affrontare l’esigenza della “multiplazione”, ossia la trasmissione contemporanea di informazioni da parte del più elevato numero possibile di mezzi di trasporto, senza interferenze di trasmissioni. Lavorai allo studio e al raffinamento di una forma di multiplazione innovativa, il CDMA (Code Division Multiple Access), che prometteva prestazioni nettamente superiori rispetto a quelle delle tecniche tradizionali. In quegli anni la telefonia cellulare di prima generazione, basata sui segnali analogici, era in fase di rapidissima espansione. Contemporaneamente era in corso la fase di standardizzazione riguardante la seconda generazione (digitale), nella quale Qualcomm irruppe proponendo l’adozione del CDMA quale alternativa alle tecniche concorrenti allora in gara, ovvero FDMA (Frequency Division Multiple Access) e TDMA (Time Division Multiple Access). Nel 1993 il CDMA fu riconosciuto come standard per la telefonia cellulare di seconda generazione e due anni dopo la Qualcomm produsse il primo cellulare con questo sistema di comunicazione. Dal 1995 al 2006 ne sono stati venduti più di 300 milioni.
D. Viterbi, non si ferma mai?
R. Ufficialmente mi sono già fermato: nel 2000, compiuti i 65 anni, sono andato in pensione.
D. Ufficialmente... ma in realtà?
R. Beh, sono stato chiamato a far parte della commissione per le tecnologie informatiche della Casa Bianca. Continuo a tenere lezioni in varie università del mondo. Con mia figlia, anche lei ingegnere, ho fondato un gruppo investimenti su compagnie emergenti. Tutto qui.
D. “Tutto qui”? Non mi sembrano inezie! E poi mi risulta che abbia anche dato vita a una fondazione a scopo filantropico...
R. Sì, attraverso la “Viterbi Family Foundation” io e mia moglie Erna sosteniamo molte istituzioni di istruzione e ricerca, tra le quali il liceo che ho frequentato da ragazzo, il MIT, il Technion Israel Institute of Technology... Non le ho detto che mi sono iscritto all’università grazie a una borsa di studio? Come posso non impegnarmi affinché tanti altri giovani di talento abbiano le mie stesse opportunità?
VITERBI’S ALGORITHM
From refugee to father of mobile phones: an extraordinary life, that of Andrea Viterbi, engineer, scientist, entrepreneur but especially forerunner of the studies that have guided the evolution of telecommunications from analogical to digital. He is the creator of the algorithm that is at the basis of the transmission data of GSM (the mobile telephony standard currently most diffused in the world) and of the CDMA technology, but his is also the telemetric system study that has enabled the launch of the first Explorer satellites. The formula that has made him famous is a sort of mathematical shield against interferences that still today allows million portable phones communicate one another. With his shy and exhibitionism-free nature, he tells us his long and exciting adventure of Italian Jew refugee in America.
by Anna Guida
It was August 27th 1939 when Andrea, four and a half years old, set foot for the first time in the United States, at the end of a crossing that had lasted 12 days.
A compulsory choice for the family of Achille Viterbi, Jew oculist from Bergamo to whom the race laws were progressively denying job and rights.
Five days later, on September 1st, the Nazi invasion of Poland marked the beginning of the Second World War.
And lots of Italian Jews remained in their homeland had a much worse destiny.
D. Let’s start from a distant time. From your childhood in Boston.
R. They were very hard years, especially for my parents. In March 1939 my father was dismissed because of racial laws from his position of Primary of Ophthalmology at “Ospedali Riuniti” of Bergamo, at the top of a brilliant career. When he arrived in Boston, he was almost sixty years old and unemployed in a foreign country of which he did not know the language. Supported by my mother, he succeeded in creating a modest profession in the city, taking care of the eyes of Italian immigrants.
My mother, a woman of wealthy bourgeois past, for supplementing dad’s salary, began making the seamstress. For me, who was only four years old, to settle in that new world was much simpler. Almost a game.
D. Do you think that the awareness of the discriminations and of the injustices suffered by your family has been a factor that has further motivated your brilliant scholastic, university and professional career?
R. These remarks, which I can face with clarity half century later, were not certainly evident to me in the years of my childhood and youth. I certainly knew that I was different from my mates and besides I was part of a tiny community of Italian Jews, therefore not easily accepted either by million Jews coming from Eastern and Central Europe or by million Italian immigrants, catholic and prevailingly southern. This awareness led me to focus on studies very much and to do everything possible to become fully American.
But I cannot say that I did all that driven by a feeling of “revenge”. I was rather guided by determination and passion. Especially for mathematics: when I was 10 years old, I already dreamt of becoming engineer!
Until the end of the lyceum, my main teacher was my father, a man of great culture and farsightedness. Together with my mother, he instilled the basics of the Italian culture to me. Our economic resources were very scarce but thanks to the excellent results achieved at the final examination of the lyceum I conquered a scholarship and the admission to the Massachusetts Institute of Technology, then and now considered the temple of technological innovation. I got in touch with the genial forerunners of the information science, such as Norbert Wiener and Claude Shannon. In particular, I became interested in the latter’s studies, such as the “mathematical theory of communications” or the concept of spread spectrum.
D. In 1957, the degree in electronic engineering. And then?
R. I joined the Jet Propulsion Laboratory of Pasadena and, then, also that special expression of the cold war that, in those years, was the struggle for the spatial leadership. Our research team soon passed under NASA’s control. I shared in the launch of the first USA satellite, Explorer, solving two important communication problems: the weakness of the signals received by the satellite, owing to the distance, and the continuous change of their frequency, produced by the orbital movement. On that occasion began my “obsession” for the digital communication and I decided to choose it as subject of my doctorate thesis, discussed at the University of Southern California (USC) in 1962.
D. Was UCLA, then, other great university in Los Angeles, which shortly after offered you the opportunity of undertaking the academic career?
R. Yes, in 1963 UCLA assigned me the course of digital communication and information theory. Just the synergies of those years between research and teaching activity generated the “nonsequential probabilistic algorithm” that took my name
D. How was your intuition born?
R. As it often happens in the scientific research, what you find is not necessarily what you are looking for. The algorithm stemmed from a need of simplification, also for didactic purposes, of a theory at which I was working.
It was originally conceived for the data transmission in the space, where you must take into account the adverse conditions that can produce casual variations of the signal. This problem is normally faced by using codes that introduce an opportune redundancy to protect signals from confusion. An important class is constituted by the so-called convolutional codes, where the original data are transformed and repeated through an opportune mathematical operation. As the convolutional codification makes the data flow particularly interdependent, the decoding requires very complex calculations. Viterbi’s algorithm intervenes just in the decoding phase to determine which sequence of transmitted data will be the most likely cause of the observed flow in output. It calculates the probability of the different incoming flows in recursive way, eliminating in block, at each step, those of minor probability. It allows then a notable reduction of the complexity of the necessary calculation operations.
D. How was it welcomed by the scientific community?
R. At that time it seemed a very powerful intuition but nobody could imagine that it would find application also outside the aerospace ambit. On the contrary, as the stochastic model to which it is applied is sufficiently general to be adapted to the description of phenomena of different kinds, as the scientific-technological development allowed it, the use of the algorithm has been extended to various other fields: telecommunications, computational biology, computational linguistic, vocal recognition.
D. It was you in person who guessed the potentialities of your discovery and committed yourself to the development of some of its commercial applications.
Perhaps we can state that you showed a quality that scientists and researchers often lack: the ability of turning scientific discoveries into “products”, into applications undergoing an economic exploitation.
Is it right?
R. By nature, I cannot stop at the stage of the theoretical formulation: whenever I reach a scientific result, another challenge starts for me, that’s to say to change the innovative idea into technology, product. Just this need drove me towards the entrepreneurial activity: in 1968 I founded the company Linkabit, together with two “academic” colleagues, Irwin Jacobs and Leonard Kleinrock. Linkabit developed studies and simulations concerning Viterbi’s algorithm for governmental agencies and in time it acquired important job orders. In the Seventies it won a contract for the implementation of the instruments for the radio communications between the earth stations and the whole fleet of the U.S. Air Force’s Strategic Air Command. The technology developed by Linkabit for this job order was a precursor of the current “Wireless Wide Area Networks” as well as of the WiFi modem currently implemented in portable computers.
D. Then still another challenge: Qualcomm.
R. In 1985, with Jacobs and other five collaborators of Linkabit, I founded another company, Qualcomm, one of the leader enterprises in the sector of wireless communications, known to the net users for producing Eudora, renowned electronic mail programme. At Qualcomm, I dealt with the need of “multiplation”, that’s to say the simultaneous information transmission by the highest possible number of transport means, without transmission interferences. I worked at the study and refinement of an innovative form of multiplation, the CDMA (Code Division Multiple Access), which promised much better performances than traditional techniques’. In those years, the first generation of mobile phones, based on analogical signals, was vey rapidly expanding. At the same time it was in course the standardization phase concerning the second generation (digital),
where Qualcomm overwhelmed by proposing the adoption of CDMA as alternative to the competing techniques in race, that’s to say FDMA (Frequency Division Multiple Access) and TDMA (Time Division Multiple Access). In 1993 CDMA was recognized as standard for the second generation of mobile phones and two years later Qualcomm produced the first portable phone with this communication system. From 1995 to 2006 more than 300 millions of it were sold.
D. Viterbi, do you never stop?
R. Officially, I have already stopped: in 2000, celebrated my 65th birthday, I retired.
D. Officially ...but actually?
R. Well, I have been called to be member of the commission for information technologies of the White House. I continue to hold lectures in several universities in the world. With my daughter, also her engineer, I founded an investment group on rising economies. That’s all.
D. “That’s all”? They do not seem trifles to me! And then I know that you have also created a foundation with charitable purpose...
R. Yes, through the “Viterbi Family Foundation” my wife and I support many education and research institutions, such as the Lyceum that I attended as a boy, MIT, Technion Israel Institute of Technology... Haven’t I just told you that I enrolled at the University thanks to a scholarship? I must absolutely commit, so that many other talented young people have my same opportunities.