Za efektivna upotreba kanala (povećanje faktora opterećenja λ→1), potrebno ga je uskladiti sa izvorom informacije na ulazu. Takvo podudaranje je moguće i za kanale bez smetnji i za kanale sa smetnjama, na osnovu teorema kodiranja za kanal koje je predložio Shannon.
Teorema kodiranja za kanal bez smetnji.
Ako izvor poruke ima kapacitet od [bit/sec], a komunikacioni kanal ima kapacitet od [bit/sec], tada se poruka može kodirati na način da prenosi informacije preko komunikacijskog kanala prosječnom brzinom proizvoljno blizu vrijednosti, ali ne i prekoračiti je.
Shannon je također predložio metodu za takvo kodiranje, koja se zvala optimalno kodiranje. Kasnije je ideja o takvom kodiranju razvijena u radovima Fana i Huffmana. Trenutno se takvi kodovi široko koriste u praksi (efikasno i optimalno kodiranje).
Šenonova teorema direktnog kodiranja za bučni kanal.
Za bilo koju izvedbu izvora poruke [bps] manje od propusnosti [bps], postoji takva metoda kodiranja koja vam omogućava da osigurate prijenos svih informacija koje generiše izvor poruke sa proizvoljno malom vjerovatnoćom greške ε.
Teorema inverznog kodiranja za kanal sa šumom.
Ne postoji metoda kodiranja koja omogućava prijenos informacija sa proizvoljno malom vjerovatnoćom greške ako je učinak izvora poruke veći od propusni opseg kanal.
Dokaz teoreme kodiranja za bučni kanal je matematički prilično obiman, pa se ograničavamo na opću raspravu o fizičkim aspektima tog kanala. praktična primjena:
1. Teorema utvrđuje teorijska granica moguću efikasnost sistema uz pouzdan prenos informacija. Iz teoreme slijedi da interferencija u kanalu ne nameće ograničenja na tačnost prijenosa. Ograničenja se nameću samo na brzinu prenosa, pri kojoj se može postići proizvoljno visoka pouzdanost prenosa.
Istovremeno, pouzdanost diskretni kanal obično se procjenjuje vrijednošću vjerovatnoće pogrešnog prijema jednog karaktera. Što je manja vjerovatnoća greške, veća je pouzdanost kanala. Pouzdanost, zauzvrat, karakterizira otpornost na buku informacioni sistem.
Brzina prenosa informacija karakteriše efikasnost sistema.
2. Teorema se ne dotiče pitanja načina konstruisanja kodova koji obezbeđuju naznačeni idealan prenos. Nakon što je potkrijepila fundamentalnu mogućnost takvog kodiranja, mobilizirala je napore naučnika da razviju specifične kodove.
3. Pri bilo kojoj konačnoj brzini prijenosa informacija, do širine pojasa, proizvoljno mala vjerovatnoća greške se postiže samo uz beskonačno povećanje trajanja kodiranih nizova znakova. Dakle, prijenos bez grešaka u prisustvu smetnji je samo teoretski moguć. Osiguranje prijenosa informacija sa vrlo malom vjerovatnoćom greške i sa dovoljno visokom efikasnošću moguće je kod kodiranja izuzetno dugih nizova znakova.
Šenonov teorem direktnog izvora opšti pogled Ne treba se brkati sa drugim Šenonovim teoremama.
Šenonove teoreme za opšti izvor opisati mogućnosti kodiranja generičkog izvora korištenjem odvojivih kodova. Drugim riječima, opisane su maksimalno dostižne mogućnosti kodiranja bez gubitaka.
Direktna teorema
Primijenjeno na kodiranje slovo po slovo, direktna teorema se može formulirati na sljedeći način:
Kao dokaz teoreme istražuju se karakteristike Shannon-Fano koda. Dati kod zadovoljava uslove teoreme i ima naznačena svojstva.
Inverzna teorema
Inverzna teorema ograničava maksimalni omjer kompresije koji se može postići kodiranjem bez gubitaka. Kako se primjenjuje na kodiranje slovo po slovo, opisuje ograničenje na prosječnu dužinu kodna riječ za bilo koji odvojivi kod.
Za bilo koji odvojivi kod s dužinama w 1 ,w 2 ,...,w K prosječna dužina poruke je veća ili jednaka entropiji izvora U, normalizirano na binarni logaritam broja slova D u koder abecedi:
Književnost
- Gabidulin, E. M., Pilipchuk, N. I.§3.4 Šenonove teoreme za izvor // Predavanja o teoriji informacija. - M.: MIPT, 2007. - S. 49-52. - 214 str. - ISBN 5-7417-0197-3
Wikimedia fondacija. 2010 .
Pogledajte šta je "Shannonova direktna teorema za opšti izvor" u drugim rječnicima:
Ne treba se brkati sa drugim Šenonovim teoremama. Šenonove teoreme za opšti izvor opisuju mogućnosti kodiranja opšteg izvora korišćenjem odvojivih kodova. Drugim riječima, opisane su maksimalno dostižne mogućnosti ... ... Wikipedia
Wikipedia ima članke o drugim osobama s ovim prezimenom, vidi Shannon. Claude Elwood Shannon Claude Elwood Shannon ... Wikipedia
Claude Elwood Shannon (eng. Claude Elwood Shannon; rođen 30. aprila 1916. Petotsky (Petoskey, Michigan) Michigan, SAD, preminuo 24. februara 2001., Medford, Massachusetts, SAD) je američki matematičar i inženjer elektrotehnike, jedan od kreatora matematičke teorije ... ... Wikipedia
Claude Elwood Shannon (eng. Claude Elwood Shannon; rođen 30. aprila 1916. Petotsky (Petoskey, Michigan) Michigan, SAD, preminuo 24. februara 2001., Medford, Massachusetts, SAD) je američki matematičar i inženjer elektrotehnike, jedan od kreatora matematičke teorije ... ... Wikipedia
- (eng. Claude Elwood Shannon; rođen 30. aprila 1916. Petotsky (Petoskey, Michigan) Michigan, SAD, preminuo 24. februara 2001., Medford, Massachusetts, SAD) je američki matematičar i inženjer elektrotehnike, jedan od osnivača matematičke teorija informacija, u ... ... Wikipediji
Claude Elwood Shannon (eng. Claude Elwood Shannon; rođen 30. aprila 1916. Petotsky (Petoskey, Michigan) Michigan, SAD, preminuo 24. februara 2001., Medford, Massachusetts, SAD) je američki matematičar i inženjer elektrotehnike, jedan od kreatora matematičke teorije ... ... Wikipedia
Claude Elwood Shannon (eng. Claude Elwood Shannon; rođen 30. aprila 1916. Petotsky (Petoskey, Michigan) Michigan, SAD, preminuo 24. februara 2001., Medford, Massachusetts, SAD) je američki matematičar i inženjer elektrotehnike, jedan od kreatora matematičke teorije ... ... Wikipedia
Claude Elwood Shannon (eng. Claude Elwood Shannon; rođen 30. aprila 1916. Petotsky (Petoskey, Michigan) Michigan, SAD, preminuo 24. februara 2001., Medford, Massachusetts, SAD) je američki matematičar i inženjer elektrotehnike, jedan od kreatora matematičke teorije ... ... Wikipedia
Program kursa
"Teorija informacija i kodiranja"
Predavanja se održavaju u IV godini VII semestra,
51 sat predavač docent
Koncept informacije, entropija. Komunikacioni sistemi. diskretni izvori. Opis izvora koji se koristi slučajni proces. statistička nezavisnost. Markovi izvori. Ergodicnost. Ergodičnost Bernulijevog izvora.
Izvođenje formule entropije (prema Fadeevu). Međusobne informacije i njihova svojstva. Entropijska svojstva. Teorema o maksimalna vrijednost entropija. Entropija po jedinici vremena izvora poruke.
Problem kodiranja diskretnog izvora kodovima jednake dužine. Brzina kodiranja. Skupovi velike vjerovatnoće. Direktne i inverzne teoreme za kodiranje diskretnog izvora kodovima jednake dužine.
Problem kodiranja izvora kodovima nejednake dužine. Troškovi kodiranja. Nedvosmisleno dešifrovani kodovi. prefiks kodovi. Kodiranje slova. Neophodan i dovoljan uslov za nedvosmislenu dešifrovanost koda. Puni kodovi. Teorema kodiranja diskretnog izvora kodovima nejednake dužine. Algoritmi za konstruisanje optimalnih kodova (Fano, Shannon, Huffman). Konstrukcija binarnog optimalnog koda sa jednako vjerovatnom distribucijom ulaznih vjerovatnoća. Primjena rezultata teorije informacija u dokazu donjih i gornjih granica složenosti implementacije booleove funkcije u nekim klasama kontrolnih sistema. Metoda za konstruisanje optimalnog koda pod uslovom da je distribucija verovatnoće izvornih slova nepoznata. Markova teorema o jedinstvenoj dešifriranju koda. Prilagodljivi algoritmi za kompresiju informacija.
Diskretni kanal bez memorije. Binarno simetrični kanal. Brzina prijenosa informacija u kanalu. Kapacitet kanala. Prošireni kanal i njegov kapacitet. Odlučujuće šeme i grupisanja zapažanja. Vjerovatnoća pogrešnog prijenosa informacija. Feinsteinova nejednakost. Teorema direktnog kodiranja za kanal bez memorije. Fano nejednakost. Teorema obrade informacija. Inverzija teoreme kodiranja.
Teorija kodiranja za ispravljanje grešaka. Kriterijum maksimalne vjerovatnoće. kodna udaljenost. Kodovi sa provjerom parnosti. Generativni i provjerite matrice. Sindrom. Algoritam za dekodiranje kodova sa provjerom parnosti. Linijski kodovi i njihov algoritam dekodiranja. Hamming granica. Hamingov kod. Ciklični kodovi. Kodiranje i dekodiranje cikličkih kodova.
LITERATURA
1. Gallagher R. Teorija informacija i pouzdana veza., M., Sov. Radio, 1979.
2. Kričevski E. Predavanja o teoriji i informacijama, Novosibirsk, Novosibirski državni univerzitet, 1966.
3. Kolesnik V., Poltyrev G. Kurs teorije informacija, Nauka, 1982.
4. Finestein A. Osnove teorije informacija, M., IL, 1960.
5. Peterson V., Weldon F. Kodovi za ispravljanje grešaka, M., Mir, 1976.
6. Berlekampova teorija algebarskog kodiranja, Moskva, Mir, 1971.
Informacioni kapacitet diskretnih (4.4) i propusnost kontinuiranih (4.7) kanala karakteriše njihove ograničavajuće mogućnosti kao sredstva za prenos informacija. Oni su otkriveni u osnovnim teoremama teorije informacija, koje su poznate kao Šenonove osnovne teoreme kodiranja. Primijenjeno na diskretni kanal, glasi:
Teorema 4.4.1. (Teorema direktnog kodiranja za DCBP.) Za diskretni kanal bez memorije po kodnim brzinama R, manji od informacionog kapaciteta , uvijek postoji kod za koji prosječna vjerovatnoća greške teži nuli kako se dužina kodne riječi povećava.
U slučaju kontinuiranog kanala, formulira se kao
Teorema 4.4.2. (Teorema direktnog kodiranja za AWGN kanal). Na AWGN kanalu sa neograničenim propusnim opsegom, informacije se mogu prenijeti sa proizvoljno malom vjerovatnoćom greške ako je brzina prijenosa manja od širine pojasa.
Inverzna teorema glasi:
Teorema 4.4.3. Po brzini prijenosa 
, veća propusnost komunikacionog kanala C, nijedan kod neće pružiti proizvoljno malu vjerovatnoću greške dekodiranja, tj. apsolutno pouzdan prijenos poruka.
Treba napomenuti da ako je inverzna teorema dokazana za proizvoljni model komunikacionog kanala, onda je direktna samo za određene vrste kanala.
Rezultati teorema kodiranja za kanal sa šumom su donekle neočekivani. Zaista, na prvi pogled se čini da smanjenje vjerovatnoće greške u prijenosu poruka zahtijeva odgovarajuće smanjenje brzine prijenosa i da bi potonja trebala težiti nuli zajedno sa vjerovatnoćom greške. Takav zaključak, posebno, proizilazi iz razmatranja višestrukog retransmisije simbola preko kanala kao načina da se smanji vjerovatnoća grešaka u prijenosu poruke. U ovom slučaju, u prisustvu smetnji u komunikacijskom kanalu, moguće je osigurati da vjerovatnoća greške u prijenosu poruke teži nuli samo kada brzina prijenosa teži nuli.
Međutim, teorema kodiranja pokazuje da je, u principu, moguće prenositi brzinom koja je proizvoljno blizu C, dok se postiže proizvoljno mala vjerovatnoća greške. Nažalost, teoreme, koje ukazuju na fundamentalno postojanje koda za ispravljanje grešaka, ne daju recept za njegovo pronalaženje. Može se samo napomenuti da je za to potrebno koristiti kodove velike dužine. Istovremeno, kako se brzina prijenosa približava širini pojasa i smanjuje se vjerovatnoća greške, kod postaje složeniji zbog povećanja dužine bloka, što dovodi do nagle komplikacije uređaja za kodiranje i dekodiranje, kao i kašnjenja. u izlazu informacija tokom dekodiranja. Metode kodiranja koje se trenutno koriste, o kojima će biti riječi kasnije, ne ostvaruju potencijal komunikacijskog sistema. Jedini izuzetak su nedavno otkriveni turbo kodovi.
1Ovaj rezultat vrijedi za sve simetrične kanale.
Kodiranje informacija
Osnovni koncepti
Šenonove teoreme o kodiranju poruka su spomenute gore. Intuitivno je jasno da je kodiranje operacija pretvaranja informacija u oblik potreban za naknadnu obradu (prijenos preko komunikacijskog kanala, pohranjivanje u memoriju računarski sistem, koristiti za donošenje odluka itd.). Također je jasno da je prilikom izgradnje bilo kojeg informacionog sistema nemoguće bez kodiranja: svako predstavljanje informacija podrazumijeva korištenje nekih kodova. Stoga ćemo detaljno analizirati teorijske osnove kodiranje informacija.
Neka bude A je proizvoljna abeceda. Elementi abecede A nazivaju se slovima (ili simbolima), a konačni nizovi sastavljeni od slova nazivaju se riječima u A. Pretpostavlja se da u bilo kojoj abecedi postoji prazna riječ koja ne sadrži slova.
Riječ α 1 se naziva početak (prefiks) riječi α ako riječ postoji α 2 , tako da α = α 1 α 2; dok je riječ α 1 se naziva pravim početkom riječi α , ako α 2 nije prazna riječ. Dužina riječi je broj slova u riječi (prazna riječ ima dužinu 0). Snimanje α 1 α 2 označava vezu (konkatenaciju) riječi α 1 i α 2. Riječ α 2 se naziva završetak (sufiks) riječi α ako riječ postoji α 1 , tako da α = α 1 α 2; dok je riječ α 2 se naziva pravi završetak riječi α , ako α 1 nije prazna riječ. Prazna riječ se po definiciji smatra početkom i krajem svake riječi. α .
Uzmite u obzir abecedu B = {0, 1, …, D– 1), gdje D≥ 2, i proizvoljan skup C. Mapiranje proizvoljnog skupa C u mnogo riječi u abecedi B pozvao D-arno kodiranje skupa C(u D= 2 kodiranje će biti binarno). Obrnuto preslikavanje se naziva dekodiranje. Dajemo primjere kodiranja.
1. Kodiranje skupa prirodnih brojeva, u kojem je broj n= 0 se preslikava u riječ e(0) = 0 i broj n ≥ 1 binarnu riječ
e(n) = b 1 b 2 … b l (n)
najmanja dužina koja zadovoljava uslov
Očigledno je da b 1 = 1, 2l (n) – 1 ≤ n < 2l (n) i stoga
l(n) = + 1 = ]log( n + 1)[,
gdje [ x] i ] x[ označava najveći cijeli broj koji ne prelazi x, i najmanji cijeli broj veći od x. Riječ e(n) naziva se binarna notacija broja n, a ovo kodiranje je reprezentacija brojeva u binarni sistem obračun. Ovo kodiranje je jedan na jedan, pošto n 1 ≠ n 2 riječi e(n 1) i e(n 2) razlikuju se. Tabela 5.1 prikazuje prikaz prvih 16 prirodnih brojeva u binarnom sistemu.
Tabela 5.1
Kodiranje e(n)
| n | e(n) | n | e(n) | n | e(n) | n | e(n) |
2. Kodiranje prvih 2 k prirodni brojevi, za koje je svaki broj n (0 ≤ n < 2k) je mapiran u riječ
e k(n) = 0k – l (n) e(n),
gdje je unos 0 k – l (n) označava riječ koja se sastoji od k – l(n) nule, e(n) – predstavljanje brojeva n u binarnom sistemu o kojem smo gore govorili. Ovo kodiranje za prvih 16 prirodnih brojeva ( k= 4) dato je u tabeli 5.2.
Tabela 5.2
Kodiranje e k(n)
| n | e k(n) | n | e k(n) | n | e k(n) | n | e k(n) |
Neka bude A = {a i, i= 1, 2, ...) je konačna ili prebrojiva abeceda čija su slova numerirana prirodni brojevi. U ovom slučaju, kodiranje slova abecede A može se postaviti u nizu D-ic riječi V = {v i, i= 1, 2, …), gdje v i postoji slika pisma a i. Takvi nizovi riječi (iz skupa V) se nazivaju kodovi (abeceda ALI). Ako je dat kod V abeceda ALI, zatim kodiranje riječi, u kojima svaka riječ a i 1 a i 2 …aik riječ se podudara v i 1 v i 2 …vik, naziva se kodiranje slovo po slovo.
U prelasku sa kodiranja jedan-na-jedan slova abecede na slovo po slovo kodiranja riječi u abecedi, svojstvo kodiranja jedan-na-jedan možda neće biti očuvano. Na primjer, kodiranje e(n) ne čuva datoj imovini, i kodiranje e k(n) čuva. Svojstvo međusobne jedinstvenosti čuvaju odvojivi kodovi. Šifra V = {v i, i= 1, 2, …) naziva se odvojivim ako je iz svake jednakosti oblika
v i 1 v i 2 …vik = vj 1 vj 2 …vjl
sledi to l = k i v i 1 = vj 1 , v i 2 = vj 2 , … , vik = vjl. Odvojivi kodovi se također nazivaju jedinstveno dekodirajući kodovi.
Prefiksni kodovi pripadaju klasi odvojivih kodova. Šifra V = {v i, i= 1, 2, …) naziva se prefiks ako nema riječi v k nije početak (prefiks) bilo koje riječi v l, l ≠ k. Ako se svaka riječ prefiksnog koda zamijeni svojim najmanjim početkom, koji nije početak ostalih kodnih riječi, tada će rezultirajući kod također biti prefiksni. Ova operacija se zove skraćivanje prefiksnog koda.
Za proizvoljan kod V, koji se sastoji od razne reči, možete napraviti kodno stablo. Ovo je usmjereni graf bez ciklusa, u kojem je vrh β 1 spojen na vrh β 2 ivica usmjerena od β 1 to β 2 ako i samo ako β 2 = β 1 b, gdje b Î B = {0, 1, …, D – 1}, D≥ 2. Za prefiksne kodove (i samo za njih), skup kodnih riječi poklapa se sa skupom krajnjih vrhova (vrhova iz kojih ne potiču ivice) kodno stablo.
Osnovne teoreme kodiranja
Svojstva kodova koja su korisna za njihovu praktičnu primjenu određena su glavnim teoremama kodiranja.
Teorema 5.1. Kraftova nejednakost. Za postojanje jedinstveno dekodiranog (odvojivog) koda koji sadrži N kodne riječi u setu (0, 1, D– 1) sa dužinama n 1 , n 2 , …, n N, potrebno je i dovoljno za nejednakost
Dokaz. Zamislite da postoji stablo koda za prefiksni kod. Koren kodnog stabla formira nivo 0, vrhovi povezani sa korenom forme nivo 1, i tako dalje. Mogući broj vrhova na k-th nivo će biti označen kao D k. Svaki vrh k-th nivo generiše tačno D n – k vrhovi n-th nivo.
n 1 ≤ n 2 ≤…≤ n N = n.
Očigledno, kodna riječ dužine k zabraniti tačno D n – k mogući krajnji vrhovi (vrhovi posljednjeg nivoa). Tada sve kodne riječi koda prefiksa onemogućuju krajnje čvorove. As ukupan broj krajnji vrhovi je D n, zatim nejednakost
,
iz čega sledi da
Time je dokazana Kraftova nejednakost.
Kao rezultat dokaza teoreme 5.1, zaključujemo da postoje barem prefiksni kodovi koji su jednoznačno dekodirani kodovi s dužinama kodne riječi n 1 , n 2 , …, n N zadovoljavajući Kraftovu nejednakost. Sljedeća teorema, nazvana McMillanova tvrdnja, generalizira ovaj zaključak na sve jedinstveno dekodirajuće kodove.
Teorema 5.2. McMillanova nejednakost. Svaki jedinstveno dekodirajući kod zadovoljava Kraftovu nejednakost.
Dokaz. Podignimo sumu na stepen L:
. (5.1)
Neka bude A k je broj kombinacija koje sadrže L kodne riječi ukupne dužine k. Tada se izraz (6.1) može predstaviti kao
,
gdje L max- maksimalna dužina poruke koje sadrže L kodne riječi. Ako je kod jedinstveno dekodirajući, onda sve sekvence iz L kodne riječi ukupne dužine k drugačije. Pošto ima svega D k onda moguće sekvence A k ≤ D k i onda
As L je broj nezavisnih kodnih riječi koje se koriste za konstruiranje svih mogućih nizova dužine koja ne prelazi L max. Dakle L ≤ L max i 
. I iz ovoga proizilazi da
Budući da je gore navedeno rezoniranje važeće za svaki jedinstveno dekodirajući kod, a ne samo za prefiksne kodove, McMillanova tvrdnja je dokazana.
Sljedeće teoreme povezuju entropiju izvora poruke i prosječnu dužinu kodne riječi.
Teorema 5.3. Teorema izvornog kodiranja I. Za bilo koji diskretni izvor bez memorije X sa konačnim alfabetom i entropijom H(X) postoje D-ic prefiks kod, u kojem prosječna dužina kodne riječi zadovoljava nejednakost
. (5.2)
Dokaz. Prije svega, hajde da to objasnimo diskretni izvor bez memorije, opisan je modelom koji ne uzima u obzir veze između simbola poruke. Dokažimo sada lijevu stranu nejednakosti (6.2):
Da bismo to učinili, koristimo definiciju entropije i Kraftove nejednakosti:
Da bismo dokazali desnu stranu nejednakosti (6.2), prepisujemo Kraftovu nejednakost u sljedećem obliku:
.
Zatim biramo za svaki pojam tako najmanji cijeli broj n i, pri čemu
Pošto je Kraftova nejednakost sačuvana pod takvim izborom, moguće je konstruisati odgovarajući prefiks kod. As n i je onda najmanji cijeli broj n i– 1 sajam
Tako je dokazana teorema izvornog kodiranja I. Određuje da prosječna dužina kodne riječi ne može biti manja od entropije izvora poruke. Imajte na umu da je u dokazu teoreme korištena ista notacija kao i pri razmatranju Kraftove nejednakosti.
Teorema 5.4. Teorema izvornog kodiranja II. Za dužinu bloka L postoje D-ary prefiks kod u kojem prosječna dužina kodne riječi po simbolu zadovoljava nejednakost
,
gdje 
.
Dokaz. Ovdje su blokovi simbola i H(X 1 , X 2 , …, X L) je entropija izvora poruke po bloku L karaktera. Da bismo dokazali teoremu, možemo koristiti teoremu izvornog kodiranja I:
Osim toga, pošto je minimalna dostižna dužina kodne riječi po simbolu vrijednost, onda kada D= 2 redundantnost koda može se odrediti formulom 
.
1 | |
