Izravni Shanonov teorem za opći izvor.

Rad je dodan na web mjesto: 2016-03-30

; boja: # 000000 "xml: lang =" ru-RU "lang =" ru-RU "> 5. Kodiranje informacija

; boja: # 000000 "xml: lang =" ru-RU "lang =" ru-RU "> 5.1. 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, koristiti za donošenje odluka itd.). Također je jasno da prilikom konstruiranja bilo informacijski sistem nemoguće je bez kodiranja: svaki prikaz informacija podrazumijeva korištenje nekih kodova. Stoga ćemo dalje detaljno analizirati teorijske osnove informacije o kodiranju.

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 ... U ovom slučaju smatra se da u bilo kojoj abecedi postoji prazna riječ koja ne sadrži slova.

Riječ α 1 naziva početak (prefiks) riječiα ako postoji riječα 2 tako da je α = α 1 α 2; štoviše, riječ α 1 naziva vlastitim početkom riječiα ako je α 2 Nije prazna riječ. Duljina riječi je broj slova u riječi (prazna riječ ima duljinu 0). Snimanjeα 1 α 2 označava povezanost (konkatenaciju) riječiα 1 i α 2. Riječ α 2 naziva se završetak (sufiks) riječiα ako postoji riječα 1, tako da je α = α 1 α 2; štoviše, riječ α 2 nazivaju vlastiti završetak riječiα ako je α 1 Nije prazna riječ. Prazna riječ se po definiciji smatra početkom i krajem svake riječi.α .

Razmotrite abecedu B = (0, 1, ..., D - 1), gdje je D ≥ 2, i proizvoljan skup C ... Proizvoljno postavljeni prikaz C u razne riječi u abecedi B poziv D -kodiranjem skupa C (za D = 2 kodiranje će biti binarno). Obrnuto preslikavanje naziva se dekodiranje. Evo nekoliko primjera kodiranja.

1. Kodiranje skupa prirodnih brojeva, u kojem je broj n = 0 odgovara riječi e (0) = 0, a broj n ≥ 1 binarna riječ

e (n) = b 1 b 2 ... b l (n)

najkraća duljina koja zadovoljava uvjet

Očito, b 1 = 1, 2 l (n) - 1 ≤ n< 2 l (n ) i stoga

l (n) = + 1 =] log (n + 1) [,

gdje je [x] i] x [označava, odnosno, 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 dano je kodiranje prikaz brojeva u binarni sustav računanje. Ovo kodiranje je jedan prema jedan, budući da za n 1 ≠ n 2 riječi e (n 1) i e (n 2 ) različiti su. Tablica 5.1 prikazuje prikaz prvih 16 prirodnih brojeva u binarnom brojevnom sustavu.

"xml: lang =" ru-RU "lang =" ru-RU "> Tablica 5.1

"xml: lang =" ru-RU "lang =" ru-RU "> Kodiranje"xml: lang =" hr-US "lang =" hr-US "> e"xml: lang =" ru-RU "lang =" ru-RU "> ("xml: lang =" hr-US "lang =" hr-US "> n"xml: lang =" ru-RU "lang =" ru-RU ">)

"xml: lang =" hr-US "lang =" hr-US "> n	"xml: lang =" hr-US "lang =" hr-US "> e"xml: lang =" hr-US "lang =" hr-US "> ("xml: lang =" hr-US "lang =" hr-US "> n"xml: lang =" hr-US "lang =" hr-US ">)	"xml: lang =" hr-US "lang =" hr-US "> n	"xml: lang =" hr-US "lang =" hr-US "> e"xml: lang =" hr-US "lang =" hr-US "> ("xml: lang =" hr-US "lang =" hr-US "> n"xml: lang =" hr-US "lang =" hr-US ">)	"xml: lang =" hr-US "lang =" hr-US "> n	"xml: lang =" hr-US "lang =" hr-US "> e"xml: lang =" hr-US "lang =" hr-US "> ("xml: lang =" hr-US "lang =" hr-US "> n"xml: lang =" hr-US "lang =" hr-US ">)	"xml: lang =" hr-US "lang =" hr-US "> n	"xml: lang =" hr-US "lang =" hr-US "> e"xml: lang =" hr-US "lang =" hr-US "> ("xml: lang =" hr-US "lang =" hr-US "> n"xml: lang =" hr-US "lang =" hr-US ">)
"xml: lang =" hr-US "lang =" hr-US "> 0	"xml: lang =" hr-US "lang =" hr-US "> 0	"xml: lang =" hr-US "lang =" hr-US "> 4	"xml: lang =" hr-US "lang =" hr-US "> 100	"xml: lang =" hr-US "lang =" hr-US "> 8	"xml: lang =" hr-US "lang =" hr-US "> 1000	"xml: lang =" hr-US "lang =" hr-US "> 12	"xml: lang =" en-US "lang =" hr-US "> 1100
"xml: lang =" hr-US "lang =" hr-US "> 1	"xml: lang =" hr-US "lang =" hr-US "> 1	"xml: lang =" hr-US "lang =" hr-US "> 5	"xml: lang =" hr-US "lang =" hr-US "> 101	"xml: lang =" hr-US "lang =" hr-US "> 9	"xml: lang =" hr-US "lang =" hr-US "> 1001	"xml: lang =" hr-US "lang =" hr-US "> 13	"xml: lang =" hr-US "lang =" hr-US "> 1101
"xml: lang =" hr-US "lang =" hr-US "> 2	"xml: lang =" hr-US "lang =" hr-US "> 10	"xml: lang =" hr-US "lang =" hr-US "> 6	"xml: lang =" hr-US "lang =" hr-US "> 110	"xml: lang =" hr-US "lang =" hr-US "> 10	"xml: lang =" hr-US "lang =" hr-US "> 1010	"xml: lang =" hr-US "lang =" hr-US "> 14	"xml: lang =" hr-US "lang =" hr-US "> 1110
"xml: lang =" hr-US "lang =" hr-US "> 3	"xml: lang =" hr-US "lang =" hr-US "> 11	"xml: lang =" hr-US "lang =" hr-US "> 7	"xml: lang =" hr-US "lang =" hr-US "> 111	"xml: lang =" hr-US "lang =" hr-US "> 11	"xml: lang =" hr-US "lang =" hr-US "> 1011	"xml: lang =" hr-US "lang =" hr-US "> 15	"xml: lang =" hr-US "lang =" hr-US "> 1111

2. Kodiranje prvih 2 k prirodni brojevi, za koje je svaki broj n (0 ≤ n< 2 k ) riječ

e k (n) = 0 k - l (n) e (n),

gdje je oznaka 0 k - l (n) označava riječ koja se sastoji od k - l (n) nule, e (n ) - brojčani prikaz n u binarnom brojevnom sustavu o kojem smo gore govorili. Ovo kodiranje za prvih 16 prirodnih brojeva ( k = 4) dat je u tablici 5.2.

"xml: lang =" ru-RU "lang =" ru-RU "> Tablica 5."xml: lang =" hr-US "lang =" hr-US "> 2

"xml: lang =" ru-RU "lang =" ru-RU "> Kodiranje"xml: lang =" hr-US "lang =" hr-US "> e; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> k"xml: lang =" ru-RU "lang =" ru-RU "> ("xml: lang =" hr-US "lang =" hr-US "> n"xml: lang =" ru-RU "lang =" ru-RU ">)

"xml: lang =" hr-US "lang =" hr-US "> n	"xml: lang =" hr-US "lang =" hr-US "> e; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> k"xml: lang =" hr-US "lang =" hr-US "> ("xml: lang =" hr-US "lang =" hr-US "> n"xml: lang =" hr-US "lang =" hr-US ">)	"xml: lang =" hr-US "lang =" hr-US "> n	"xml: lang =" hr-US "lang =" hr-US "> e; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> k"xml: lang =" hr-US "lang =" hr-US "> ("xml: lang =" hr-US "lang =" hr-US "> n"xml: lang =" hr-US "lang =" hr-US ">)	"xml: lang =" hr-US "lang =" hr-US "> n	"xml: lang =" hr-US "lang =" hr-US "> e; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> k"xml: lang =" hr-US "lang =" hr-US "> ("xml: lang =" hr-US "lang =" hr-US "> n"xml: lang =" hr-US "lang =" hr-US ">)	"xml: lang =" hr-US "lang =" hr-US "> n	"xml: lang =" hr-US "lang =" hr-US "> e; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> k"xml: lang =" hr-US "lang =" hr-US "> ("xml: lang =" hr-US "lang =" hr-US "> n"xml: lang =" hr-US "lang =" hr-US ">)
"xml: lang =" hr-US "lang =" hr-US "> 0	"xml: lang =" hr-US "lang =" hr-US "> 0000	"xml: lang =" hr-US "lang =" hr-US "> 4	"xml: lang =" hr-US "lang =" hr-US "> 0100	"xml: lang =" hr-US "lang =" hr-US "> 8	"xml: lang =" hr-US "lang =" hr-US "> 1000	"xml: lang =" hr-US "lang =" hr-US "> 12	"xml: lang =" en-US "lang =" hr-US "> 1100
"xml: lang =" hr-US "lang =" hr-US "> 1	"xml: lang =" hr-US "lang =" hr-US "> 0001	"xml: lang =" hr-US "lang =" hr-US "> 5	"xml: lang =" hr-US "lang =" hr-US "> 0101	"xml: lang =" hr-US "lang =" hr-US "> 9	"xml: lang =" hr-US "lang =" hr-US "> 1001	"xml: lang =" hr-US "lang =" hr-US "> 13	"xml: lang =" hr-US "lang =" hr-US "> 1101
"xml: lang =" hr-US "lang =" hr-US "> 2	"xml: lang =" hr-US "lang =" hr-US "> 0010	"xml: lang =" hr-US "lang =" hr-US "> 6	"xml: lang =" hr-US "lang =" hr-US "> 0110	"xml: lang =" hr-US "lang =" hr-US "> 10	"xml: lang =" hr-US "lang =" hr-US "> 1010	"xml: lang =" hr-US "lang =" hr-US "> 14	"xml: lang =" hr-US "lang =" hr-US "> 1110
"xml: lang =" hr-US "lang =" hr-US "> 3	"xml: lang =" hr-US "lang =" hr-US "> 0011	"xml: lang =" hr-US "lang =" hr-US "> 7	"xml: lang =" hr-US "lang =" hr-US "> 0111	"xml: lang =" hr-US "lang =" hr-US "> 11	"xml: lang =" hr-US "lang =" hr-US "> 1011	"xml: lang =" hr-US "lang =" hr-US "> 15	"xml: lang =" hr-US "lang =" hr-US "> 1111

Neka je A = (a i, i = 1, 2, ...) - 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 -arne riječi V = (v i, i = 1, 2, ...), gdje je v i postoji slika slova a i ... Takvi nizovi riječi (iz skupa V ) nazivaju se kodovi (abeceda A). Ako je dan šifra V abecede A , zatim kodiranje riječi u kojima svaka riječ a i 1 a i 2 ... a ik odgovara riječi v i 1 v i 2 ... v ik naziva se kodiranje slovo po slovo.

U prijelazu s jednoznačnog kodiranja slova abecede na slovo po slovo kodiranja riječi u abecedi, svojstvo jedan na jedan možda neće biti očuvano. Na primjer kodiranje e (n ) ne čuva ovu imovinu i kodiranje e k (n ) sprema. Odvojivi kodovi zadržavaju svojstvo jedan na jedan. Kod V = (v i, i = 1, 2, ...) naziva se odvojivim ako je iz svake jednakosti oblika

v i 1 v i 2… v ik = v j 1 v j 2… v jl

slijedi da je l = k i v i 1 = v j 1, v i 2 = v j 2,..., v ik = v jl ... Odvojivi kodovi se također nazivaju jedinstveno dekodiranim kodovima.

Prefiksni kodovi pripadaju klasi odvojivih kodova. Kod V = (v i, i = 1, 2, ...) naziva se prefiks ako nema riječi v k nije početak (prefiks) nijedne 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 s prefiksom. Ova se operacija naziva skraćivanje prefiksa.

Za proizvoljni kod V koja se sastoji od različite riječi, možete izgraditi stablo koda. To je usmjereni graf koji ne sadrži cikluse, u kojem je vrhβ 1 spojena na vrhβ 2 rub usmjeren odβ 1 do β 2 , ako i samo akoβ 2 = β 1 b, gdje je b  B = (0, 1, ..., D - 1), D ≥ 2. Za prefiksne kodove (i samo za njih) skup kodnih riječi poklapa se sa skupom terminalnih vrhova (vrhova iz kojih ne izlaze rubovi) kodno stablo.

5.2. Osnovni teoremi kodiranja

Svojstva kodova korisnih za njih praktična aplikacija, određeni su osnovnim teoremima kodiranja.

Teorem 5.1. Craftova nejednakost.Za postojanje jedinstveno dekodiranog (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 za nejednakost

Dokaz. Zamislite da imate stablo koda za prefiksni kod. Korijen stabla koda je razina 0, čvorovi povezani s korijenom su razine 1, itd. Mogući broj vrhova po k -th razina se označava kao D k. Svaki vrh k -th razina generira točno D n - k vrhova n -te razine.

n 1 ≤ n 2 ≤… ≤ n N = n.

Očito, kodna riječ duljine k točno zabranjuje D n - k mogući krajnji vrhovi (vrhovi posljednje razine). Tada sve kodne riječi prefiksnog koda zabranjuju krajnje vrhove. Jer ukupni broj krajnji vrhovi je D n , zatim nejednakost

iz čega proizlazi da

Time je dokazana Kraftova nejednakost.

Kao rezultat dokaza teorema 5.1, zaključuje se da postoje barem prefiksni kodovi koji su jednoznačno dekodirani 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 dekodirane kodove.

Teorem 5.2. McMillanova nejednakost.Svaki jedinstveno dekodirani kod zadovoljava Craftovu nejednakost.

Dokaz. Podignimo zbroj na stepen L:

. (5.1)

Neka je A k - broj kombinacija koje sadrže L kodne riječi ukupne duljine k ... Tada se izraz (6.1) može predstaviti kao

gdje je L max – maksimalna duljina poruka koja sadrži L kodne riječi. Ako je kod jednoznačno dekodiran, tada su sve sekvence iz L ukupne duljine kodnih riječi k su različiti. Pošto ima svega D k onda moguće sekvence A k ≤ D k i tada

Budući da je L Je li broj neovisnih kodnih riječi koje se koriste za konstruiranje svih mogućih nizova duljine koja ne prelazi L max. Dakle, L ≤ L max i. A iz ovoga proizlazi da

Budući da gornje razmišljanje vrijedi za svaki jedinstveno dekodirani kod, a ne samo za prefiksne kodove, McMillanova izjava je dokazana.

Sljedeći teoremi povezuju entropiju izvora poruke i srednju duljinu kodna riječ.

Teorem 5.3. Teorem izvornog kodiranja ja Za bilo koji diskretni izvor bez memorije x s konačnom abecedom i entropijom H (X) postoji D -osobne kod prefiksa, u kojem prosječna duljina kodne riječi zadovoljava nejednakost

. (5.2)

Dokaz. Prije svega, razjasnimo da je diskretni izvor bez memorije opisan modelom koji ne uzima u obzir veze između simbola poruke. Sada dokazujemo lijevu stranu nejednakosti (6.2):

Za to koristimo definiciju entropije i Kraftove nejednakosti:

Da bismo dokazali desnu stranu nejednakosti (6.2), prepisujemo Kraftovu nejednakost u sljedećem obliku:

Zatim za svaki pojam biramo najmanji cijeli broj n i za koje

Budući da je Kraftova nejednakost sačuvana za ovaj izbor, moguće je konstruirati odgovarajući prefiksni kod. Jer n i Je najmanji cijeli broj, tada za n i - 1

Zatim

Dakle, teorem izvornog kodiranja ja dokazano. Određuje da prosječna duljina kodne riječi ne može biti manja od entropije izvora poruke. Primijetimo da smo u dokazu teorema koristili istu notaciju kao i pri razmatranju Kraftove nejednakosti.

Teorem 5.4. Teorem izvornog kodiranja II. Za blok duljine L postoji D -arnog prefiksnog koda 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 li entropija izvora poruke po bloku od L likovima. Da biste dokazali teorem, možete koristiti teorem izvornog kodiranja ja:

Teorem izvornog kodiranja II omogućuje nam da tvrdimo da postoje takve metode kodiranja za dovoljno dugu poruku da se prosječna duljina kodne riječi može proizvoljno približiti vrijednosti. Doista, za L  ∞, H L (X)  H, gdje je H Da li je entropija izvora poruke po jednom simbolu, nejednakost je istinita

, (5.3)

gdje. To se također može protumačiti na sljedeći način: za bilo koji proizvoljno mali brojε , postoji metoda za kodiranje blokova koji sadrže simbole, u kojoj je nejednakost (5.3) zadovoljena za prosječnu duljinu kodne riječi po simbolu.

Osim toga, budući da je minimalna dostižna duljina kodne riječi po simbolu vrijednost, tada za D = 2 redundantnost koda može se odrediti formulom.

; boja: # 000000 "xml: lang =" ru-RU "lang =" ru-RU "> 5.3. Optimalno kodiranje

Zadatak konstruiranja optimalnog koda je pronaći pozitivne cijele brojeve n 1, n 2, ..., n N minimiziranje prosječne duljine kodne riječi, pod uvjetom da je zadovoljena Kraftova nejednakost:

Prilikom konstruiranja kodova u slučaju abecede A = (a i, i = 1, 2, ..., N ) s poznatom distribucijom vjerojatnosti P = (p i, i = 1, 2, ..., N ) bez gubitka općenitosti, možemo pretpostaviti da su slova abecede A numerirani su silaznim redoslijedom njihovih vjerojatnosti, tj. p 1 ≥ p 2 ≥… ≥ p N ... Osim toga, razmotrit ćemo samo binarne kodove.

Postoje dvije poznate metode (Fano i Shannon) za konstruiranje kodova koji su blizu optimalnih. Fanova metoda je sljedeća. Popis slova, poredan opadajućim redoslijedom vjerojatnosti, podijeljen je u dva uzastopna dijela tako da se zbroji vjerojatnosti slova koja su u njima što manje razlikuju jedan od drugog. Slova iz prvog dijela dobivaju znak 0, a slova iz drugog dijela - znak 1. Zatim se isto radi sa svakim od primljenih dijelova, ako sadrži, tako da barem, dva slova. Proces se nastavlja sve dok se cijeli popis ne podijeli na dijelove koji sadrže po jedno slovo. Svako slovo je povezano s nizom znakova koji su kao rezultat ovog procesa dodijeljeni ovom slovu. Lako je vidjeti da je rezultirajući kod s prefiksom.

Shanonova metoda je primjenjiva samo kada su sve vjerojatnosti pozitivne. Sastoji se u tome da slov a i s vjerojatnošću p i > 0, niz iz n i =] log (1 / p i ) [prve znamenke nakon decimalne točke u proširenju broja u beskonačni razlomak (za a 1 pretpostavljamo da je q 1 = 0). Budući da je u l> k (s obzirom na činjenicu da p l ≤ p k) n l ≥ n k a zatim se tako dobiveni kod stavlja prefiks. Na temelju dobivenog prefiksnog koda konstruira se skraćeni prefiksni kod koji je rezultat kodiranja Shannon metodom.

Na primjer, neka postoji skup slova A = (a 1, a 2, a 3, a 4, a 5, a 6, a 7 ) s distribucijom vjerojatnosti P = (0,2, 0,2, 0,19, 0,12, 0,11, 0,09, 0,09). Provedimo kodiranje slova Fano metodom.

1. Podijelite popis na dva dijela tako da se zbrojevi vjerojatnosti slova uključenih u njih što manje razlikuju jedan od drugog:

A 1 = (a 1, a 2, a 3), P 1 = (0,2, 0,2, 0,19);

A 2 = (a 4, a 5, a 6, a 7), P 2 = (0,12, 0,11, 0,09, 0,09).

2. Dodijelimo slovima iz prvog dijela simbol 0, a slovima drugog dijela simbol 1:

A 1 = (a 1/0, a 2/0, a 3/0);

A 2 = (a 4/1, a 5/1, a 6/1, a 7/1).

3. Ponovimo uzastopno specificirane radnje za svaki dio posebno. V kao rezultat dobivamo:

A 1 1 = (a 1/00);

A 121 = (a 2/010);

A 122 = (a 3/011);

A 211 = (a 4/100);

A 212 = (a 5/101);

A 221 = (a 6/110);

A 222 = (a 7/111).

Rezultirajuće kodne riječi prikazane su za svako slovo desno od kose crte. U ovom slučaju redoslijed indeksa dobivenih jednoslovnih popisa pokazuje slijed dijeljenja izvornog popisa skupina na dijelove.

Fano proces kodiranja prikladno je oblikovan u obliku tablice. Za razmatrani primjer prikazan je u tablici 5.3.

"xml: lang =" ru-RU "lang =" ru-RU "> Tablica 5.3

"xml: lang =" ru-RU "lang =" ru-RU "> Fano kodiranje

"xml: lang =" hr-US "lang =" hr-US "> a; vertical-align: sub "xml: lang =" ru-RU "lang =" ru-RU "> 1	"xml: lang =" ru-RU "lang =" ru-RU "> 0,20	"xml: lang =" ru-RU "lang =" ru-RU "> 0	"xml: lang =" ru-RU "lang =" ru-RU "> 0	"xml: lang =" ru-RU "lang =" ru-RU "> 00
"xml: lang =" hr-US "lang =" hr-US "> a; vertical-align: sub "xml: lang =" ru-RU "lang =" ru-RU "> 2	"xml: lang =" ru-RU "lang =" ru-RU "> 0,20		"xml: lang =" ru-RU "lang =" ru-RU "> 1	"xml: lang =" ru-RU "lang =" ru-RU "> 0	"xml: lang =" ru-RU "lang =" ru-RU "> 010
"xml: lang =" hr-US "lang =" hr-US "> a; vertical-align: sub "xml: lang =" ru-RU "lang =" ru-RU "> 3	"xml: lang =" ru-RU "lang =" ru-RU "> 0,19			"xml: lang =" ru-RU "lang =" ru-RU "> 1	"xml: lang =" ru-RU "lang =" ru-RU "> 011
"xml: lang =" hr-US "lang =" hr-US "> a; vertical-align: sub "xml: lang =" ru-RU "lang =" ru-RU "> 4	"xml: lang =" ru-RU "lang =" ru-RU "> 0.12	"xml: lang =" ru-RU "lang =" ru-RU "> 1	"xml: lang =" ru-RU "lang =" ru-RU "> 0	"xml: lang =" ru-RU "lang =" ru-RU "> 0	"xml: lang =" ru-RU "lang =" ru-RU "> 100
"xml: lang =" hr-US "lang =" hr-US "> a; vertical-align: sub "xml: lang =" ru-RU "lang =" ru-RU "> 5	"xml: lang =" ru-RU "lang =" ru-RU "> 0.11			"xml: lang =" ru-RU "lang =" ru-RU "> 1	"xml: lang =" ru-RU "lang =" ru-RU "> 101
"xml: lang =" hr-US "lang =" hr-US "> a; vertical-align: sub "xml: lang =" ru-RU "lang =" ru-RU "> 6	"xml: lang =" ru-RU "lang =" ru-RU "> 0.09		"xml: lang =" ru-RU "lang =" ru-RU "> 1	"xml: lang =" ru-RU "lang =" ru-RU "> 0	"xml: lang =" ru-RU "lang =" ru-RU "> 110
"xml: lang =" hr-US "lang =" hr-US "> a; vertical-align: sub "xml: lang =" ru-RU "lang =" ru-RU "> 7	"xml: lang =" ru-RU "lang =" ru-RU "> 0.09			"xml: lang =" ru-RU "lang =" ru-RU "> 1	"xml: lang =" ru-RU "lang =" ru-RU "> 111

Odredimo prosječnu duljinu kodne riječi:

Sada napravimo Shannon kodiranje. Proces kodiranja prikazan je u tablici 5.4.

"xml: lang =" ru-RU "lang =" ru-RU "> Tablica 5.4

"xml: lang =" ru-RU "lang =" ru-RU "> Shannon kodiranje

"xml: lang =" hr-US "lang =" hr-US "> a; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> i	"xml: lang =" hr-US "lang =" hr-US "> n; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> i	"xml: lang =" hr-US "lang =" hr-US "> q; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> i	"xml: lang =" ru-RU "lang =" ru-RU "> Kôd"xml: lang =" hr-US "lang =" hr-US "> a; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> i	"xml: lang =" ru-RU "lang =" ru-RU "> Skraćeni kod"xml: lang =" hr-US "lang =" hr-US "> a; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> i
"xml: lang =" hr-US "lang =" hr-US "> a; vertical-align: sub "xml: lang =" ru-RU "lang =" ru-RU "> 1	"xml: lang =" hr-US "lang =" hr-US ">] 2.321… [= 3	"xml: lang =" hr-US "lang =" hr-US "> 0	000	000
a 2	] 2.321… [= 3	0.2	001	001
a 3	] 2.395… [= 3	0.4	011	01
a 4	] 3.058… [= 4	0,59	1001	100
a 5	] 3.183… [= 4	0,71	1011	101
a 6	] 3.472… [= 4	0,82	1101	110
a 7	] 3.472… [= 4	0,91	1110	111

Kao i u prethodnom slučaju, nalazimo prosječnu duljinu kodne riječi:

.

Kao što možete vidjeti, rezultati kodiranja Fano i Shannon metodama u smislu minimiziranja prosječne duljine koda praktički su se poklopili. Stoga se ove metode često smatraju jednom (u Fanovoj formulaciji) i nazivaju Shannon-Fano metoda.

Godine 1952. David Huffman predložio je optimalnu metodu kodiranja prefiksa za diskretni izvori, koji se, za razliku od metoda Shannon i Fano, još uvijek koristi u praksi. D. Huffman je dokazao da će prosječna duljina kodne riječi, dobivena njegovom metodom, biti minimalna. Huffmanovo kodiranje radi se u tri koraka.

1. Redoslijed: slova su poredana silaznim redoslijedom njihovih vjerojatnosti.

2. Redukcija: dva slova s ​​najmanjom vjerojatnošću spajaju se u jedno s ukupnom vjerojatnošću; popis slova se preuređuje prema koraku 1; proces se nastavlja dok se sva slova ne spoje u jedno. U ovom slučaju moguće je postići izjednačavanje duljina kodnih riječi koristeći sljedeću strategiju: ako nekoliko slova ima iste vjerojatnosti, tada se ona dva od njih koja su prethodno imala najmanji broj spojeva kombiniraju (iako to neće utjecati na prosječnu duljinu koda).

3. Kodiranje: počevši od posljednjeg spoja, jednoj komponenti složenog slova uzastopno se dodjeljuje simbol 0, a drugoj - simbolu 1; proces se nastavlja sve dok se sva izvorna slova ne kodiraju.

Izvedimo Huffmanovo kodiranje za skup razmatran u primjerima primjene Fano i Shannon metoda.

1. Izvorni popis pisamaA = { a1 , a2 , a3 , a4 , a5 , a6 , a7 ) je već naručeno odP = {0.2, 0.2, 0.19, 0.12, 0.11, 0.09, 0.09}.

2. Kombinirajte slovaa6 ia7 u jednom slovua1 s vjerojatnošću0.18 ipreureditipopis:

P1 = {0.2, 0.2, 0.19, 0.18, 0.12, 0.11}, A1 = { a1 , a2 , a3 , a1 , a4 , a5 }.

3. Ponovite korak 2 dok na popisu ne ostane samo jedno slovo:

P2 = {0.23, 0.2, 0.2, 0.19, 0.18}, A2 = { a2 , a1 , a2 , a3 , a1 };

P3 = {0.37, 0.23, 0.2, 0.2}, A3 = { a3 , a2 , a1 , a2 };

P4 = {0.4, 0.37, 0.23}, A4 = { a4 , a3 , a2 };

P5 = {0.6, 0.4}, A5 = { a5 , a4 };

P6 = {1}, A6 = { a6 }.

4. Dodijelimobinarnikodovisimboli:

a6 : a5 = 0, a4 = 1;

a5 : a3 = 00, a2 = 01;

a4 : a1 = 10, a2 = 11;

a3 : a3 = 000, a1 = 001;

a2 : a4 = 010, a5 = 011;

a1 : a6 = 0010, a7 = 0011.

Stoga su sljedeći binarni kodovi dodijeljeni izvornim slovima:a1 = 10, a2 = 11, a3 = 000, a4 = 010, a5 = 011, a6 = 0010, a7 = 0011, što daje prosječnu duljinu koda koja je manja nego u slučaju kodiranja Fano i Shannon.

Definirajmo redundanciju primljenih kodova. Da bismo to učinili, nalazimo entropiju izvora poruke:

.

Tada kodovi imaju sljedeću redundanciju:

Fano kod:;

Shannon kod:;

Huffmanova šifra:.

Dakle, redundantnost Huffmanovog koda je minimalna.

Za smanjenje redundancije, t.j. smanjujući prosječnu duljinu kodne riječi za jedan simbol, možete koristiti blok kodiranje, čije je obrazloženje dano u teoremu izvornog kodiranjaII... U ovom slučaju morate dobiti sve vrste grupa slova zadane dužine, pronaći vjerojatnosti skupina, kao vjerojatnosti zajedničkog pojavljivanja slova grupe u isto vrijeme, te izvršiti kodiranje, smatrajući skupine simbolima nove abecede.

STRANA 43

Izravni Shannonov teorem o izvoru opći pogled Ne smije se miješati s drugim Shanonovim teoremima.

Shanonovi teoremi za opći izvor opisati mogućnosti kodiranja generičkog izvora korištenjem odvojivih kodova. Drugim riječima, opisana je maksimalna dostižna sposobnost kodiranja bez gubitaka.

Izravni teorem

Kako se primjenjuje na kodiranje slovo po slovo, izravni se teorem može formulirati na sljedeći način:

Kao dokaz teorema istražuju se karakteristike Shannon-Fano koda. Ovaj kod zadovoljava uvjete teorema i posjeduje navedena svojstva.

Obrnuti teorem

Obrnuti teorem ograničava maksimalni omjer kompresije postignut kodiranjem bez gubitaka. Primijenjeno na kodiranje slovo po slovo, opisuje ograničenje prosječne duljine kodne riječi za bilo koji kod koji se može odvojiti.

Za bilo koji odvojivi kod s duljinama w 1 ,w 2 ,...,w K prosječna duljina poruke veća je 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 o teoriji informacija. - M .: MIPT, 2007 .-- S. 49-52. - 214 str. - ISBN 5-7417-0197-3

Zaklada Wikimedia. 2010.

Pogledajte što je "Direct Shannon teorem za opći izvor" u drugim rječnicima:

Ne smije se miješati s drugim Shanonovim teoremima. Shannonovi teoremi za generički izvor opisuju mogućnosti kodiranja generičkog izvora korištenjem odvojivih kodova. Drugim riječima, opisane su najveće moguće mogućnosti ... ... Wikipedia

Na Wikipediji postoje članci o drugim osobama s ovim prezimenom, vidi Shannon. Claude Elwood Shannon ... Wikipedia

Claude Elwood Shannon (rođen 30. travnja 1916., Petotsky (Petoskey, Michigan) Michigan, SAD, preminuo 24. veljače 2001., Medford, Massachusetts, SAD) američki je matematičar i inženjer elektrotehnike, jedan od utemeljitelja matematičke teorije ... ... Wikipedia

Claude Elwood Shannon (rođen 30. travnja 1916., Petotsky (Petoskey, Michigan) Michigan, SAD, preminuo 24. veljače 2001., Medford, Massachusetts, SAD) američki je matematičar i inženjer elektrotehnike, jedan od utemeljitelja matematičke teorije ... ... Wikipedia

- (eng. Claude Elwood Shannon; rođen 30. travnja 1916. Petotsky (Petoskey, Michigan) Michigan, SAD, preminuo 24. veljače 2001., Medford, Massachusetts, SAD) američki matematičar i inženjer elektrotehnike, jedan od utemeljitelja matematičkih informacija teoriji, u ... ... Wikipediji

Claude Elwood Shannon (rođen 30. travnja 1916., Petotsky (Petoskey, Michigan) Michigan, SAD, preminuo 24. veljače 2001., Medford, Massachusetts, SAD) američki je matematičar i inženjer elektrotehnike, jedan od utemeljitelja matematičke teorije ... ... Wikipedia

Claude Elwood Shannon (rođen 30. travnja 1916., Petotsky (Petoskey, Michigan) Michigan, SAD, preminuo 24. veljače 2001., Medford, Massachusetts, SAD) američki je matematičar i inženjer elektrotehnike, jedan od utemeljitelja matematičke teorije ... ... Wikipedia

Claude Elwood Shannon (rođen 30. travnja 1916., Petotsky (Petoskey, Michigan) Michigan, SAD, preminuo 24. veljače 2001., Medford, Massachusetts, SAD) američki je matematičar i inženjer elektrotehnike, jedan od utemeljitelja matematičke teorije ... ... Wikipedia

Za učinkovito korištenje kanala (povećanje faktora opterećenja λ → 1), mora se uskladiti s izvorom informacija na ulazu. Takvo podudaranje je moguće i za bučne i za bučne kanale, na temelju teorema kodiranja kanala koje je predložio Shannon.

Teorem kodiranja za bučni kanal.

Ako izvor poruka ima performanse [bit/sec], a komunikacijski kanal ima propusnost [bit/sec], tada možete kodirati poruku na način da prosječnom brzinom prenosite informacije preko komunikacijskog kanala, proizvoljno blizu vrijednosti, ali ne i prekoračiti je...

Shannon je također predložio metodu takvog kodiranja, koja se naziva optimalno kodiranje. Kasnije je ideja o takvom kodiranju razvijena u djelima Fana i Huffmana. Trenutno se takvi kodovi široko koriste u praksi (učinkovito i optimalno kodiranje).

Shanonov teorem izravnog kodiranja za bučni kanal.

Za bilo koju izvedbu izvora poruke [bit/sec] manje od propusnost[bit/sec], postoji takva metoda kodiranja koja omogućuje prijenos svih informacija koje generira izvor poruke s proizvoljno malom vjerojatnošću pogreške ε.

Teorem inverznog kodiranja za bučni kanal.

Ne postoji metoda kodiranja koja dopušta prijenos informacija s proizvoljno malom vjerojatnošću pogreške ako je izvedba izvora poruke veća od propusnosti kanala.

Dokaz teorema kodiranja za bučni kanal matematički je prilično opsežan, stoga se ograničavamo na opću raspravu o fizičkim aspektima njegove praktične primjene:

1. Teorem utvrđuje teorijsku granicu moguće učinkovitosti sustava s pouzdanim prijenosom informacija. Iz teorema slijedi da smetnje kanala ne nameću ograničenja na točnost prijenosa. Ograničenja se nameću samo na brzinu prijenosa pri kojoj se može postići proizvoljno visoka pouzdanost prijenosa.

U ovom slučaju, pouzdanost diskretnog kanala obično se procjenjuje vrijednošću vjerojatnosti pogrešnog prijema jednog simbola. Što je manja vjerojatnost pogreške, to je veća pouzdanost kanala. Pouzdanost, pak, karakterizira otpornost informacijskog sustava na buku.

Brzina prijenosa informacija karakterizira učinkovitost sustava.

2. Teorem se ne dotiče pitanja načina konstruiranja kodova koji osiguravaju naznačeni idealan prijenos. Potkrijepivši temeljnu mogućnost takvog kodiranja, mobilizirala je napore znanstvenika da razviju specifične kodove.

3. Za bilo koju konačnu brzinu prijenosa informacija, do propusnosti, proizvoljno mala vjerojatnost pogreške postiže se samo uz beskonačno povećanje trajanja kodiranih znakovnih nizova. Dakle, prijenos bez grešaka u prisutnosti smetnji je samo teoretski moguć. Osiguravanje prijenosa informacija s vrlo malom vjerojatnošću pogreške i s dovoljno visokom učinkovitošću moguće je kod kodiranja iznimno dugih nizova znakova.

Za bilo koju produktivnost izvora poruke H, manju od kapaciteta kanala C, postoji metoda kodiranja koja omogućuje prijenos svih informacija koje generira izvor poruka s proizvoljno malom vjerojatnošću pogreške.

Iako je dokaz ovog teorema, koji je predložio Shannon, naknadno podvrgnut dubljem i rigoroznijem matematičkom prikazu, njegova ideja je ostala nepromijenjena. Dokazuje se samo postojanje željene metode kodiranja za koju se utvrđuje prosječna vjerojatnost pogreške za sve mogući načini kodiranje i pokazati da se može učiniti manjim od proizvoljno male vrijednosti e. Štoviše, postoji barem jedna metoda kodiranja za koju je vjerojatnost pogreške manja od prosjeka.

Dokaz teorema. Neka H (x) i H (x | y) - a priori i posteriori entropija po simbolu (od strane primatelja) za sustav koji implementira kapacitet S kanal. Na temelju imovine E za dovoljno dugo trajanje ( P simboli) svi mogući prijenosi bilo kojeg ansambla raspadaju se u vrlo vjerojatne i malo vjerojatne skupine; istovremeno se mogu dati sljedeće tvrdnje o broju signala u odgovarajućim skupinama:

a) Skupina vrlo vjerojatnih odaslanih signala sadrži oko 2 nn (x) sekvence.

b) Skupina vrlo vjerojatnih primljenih signala sadrži oko 2 pon (g) sekvence.

c) Svaki vrlo vjerojatno primljeni signal mogao bi (s približno jednakim vjerojatnostima) potjecati od oko 2 nn (x | y) odaslane signale vrlo vjerojatne skupine.

d) Svaki poslani signal iz vrlo vjerojatne grupe može (s približno istim vjerojatnostima) odgovarati približno 2 nn (y | x) primili signale velike vjerojatnosti.

Na temelju imovine E entropija diskretnih procesa, s povećanjem P svi odgovarajući e i d će težiti nuli.

Sada neka se informacija prenosi preko istog kanala s ulaznom brzinom jednakom N< С. U ovom slučaju, broj vrlo vjerojatno poslanih signala duljine od P znakovi će biti jednaki 2 pon< 2nn (x)... Kao što je već napomenuto, problem izbora određeni kod sastoji se u naznaci koji od 2 nn (x) moguće sekvence biraju se kao 2 pon dopušteni za otpremu i kako su podijeljeni u 2 pon podskupine 2 pon (g) izlazne sekvence. Razmotrimo klasu svih vrsta kodova koji će ispasti ako 2 pon dopuštene sekvence za objavljivanje nasumično među 2 nn (x) mogući signali vrlo vjerojatne skupine; pronaći prosječnu vrijednost vjerojatnosti pogreške za ove kodove.

Neka se primi neki signal kod K. U ovom slučaju, vjerojatnost pogreške jednaka je vjerojatnosti da se dati signal može pojaviti iz više od jedne od 2 pon dopušteni signali. Budući da se kod dobiva slučajnim (jednako vjerojatnim) izborom 2 pon sekvence od 2 nn (x), zatim vjerojatnost da unaprijed postavljeni signal na ulazu kanala bit će među dopuštenim, jednaka

Primljeni signal do odgovara 2 nn (x | y) eventualno slali signale. Otuda je prosječna vjerojatnost da nijedan od 2 nn (x | y) signala (osim jednog stvarno poslanog) nije dopušteno, jednako (zapostavljamo jedinicu u usporedbi s nn (x | y))

Ovo je prosječna vjerojatnost prijema bez pogrešaka. Nadalje, budući da N< С = Н(х) – Н(х| у), zatim

H - H (x) = - H (x | y) - h , (8.23)

Gdje je h> 0. Zamjenom (8.23) u (8.22) dobivamo

Može se pokazati da

oni. da se slučajnim kodiranjem u dovoljno dugim blokovima prosječna vjerojatnost pogreške može učiniti proizvoljno malom. Tvrdnja o postojanju barem jednog koda koji daje vjerojatnost pogreške manju od prosječne dovršava dokaz.

Imajte na umu da jednakost (8.25) vrijedi za bilo koji, proizvoljno mali, pozitivan h. To znači da teorem prihvaća uvjet H £ C.

To daje posebno značenje konceptu propusnosti: ispostavilo se da propusnost nije samo najveća moguća brzina prijenosa podataka, već maksimalna brzina, u kojem je prijenos još uvijek moguć s proizvoljno malom vjerojatnošću pogreške.

Shanonov drugi teorem o kodiranju u prisutnosti šuma. Da bi se osigurala dovoljna otpornost na buku, potrebno je uvesti u odaslani signal redundantnost, čime se smanjuje brzina prijenosa informacija. Sasvim je prirodno bojati se da će se s povećanjem ograničenja male vjerojatnosti pogreške potrebna redundantnost povećati, progresivno smanjujući brzinu prijenosa informacija, vjerojatno na nulu. Međutim, sve nedoumice otklanja Drugi Shannon teorem kodiranja za bučne kanale, koji se može formulirati na sljedeći način:

Teorema.Pod uvjetom H £ C, među kodovima koji daju (prema Prvom teoremu) proizvoljno malu vjerojatnost pogreške, postoji kod u kojem je brzina prijenosa informacija R proizvoljno bliska brzini stvaranja informacija H.

Brzina prijenosa informacija (po znaku) definirana je kao

R = H - H (x | y), (8.26)

gdje H (x | y) - posteriornu entropiju poslanog signala po simbolu, ili raspršivanje informacija u kanalu.

Dokaz teorema (vidi) počinje tvrdnjom da je minimalna potrebna redundancija po simbolu H (x | y) dodatni likovi. Nadalje je prikazano da se kod može izabrati tako da H (x | y) bila proizvoljno mala.

Rasprava o teoremama. Prije svega, napomenimo temeljnu prirodu dobivenih rezultata. Teorem postavlja teorijsku granicu moguće učinkovitosti sustava s pouzdanim prijenosom informacija. Pobija se ideja, koja se činila intuitivno točnom, da je postizanje proizvoljno male vjerojatnosti pogreške u slučaju prijenosa informacija preko šumnog kanala moguće samo uz uvođenje beskonačno velike redundance, t.j. kada se brzina prijenosa smanji na nulu. Iz teorema proizlazi da smetnje kanala ne nameću ograničenja na točnost prijenosa. Ograničenje se nameće samo na brzinu prijenosa pri kojoj se može postići proizvoljno visoka pouzdanost prijenosa.

Teoremi su nekonstruktivni u smislu da se ne dotiču pitanja načina građenja kodova koji osiguravaju naznačeni idealan prijenos. Međutim, nakon što su potkrijepili temeljnu mogućnost takvog kodiranja, mobilizirali su napore znanstvenika da razviju specifične kodove.

Treba napomenuti da se za bilo koju konačnu brzinu prijenosa informacija do propusnosti, proizvoljno mala vjerojatnost pogreške postiže samo uz neograničeno povećanje trajanja kodiranih znakovnih nizova. Dakle, prijenos bez grešaka u prisutnosti smetnji je samo teoretski moguć.

Osiguravanje prijenosa informacija s vrlo malom vjerojatnošću pogreške i dovoljno visokom učinkovitošću moguće je kod kodiranja iznimno dugih nizova znakova. U praksi je stupanj pouzdanosti i učinkovitosti ograničen s dva čimbenika: veličinom i cijenom opreme za kodiranje i dekodiranje te vremenom kašnjenja. prenesena poruka... Trenutno se relativno koristi jednostavne metode kodiranja koja ne implementiraju mogućnosti koje ukazuje teorija. Međutim, stalno rastući zahtjevi za pouzdanost prijenosa i napredak u tehnologiji za stvaranje velikih integrirani krugovi promicati uvođenje sve sofisticiranije opreme za te namjene.

Međutim, treba imati na umu da teoremi za diskretne šumne kanale, kao ni teorema 2 za kanale s šumom, ne navode da je kodiranje dugih nizova poruka jedina metoda učinkovito kodiranje. Smisao ovih teorema je potvrditi postojanje učinkovite metode kodiranja i u postavljanju kvantitativnih granica najveće moguće brzine prijenosa podataka. U vezi s tim važni su ne samo izravni, nego i obrnuti iskazi ovih teorema. Iz dokaza teorema proizlazi samo da se kodiranjem dovoljno dugih nizova poruka uvijek može što bliže približiti maksimalnoj mogućoj brzini prijenosa poruke (s minimalnom vjerojatnošću pogreške za bučne kanale). Potonje, međutim, ne znači da druge učinkovite metode kodiranja ne mogu postojati. Naprotiv, na nizu konkretnih primjera može se pokazati da takve metode postoje.

Nažalost, trenutno nisu pronađene opće metode za konstruiranje učinkovitih kodova za bučne kanale koji zadovoljavaju različite praktične zahtjeve. Postupno, međutim, takve metode izlaze na vidjelo. Vrlo zanimljiva i važna tvrdnja teorema je da u bučnom kanalu s proizvoljno niskom nepouzdanošću prijenosa poruke (→ 0) brzina prijenosa informacija može biti proizvoljno blizu C C ... Ranije je prevladavalo mišljenje, temeljeno na intuitivnim razmatranjima, da bi se s tim zahtjevima brzina prijenosa informacija trebala beskonačno smanjivati.

Temeljni značaj teorema leži u činjenici da oni dopuštaju, znajući granične (teorijske) vrijednosti brzine prijenosa informacija C C , ocijeniti učinkovitost korištenih metoda kodiranja.

Dakle, gornji teoremi su teoremi postojanja.

Iz dokaza ovih teorema ne proizlazi kako konstruirati kod i izvesti dekodiranje tako da je vjerojatnost pogreške onoliko mala koliko želite, a brzina prijenosa proizvoljno blizu kapaciteta komunikacijske linije. Teoremi su asimptotični, tj. nisu konstruktivni. Međutim, od velike je važnosti samo poznavanje potencijalnih mogućnosti: usporedba karakteristika stvarni sustavi S teorijske granice omogućuje procjenu postignute razine i izvedivosti daljnjih troškova za njeno povećanje. Primijenjena pitanja razmatraju se u posebnom dijelu teorije informacija - teoriji kodiranja, koja proučava metode konstruiranja specifičnih kodova i njihova svojstva, posebice točne ili granične ovisnosti vjerojatnosti pogrešaka iz parametara koda.

Inverzni Shanonov teorem za bučne kanale. Obrnuti teorem ukazuje na uvjete koji nastaju kada se informacija prenosi preko šumnog kanala brzinom koja prelazi širinu pojasa.

Teorema.Ako je brzina stvaranja informacija H veća od kapaciteta kanala C, tada nijedan kod ne može učiniti vjerojatnost pogreške proizvoljno malom. Minimalno raspršivanje informacija po simbolu, dostižno za H> C, jednako je H - C; nijedan kod ne može osigurati manje raspršivanje informacija.

Dokaz Shannonovog inverznog teorema može se naći u.

Obrnuti teorem tvrdi da za H> C prijenos bez grešaka je nemoguć; štoviše, što je veći omjer H / C,što je veća preostala nesigurnost H (x | y). Potonje je povezano s vjerojatnošću primanja pogrešaka. Prirodno se postavlja pitanje kako se postiže minimalna vjerojatnost pogreške najbolje kodiranje, sa stavom N/S. Za binarni kanal rješenje je dano. Na k = N / C< 1 вероятность ошибки e(Do) = 0 prema prvom teoremu. Na Do® ¥ e ( Do) ® 0,5, što znači da je razlomak prenesene informacije cijelog kanala koji ulazi na ulaz teži nuli na Do® ¥; što je prijenos brži, to se prenosi manje informacija.

Kontrolna pitanja

1. Navedite opravdanje za potrebu uvođenja redundancije kod kodiranja u bučnom kanalu.

2. Kako se prosječna količina informacija (po znaku) prenosi preko diskretni kanal sa šumovima?

3. Kako se određuje brzina prijenosa i širina pojasa šumnog kanala?

4. Formulirajte i objasnite teoreme Shannonovog kodiranja naprijed i natrag za bučni kanal.

5. Koje relacije slijede iz teorema o asimptotičkoj jednakoj vjerojatnosti za dovoljno duge tipične lance za stacionarne šumne kanale?

6. Koji je razlog svrsishodnosti kodiranja dugih nizova znakova?

7. Koja formula određuje širinu pojasa binarne veze balansirani kanal bez memorije, pod kojim uvjetom širina pojasa ovog kanala ide na nulu?