Poruke abecede izvora ispisuju se silaznim redoslijedom vjerojatnosti njihovog pojavljivanja. Zatim se dijele na dva dijela tako da su ukupne vjerojatnosti poruka u svakom od tih dijelova, ako je moguće, gotovo jednake. Porukama prvog dijela dodjeljuje se 0 kao prvi znak, a porukama drugog dijela - 1 (i obrnuto). Zatim se svaki od tih dijelova (ako sadrži više od jedne poruke) podijeli na dva jednako vjerojatna dijela, a za prvi se uzima 0 kao drugi znak, a za drugi 1. Taj se postupak ponavlja sve dok se svaki primljenih dijelova sadrži jednu po jednu poruku. Za primjer prikazan u tablici. 1 u prvoj fazi cijepanja prvog dijela bit će jedna poruka a 1 s vjerojatnošću P(a 1) = 0,4, u drugom dijelu - ostale poruke s ukupnom vjerojatnošću P Σ ( a 2 -a 6) = 0,6. Dodajmo poruku a 1 znak 0, a ostale poruke kao prvi znak - 1.
Tablica 1. Proizvoljno kodiranje poruke
U drugoj fazi dijelimo poruke ( a 2 ,a 3 ,a 4 ,a 5 ,a 6) na dva jednako vjerojatna dijela, uključujući i prvi dio poruke a 2, a u drugom dijelu - poruke ( a 3 ,a 4 ,a 5 ,a 6). Dodajmo poruku a 2 kao drugi znak 0, a ostale poruke - 1 itd. Kao rezultat, dolazimo do koda DO 2, dano u tablici. 2.
Tablica 2. Kodiranje poruka sa Shannon-Fano kodom
Kod svojom konstrukcijom zadovoljava svojstvo prefiksa. Stoga, gornji slijed binarnih znakova “ L
”Dekodira se nedvosmisleno: ( a 1 ,a 1 ,a 4 ,a 1 ,a 1 ,a 1 ,a 6 ,a jedan). Prosječan broj znakova po poruci, uzimajući u obzir njihove vjerojatnosti 
= 0,4 * 1 + 0,3 * 2 + 0,3 * 4 = 2,2, tj. neznatno premašuje entropiju izvora poruke.
2.4. Prosječna duljina kodne riječi
Shannon-Fano postupak ne mora nužno minimizirati 
, budući da postizanje velike vrijednosti prosječne samoinformacije na jednom kodnom slovu može dovesti do lošeg izbora sljedećih kodnih slova. Ako se ova particija može izračunati tako da su grupe točno jednako vjerojatne u svakoj fazi particije, tada će vjerojatnosti izvornih slova i duljine kodnih riječi biti povezane jednakošću
(2)
Ograničenja na duljinu kodnih riječi prefiksnog koda određena su Craftovom nejednakošću i teoremom kodiranja za izvor.
Teorem 1.(Kraftova nejednakost). Ako cijeli brojevi ( 
) zadovoljavaju nejednakost
(3)
onda postoji kod koji ima svojstvo prefiksa s abecedom veličine D, duljine kodnih riječi u kojima su jednake tim brojevima. Suprotno tome, duljine kodnih riječi bilo kojeg koda sa svojstvom prefiksa zadovoljavaju nejednakost (3). Teorem ne navodi da bilo koji kod čija duljina kodne riječi zadovoljava (3) ima prefiks. Tako, na primjer, skup binarnih kodnih riječi (0; 00; 11) zadovoljava (3), ali nema svojstvo prefiksa. Teorem kaže da postoji neki prefiksni kod s takvim duljinama, na primjer kod (0; 10; 11). Niti jedan jedinstveni kod za dekodiranje nema svojstvo prefiksa, na primjer, K3 kod tablice. 3. U njemu je svaka kodna riječ prefiks svake duže kodne riječi. U isto vrijeme, jednoznačnost dekodiranja je trivijalna, budući da simbol 0 uvijek definira početak nove kodne riječi. Kodovi sa svojstvom prefiksa razlikuju se, međutim, od ostalih jednoznačno dekodiranih kodova po tome što se kraj kodne riječi uvijek može prepoznati, tako da se dekodiranje može izvesti bez odgađanja promatranog slijeda kodnih riječi (k. K4 iz tablice 3). Iz tog razloga, prefiks kodovi se ponekad nazivaju trenutnim kodovima.
Tablica 3. Jedinstveno dekodirani kodovi
Budući da duljine kodnih riječi bilo kojeg jedinstveno dekodiranog koda zadovoljavaju (3) i moguće je konstruirati prefiksni kod za bilo koji skup duljina koji zadovoljava (3), tada se bilo koji jednoznačno dekodirani kod može zamijeniti prefiksnim kodom bez promjene duljina kodne riječi. Stoga je sljedeći Teorem 2 za izvorno kodiranje s obzirom na prosječnu duljinu kodne riječi predložen i za jednoznačno dekodirane kodove i za podklasu prefiksnih kodova.
Informacija je skup informacija koje treba pohraniti, prenijeti, obraditi i koristiti u ljudskoj djelatnosti.
Promjena karakteristika medija, koji se koristi za predstavljanje informacija, naziva se signal , a vrijednost ove karakteristike, koja se odnosi na određenu ljestvicu mjerenja, naziva se parametar signala .
Razlikovati dvije vrste signala (i zbog toga dvije vrste poruka ): kontinuirano i diskretno.
Kako bi se osigurala jednostavnost i pouzdanost prepoznavanja diskretnih signala ( znakovi ), preporučljivo je smanjiti njihov broj na minimum. U pravilu pribjegavaju operaciji predstavljanja izvornih znakova u drugoj abecedi s manjim brojem znakova, tzv. simboli ... Kada se govori o ovoj operaciji, koristi se isti izraz - " kodiranje ».
Vlastite informacije
Količina informacija koju pismo nosi x i abeceda, nazovimo vlastite informacije
sadržane u x i i označiti 
.
.
Shanonova formula
Usrednjujmo vlastitu informaciju, t.j. izračunati prosječnu količinu informacija koju nosi jedan znak abecede 
:
.
Prosječna količina informacija pripisiv jedno slovo Zove se entropija abeceda (ili izvor) i označena H:
-
Shanonova formula
.
Očito je da prosječno 1 količina informacija u dužini poruke n izračunato po formuli:
.
Komentar.Količina informacija pripisuje se samoj poruci.
Komentar. Entropija je karakteristika izvora poruka (abeceda).
Hartleyeva formula
Na jednakovjerojatnost znakovi abecede 
, iz Shanonove formule dobivamo:.
-
Hartleyeva formula
.
Informacijske jedinice
Jedinica količine informacije po jednom elementu poruke (mjerna jedinica entropije) naziva se malo .
Razmotrimo abecedu jednakovjerojatnih simbola s entropijom jednakom 1: 
... Pošto iz ovoga proizlazi 
, onda je jasno da je 1 bit količina informacija koja je sadržana u binarnoj poruci (abecedi (0,1)) duljine 1.
U nastavku, u izrazima za I i H uvijek ćemo koristiti logaritme s bazom 2.
Entropijska svojstva
1. Entropija N- vrijednost
- nenegativni(N 0) ,
-
ograničeno,
Ova svojstva proizlaze iz činjenice da svi njegovi pojmovi imaju iste kvalitete. 
.
2. Entropija je nula ako je vjerojatnost jednog od simbola 1... U ovom se slučaju govori o potpuno determinističkom izvoru i odsustvu neizvjesnosti u njemu, budući da promatrač prije trenutka promatranja zna za izvornu poruku.
3. Također se može pokazati da je entropija je maksimalno ako su svi znakovi abecede jednako vjerojatni, tj. N max = log m... Dakle, Hartleyeva formula se koristi za pronalaženje najveće moguće vrijednosti entropije (za fiksni broj simbola).
4. Od posebnog interesa su binarne poruke korištenjem binarna abeceda(0,1). Budući da je u m= 2 vjerojatnosti znakova abecede str 1 1 i str 2 1, onda možemo staviti str 1 = str i str 2 = 1-str... Tada je entropija određena relacijom
Klikom na gumb "Preuzmi arhivu" besplatno ćete preuzeti datoteku koja vam je potrebna.
Prije nego što preuzmete ovu datoteku, sjetite se onih dobrih sažetaka, testova, seminarskih radova, diplomskih radova, članaka i drugih dokumenata koji nisu traženi na vašem računalu. To je vaš posao, mora sudjelovati u razvoju društva i koristiti ljudima. Pronađite ove radove i pošaljite ih u bazu znanja.
Mi i svi studenti, diplomski studenti, mladi znanstvenici koji koriste bazu znanja u svom studiju i radu bit ćemo vam jako zahvalni.
Za preuzimanje arhive s dokumentom, u polje ispod unesite peteroznamenkasti broj i kliknite gumb "Preuzmi arhivu"
Slični dokumenti
Ukupan broj poruka koje se ne ponavljaju. Proračun brzine prijenosa informacija i propusnosti komunikacijskih kanala. Određivanje redundancije poruke i optimalno kodiranje. Postupak za konstruiranje optimalnog koda pomoću Shannon-Fano metode.
seminarski rad, dodan 17.04.2009
Opis i značajke nekih algoritama za arhiviranje. Konstrukcija Huffmanovog koda. Dinamički algoritam za konstruiranje Huffmanovog koda. Obrnuti oporavak teksta. Metode za dvostupanjsko kodiranje informacija. Praktična implementacija algoritma LZ77.
seminarski rad, dodan 24.12.2012
Procjena računske složenosti programa. Implementacija Huffmanovog algoritma kodiranja informacija. Testirajte kodiranje u binarnom i u Huffmanovu stablu. Binarni kod znakova. Simbol i učestalost njegovog pojavljivanja u tekstu. Proračun složenosti algoritma.
test, dodano 16.12.2012
Određivanje prosječne količine informacija. Ovisnost između simbola matrice uvjetnih vjerojatnosti. Shannon – Fano kodiranje. Širina pojasa komunikacijskog kanala. Učinkovitost kodiranja poruka metodom D. Huffmana, karakterizacija koda.
test, dodano 04.05.2015
Definicija pojmova koda, kodiranje i dekodiranje, vrste, pravila i zadaci kodiranja. Primjena Shannonovih teorema u teoriji komunikacije. Klasifikacija, parametri i konstrukcija kodova za ispravljanje pogrešaka. Načini prijenosa kodova. Primjer izgradnje Shannonovog koda.
seminarski rad, dodan 25.02.2009
Analiza učinkovitosti metoda kodiranja. Prosječna veličina jednog bita i prosječna duljina kodne riječi. Huffmanovo kodiranje. Kodiranje informacija prema Chenon-Fano metodi. Izgradnja kodnog stabla za različite metode kodiranja.
test, dodano 15.10.2013
Kodiranje i dekodiranje, pretvaranje diskretne poruke u diskretni signal. Izgradnja matematičkog modela ispravljačkog koda. Formiranje matrice informacijskog koda. Modularna struktura programa. Specifikacije za softverske module.
seminarski rad, dodan 28.11.2014
U gornjim primjerima kodiranja sve su kodne riječi bile iste duljine. Međutim, to nije potrebno. Štoviše, ako se vjerojatnosti pojavljivanja poruka značajno razlikuju jedna od druge, onda je bolje poruke s velikom vjerojatnošću pojavljivanja kodirati kratkim riječima, a rijetke poruke kodirati dužim riječima. Kao rezultat toga, tekst koda će, pod određenim uvjetima, u prosjeku postati kraći.
Pokazatelj ekonomičnosti ili učinkovitosti neujednačenog koda nije duljina pojedinih kodnih riječi, već njihova "prosječna" duljina, određena jednakošću:
gdje je kodna riječ kojom je poruka kodirana, a njezina duljina, vjerojatnost poruke, ukupan broj poruka iz izvora. Za sažetost pisanja formula, u nastavku se može koristiti sljedeća oznaka 
i 
... Imajte na umu da oznaka prosječne duljine kodiranja kroz naglašava činjenicu da ova vrijednost ovisi i o izvoru poruka i o načinu kodiranja.
Najekonomičniji je kod s najmanjom prosječnom duljinom. Uzmimo primjere za usporedbu učinkovitosti različitih metoda kodiranja istog izvora.
Neka izvor sadrži 4 poruke s vjerojatnostima. Te se poruke mogu kodirati kodnim riječima od dva znaka fiksne duljine u abecedi 
prema tablici kodova.
Očito, za predstavljanje (prijenos) bilo koje sekvence, u prosjeku su potrebna 2 znaka po poruci. Usporedimo učinkovitost takvog kodiranja s gore opisanim kodiranjem s riječima promjenjive duljine. Tablica kodova za ovaj slučaj može biti sljedeća.
U ovoj tablici, za razliku od prethodne, najčešće poruke su kodirane jednim binarnim znakom. Za posljednju opciju kodiranja imamo
dok je za uniformni kod prosječna duljina (poklapa se s ukupnom duljinom kodnih riječi). Iz razmatranog primjera može se vidjeti da kodiranje poruka riječima različite duljine može dati značajno (gotovo dvostruko) povećanje učinkovitosti kodiranja.
Kod korištenja neujednačenih kodova javlja se problem, što ćemo objasniti na primjeru zadnje tablice kodova. Neka se ova tablica koristi za kodiranje niza poruka 
, uslijed čega se pretvara u sljedeći binarni tekst: 010110. Prvi znak izvorne poruke dekodira se nedvosmisleno - ovo. Međutim, počinje daljnja neizvjesnost: ili 
... Ovo su samo neke od mogućih opcija za dekodiranje izvornog niza znakova.
Treba napomenuti da se nejasnoća dekodiranja riječi pojavila unatoč činjenici da je ispunjen uvjet za jednoznačno dekodiranje znakova (ijektivnost kodnog preslikavanja).
Bit problema leži u nemogućnosti jednoznačne identifikacije kodnih riječi. Da bismo ga riješili, bilo bi potrebno odvojiti jednu kodnu riječ od druge. Naravno, to se može učiniti, ali samo pomoću stanke između riječi ili posebnog znaka za razdvajanje, za koji je potrebna posebna oznaka koda. I jedan i drugi način, prvo, proturječe gore opisanoj metodi kodiranja riječi spajanjem kodova znakova koji čine riječ, i, drugo, dovest će do značajnog produljenja kodnog teksta, negirajući prednosti korištenjem kodova promjenjive duljine.
Rješenje ovog problema je mogućnost odabira pojedinačnih kodnih riječi u bilo kojem kodnom tekstu bez korištenja posebnih znakova za razdvajanje. Drugim riječima, potrebno je da kod zadovoljava sljedeći zahtjev: bilo koji slijed kodnih točaka može se jedinstveno podijeliti u kodne riječi. Kodovi za koje je ispunjen zadnji zahtjev nazivaju se jednoznačno dekodirani (ponekad se nazivaju kodovi bez zareza).
Razmotrite kod (abecedna shema kodiranja) 
dat tablicom kodova
i razne riječi sastavljene od elementarnih kodova.
Definicija... Za kod se kaže da je jednoznačno dekodiran ako
odnosno svaka riječ sastavljena od elementarnih kodova jednoznačno se rastavlja na elementarne kodove.
Ako tablica kodova sadrži iste kodne riječi, odnosno ako
onda kod sigurno nije jednoznačno dekodiran (shema nije odvojiva). O takvim kodovima se dalje ne raspravlja.
Razmotrimo skup poruka za njih s odgovarajućim vjerojatnostima.Svaka poruka mora biti predstavljena kodnom riječi koja se sastoji od uzastopnih znakova koji pripadaju danoj abecedi. Označimo brojem različitih simbola u abecedi, brojem simbola u kodnoj riječi koja odgovara poruci. Prosječan broj simbola po poruci jednak je po definiciji
Naš prvi zadatak je pronaći donju granicu za
U sekti. U 2.8 smo vidjeli da je entropija skupa poruka prosječna količina informacija potrebna za jedinstvenu identifikaciju poruke iz tog skupa. U istom odjeljku vidjeli smo da simboli u prosjeku nose najveću količinu informacija kada su jednako vjerojatni. Ova maksimalna vrijednost je, naime, kapacitet kodne abecede. Osim toga, jednakosti (2.100) i (2.105) pokazuju da statistička ovisnost određenog simbola o prethodnim ne može povećati prosječnu količinu informacija po ovom simbolu. Na temelju toga možemo zaključiti da
Gdje ćemo dobiti
odnosno prosječan broj simbola po poruci ne može biti manji od entropije ansambla poruka podijeljene s kapacitetom abecede. Izravan dokaz ovog rezultata dat je u pogl. 3.5.
Obrazloženje korišteno za dobivanje ove donje granice omogućuje predlaganje općih pravila za konstruiranje kodnih riječi s prosječnom duljinom dovoljno blizu ovoj granici. Prvo pravilo je da se na svakoj od pozicija kodne riječi trebaju koristiti različiti znakovi abecede s jednakim vjerojatnostima kako bi se maksimizirala prosječna količina informacija koju daju. Drugo pravilo je da su vjerojatnosti nastanka
znakovi na svakoj poziciji kodne riječi moraju biti neovisni o svim prethodnim znakovima. Ako se ova pravila točno poštuju, tada će prosječna duljina generiranih kodnih riječi biti jednaka minimalnoj vrijednosti određenoj formulom (3.3). Vidjet ćemo, međutim, da se samo u posebnim slučajevima simboli mogu koristiti s jednakim vjerojatnostima i učiniti ih neovisnima o svim prethodnim simbolima. Najbolje je objasniti ova pravila za konstruiranje skupova kodnih riječi koristeći sljedeće konkretne primjere. Korišteni postupak kodiranja sličan je onom koji je prvi predložio Shannon.
