Giải thích về entropy shanon

Question

Tôi thường được xem như một lời giải thích cho shanon entropy rằng nó đại diện cho " số lượng trung bình các câu hỏi có / không cần thiết để tìm ra trạng thái mà một hệ thống nhất định đang ở. "

Điều này hoạt động rất tốt đối với một hệ thống có một số trạng thái chẵn có thể xảy ra, nhưng nếu tôi cố gắng làm điều này với giả sử, 3 trạng thái có thể có tất cả đều tương đương thì tôi không thấy điều này là đúng. Thật vậy, bằng cách sử dụng entropy,$ H = \sum_{n = 1}^{3}\frac{1}{3}\log_2(\frac{1}{3}) = 1.58$Tôi tìm thấy một con số trung bình là 1,58 câu hỏi có / không. Nếu tôi mã hóa$1^{st}$trạng thái như 0,$2^{nd}$trạng thái như 1và$3^{rd}$vì 00số bit (câu hỏi) trung bình mà tôi cần mô tả hệ thống là$\frac{4}{3}=1.33$.

Tôi đã mắc lỗi ở đâu đó hay điều đó có nghĩa là lời giải thích này với câu hỏi có / không chỉ là một cách để đơn giản hóa mọi thứ?

Answer 1

Đầu tiên, mã hóa đề xuất của bạn $A\to 0$, $B \to 1$, $C\to 00$đạt được độ dài mã hóa dưới entropy, điều này là không thể.

Vấn đề là mã hóa của bạn thực tế vô dụng, bởi vì nó không "có thể giải mã duy nhất": nếu bạn nhận được $00$ bạn không thể biết liệu đầu vào là $AA$ hoặc là $C$.

Sau đó, bạn cần phải làm một cái gì đó như $A\to 0$, $B \to 10$, $C\to 11$ , có độ dài mã hóa trung bình là $5/3=1.666$ , phía trên entropy ($H=1.585$). Điều này là để được mong đợi.

Và nếu bạn mã hóa từng giá trị riêng biệt, thì, vâng, bạn không thể hoạt động tốt hơn thế. Nhưng bạn có thể mã nhiều giá trị với nhau (mã "phần mở rộng của nguồn") và tiếp cận entropy.

Hãy xem xét ví dụ một nhóm $n=5$các giá trị. Có$3^5=243$các giá trị khớp có thể xảy ra như nhau. Bởi vì$243 < 256 = 2^8$, bạn có thể viết mã này với nhóm với $8$ Câu hỏi có, không.

Do đó, với sơ đồ đơn giản này, bạn cần yêu cầu $8$ câu hỏi để khám phá $5$ giá trị, cung cấp độ dài mã hóa $8/5=1.6$, gần entropy.

Ở trên không phải là tối ưu (xem phần mã hóa Huffman) nhưng bạn có được ý tưởng.

Answer 2

Độ dài mã dự kiến ​​của mã Shannon-Fano là

$ \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.$

Lưu ý rằng ràng buộc có "+1" - điều này phù hợp với tính toán của bạn

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

Lưu ý rằng mã Shannon-Fano không tối ưu, nhưng mã Huffman thì có. Để biết mã Huffman, hãy xem

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