✨Bất đẳng thức Fano

Trong lý thuyết thông tin, bất đẳng thức Fano liên hệ lượng thông tin bị mất trên một kênh nhiễu với xác suất phân loại sai. Nó được tìm ra bởi Robert Fano đầu thập niên 1950 khi đang dạy một semina tiến sĩ về lý thuyết thông tin tại MIT, và sau đó được đưa vào cuốn sách năm 1961 của ông.

Nó được dùng để tìm ra một chặn dưới cho xác suất lỗi của bất kì bộ giải mã nào.

Đặt các biến ngẫu nhiên X và Y đại diện cho thông điệp vào và ra (trong số r+1 thông điệp có thể) với xác suất hợp $P(x,y)$. Bất đẳng thức Fano là :$H(X|Y)\backslash leq\; H(e)+P(e)\backslash log(r),$

trong đó :$H\backslash left(X|Y\backslash right)=-\backslash sum\_\{i,j\}\; P(x\_i,y\_j)\backslash log\; P\backslash left(x\_i|y\_j\backslash right)$

là entropy có điều kiện, :$P(e)=P(X\backslash neq\; Y)$

là xác suất lỗi, và :$H(e)=-P(e)\backslash log\; P(e)-(1-P(e))\backslash log(1-P(e))$

là entropy nhị phân tương ứng.