Interpretasi entropi shanon

Question

Saya sering melihat penjelasan untuk entropi shanon yang mewakili " jumlah rata-rata pertanyaan ya / tidak yang diperlukan untuk mengetahui keadaan sistem tertentu. "

Ini bekerja sangat baik untuk sistem yang memiliki jumlah kemungkinan status genap, tetapi jika saya mencoba melakukan ini dengan katakanlah, 3 kemungkinan status semua peralatan yang dapat saya gunakan, saya tidak menemukan ini benar. Memang, dengan menggunakan entropi,$ H = \sum_{n = 1}^{3}\frac{1}{3}\log_2(\frac{1}{3}) = 1.58$Saya menemukan jumlah rata-rata 1,58 pertanyaan ya / tidak. Jika saya menyandikan file$1^{st}$menyatakan sebagai 0, itu$2^{nd}$menyatakan sebagai 1dan$3^{rd}$sebagai 00, jumlah rata-rata bit (pertanyaan) yang saya butuhkan untuk mengkarakterisasi sistem adalah$\frac{4}{3}=1.33$.

Apakah saya membuat kesalahan di suatu tempat atau apakah itu berarti penjelasan dengan pertanyaan ya / tidak ini hanyalah cara untuk menyederhanakan?

Answer 1

Pertama, pengkodean yang Anda usulkan $A\to 0$, $B \to 1$, $C\to 00$mencapai panjang pengkodean di bawah entropi, yang seharusnya tidak mungkin.

Masalahnya adalah encoding Anda praktis tidak berguna, karena tidak "dapat didekodekan secara unik": jika Anda menerima $00$ Anda tidak dapat mengetahui apakah masukannya $AA$ atau $C$.

Maka Anda perlu melakukan sesuatu seperti $A\to 0$, $B \to 10$, $C\to 11$ , yang memiliki panjang pengkodean rata-rata $5/3=1.666$ , di atas entropi ($H=1.585$). Ini yang diharapkan.

Dan jika Anda mengkodekan setiap nilai yang diisolasi, maka, ya, Anda tidak dapat melakukan lebih baik dari itu. Tapi Anda bisa mengkodekan beberapa nilai bersama-sama (kode "ekstensi sumber"), dan mendekati entropi.

Pertimbangkan misalnya sekelompok $n=5$nilai-nilai. Ada$3^5=243$nilai gabungan yang sama-sama mungkin. Karena$243 < 256 = 2^8$, Anda dapat membuat kode ini dengan grup dengan $8$ pertanyaan ya-tidak.

Karenanya, dengan skema sederhana ini, Anda perlu bertanya $8$ pertanyaan untuk ditemukan $5$ nilai, yang memberikan panjang pengkodean $8/5=1.6$, di dekat entropi.

Di atas tidak optimal (lihat pengkodean Huffman) tetapi Anda mendapatkan ide.

Answer 2

Panjang kode yang diharapkan dari kode Shannon-Fano adalah

$ \mathbb {E} L=\sum _{i=1}^{n}p_{i}l_{i}\leq \sum _{i=1}^{n}p_{i}(-\log _{2}p_{i}+1)=-\sum _{i=1}^{n}p_{i}\log _{2}p_{i}+\sum _{i=1}^{n}p_{i}=H(X)+1.$

Perhatikan bahwa batasan memiliki "+1" - ini sesuai dengan perhitungan Anda

http://en.wikipedia.org/wiki/Shannon%E2%80%93Fano_coding

Perhatikan bahwa kode Shannon-Fano tidak optimal, tetapi kode Huffman optimal. Untuk kode Huffman, lihat

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