Teorija kod. Teorija kodiranja

Iz Wikipedije, proste enciklopedije

teorija kodiranja- veda o lastnostih kod in njihovi primernosti za doseganje cilja.

Splošne informacije

Kodiranje je postopek pretvorbe podatkov iz oblike, primerne za neposredno uporabo, v obliko, primerno za prenos, shranjevanje, samodejno obdelavo in zaščito pred nepooblaščenim dostopom. Glavni problemi teorije kodiranja vključujejo vprašanja kodiranja ena proti ena in kompleksnost implementacije komunikacijskega kanala pod danimi pogoji:86. V zvezi s tem teorija kodiranja obravnava predvsem naslednja področja:18:

Stiskanje podatkov

Naprej popravek napak

Kriptografija

Kriptografija (iz druge grščine. κρυπτός - skrito in γράφω - pišem), je to področje znanja o načinih zagotavljanja zaupnosti (nezmožnost branja informacij zunanjim osebam), celovitosti podatkov (nezmožnost neopazne spremembe informacij), avtentikacije (preverjanje avtorstva ali drugih lastnosti predmeta), kot tudi nezmožnost zavrnitve avtorstva

04.04.2006 Leonid Černjak Kategorija:Tehnologija

"Odprti sistemi" Nastanek računalnikov bi bil nemogoč, če hkrati z njihovim nastankom ne bi nastala tudi teorija kodiranja signalov.Teorija kodiranja je eno tistih področij matematike, ki je pomembno vplivalo na razvoj računalništva.

"Odprti sistemi"

Ustvarjanje računalnikov bi bilo nemogoče, če hkrati z njihovim pojavom ne bi nastala teorija kodiranja signalov.

Teorija kodiranja je eno tistih področij matematike, ki je izrazito vplivalo na razvoj računalništva. Njegovo področje uporabe se razteza na prenos podatkov po realnih (ali šumnih) kanalih, predmet pa je zagotavljanje pravilnosti posredovanih informacij. Z drugimi besedami, proučuje, kako najbolje zapakirati podatke, tako da je po signalizaciji mogoče iz podatkov zanesljivo in enostavno izluščiti koristne informacije. Včasih teorijo kodiranja zamenjujejo s šifriranjem, vendar to ni res: kriptografija rešuje obratni problem, njen cilj je otežiti pridobivanje informacij iz podatkov.

Potreba po kodiranju podatkov se je prvič pojavila pred več kot sto petdesetimi leti, kmalu po izumu telegrafa. Kanali so bili dragi in nezanesljivi, zaradi česar je bila naloga zmanjšanja stroškov in povečanja zanesljivosti prenosa telegramov nujna. Problem se je še poslabšal s polaganjem čezatlantskih kablov. Od leta 1845 so prišli v uporabo posebni šifranti; z njihovo pomočjo so telegrafisti ročno »stisnili« sporočila in nadomeščali običajna zaporedja besed s krajšimi kodami. Hkrati se je za preverjanje pravilnosti prenosa začela uporabljati pariteta, metoda, ki se je uporabljala tudi za preverjanje pravilnosti vnosa luknjanih kartic v računalnikih prve in druge generacije. Da bi to naredili, je bila v zadnji vhodni krov vstavljena posebej pripravljena kartica s kontrolno vsoto. Če vhodna naprava ni bila zelo zanesljiva (ali je bil sklop prevelik), lahko pride do napake. Da bi ga popravili, se je postopek vnosa ponavljal, dokler se izračunana kontrolna vsota ni ujemala z zneskom, shranjenim na kartici. Ne samo, da je ta shema neprijetna, zgreši tudi dvojne napake. Z razvojem komunikacijskih kanalov je bil potreben učinkovitejši nadzorni mehanizem.

Prvo teoretično rešitev problema prenosa podatkov po hrupnih kanalih je predlagal Claude Shannon, utemeljitelj statistične teorije informacij. Shannon je bil zvezda svojega časa, bil je eden izmed ameriške akademske elite. Kot podiplomski študent na Vannevar Bushu je leta 1940 prejel Nobelovo nagrado (ne zamenjujte z Nobelovo nagrado!), ki jo podeljujejo znanstvenikom, mlajšim od 30 let. Medtem ko je bil v Bell Labs, je Shannon napisal "Matematično teorijo prenosa sporočil" (1948), kjer je pokazal, da če je pasovna širina kanala večja od entropije vira sporočila, je sporočilo mogoče kodirati tako, da bo posredovan brez nepotrebnega odlašanja. Ta zaključek je vsebovan v enem od izrekov, ki jih je dokazal Shannon, njegov pomen pa je omejen na dejstvo, da če obstaja kanal z zadostno pasovno širino, se lahko sporočilo prenese z nekaj časovnimi zamiki. Poleg tega je prikazal teoretično možnost zanesljivega prenosa ob prisotnosti šuma v kanalu. Formulo C = W log ((P+N)/N), vklesano na skromnem Shannonovem spomeniku, postavljenem v njegovem domačem kraju v Michiganu, primerjajo po vrednosti s formulo Alberta Einsteina E = mc 2 .

Shannonovo delo je sprožilo veliko nadaljnjih raziskav na področju informacijske teorije, vendar niso imele praktične inženirske uporabe. Prehod iz teorije v prakso so omogočila prizadevanja Richarda Hamminga, Shannoninega kolega v Bell Labs, ki je zaslovel z odkritjem razreda kod, ki so jih poimenovali "Hammingove kode". Obstaja legenda, da je neprijetnost pri delu z luknjanimi karticami na relejnem računskem stroju Bell Model V sredi 40-ih spodbudila izum njihovih Hammingovih kod. Ob vikendih, ko ni bilo operaterjev, je dobil čas za delo na stroju, sam pa se je moral ubadati z vložkom. Kakor koli že, vendar je Hamming predlagal kode, ki so sposobne popraviti napake v komunikacijskih kanalih, vključno z linijami za prenos podatkov v računalnikih, predvsem med procesorjem in pomnilnikom. Hammingove kode so postale dokaz, kako je mogoče v praksi uresničiti možnosti, ki jih nakazujejo Shannonovi izreki.

Hamming je svoj članek objavil leta 1950, čeprav notranja poročila njegovo teorijo kodiranja datirajo v leto 1947. Zato nekateri menijo, da bi morali Hamminga, ne Shannona, šteti za očeta teorije kodiranja. Vendar pa je v zgodovini tehnologije neuporabno iskati prvega.

Gotovo je le, da je Hamming prvi predlagal "kode za popravljanje napak" (Error-Correcting Code, ECC). Sodobne modifikacije teh kod se uporabljajo v vseh sistemih za shranjevanje podatkov in za izmenjavo med procesorjem in RAM-om. Ena izmed njihovih različic, Reed-Solomonova koda, se uporablja v CD-jih, ki omogoča predvajanje posnetkov brez škripanja in hrupa, ki bi lahko povzročil praske in prašne delce. Obstaja veliko različic kod, ki temeljijo na Hammingu, razlikujejo se po algoritmih kodiranja in številu kontrolnih bitov. Takšne kode so pridobile poseben pomen v povezavi z razvojem komunikacij globokega vesolja z medplanetarnimi postajami, na primer, obstajajo kode Reed-Muller, kjer je 32 kontrolnih bitov za sedem informacijskih bitov ali 26 za šest.

Med najnovejšimi kodami ECC je treba omeniti kode LDPC (Low-Density Parity-check Code). Pravzaprav jih poznamo že kakšnih trideset let, posebno zanimanje zanje pa so odkrili ravno v zadnjih letih, ko se je začela razvijati televizija visoke ločljivosti. Kode LDPC niso 100-odstotno zanesljive, vendar se lahko stopnja napak prilagodi na želeno raven, pri čemer se v največji možni meri izkoristi pasovna širina kanala. "Turbo kode" so jim blizu, učinkovite so pri delu s predmeti v globokem vesolju in z omejeno pasovno širino kanala.

Ime Vladimirja Aleksandroviča Kotelnikova je trdno vpisano v zgodovino teorije kodiranja. Leta 1933 je v "Gradivih o radijskih zvezah za prvi vseslovenski kongres o tehnični rekonstrukciji zvez" objavil delo "O pasovni širini? Eter? in žice? Ime Kotelnikova je enakopravno vključeno v ime enega najpomembnejših izrekov v teoriji kodiranja. Ta izrek definira pogoje, pod katerimi se lahko preneseni signal obnovi brez izgube informacij.

Ta izrek so imenovali različno, vključno z "izrekom WKS" (okrajšava WKS je vzeta od Whittaker, Kotelnikov, Shannon). V nekaterih virih se uporabljata tako Nyquist-Shannonov vzorčni izrek kot Whittaker-Shannonov vzorčni izrek, v domačih univerzitetnih učbenikih pa najpogosteje najdemo preprosto "Kotelnikovov izrek". Pravzaprav ima izrek daljšo zgodovino. Njegov prvi del je leta 1897 dokazal francoski matematik Emile Borel. Edmund Whittaker je prispeval leta 1915. Leta 1920 je Japonec Kinnosuki Ogura objavil popravke Whittakerjevih raziskav, Američan Harry Nyquist pa je leta 1928 izpopolnil principe digitalizacije in rekonstrukcije analognega signala.

Claude Shannon(1916 - 2001) je že od šolskih let kazal enako zanimanje za matematiko in elektrotehniko. Leta 1932 je vstopil na Univerzo v Michiganu, leta 1936 - na Massachusetts Institute of Technology, kjer je leta 1940 diplomiral in prejel dve diplomi - magisterij iz elektrotehnike in doktorat iz matematike. Leta 1941 se je Shannon pridružil Bell Laboratories. Tu je začel razvijati ideje, ki so kasneje privedle do teorije informacij. Leta 1948 je Shannon objavil članek "Matematična teorija komunikacije", kjer so bile oblikovane osnovne ideje znanstvenika, zlasti določitev količine informacij z entropijo, in predlagal tudi enoto informacije, ki določa izbiro dveh enako verjetne možnosti, torej tisto, čemur so kasneje rekli bit . V letih 1957-1961 je Shannon objavil dela, ki so dokazala izrek o prepustnosti za hrupne komunikacijske kanale, ki zdaj nosi njegovo ime. Leta 1957 je Shannon postal profesor na Massachusetts Institute of Technology, od koder se je 21 let kasneje upokojil. Na "zasluženem počitku" se je Shannon popolnoma posvetil svoji stari strasti do žongliranja. Izdelal je več strojev za žongliranje in celo ustvaril splošno teorijo žongliranja.

Richard Hamming(1915 - 1998) je začel svoje izobraževanje na Univerzi v Chicagu, kjer je leta 1937 diplomiral. Leta 1939 je magistriral na Univerzi v Nebraski in doktoriral iz matematike na Univerzi v Illinoisu. Leta 1945 je Hamming začel delati na projektu Manhattan, velikem vladnem raziskovalnem prizadevanju za izdelavo atomske bombe. Leta 1946 se je Hamming pridružil Bell Telephone Laboratories, kjer je delal s Claudom Shannonom. Leta 1976 je Hamming prejel stolico na Mornariški podiplomski šoli v Montereyu v Kaliforniji.

Delo, ki ga je proslavilo, temeljno študijo kod za odkrivanje in popravljanje napak, je Hamming objavil leta 1950. Leta 1956 je sodeloval pri razvoju enega od zgodnjih velikih računalnikov IBM 650. Njegovo delo je postavilo temelje za programski jezik, ki se je pozneje razvil v programske jezike na visoki ravni. Kot priznanje za Hammingov prispevek na področju računalništva je IEEE uvedel medaljo za zasluge za računalništvo in teorijo sistemov, poimenovano po njem.

Vladimir Kotelnikov(1908 - 2005) je leta 1926 vstopil na Fakulteto za elektrotehniko Moskovske visoke tehnične šole po imenu N. E. Bauman (MVTU), vendar je postal diplomant Moskovskega inštituta za elektrotehniko (MPEI), ki se je ločil od Moskovske visoke tehnične šole kot neodvisni inštitut. Med študijem na podiplomskem študiju (1931-1933) je Kotelnikov matematično natančno formuliral in dokazal "referenčni izrek", ki je bil pozneje poimenovan po njem. Po diplomi iz podiplomske šole leta 1933 je Kotelnikov, ki je ostal poučeval na Moskovskem inštitutu za elektrotehniko, odšel na delo na Centralni raziskovalni inštitut za komunikacije (TsNIIS). Leta 1941 je V. A. Kotelnikov oblikoval jasno stališče o zahtevah, ki jih mora izpolnjevati matematično nerazložljiv sistem, in je bil podan dokaz o nezmožnosti njegovega dešifriranja. Leta 1944 je Kotelnikov prevzel mesto profesorja, dekana Fakultete za radiotehniko MPEI, kjer je delal do leta 1980. Leta 1953, ko je bil star 45 let, je bil Kotelnikov takoj izvoljen za rednega člana Akademije znanosti ZSSR. Od leta 1968 do 1990 je bil V. A. Kotelnikov tudi profesor, vodja oddelka na Moskovskem inštitutu za fiziko in tehnologijo.

Rojstvo teorije kodiranja

04.04.2006 Leonid Černjak Kategorija:Tehnologija

"Odprti sistemi" Nastanek računalnikov bi bil nemogoč, če hkrati z njihovim nastankom ne bi nastala tudi teorija kodiranja signalov.Teorija kodiranja je eno tistih področij matematike, ki je pomembno vplivalo na razvoj računalništva.

"Odprti sistemi"

Ustvarjanje računalnikov bi bilo nemogoče, če hkrati z njihovim pojavom ne bi nastala teorija kodiranja signalov.

Teorija kodiranja je eno tistih področij matematike, ki je izrazito vplivalo na razvoj računalništva. Njegovo področje uporabe se razteza na prenos podatkov po realnih (ali šumnih) kanalih, predmet pa je zagotavljanje pravilnosti posredovanih informacij. Z drugimi besedami, proučuje, kako najbolje zapakirati podatke, tako da je po signalizaciji mogoče iz podatkov zanesljivo in enostavno izluščiti koristne informacije. Včasih teorijo kodiranja zamenjujejo s šifriranjem, vendar to ni res: kriptografija rešuje obratni problem, njen cilj je otežiti pridobivanje informacij iz podatkov.

Potreba po kodiranju podatkov se je prvič pojavila pred več kot sto petdesetimi leti, kmalu po izumu telegrafa. Kanali so bili dragi in nezanesljivi, zaradi česar je bila naloga zmanjšanja stroškov in povečanja zanesljivosti prenosa telegramov nujna. Problem se je še poslabšal s polaganjem čezatlantskih kablov. Od leta 1845 so prišli v uporabo posebni šifranti; z njihovo pomočjo so telegrafisti ročno »stisnili« sporočila in nadomeščali običajna zaporedja besed s krajšimi kodami. Hkrati se je za preverjanje pravilnosti prenosa začela uporabljati pariteta, metoda, ki se je uporabljala tudi za preverjanje pravilnosti vnosa luknjanih kartic v računalnikih prve in druge generacije. Da bi to naredili, je bila v zadnji vhodni krov vstavljena posebej pripravljena kartica s kontrolno vsoto. Če vhodna naprava ni bila zelo zanesljiva (ali je bil sklop prevelik), lahko pride do napake. Da bi ga popravili, se je postopek vnosa ponavljal, dokler se izračunana kontrolna vsota ni ujemala z zneskom, shranjenim na kartici. Ne samo, da je ta shema neprijetna, zgreši tudi dvojne napake. Z razvojem komunikacijskih kanalov je bil potreben učinkovitejši nadzorni mehanizem.

Prvo teoretično rešitev problema prenosa podatkov po hrupnih kanalih je predlagal Claude Shannon, utemeljitelj statistične teorije informacij. Shannon je bil zvezda svojega časa, bil je eden izmed ameriške akademske elite. Kot podiplomski študent na Vannevar Bushu je leta 1940 prejel Nobelovo nagrado (ne zamenjujte z Nobelovo nagrado!), ki jo podeljujejo znanstvenikom, mlajšim od 30 let. Medtem ko je bil v Bell Labs, je Shannon napisal "Matematično teorijo prenosa sporočil" (1948), kjer je pokazal, da če je pasovna širina kanala večja od entropije vira sporočila, je sporočilo mogoče kodirati tako, da bo posredovan brez nepotrebnega odlašanja. Ta zaključek je vsebovan v enem od izrekov, ki jih je dokazal Shannon, njegov pomen pa je omejen na dejstvo, da če obstaja kanal z zadostno pasovno širino, se lahko sporočilo prenese z nekaj časovnimi zamiki. Poleg tega je prikazal teoretično možnost zanesljivega prenosa ob prisotnosti šuma v kanalu. Formulo C = W log ((P+N)/N), vklesano na skromnem Shannonovem spomeniku, postavljenem v njegovem domačem kraju v Michiganu, primerjajo po vrednosti s formulo Alberta Einsteina E = mc 2 .

Shannonovo delo je sprožilo veliko nadaljnjih raziskav na področju informacijske teorije, vendar niso imele praktične inženirske uporabe. Prehod iz teorije v prakso so omogočila prizadevanja Richarda Hamminga, Shannoninega kolega v Bell Labs, ki je zaslovel z odkritjem razreda kod, ki so jih poimenovali "Hammingove kode". Obstaja legenda, da je neprijetnost pri delu z luknjanimi karticami na relejnem računskem stroju Bell Model V sredi 40-ih spodbudila izum njihovih Hammingovih kod. Ob vikendih, ko ni bilo operaterjev, je dobil čas za delo na stroju, sam pa se je moral ubadati z vložkom. Kakor koli že, vendar je Hamming predlagal kode, ki so sposobne popraviti napake v komunikacijskih kanalih, vključno z linijami za prenos podatkov v računalnikih, predvsem med procesorjem in pomnilnikom. Hammingove kode so postale dokaz, kako je mogoče v praksi uresničiti možnosti, ki jih nakazujejo Shannonovi izreki.

Hamming je svoj članek objavil leta 1950, čeprav notranja poročila njegovo teorijo kodiranja datirajo v leto 1947. Zato nekateri menijo, da bi morali Hamminga, ne Shannona, šteti za očeta teorije kodiranja. Vendar pa je v zgodovini tehnologije neuporabno iskati prvega.

Gotovo je le, da je Hamming prvi predlagal "kode za popravljanje napak" (Error-Correcting Code, ECC). Sodobne modifikacije teh kod se uporabljajo v vseh sistemih za shranjevanje podatkov in za izmenjavo med procesorjem in RAM-om. Ena izmed njihovih različic, Reed-Solomonova koda, se uporablja v CD-jih, ki omogoča predvajanje posnetkov brez škripanja in hrupa, ki bi lahko povzročil praske in prašne delce. Obstaja veliko različic kod, ki temeljijo na Hammingu, razlikujejo se po algoritmih kodiranja in številu kontrolnih bitov. Takšne kode so pridobile poseben pomen v povezavi z razvojem komunikacij globokega vesolja z medplanetarnimi postajami, na primer, obstajajo kode Reed-Muller, kjer je 32 kontrolnih bitov za sedem informacijskih bitov ali 26 za šest.

Med najnovejšimi kodami ECC je treba omeniti kode LDPC (Low-Density Parity-check Code). Pravzaprav jih poznamo že kakšnih trideset let, posebno zanimanje zanje pa so odkrili ravno v zadnjih letih, ko se je začela razvijati televizija visoke ločljivosti. Kode LDPC niso 100-odstotno zanesljive, vendar se lahko stopnja napak prilagodi na želeno raven, pri čemer se v največji možni meri izkoristi pasovna širina kanala. "Turbo kode" so jim blizu, učinkovite so pri delu s predmeti v globokem vesolju in z omejeno pasovno širino kanala.

Ime Vladimirja Aleksandroviča Kotelnikova je trdno vpisano v zgodovino teorije kodiranja. Leta 1933 je v "Gradivih o radijskih zvezah za prvi vseslovenski kongres o tehnični rekonstrukciji zvez" objavil delo "O pasovni širini? Eter? in žice? Ime Kotelnikova je enakopravno vključeno v ime enega najpomembnejših izrekov v teoriji kodiranja. Ta izrek definira pogoje, pod katerimi se lahko preneseni signal obnovi brez izgube informacij.

Ta izrek so imenovali različno, vključno z "izrekom WKS" (okrajšava WKS je vzeta od Whittaker, Kotelnikov, Shannon). V nekaterih virih se uporabljata tako Nyquist-Shannonov vzorčni izrek kot Whittaker-Shannonov vzorčni izrek, v domačih univerzitetnih učbenikih pa najpogosteje najdemo preprosto "Kotelnikovov izrek". Pravzaprav ima izrek daljšo zgodovino. Njegov prvi del je leta 1897 dokazal francoski matematik Emile Borel. Edmund Whittaker je prispeval leta 1915. Leta 1920 je Japonec Kinnosuki Ogura objavil popravke Whittakerjevih raziskav, Američan Harry Nyquist pa je leta 1928 izpopolnil principe digitalizacije in rekonstrukcije analognega signala.

Claude Shannon(1916 - 2001) je že od šolskih let kazal enako zanimanje za matematiko in elektrotehniko. Leta 1932 je vstopil na Univerzo v Michiganu, leta 1936 - na Massachusetts Institute of Technology, kjer je leta 1940 diplomiral in prejel dve diplomi - magisterij iz elektrotehnike in doktorat iz matematike. Leta 1941 se je Shannon pridružil Bell Laboratories. Tu je začel razvijati ideje, ki so kasneje privedle do teorije informacij. Leta 1948 je Shannon objavil članek "Matematična teorija komunikacije", kjer so bile oblikovane osnovne ideje znanstvenika, zlasti določitev količine informacij z entropijo, in predlagal tudi enoto informacije, ki določa izbiro dveh enako verjetne možnosti, torej tisto, čemur so kasneje rekli bit . V letih 1957-1961 je Shannon objavil dela, ki so dokazala izrek o prepustnosti za hrupne komunikacijske kanale, ki zdaj nosi njegovo ime. Leta 1957 je Shannon postal profesor na Massachusetts Institute of Technology, od koder se je 21 let kasneje upokojil. Na "zasluženem počitku" se je Shannon popolnoma posvetil svoji stari strasti do žongliranja. Izdelal je več strojev za žongliranje in celo ustvaril splošno teorijo žongliranja.

Richard Hamming(1915 - 1998) je začel svoje izobraževanje na Univerzi v Chicagu, kjer je leta 1937 diplomiral. Leta 1939 je magistriral na Univerzi v Nebraski in doktoriral iz matematike na Univerzi v Illinoisu. Leta 1945 je Hamming začel delati na projektu Manhattan, velikem vladnem raziskovalnem prizadevanju za izdelavo atomske bombe. Leta 1946 se je Hamming pridružil Bell Telephone Laboratories, kjer je delal s Claudom Shannonom. Leta 1976 je Hamming prejel stolico na Mornariški podiplomski šoli v Montereyu v Kaliforniji.

Delo, ki ga je proslavilo, temeljno študijo kod za odkrivanje in popravljanje napak, je Hamming objavil leta 1950. Leta 1956 je sodeloval pri razvoju enega od zgodnjih velikih računalnikov IBM 650. Njegovo delo je postavilo temelje za programski jezik, ki se je pozneje razvil v programske jezike na visoki ravni. Kot priznanje za Hammingov prispevek na področju računalništva je IEEE uvedel medaljo za zasluge za računalništvo in teorijo sistemov, poimenovano po njem.

Vladimir Kotelnikov(1908 - 2005) je leta 1926 vstopil na Fakulteto za elektrotehniko Moskovske visoke tehnične šole po imenu N. E. Bauman (MVTU), vendar je postal diplomant Moskovskega inštituta za elektrotehniko (MPEI), ki se je ločil od Moskovske visoke tehnične šole kot neodvisni inštitut. Med študijem na podiplomskem študiju (1931-1933) je Kotelnikov matematično natančno formuliral in dokazal "referenčni izrek", ki je bil pozneje poimenovan po njem. Po diplomi iz podiplomske šole leta 1933 je Kotelnikov, ki je ostal poučeval na Moskovskem inštitutu za elektrotehniko, odšel na delo na Centralni raziskovalni inštitut za komunikacije (TsNIIS). Leta 1941 je V. A. Kotelnikov oblikoval jasno stališče o zahtevah, ki jih mora izpolnjevati matematično nerazložljiv sistem, in je bil podan dokaz o nezmožnosti njegovega dešifriranja. Leta 1944 je Kotelnikov prevzel mesto profesorja, dekana Fakultete za radiotehniko MPEI, kjer je delal do leta 1980. Leta 1953, ko je bil star 45 let, je bil Kotelnikov takoj izvoljen za rednega člana Akademije znanosti ZSSR. Od leta 1968 do 1990 je bil V. A. Kotelnikov tudi profesor, vodja oddelka na Moskovskem inštitutu za fiziko in tehnologijo.

Rojstvo teorije kodiranja

"Cilj tega tečaja je pripraviti vas na vašo tehnično prihodnost."

Tako ima Hamming (ja, ja, samopreverjanje in samopopravljanje Hammingovih kod) na podlagi njegovih predavanj napisano celo knjigo. Prevajamo, ker človek pove svoje mnenje.

Ta knjiga ne govori samo o IT, to je knjiga o načinu razmišljanja neverjetno kul ljudi. »Ne gre samo za naboj pozitivnega razmišljanja; opisuje pogoje, ki povečujejo možnosti za odlično delo.«

Prevedli smo že 28 (od 30) poglavij. In delamo na objavi "v papirju".

Teorija kodiranja - I

Za poenostavitev problema predstavitve informacij razmislite o problemu prenosa informacij od točke do točke. To vprašanje je povezano z vprašanjem shranjevanja informacij. Problemi prenosa informacij v času in prostoru so enaki. Slika 10.1 prikazuje tipičen model prenosa informacij.

Slika 10.1

Na levi strani slike 10.1 je vir informacij. Pri obravnavi modela nam narava vira ni pomembna. Lahko je niz abecednih znakov, številk, matematičnih formul, glasbenih not, simbolov, s katerimi lahko predstavljamo plesne gibe – narava vira in pomen shranjenih znakov ni del prenosnega modela. Upoštevamo samo vir informacij, s takšno omejitvijo dobimo močno, splošno teorijo, ki jo lahko razširimo na številna področja. Je abstrakcija številnih aplikacij.

Ko je Shannon v poznih štiridesetih letih ustvaril informacijsko teorijo, je veljalo, da bi se morala imenovati komunikacijska teorija, vendar je vztrajal pri izrazu informacije. Ta izraz je postal stalen vzrok tako povečanega zanimanja kot nenehnih frustracij v teoriji. Preiskovalci so želeli zgraditi cele »teorije informacij«, izrodile so se v teorije o naboru znakov. Če se vrnemo k modelu prenosa, imamo vir podatkov, ki jih je treba kodirati za prenos.

Kodirnik je sestavljen iz dveh delov, prvi del se imenuje izvorni kodirnik, natančno ime je odvisno od vrste vira. Viri različnih tipov podatkov ustrezajo različnim tipom kodirnikov.

Drugi del postopka kodiranja se imenuje kodiranje kanala in je odvisen od vrste kanala za prenos podatkov. Tako se drugi del postopka kodiranja ujema z vrsto prenosnega kanala. Tako se pri uporabi standardnih vmesnikov podatki iz vira najprej kodirajo glede na zahteve vmesnika, nato pa glede na zahteve uporabljenega kanala za prenos podatkov.

V skladu z modelom na sliki 10.1 je podatkovna povezava izpostavljena "dodatnemu naključnemu šumu". Ves šum v sistemu se na tej točki združi. Predpostavlja se, da kodirnik sprejme vse simbole brez popačenja, dekoder pa opravlja svojo funkcijo brez napak. To je nekaj idealizacije, vendar je za mnoge praktične namene blizu realnosti.

Tudi faza dekodiranja je sestavljena iz dveh stopenj: kanal - standard, standard - sprejemnik podatkov. Ob koncu prenosa se podatki prenesejo do potrošnika. Ponovno ne upoštevamo, kako si potrošnik razlaga te podatke.

Kot smo že omenili, sistem za prenos podatkov, kot so telefonska sporočila, radio, TV programi, predstavlja podatke kot niz številk v registrih računalnika. Ponovno se prenos v prostoru ne razlikuje od prenosa v času ali shranjevanja informacij. Če imate informacije, ki jih boste čez nekaj časa potrebovali, jih je treba kodirati in shraniti v viru za shranjevanje podatkov. Po potrebi se informacije dekodirajo. Če sta sistem kodiranja in dekodiranja enaka, prenašamo podatke po prenosnem kanalu nespremenjene.

Temeljna razlika med predstavljeno teorijo in običajno teorijo v fiziki je predpostavka, da pri izvoru in sprejemniku ni šuma. Pravzaprav se napake pojavljajo v kateri koli opremi. V kvantni mehaniki se hrup pojavi na kateri koli stopnji v skladu z načelom negotovosti in ne kot začetni pogoj; v vsakem primeru koncept hrupa v informacijski teoriji ni enakovreden analognemu pojmu v kvantni mehaniki.
Za določnost bomo nadalje obravnavali binarno obliko predstavitve podatkov v sistemu. Druge oblike so obdelane na podoben način, zaradi enostavnosti jih ne bomo upoštevali.

Začnimo s sistemi s kodiranimi znaki spremenljive dolžine, kot v klasični Morsejevi abecedi pik in pomišljajev, v kateri so pogosto pojavljajoči se znaki kratki, redki znaki pa dolgi. Ta pristop omogoča doseganje visoke učinkovitosti kode, vendar je treba omeniti, da je Morsejeva koda trinarna, ne binarna, saj vsebuje presledek med pikami in pomišljajem. Če so vsi znaki v kodi enako dolgi, se taka koda imenuje blok.

Prva očitna nujna lastnost kode je zmožnost nedvoumnega dekodiranja sporočila v odsotnosti šuma, vsaj zdi se, da je to zaželena lastnost, čeprav je v nekaterih situacijah to zahtevo mogoče zanemariti. Podatki iz prenosnega kanala se sprejemniku prikažejo kot tok 0 s in 1 s.

Dva sosednja znaka bomo imenovali dvojna razširitev, tri sosednje znake trojna razširitev in na splošno, če pošljemo N znakov, prejemnik vidi dodatke k osnovni kodi N znakov. Sprejemnik, ki ne pozna vrednosti N, mora tok razdeliti na oddajne bloke. Ali z drugimi besedami, prejemnik mora biti sposoben razstaviti tok na edinstven način, da lahko rekonstruira izvirno sporočilo.

Razmislite o abecedi z majhnim številom znakov; običajno so abecede veliko večje. Jezikovne abecede se začnejo s 16 do 36 znaki, vključno z velikimi in malimi črkami, številkami, znaki, ločili. Na primer, v tabeli ASCII je 128 = 2^7 znakov.
Razmislite o posebni kodi, sestavljeni iz 4 znakov s1, s2, s3, s4

s1 = 0; s2 = 00; s3 = 01; s4 = 11.

Kako naj prejemnik razlaga naslednji prejeti izraz

kako s1s1s4 ali kako s2s4?

Na to vprašanje ne morete nedvoumno odgovoriti, ta koda zagotovo ni dekodirana, zato je nezadovoljiva. Po drugi strani pa koda

s1 = 0; s2 = 10; s3 = 110; s4 = 111

Dekodira sporočilo na edinstven način. Vzemimo poljuben niz in razmislimo, kako ga bo sprejemnik dekodiral. Zgraditi morate dekodirno drevo v skladu z obliko na sliki 10.II. Linija

1101000010011011100010100110 …

Lahko se razdeli na bloke znakov

110, 10, 0, 10, 0, 110, 111, 0, 0, 0, 10, 10, 0, 110, …

V skladu z naslednjim pravilom za izdelavo dekodirnega drevesa:

Če ste na vrhu drevesa, preberite naslednji znak. Ko dosežete list drevesa, pretvorite zaporedje v znak in se vrnete nazaj na začetek.

Treba je biti pozoren na naslednje. Prvič, dekodiranje je strogo pretočni proces, v katerem se vsak bit pregleda samo enkrat. Drugič, protokoli običajno vključujejo znake, ki označujejo konec postopka dekodiranja in so potrebni za označevanje konca sporočila.

Neuporaba končnega znaka je pogosta napaka pri oblikovanju kode. Seveda je mogoče zagotoviti stalni način dekodiranja, v tem primeru zaključni simbol ni potreben.

Slika 10.II

Naslednje vprašanje so kode za pretočno (takojšnje) dekodiranje. Razmislite o kodi, ki je pridobljena iz prejšnje preslikave znakov

s1 = 0; s2 = 01; s3 = 011; s4 = 111.

Recimo, da imamo zaporedje 011111...111 . Edini način, kako lahko dekodirate besedilo sporočila, je, da združite bite od konca do 3 v skupini in izberete skupine z začetnimi ničlami ​​pred enicami, nato pa lahko dekodirate. Takšno kodo je mogoče dekodirati na edinstven način, vendar ne takoj! Za dekodiranje morate počakati do konca prenosa! V praksi ta pristop izravnava hitrost dekodiranja (McMillanov izrek), zato je treba iskati metode takojšnjega dekodiranja.

Razmislite o dveh načinih kodiranja istega znaka Si:

s1 = 0; s2 = 10; s3 = 110; s4=1110, s5=1111,

Dekodirno drevo za to metodo je prikazano na sliki 10.III.

Slika 10.III

Drugi način

s1 = 00; s2 = 01; s3 = 100; s4=110, s5=111,

Dekodirno drevo te oskrbe je predstavljeno na sliki 10.IV.

Najbolj očiten način za merjenje kakovosti kode je povprečna dolžina za določen niz sporočil. Da bi to naredili, je treba izračunati dolžino kode vsakega simbola, pomnoženo z ustrezno verjetnostjo pojava pi. To vam bo dalo dolžino celotne kode. Formula za povprečno dolžino kode L za abecedo q znakov je naslednja

Kjer je pi verjetnost pojava znaka si, je li ustrezna dolžina kodiranega znaka. Za učinkovito kodo mora biti vrednost L čim manjša. Če je P1 = 1/2, p2 = 1/4, p3 = 1/8, p4 = 1/16 in p5 = 1/16, potem za kodo #1 dobimo vrednost dolžine kode

In za kodo #2

Dobljene vrednosti označujejo prednost prve kode.
Če imajo vse besede v abecedi enako verjetnost pojavljanja, je druga koda bolj zaželena. Na primer, s pi = 1/5, dolžina kode #1

In dolžina kode #2

Ta rezultat prikazuje prednost kode 2. Pri snovanju »dobre« kode je torej treba upoštevati verjetnost pojavljanja znakov.

Slika 10.IV

Slika 10.V

Upoštevajte Kraftovo neenakost, ki določa mejno vrednost kodne dolžine znaka li. Glede na osnovo 2 je neenakost predstavljena kot

Ta neenakost pravi, da v abecedi ne sme biti preveč kratkih znakov, sicer bo vsota precej velika.

Da bi dokazali Kraftovo neenakost za katero koli hitro unikatno dekodljivo kodo, zgradimo dekodirno drevo in uporabimo metodo matematične indukcije. Če ima drevo enega ali dva lista, kot je prikazano na sliki 10.V, potem ni dvoma, da neenakost drži. Nadalje, če ima drevo več kot dva lista, potem drevo dolžine m razdelimo na dve poddrevesi. Po principu indukcije predpostavimo, da neenakost velja za vsako vejo višine m -1 ali manj. Po principu indukcije, uporaba neenakosti za vsako vejo. Označimo dolžini kod vej K" in K"". Ko se dve veji drevesa združita, se dolžina vsake poveča za 1, zato je dolžina kode sestavljena iz vsot K'/2 in K' '/2,

Izrek je dokazan.

Razmislite o dokazu Macmillanovega izreka. Uporabimo Kraftovo neenakost za nepretočno dekodirane kode. Dokaz temelji na dejstvu, da je za vsako število K > 1 n-ta potenca števila zagotovo večja od linearne funkcije n, kjer je n dokaj veliko število. Dvignite Kraftovo neenakost na n-to potenco in izraz predstavite kot vsoto

Kjer je Nk število znakov dolžine k, se seštevek začne z najmanjšo dolžino predstavitve n-tega znaka in konča z največjo dolžino nl, kjer je l največja dolžina kodiranega znaka. Iz edinstvene zahteve po dekodiranju izhaja, da. Znesek je predstavljen kot

Če je K > 1, je treba n nastaviti precej veliko, da neenakost postane napačna. Zato k<= 1; теорема Макмиллана доказана.

Oglejmo si nekaj primerov uporabe Kraftove neenakosti. Ali lahko obstaja edinstveno dekodirana koda z dolžinami 1, 3, 3, 3? Da, ker

Kaj pa dolžine 1, 2, 2, 3? Izračunajte po formuli

Neenakost je kršena! V tej kodi je preveč kratkih znakov.

Kode s pikami (kode z vejicami) so kode, ki so sestavljene iz znakov 1, ki se končajo z znakom 0, razen zadnjega znaka, ki je sestavljen iz vseh enic. Eden od posebnih primerov je koda

s1 = 0; s2 = 10; s3 = 110; s4 = 1110; s5= 11111.

Za to kodo dobimo izraz za Kraftovo neenakost

V tem primeru dosežemo enakost. Lahko vidimo, da se za točkovne kode Kraftova neenakost sprevrže v enakost.

Pri gradnji kode morate biti pozorni na vsoto Kraft. Če Kraftova vsota začne presegati 1, je to znak za vključitev simbola drugačne dolžine, da se zmanjša povprečna dolžina kode.

Opozoriti je treba, da Kraftova neenakost ne pravi, da je ta koda enolično dekodljiva, ampak da obstaja koda s simboli takšne dolžine, ki je enolično dekodljiva. Če želite zgraditi edinstveno kodo, ki jo je mogoče dekodirati, lahko dodelite ustrezno dolžino v bitih li kot binarno število. Na primer, za dolžine 2, 2, 3, 3, 4, 4, 4, 4 dobimo Kraftovo neenakost

Zato lahko obstaja taka edinstvena koda toka, ki jo je mogoče dekodirati.

s1 = 00; s2 = 01; s3 = 100; s4 = 101;

S5 = 1100; s6 = 1101; s7 = 1110; s8 = 1111;

Želim biti pozoren na to, kaj se dejansko zgodi, ko izmenjujemo ideje. Na primer, v tem trenutku želim prenesti idejo iz svoje glave v vašo. Povem nekaj besed, s katerimi verjamem, da boste lahko razumeli (dobili) to idejo.

Toda ko boste pozneje želeli to idejo posredovati svojemu prijatelju, boste skoraj zagotovo rekli povsem druge besede. V resnici pomen ali pomen ni vsebovan v nobeni določeni besedi. Uporabil sem nekaj besed, vendar lahko uporabite povsem druge besede, da izrazite isto idejo. Tako lahko različne besede posredujejo isto informacijo. Toda takoj, ko sogovorniku poveš, da ne razumeš sporočila, bo sogovornik praviloma izbral drug nabor besed za prenos pomena, drugega ali celo tretjega. Tako informacije niso vsebovane v nizu določenih besed. Ko prejmete določene besede, potem se odlično potrudite, da besede prevedete v idejo, ki vam jo želi sogovornik posredovati.

Naučimo se izbirati besede, da se prilagodimo sogovorniku. V nekem smislu izbiramo besede glede na naše misli in raven šuma v kanalu, čeprav takšna primerjava ne odraža natančno modela, ki ga uporabljam za predstavljanje šuma v procesu dekodiranja. V velikih organizacijah je resna težava nesposobnost sogovornika slišati, kaj govori sogovornik. Na visokih položajih zaposleni slišijo, »kar želijo slišati«. V nekaterih primerih morate to imeti v mislih, ko napredujete po lestvici podjetja. Predstavitev informacij v formalni obliki je delni odraz procesov našega življenja in je našla široko uporabo daleč onkraj meja formalnih pravil v računalniških aplikacijah.

Se nadaljuje...

Kdor želi pomagati pri prevodu, postavitvi in ​​izdaji knjige - pišite na osebno ali mail [e-pošta zaščitena]

Mimogrede, lansirali smo tudi prevod še ene kul knjige -

Za analizo različnih virov informacij in kanalov njihovega prenosa je potrebno kvantitativno merilo, ki bi omogočilo oceno količine informacij, ki jih vsebuje sporočilo in prenaša signal. Takšen ukrep je leta 1946 uvedel ameriški znanstvenik C. Shannon.

Nadalje predpostavimo, da je vir informacij diskreten in daje zaporedje elementarnih sporočil (i,), od katerih je vsako izbrano iz diskretnega niza (abecede) a, a 2 ,...,d A; Za je obseg abecede vira informacij.

Vsako osnovno sporočilo vsebuje določene informacije kot niz informacij (v obravnavanem primeru) o stanju obravnavanega vira informacij. Za količinsko opredelitev mere te informacije ni pomembna njena semantična vsebina, pa tudi stopnja pomembnosti te informacije za njenega prejemnika. Upoštevajte, da je prejemnik pred prejemom sporočila vedno negotov, katero sporočilo sem. izmed vseh možnih mu bo dano. Ta negotovost je ocenjena s predhodno verjetnostjo P(i,) prenosa sporočila i,. Sklepamo, da je objektivna kvantitativna mera informacij, ki jih vsebuje osnovno sporočilo diskretnega vira, določena z verjetnostjo izbire danega sporočila in določa cc kot funkcijo te verjetnosti. Ista funkcija označuje stopnjo negotovosti, ki jo ima prejemnik informacije glede stanja diskretnega vira. Sklenemo lahko, da stopnja negotovosti glede pričakovanih informacij določa zahteve za kanale za prenos informacij.

Na splošno verjetnost P(a,) izbira vira nekega elementarnega sporočila i, (v nadaljevanju ga bomo imenovali simbol) je odvisna od prej izbranih simbolov, tj. je pogojna verjetnost in ne bo sovpadala z a priori verjetnostjo takšne izbire.

Tim to ^ P(a:) = 1, saj vsi i tvorijo celotno skupino dogodkov

gyi), izbira teh simbolov pa je izvedena z uporabo neke funkcionalne odvisnosti J(a,)= P(a,) = 1, če je izbira simbola po viru vnaprej določena, J(a,)= a „ a P(a t,a) je verjetnost takšne izbire, potem je količina informacij, ki jih vsebuje par simbolov, enaka vsoti količine informacij, ki jih vsebuje vsak od simbolov i in i. Ta lastnost kvantitativne mere informacije se imenuje aditivnost .

To verjamemo P(a,)- pogojna verjetnost izbire znaka i, za vsemi znaki pred njim, in P(a,,i,) je pogojna verjetnost izbire simbola i; za i, in vse predhodne, vendar glede na to P (a 1, a 1) \u003d P (a) P(i,|i y), lahko zapišemo pogoj aditivnosti

Uvedemo notacijo P(a) = P p P (ar) \u003d Q in prepišite pogoj (5.1):

To verjamemo R, O* 0. Z izrazom (5.2) določimo obliko funkcije (str (R). Z razlikovanjem, množenjem z R* 0 in označuje RO = R, zapisati

Upoštevajte, da je razmerje (5.3) izpolnjeno za katerikoli R f O u^^O. Vendar pa ta zahteva vodi do nespremenljivosti desne in leve strani (5.3): Pq>"(P)= Ar"(/?) - Za - konst. Potem pridemo do enačbe Pc> "(P) = TO in po integraciji dobimo

Upoštevajmo, da bomo prepisali

Posledično se je ob izpolnitvi dveh pogojev o lastnostih J(a,) izkazalo, da je oblika funkcionalne odvisnosti J(a,) o verjetnosti izbire simbola a t do konstantnega koeficienta TO enolično definiran

Koeficient TO vpliva le na merilo in določa sistem enot za merjenje količine informacij. Ker ln[P] F 0, potem je smiselno izbrati To Os tako da merilo količine informacij J(a) je bil pozitiven.

Ob sprejetju K=-1, zapiši

Iz tega sledi, da je enota količine informacije enaka informaciji, da se je zgodil dogodek, katerega verjetnost je enaka jaz. Takšno količinsko enoto informacije imenujemo naravna enota. Pogosteje se domneva, da TO= -, torej

Tako smo prišli do binarne enote količine informacije, ki vsebuje sporočilo o nastopu enega od dveh enako verjetnih dogodkov in se imenuje »bit«. Ta enota je razširjena zaradi uporabe binarnih kod v komunikacijski tehnologiji. Če izberemo osnovo logaritma v splošnem primeru, dobimo

kjer je lahko logaritem s poljubno osnovo.

Lastnost aditivnosti kvantitativne mere informacije omogoča, da na podlagi izraza (5.9) določimo količino informacije v sporočilu, sestavljenem iz zaporedja znakov. Verjetnost, da vir izbere takšno zaporedje, se upošteva ob upoštevanju vseh predhodno dostopnih sporočil.

Kvantitativna mera informacij, ki jih vsebuje osnovno sporočilo a (, ne daje predstave o povprečni količini informacij J(A), ki ga izda vir, ko je izbrano eno osnovno sporočilo a d

Povprečna količina informacij označuje vir informacij kot celoto in je ena najpomembnejših značilnosti komunikacijskih sistemov.

Opredelimo to lastnost za diskretni vir neodvisnih sporočil z abecedo TO. Označimo z NA) povprečna količina informacij na znak in je matematično pričakovanje naključne spremenljivke L - količina informacij, ki jih vsebuje naključno izbran znak A

Povprečno količino informacij na simbol imenujemo entropija vira neodvisnih sporočil. Entropija je pokazatelj povprečne apriorne negotovosti pri izbiri naslednjega znaka.

Iz izraza (5.10) sledi, da če je ena od verjetnosti P(a) je enaka ena (torej so vsi ostali enaki nič), potem bo entropija vira informacije enaka nič - sporočilo je popolnoma definirano.

Entropija bo največja, če so predhodne verjetnosti vseh možnih simbolov enake TO, tj. R(a() = 1 /TO, Potem

Če vir neodvisno izbere binarne simbole z verjetnostjo P, = P(a x) in P 2 \u003d 1 - P, potem bo entropija na znak

Na sl. 16.1 prikazuje odvisnost entropije binarnega vira od a priori verjetnosti izbire med dvema binarnima simboloma, ta slika tudi kaže, da je entropija največja pri R, = R 2 = 0,5

1 o 1 dvd - in v binarnih enotah log 2 2 = 1-

riž. 5.1. Entropijska odvisnost pri K = 2 o verjetnosti izbire enega od njih

Entropija virov z enako verjetno izbiro simbolov, vendar z različnimi velikostmi abecede TO, logaritmično narašča z rastjo TO.

Če je verjetnost izbire simbolov drugačna, potem entropija vira pade I(A) glede na možni maksimum H(A) psh = dnevnik TO.

Večja kot je korelacija med simboli, manj svobode pri izbiri naslednjih simbolov in manj informacij ima na novo izbrani simbol. To je posledica dejstva, da negotovost pogojne porazdelitve ne more preseči entropije njihove brezpogojne porazdelitve. Entropijo vira označimo s spominom in abecedo TO skozi H(AA"), in entropija vira brez spomina, vendar v isti abecedi - skozi NA) in dokaži neenakost

Z uvedbo notacije P(aa") za pogojno verjetnost izbire simbola a,(/ = 1, 2, DO) ob predpostavki, da je simbol predhodno izbran ajij =1,2,DO) in izpustimo transformacije, pišemo brez dokaza

kar dokazuje neenakost (5.13).

Enakost v (5.13) ali (5.14) je dosežena, ko

To pomeni, da je pogojna verjetnost izbire simbola enaka brezpogojni verjetnosti izbire le-tega, kar je možno le pri virih brez spomina.

Zanimivo je, da je entropija besedila v ruščini 1,5 binarne enote na znak. Hkrati z isto abecedo K= 32 s pogojem neodvisnih in enako verjetnih simbolov H(A) tp = 5 binarnih znakov na znak. Tako je prisotnost notranjih povezav zmanjšala entropijo za približno 3,3-krat.

Pomembna značilnost diskretnega vira je njegova redundanca p in:

Redundanca vira informacij je brezrazsežna količina znotraj . Seveda je v odsotnosti redundance p u = 0.

Za prenos določene količine informacij iz vira, ki nima korelacije med simboli, z enako verjetnostjo vseh simbolov, najmanjše možno število prenesenih simbolov /7 min: /r 0 (/7 0 R (L max)) je potrebno. Za prenos enake količine informacij iz vira z entropijo (simboli so medsebojno povezani in neenakomerno verjetni) je potrebno povprečno število simbolov n = n„H(A) m JH(A).

Za diskretni vir je značilna tudi zmogljivost, ki je določena s številom simbolov na časovno enoto v H:

Če uspešnost I(A) definirajte v binarnih enotah, čas pa v sekundah, torej NA) - je število binarnih enot na sekundo. Za diskretne izvore, ki proizvajajo stacionarna zaporedja znakov dovolj velike dolžine /?, so uvedeni naslednji koncepti: tipična in netipična zaporedja izvornih znakov, v katera so vsa zaporedja dolžine p. Vse tipične sekvence NlMl (A) vir pri p-»oo imajo približno enako verjetnost pojava

Skupna verjetnost pojava vseh atipičnih zaporedij se nagiba k ničli. V skladu z enakostjo (5.11) ob predpostavki, da je verjetnost tipičnih zaporedij /N rm (A), entropija vira je logN TIin (,4) in potem

Upoštevajte količino in hitrost prenosa informacij po diskretnem kanalu s šumom. Prej smo upoštevali informacije, ki jih ustvari diskretni vir v obliki zaporedja znakov (i,).

Zdaj pa predpostavimo, da je izvorna informacija kodirana in predstavlja zaporedje kodnih simbolov (b, (/ = 1,2,..T - kodna baza), je skladen z diskretnim kanalom za prenos informacij, na izhodu katerega se pojavi zaporedje simbolov

Predvidevamo, da je operacija kodiranja ena proti ena - z zaporedjem znakov (b,) lahko enolično obnovimo zaporedje (i,), tj. s kodnimi simboli je mogoče v celoti obnoviti izvorne informacije.

Če pa upoštevamo ubežne znake |?. j in vnosnih simbolov (/>,), potem zaradi prisotnosti motenj v kanalu za prenos informacij obnovitev ni mogoča. Entropija izhodnega zaporedja //(/?)

je lahko večja od entropije vhodnega zaporedja H(B), vendar se količina informacij za prejemnika ni povečala.

V najboljšem primeru so razmerja ena proti ena med vhodom in izhodom možna in koristne informacije se ne izgubijo, v najslabšem primeru pa o vhodnih simbolih ni mogoče reči ničesar iz izhodnih simbolov kanala za prenos informacij, koristne informacije se v kanalu popolnoma izgubijo.

Ocenimo izgubo informacij v šumnem kanalu in količino informacij, ki se prenašajo po šumnem kanalu. Štejemo, da je bil znak prenesen pravilno, če je s prenesenim znakom 6 sprejet

simbol bj z isto številko (/= j). Nato za idealen kanal brez šuma zapišemo:

Po simbolu bj-na izhodu kanala zaradi neenakosti (5.21)

negotovost je neizogibna. Predvidevamo lahko, da informacije v simbolu b i se ne prenese v celoti in se del izgubi v kanalu zaradi motenj. Na podlagi koncepta kvantitativne mere informacije bomo predpostavili, da je numerični izraz negotovosti, ki se pojavi na izhodu kanala po prejemu simbola ft ; :

in določa količino izgubljenih informacij v kanalu med prenosom.

Pritrditev ft. in s povprečenjem (5.22) po vseh možnih simbolih dobimo vsoto

ki določa količino izgubljene informacije v kanalu pri prenosu elementarnega simbola po kanalu brez pomnilnika ob sprejemu simbola bj(t).

Pri povprečenju vsote (5.23) po vseh ft dobimo vrednost Z?), ki jo označimo z n(v/v- Določa količino izgubljenih informacij pri prenosu enega znaka po kanalu brez spomina:

Kje P^bjbjj- skupna verjetnost dogodka, ki ob prenosu

simbol b. vzel bo simbol b t.

H [z/ odvisno od značilnosti vira informacij o

kanalski vhod IN in na verjetnostne značilnosti komunikacijskega kanala. Po Shannonu v teoriji statistične komunikacije n(v/v se imenuje nezanesljivost kanala.

Pogojna entropija HB/B, entropija diskretnega vira

na vhodu kanala H(Š) in entropija IN ^B) na izhodu ne more biti

negativno. V kanalu brez motenj je kanal nezanesljiv

n(v/v = 0. V skladu z (5.20) opazimo, da H^v/v^

in enakost nastopi le, če sta vhod in izhod kanala statistično neodvisna:

Izhodni simboli niso odvisni od vhodnih simbolov - v primeru pokvarjenega kanala ali zelo močnih motenj.

Kot prej lahko za tipična zaporedja pišemo

reči, da je v odsotnosti motenj njegova nezanesljivost

Pod informacijami, ki se prenašajo v povprečju po kanalu J[ b/ na simbol razumemo razliko med količino informacij na vhodu kanala J(B) in informacije, izgubljene v /? kanalu).

Če sta vir informacij in kanal brez pomnilnika, potem

Izraz (5.27) določa entropijo izhodnih simbolov kanala. Del informacij na izhodu kanala je uporaben, preostanek pa lažen, saj nastane zaradi motenj v kanalu. Naj opozorimo na to n[v/ 2?) izraža informacije o motnjah v kanalu in razliko i(d)-I(d/d) - koristne informacije, ki so prešle skozi kanal.

Upoštevajte, da je velika večina zaporedij, ki nastanejo na izhodu kanala, netipičnih in imajo zelo majhno skupno verjetnost.

Praviloma se upošteva najpogostejša vrsta motenj - aditivni šum. N(t); Signal na izhodu kanala ima obliko:

Za diskretne signale ima ekvivalentni šum, ki izhaja iz (5.28), diskretno strukturo. Šum je diskretno naključno zaporedje, podobno zaporedju vhodnih in izhodnih signalov. Označimo simbole abecede aditivnega šuma v diskretnem kanalu kot C1 = 0, 1,2, T- 1). Pogojne prehodne verjetnosti v takem kanalu

Ker IN (^B/?) In (B) potem, posledično, informacija izhodnega zaporedja diskretnega kanala #(/) glede na vhod B(t) ali pa obratno In (B) - H ^ v / v) (5).

Z drugimi besedami, informacije, ki se prenašajo po kanalu, ne morejo preseči informacij na njegovem vhodu.

Če vhod kanala prejme povprečje x k simbolov v eni sekundi, potem je mogoče določiti povprečno hitrost prenosa informacij po kanalu s šumom:

Kje Н(В) = V k J(B,B^ - zmogljivost vira na vhodu kanala; n (in / in) \u003d U do n (noter, in) ~ nezanesljivost kanala na časovno enoto; H (B) = V k H^B^- delovanje vira, ki ga tvori izhod kanala (oddaja del koristnih in del lažnih informacij); H ^ in / B ^ \u003d U do 1 / (in / in)- količino lažnih podatkov,

ustvaril motnje v kanalu na časovno enoto.

Koncepte količine in hitrosti prenosa informacij po kanalu lahko uporabimo za različne dele komunikacijskega kanala. To je lahko razdelek "vhod kodirnika - izhod dekoderja".

Upoštevajte, da z razširitvijo odseka obravnavanega kanala ni mogoče preseči hitrosti na katerem koli njegovem sestavnem delu. Vsaka nepopravljiva transformacija vodi v izgubo informacij. Nepovratne transformacije ne vključujejo le vpliva motenj, temveč tudi detekcijo, dekodiranje s kodami z redundanco. Obstajajo načini za zmanjšanje izgube pri sprejemu. To je "sprejem na splošno".

Upoštevajte pasovno širino diskretnega kanala in izrek o optimalnem kodiranju. Shannon je uvedel karakteristiko, ki določa največje možne hitrosti prenosa informacij po kanalu z znanimi lastnostmi (šum) pod številnimi omejitvami na skupino vhodnih signalov. To je pasovna širina kanala C. Za diskretni kanal

kjer je maksimum varovan z možnimi vhodnimi viri IN dano Vk in glasnost abecede vhodnih znakov T.

Na podlagi definicije prepustnosti diskretnega kanala zapišemo

Upoštevajte, da je C = 0 z neodvisnim vhodom in izhodom (visoka raven hrupa v kanalu) in v skladu s tem

v odsotnosti motenj motenj na signalu.

Za binarni simetrični kanal brez pomnilnika

riž. 5.2.

Graf odvisnosti zmogljivosti binarnega kanala od parametra R prikazano na sl. 5.2. pri R= 1/2 pasovne širine kanala C = 0, pogojna entropija

//(/?//?) = 1. Praktično zanimanje

graf predstavlja 0

Shannonov temeljni izrek o optimalnem kodiranju je povezan s konceptom zmogljivosti. Njegova formulacija za diskretni kanal je naslednja: če je zmogljivost vira sporočila NA) manjša od pasovne širine kanala C:

Obstaja metoda optimalnega kodiranja in dekodiranja, pri kateri je verjetnost napake ali nezanesljivosti kanala n[a!A j je lahko poljubno majhen. če

takih načinov ni.

V skladu s Shannonovim izrekom je končna vrednost Z je mejna vrednost hitrosti prenosa informacij brez napak po kanalu. Toda za hrupni kanal načini iskanja optimalne kode niso navedeni. Vendar pa je teorem korenito spremenil poglede na temeljne možnosti tehnologije prenosa informacij. Pred Shannonom je veljalo, da je v hrupnem kanalu mogoče doseči poljubno majhno verjetnost napake z zmanjšanjem hitrosti prenosa informacij na nič. To je na primer povečanje zvestobe komunikacije zaradi ponavljanja znakov v kanalu brez spomina.

Znanih je več strogih dokazov Shannonovega izreka. Izrek je bil dokazan za diskretni kanal brez spomina z naključnim kodiranjem. V tem primeru se upošteva množica vseh naključno izbranih kod za dani vir in dani kanal in se uveljavi dejstvo asimptotičnega pristopa k ničli povprečne verjetnosti napačnega dekodiranja po vseh kodah z neomejenim povečanjem trajanja zaporedje sporočil. Tako je dokazano samo dejstvo obstoja kode, ki zagotavlja možnost brezhibnega dekodiranja, ni pa predlagana nedvoumna metoda kodiranja. Hkrati med dokazom postane očitno, da ob ohranjanju enakosti entropij niza sporočilnega zaporedja in ena proti ena ustreznega niza kodnih besed, uporabljenih za prenos, ansambel IN treba je uvesti dodatno redundanco, da se poveča medsebojna odvisnost zaporedja kodnih simbolov. To je mogoče storiti le z razširitvijo nabora kodnih zaporedij, iz katerih so izbrane kodne besede.

Kljub dejstvu, da glavni kodirni izrek za hrupne kanale ne navaja nedvoumnih načinov izbire določene kode in jih tudi ni v dokazu izreka, je mogoče pokazati, da večina naključno izbranih kod pri kodiranju dovolj dolgega sporočila zaporedij, nekoliko presegajo povprečno verjetnost napačnega dekodiranja. Vendar pa so praktične možnosti kodiranja v dolgih blokih omejene zaradi težav pri izvajanju pomnilniških sistemov in logične obdelave zaporedij velikega števila elementov kode ter povečanja zakasnitve pri prenosu in obdelavi informacij. Pravzaprav so še posebej zanimivi rezultati, ki omogočajo določitev verjetnosti napačnega dekodiranja za končna obdobja p uporabljeni kodni bloki. V praksi so omejeni na zmerne vrednosti zakasnitve in dosežejo povečanje verjetnosti prenosa z nepopolno uporabo pasovne širine kanala.