Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Entropija signala?

[es] :: Matematika :: Entropija signala?

Strane: 1 2

[ Pregleda: 12587 | Odgovora: 37 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8578
*.3gnet.mts.telekom.rs.



+2777 Profil

icon Re: Entropija signala?16.02.2014. u 09:24 - pre 103 meseci
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.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

hotchimney

Član broj: 300237
Poruke: 462



+822 Profil

icon Re: Entropija signala?18.02.2014. u 15:06 - pre 103 meseci
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.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8578
*.dynamic.isp.telekom.rs.



+2777 Profil

icon Re: Entropija signala?18.02.2014. u 16:15 - pre 103 meseci
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.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

hotchimney

Član broj: 300237
Poruke: 462



+822 Profil

icon Re: Entropija signala?18.02.2014. u 17:29 - pre 103 meseci
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.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8578
*.ptt.rs.



+2777 Profil

icon Re: Entropija signala?19.02.2014. u 14:08 - pre 103 meseci
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.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

hotchimney

Član broj: 300237
Poruke: 462



+822 Profil

icon Re: Entropija signala?20.02.2014. u 00:27 - pre 103 meseci
http://demonstrations.wolfram....fAMessageUsingRandomVariables/
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8578
*.3gnet.mts.telekom.rs.



+2777 Profil

icon Re: Entropija signala?20.02.2014. u 08:51 - pre 103 meseci
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 .
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

hotchimney

Član broj: 300237
Poruke: 462



+822 Profil

icon Re: Entropija signala?20.02.2014. u 11:35 - pre 103 meseci
Uz napomenu, ako nisu poznate verovatnoće, mogu se koristiti relativne frekvencije simbola u poruci.
 
Odgovor na temu

atomant
Beograd

Član broj: 47540
Poruke: 263
*.dynamic.isp.telekom.rs.



+34 Profil

icon Re: Entropija signala?20.02.2014. u 14:37 - pre 103 meseci
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).
If you can't explain it simply, you don't understand it well enough. A. Einstein
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1231
*.WiMAX.Verat.NET.



+488 Profil

icon Re: Entropija signala?20.03.2014. u 04:59 - pre 102 meseci
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"?

Nemoj da pricas?
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1231
*.WiMAX.Verat.NET.



+488 Profil

icon Re: Entropija signala?28.03.2014. u 02:05 - pre 102 meseci
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]
Nemoj da pricas?
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1231
*.WiMAX.Verat.NET.



+488 Profil

icon Re: Entropija signala?26.04.2014. u 03:21 - pre 101 meseci
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?

Nemoj da pricas?
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8578
*.ptt.rs.



+2777 Profil

icon Re: Entropija signala?26.04.2014. u 14:57 - pre 101 meseci
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.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1231
*.WiMAX.Verat.NET.



+488 Profil

icon Re: Entropija signala?06.05.2014. u 02:57 - pre 100 meseci
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?
Nemoj da pricas?
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1231
87.116.160.*



+488 Profil

icon Re: Entropija signala?17.12.2020. u 21:39 - pre 20 meseci
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 ... ?
Nemoj da pricas?
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1231
87.116.160.*



+488 Profil

icon Re: Entropija signala?20.12.2020. u 23:42 - pre 20 meseci
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?
Nemoj da pricas?
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1231
87.116.160.*



+488 Profil

icon Re: Entropija signala?25.12.2020. u 01:36 - pre 20 meseci
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..

Nemoj da pricas?
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1231
87.116.164.*



+488 Profil

icon Re: Entropija signala?03.01.2021. u 16:15 - pre 19 meseci
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?

Nemoj da pricas?
 
Odgovor na temu

[es] :: Matematika :: Entropija signala?

Strane: 1 2

[ Pregleda: 12587 | Odgovora: 37 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.