Iš technologijų istorijos. Galaherio kodas (7)
Klodas Šenonas įrodė tarsi sveikam protui prieštaraujantį teiginį, kad, nežiūrint kokia yra informacijos siuntimo kanalo kokybė, juo vis vien įmanoma persiųsti informaciją be klaidų.
Prisijunk prie technologijos.lt komandos!
Laisvas grafikas, uždarbis, daug įdomių veiklų. Patirtis nebūtina, reikia tik entuziazmo.
Sudomino? Užpildyk šią anketą!
Tam reikia pridėti papildomos informacijos – papildomų kodų, kad imtuve atsiradusios klaidos būtų ištaisytos. Jis taip pat įrodė, kad visada egzistuoja apskaičiuojama riba, kokio didumo ta papildoma informacija turėtų būti, ir tuo pačiu egzistuoja maksimali kanalo talpa (arba kanalo pralaidumas), kurį lemia tik to kanalo dažnio juosta ir triukšmų lygis. Ši maksimali kanalo talpa dažnai vadinama Šenono riba. Plačiau apie tai galite paskaityti šiame straipsnyje.
Ir, kas buvo ne mažiau netikėta, Šenonas įrodė, kad visada egzistuoja kodai, kurie leistų ištaisyti siunčiamą ir triukšmų iškraipomą signalą.
Matematikai bei informatikos specialistai ėmė ieškoti, kaip rasti būdus, didinančius kanalų pralaidumą, ir jų dalinis pasiekimas buvo faksų ir modemų greičio padidinimas nuo 9,6 kilobitų per sekundę (kbps) iki 14,4 kilobitų kbps, maždaug 1980 metais. Tačiau ir toks greitis dar buvo toli nuo Šenono ribos.
Tuomet 1993 metais du prancūzai – Alainas Glavje (Alain Glavieux) ir Klodas Berou (Claude Berrou) iš Bretanės telekomunikacijų instituto pasiūlė savo sprendimą - vadinamuosius „turbo kodus“, kurie, jų teigimu, padidina kanalo talpą beveik iki Šenono ribos. Tiesa, kai jie pristatė savo darbą tarptautinėje konferencijoje, jis buvo išjuoktas – autoriai neturėjo jokio matematinio pagrindimo ir kodų algoritmus sukūrė klaidų ir mėginimų būdu.
Tačiau praktiniai bandymai patvirtino, kad pasiūlytas būdas visai neblogai veikia.
Jie veikė iteracijų būdu – dekodavimo įtaisas darydavo spėjimus, koks turėtų būti originalus signalas, kiekvienas spėjimas būdavo vėl siunčiamas atgal į dekodavimo įtaisą, ir sekantis spėjimas jau būdavo tikslesnis. Tęsiant šį grįžtamojo ryšio procesą, buvo nuosekliais mažinamas iškraipymų skaičius.
Ši gana netikėta sėkmė paskatino daugiau tyrėjų įsijungti į darbą, ir vėlgi netikėtai paaiškėjo, kad kodai, veikiantys ne blogiau nei „turbo kodai“ buvo atrasti jau seniai, 1960 metais – juos savo daktaro disertacijoje pateikė Masačiusetso technikos universiteto darbuotojas Robertas Galaheris (Robert Gallager).
Į šį darbą tuomet niekas neatkreipė dėmesio, nes 60-aisiais dar nebuvo technologijų, kurios būtų leidusios praktiškai panaudoti jo idėją.
Galaherio pasiūlytame kode buvo naudojami papildomi bitai, vadinami lyginumo kontrolės bitais (parity bits), kuriuose buvo informacija apie siunčiamos žinutės informacijos bitus.
Pavyzdžiui, jei siunčiama tokia 7 bitų seka 010 1100 ir naudojamas lyginis kontrolės bitas, gavėjui pasiunčiama tokia 8 bitų seka – 1010 1100. Pirmas bitas yra kontrolės bitas, lygus 1, nes pradinėje sekoje bitų suma yra nelyginė – 3. Visa sekos, kurioje naudojamas lyginis kontrolės bitas, bitų suma visada bus lyginė.
Jei būtų naudojamas nelyginis kontrolės bitas, ši seka būtų 0010 1100, o sekos bitų suma – visada nelyginė.
Toks būdas leido aptikti, ar gauta žinutė yra iškraipyta – jei naudojant lyginį kontrolės bitą gauta sekos bitų suma yra nelyginė, vadinasi, atsirado klaida. Tuomet gavėjas turėjo paprašyti pakartoti šią seką iš naujo - kontrolės bitų metodas neleido nustatyti, kurioje vietoje ta klaida yra.
Kitas metodo trūkumas – sekoje jis galėjo aptikti tik nelyginį klaidų skaičių, tačiau to galima išvengti, jei seka būtų skaidoma tik po tris bitus, o ketvirtas būtų kontrolės bitas, Pavyzdžiui, vienas kontrolės bitas nurodo, ar žinutės 1, 2 ir 4 bito suma yra lyginė ar ne, kitas kontrolės bitas apibūdina 3, 4 ir 6 bito sumą, ir t.t., tuomet visada bus galima nustatyti, ar informacija gauta su klaidomis.
Galaherio metodas leido visai priartėti prie Šenono ribos, ir jis buvo patikimesnis nei „turbo kodai“ – jų trūkumas glūdėjo pačiame iteraciniame veikimo principe – jis galėdavo pradėti veikti uždaru ciklu ir duoti neteisingą galutinį rezultatą, panašiai kaip kad jei išgirstume gandą iš skirtingų žmonių, pradėtume tikėti, kad tai tiesa, nors tai viso tik tam tikrame žmonių rate cirkuliuojanti informacija.
Dėl savo paprastumo Galaherio pasiūlytas metodas, dar vadinamas Galaherio kodu, labai plačiai paplito skaitmeniniuose prietaisuose, ypač atliekant tokias operacijas, kurias lengva pakartoti, jei buvo aptikta klaida – pavyzdžiui, įrašant duomenis į kompiuterių atmintį ar kietąjį diską.
