Za učinkovitu upotrebu kanala (povećanje faktora opterećenja λ→1), potrebno ga je uskladiti s izvorom informacija na ulazu. Takvo podudaranje je moguće za oba kanala bez smetnji i sa smetnjama, na temelju teorema o kodiranju kanala koje je predložio Shannon.
Teorem kodiranja za kanal bez smetnji.
Ako izvor poruke ima kapacitet [bit/sek], a komunikacijski kanal ima kapacitet [bit/sek], tada možete kodirati poruku na takav način da prenosite informacije preko komunikacijskog kanala prosječnom brzinom, proizvoljno blizu vrijednosti, ali je ne premašiti.
Shannon je također predložio metodu za takvo kodiranje, koja je nazvana optimalno kodiranje. Ideja takvog kodiranja kasnije je razvijena u radovima Fanoa i Huffmana. Trenutno se takvi kodovi široko koriste u praksi (učinkovito i optimalno kodiranje).
Shannonov teorem o izravnom kodiranju za kanal s šumom.
Za bilo koju izvedbu izvora poruke [bit/sek] manju od propusnosti [bit/sek], postoji metoda kodiranja koja omogućuje prijenos svih informacija koje je stvorio izvor poruke s proizvoljno malom vjerojatnošću pogreške ε.
Inverzni teorem kodiranja za kanal s šumom.
Ne postoji metoda kodiranja koja omogućuje prijenos informacija s bilo kakvom vjerojatnošću pogreške ako je izvedba izvora poruke veća propusnost kanal.
Dokaz teorema o kodiranju za kanal sa šumom matematički je prilično dugačak, pa ćemo se ograničiti na opću raspravu o njegovim fizičkim aspektima. praktična aplikacija:
1. Teorem utvrđuje teorijska granica moguću učinkovitost sustava uz pouzdan prijenos informacija. Iz teorema proizlazi da smetnje u kanalu ne postavljaju ograničenja na točnost prijenosa. Ograničenja su nametnuta samo na brzinu prijenosa pri kojoj se može postići proizvoljno visoka pouzdanost prijenosa.
U isto vrijeme, pouzdanost diskretni kanal obično se procjenjuje vrijednošću vjerojatnosti pogrešnog prijema jednog simbola. Što je manja vjerojatnost pogreške, veća je pouzdanost kanala. Pouzdanost pak karakterizira otpornost na buku informacijski sistem.
Brzina prijenosa informacija karakterizira učinkovitost sustava.
2. Teorem se ne bavi pitanjem načina konstruiranja kodova koji osiguravaju navedeni idealni prijenos. Nakon što je potkrijepila temeljnu mogućnost takvog kodiranja, mobilizirala je napore znanstvenika da razviju specifične kodove.
3. Pri bilo kojoj konačnoj brzini prijenosa informacija, do propusnosti, proizvoljno mala vjerojatnost pogreške postiže se samo uz neograničeno povećanje trajanja kodiranih nizova znakova. Stoga je prijenos bez grešaka u prisutnosti smetnji samo teoretski moguć. Osiguravanje prijenosa informacija s vrlo malom vjerojatnošću pogreške i s prilično visokom učinkovitošću moguće je kod kodiranja iznimno dugih nizova znakova.
Shannonov izravni teorem za izvor opći pogled Ne smije se miješati s drugim Shannonovim teoremima.
Shannonovi teoremi za opći izvor opisuju mogućnosti kodiranja općeg izvora korištenjem odvojivih kodova. Drugim riječima, opisane su najveće moguće mogućnosti kodiranja bez gubitaka.
Izravni teorem
Kada se primijeni na kodiranje slovo po slovo, izravni teorem može se formulirati na sljedeći način:
Da bi se dokazao teorem, ispitane su karakteristike Shannon-Fano koda. Ovaj kod zadovoljava uvjete teoreme i ima navedena svojstva.
Konverzni teorem
Obrnuti teorem ograničava maksimalni omjer kompresije koji se može postići kodiranjem bez gubitaka. Kada se primjenjuje na kodiranje slovo po slovo, opisuje ograničenje prosječne duljine kodna riječ za bilo koji odvojivi kod.
Za svaki odvojivi kod s duljinama w 1 ,w 2 ,...,w K prosječna duljina poruke je veća ili jednaka entropiji izvora U, normaliziran na binarni logaritam broja slova D u abecedi kodera:
Književnost
- Gabidulin, E.M., Pilipchuk, N.I.§3.4 Shannonovi teoremi za izvor // Predavanja iz teorije informacija. - M.: MIPT, 2007. - str. 49-52. - 214 str. - ISBN 5-7417-0197-3
Zaklada Wikimedia. 2010.
Pogledajte što je "Shannonov izravni teorem za izvor općeg oblika" u drugim rječnicima:
Ne smije se miješati s drugim Shannonovim teoremima. Shannonovi teoremi za opći izvor opisuju mogućnosti kodiranja općeg izvora korištenjem kodova koji se mogu odvojiti. Drugim riječima, opisane su najveće moguće mogućnosti... ... Wikipedia
Wikipedia ima članke o drugim osobama s ovim prezimenom, pogledajte Shannon. Claude Elwood Shannon Claude Elwood Shannon ... Wikipedia
Claude Elwood Shannon (rođen 30. travnja 1916., Petoskey, Michigan, Michigan, SAD, umro 24. veljače 2001., Medford, Massachusetts, SAD) američki matematičar i inženjer elektrotehnike, jedan od tvoraca matematičke teorije... ... Wikipedia
Claude Elwood Shannon (rođen 30. travnja 1916., Petoskey, Michigan, Michigan, SAD, umro 24. veljače 2001., Medford, Massachusetts, SAD) američki matematičar i inženjer elektrotehnike, jedan od tvoraca matematičke teorije... ... Wikipedia
- (engleski Claude Elwood Shannon; rođen 30. travnja 1916., Petoskey, Michigan, Michigan, SAD, umro 24. veljače 2001., Medford, Massachusetts, SAD) američki matematičar i inženjer elektrotehnike, jedan od tvoraca matematičke teorije informacija, u . .. ... Wikipedia
Claude Elwood Shannon (rođen 30. travnja 1916., Petoskey, Michigan, Michigan, SAD, umro 24. veljače 2001., Medford, Massachusetts, SAD) američki matematičar i inženjer elektrotehnike, jedan od tvoraca matematičke teorije... ... Wikipedia
Claude Elwood Shannon (rođen 30. travnja 1916., Petoskey, Michigan, Michigan, SAD, umro 24. veljače 2001., Medford, Massachusetts, SAD) američki matematičar i inženjer elektrotehnike, jedan od tvoraca matematičke teorije... ... Wikipedia
Claude Elwood Shannon (rođen 30. travnja 1916., Petoskey, Michigan, Michigan, SAD, umro 24. veljače 2001., Medford, Massachusetts, SAD) američki matematičar i inženjer elektrotehnike, jedan od tvoraca matematičke teorije... ... Wikipedia
Program tečaja
"Teorija informacija i kodiranja"
Nastava se izvodi na 4. godini, VII semestar,
51 sat, nositelj izv. prof
Pojam informacije, entropije. Komunikacijski sustavi. Diskretni izvori. Opis korištenja izvora slučajni proces. Statistička neovisnost. Markovi izvori. Ergodičnost. Ergodičnost Bernoullijevog izvora.
Derivacija entropijske formule (prema Fadejevu). Međusobno informiranje i njegova svojstva. Svojstva entropije. Teorem o maksimalna vrijednost entropija. Entropija po jedinici vremena izvora poruke.
Problem kodiranja diskretnog izvora kodovima jednake dužine. Brzina kodiranja. Skupovi visoke vjerojatnosti. Izravni i inverzni teoremi za kodiranje diskretnog izvora s kodovima jednake duljine.
Problem kodiranja izvora kodovima nejednake duljine. Trošak kodiranja. Nedvosmisleno dešifrirani kodovi. Prefiksni kodovi. Kodiranje slovo po slovo. Nužan i dovoljan uvjet za jedinstvenu dešifrabilnost koda. Puni kodovi. Teorem za kodiranje diskretnog izvora s kodovima nejednake duljine. Algoritmi za konstruiranje optimalnih kodova (Fano, Shannon, Huffman). Konstrukcija binarnog optimalnog koda s jednakom distribucijom vjerojatnosti ulaznih vjerojatnosti. Primjena teorije informacija rezultira dokazivanjem donje i gornje granice složenosti implementacije Booleove funkcije u nekim klasama upravljačkih sustava. Metoda za konstruiranje optimalnog koda pod uvjetom da je distribucija vjerojatnosti izvornih slova nepoznata. Markovljev teorem o jedinstvenoj dešifriranju koda. Prilagodljivi algoritmi za kompresiju informacija.
Diskretni kanal bez memorije. Binarni simetrični kanal. Brzina prijenosa informacija u kanalu. Kapacitet kanala. Prošireni kanal i njegov kapacitet. Odlučni obrasci i grupiranja opažanja. Mogućnost pogrešnog prijenosa informacija. Feinsteinova nejednakost. Izravni teorem za kodiranje kanala bez memorije. Fanova nejednakost. Teorem o obradi informacija. Inverzija teorema kodiranja.
Teorija kodiranja otpornog na smetnje. Kriterij najveće vjerojatnosti. Kodna udaljenost. Paritetni kodovi. Generativni i kontrolne matrice. Sindrom. Algoritam za dekodiranje kodova za provjeru pariteta. Linearni kodovi i njihov algoritam dekodiranja. Hamming vezan. Hammingov kod. Ciklički kodovi. Kodiranje i dekodiranje cikličkih kodova.
KNJIŽEVNOST
1. Gallagher R. Teorija informacija i pouzdana veza., M., Sov. Radio, 1979.
2. Krichevsky E. Predavanja o teoriji i informacijama, Novosibirsk, NSU, 1966.
3. Kolesnik V., Poltyrev G. Tečaj teorije informacija, Nauka, 1982.
4. Fainstein A. Osnove teorije informacija, M., IL, 1960.
5. Peterson V., Weldon F. Kodovi za ispravljanje pogrešaka, M., Mir, 1976.
6. Berlekamp Algebarska teorija kodiranja, M., Mir, 1971.
Informacijski kapacitet diskretnih (4.4) i kapacitet kontinuiranih (4.7) kanala karakterizira njihove maksimalne mogućnosti kao sredstva prijenosa informacija. Oni su otkriveni u temeljnim teoremima teorije informacija, koji su poznati kao temeljni teoremi Shannonovog kodiranja. U odnosu na diskretni kanal glasi:
Teorem 4.4.1. (Teorem o izravnom kodiranju za DKBP.) Za diskretni kanal bez memorije kodnim brzinama R, manji od informacijskog kapaciteta, uvijek postoji kod za koji prosječna vjerojatnost pogreške teži nuli kako se duljina kodne riječi povećava.
U slučaju kontinuiranog kanala, formulira se kao
Teorem 4.4.2. (Teorem o izravnom kodiranju za AWGN kanal). Preko AWGN kanala s neograničenom propusnošću, informacije se mogu prenijeti s proizvoljno niskom vjerojatnošću pogreške ako je brzina prijenosa manja od propusnosti.
Obrnuti teorem kaže:
Teorem 4.4.3. Brzinom prijenosa podataka 
, veći kapacitet komunikacijskog kanala C, niti jedan kod neće dati proizvoljno malu vjerojatnost greške dekodiranja, tj. apsolutno pouzdan prijenos poruka.
Treba napomenuti da ako se inverzni teorem dokazuje za proizvoljan model komunikacijskog kanala, tada se izravni dokazuje samo za određene vrste kanala.
Rezultati teorema kodiranja za kanal s šumom pomalo su neočekivani. Doista, na prvi se pogled čini da smanjenje vjerojatnosti pogrešaka u prijenosu poruka zahtijeva odgovarajuće smanjenje brzine prijenosa i da bi potonja trebala težiti nuli zajedno s vjerojatnošću pogrešaka. Ovaj zaključak, posebice, proizlazi iz razmatranja višestrukog ponovnog prijenosa simbola preko kanala kao načina da se smanji vjerojatnost pogrešaka u prijenosu poruka. U ovom slučaju, uz prisutnost smetnji u komunikacijskom kanalu, moguće je osigurati da vjerojatnost pogreške u prijenosu poruke teži nuli samo ako brzina prijenosa teži nuli.
Međutim, teorem o kodiranju pokazuje da je u načelu moguće slati brzinom proizvoljno blizu C, dok se postiže proizvoljno mala vjerojatnost pogreške. Nažalost, teoremi, iako ukazuju na temeljno postojanje koda otpornog na pogreške, ne daju recept za njegovo pronalaženje. Možemo samo napomenuti da je za to potrebno koristiti dugačke kodove. Štoviše, kako se brzina prijenosa približava propusnosti i smanjuje se vjerojatnost pogrešaka, kod postaje složeniji zbog povećanja duljine blokova, što dovodi do oštre komplikacije uređaja za kodiranje i dekodiranje, kao i kašnjenja u izlaz informacija tijekom dekodiranja. Trenutno korištene metode kodiranja, o kojima će biti riječi kasnije, ne ostvaruju potencijalne mogućnosti komunikacijskog sustava. Jedina iznimka su nedavno otvoreni turbo kodovi.
1Ovaj rezultat vrijedi za sve simetrične kanale.
Kodiranje informacija
Osnovni koncepti
Shannonovi teoremi o kodiranju poruka spomenuti su gore. Intuitivno je jasno da je kodiranje operacija pretvaranja informacija u oblik potreban za naknadnu obradu (prijenos preko komunikacijskog kanala, pohranjivanje u memoriju računalni sustav, korištenje za donošenje odluka itd.). Također je jasno da je pri izgradnji bilo kojeg informacijskog sustava nemoguće bez kodiranja: svaka prezentacija informacija podrazumijeva korištenje neke vrste kodova. Stoga ćemo dalje detaljnije analizirati teorijska osnova kodiranje informacija.
Neka A– proizvoljna abeceda. Elementi abecede A nazivaju se slovima (ili simbolima), a konačni nizovi sastavljeni od slova nazivaju se riječima u A. Vjeruje se da u bilo kojoj abecedi postoji prazna riječ koja ne sadrži slova.
Riječ α 1 naziva se početak (prefiks) riječi α , ako riječ postoji α 2 , tako da α = α 1 α 2 ; ujedno i riječ α 1 naziva se pravilan početak riječi α , Ako α 2 nije prazna riječ. Duljina riječi je broj slova u riječi (prazna riječ ima duljinu 0). Snimiti α 1 α 2 označava vezu (ulančanje) riječi α 1 i α 2. Riječ α 2 naziva se završetak (sufiks) riječi α , ako riječ postoji α 1, tako da α = α 1 α 2 ; ujedno i riječ α 2 naziva se pravilan završetak riječi α , Ako α 1 nije prazna riječ. Prazna riječ se po definiciji smatra početkom i završetkom svake riječi α .
Razmotrite abecedu B = {0, 1, …, D– 1), gdje D≥ 2, i proizvoljan skup C. Proizvoljni prikaz skupa C u mnogo riječi u abecedi B nazvao D-ary skup kodiranja C(na D= 2 kodiranje će biti binarno). Inverzno preslikavanje naziva se dekodiranje. Navedimo primjere kodiranja.
1. Kodiranje skupa prirodnih brojeva, u kojem je broj n= 0 odgovara riječi e(0) = 0, i broj n ≥ 1 binarna riječ
e(n) = b 1 b 2 … b l (n)
najmanja duljina koja zadovoljava uvjet
Očito 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, a najmanji cijeli broj veći od x. Riječ e(n) naziva se binarni zapis broja n, a ovo kodiranje je reprezentacija brojeva u binarni sustav Računanje. Ovo kodiranje je jedan na jedan jer kada n 1 ≠ n 2 riječi e(n 1) i e(n 2) drugačiji. Tablica 5.1 prikazuje prikaz prvih 16 prirodnih brojeva u binarnom brojevnom sustavu.
Tablica 5.1
Kodiranje e(n)
| n | e(n) | n | e(n) | n | e(n) | n | e(n) |
2. Kodiranje prve 2 k prirodnih brojeva, za koje svaki broj n (0 ≤ n < 2k) odgovara riječi
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) – prikaz broja n u binarnom brojevnom sustavu o kojem je gore bilo riječi. Ovo kodiranje je za prvih 16 prirodnih brojeva ( k= 4) dan je u tablici 5.2.
Tablica 5.2
Kodiranje e k(n)
| n | e k(n) | n | e k(n) | n | e k(n) | n | e k(n) |
Neka A = {a ja, ja= 1, 2, ...) – konačna ili brojna abeceda čija su slova numerirana prirodni brojevi. U ovom slučaju, kodiranje slova abecede A može se odrediti nizom D- doslovne riječi V = {v i, ja= 1, 2, …), gdje v i postoji slika slova a ja. Takvi nizovi riječi (iz skupa V) nazivaju se kodovi (abecede A). Ako je data šifra V abeceda A, zatim kodiranje riječi, u kojem se svaka riječ a ja 1 a ja 2 …a ik odgovara riječi v i 1 v i 2 …v ik, nazvano kodiranje slovo po slovo.
Prilikom prelaska s kodiranja slova abecede jedan na jedan na kodiranje riječi u abecedi slovo po slovo, svojstvo znaka jedan na jedan možda neće biti sačuvano. Na primjer, kodiranje e(n) ne sprema ovo svojstvo, i kodiranje e k(n) sprema ga. Svojstvo jedan-na-jedan očuvano je kodovima koji se mogu odvojiti. Kodirati V = {v i, ja= 1, 2, …) naziva se odvojivim ako iz svake jednakosti oblika
v i 1 v i 2 …v ik = v j 1 v j 2 …vjl
slijedi to l = k I v i 1 = v j 1 , v i 2 = v j 2 , … , v ik = vjl. Odvojivi kodovi se također nazivaju jedinstveno dekodirajući kodovi.
Prefiks kodovi pripadaju klasi odvojivih kodova. Kodirati V = {v i, ja= 1, 2, …) naziva se prefiks ako nema riječi vk nije početak (prefiks) bilo koje riječi v l, l ≠ k. Ako se svaka riječ koda prefiksa zamijeni njezinim najmanjim početkom, koji nije početak drugih kodnih riječi, tada će rezultirajući kod također biti prefiks. Ova se operacija naziva skraćivanje prefiksnog koda.
Za proizvoljni kod V, koja se sastoji od različite riječi, možete izgraditi stablo koda. Ovo je usmjereni graf koji ne sadrži cikluse u kojima je vrh β 1 spojen na vrh β 2 rub usmjeren od β 1 do β 2 ako i samo ako β 2 = β 1 b, Gdje b Î B = {0, 1, …, D – 1}, D≥ 2. Za prefiks kodove (i samo za njih), skup kodnih riječi podudara se sa skupom krajnjih vrhova (vrhova iz kojih ne potječu bridovi) kodno stablo.
Osnovni teoremi kodiranja
Svojstva kodova koja su korisna za njihovu praktičnu primjenu određena su osnovnim teoremima kodiranja.
Teorem 5.1. Kraftova nejednakost. Za postojanje jedinstveno dekodibilnog (odvojivog) koda koji sadrži N kodne riječi u skupu (0, 1, D– 1) s duljinama n 1 , n 2 , …, n N, potrebno je i dovoljno da nejednakost vrijedi
Dokaz. Zamislimo da imamo kodno stablo za prefiks kod. Korijen stabla koda čini razinu 0, vrhovi povezani s korijenom čine razinu 1, itd. Mogući broj vrhova po k-tu razinu označavamo kao Dk. Svaki vrh k razina mrijesti točno Dn – k vrhovi n-tu razinu.
n 1 ≤ n 2 ≤…≤ n N = n.
Očito, kodna riječ duljine k zabranjuje točno Dn – k mogući krajnji vrhovi (vrhovi posljednje razine). Tada sve kodne riječi koda prefiksa zabranjuju krajnje vrhove. Jer ukupni broj krajnji vrhovi su jednaki Dn, tada je nejednakost istinita
,
iz čega proizlazi da
Dakle, Kraftova nejednakost je dokazana.
Kao rezultat dokaza teorema 5.1, zaključuje se da postoje barem prefiksni kodovi koji su jedinstveno dekodibilni kodovi s duljinama kodnih riječi n 1 , n 2 , …, n N, zadovoljavajući Kraftovu nejednakost. Sljedeći teorem, nazvan McMillanova izjava, generalizira ovaj zaključak za sve jedinstveno dekodibilne kodove.
Teorem 5.2. McMillanova nejednakost. Svaki jedinstveno dekodirajući kod zadovoljava Kraftovu nejednakost.
Dokaz. Podignimo zbroj na potenciju L:
. (5.1)
Neka A k– broj kombinacija koje sadrže L kodne riječi ukupne duljine k. Tada se izraz (6.1) može prikazati kao
,
Gdje L max – maksimalna duljina poruke koje sadrže Lšifrirane riječi. Ako se kod može jedinstveno dekodirati, tada su sve sekvence iz L kodne riječi ukupne dužine k su različiti. Budući da postoji samo Dk mogući nizovi, dakle A k ≤ Dk i onda
Jer L je broj neovisnih kodnih riječi koje se koriste za konstruiranje svih mogućih nizova duljine koja ne prelazi L max. Zato L ≤ L max i 
. A iz ovoga slijedi da
Budući da gornje razmišljanje vrijedi za svaki kod koji se može jedinstveno dekodirati, a ne samo za prefiks kodove, McMillanova izjava je dokazana.
Sljedeći teoremi povezuju entropiju izvora poruke i prosječnu duljinu kodne riječi.
Teorem 5.3. Teorem o izvornom kodiranju I. Za svaki diskretni izvor bez memorije x s konačnom abecedom i entropijom H(x) postoji D-ichny kod prefiksa, u kojoj prosječna duljina kodne riječi zadovoljava nejednakost
. (5.2)
Dokaz. Prije svega, razjasnimo to diskretni izvor bez memorije, opisuje se modelom koji ne uzima u obzir veze između simbola poruka. Sada dokažemo lijevu stranu nejednakosti (6.2):
Da bismo to učinili, koristimo se definicijom entropije i Kraftovom nejednakošću:
Da bismo dokazali desnu stranu nejednakosti (6.2), prepisujemo Kraftovu nejednakost u sljedećem obliku:
.
Zatim za svaki član biramo najmanji cijeli broj n i, na kojem
Budući da Kraftova nejednakost ostaje ista s ovim izborom, možemo konstruirati odgovarajući prefiks kod. Jer n i je najmanji cijeli broj, tada for n i– 1 je fer
Dakle, teorem I kodiranja izvora je dokazan. Određuje da prosječna duljina kodne riječi ne može biti manja od entropije izvora poruke. Imajte na umu da je dokaz teorema koristio isti zapis kao i kada je razmatrana Kraftova nejednakost.
Teorem 5.4. Teorem o izvornom kodiranju II. Za duljinu bloka L postoji D-arni prefiksni kod u kojem prosječna duljina kodne riječi po znaku zadovoljava nejednakost
,
Gdje 
.
Dokaz. Ovdje su blokovi znakova i H(x 1 , x 2 , …, x L) je entropija izvora poruke po bloku L likovi. Da biste dokazali teorem, možete koristiti teorem I izvornog kodiranja:
Nadalje, budući da je minimalna moguća duljina kodne riječi po simbolu vrijednost , onda kada D= 2 redundantnost koda može se odrediti formulom 
.
1 | |
