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

編碼步驟

1. 輸入機率分布 p(x)。
2. 計算 CDF F(x) 與修正值 F̄(x)。
3. 計算碼長 l(x) = ceil(log2(1/p(x))) + 1。
4. 將 F̄(x) 轉二進制小數，截取 l(x) 位得到碼字。

C 語言實現關鍵結構

typedef struct {
    double px;     // 機率
    double Fx;     // CDF
    double Fbax;   // 修正 CDF
    int lx;        // 碼長
    int code[MAX]; // 二進制碼字
} SFE;

核心函數

// 1. 計算 CDF
void count_fx(SFE a[], int n) {
    double sum = 0;
    for (int i=1; i<=n; ++i) {
        sum += a[i].px;
        a[i].Fx = sum;
    }
}

// 2. 計算修正 CDF
void count_fbax(SFE a[], int n) {
    double sum = 0;
    for (int i=1; i<=n; ++i) {
        if (i==1) a[i].Fbax = a[i].px / 2.0;
        else {
            for (int j=1; j EPS) {
        m *= 2;
        *code = (int)m;
        decimal(m - (int)m, code+1);
    }
}

void f_binary(SFE a[], int n) {
    for (int i=1; i<=n; ++i)
        decimal(a[i].Fbax, a[i].code);
}

注意事項

• code 陣列需足夠大（建議 ≥ 最大碼長），否則易發生越界——特別是無限循環二進制小數（如 0.1₁₀ = 0.000110011…₂）。
• 實際工程中常只存 l(x) 位，避免無限展開。

實驗結果示例

有限二進制位數範例

無限二進制位數範例（需截斷）

總結

Shannon-Fano-Elias 編碼理論優雅，實現關鍵在精確控制二進制轉換精度與陣列邊界。理解其 CDF 中點取碼原理，有助於深入掌握算術編碼等後續技術。