Kod Quest

W 1948 roku świat był nadal miejscem analogowym. Candid Camera i Ed Sullivan dopiero zaczynali swoje długie występy w telewizji; Program radiowy Jacka Benny'ego miał dziesiątki milionów słuchaczy. Ale zły odbiór był faktem. Zakłócenia elektromagnetyczne, fizyczne przeszkody między wieżą transmisyjną a odbiornikiem oraz inne źródła tego, co inżynierowie nazywają hałasem, rutynowo zakłócały monologi Benny’ego lub występy gości Sullivana. W większości obszarów, przynajmniej w przypadku niektórych stacji, ludzie pogodzili się z zaśnieżonymi obrazami lub zakłóconym dźwiękiem.

Claude Shannon, 1948

Jednak w tym samym roku Claude Shannon, SM ‘40, PhD ‘40, opublikował przełomowy artykuł, w którym matematycznie udowodnił, że nawet w obecności dużego szumu możliwe jest przesyłanie informacji praktycznie bez błędów. To był świat analogowy, ale oszałamiający wniosek Shannona był wynikiem jego umiejętności cyfrowego myślenia. Shannon argumentował, że informacje w dowolnym medium można przedstawić za pomocą cyfr binarnych lub bitów – słowa, które jego artykuł wprowadził do świata. Wyjaśnił, że szum w kanale komunikacyjnym może uszkodzić bity, ale dodanie dodatkowych bitów, które są powiązane z oryginalnymi bitami za pomocą jakiegoś znanego algorytmu – kodu korygującego błędy – umożliwi wydedukowanie oryginalnej sekwencji.

Im głośniejszy kanał, tym więcej dodatkowych informacji należy dodać, aby możliwa była korekcja błędów. A im więcej dodatkowych informacji zostanie zawartych, tym wolniejsza będzie transmisja. Shannon pokazał, jak obliczyć najmniejszą liczbę dodatkowych bitów, która może zagwarantować minimalny błąd – a tym samym najwyższą szybkość, z jaką możliwa jest bezbłędna transmisja danych. Nie potrafił jednak powiedzieć, jak mógłby wyglądać praktyczny schemat kodowania.

Badacze spędzili 45 lat na poszukiwaniu jednego. Wreszcie, w 1993 roku, para francuskich inżynierów ogłosiła zestaw kodów – kody turbo – które osiągnęły szybkość transmisji danych bliską teoretycznej granicy Shannona. Początkową reakcją było niedowierzanie, ale późniejsze dochodzenie potwierdziło twierdzenia badaczy. Okazało się również, że jest to jeszcze bardziej zaskakujący fakt: kody równie dobre jak kody turbo, które nawet opierały się na tego samego rodzaju sztuczkach matematycznych, zostały wprowadzone ponad 30 lat wcześniej, w rozprawie doktorskiej MIT Roberta Gallagera, SM. 57, ScD '60. Po dziesięcioleciach zaniedbań kody Gallagera w końcu znalazły praktyczne zastosowanie. Wykorzystywane są w transmisji telewizji satelitarnej i danych bezprzewodowych, a chipy dedykowane do ich dekodowania można znaleźć w komercyjnych telefonach komórkowych.

Narodziny teorii informacji

Gallager przybył do MIT w 1956 – w tym samym roku sam Shannon powrócił jako profesor po 15 latach w Bell Labs. Ale to nie perspektywa pracy z Shannon skłoniła go do wybrania MIT zamiast Yale, gdzie również złożył podanie na studia magisterskie. Byłem w wojsku – wykonywałem bezsensowne zadanie – i naprawdę nienawidziłem tego, co robiłem, mówi Gallager, który po zdobyciu doktoratu nauczał w MIT przez ponad 40 lat i nadal doradza doktorantom jako emerytowany profesor w Laboratorium Badawczym Elektronika. MIT rozpoczął się tydzień wcześniej niż Yale. A tak bardzo chciałem wyjść z wojska, że ​​to był naprawdę jedyny powód, dla którego przyjechałem na MIT.

Gallager nie był nawet pewien, czy chce studiować teorię informacji, rozwijającą się nową dyscyplinę zrodzoną z artykułu Shannona z 1948 roku. Ale przed dołączeniem do Army Signal Corps, Gallager również pracował przez kilka lat w Bell Labs, gdzie spędzał trzy dni w tygodniu w klasie, ucząc się najnowszych osiągnięć w dziedzinie elektrotechniki. Chociaż nigdy nie spotkał Shannon, to doświadczenie pomogło mu rozpoznać zakres jego osiągnięć. Po prostu uważałem go za swego rodzaju boga, mówi Gallager.

Rzeczywiście, zanim Shannon dołączył do wydziału MIT, był pomniejszą gwiazdą. Już w 1953 roku w magazynie „Fortune” w artykule na temat teorii informacji deklamowano: „Nie będzie przesadą stwierdzenie, że postęp człowieka w pokoju i bezpieczeństwie w czasie wojny zależy bardziej od owocnego zastosowania teorii informacji niż od fizycznych demonstracji, czy to w bombach”. lub w elektrowniach, to słynne równanie Einsteina działa.

Tym, co zawładnęło publiczną wyobraźnią, był pomysł, że informacje w całej swojej różnorodności – tekst, dźwięk, wideo – można sprowadzić do zwykłych sekwencji jedynek i zer. Komercyjne urządzenia cyfrowe jeszcze nie istniały, więc zadziwiło ludzi, że 001001010101000101011101 może reprezentować część symfonii, część filmu, kolor lub wers z książki. Ale jak zauważył Shannon w swoim artykule, jego kolega z Bell Labs, Ralph Hartley, wysunął podobną sugestię 20 lat wcześniej. Aspektem artykułu, który urzekł – i nadal urzeka – kolegów inżynierów Shannona, był pomysłowy sposób, w jaki udowodnił, że musi istnieć jakiś kod zdolny do bezbłędnej transmisji danych aż do przepustowości kanału.

Aby zrozumieć, jak działa kod korygujący błędy, rozważ kogoś, kto próbuje wysłać czterobitową wiadomość przez zaszumiony kanał. Jeśli szum powoduje, że jeden z bitów zmienia się na przeciwny, odbiornik nie ma możliwości dowiedzenia się, że wystąpił błąd. Po prostu powtórzenie wiadomości, tak aby 0011 stało się 00110011, rozwiązuje ten problem: teraz, jeśli jeden bit zostanie odwrócony, odbiorca wie, że wystąpił błąd, ponieważ dwie wersje wiadomości nie pasują do siebie. Ale nie można powiedzieć, który z nich jest poprawny. Lepszym sposobem kodowania wiadomości może być wykorzystanie czterech dodatkowych bitów do reprezentowania informacji o bitach wiadomości: na przykład piąty bit może powiedzieć, czy pierwsze dwa bity wiadomości mają takie same lub różne wartości; szósty bit mógł zrobić to samo z bitami trzecim i czwartym, siódmy z bitami pierwszym i trzecim, a ósmy z bitami drugim i czwartym. Jeśli jeden z pierwszych czterech bitów zostanie odwrócony, ostatnie cztery mogą go zidentyfikować; jeśli jeden z ostatnich czterech bitów zostanie odwrócony, pozostałe trzy mogą przekazać wystarczającą ilość informacji, aby to zrekompensować.

Artykuł Shannona wystrzega się jednak takich przemyśleń na temat tego, jak właściwie konstruować kody. Zamiast tego podchodzi do koncepcji korekcji błędów poprzez statystyczną analizę ogólnych właściwości kodów wybranych całkowicie losowo. Aby zrozumieć jego podejście, pomocne może być zobaczenie, jak można je zastosować do naszych hipotetycznych sekwencji ośmiobitowych, które kodują komunikaty czterobitowe.

Istnieje 16 możliwych czterobitowych wiadomości, a metoda Shannona przydzieli każdemu z nich losowo wybrany ośmiobitowy numer seryjny – jego słowo kodowe. Odbiorca, podobnie jak nadawca, miałby książkę kodów korelującą 16 możliwych czterobitowych wiadomości z 16 losowymi ośmiobitowymi słowami kodowymi. Ponieważ istnieje 256 możliwych sekwencji ośmiobitowych, 240 nie pojawia się w książce kodów. Ktoś, kto otrzyma jedną z tych 240 sekwencji, będzie wiedział, że do danych wkradł się błąd. Ale tak długo, jak 16 dozwolonych słów kodowych różni się wystarczająco od siebie, prawdopodobnie istnieje tylko jedno, które jest najbliżej uszkodzonej sekwencji. Na przykład, jeśli 00000001 i 11111110 są poprawnymi słowami kodowymi, ale 00000011 nie, to ktoś, kto otrzyma sekwencję 00000011, może wywnioskować, że zamierzonym słowem kodowym jest znacznie większe prawdopodobieństwo, że będzie 00000001 niż 11111110.

W prawdziwym życiu oczywiście nikt nie martwi się przesyłaniem wiadomości o długości zaledwie czterech bitów. Ale dzięki analizie statystycznej Shannon był w stanie wyciągnąć wnioski na temat zakodowanych wiadomości o dowolnej długości, wysyłanych kanałami z dowolną ilością szumu. W szczególności był w stanie rygorystycznie określić zarówno stopień różnicy między losowo wybranymi słowami kodowymi, jak i prawdopodobieństwo, że uszkodzona sekwencja będzie przypominać tylko jedno z nich. Chociaż prawdopodobieństwo, że dwie ośmiobitowe sekwencje będą podobne, jest stosunkowo wysokie, Shannon wykazał, że wraz z wydłużaniem się słów kodowych prawdopodobieństwo podobieństwa maleje wykładniczo. W rzeczywistości jednym z jego najbardziej zaskakujących wyników było to, że w przypadku długich wiadomości większość losowo przypisanych słów kodowych będzie się różnić od siebie na tyle, na ile to możliwe. Oznacza to, że prawie każdy schemat kodowania — każdy sposób generowania tych słów — umożliwiłby bezbłędną transmisję przez zaszumiony kanał z prędkością bliską maksymalnej.

David Forney, SM '63, ScD '65, były wiceprezes Codex Corporation i Motorola, który powrócił do MIT w 1996 roku, wymagał dużej intuicji, by pomyśleć, że idealnie losowy kod może być średnio całkiem dobrym kodem. jako adiunkt. Okazuje się, że to drastycznie upraszcza analizę, bo teraz można przeprowadzić analizę przeciętnego przypadku. Forney zatrzymuje się na chwilę, po czym dodaje: Nie mówiąc, że było to całkiem proste: musiał wymyślić przynajmniej kilka twierdzeń, jeśli nie działy matematyki. Ale Gallager się zgadza. O pracy Shannona z 1948 r. mówi: Po przestudiowaniu jej przez dwa lata wydaje się to bardzo proste. Tak wielu ludzi powie ci: „To naprawdę bardzo proste”. I kiedy to zrozumiesz, tak jest.

Nieodparte wyzwanie

Matematyczny opis informacji Shannona miał wiele konsekwencji. Jego artykuł z 1948 r. wprowadził również ideę kompresji danych lub przedstawiania tych samych informacji za pomocą mniejszej liczby bitów; kompresja pozwala programom takim jak WinZip lub StuffIt zmniejszać pliki, aby nie przeciążały serwerów poczty e-mail, i służy do oszczędzania miejsca na dyskach. Teoria informacji stawia również badania nad kryptografią na bardziej bezpiecznych podstawach matematycznych; Rzeczywiście, Gallager wierzy, że to wojenna praca kryptograficzna Shannona w Bell Labs doprowadziła go do jego nowatorskiej koncepcji komunikacji.

Jednak zanim Shannon wrócił do MIT, zaczął odczuwać, że entuzjazm otaczający jego teorię przekroczył nawet jej znaczące zalety. W artykule z 1956 roku zatytułowanym The Bandwagon przytoczył próby zastosowania teorii informacji do dziedzin takich jak biologia, psychologia, językoznawstwo, fizyka podstawowa, ekonomia, teoria organizacji i wiele innych, i zobowiązał się do umiarkowania w tej sytuacji.

Niesmak Shannona do światła reflektorów graniczył z samotnością. Według Joela Westa ’79, profesora College of Business na Uniwersytecie Stanowym w San José, który pisze książkę o rozwoju teorii informacji, Shannon doradzał tylko siedmiu doktorantom podczas 22 lat spędzonych na MIT. Był dość nieśmiały i przechodził na emeryturę, więc jeśli chciałeś go jako przełożonego, naprawdę musiałeś być dość agresywny, mówi Gallager. Byłem też nieśmiały i przechodziłem na emeryturę, i nie miałem wystarczającej pewności siebie, żeby nawet wejść i porozmawiać z facetem.

Jako nauczyciel, Shannon nie miał cierpliwości do nudy chowańca. Był znacznie bardziej zainteresowany nowym niż starym, mówi Elwyn Berlekamp '62, SM '62, PhD '64, emerytowany profesor matematyki na University of California w Berkeley, który (wraz z Gallagerem) był współautorem książki Shannona. ostateczny opublikowany artykuł.

Niewiele uczył, mówi Gallager. Ale kiedy uczył, to było jak wygłaszanie pogadanek naukowych. Pamiętam, jak kiedyś prowadził kurs, który w semestrze miał około 25 wykładów, a każdy wykład był nowym wynikiem badań. Robił je jeden po drugim i nigdy nie przestawał wymyślać czegoś ciekawego. To był naprawdę fantastyczny okres.

Shannon był moim zdaniem trochę nie na miejscu w środowisku akademickim, mówi James L. Massey, SM ‘60, PhD ‘62, teoretyk informacji i emerytowany profesor na ETH Zurich. Jego prawdziwym gatunkiem było bycie niezależnym badaczem i robienie rzeczy na swój własny, wysoce indywidualistyczny sposób.

Możliwe też, że Shannon po prostu czuł się niekomfortowo z uwielbieniem. Berlekamp wspomina, jak IEEE Information Theory Society zaprosiło Shannona do wygłoszenia wykładu i odebrania inauguracyjnej Nagrody Shannona w Izraelu w 1973 roku. Nigdy nie widziałem nikogo, kto miałby więcej motyli niż on, mówi. Pięć minut przed rozpoczęciem rozmowy jest przy barze i jest dość przygnębiony. Naprawdę boi się wyjść na scenę i wszystkich rozczarować. Ponieważ oczywiście oczekują Boga, co jest prawdą, a on wie, że nie może działać jak Bóg.

Ale jeśli Shannon rzadko był bezpośrednim mentorem młodych adeptów teorii informacji, postawił im nieodparte wyzwanie. Kodowanie losowe nigdy nie zadziałałoby w praktyce: rozmiar hipotetycznego podręcznika Shannona podwajał się z każdym dodatkowym bitem w wiadomości. Książka kodów dla pojedynczego 1000-bitowego pakietu danych podróżującego przez Internet wymagałaby więcej wpisów niż atomów we wszechświecie. Ale każdy bardziej praktyczny mechanizm kodowania – taki jak powtarzanie oryginalnej wiadomości lub dodawanie dodatkowych bitów opisujących bity wiadomości – był odpowiednikiem jakiegoś losowego schematu kodowania, ponieważ generował te same słowa kodowe. A demonstrując, że zdecydowana większość losowych schematów kodowania była zbliżona do pojemności, Shannon dał nadzieję, że jeden z praktycznych jest również.

Nieuchwytne kody

Zamiast używać książki kodów do dopasowywania słów kodowych i komunikatów, praktyczny schemat kodowania zapewniłby sposób na obliczeniowe wyodrębnienie komunikatu ze słów kodowych. Szereg operacji matematycznych może, z dużym prawdopodobieństwem dokładności, zidentyfikować i skorygować błędy w prawdopodobnie uszkodzonej sekwencji bitów odbieranej przez zaszumiony kanał.

Jest to jedna z osobliwości kodów korygujących błędy, że dobry algorytm kodowania niekoniecznie oznacza dobry algorytm dekodowania. Korzystając z analiz statystycznych podobnych do tych, które przeprowadził Shannon, teoretycy kodowania byli w stanie wykazać, że dany kod zbliża się do zdolności – że maksymalizuje różnicę między słowami kodowymi. Ale to nie znaczyło, że mieli skuteczny sposób na jego dekodowanie.

Między publikacją artykułu Shannona a początkiem lat 90. badacze proponowali coraz lepsze kody, a także coraz lepsze algorytmy dekodowania. Jednak praktyczny kod zbliżenia się do zdolności pozostał nieuchwytny. Kiedyś wśród teoretyków kodowania było powiedzenie, mówi Forney, że prawie każdy kod jest dobry – z wyjątkiem wszystkich, o których możemy pomyśleć.

Kody, które Gallager przedstawił w swojej pracy doktorskiej z 1960 r., były próbą zachowania części przypadkowości hipotetycznego systemu Shannona bez poświęcania wydajności dekodowania. Podobnie jak wiele wcześniejszych kodów, Gallager używał tak zwanych bitów parzystości, które wskazują, czy jakaś inna grupa bitów ma sumy parzyste czy nieparzyste. Jednak wcześniejsze kody generowały bity parzystości w sposób systematyczny: pierwszy bit parzystości może wskazywać, czy suma bitów wiadomości od jednego do trzech była parzysta; następny bit parzystości może zrobić to samo dla bitów od drugiego do czwartego, trzeci dla bitów od trzeciego do piątego i tak dalej. Natomiast w kodach Gallagera korelacja między bitami parzystości a bitami wiadomości była losowa: pierwszy bit parzystości może opisywać, powiedzmy, sumę bitów wiadomości 4, 27 i 83; następny może zrobić to samo dla bitów wiadomości 19, 42 i 65.

Gallager był w stanie wykazać matematycznie, że w przypadku długich wiadomości jego pseudolosowe kody zbliżały się do możliwości. Z wyjątkiem tego, że wiedzieliśmy również o innych rzeczach, które zbliżały się do zdolności, mówi. Nigdy nie było pytania, które kody są dobre. Zawsze było pytanie, jakie algorytmy dekodujące można opracować.

To tam Gallager dokonał przełomu. Jego kody wykorzystywały dekodowanie iteracyjne, co oznacza, że ​​dekoder kilkakrotnie przechodził przez dane, dokonując coraz bardziej precyzyjnych domysłów na temat tożsamości każdego bitu. Jeśli, na przykład, bity parzystości opisują tryplety bitów, to wiarygodna informacja o dowolnych dwóch bitach może przekazywać informację o trzecim. Algorytm iteracyjnego dekodowania Gallagera jest obecnie najczęściej używanym algorytmem nie tylko do dekodowania własnych kodów, ale często także do dekodowania kodów turbo. Znalazła również zastosowanie w rodzaju rozumowania statystycznego stosowanego w wielu systemach sztucznej inteligencji.

Techniki iteracyjne polegają na pierwszym zgadywaniu, jaki może być otrzymany bit i nadaniu mu wagi w zależności od tego, jak jest wiarygodny, mówi Forney. Wtedy może uzyskasz więcej informacji na ten temat, ponieważ jest on zaangażowany w sprawdzanie parzystości z innymi bitami, co daje lepsze oszacowanie jego niezawodności. Forney mówi, że ostatecznie domysły powinny zbiegać się w kierunku spójnej interpretacji wszystkich fragmentów wiadomości.

Chociaż Gallager nie był w stanie zebrać się na odwagę, by poprosić Shannon, aby został jego doradcą, mówi, że rozmawiał z Shannon trzy lub cztery razy podczas pisania swojej pracy magisterskiej. Poza tym, że rozmowa z Claude trzy lub cztery razy była jak rozmowa z większością ludzi 50 razy, mówi. Był kimś, kto bardzo szybko pochwycił te pomysły. Nie był świetny we wszystkich szczegółach technicznych. Ale żeby zobaczyć strukturę czegoś, zobaczyć, dlaczego to powinno działać i zobaczyć, co może sprawić, że będzie lepiej – cóż, z pewnością był najmądrzejszą osobą, jaką kiedykolwiek spotkałem.

Mimo to Shannon nie przewidział sukcesu kodów Gallagera. Pamiętam, że uważał, że są interesujące, ale nie miałem poczucia, że ​​był nimi podekscytowany – mówi Gallager. Rozumie dlaczego. Kody Gallagera zbliżały się do pojemności kanału w miarę wydłużania się; ale wraz z wydłużaniem się procesu dekodowania również stawał się bardziej złożony – zdecydowanie zbyt złożony dla ówczesnych komputerów. Badacze kodowania wiedzieli oczywiście, że komputery ulegną poprawie. Nikt jednak nie wiedział, czyim kodeksom te ulepszenia będą sprzyjać.

Niemniej jednak MIT natychmiast zatrudnił Gallagera jako członka wydziału na podstawie jego pracy magisterskiej. W następnych latach, podczas gdy jego własny schemat kodowania popadł w zapomnienie, nauczał i był mentorem falę błyskotliwych uczniów – w tym Masseya, Forneya i Berlekampa – których wkład w teorię kodowania miał bardziej bezpośrednie implikacje praktyczne niż jego własny.

Gallager wydaje się jednak równie niewzruszony długim zaniedbaniem swoich kodeksów, jak ich niedawnym odrodzeniem – być może dlatego, że zawsze patrzył dalekowzrocznie. Ma talent do wymyślania rzeczy, które leżą w uśpieniu przez dziesiątki lat, aż ludzie nagle zdają sobie sprawę, że to całkiem dobre rzeczy, mówi Vincent Chan '71, MS '71, EE '72, PhD '74, profesor elektrotechniki, jego biurko tabliczka na drzwi z biura, które kiedyś dzielił z Shannon. Chan przypomina niedawną wizytę w laboratoriach dużej firmy zajmującej się oprogramowaniem, gdzie badacz chwalił się nową techniką kompresji, która umożliwiłaby plikom wideo zajęcie zaledwie setnej ilości pamięci niż obecnie. Chan czuł się w obowiązku wskazać, że Gallager wprowadził tę technikę w 1974 roku. Wiele z tych pomysłów wymaga sporo czasu na przemyślenie, mówi, a w czasie, gdy je rozważasz, jest wiele, wiele opcji . I naprawdę musisz bardzo dokładnie przemyśleć i być może przez długi czas, zanim zorientujesz się, który z nich jest właściwy. Bob często to robi.

Muriel Médard ‘89, ‘90, MS ‘91, ScD ‘95, teoretyk informacji w Research Lab of Electronics, zgadza się. Bob nie biegał dookoła, próbując publikować i upewniać się, że nie zostanie zgarnięty, mówi. Na przykład Médard przypomina rozmowę Gallagera z wybitnym młodszym teoretykiem informacji, który opisując swoją pracę, przytoczył niedawno udowodnione twierdzenie, na którym się opierał. Bob zaczyna grzebać w różnych rzeczach, tak jak to robi, mówi Médard. W końcu wyciągnął postrzępioną kopię jednego ze swoich dokumentów. Miał ten maleńki dowód, mówi Médard. I to było jak przypis. Gruby przypis, ale przypis. – Nazwali to? – Tak, Bob, to teraz ważne twierdzenie.

Dzisiaj kody Gallagera leżą u podstaw podejść, które są najbliższe maksymalnej szybkości transmisji danych dla danego kanału komunikacji – bliższe nawet niż kody turbo. Oprócz zastosowań w telekomunikacji zaczynają zastępować starsze kody służące do ochrony danych na dyskach i innych urządzeniach pamięci masowej.

Dla ludzi takich jak Forney, którzy byli w MIT w okresie, który nazywa złotym wiekiem teorii kodowania, fakt, że wyzwanie rzucone przez artykuł Shannona z 1948 roku zostało spełnione, jest nieco słodko-gorzkie. Ci z nas, którzy znają i kochają kodowanie, niechętnie twierdzą, że problem został całkowicie rozwiązany, mówi Forney. Ale prawdą jest, że większość ludzi przeszła do innych rzeczy.

Od 1950 do 1965 MIT był wylęgarnią teorii informacji, mówi Joel West. To był naprawdę złoty wiek.

ukryć