211service.com
Kodo ieškojimas
1948 m. pasaulis vis dar buvo analogiška vieta. „Candid Camera“ ir Edas Sullivanas tik pradėjo savo ilgus pasirodymus televizijoje; Jacko Benny radijo laida turėjo dešimtis milijonų klausytojų. Tačiau blogas priėmimas buvo gyvenimo faktas. Elektromagnetiniai trukdžiai, fizinės kliūtys tarp perdavimo bokšto ir imtuvo ir kiti inžinierių vadinamo triukšmo šaltiniai nuolat sutrikdė Benny monologus ar Sullivano svečių pasirodymus. Daugumoje vietovių, bent kai kuriose stotyse, žmonės susitaikė su apsnigtais vaizdais ar statiniu garsu.
Klodas Šenonas, 1948 m
Tačiau tais pačiais metais Claude'as Shannonas, SM ‘40, PhD ‘40, paskelbė reikšmingą darbą, kuriame matematiškai įrodė, kad net ir esant dideliam triukšmui, informaciją galima perduoti praktiškai be klaidų. Tai buvo analoginis pasaulis, tačiau nuostabi Shannon išvada buvo jo sugebėjimo mąstyti skaitmeniniu būdu rezultatas. Šenonas teigė, kad informacija bet kurioje laikmenoje gali būti pavaizduota naudojant dvejetainius skaitmenis arba bitus - žodį, kurį jo straipsnis pristatė pasauliui. Nors triukšmas ryšio kanale gali sugadinti bitus, jis paaiškino, pridėjus papildomų bitų, kurie yra susiję su pradiniais bitais pagal tam tikrą žinomą algoritmą – klaidų taisymo kodą – bus galima nustatyti pradinę seką.
Kuo triukšmingesnis kanalas, tuo daugiau papildomos informacijos reikia pridėti, kad būtų galima ištaisyti klaidas. Ir kuo daugiau papildomos informacijos bus įtraukta, tuo lėtesnis bus perdavimas. Šenonas parodė, kaip apskaičiuoti mažiausią papildomų bitų skaičių, kuris galėtų garantuoti minimalią klaidą, taigi ir didžiausią duomenų perdavimo greitį be klaidų. Tačiau jis negalėjo pasakyti, kaip galėtų atrodyti praktiška kodavimo schema.
Tyrėjai ieškojo 45 metus. Galiausiai, 1993 m., pora prancūzų inžinierių paskelbė kodų rinkinį – turbo kodus, kurie pasiekė duomenų perdavimo spartą, artimą Šenono teorinei ribai. Pradinė reakcija buvo netikėjimas, tačiau vėlesnis tyrimas patvirtino tyrėjų teiginius. Taip pat paaiškėjo dar labiau stulbinantis faktas: kodai, tokie pat geri kaip turbo kodai, kurie netgi rėmėsi to paties tipo matematiniais triukais, buvo pateikti daugiau nei 30 metų anksčiau, MIT daktaro disertacijoje Roberto Gallagerio, SM. 57, ScD '60. Po dešimtmečius trukusio aplaidumo Gallagerio kodai pagaliau rado praktinį pritaikymą. Jie naudojami perduodant palydovinę televiziją ir belaidžius duomenis, o jiems iššifruoti skirtų lustų galima rasti komerciniuose mobiliuosiuose telefonuose.
Informacijos teorijos gimimas
Gallageris atvyko į MIT 1956 m. – tais pačiais metais pats Shannonas grįžo kaip profesorius po 15 metų „Bell Labs“. Tačiau ne galimybė dirbti su Šenonu paskatino jį pasirinkti MIT, o ne Jeilį, kur jis taip pat pateikė prašymą baigti mokyklą. Buvau kariuomenėje – atlikau beprasmę užduotį – ir tikrai nekenčiau to, ką dariau, – sako Gallager, kuris dėstė MIT daugiau nei 40 metų po to, kai įgijo daktaro laipsnį ir vis dar pataria magistrantams kaip profesorius emeritas Mokslinių tyrimų laboratorijoje. Elektronika. MIT prasidėjo viena savaite anksčiau nei Jeilis. Ir aš taip norėjau išeiti iš armijos, kad tai buvo vienintelė priežastis atvykti į MIT.
Gallageris net nebuvo tikras, kad nori studijuoti informacijos teoriją – klestinčią naują discipliną, kurią sukūrė Shannon 1948 m. Tačiau prieš prisijungdamas prie armijos signalų korpuso, Gallageris taip pat keletą metų dirbo Bell Labs, kur tris dienas per savaitę praleisdavo klasėje, mokydamasis apie naujausius elektros inžinerijos laimėjimus. Nors jis niekada nebuvo susitikęs su Šenonu, ši patirtis padėjo jam atpažinti savo pasiekimų mastą. Aš tiesiog žiūrėjau į jį kaip į dievą, sako Gallageris.
Iš tiesų, tuo metu, kai Šenonas įstojo į MIT fakultetą, jis buvo nedidelė įžymybė. Jau 1953 m. žurnale „Fortune“ buvo paskelbtas straipsnis apie informacijos teoriją: „Galbūt neperdėta sakyti, kad žmogaus pažanga taikos sąlygomis ir saugumas kare labiau priklauso nuo vaisingo informacijos teorijos pritaikymo, o ne nuo fizinių demonstracijų bombose. arba elektrinėse, ta garsioji Einšteino lygtis veikia.
Visuomenės vaizduotę sužavėjo mintis, kad visa informacija – tekstas, garsas, vaizdo įrašas – gali būti sujungta į vien 1 ir 0 sekas. Komerciniai skaitmeniniai įrenginiai dar neegzistavo, todėl žmonėms kilo mintis, kad 001001010101000101011101 gali būti simfonijos dalis, filmo dalis, spalva arba knygos eilutė. Tačiau, kaip savo darbe pažymėjo Shannonas, jo kolega iš Bell Labs Ralphas Hartley buvo pateikęs panašų pasiūlymą prieš 20 metų. Straipsnio aspektas, kuris žavėjo ir tebetraukia Shannon kolegas inžinierius, buvo išradingas būdas, kuriuo jis įrodė, kad turi būti tam tikras kodas, galintis perduoti duomenis be klaidų iki kanalo talpos.
Norėdami suprasti, kaip veikia klaidų taisymo kodas, apsvarstykite asmenį, kuris triukšmingu kanalu bando nusiųsti keturių bitų pranešimą. Jei dėl triukšmo vienas iš bitų pasisuka į priešingą pusę, imtuvas negali žinoti, kad įvyko klaida. Paprasčiausiai pakartojus pranešimą, kad 0011 taptų 00110011, ši problema išspręsta: dabar, jei vienas bitas pakrypsta į priešingą pusę, gavėjas žino, kad įvyko klaida, nes dvi pranešimo versijos nesutampa. Tačiau neįmanoma pasakyti, kuris iš jų yra teisingas. Geresnis būdas koduoti pranešimą gali naudoti keturis papildomus bitus informacijai apie pranešimo bitus pavaizduoti: pavyzdžiui, penktasis bitas gali pasakyti, ar pirmieji du pranešimo bitai turi tokias pačias ar skirtingas reikšmes; šeštasis bitas gali padaryti tą patį trečiam ir ketvirtam bitams, septintas - pirmam ir trečiam, o aštuntas - antram ir ketvirtam bitams. Jei vienas iš pirmųjų keturių bitų apverčiamas, paskutiniai keturi gali jį identifikuoti; jei vienas iš paskutinių keturių bitų bus apverstas, kiti trys gali perduoti pakankamai informacijos, kad tai kompensuotų.
Tačiau Shannon dokumentas vengia bet kokių tokių apmąstymų apie tai, kaip iš tikrųjų sukurti kodus. Vietoj to, jis priartėja prie klaidų taisymo koncepcijos, statistiškai analizuodamas bendras visiškai atsitiktinai parinktų kodų savybes. Norint suprasti jo požiūrį, gali būti naudinga išsiaiškinti, kaip jį būtų galima pritaikyti mūsų hipotetinėms aštuonių bitų sekoms, kurios koduoja keturių bitų pranešimus.
Yra 16 galimų keturių bitų pranešimų, o Šenono metodas kiekvienam iš jų priskirtų savo atsitiktinai parinktą aštuonių bitų serijos numerį – kodinį žodį. Gavėjas, kaip ir siuntėjas, turėtų kodų knygą, koreliuojančią 16 galimų keturių bitų pranešimų su 16 atsitiktinių aštuonių bitų kodo žodžių. Kadangi yra 256 galimos aštuonių bitų sekos, kodų knygelėje nėra 240. Kažkas, gavęs vieną iš tų 240 sekų, žinos, kad į duomenis įsivėlė klaida. Tačiau tol, kol 16 leidžiamų kodo žodžių pakankamai skiriasi vienas nuo kito, greičiausiai bus tik vienas, kuris bus arčiausiai sugadintos sekos. Pavyzdžiui, jei 00000001 ir 11111110 yra galiojantys kodo žodžiai, bet 00000011 ne, tada kažkas, gavęs seką 00000011, gali padaryti išvadą, kad numatytas kodo žodis buvo daug labiau tikėtinas 00000001 nei 11111110.
Realiame gyvenime, žinoma, niekas nesijaudina dėl tik keturių bitų pranešimų. Tačiau naudodamas statistinę analizę, Shannonas galėjo padaryti išvadas apie bet kokio ilgio užkoduotus pranešimus, siunčiamus kanalais su bet kokiu triukšmo kiekiu. Visų pirma, jis sugebėjo tiksliai kiekybiškai įvertinti atsitiktinai parinktų kodo žodžių skirtumo laipsnį ir tikimybę, kad sugadinta seka bus panaši į tik vieną iš jų. Nors tikimybė, kad dvi aštuonių bitų sekos bus panašios, yra gana didelė, Shannon parodė, kad ilgėjant kodo žodžiams, panašumo tikimybė mažėja eksponentiškai. Tiesą sakant, vienas iš labiausiai stulbinančių jo rezultatų buvo tai, kad ilgų pranešimų atveju dauguma atsitiktinai priskirtų kodo žodžių beveik taip pat skirsis vienas nuo kito, kiek tik įmanoma. Tai reiškia, kad beveik bet kokia kodavimo schema – bet koks šių žodžių generavimo būdas – leistų be klaidų perduoti triukšmingu kanalu beveik maksimaliu greičiu.
Prireikė daug intuicijos, kad galvočiau, kad visiškai atsitiktinis kodas gali būti vidutiniškai geras kodas, sako Davidas Forney, SM '63, ScD '65, buvęs Codex Corporation ir Motorola viceprezidentas, grįžęs į MIT 1996 m. kaip docentas. Pasirodo, tai labai supaprastina analizę, nes dabar galite atlikti vidutinę atvejo analizę. Forney trumpam stabteli, o paskui priduria: „Nesakau, kad tai buvo visiškai paprasta: jis turėjo sugalvoti bent kelias teoremas, jei ne matematikos šakas. Bet Gallageris sutinka. Apie 1948 m. Šenono darbą jis sako: „Kai jį studijuojate dvejus metus, tai atrodo labai paprasta. Tiek daug žmonių jums pasakys: „Tai tikrai labai paprasta.“ Ir kai jūs tai suprasite, taip ir yra.
Nenugalimas iššūkis
Šenono matematinis informacijos aprašymas turėjo daug pasekmių. Jo 1948 m. darbas taip pat pristatė duomenų glaudinimo idėją arba tos pačios informacijos pateikimą su mažiau bitų; Suspaudimas leidžia tokioms programoms kaip „WinZip“ ar „StuffIt“ sumažinti failus, kad jie neužgožtų el. pašto serverių, be to, jis naudojamas siekiant sutaupyti vietos diskų įrenginiuose. Informacijos teorija taip pat padėjo kriptografijos studijoms saugesnį matematinį pagrindą; Gallageris mano, kad būtent Šenono karo laikų kriptografinis darbas „Bell Labs“ paskatino jį sukurti naują komunikacijos koncepciją.
Tačiau tuo metu, kai Šenonas grįžo į MIT, jis pradėjo jausti, kad jo teorijos entuziazmas viršija net didelius jos nuopelnus. 1956 m. straipsnyje „The Bandwagon“ jis paminėjo bandymus pritaikyti informacijos teoriją tokiose srityse kaip biologija, psichologija, lingvistika, fundamentinė fizika, ekonomika, organizacijos teorija ir daugelyje kitų, ir įsipareigojo šioje situacijoje laikytis saiko.
Šenono pasibjaurėjimas rampų šviesai ribojosi su atsiskyrimu. Pasak Joel West ‘79, San Chosė valstijos universiteto Verslo koledžo profesoriaus, rašančio knygą apie informacijos teorijos raidą, Shannon patarė tik septyniems magistrantams per 22 metus MIT. Jis buvo gana drovus ir išeinantis į pensiją, todėl jei norėjote jį gauti vadovu, tikrai turėjote būti gana agresyvūs, sako Gallager. Aš taip pat buvau drovi, išėjau į pensiją ir neturėjau pakankamai pasitikėjimo savimi, kad galėčiau net įeiti pasikalbėti su vaikinu.
Šenonas, kaip mokytojas, turėjo mažai kantrybės nuo pažįstamų žmonių nuobodulio. Jis daug labiau domėjosi nauja nei sena, sako Elwyn Berlekamp '62, SM '62, PhD '64, Kalifornijos universiteto Berklio matematikos profesorius emeritas, kuris (kartu su Gallageriu) buvo Shannon's bendraautoris. paskutinis paskelbtas darbas.
Jis daug ko nemokė, sako Gallageris. Tačiau kai jis dėstė, tai buvo tarsi mokslinės kalbos. Prisimenu, kartą jis skaitė kursą, kuriame per semestrą buvo apie 25 paskaitos, ir kiekviena paskaita buvo naujas tyrimo rezultatas. Jis darydavo juos vieną po kito ir niekada nesugalvodavo ko nors įdomaus. Tai buvo tikrai fantastiškas laikotarpis.
Šenonas, mano nuomone, buvo šiek tiek netinkamas akademinėje bendruomenėje, sako Jamesas L. Massey, SM ‘60, PhD ‘62, informacijos teoretikas ir ETH Ciuricho profesorius emeritas. Tikrasis jo žanras buvo būti nepriklausomu tyrinėtoju ir daryti dalykus savo labai individualistiniu būdu.
Taip pat gali būti, kad Šenonas tiesiog nepatogiai mėgavosi. Berlekampas prisimena, kai IEEE informacijos teorijos draugija pakvietė Šenoną perskaityti paskaitą ir 1973 m. Izraelyje gauti savo inauguracinį Šenono apdovanojimą. Niekada nemačiau nė vieno, kuris turėtų daugiau drugelių nei jis, sako jis. Likus penkioms minutėms iki pokalbio pradžios, jis yra prie baro ir yra gana prislėgtas. Jis tikrai bijo lipti į sceną ir visus nuvilti. Nes, žinoma, jie tikisi Dievo, o tai tiesa, ir jis žino, kad negali elgtis kaip Dievas.
Tačiau jei Šenonas retai buvo tiesioginis jaunų informacijos teorijos studentų mentorius, jis metė jiems nenugalimą iššūkį. Atsitiktinis kodavimas niekada neveiks praktiškai: Šenono hipotetinės kodų knygos dydis padvigubėjo su kiekvienu papildomu pranešimo bitu. Vieno 1000 bitų duomenų paketo, keliaujančio internetu, kodų knyga pareikalautų daugiau įrašų nei visatoje yra atomų. Tačiau bet koks praktiškesnis kodavimo mechanizmas, pvz., pradinio pranešimo kartojimas arba papildomų bitų, apibūdinančių pranešimo bitus, pridėjimas buvo tam tikros atsitiktinės kodavimo schemos atitikmuo, nes jis generuotų tuos pačius kodo žodžius. Ir įrodydamas, kad didžioji dauguma atsitiktinių kodavimo schemų buvo artimos pajėgumams, Shannon suteikė vilties, kad viena iš praktinių taip pat yra.
Nesuprantami kodai
Užuot naudojus kodų knygą kodiniams žodžiams ir žinutėms suderinti, praktiška kodavimo schema būtų būdas išgauti pranešimą iš kodinių žodžių skaičiavimo būdu. Daugybė matematinių operacijų su didele tikslumo tikimybe galėtų nustatyti ir ištaisyti klaidas galimai sugadintoje bitų sekoje, gautoje per triukšmingą kanalą.
Tai vienas iš klaidų taisymo kodų ypatumų, kad geras kodavimo algoritmas nebūtinai reiškia gerą dekodavimo algoritmą. Naudodami statistinę analizę, panašią į Shannono, kodavimo teoretikai sugebėjo parodyti, kad tam tikras kodas buvo artimas pajėgumui – kad jis padidins kodo žodžių skirtumą. Tačiau tai nereiškė, kad jie turėjo veiksmingą būdą tai iššifruoti.
Nuo Šenono publikacijos iki 1990-ųjų pradžios mokslininkai pasiūlė vis geresnius kodus ir vis geresnius dekodavimo algoritmus. Tačiau praktinis gebėjimų kodeksas liko sunkiai suprantamas. Forney sako, kad kodavimo teoretikai sakė, kad beveik bet koks kodas yra geras, išskyrus visus, kuriuos galime įsivaizduoti.
Kodai, kuriuos Gallageris pateikė savo 1960 m. daktaro disertacijoje, buvo bandymas išsaugoti kai kuriuos Šenono hipotetinės sistemos atsitiktinumus, neprarandant dekodavimo efektyvumo. Kaip ir daugelis ankstesnių kodų, Gallager naudojo vadinamuosius pariteto bitus, kurie nurodo, ar kuri nors kita bitų grupė turi lygines ar nelygines sumas. Tačiau ankstesni kodai pariteto bitus generuodavo sistemingai: pirmasis pariteto bitas gali nurodyti, ar pranešimo bitų nuo vieno iki trijų suma buvo lygi; kitas pariteto bitas gali padaryti tą patį pranešimo bitams nuo dviejų iki keturių, trečiasis – nuo trijų iki penkių ir pan. Gallagerio koduose, priešingai, koreliacija tarp pariteto bitų ir pranešimo bitų buvo atsitiktinė: pirmasis lyginumo bitas gali apibūdinti, tarkime, 4, 27 ir 83 pranešimo bitų sumą; kitas gali padaryti tą patį pranešimo bitams 19, 42 ir 65.
Gallageris sugebėjo matematiškai įrodyti, kad ilgų pranešimų atveju jo pseudoatsitiktiniai kodai artėjo prie pajėgumų. Išskyrus tai, kad žinojome ir kitų dalykų, kurie taip pat artėjo prie pajėgumų, sako jis. Niekada nekilo klausimas, kurie kodai yra geri. Visada buvo klausimas, kokius dekodavimo algoritmus galite sukurti.
Čia Gallageris padarė savo persilaužimą. Jo kodai naudojo kartotinį dekodavimą, o tai reiškia, kad dekoderis kelis kartus perduos duomenis, todėl vis labiau spėliojo apie kiekvieno bito tapatybę. Jei, pavyzdžiui, lyginumo bitai apibūdino bitų trejetus, tada patikima informacija apie bet kuriuos du bitus gali perduoti informaciją apie trečiąjį. Gallager kartotinis dekodavimo algoritmas yra šiandien dažniausiai naudojamas ne tik jo paties kodams, bet dažnai ir turbo kodams iššifruoti. Jis taip pat buvo pritaikytas daugelyje dirbtinio intelekto sistemų naudojamų statistinių samprotavimų tipuose.
Iteratyvūs metodai apima pirmąjį atspėjimą, kas gali būti gautas bitas, ir įvertinimą pagal jo patikimumą, sako Forney. Tada galbūt gausite daugiau informacijos apie tai, nes jis yra susijęs su pariteto tikrinimu su kitais bitais, todėl galite geriau įvertinti jo patikimumą. Galiausiai, pasak Forney, spėjimai turėtų susilieti į nuoseklų visų pranešimo dalių aiškinimą.
Nors Gallageris nesugebėjo sukaupti drąsos paprašyti Šenono būti jo patarėju, jis sako, kad rašydamas disertaciją su Shannon kalbėjosi tris ar keturis kartus. Išskyrus tai, kad pokalbis su Klodu tris ar keturis kartus prilygo daugeliui žmonių 50 kartų, sako jis. Jis buvo žmogus, kuris labai greitai įsisavino idėjas. Jis nebuvo puikus visomis techninėmis detalėmis. Tačiau norint pamatyti kažko struktūrą, suprasti, kodėl tai turėtų veikti, ir pamatyti, kas galėtų tai padaryti geriau – na, jis tikrai buvo protingiausias žmogus, kokį tik esu sutikęs.
Vis dėlto Shannon nenumatė Gallager kodų sėkmės. Prisimenu, kad jis manė, kad jie buvo įdomūs, bet aš neturėjau jausmo, kad jį jie jaudina, sako Gallageris. Jis supranta kodėl. Gallager kodai priartėjo prie kanalo talpos ilgėjant; bet ilgėjant, dekodavimo procesas taip pat tapo sudėtingesnis – per daug sudėtingas to meto kompiuteriams. Kodavimo tyrinėtojai, žinoma, žinojo, kad kompiuteriai tobulės. Tačiau niekas nežinojo, kam šie patobulinimai bus naudingi.
Nepaisant to, MIT iš karto pasamdė Gallagerį fakulteto nariu, remdamasis jo disertacija. Vėlesniais metais, kol jo paties kodavimo schema tvyrojo nežinomybėje, jis mokė ir vadovavo puikių studentų bangai, įskaitant Massey, Forney ir Berlekampą, kurių indėlis į kodavimo teoriją turėjo daugiau tiesioginių praktinių pasekmių nei jo paties.
Tačiau atrodo, kad Galagerį taip pat nesujaudina ilgas savo kodeksų nepaisymas, kaip ir jų pastarojo meto atgimimas – galbūt todėl, kad jis visada žiūrėjo į tolimą. Jis geba išrasti daiktus, kurie neveikia dešimtis metų, kol žmonės staiga supranta, kad tai gana geri dalykai, sako Vincentas Chanas '71, MS '71, EE '72, PhD '74, elektros inžinerijos profesorius, kuris vis dar demonstruoja jo rašomasis stalas – durų lenta iš biuro, kuriuo kadaise dalijosi su Šenonu. Chanas prisimena neseniai vykusį apsilankymą didelės programinės įrangos kompanijos laboratorijose, kur tyrėjas gyrėsi nauju glaudinimo būdu, leidžiančiu vaizdo failams užimti tik šimtąją dalį atminties nei dabar. Chanas jautė pareigą pabrėžti, kad Gallageris šią techniką pristatė 1974 m. Daugeliui šių idėjų apgalvoti reikia nemažai laiko, sako jis, ir tuo metu, kai jas svarstote, yra daug, daug galimybių. . Ir jūs tikrai turite labai gerai pagalvoti ir galbūt ilgą laiką, kol išsiaiškinsite, kuris iš jų yra tinkamas. Bobas tai daro daug.
Muriel Médard ‘89, ‘90, MS ‘91, ScD ‘95, informacijos teoretikas iš Elektronikos tyrimų laboratorijos, sutinka. Bobas nelakstė, bandydamas publikuoti ir įsitikinti, kad jis nėra apčiuopiamas, sako ji. Pavyzdžiui, Médardas prisimena pokalbį tarp Gallagerio ir žinomo jaunesnio informacijos teoretiko, kuris, aprašydamas savo darbą, citavo neseniai pasiteisinusią teoremą, kuria jis rėmėsi. Bobas pradeda raustis po daiktus taip, kaip tai daro, sako Médard. Galiausiai jis pagamino suplyšusią vieno iš savo dokumentų kopiją. Médardas sako, kad jis turėjo šį paauglišką įrodymą. Ir tai buvo tarsi išnaša. Stora išnaša, bet išnaša. „Jie tai pavadino?“ „Taip, Bobai, dabar tai pagrindinė teorema“.
Šiandien „Gallager“ kodai remiasi metodais, kurie yra arčiausiai didžiausios tam tikro ryšio kanalo duomenų perdavimo spartos – net arčiau nei turbo kodai. Be jų taikomųjų programų telekomunikacijų srityje, jie pradeda keisti senesnius kodus, naudojamus duomenims apsaugoti diskų įrenginiuose ir kituose saugojimo įrenginiuose.
Tokiems žmonėms kaip Forney, kurie buvo MIT tuo, ką jis vadina kodavimo teorijos aukso amžiumi, faktas, kad buvo patenkintas 1948 m. Shannono dokumentas, yra šiek tiek saldus. Tie iš mūsų, kurie žino ir mėgsta kodavimą, nenori pasakyti, kad problema buvo visiškai išspręsta, sako Forney. Tačiau tiesa, kad dauguma žmonių perėjo prie kitų dalykų.
1950–1965 m. MIT buvo informacijos teorijos židinys, sako Joelis Westas. Tai tikrai buvo aukso amžius. 