Entropija signala?

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.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

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.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

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.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

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 .

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Evo vam kratka simulacija u Matlabu:




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).

Potpis

If you can't explain it simply, you don't understand it well enough. A. Einstein

Da ne bude da nisam odgovorio:



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"?

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?

Dok ne nateram sebe da jos po nesto napisem:



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?

Ako je broj mogućih poruka manji od 2ⁿ, ali ne i od 2^n-1, onda ti je dovoljno n bitova, bez obzira na to kakve su poruke.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

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:

... i ako su verovatnoce tih poruka na nekom duzem nizu bita jednake, ima li kompresije ili nema?

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 ... ?

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?

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/i...00000+*+log2%28256%29%29%2F256

https://www.wolframalpha.com/i...1000000+*+log2%2816%29%29%2F16

Ne znam ni ovi linkovi kako da se nateraju da rade..