Šenono riba

Klodas Šenonas (Claude Shannon), Masačiūsetso technologijos instituto darbuotojas, čia dirbęs nuo 1956 iki 1978, įrodė, kad bet kokia komunikacijos linija – laidinė, radijo dažnio, optinio kabelio ar kitokia, gali būti charakterizuojama dviem pagrindiniais faktoriais – dažnio juosta ir triukšmų lygiu.

Dažnių juosta – tai elektrinio, optinio ar elektromagnetinio signalo dažniai, kurie naudojamas signalui perduoti ta linija, o triukšmas – bet kokie kiti signalai, iškraipantys naudingąjį.

Remiantis šiais dviem kriterijais, Šenonas apskaičiavo, koks gali būti maksimalus kanalo pralaidumas, kuriuo signalas gali būti perduodamas visiškai neiškraipytas – be jokių klaidų.

Jis šį dydį pavadino kanalo talpa, tačiau dabar ji dažniausiai vadinama Šenono riba.

Triukšmingame ryšio kanale vienintelė galimybė signalo gavėjui jo negauti su klaidomis – signalui pridėti papildomos informacijos.

Pavyzdžiui, jeigu norine perduoti laišką, kuriame yra tik trys bitai - 001, jį galima nusiųsti tris kartus: 001 001 001. Jei klaida atsirado ir imtuvas gavo 001 011 001, gavėjas gali būti beveik tikras, kad teisinga seka buvo 001.

Bet koks būdas, kuris prideda papildomos informacijos taip, kad būtų išvengta klaidų, vadinamas klaidų ištaisymo kodu. Kuo signalas triukšmingesnis, tuo ilgesnis tas kodas turi būti – prie naudingo signalo reikia pridėti daugiau papildomos informacijos. Taip siunčiama žinutė tampa ilgesne.

Taigi idealus klaidų ištaisymo kodas turi būti kuo trumpesnis, tačiau tuo pačiu metu ir toks, kad tikimybė ištaisyti atsiradusias klaidas būtų maksimali.

Vadinasi, tos pačios žinutės pakartojimas tris kartus būtų gana prastas variantas – jis duomenų siuntimo greitį sumažina net dviem trečdaliais, tačiau vis vien jau negali ištaisyti dviejų tam tikrose vietose atsiradusių klaidų – seka su dviem klaidomis 001 011 011 jau būtų gauta klaidingai, kaip 011.

Tačiau Šenonas sugebėjo pagrįsti, kad yra ir geresnių klaidų ištaisymo kodų – jis matematiškai įrodė, kad visada yra tokių klaidų ištaisymo kodų, kurie leidžia linijos pralaidumą priartinti prie Šenono ribos. Tačiau šis įrodymas nedavė atsakymo, kaip sukurti tokį optimalų klaidų ištaisymo algoritmą.

Tarkime, kanalas yra prastos kokybės, ir keturių bitų žinutei pasiųsti reikia aštuonių bitų žinutės. Ir siuntėjas, ir gavėjas tuomet turi turėti specialią kodų knygutę, kuri susietų 16-ka galimų keturių bitų kombinacijų su 16 aštuonių bitų kodų. Kadangi 8 bitų žinutė gali turėti 256 skirtingų sekų, tai iš jų bent 240 nebūtų kodų knygutėje. Taigi, gavus bent vieną iš tų 240 sekų, gavėjas žinotų, kad signale atsirado klaida.
Tačiau iš 16 galimų kodų sekų bent vienas arba pilnai sutaps su gauta žinute, arba skirsis minimaliai, pavyzdžiui, tik vienu bitu.

Šenonas įrodė, kad, jei statistiškai nagrinėtume visus galimus kodų atitikimus gautoms žinutėms, tai bus bent vienas kodas, kuris leistų kanalo pralaidumui priartėti prie Šenono ribos.

Ir kuo ilgesnis tas kodas būtų, tuo arčiau Šenono ribos galima priartėti. Tačiau jau tūkstančio bitų žinutei kodų knygelė nebetilptų net į šiuolaikinio kompiuterio kietąjį diską, nes joje turėtų būti visi tūkstančio bitų galimų išdėstymų variantai.

Šenono darbai, įrodę, kad kanalų pralaidumą galima padidinti, tačiau nepateikę būdų, kaip tai padaryti praktiškai, davė darbo tyrėjams dar beveik penkiasdešimčiai metų.

Vienas iš pasiekimų buvo faksų ir modemų greičio padidinimas nuo 9,6 kilobitų per sekundę (kbps) iki 14,4 kbps 80-aisiais praeito amžiaus metais. O po to – ir iki 28,8 bei 36,6 kbps 90-aisiais.

Apie tai – kiek vėliau.

Klodas Šenonas su elektromechanine pele, vardu Tesėjas, vaikščiojančia labirintu. Tai buvo vienas pirmųjų bandymų su dirbtiniu intelektu – mėginimas leisti mokytis mašinai pačiai.
Nuotrauka: Bell Labs, apie 1950-uosius metus.