Poruke abecede izvora ispisuju se u opadajućem redosledu verovatnoće njihovog pojavljivanja. Zatim se dijele na dva dijela tako da su ukupne vjerovatnoće poruka u svakom od ovih dijelova, ako je moguće, gotovo iste. Porukama prvog dijela dodjeljuje se 0 kao prvi znak, a porukama drugog dijela - 1 (i obrnuto). Zatim se svaki od ovih dijelova (ako sadrži više od jedne poruke) podijeli na dva podjednako vjerovatna dijela, a za prvi se uzima 0 kao drugi znak, a za drugi 1. Ovaj proces se ponavlja sve do svakog primljenih dijelova sadrži jednu po jednu poruku. Za primjer prikazan u tabeli. 1 u prvoj fazi cijepanja prvog dijela bit će jedna poruka a 1 sa vjerovatnoćom P(a 1) = 0,4, u drugom dijelu - ostale poruke sa ukupnom vjerovatnoćom P Σ ( a 2 -a 6) = 0,6. Hajde da dodamo poruku a 1 znak 0, a ostale poruke kao prvi znak - 1.
Tabela 1. Proizvoljno kodiranje poruke
U drugoj fazi dijelimo poruke ( a 2 ,a 3 ,a 4 ,a 5 ,a 6) na dva podjednako verovatna dela, uključujući i prvi deo poruke a 2, au drugom dijelu - poruke ( a 3 ,a 4 ,a 5 ,a 6). Hajde da dodamo poruku a 2 kao drugi znak 0, a ostale poruke - 1 itd. Kao rezultat, dolazimo do koda TO 2, dato u tabeli. 2.
Tabela 2. Kodiranje poruka sa Shannon-Fano kodom
Kod po svojoj konstrukciji zadovoljava svojstvo prefiksa. Stoga, gornji niz 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 vjerovatnoće 
= 0,4 * 1 + 0,3 * 2 + 0,3 * 4 = 2,2, tj. neznatno premašuje entropiju izvora poruke.
2.4. Prosječna dužina kodne riječi
Shannon-Fano procedura 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 za naredna kodna slova. Ako se ova particija može izračunati tako da su grupe jednako vjerojatne u svakoj fazi particije, tada će vjerovatnoće izvornih slova i dužina kodnih riječi biti povezane jednakošću
(2)
Ograničenja dužine kodnih riječi prefiksnog koda određena su Craft-ovom nejednakošću i teoremom kodiranja za izvor.
Teorema 1.(Kraftova nejednakost). Ako cijeli brojevi ( 
) zadovoljavaju nejednakost
(3)
onda postoji kod koji ima svojstvo prefiksa sa abecedom veličine D, dužine kodnih reči u kojima su jednake ovim brojevima. Suprotno tome, dužine kodnih riječi bilo kojeg koda sa svojstvom prefiksa zadovoljavaju nejednakost (3). Teorema ne kaže da bilo koji kod čija dužina kodne riječi zadovoljava (3) ima prefiks. Tako, na primjer, skup binarnih kodnih riječi (0; 00; 11) zadovoljava (3), ali nema svojstvo prefiksa. Teorema kaže da postoji neki prefiksni kod sa takvim dužinama, na primjer kod (0; 10; 11). Nijedan jedinstveni kod za dekodiranje nema svojstvo prefiksa, na primjer, K3 kod tabele. 3. U njemu je svaka kodna riječ prefiks svake duže kodne riječi. U isto vrijeme, jednoznačnost dekodiranja je trivijalna, jer simbol 0 uvijek definira početak nove kodne riječi. Kodovi sa svojstvom prefiksa razlikuju se, međutim, od drugih jednoznačno dekodiranih kodova po tome što se kraj kodne riječi uvijek može prepoznati, tako da se dekodiranje može izvesti bez odlaganja posmatranog niza kodnih riječi (kod. K4 iz Tabele 3). Iz tog razloga, prefiksni kodovi se ponekad nazivaju trenutnim kodovima.
Tabela 3. Jedinstveno dekodirani kodovi
Pošto dužine kodnih riječi bilo kojeg jedinstveno dekodiranog koda zadovoljavaju (3) i moguće je konstruirati prefiks kod za bilo koji skup dužina koji zadovoljava (3), tada se svaki jedinstveno dekodirani kod može zamijeniti prefiksnim kodom bez promjene dužine kodne riječi. Stoga je sljedeća teorema 2 za izvorno kodiranje u odnosu na prosječnu dužinu kodne riječi predložena i za jednoznačno dekodirane kodove i za podklasu prefiksnih kodova.
Informacije je skup informacija koje se pohranjuju, prenose, obrađuju i koriste u ljudskoj aktivnosti.
Promena karakteristika medija, koji se koristi za predstavljanje informacija, naziva se signal , a vrijednost ove karakteristike, koja se odnosi na određenu skalu mjerenja, naziva se parametar signala .
Razlikovati dvije vrste signala (i stoga dvije vrste poruka ): kontinuirano i diskretno.
Da bi se osigurala jednostavnost i pouzdanost prepoznavanja diskretnih signala ( znakovi ), preporučljivo je smanjiti njihov broj na minimum. U pravilu pribjegavaju operaciji predstavljanja originalnih znakova u drugom alfabetu 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, zovimo sopstvene informacije
sadržano u x i i označiti 
.
.
Šenonova formula
Hajde da usredsredimo sopstvene informacije, tj. izračunati prosječnu količinu informacija koju nosi jedan znak abecede 
:
.
Prosječna količina informacija pripisiv jedno slovo se zove entropija abeceda (ili izvor) i označeno H:
-
Šenonova formula
.
Očigledno je da prosječna 1 količina informacija u dužini poruke n izračunato po formuli:
.
Komentar.Količina informacija se pripisuje samoj poruci.
Komentar. Entropija je karakteristika izvora poruka (abeceda).
Hartleyeva formula
At equiprobability znakova abecede 
, iz Šenonove formule dobijamo:.
-
Hartleyeva formula
.
Informacijske jedinice
Jedinica količine informacija po jednom elementu poruke (jedinica mjerenja entropije) se zove bit .
Razmotrimo abecedu jednakovjerovatnih simbola sa entropijom jednakom 1: 
... Pošto iz ovoga proizilazi 
, onda je jasno da je 1 bit količina informacija koja je sadržana u binarnoj poruci (abeceda (0,1)) dužine 1.
U daljem tekstu, u izrazima za I i H, uvijek ćemo koristiti logaritme sa bazom 2.
Entropijska svojstva
1. Entropija N- vrijednost
- nenegativan(N 0) ,
-
ograničeno,
Ova svojstva proizilaze iz činjenice da svi njegovi pojmovi imaju iste kvalitete. 
.
2. Entropija je nula ako je vjerovatnoća jednog od simbola 1... U ovom slučaju se govori o potpuno determinističkom izvoru i odsustvu neizvjesnosti u njemu, budući da posmatrač zna za izvornu poruku prije trenutka svog opažanja.
3. Takođe se može pokazati da je entropija je maksimalno ako su svi znakovi abecede jednako vjerovatni, tj. N max = log m... Dakle, Hartleyeva formula se koristi za pronalaženje maksimalne moguće vrijednosti entropije (za fiksni broj simbola).
4. Od posebnog interesa su binarne poruke koristeći binarni alfabet(0,1). Od u m= 2 vjerovatnoće 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 dugme "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, teza, članaka i drugih dokumenata koji nisu traženi na vašem računalu. Ovo je vaš rad, mora učestvovati u razvoju društva i koristiti ljudima. Pronađite ove radove i pošaljite ih u bazu znanja.
Mi i svi studenti, postdiplomci, mladi naučnici koji koriste bazu znanja u svom studiranju i radu bićemo vam veoma zahvalni.
Da preuzmete arhivu sa dokumentom, u polje ispod unesite petocifreni broj i kliknite na dugme "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. Procedura za konstruisanje optimalnog koda primenom Shannon-Fano metode.
seminarski rad, dodan 17.04.2009
Opis i karakteristike nekih algoritama za arhiviranje. Konstrukcija Huffmanovog koda. Dinamički algoritam za konstruisanje Huffmanovog koda. Oporavak teksta unatrag. Metode za dvostepeno kodiranje informacija. Praktična implementacija LZ77 algoritma.
seminarski rad, dodan 24.12.2012
Procjena računske složenosti programa. Implementacija Huffmanovog algoritma za kodiranje 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. Zavisnost između simbola matrice uslovnih vjerovatnoća. Shannon – Fano kodiranje. Propusnost komunikacijskog kanala. Efikasnost 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 komunikacija. Klasifikacija, parametri i konstrukcija kodova za ispravljanje grešaka. Metode prijenosa kodova. Primjer izgradnje Shannonovog koda.
seminarski rad, dodan 25.02.2009
Analiza efikasnosti metoda kodiranja. Prosječna veličina jednog bita i prosječna dužina kodne riječi. Huffman 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 programska struktura. Specifikacija softverskih modula.
seminarski rad, dodan 28.11.2014
U gornjim primjerima kodiranja, sve kodne riječi su bile iste dužine. Međutim, to nije potrebno. Štaviše, ako se vjerovatnoće pojavljivanja poruka značajno razlikuju jedna od druge, onda je bolje poruke s velikom vjerovatnoćom pojavljivanja kodirati kratkim riječima, a rijetke poruke kodirati dužim riječima. Kao rezultat toga, tekst koda će, pod određenim uslovima, u prosjeku postati kraći.
Pokazatelj ekonomičnosti ili efikasnosti neujednačenog koda nije dužina pojedinačnih kodnih riječi, već njihova "prosječna" dužina, određena jednakošću:
gdje je kodna riječ kojom je poruka kodirana, a njena dužina, vjerovatnoća poruke, ukupan broj poruka iz izvora. Za kratkoću pisanja formula, u nastavku se može koristiti sljedeća notacija 
i 
... Imajte na umu da označavanje prosječne dužine 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 dužinom. Koristimo primjere da uporedimo efikasnost različitih metoda kodiranja istog izvora.
Neka izvor sadrži 4 poruke sa vjerovatnoćama. Ove poruke mogu biti kodirane dvoznakovnim kodnim riječima fiksne dužine u abecedi 
prema tablici kodova.
Očigledno, za predstavljanje (prenos) bilo koje sekvence, u prosjeku su potrebna 2 znaka po poruci. Uporedimo efikasnost takvog kodiranja sa gore opisanim kodiranjem sa rečima promenljive dužine. Tabela kodova za ovaj slučaj može biti sljedeća.
U ovoj tabeli, za razliku od prethodne, najčešće poruke su kodirane jednim binarnim znakom. Za posljednju opciju kodiranja imamo
dok za uniformni kod, prosečna dužina (poklapa se sa ukupnom dužinom kodnih reči). Iz razmatranog primjera se može vidjeti da kodiranje poruka riječima različite dužine može dati značajno (skoro dvostruko) povećanje efikasnosti kodiranja.
Prilikom korištenja neujednačenih kodova javlja se problem, koji ćemo objasniti na primjeru posljednje tablice kodova. Neka se ova tabela koristi za kodiranje niza poruka 
, kao rezultat toga se pretvara u sljedeći binarni tekst: 010110. Prvi znak originalne poruke se nedvosmisleno dekodira - ovo. Međutim, počinje dalja neizvjesnost: ili 
... Ovo su samo neke od mogućih opcija za dekodiranje originalnog niza znakova.
Treba napomenuti da se nejasnoća dekodiranja riječi pojavila uprkos činjenici da je ispunjen uvjet za jednoznačno dekodiranje znakova (ijektivnost kodnog preslikavanja).
Suština problema je u nemogućnosti jednoznačne identifikacije kodnih riječi. Da bi se to riješilo, bilo bi potrebno odvojiti jednu kodnu riječ od druge. Naravno, to se može učiniti, ali samo pomoću pauze između riječi ili posebnog znaka za razdvajanje, za koji je potrebna posebna oznaka koda. I jedan i drugi način, prvo, suprotstavljaju se gore opisanoj metodi kodiranja riječi spajanjem kodova znakova koji čine riječ, i, drugo, dovest će do značajnog produžavanja kodnog teksta, negirajući prednosti koristeći kodove promjenjive dužine.
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, neophodno je da kod zadovoljava sljedeći zahtjev: bilo koji niz kodnih tačaka može se jedinstveno podijeliti na kodne riječi. Kodovi za koje je ispunjen posljednji zahtjev nazivaju se jedinstveno dekodirani (ponekad se nazivaju kodovi bez zareza).
Razmotrite kod (abecedna shema kodiranja) 
dato tabelom kodova
i razne riječi sastavljene od elementarnih kodova.
Definicija... Za kod se kaže da je jedinstveno dekodiran ako
to jest, svaka riječ sastavljena od elementarnih kodova je jedinstveno razložena na elementarne kodove.
Ako tabela kodova sadrži iste kodne riječi, odnosno ako
onda kod sigurno nije jednoznačno dekodiran (šema nije odvojiva). O takvim kodovima se dalje ne raspravlja.
Razmotrimo skup poruka koje su upućene njima sa odgovarajućim vjerovatnoćama.Svaka poruka mora biti predstavljena kodnom riječi koja se sastoji od sekvencijalnih znakova koji pripadaju datom alfabetu. Označimo brojem različitih simbola u abecedi, brojem simbola u kodnoj riječi koja odgovara poruci. Prosječan broj simbola po poruci je jednak po definiciji
Naš prvi zadatak je pronaći donju granicu za
U sekti. U 2.8 smo vidjeli da je entropija ansambla poruka prosječna količina informacija potrebnih za jedinstvenu identifikaciju poruke iz tog ansambla. U istom odeljku smo videli da simboli nose, u proseku, maksimalnu količinu informacija kada su podjednako verovatni. Ova maksimalna vrijednost je, naime, kapacitet kodne abecede. Osim toga, jednakosti (2.100) i (2.105) pokazuju da statistička zavisnost određenog simbola od prethodnih ne može povećati prosječnu količinu informacija po ovom simbolu. Na osnovu toga možemo zaključiti da
Gde da stignemo
odnosno prosječan broj simbola po poruci ne može biti manji od entropije ansambla poruka podijeljene sa kapacitetom abecede. Direktan dokaz ovog rezultata dat je u sek. 3.5.
Rezoniranje koje se koristi za dobijanje ove donje granice omogućava da se predlože opšta pravila za konstruisanje kodnih reči sa prosečnom dužinom dovoljno blizu ovoj granici. Prvo pravilo je da na svakoj od pozicija kodne riječi treba koristiti različite znakove abecede sa jednakim vjerovatnoćama kako bi se maksimizirala prosječna količina informacija koju oni daju. Drugo pravilo je da su vjerovatnoće pojave
znakovi na svakoj poziciji kodne riječi moraju biti nezavisni od svih prethodnih znakova. Ako se ova pravila poštuju tačno, tada će prosječna dužina generiranih kodnih riječi biti jednaka minimalnoj vrijednosti određenoj formulom (3.3). Videćemo, međutim, da se samo u posebnim slučajevima simboli mogu koristiti sa jednakim verovatnoćama i učiniti ih nezavisnim od svih prethodnih simbola. Najbolje je objasniti ova pravila za konstruiranje skupova kodnih riječi koristeći sljedeće konkretne primjere. Korištena procedura kodiranja je slična onoj koju je prvi predložio Shannon.
