Shannon-Fano-Elias 編碼：原理與 C 語言實現

理論基礎

對離散隨機變量 X={1..m}，概率 p(x)>0。定義累積分布函數 F(x)=Σ_{i≤x} p(i)，修正累積分布函數 F̄(x)=F(x-1)+p(x)/2（即階梯中點）。編碼為 F̄(x) 的二進制小數展開，取前 l(x)=⌈log₂(1/p(x))⌉+1 位。

編碼步驟

1. 輸入概率分佈 p(x)。
2. 計算 F(x) 累積和。
3. 計算 F̄(x) = F(x-1) + p(x)/2（x=1 時 F̄(1)=p(1)/2）。
4. 碼長 l(x) = ceil(log2(1/p(x))) + 1。
5. 將 F̄(x) 轉為二進制小數，取前 l(x) 位作為碼字。

C 語言關鍵結構與函數

#define MAX_SYM 100
#define MAX_CODE_LEN 200 // 須足夠大防越界

typedef struct {
    double px, Fx, Fbax;
    int lx;
    int code[MAX_CODE_LEN];
} SFE;

SFE sym[MAX_SYM];

void calc_Fx() { // 累積分布
    double sum = 0;
    for (int i=1; i<=m; ++i) {
        sum += sym[i].px;
        sym[i].Fx = sum;
    }
}

void calc_Fbax() { // 修正累積
    sym[1].Fbax = sym[1].px / 2.0;
    for (int i=2; i<=m; ++i) {
        double sum = 0;
        for (int j=1; j 1e-12) {
        val *= 2;
        *code = (int)val;
        decimal_to_binary(val - (int)val, code+1);
    }
}

實現陷阱

• 二進制小數可能無限長（如 0.1₁₀），code 數組必須足夠大，或直接只生成前 l(x) 位。
• 浮點精度誤差，判斷終止條件需設閾值（如 1e-12）。
• 碼長公式 +1 保證唯一可解碼（Kraft 不等式）。