[ MajorFatal @ 09.11.2013. 01:39 ] @
Neki izvor signala koji je u stanju da izemituje samo 2 razlicita simbola npr: t i z izemitovao je ovakav signal: zttttttttttttttztzztztttz. Kolika je entropija takvog (izemitovanog) signala? Kako se to racuna, po kojoj formuli?

Iako je entropija u pitanju ja bih da na ovo pitanje bude odgovoreno ovde zbog "Matematicke teorije informacija" od C.Shanon-a.
[ darkosos @ 09.11.2013. 08:41 ] @
http://en.wikipedia.org/wiki/Information_theory#Entropy
[ MajorFatal @ 09.11.2013. 13:25 ] @
Hvala za link, citao sam i nasao formule ali nisam siguran da umem da ih upotrebim kako treba. Sta ako ne znam ili ne mogu da znam verovatnocu pojavljivanja simbola?
[ darkosos @ 10.11.2013. 14:31 ] @
Nemam pojma :) Bas zato sam se i zainteresovao i nasao na W. Ako je entropija odstupanje od ocekivanog, onda ne mozes znati koliko je odstupanje ako ne znas sta je ocekivano...
[ atomant @ 10.11.2013. 15:34 ] @
Ako mislis da izracunas entropiju moras da znas verovatnocu pojavljivanja simbola u poruci. Entropija se racuna po formuli:

gde je verovatnoca pojavljivanja simbola .

Ako imas samo 2 simbola, kao u primeru koji je naveden u prvom postu, onda su verovatnoce pojavljivanja simbola i , pa se gornja formula svodi na i grafik entropije ima oblik (ovu sliku sam pozajmio sa interneta):




Dakle moras da znas verovatnocu pojavljivanja simbola na izvoru. Ako je na izvoru konstantno jedan simbol, sadrzaj informacije je 0 (H=0). Ako izvor emituje n simbola gde svaki ima jednaku verovatnocu pojavljivanja onda je

U konkretnom slucaju:
pa je [bita/simbol]

[Ovu poruku je menjao atomant dana 10.11.2013. u 20:44 GMT+1]
[ MajorFatal @ 14.12.2013. 02:15 ] @
Kao sto rekoh (aorist) ne znam verovatnocu pojavljivanja simbola u poruci. Otkopao sam monolit na mesecu i on je shibnuo poruku u daleki svemir a ja konstatovao, od kuda da znam verovatnocu? Telegrafska stanica na divljem zapadu je iznenenada proradila, ne znam da li je uletela veverica, iskusan telegrafista ili duduk, meni su svojevremeno rekli da svaki konacan skup signala ima meru koja se zove entropija...i koja odredjuje do koje mere taj skup signala ili poruka moze biti kompresovan? I to je ono sto me zanima, pa ako neko moze da mi objasni (ili samo objasni)?

Citat:
darkosos: Nemam pojma :) Bas zato sam se i zainteresovao i nasao na W. Ako je entropija odstupanje od ocekivanog, onda ne mozes znati koliko je odstupanje ako ne znas sta je ocekivano...


Mislim da entropija nije odstupanje od ocekivanog, imas ovde: http://sr.wikipedia.org/wiki/%...%D0%B0%D1%86%D0%B8%D1%98%D0%B0)

tj. "U teoriji informacije, entropija je mera neodređenosti pridružena slučajnoj promenljivoj. U ovom kontekstu, obično se misli na Šenonovu entropiju, koja kvantifikuje očekivanu vrednost informacije sadržane u poruci, obično u jedinicama kao što su biti. Ekvivalentno, Šenonova entropija je mera prosečnog informacionog sadržaja koji se propušta kada se ne zna vrednost slučajne promenljive. Koncept je uveo Klod Šenon u svom čuvenom radu iz 1948. godine „Matematička teorija komunikacija“.
Šenonova entropija predstavlja apsolutnu granicu najbolje moguće kompresije bez gubitaka bilo kakve komunikacije, pod izvesnim ograničenjima: ako tretiramo poruke da su kodovane kao niz nezavisnih slučajnih promenljivih sa istom raspodelom, prva Šenonova teorema pokazuje da, u graničnom slučaju, srednja dužina najkraće moguće reprezentacije za kodovanje poruka u datom alfabetu je njihova entropija podeljena sa logaritmom broja simbola u ciljnom alfabetu."

Tj. entropija ti je mera neuredjensti sistema tj. u ovom smislu neodredjenosti sistema

teorija informacija ti je ovde: http://plan9.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf

Citat:
atomant: Ako mislis da izracunas entropiju moras da znas verovatnocu pojavljivanja simbola u poruci. Entropija se racuna po formuli:

gde je verovatnoca pojavljivanja simbola .

Ako imas samo 2 simbola, kao u primeru koji je naveden u prvom postu, onda su verovatnoce pojavljivanja simbola i , pa se gornja formula svodi na i grafik entropije ima oblik (ovu sliku sam pozajmio sa interneta):




Dakle moras da znas verovatnocu pojavljivanja simbola na izvoru. Ako je na izvoru konstantno jedan simbol, sadrzaj informacije je 0 (H=0). Ako izvor emituje n simbola gde svaki ima jednaku verovatnocu pojavljivanja onda je

U konkretnom slucaju:
pa je [bita/simbol]

[Ovu poruku je menjao atomant dana 10.11.2013. u 20:44 GMT+1]


Hvala, veoma si mi pomagao, da proverim da li sam dobro razumeo, u slucaju da je izvor signala izemitovao neku od sledecih poruka:

1.) tttttttttttttttttttzzzzzz
2.) tztttztttztttztttztttzttt
3.) ztztttttzttzttttztttztttt

sve ove poruke bi imale isti nivo entropije jer imaju isti broj simbola t i z? tj.

pa je [bita/simbol]

kao sto rekoh meni treba entropija koja "odredjuje" do koje mere neki signal moze biti kompresovan "u istom alfabetu" valjda, ili u "ciljanom" alfabetu? Mozda je "relativna entropija" u pitanju? 1 - (minus) relativna entropija je redundansa?
[ hotchimney @ 14.12.2013. 03:18 ] @
Samo da primetim da na stranici Wikipedia za koju je ostavljen link stoji:
Citat:
Nemamo članak "Entropija (teorija informacija"

[ MajorFatal @ 14.12.2013. 11:27 ] @
Pardon, ovde:

http://sr.wikipedia.org/wiki/%...%D0%B0%D1%86%D0%B8%D1%98%D0%B5

i ovde:

http://sr.wikipedia.org/wiki/%...%D0%B0%D1%86%D0%B8%D1%98%D0%B0)

ne znam zasto ne radi ovaj drugi link, mozete doci do te stranice ako ukucate "entropija" u polje za pretragu na wikipediji pa onda nadjete link za Entropija (teorija informacije) tekst je trenutno ovaj:

Entropija (teorija informacija)
Iz Vikipedije, slobodne enciklopedije
U teoriji informacije, entropija je mera neodređenosti pridružena slučajnoj promenljivoj. U ovom kontekstu, obično se misli na Šenonovu entropiju, koja kvantifikuje očekivanu vrednost informacije sadržane u poruci, obično u jedinicama kao što su biti. Ekvivalentno, Šenonova entropija je mera prosečnog informacionog sadržaja koji se propušta kada se ne zna vrednost slučajne promenljive. Koncept je uveo Klod Šenon u svom čuvenom radu iz 1948. godine „Matematička teorija komunikacija“.
Šenonova entropija predstavlja apsolutnu granicu najbolje moguće kompresije bez gubitaka bilo kakve komunikacije, pod izvesnim ograničenjima: ako tretiramo poruke da su kodovane kao niz nezavisnih slučajnih promenljivih sa istom raspodelom, prva Šenonova teorema pokazuje da, u graničnom slučaju, srednja dužina najkraće moguće reprezentacije za kodovanje poruka u datom alfabetu je njihova entropija podeljena sa logaritmom broja simbola u ciljnom alfabetu.
Jedno bacanje fer novčića nosi entropiju od jednog bita. Dva bacanja - dva bita. Brzina entropije za novčić je jedan bit po bacanju. Međutim, ako novčić nije fer, tada je neodređenost manja (ako bismo morali da se kladimo na ishod narednog pokušaja, verovatno ćemo se kladiti na češći rezultat), pa je i Šenonova entropija manja. Matematički, jedno bacanje novčića (fer ili ne) predstavlja Bernulijev eksperiment, a njegova entropija data je binarnom entropijskom funkcijom. Niz bacanja novčića sa dve glave imaće nultu entropiju, jer su ishodi potpuno predvidljivi. Brzina entropije teksta na engleskom je od 1 do 1,5 bita po slovu, odnosno od 0,6 do 1,3 bita po slovu, prema procenama baziranim na eksperimentima.[1][2]
Definicija[uredi]

Šenon je definisao entropiju H diskretnog izvora bez memorije (diskretne slučajne promenljive) X nad konačnim alfabetom Z=\{z_1, z_2, \dots, z_m\} na sledeći način. Prvo se dodeli svakoj verovatnoći p nekog događaja njena količina informacije I(p) = -\log_2 p. Tada je entropija po simbolu definisana kao očekivana vrednost (matematičko očekivanje) količine informacija
H_1 = \sum_{z\in Z} p_z \cdot I(p_z) = - \sum_{z\in Z} p_z \cdot \log_2 p_z,
Neka je z\in Z, tada je p_z = P(X=z) verovatnoća da se dogodi simbol z iz alfabeta, ili ekvivalentno
(1)\qquad H_1 = - \sum_{i=1}^{m} p_i \cdot \log_2 p_i,
Za graničnu vrednost \lim_{p_i\rightarrow 0} p_i \cdot \log_2 p_i se može pokazati da je nula. Prema tome, sabirci sa verovatnoćom jednakom nuli ne doprinose ukupnom zbiru (tj. entropiji).
Entropija H_n za reči w dužine n je data sa
H_n = -\sum_{w\in Z^n} p_w \cdot \log_2 p_w,
gde je p_w = P(X=w) verovatnoća da će se dogoditi reč w. Entropija H je tada granična vrednost:
(2)\qquad H = \lim_{n\to \infty} \frac{H_n}{n}.
Ako su simboli statistički nezavisni, tada H_n = nH_1 za svako n, kao i H = H_1.
Interpretacija[uredi]

Entropija predstavlja meru prosečnog informacionog sadržaja po simbolu izvora koji predstavlja neki sistem ili informacionu sekvencu. U teoriji informacija, kao mera za količinu informacije u nekoj poruci može poslužiti koliko se promenila verovatnoća događaja pod uticajem te poruke. Na primer, ako za vreme leta vremenska prognoza za sutrašnji dan najavi 30° C, to nam neće doneti mnogo informacija, jer ne sadrži ništa neočekivano. Međutim, ako se ista takva prognoza dogodi zimi, to predstavlja potpuno neočekivanu vest i samim tim sadrži mnogo informacija. Pod informacijom se može smatrati i mera uklonjene nesigurnosti. Što se više simbola primi od izvora, dobijamo više informacija i opada nesigurnost oko onoga šta je moglo biti poslato.
Definicija informacionog sadržaja se može na sledeći način opisati: ako se desi događaj čija je verovatnoća p_i, tada je kroz to izabran jedan konkretan događaj iz hipotetičkog skupa od \tfrac{1}{p_i} jednako verovatnih događaja. Da bi se ovi događaji međusobno razlikovali, potrebno im je dodeliti \log_2 \left(\tfrac{1}{p_i}\right) = -\log_2 (p_i) bita. Ova vrednost predstavlja količinu informacije jednog određenog događaja u bitima. Kada se količina informacije svakog događaja ponderiše sa verovatnoćom istog događaja, i kada se saberu (tj. pronađe se matematičko očekivanje količine informacije), dobijamo srednju ili očekivanu količinu informacije po simbolu.
Jedinica Šenon definiše količinu informacije koju sadrži poruka o događaju sa verovatnoćom p = 0,5. Na primer, saopštenje o tome da je metalni novčić pao na određenu stranu donosi informaciju od 1 Šenona. Ili, ako na prijemnoj strani binarnog telekomunikacionog sistema, čiji je signal sastavljen od bipolarnih impulsa konstantne amplitude, merimo polarnost dolazećih impulsa, i ako je verovatnoća pojavljivanja pozitivnih i negativnih amplituda jednaka, onda svaki impuls nosi informaciju od 1 Šenona. Međutim, ako verovatnoće pojavljivanja pozitivnih i negativnih amplituda nisu jednake, onda jedan impuls donosi prijemniku neku drugu količinu informacija koja nije 1 Šenon. Treba razlikovati pojam binarni digit, skraćeno bit, od pojma Šenon. Bit je samo nosilac informacije i fizički je predstavljen impulsom koji može da ima dva stanja. U zavisnosti od verovatnoće pojavljivanja stanja, bit može da donosi prijemniku veću ili manju količinu informacija. Samo kad su verovatnoće pojavljivanja dva stanja kod bita jednake, onda bit nosi količinu informacije od 1 Šenona.[3]
Izvori[uredi]

^ Schneier, B: Applied Cryptography, Second edition, page 234. John Wiley and Sons.
^ Shannon, Claude E.: Prediction and entropy of printed English, The Bell System Technical Journal, 30:50-64, January 1951.
^ Lukatela, G: Statistička teorija telekomunikacija i teorija informacija, strane 258-259. Građevinska knjiga, Beograd, 1981.

[ atomant @ 14.12.2013. 11:37 ] @
Citat:
MajorFatal:
Hvala, veoma si mi pomagao, da proverim da li sam dobro razumeo, u slucaju da je izvor signala izemitovao neku od sledecih poruka:

1.) tttttttttttttttttttzzzzzz
2.) tztttztttztttztttztttzttt
3.) ztztttttzttzttttztttztttt

sve ove poruke bi imale isti nivo entropije jer imaju isti broj simbola t i z? tj.

pa je [bita/simbol]

kao sto rekoh meni treba entropija koja "odredjuje" do koje mere neki signal moze biti kompresovan "u istom alfabetu" valjda, ili u "ciljanom" alfabetu? Mozda je "relativna entropija" u pitanju? 1 - (minus) relativna entropija je redundansa?



Da. Sve poruke koje si naveo bi imale isti nivo entropije.
Ako te zanima kodiranje signala na osnovu entropije, pogledaj clanak na wikipediji o Hafmanovom kodu za kompresiju podataka bez gubitaka (JPEG i MPEG formati slike i videa koriste ovu vrstu kompresije, doduse rezultujuci video i slika imaju neke gubitke u informacijama ali one ne poticu od Hafmanovog koda vec od drugih koraka u kompresiji). PNG i GIF su looseless kompresije.

http://en.wikipedia.org/wiki/Huffman_coding
[ MajorFatal @ 19.01.2014. 05:26 ] @
Dakle evo ovde na primer: http://www.elitesecurity.org/t93798-1#611499

"Svaki signal (konacni niz karaktera da se ogranicimo) ima jednu vrednost koja se zove entropija, i koja oblikuje teoretski minimum sa kojim ta ista informacija moze da se opise."

s tim sto, za ova dva signala:

1.)ttttttttttttttttttttttttzzzzzzzzzzzzzzzzzzzzzzzz

2.)ttzztttztzzzzztztzttzzttttzzttzztztzttzztttztzzz

ako bih racunao entropiju tako kako si ti predlozio ispalo bi da imaju isti nivo entropije: tacno 1, tj. da su oba "nekompresibilni" a meni deluje kako god da pregledam da ovaj prvi signal pod rednim brojem 1. ima dosta redundanse i da je samim tim kompresibilan, za razliku od drugog pod rednim brojem 2. koji deluje da je prilicno random strukture i samim tim zaista prilicno nekompresabilan?

Dakle to me zanima: kako da odredim vrednost entropije koja mi oblikuje teoretski minimum sa kojim neku informaciju mogu da opisem?
[ MajorFatal @ 03.02.2014. 01:41 ] @
za ova dva signala:

1.)ttttttttttttttttttttttttzzzzzzzzzzzzzzzzzzzzzzzz

2.)ttzztttztzzzzztztzttzzttttzzttzztztzttzztttztzzz

ako bih racunao entropiju po formuli koju si dao bilo bi:

pa je [bita/simbol]

ili na vecem primeru:



ovo je slika do pola bela, a od pola crne boje u .bmp formatu i zauzima oko 500k, sve su prilike da program koji koristim za obradu grafike koduje belu boju sa #FFFFFF a crnu sa #000000


ako bih racunao entropiju po gorenavedenoj formuli ispalo bi da je medjutim ova slika je veoma kompresabilna zip je svede na 711 bita, za razliku od nekog .exe fajla slicne velicine kod koga je entropija zaista oko 1 i koga zip "smanji" samo za stoti deo velicine originalnog fajla sa 507k na 494k?

Dakle ili nije ta formula za entropiju, ili entropija ne oblikuje teoretski minimum sa kojim neki signal moze da se opise?

[Ovu poruku je menjao MajorFatal dana 03.02.2014. u 02:52 GMT+1]
[ djoka_l @ 03.02.2014. 08:11 ] @
Druže majore,
pohvalno j e što si odlučio da malo istražiš teoriju pre nego što se ponovo baciš na komprimovanje slučajnog niza (kao što si pre pokušavao).
Međutim, potrebno je da još malo proučiš materiju, pre nego što tvoj algoritam proradi.

Vidim da ne razumeš pojam simbola, pa da ti malo razjasnim.
Kada imaš binarni signal i posmatraš poruku bit po bit (u tvom slučaju gledaš samo simbole t i z, a to možemo i da interpretiramo kao 0 1) nikakvu kompresiju ne možemo da ostvarimo jer jedan bit informacije ne možemo da predstavimo sa manje od jednog bita. Kolikva god da je frekvencija pojavljivanja jednog ili drugog simbola, ne možeš uzeti da je jedan signal, na primer t predstavljen sa 0.2 bita, a drugi sa 8 bita, pa da ostvariš kompresiju drugačijim kodiranjem, nego mora biti po jedan bit.

Sa druge strane, kada se kaže "signal" u teoriji informacija se ne podrazuma jedan bit informacije nego jedan simbol iz skupa simbola. Zamisli situaciju da meteorološka stanica treba da pošalje jedan podatak koji predstavlja vreme, i da to vreme uzima jednu od vrednosti iz skupa, sunčano, oblačno, kiša, sneg. Dakle, imamo skup od 4 "simbola" i treba da ih kodiramo na neki način. Pošto imamo 4 različita ishoda eksperimenta, tada su nam potrebna dva bita, pa recimo da te ishode kodiramo kao 00, 01, 10 i 11.

E sada, ako ta meteorološka stanica radi u pustinji, ona će najčešće slati poruku 00, ponekad 01, vrlo retko 10, a skoro nikada 11. Dakle, ima smisla da se sunčano vreme kodira sa jednim bitom, na primer 0, a da se ova druga tri vremena kodiraju sa više od dva bita, pa bi se pri tome poruka "komprimovala".

Dakle, posmatraj malo, umesto bit po bit, poruku kao grupu bitova, pa ćeš videti da se pojavljuju drugačije vrednosti entropije.

Recimo tvoja poruka od 24 slova t i 24 slova z u prvom slučaju ima verovatnoću pojavljivanja 24 slova t u nizu 1/2 i 24 slova z u nizu 1/2, pa je moguće da (pošto ima samo dva moguća ishoda) se svaki od mogućih ishoda kodira samo sa jednim bitom.

[Ovu poruku je menjao djoka_l dana 03.02.2014. u 09:49 GMT+1]
[ MajorFatal @ 08.02.2014. 02:26 ] @
Citat:
djoka_l: Druže majore,
pohvalno j e što si odlučio da malo istražiš teoriju pre nego što se ponovo baciš na komprimovanje slučajnog niza (kao što si pre pokušavao).


Druze djoka_I, nemam pojma o cemu pricas: http://sr.wikipedia.org/w/inde...&action=edit&redlink=1

Deluje mi da si malo odlutao od zadatka za sta sam verovatno ja kriv zbog nevestog nacina postavljanja, pa da ponovim preciznije: kad odredim nivo entropije nekog signala, a uzimajuci u obzir matematicku teoriju informacija, na koji nacin, kako, uz pomoc koje jednacine mi nivo entropije oblikuje teoretski minimum sa kojim ta ista informacija moze da se opise.?

Citat:
Međutim, potrebno je da još malo proučiš materiju, pre nego što tvoj algoritam proradi.

Radi savrseno, hvala na propitivanju, tj, program uradjen po algoritmu radi savrseno, doduse ne po onom koji sam predstavio na es-u. Ako se dobro secam, a secam se, tvoja primedba u jednoj od rasprava koju sam pokrenuo je bila da je glavni problem sa algoritmom da on ni ne postoji, pa ako ne postoji ne moze ni da proradi?

Citat:
Vidim da ne razumeš pojam simbola, pa da ti malo razjasnim.

Nauci me kaludjeru moj http://www.youtube.com/watch?v=EuyEapqJOcE



Citat:
Kada imaš binarni signal i posmatraš poruku bit po bit (u tvom slučaju gledaš samo simbole t i z, a to možemo i da interpretiramo kao 0 1)
a mozemo da interpretiramo i kao z u, u i, i o, o p, tj. bilo koja dva simbola, tacno netacno, ima napon nema napon, itd... ja bih rekao simbol po simbol, a ne bit po bit? (mozemo da interpretiramo kao 0 1 ali zasto bi, ako je jedina operacija kodovanje tj. zamena jednog niza drugim, zasto bi smo uvodili binarni brojni sistem ako necemo operisati nad brojevima i koristiti racunske operacije? t i z su sasvim lepa slova kao sto su i 0 i 1 lepi brojevi.)

Citat:
nikakvu kompresiju ne možemo da ostvarimo jer jedan bit informacije ne možemo da predstavimo sa manje od jednog bita.
Ali ja to nisam ni tvrdio?

Citat:
Kolikva god da je frekvencija pojavljivanja jednog ili drugog simbola, ne možeš uzeti da je jedan signal, na primer t predstavljen sa 0.2 bita, a drugi sa 8 bita,
Ko kaze da ne mogu, to je stvar konvencije?

Citat:
pa da ostvariš kompresiju drugačijim kodiranjem,
Naravno, kompresija se moze ostvariti samo i iskljucivo drugacijim kodiranjem?

Citat:
nego mora biti po jedan bit.
"Biti po jedan bit"? Eh te jezicke zavrzlame.



Citat:
Sa druge strane, kada se kaže "signal" u teoriji informacija se ne podrazuma jedan bit informacije nego jedan simbol iz skupa simbola.

Ne bih rekao. Kad se kaze "signal" u teoriji informacija a i inace, misli se na signal iliti poruku tj, niz simbola a ne na jedan simbol iz skupa simbola. ispravi me ako gresim? "Signal" je signal, a simbol je simbol, "signal" nije jedan simbol iz skupa simbola kao sto si ti napisao.

Citat:
Zamisli situaciju da meteorološka stanica treba da pošalje jedan podatak koji predstavlja vreme, i da to vreme uzima jednu od vrednosti iz skupa, sunčano, oblačno, kiša, sneg.

Ti za pocetak zamisli situaciju da ljudi resavaju zadatke koji su postavljeni, a ne neke druge.

Citat:
Dakle, imamo skup od 4 "simbola" i treba da ih kodiramo na neki način.

Ne, nego imamo skup od 4 vrednosti, i mozda hocemo da ih kodiramo na neki nacin, prilagodjeno kanalu prenosa ili primaocu poruke.
Citat:
Pošto imamo 4 različita ishoda eksperimenta, tada su nam potrebna dva bita, pa recimo da te ishode kodiramo kao 00, 01, 10 i 11.

Mislim da ti nedostaje par reci: "najmanje", "sa istim verovatnocama pojavljivana" i "binarni brojni sistem". Kao na primer: posto "imamo" 4 razlicita ishoda eksperimenta, sa istim verovatnocama pojavljivanja, tada su nam potrebna najmanje dva bita (simbola?) za kodovanje tih vrednosti, tj. ishoda eksperimenta, pa recimo da te ishode kodiramo kao: tt, tz, zt, zz ili tt, tzt, ztzz i zztzztzztzz, ili 0, 1, 2, 3 ili a, b, c, d ili itd...


Citat:
E sada, ako ta meteorološka stanica radi u pustinji, ona će najčešće slati poruku 00, ponekad 01, vrlo retko 10, a skoro nikada 11. Dakle, ima smisla da se sunčano vreme kodira sa jednim bitom, na primer 0, a da se ova druga tri vremena kodiraju sa više od dva bita, pa bi se pri tome poruka "komprimovala".


Pa, sad, sve zavisi, moram prvo da dohakam da si ti zamislio da meteoroloska stanica svakodnevno ili vise puta u toku dana meri vreme i salje informaciju o istom. U suprotnom ako bi m. stanica merila vreme 6 puta godisnje ili na primer sve ukupno 6 puta, s tim sto bi tih 6 puta bilo rasporedjeno bas pocetkom kisne sezone koja opet traje 2 nedelje godisnje, dosli bi do ovoga: 3 puta suncano, 2 puta oblacno, 1 puta kisa, 0 puta sneg. Ima smisla da se suncano vreme kodira sa jednim bitom (simbolom) ako bi izvestaj o tome isao 345 puta u godini, ali ako bi isao tri puta godisnje? Na matematickom smo forumu, izvoli izracunaj, ako suncano vreme kodiras sa 1 simbolom, a ova druga tri vremena sa vise od dva simbola, koliko godina vremena treba da prodje da bi mogao da racunas da ti je poruka "komprimovana" kao sto si lepo napisao?



Citat:
Dakle, posmatraj malo, umesto bit po bit, poruku kao grupu bitova, pa ćeš videti da se pojavljuju drugačije vrednosti entropije.

Da pokusam: posmatracu poruku: 1.)ttttttttttttttttttttttttzzzzzzzzzzzzzzzzzzzzzzzz za koju sam utvrdio da je entropija jednako 1:

a) grupa "bitova" (simbola) duzine dva: tt 12 puta, tz nula puta, zt nula puta (pa tz i zt ne ucestvuju u racunici) i zz 12 puta, sve ukupno 24 grupe od po dva simbola. Racunam entropiju:

pa je [bita/simbol]

b) grupa "bitova" (simbola) duzine tri: ttt: osam puta, ttz, tzt, tzz, ztt, ztz, zzt nula puta, zzz osam puta. Sve ukupno: 16 grupa od po tri simbola.

pa je [bita/simbol]

c) grupa "bitova" (simbola) duzine cetri: ... itd...

I dalje je entropija 1 pa bi signal ( poruka ) trebao biti nekompresabilan, ali je u realnosti veoma kompresabilan kao sto smo videli na vecem primeru.


Citat:
Recimo tvoja poruka od 24 slova t i 24 slova z u prvom slučaju ima verovatnoću pojavljivanja 24 slova t u nizu 1/2 i 24 slova z u nizu 1/2, pa je moguće da (pošto ima samo dva moguća ishoda) se svaki od mogućih ishoda kodira samo sa jednim bitom.
"poruka od 24 slova t i 24 slova z u prvom slučaju" rekao bih da nema verovatnocu pojavljivanja 24 slova t u nizu 1/2, vec izvesnost da se pojavilo 24 simbola t i 24 simbola z, a nikakvu verovatnocu bilo kakvog pojavljivanja. poruka je zavrsena i ne planira se bilo kakvo novo emitovanje simbola t ili z.

Citat:
pa je moguće da (pošto ima samo dva moguća ishoda)
samo dva moguca ishoda cega???

Citat:
se svaki od mogućih ishoda kodira samo sa jednim bitom.


Iskreno receno mislim da i celu poruku mozes da kodiras samo sa jednim bitom, ako se bavis kodiranjem, ali i kodiranje kao operacija ima svoja pravila i uslove...

Jos jednom za one sa rasutom paznjom zadatak je: Na osnovu nivoa entropije nekog signala, a uzimajuci u obzir matematicku teoriju informacija, na koji nacin, kako, uz pomoc koje jednacine mi nivo entropije oblikuje teoretski minimum sa kojim ta ista informacija moze da se opise?



[ Odin D. @ 08.02.2014. 03:59 ] @
Citat:
MajorFatal: Kao sto rekoh (aorist) ne znam verovatnocu pojavljivanja simbola u poruci. Otkopao sam monolit na mesecu i on je shibnuo poruku u daleki svemir a ja konstatovao, od kuda da znam verovatnocu? Telegrafska stanica na divljem zapadu je iznenenada proradila, ne znam da li je uletela veverica, iskusan telegrafista ili duduk, meni su svojevremeno rekli da svaki konacan skup signala ima meru koja se zove entropija...i koja odredjuje do koje mere taj skup signala ili poruka moze biti kompresovan? I to je ono sto me zanima, pa ako neko moze da mi objasni (ili samo objasni)?

Entropija je definisana kao prosjecna kolicina informacija koju prenosi jedan simbol.
Simbol je jedan znak iz alfabeta kojeg emituje izvor informacija. U tvom slucaju simbol je binarni (t ili z).

Matematicki, entropija JE DEFINISANA preko formule koja u sebi SADRZI VJEROVATNOCU pojavljivanja tih simbola u poruci.

To sto ti ne znas vjerovatnocu pojavljivanja simbola u porukama koje emituje neki izvor direktno implicira da ne mozes znati ni entropiju tog signala, a posto ne znas entropiju onda, je li, logicno slijedi da ne mozes izrazunati nista preko formula koje se baziraju na poznavanju entropije, bez obzira sta ti je neko svojevremeno o tome rekao.

Citat:
MajorFatal: meni su svojevremeno rekli da svaki konacan skup signala ima meru koja se zove entropija...

Ispravno je da "svaki signal sa konacnim skupom simbola koji imaju poznatu vjerovatnocu pojavljivanja ima mjeru koja se zove entropija".
[ Nedeljko @ 09.02.2014. 20:09 ] @
Citat:
Odin D.: Matematicki, entropija JE DEFINISANA preko formule koja u sebi SADRZI VJEROVATNOCU pojavljivanja tih simbola u poruci.

Živo me zanima kako glasi ta formula koju niko nikada nigde nije ni video ni napisao.

Entropija se definiše za slučajne promenljive. Ako pojavljivanja simbola u porukama nisu nezavisna, kakve god da su im verovatnoće (pozate ili nepoznate), enropija izvora poruka nije jednoznačno određena.

Ako je diskretna slučajna pomenljiva koja može da ima vrednosti sa verovatnoćama , gde je i , onda je njena entropija

,

pri čemu uzimaš da je .

Ako izvor emituje poruke od 10 istih bitova, pri čemu su u pogledu verovatnoće 0 i 1 ravnopravni, onda je entropija izvora jednaka 1, jer imaš samo dve moguće poruke - 0000000000 i 1111111111, koje su jednakoverovatne, tj. .

Ako pak imaš izvor koji može bilo koji niz od 10 bitova da proizvede sa jednakom verovatnoćom, onda je i entropija izvora je jednaka 10.
[ hotchimney @ 09.02.2014. 22:12 ] @
Citat:
MajorFatal

kad odredim nivo entropije nekog signala, a uzimajuci u obzir matematicku teoriju informacija, na koji nacin, kako, uz pomoc koje jednacine mi nivo entropije oblikuje teoretski minimum sa kojim ta ista informacija moze da se opise.?

Dobro, ako sam pravilo razumeo, ti si odredio entropiju signala (ne ulazeći u to na koji način).

Ako imas dva simbola tada je Shannon-ova entropija jednaka

H(X) = -(p(x1)*log2p(x1)+p(x2)*log2p(x2))

Može da bude p(x1) < p(x2), p(x1) == p(x2) i p(x1) > p(x2) i važ p(x1) + p(x2) = 1.

Definiši neki statistički test (izbor testa ti je na volju jer nije uslov zadatka). Primeni taj test na sva tri slučaja i dobićeš neke informacije koje ti mogu poslužiti u odgovoru na postavljeno pitanje u granicama odredjenim moći testa.

Onda ti ostaje da napišeš program (malo složeniji) koji će test da primeni na više promenljivih.
[ Odin D. @ 11.02.2014. 18:25 ] @
Citat:
Nedeljko: Živo me zanima kako glasi ta formula koju niko nikada nigde nije ni video ni napisao.


Izvinjavam se zbog kasnjenja, dva dana nisam mogao da otvorim ES, ne znam sta je bilo u pitanju.

Elem, sto se tice tvoje opaske, moram prvo da se ogranicim: moje primjedbe se odnose iskljucivo na pitanje sa ove teme i iskljucivo u okviru matematicke teorije i prakse DIGITALNIH KOMUNIKACIJA. Na osnovu pitanja koje je pokrenulo ovu temu sam zakljucio da se o tome radi.

Dakle, u teoriji i praksi digitalnih komunikacija formula kojom se racuna entropija nekog izvora signala u sebi sadrzi clanove koji predstavljaju vjerovatnoce pojavljivanja simbola(ili uopsteno - poruka) koje izvor emituje.
Formula je ovdje vise puta napisana, a posto se u njoj pojavljuju clanovi p(i) gdje to p(i) predstavlja vjerovatnocu pojavljivanja simbola/poruke i, onda je to ta formula koja u sebi sadrzi pomenute vjerovatnoce.
Ne znam zbog cega onda mislis da je "niko nikada nigde nije ni video ni napisao"?!


Citat:
Nedeljko: Entropija se definiše za slučajne promenljive. Ako pojavljivanja simbola u porukama nisu nezavisna, kakve god da su im verovatnoće (pozate ili nepoznate), enropija izvora poruka nije jednoznačno određena.

U teoriji i praksi digitalnih komunikacija entropija je itekako definisana i odredjena za izvor koji emituje poruke/signale cije pojavljivanje nije statisticki medjusobno nezavisno.
U tom slucaju, formula za entropiju u obzir uzima 'joint and conditional statistics' (ne znam ispravan izraz za ovo na srpskom jeziku, ali onaj ko se time bavi na domacem terenu sigurno zna o cemu se radi) niza simbola. To bi bilo neko P(i , j) i P(i | j) u formulu za entropiju u slucaju npr. izvora sa memorijom od jednog simbola.
Na tome su zasnovane citave moderne telekomunikacije i dobar broj digitalnih kodova. Vrlo me cudi takva izjava.

Citat:
Nedeljko
Ako izvor emituje poruke od 10 istih bitova, pri čemu su u pogledu verovatnoće 0 i 1 ravnopravni, onda je entropija izvora jednaka 1, jer imaš samo dve moguće poruke - 0000000000 i 1111111111, koje su jednakoverovatne, tj. .

Nema mnogo smisla (osim ako je u pitanju dodatna redudansa uslijed ocekivanih smetnji na vezama) da se emituju poruke 0000000000 i 1111111111 kad se to moze kompletno zamjeniti sa 0 i 1, zato i entropija jeste 1, a sta to znaci pogledati malo nize alternativna tumacenja entropije.

Citat:
Nedeljko: Ako pak imaš izvor koji može bilo koji niz od 10 bitova da proizvede sa jednakom verovatnoćom, onda je i entropija izvora je jednaka 10.

Zbog toga u teoriji i praksi digitalnih komunikacija postoji jos par alternativnih 'prakticnih' tumacenja entropije koji djeluju malo jasnije onima koji nisu teorijski matematicari:

i) - entropija je definisana kao prosjecna kolicina prenesenih informacija po simbolu;
ii) - u specijalnom slucaju npr. binarnih signala: entropija predstavlja minimalni broj binarnih cifri potrebnih za kodiranje simbola (usrednjeno na dovoljno dugackoj sekvenci simbola).

Zbog toga se npr. ASCII poruke mogu kodirati u prosjeku sa manje od 7 bitova po simbolu, jer simboli u nekom jeziku obicno nemaju istu vjerovatnocu pojavljivanja niti su te vjerovatnoce nezavisne. Slovo 'a' se recimo mnogo cesce pojavljuje u engleskom jeziku nego slovo 'z', pa se za kodiranje slova 'a' moze izabrati neka kraca binarna sekvenca od npr. 3 bita, a za slovo 'z' neka od 20 bitova (Huffman-ov kod je popularan za takve akrobacije). No, u prosjeku, posto se 'a' emituje mnogo cesce nego 'z', ukupan broj emitovanih bitova bude manji nego da su i 'a' i 'z' kodirani sa po 7 bitova npr., pa je npr. entropija izvora koji emituje neki tekst na engleskom jeziku pomocu ASCII simbola manja od 7.

Dakle, to je entropija signala u digitalnim komunikacijama i to je 'prakticno' znacenje entropije u tom domenu.
(Pretpostavljam da nema nikakve specijalne razlike u odnosu na 'entropiju slucajne promenjive' kako se to radi/naziva u teorijskoj matematici, osim naziva i tumacenja prilagodjenih na domen signala i komunikacija).


[ MajorFatal @ 15.02.2014. 17:38 ] @
Takodje se izvinjavam zbog dinamike kojom pisem ovde ali sam stvarno u cajknotu sa vremenom.

Za sada samo ovo:

Ako sam ikoga doveo u zabludu nevestim izlaganjem, "z" i "t" u gornjim primerima bi trebalo da korespondiraju sa 0 i 1 iz binarnog brojnog sistema samo bez onog "brojni", z nije vece od t (i obrnuto), ne mogu se sabirati, nijedan od simbola ne odgovara logickoj nuli ili jedinici tj. tacno i netacno itd...uz pomoc niza z i t moze se samo kodovati neka poruka, ne mogu se odseci leading t-s itd...
Slobodno ih zamenite sa 0 i 1 iz navike ili sa razlogom, ali bih onda voleo i da navedete razlog.
Dakle iza "z" ili "t" ne postoje blokovi koda, ili neki drugi binarni nizovi, z i t nisu deo nekog sireg alfabeta, azbuke, abecede, ascii koda, vec jedina dva simbola, znaka u alfabetu koji koristimo, tj izvor signala emituje samo dva razlicita signala a mi smo ih oznacili sa "z" i "t".

Izvor signala je binarni tj. emituje samo 2 razlicita impulsa.
Alfabet kojim obelezavamo ta dva impulsa (signala) je binarni i sastoji se od "t" i "z".
Signal je binarni i izgleda kao niz t i z na primer: ttztzztzzzztttt...

Izvor signala je izemitovao ovakvu poruku: "tzzzzzzzzzzzztzztttzttzztzttt"

1.) Izracunati entropiju poruke koja je emitovana
2.) Na osnovu izracunate entropije zakljuciti, izracunati, pokazati, naslikati, oblikovati teoretski minimum sa kojim je taj isti binarni signal (poruku) moguce opisati u istom alfabetu t i z.
[ djoka_l @ 15.02.2014. 19:36 ] @
Evo uputstva za kodiranje poruke:
1. Poruku: tzzzzzzzzzzzztzztttzttzztzttt kodiramo sa '0'
2. Ako je poruka različita od tzzzzzzzzzzzztzztttzttzztzttt, kodiramo tako što stavimo kao prvi bit poruke vrednost '1', a zatim svako 't' zamenimo sa '1', a svako z sa '0'

Dakle, teorijski minimum kojim kodiramo tzzzzzzzzzzzztzztttzttzztzttt je jedan bit (0).
[ Odin D. @ 16.02.2014. 00:19 ] @
Imam ja jos kraci minimum: ako do podne ne stigne nikakva poruka podrazumjeva se "tzzzzzzzzzzzztzztttzttzztzttt", u suprotnom t zamjenimo sa "1", a z sa "0".
Tako da je teorijski minimum za navedenu poruku nula bitova.
[ Nedeljko @ 16.02.2014. 09:24 ] @
Citat:
MajorFatal:  1.) Izracunati entropiju poruke koja je emitovana

Entropija nije definisana za poruke, već za slučajne promenljive, što u ovom slučaju znači izvor kao celinu, a ne poruku koju je emitovo.
[ hotchimney @ 18.02.2014. 15:06 ] @
Entropija poruke se pominje na wikipedia
Citat:
The entropy of a message multiplied by the length of that message is a measure of how much information the message contains.

http://en.wikipedia.org/wiki/Entropy_(information_theory)

iako u tom tekstu nije definsana.
[ Nedeljko @ 18.02.2014. 16:15 ] @
Među referencama na istoj strani pod 2 piše da se pod "porukom" smatra specifična realizacija slučajne promenljive.

Dakle, ipak se radi o entropiji slučajne promenljive.

To je kako kada kažeš da je prosečan beograđanin visok 175.347cm? Koji beograđanin? Možda čak nijedan nema tu visinu, već je to matematičko očekivanje visine slučajno izabranog beograđanina.
[ hotchimney @ 18.02.2014. 17:29 ] @
Napisao si da entropija nije definisana za poruke.

Ali ako poruku definišemo kao "specifična realizacija slučajne promenljive" tada je pitanje kako izračunati entropiju poruke?

Ako podjemo od Shannon-ove definicije i X={"tzzzzzzzzzzzztzztttzttzztzttt"},
P(X=x1)=1
pa je
H(X)=0.
[ Nedeljko @ 19.02.2014. 14:08 ] @
Pa, i dalje mislim da nije definisana za poruke, a promeniću mišljenje kada mi neko nađe definiciju entropije poruke, tj. formulu.

Tamo se pod "porukom" smatra specifična realizacija slučajne promenljive, što može da bude npr. uređaj koji emituje poruke, što je opet slučajna promenljia, tj. njena prakična realizacija (buući da je slučajna promenljiva apstraktan matematički pojam), a ne konkretan niz znakova koji smo dobili kao izlaz uređaja. Taj uređaj je nešto što može da emituje nekakve poruke sa određenom verovatnoćom.

Tamo nigde nije data nijedna formula pomoću koje mogu da izračunam entropiju konkretnog niza simbola, već samo formula pomoću koje mogu da izračunam entropiju slučajne promenljive.
[ hotchimney @ 20.02.2014. 00:27 ] @
http://demonstrations.wolfram....fAMessageUsingRandomVariables/
[ Nedeljko @ 20.02.2014. 08:51 ] @
Dakle, ako se alfabet sastoji od simbola , pri čemu se simbol javlja sa verovatnoćom , gde je naravno i , onda je

.

Dakle, ako imamo slova i sva se jednako verovatno pojavljuju, onda je entropija bilo koje poruke dužine iznosi , a ako je pritom i , onda je entropija takve poruke .
[ hotchimney @ 20.02.2014. 11:35 ] @
Uz napomenu, ako nisu poznate verovatnoće, mogu se koristiti relativne frekvencije simbola u poruci.
[ atomant @ 20.02.2014. 14:37 ] @
Evo vam kratka simulacija u Matlabu:

Code:
simboli = ['t','z'];

MAX_DUZINA_NIZA = 50;
BROJ_ITERACIJA = 10000;
BROJ_SIMBOLA = length(simboli);

P=zeros(BROJ_ITERACIJA,BROJ_SIMBOLA);
H=zeros(1,BROJ_ITERACIJA); poruke=[];

for i=1:BROJ_ITERACIJA
    indeksi = randi(numel(simboli),[1 MAX_DUZINA_NIZA]);
    niz_simb = simboli(indeksi);
    poruke = [poruke; niz_simb];
    for j=1:BROJ_SIMBOLA
        P(i,j)= length(niz_simb(niz_simb==simboli(j))) / MAX_DUZINA_NIZA;
        H(i) = H(i) + (-P(i,j)*log2(P(i,j)));
    end
end

figure;
plot(P(:,1),H,'b.');
xlabel('p(z)'); ylabel('H');

figure;
hist(H,20);



Broj simbola se moze menjati, recimo moze se dodati 'k' ili nekoliko simbola. U promenljivoj poruke se cuvaju sve nasumicno generisane poruke.
Ko ima zivaca moze da se igra sa brojem iteracija.


A sto se tice pitanja, ostajem pri onome sto sam vec rekao. Entropija za one tri sekvence je ista, jer nemamo verovatnocu pojavljivanja simbola unapred utvrdjenu na osnovu nekih posmatranja pa onda racunamo na osnovu frekvencije simbola u poruci. Ako je ona ista, onda je entropija svake od te tri poruke jednaka.

Poredjenje sa slikom ne stoji, posto se kod slike vrsi kompresija u odnosu na 4 ili 8-susedstvo piksela pa tamo gde su svi crni moze da se uradi kompresija (isti slucaj kad su svi beli). Kada bismo znali da postoji ogranicen skup poruka koji se prenose onda bi broj bita potreban za prenos bio daleko manji, ali posto je svaka sekvenca jednako verovatna, onda nema kompresije. Eventualno bi moglo da se prica o kompresiji ako se simbol t zameni 0 a simbol z jedinicom (lakse je preneti 0 i 1 nego kodirati t i z bilo kojim drugim nacinom kodovanja).
[ MajorFatal @ 20.03.2014. 04:59 ] @
Da ne bude da nisam odgovorio:

Citat:
atomant:

Ako te zanima kodiranje signala na osnovu entropije, pogledaj clanak na wikipediji o Hafmanovom kodu za kompresiju podataka bez gubitaka (JPEG i MPEG formati slike i videa koriste ovu vrstu kompresije, doduse rezultujuci video i slika imaju neke gubitke u informacijama ali one ne poticu od Hafmanovog koda vec od drugih koraka u kompresiji). PNG i GIF su looseless kompresije.

http://en.wikipedia.org/wiki/Huffman_coding


Uglavnom sta me zanima to i pitam. Tako da me zanimalo "kodiranje signala na osnovu
entropije" sigurno bih to i pitao. Hvala u svakom slucaju za sugestiju, verujem da je
iz najbolje namere, cituckao sam ja to i ranije, ali: ne vidim poentu?

I.) Iako na pocetku teksta zaista stoji da je Hafmanov kod "entropy encoding
algorithm":

In computer science and information theory, Huffman coding is an entropy encoding
algorithm used for lossless data compression.

ako pogledam kako se podaci koduju uz pomoc Hafmanovog koda tj. kako se gradi "Hafman tree"

1.)Create a leaf node for each symbol and add it to the priority queue.
2.)While there is more than one node in the queue:
- 1.)Remove the two nodes of highest priority (lowest probability) from the queue
- 2.)Create a new internal node with these two nodes as children and with probability
- equal to the sum of the two nodes' probabilities.
- 3.)Add the new node to the queue.
3.)The remaining node is the root node and the tree is complete.

nigde ne vidim entropiju kao meru ??? Da se primenjuje ili na bilo koji nacin ucestvuje?
Na osnovu broja pojavljivanja nekog simbola u poruci (ili predvidjenog broja pojavljivanja)
odredjuje se njegova verovatnoca, na osnovu verovatnoca pojavljivanja simbola odredjuju se
kodovi kojim ce ti simboli biti kodovani. Gde je tu entropija da bi kodovanje bilo
"na osnovu entropije"?

II.) Za primer koji sam naveo:

"zttttttttttttttztzztztttz"

izracunate su verovatnoce pojavljivanja simbola 'z' i 't':

p('z')=0.24 p('t')=0.76

In fact, a Huffman code corresponds closely to an arithmetic code where each of the
frequencies is rounded to a nearby power of ½ — for this reason Huffman deals relatively
poorly with distributions where symbols have frequencies far from a power of ½, such as
0.75 or 0.375. This includes most distributions where there are either a small numbers
of symbols (such as just the bits 0 and 1) or where one or two symbols dominate the rest.

III.)
Dosta ljudi je vec primetilo da se binarni signal koji se sastoji od z i t moze u
potpunosti zameniti nizom nula i jedinica sa istim rasporedom kao z i t. Te tako ulozivsi
neke resurse tek toliko da napravimo tabelu z=0, t=1 ili z=1, t=0 vec prema tome ko koje
slovo ili broj vise voli umesto pocetnog niza imacemo

"0111111111111110100101110" ili "1000000000000001011010001" gde ce p(0)=0.24, p(1)=0.76
(ili p(1)=0.24, p(0)=0.76):


For an alphabet {0, 1} with probabilities 0.625 and 0.375, Huffman encoding treats them
as though they had 0.5 probability each, assigning 1 bit to each value, which does not
achieve any compression over naive block encoding.

To jest niz 0011101... ce zameniti tim istim nizom 0011101...itd?

Mada ja mislim da bi i recenica:

"For an alphabet {z, t} with probabilities 0.625 and 0.375, Huffman encoding treats them
as though they had 0.5 probability each, assigning 1 bit to each value, which does not
achieve any compression over naive block encoding"

takodje bila tacna.

Prethodna 2 citata su preuzeta sa stranice:

http://en.wikipedia.org/wiki/Arithmetic_coding

Zasto bi onda trebalo da me zanima Hafmanovo kodiranje "za kompresiju podataka bez
gubitaka na osnovu entropije"?
[ MajorFatal @ 28.03.2014. 02:05 ] @
Recimo da imam neki niz od 1000 bita 0 i 1, N= 1000 duzina niza, i recimo da sam utvrdio za taj niz da je entropija H = 0.694, da li to znaci da pocetni niz od 1000 bita mogu da kompresujem najvise do 694 bita, ili do velicine od 306 bita (1000 - 694 = 306) ili do N1 = HPiSinCosLogCtg (N) bita? Kako se to odredjuje, tj. kako entropija "oblikuje" teoretski minimum sa kojim pocetni niz od 1000 bita moze da se opise?

Ili, recimo da imam neki niz od 1000 bita 0 i 1, N= 1000 duzina niza, i recimo da sam utvrdio za taj niz da je entropija H = 18, da li to znaci da pocetni niz od 1000 bita mogu da kompresujem najvise do 18 puta, ili da ga skratim za najvise 18 bita, ili na 18 bita ili...

Ili je recenica:

"Svaki signal (konacni niz karaktera da se ogranicimo) ima jednu vrednost koja se zove entropija, i koja oblikuje teoretski minimum sa kojim ta ista informacija moze da se opise."

bleskasta?

[Ovu poruku je menjao MajorFatal dana 28.03.2014. u 03:33 GMT+1]
[ MajorFatal @ 26.04.2014. 03:21 ] @
Dok ne nateram sebe da jos po nesto napisem:

Citat:
atomant:
Kada bismo znali da postoji ogranicen skup poruka koji se prenose onda bi broj bita potreban za prenos bio daleko manji, ali posto je svaka sekvenca jednako verovatna, onda nema kompresije.


A sta ako znamo "da postoji ogranicen skup poruka koji se prenose" ali je svaka sekvenca od tih koje se prenose i dalje jednako verovatna? Da li tad ima ili nema kompresije po tvom misljenju?
[ Nedeljko @ 26.04.2014. 14:57 ] @
Ako je broj mogućih poruka manji od 2n, ali ne i od 2n-1, onda ti je dovoljno n bitova, bez obzira na to kakve su poruke.
[ MajorFatal @ 06.05.2014. 02:57 ] @
Samo sam hteo da skrenem paznju coveku da ima dva kriterijuma: "ogranicenost broja poruka" i "jednakost verovatnoca sekvenci" u istoj recenici, pa ne moze bas lepo da se razluci kad je "broj bita za prenos daleko manji" a kada "nema kompresije".

A pitanje moze da ostane isto:

Citat:
Nedeljko: Ako je broj mogućih poruka manji od 2n, ali ne i od 2n-1, onda ti je dovoljno n bitova, bez obzira na to kakve su poruke.
... i ako su verovatnoce tih poruka na nekom duzem nizu bita jednake, ima li kompresije ili nema?
[ MajorFatal @ 17.12.2020. 21:39 ] @
Da li neko može da odgovori na sledeće pitanje: Recimo da imam na raspolaganju alfabet od nekih 16 slova: Q, W, E, R, T, Z, A, S, D, F, G, H, i da je svako od tih slova kodovano sa po 8 bita, tj. jedan bajt. Recimo da je sa tih 16 slova ispisana neka duža random (sa slučajnim rasporedom slova) poruka na primer dužine 1 megabajt, ali da su frekvencije pojavljivanja svih tih slova iste, šta će recimo zip algoritam da uradi sa takvim fajlom od 1 Mb, za koliko će uspeti da ga skrati?

Ja recimo znam da 16 slova može da se koduje sa po 4 bita, tako bi prostim blok kodovanjem ali biranjem 4 bita za svako slovo, umesto po 8 bita, fajl od 1 Mb mogao da se prepolovi. Da li će zip algoritam da bude uspešniji nad takvim fajlom i za koliko?

Ovo bi odgovaralo situaciji: "atomant:
Kada bismo znali da postoji ogranicen skup poruka koji se prenose onda bi broj bita potreban za prenos bio daleko manji, ali posto je svaka sekvenca jednako verovatna, onda nema kompresije."

Postoji ograničen skup poruka koje se prenose, jer poruka dužine 8 bita ima 256 različitih, a u celom fajlu se koriste samo 16 njih, a svaka sekvenca od 8 bita je jednako verovatna jer su im svima frekvencije (i broj) pojavljivanja u poruci od 1 Mb jednake?

Da ne pitam kolika je entropija takvog fajla, ali šta će zip algoritam da uradi nad takvim podacima, jer on pravi one svoje tabele u koje upisuje i kombinacije od po dva slova, i po tri itd ... ?
[ MajorFatal @ 20.12.2020. 23:42 ] @
Znam da pitanje nije strogo iz matematike, ali baš niko nema odgovor?

Fajl od 1 Mb ako ima zastupljenih svih 256 različitih reči dužine bajt, istih frekvencija, u random rasporedu, nije kompesabilan, ali isto tako i fajl od 1 Mb u kojem je samo 16 reči od mogućih 256, istih frekvencija, u random rasporedu isto nije kompresibilan ni po kakvom znanom metodu?
[ MajorFatal @ 25.12.2020. 01:36 ] @
Citat:
Nedeljko:
Dakle, ako imamo slova i sva se jednako verovatno pojavljuju, onda je entropija bilo koje poruke dužine iznosi , a ako je pritom i , onda je entropija takve poruke .


Pokušao bih ovo da iskoristim bar da uporedim ova dva fajla po količini, nivou entropije, ali sam izgleda nešto zeznuo, recimo da su oba fajla po milion bajta, ispada da ako u prvom ima svih 256 različitih kodnih reči dužine osam, da je entropija oko 31.000, a ako ima samo 16 različitih kodnih reči dužine osam (1 bajt) u fajlu dužine milion bajta ispada da je entropija takvog fajla 250.000???

Šta li sam zeznuo...

https://www.wolframalpha.com/input/?i=%281000000+*+log2%28256%29%29%2F256

https://www.wolframalpha.com/input/?i=%281000000+*+log2%2816%29%29%2F16

Ne znam ni ovi linkovi kako da se nateraju da rade..
[ MajorFatal @ 03.01.2021. 16:15 ] @
Citat:
Nedeljko:
Dakle, ako se alfabet sastoji od simbola , pri čemu se simbol javlja sa verovatnoćom , gde je naravno i , onda je

.

Dakle, ako imamo slova i sva se jednako verovatno pojavljuju, onda je entropija bilo koje poruke dužine iznosi , a ako je pritom i , onda je entropija takve poruke .


Ne bih rekao da entropija bilo koje poruke može da bude određena na način na koji si predložio, u formuli imaš samo m dužinu poruke, i n broj slova koja se jednako verovatno pojavljuju. Formula govori samo o sastavu poruke, dužini, broju slova, verovatnoći pojavljivanja - koja je ista za sva slova ... ali ništa o rasporedu tih slova, koji mislim da je bitan za ovu temu, ako je nivo entropije obrnuto proporcionalan kompresibilnosti.

Takva neka poruka može da bude sastavljena od n slova poređanih u rastućem rasporedu po binarnoj vrednosti, ili po opadajućem rasporedu, ili bilo kom unapred definisanom rasporedu, po nekoj formuli, sve takve poruke bile bi kompresibilne. U slučaju da je raspored slova u poruci random, slučajan, takva poruka bi bila teže kompresibilina. Zar ne? A formula koju si predložio to nije u stanju da registruje? Pa ne može da govori o nivou entropije, ili bar ne govori do kraja?