精华内容
下载资源
问答
  • 信源编码的代码实现 (c++版)

    香农编码

    (1) 将信源消息符号按其出现的概率大小依次排列 p1 ≥ p2 ≥ … ≥ pn
    (2) 确定满足下列不等式的整数码长Ki为 -log2(pi) ≤ Ki < -log2(pi) + 1
    (3) 为了编成唯一可译码, 计算第i个消息的累加概率
    (4) 将累加概率Pi转换成二进制数。
    (5) 取Pi二进数的小数点后Ki位即为该消息符号的二进制码字。

    在这里插入图片描述

    例如: 当i=4时, 有-log2(0.17) ≤ K4 < -log2(0.17) + 1
    即: 2.56 ≤ K4 < 3.56, 所以K4=3
    累加概率P4=0.57, 变换成二进制位0.1001… 由于K4=3, 所以第4个消息的香农码为100

    #include <iostream>
    #include <vector>
    #include <string>
    #include <algorithm>
    using namespace std;
    
    struct Shannon_struct
    {
        string name;          // 信源符号名称
        double p;             // 符号概率
        double sum_p;         // 累加概率
        int result_length;    // 码字长度
        vector<int> result;   // 香农码
    };
    
    /**
     * 求解香农码
     * 方法: 用计算累加概率sum_p的二进制数的方式,               (注意: 0<=sum_p<1)
     * 求出该二进制数的小数部分, 只取前n位, n代表码字长度        (注意: 忽略前面的0和小数点)
     */
    void shannonCodeing(Shannon_struct* s)
    {
        int num = 0;
        double temp = s->sum_p;   // 用temp来暂存累加概率, 防止直接修改s->sum_p的值
        for (int i = 0; i < s->result_length; i++)
        {
            temp = temp * 2;  // 乘二取整
            if (temp >= 1)
            {
                num = 1;
                temp = temp - 1;
            }
            else
            {
                num = 0;
            }
            s->result.push_back(num);
        }
    }
    
    /**
     * 自定义结构体比较函数
     * 按照符号概率p由大到小进行排序
     */
    bool cmp(Shannon_struct a, Shannon_struct b)
    {
        return a.p > b.p;
    }
    
    int main()
    {
        int symbol_num = 0; // 符号的总数
        cout << "请输入一共有多少个信源符号: ";
        cin >> symbol_num;
        Shannon_struct* s = new Shannon_struct[symbol_num];
    
        cout << "请输入信源符号(字符型)和对应的概率: " << endl;
        for (int i = 0; i < symbol_num; i++)
        {
            cin >> s[i].name >> s[i].p;
        }
    
        // 将信源符号按照其出现的概率p由大到小进行排序 
        sort(s, s + symbol_num, cmp);
    
        for (int i = 0; i < symbol_num; i++)
        {
            if (i == 0)
            {
                s[i].sum_p = 0;
            }
            else
            {
                s[i].sum_p = s[i - 1].p + s[i - 1].sum_p;
            }
            //cout << -1 * log2(s[i].p) << endl;
            s[i].result_length = (int)ceil(-1 * log2(s[i].p)); // log2表示以2为底的对数
            shannonCodeing(&s[i]);    // 求出对应的香农码
        }
    
        // 输出部分
        cout << "\n\n信源符号 概率 累加概率 码字长度 香农码" << endl;
        for (int i = 0; i < symbol_num; i++)
        {
            cout << "  " << s[i].name << "\t " << s[i].p << "\t " << s[i].sum_p << "  \t  " << s[i].result_length << "\t";
            for (int j = 0; j < s[i].result.size(); j++)
            {
                cout << s[i].result[j];
            }
            cout << endl;
        }
    
        delete[] s;
        return 0;
    }
    
    /*
    测试数据:
    7
    a7 0.01
    a2 0.19
    a4 0.17
    a5 0.15
    a1 0.20
    a6 0.10
    a3 0.18
    
    输出结果:
    信源符号 概率 累加概率 码字长度 香农码
      a1     0.2     0        3     000
      a2     0.19    0.2      3     001
      a3     0.18    0.39     3     011
      a4     0.17    0.57     3     100
      a5     0.15    0.74     3     101
      a6     0.1     0.89     4     1110
      a7     0.01    0.99     7     1111110
    */
    

    费诺编码

    (1) 将信源消息符号按其出现的概率大小依次排列: p1 ≥ p2 ≥ … ≥ pn
    (2) 将依次排列的信源符号按概率值分为两大组, 使两个组的概率之和近于相同, 并对各组赋予一个二进制符号“0”和“1”。
    (3) 将每一大组的信源符号进一步再分成两组, 使划分后的两个组的概率之和近似相同, 并对各组赋予一个二进制符号“0”和“1”。
    (4) 如此重复, 直至每个组只剩下一个信源符号为止。
    (5) 信源符号所对应的码字即为费诺码。

    在这里插入图片描述

    #include <iostream>
    #include <vector>
    #include <string>
    #include <algorithm>
    using namespace std;
    
    struct Fano_struct
    {
        string name;          // 信源符号名称
        double p;             // 符号概率
        int result_length;    // 码字长度
        vector<int> result;   // 费诺编码
    };
    
    /**
     * 计算结构体数组s在[start, end)之间的中点下标
     * 返回值: 中点mid
     */
    int calculate_mid(Fano_struct* s, int start, int end)
    {
        int i = start;
        int j = end;
        double part1 = s[start].p;
        double part2 = s[end].p;
        while (i < j - 1)     // 当i与j相差2时, 停止循环, 注意不能是i<j, 因为这样循环结束后, i==j
        {
            if (part1 > part2)
            {
                j--;
                part2 = part2 + s[j].p;
            }
            else
            {
                i++;
                part1 = part1 + s[i].p;
            }
            //cout << part1 << " " << part2 << " " << i << " " << j << endl;
        }
        return j;
    }
    
    /**
     * 分组赋值:
     * 将依次排列的信源符号按概率分成两组, 使这两个组的概率之和近似相同, 分别赋予一个二进制码0和1,
     * 持续分组并赋值, 直到每个组只剩下最后一个信源符号为止。
     * start和end是待赋值的起点和终点下标
     * mid是calculate_mid()计算得到的中点下标
     * 将费诺码往后添加一个0或1
     * 即: s[i].result.push_back(0或1)
     */
    void groupAssign(Fano_struct* s, int start, int end)
    {
        if (end - start < 1)
        {
            return; // 递归终止条件, 当起点和终点相邻时, 此时不需要再分组了
        }
    
        int mid = calculate_mid(s, start, end);    // 求中点的下标
        for (int i = start; i < mid; i++)
        {
            s[i].result.push_back(0);     // 向前一组的费诺码往后添加一个0
        }
        for (int i = mid; i <= end; i++)
        {
            s[i].result.push_back(1);     // 向后一组的费诺码往后添加一个0
        }
    
        groupAssign(s, start, mid - 1);
        groupAssign(s, mid, end);
    }
    
    /**
     * 已知费诺码, 计算码长
     */
    void calculate_length(Fano_struct* s, int symbol_num)
    {
        for (int i = 0; i < symbol_num; i++)
        {
            s[i].result_length = s[i].result.size();
        }
    }
    
    /**
     * 自定义结构体比较函数
     * 按照符号概率p由大到小进行排序
     */
    bool cmp(Fano_struct a, Fano_struct b)
    {
        return a.p > b.p;
    }
    
    int main()
    {
        int symbol_num = 0; // 符号的总数
        cout << "请输入一共有多少个信源符号: ";
        cin >> symbol_num;
        Fano_struct* s = new Fano_struct[symbol_num];
    
        cout << "请输入信源符号(字符型)和对应的概率: " << endl;
        for (int i = 0; i < symbol_num; i++)
        {
            cin >> s[i].name >> s[i].p;
        }
    
        // 将信源符号按照其出现的概率p由大到小进行排序 
        sort(s, s + symbol_num, cmp);
    
        // 计算费诺码
        groupAssign(s, 0, symbol_num - 1);
    
        // 计算每个信源符号的码长
        calculate_length(s, symbol_num);
    
        // 输出部分
        cout << "\n信源符号 概率 码字长度 费诺编码" << endl;
        for (int i = 0; i < symbol_num; i++)
        {
            cout << "  " << s[i].name << "\t " << s[i].p << "  \t  " << s[i].result_length << "\t";
            for (unsigned int j = 0; j < s[i].result.size(); j++)
            {
                cout << s[i].result[j];
            }
            cout << endl;
        }
    
        delete[] s;
        return 0;
    }
    
    /*
    测试数据:
    7
    a7 0.01
    a2 0.19
    a4 0.17
    a5 0.15
    a1 0.20
    a6 0.10
    a3 0.18
    
    输出结果:
    信源符号 概率 码字长度 费诺编码
      a1     0.2      2     00
      a2     0.19     3     010
      a3     0.18     3     011
      a4     0.17     2     10
      a5     0.15     3     110
      a6     0.1      4     1110
      a7     0.01     4     1111
    */
    

    哈夫曼编码

    • 注意: 哈夫曼编码方法得到的码并非唯一的
      每次对信源缩减时, 赋予信源最后两个概率最小的符号, 用0和1都是可以的, 所以会得到不同的哈夫曼码, 但不会影响码字的长度。
    • 另外, 在下面提供的这两个代码中, 可以把sort()函数删去(目的仅仅是为了输出时按照概率进行排序),则程序也是没有问题的, 因为在selectMin()函数每次就找到了数组中最小和次小的两个元素, 进而合并成一棵子树。

    C++版

    #include <iostream>
    #include <iomanip>
    #include <string>
    #include <algorithm>
    using namespace std;
    
    struct HTNode
    {
        string name;
        double p;      // 概率❗
        int lchild;    
        int rchild;  
        int parent;  
    };
    
    /**
     * 在huffTree数组中找到parent为-1的最小和次小的两个元素, 并将其下标存入s1和s2
     */
    void selectMin(HTNode huffTree[], int k, int& s1, int& s2)
    {
        // 1.查找最小元素的下标s1
        for (int i = 0; i < k; i++)
        {
            if (huffTree[i].parent == -1)
            {
                s1 = i; 
                break;
            }
        }
        for (int i = 0; i < k; i++)
        {
            if (huffTree[i].parent == -1 && huffTree[s1].p > huffTree[i].p)
            {
                s1 = i;
            }
        }
    
        // 2.查找次小元素的下标s2
        for (int j = 0; j < k; j++)
        {
            if (huffTree[j].parent == -1 && j != s1)
            {
                s2 = j; 
                break;
            }
        }
        for (int j = 0; j < k; j++)
        {
            if (huffTree[j].parent == -1 && huffTree[s2].p > huffTree[j].p && j != s1)
            {
                s2 = j;
            }
        }
    }
    
    /**
     * 创建哈夫曼树 
     */
    void HuffmanTree(HTNode huffTree[], int n)
    {
        // 初始化所有元素的双亲、左右孩子都置为-1;
        for (int i = 0; i < 2 * n - 1; i++)
        {
            huffTree[i].parent = -1;
            huffTree[i].lchild = -1;
            huffTree[i].rchild = -1;
        }
        // 构建哈夫曼树
        for (int k = n; k < 2 * n - 1; k++)
        {
            int i1, i2;
            selectMin(huffTree, k, i1, i2); // 找到parent为-1的最小和次小的两个元素, 并将其下标存入i1、i2
            huffTree[k].p = huffTree[i1].p + huffTree[i2].p;
            huffTree[i1].parent = k;
            huffTree[i2].parent = k;
            huffTree[k].lchild = i1;
            huffTree[k].rchild = i2;
        }
    }
    
    /**
     * 打印哈夫曼数组
     */
    void printHuffmanArray(HTNode huffTree[], int n)
    {
        cout << "\n打印构造好的哈夫曼数组的内容: " << endl;
        cout << "weight parent lchild rchild " << endl;
        cout << left;    // 左对齐输出
        for (int i = 0; i < 2 * n - 1; i++)
        {
            cout << setw(6) << huffTree[i].p << " ";
            cout << setw(6) << huffTree[i].parent << " ";
            cout << setw(6) << huffTree[i].lchild << " ";
            cout << setw(6) << huffTree[i].rchild << endl;
        }
    }
    
    /**
     * 从叶子到根逆向求每个字符的哈夫曼编码
     */
    void huffmanCoding(HTNode huffTree[], char* huffCode[], int n)
    {
        char* temp = new char[n]; // 储存临时产生的编码串
        temp[n - 1] = '\0';
    
        // 遍历输入的n个信源符号, 生成它们对应的哈夫曼编码
        for (int i = 0; i < n; i++)
        {
            int start = n - 1; // 用来控制temp数组的下标, 先让start为数组末尾, 再从后往前移动
            int pos = i;                      
            int parent = huffTree[pos].parent;
    
            while (parent != -1)
            {
                if (huffTree[parent].lchild == pos)
                {
                    temp[--start] = '0'; // 左子树的编码为0
                }
                else
                {
                    temp[--start] = '1'; // 右子树的编码为1
                }
                pos = parent;                    
                parent = huffTree[parent].parent; 
            }
    
            huffCode[i] = new char[n - start]; 
            strcpy(huffCode[i], &temp[start]);
        }
        delete[] temp; // 释放工作空间
    }
    
    /**
     * 自定义结构体比较函数
     * 按照符号概率p由大到小进行排序
     */
    bool cmp(HTNode a, HTNode b)
    {
        return a.p > b.p;
    }
    
    int main()
    {
        int num = 0; // 符号的总数
        cout << "请输入一共有多少个信源符号: ";
        cin >> num;
    
        HTNode* huffTree = new HTNode[2 * num - 1];
    
        cout << "请输入信源符号和对应的概率: " << endl;
        for (int i = 0; i < num; i++)
        {
            cin >> huffTree[i].name >> huffTree[i].p;
        }
    
        // 将信源符号按照其出现的概率p由大到小进行排序 
        sort(huffTree, huffTree + num, cmp);
    
        // 创建哈夫曼树
        HuffmanTree(huffTree, num);
    
        // 打印哈夫曼数组
        printHuffmanArray(huffTree, num);
    
        // 进行哈夫曼编码
        cout << "\n输出哈夫曼编码: " << endl;
        char** huffCode = new char* [num];          
        huffmanCoding(huffTree, huffCode, num);
    
        cout << "信源符号 概率 哈夫曼编码 码字长度" << endl;
        cout << left;
        for (int i = 0; i < num; i++)
        {
            cout << "  ";
            cout << setw(7) << huffTree[i].name << " ";
            cout << setw(7) << huffTree[i].p << " ";
            cout << setw(7) << huffCode[i] << " ";
            cout << setw(7) << strlen(huffCode[i]) << endl;
        }
    
        delete[] huffTree;
        for (int i = 0; i < num; i++)
        {
            delete[] huffCode[i];
        }
        delete[] huffCode;
        return 0;
    }
    
    /*
    测试数据:
    7
    a7 0.01
    a2 0.19
    a4 0.17
    a5 0.15
    a1 0.20
    a6 0.10
    a3 0.18
    */
    

    在这里插入图片描述

    C语言版

    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #define MAX_SIZE 100
    
    struct HTNode
    {
        char name[MAX_SIZE];
        double p;      // 概率
        int lchild;
        int rchild;
        int parent;
    };
    
    /**
     * 在huffTree数组中找到parent为-1的最小和次小的两个元素, 并将其下标存入s1和s2
     */
    void selectMin(HTNode huffTree[], int k, int* s1, int* s2)
    {
        // 1.查找最小元素的下标s1
        for (int i = 0; i < k; i++)
        {
            if (huffTree[i].parent == -1)
            {
                *s1 = i;
                break;
            }
        }
        for (int i = 0; i < k; i++)
        {
            if (huffTree[i].parent == -1 && huffTree[*s1].p > huffTree[i].p)
            {
                *s1 = i;
            }
        }
    
        // 2.查找次小元素的下标s2
        for (int j = 0; j < k; j++)
        {
            if (huffTree[j].parent == -1 && j != *s1)
            {
                *s2 = j;
                break;
            }
        }
        for (int j = 0; j < k; j++)
        {
            if (huffTree[j].parent == -1 && huffTree[*s2].p > huffTree[j].p && j != *s1)
            {
                *s2 = j;
            }
        }
    }
    
    /**
     * 创建哈夫曼树
     */
    void HuffmanTree(HTNode huffTree[], int n)
    {
        // 初始化所有元素的双亲、左右孩子都置为-1;
        for (int i = 0; i < 2 * n - 1; i++)
        {
            huffTree[i].parent = -1;
            huffTree[i].lchild = -1;
            huffTree[i].rchild = -1;
        }
        // 构建哈夫曼树
        for (int k = n; k < 2 * n - 1; k++)
        {
            int i1, i2;
            selectMin(huffTree, k, &i1, &i2); // 找到parent为-1的最小和次小的两个元素, 并将其下标存入i1、i2
            huffTree[k].p = huffTree[i1].p + huffTree[i2].p;
            huffTree[i1].parent = k;
            huffTree[i2].parent = k;
            huffTree[k].lchild = i1;
            huffTree[k].rchild = i2;
        }
    }
    
    /**
     * 打印哈夫曼数组
     */
    void printHuffmanArray(HTNode huffTree[], int n)
    {
        printf("\n打印构造好的哈夫曼数组的内容: \n");
        printf("weight parent lchild rchild \n");
        for (int i = 0; i < 2 * n - 1; i++)
        {
            printf("%6.2f ", huffTree[i].p);
            printf("%6d ", huffTree[i].parent);
            printf("%6d ", huffTree[i].lchild);
            printf("%6d\n", huffTree[i].rchild);
        }
    }
    
    /**
     * 从叶子到根逆向求每个字符的哈夫曼编码
     */
    void huffmanCoding(HTNode huffTree[], char* huffCode[], int n)
    {
        char temp[MAX_SIZE]; // 储存临时产生的编码串
        temp[n - 1] = '\0';
    
        // 遍历输入的n个信源符号, 生成它们对应的哈夫曼编码
        for (int i = 0; i < n; i++)
        {
            int start = n - 1; // 用来控制temp数组的下标, 先让start为数组末尾, 再从后往前移动
            int pos = i;
            int parent = huffTree[pos].parent;
    
            while (parent != -1)
            {
                if (huffTree[parent].lchild == pos)
                {
                    temp[--start] = '0';
                }
                else
                {
                    temp[--start] = '1';
                }
                pos = parent;
                parent = huffTree[parent].parent;
            }
    
            // huffCode[i] = new char[n - start];
            huffCode[i] = (char*)malloc((n - start) * sizeof(char));
            strcpy(huffCode[i], &temp[start]);
        }
    }
    
    
    /**
     * 将信源符号按照其出现的概率p由大到小进行排序 
     */
    void sort(HTNode huffTree[], int symbol_num)
    {
        for (int i = 0; i < symbol_num; i++)
        {
            for (int j = 0; j < symbol_num - i - 1; j++)
            {
                if (huffTree[j].p < huffTree[j + 1].p)
                {
                    // 交换两个结构体的顺序:
    //                 char name[MAX_SIZE];
    //                 double p;     
    //                 int lchild;   (因为后面的这些还没有输入, 所以可以不交换)
    //                 int rchild;
    //                 int parent;
                    char tempName[MAX_SIZE];
                    strcpy(tempName, huffTree[j].name);
                    strcpy(huffTree[j].name, huffTree[j + 1].name);
                    strcpy(huffTree[j + 1].name, tempName);
    
                    double tempP = huffTree[j].p;
                    huffTree[j].p = huffTree[j + 1].p;
                    huffTree[j + 1].p = tempP;
                }
            }
        }
    }
    
    
    int main()
    {
        int num = 0; // 符号的总数
        printf("请输入一共有多少个信源符号: ");
        scanf("%d", &num);
    
        HTNode huffTree[MAX_SIZE * 2 - 1];
    
        printf("请输入信源符号和对应的概率: ");
        for (int i = 0; i < num; i++)
        {
            getchar();
            scanf("%s %lf", &huffTree[i].name, &huffTree[i].p);
        }
    
        // 将信源符号按照其出现的概率p由大到小进行排序
        sort(huffTree, num);
    
        // 创建哈夫曼树
        HuffmanTree(huffTree, num);
    
        // 打印哈夫曼数组
        printHuffmanArray(huffTree, num);
    
        // 进行哈夫曼编码
        printf("\n输出哈夫曼编码: \n");
    
        char* huffCode[MAX_SIZE];
        huffmanCoding(huffTree, huffCode, num);
    
        printf("信源符号 概率 码字长度 哈夫曼编码\n");
        for (int i = 0; i < num; i++)
        {
            printf("  ");
            printf("%s ", huffTree[i].name);
            printf("%7.2f  ", huffTree[i].p);
            printf("  %d   ", strlen(huffCode[i]));
            printf("  %s\n", huffCode[i]);
        }
        return 0;
    }
    
    /*
    测试数据:
    7
    a7 0.01
    a2 0.19
    a4 0.17
    a5 0.15
    a1 0.20
    a6 0.10
    a3 0.18
    */
    
    

    游程编码

    #include <iostream>
    #include <vector>
    #include <string>
    using namespace std;
    
    int main()
    {
        vector<int> vt, result;
        string str;
        cout << "请输入一个二元序列 (只含有0或1)" << endl;
        getline(cin, str);
        for (int i = 0; i < str.length(); i++)
        {
            if (str[i] == '0' || str[i] == '1') // 如果不是0或1, 则跳过
            {
                int num = str[i] - '0';
                vt.push_back(num);
            }
        }
    
        // 将二元序列转换成为游程序列result中
        int value = vt[0];
        int num = 1;
        vt.push_back(-1);  // 加上这个, 可以方便的处理最后一个数字...
        for (int i = 1; i < vt.size(); i++)
        {
            if (vt[i] == value)
            {
                num++;
            }
            else
            {
                result.push_back(num);
                num = 1;
                value = vt[i];
            }
        }
    
        // 输出得到的游程序列
        cout << "\n得到的游程序列的结果是: " << endl;
        for (int i = 0; i < result.size(); i++)
        {
            if (result[i] > 0 && result[i] < 10)
            {
                cout << result[i];
            }
            else
            {
                cout << " " << result[i] << " ";    // 当游程编码超过9后, 输出加上空格
            }
        }
    
        return 0;
    }
    
    
    /*
    测试数据1:
    000101110010001
    输出:
    31132131
    
    测试数据2 (如果游程编码的值>=10, 旁边加个空格):
    1010100110100011111100000000001
    输出:
    11111221136 10 1
    
    测试数据3 (排除0和1以外的数字):
    1010100qdv110100dvcd01111110c000000022001
    输出:
    11111221136 10 1
    */
    

    算术编码

    例: 有四个符号a, b, c, d构成简单序列S=abda, 各符号及其对应概率如下表, 算术编码过程如下:

    在这里插入图片描述


    在这里插入图片描述

    #include <iostream>
    #include <string>
    #include <algorithm>
    #include <sstream>
    using namespace std;
    
    struct symbol_struct
    {
        char name;         // 信源符号名称
        double p;          // 符号概率
        double sum_p;      // 累加概率
    };
    
    /**
     * 十进制小数转二进制小数:
     */
    double doubleToBinary(double num)
    {
        string str = "0.";
        while (num != 1 && str.size() < 18)  // 保留16位小数
        {
            num = num * 2;
            if (num >= 1)
            {
                num = num - 1;
                str.push_back('1');
            }
            else
            {
                str.push_back('0');
            }
        }
    
        // str储存了该二进制数, 用atof函数将其转换成double类型并返回
        return atof(str.c_str());
    }
    
    /**
     * 在symbol_struct中, 寻找字符ch, 并返回其下标
     */
    int findPos(symbol_struct* s, int symbol_num, char ch)
    {
        for (int i = 0; i < symbol_num; i++)
        {
            if (s[i].name == ch)
            {
                return i;
            }
        }
    
        exit(-1); // 查找失败, 直接退出
    }
    
    /**
     * 算术编码
     */
    stringstream arithmetic_coding(symbol_struct* s, string input_str, int symbol_num)
    {
        double start = 0;    // 起始值
        double length = 1;   // 序列长度
    
        for (int i = 0; i < input_str.length(); i++)           // 对于待编码的符号, 
        {
            int pos = findPos(s, symbol_num, input_str[i]);    // 找到该符号在s数组中的下标  (目的: 得到元素概率和累加概率)
            start = start + length * s[pos].sum_p;             // 起始 + 序列长度 * 该元素的累加概率❗
            length = length * s[pos].p;                        // 原序列长度 * 该元素概率❗
            printf("\n第%d个元素: 起始 = %.16lf   ---  序列长度  = %.16lf", i + 1, start, length);
        }
    
        // 循环结束后, 二进制形式的start的的纯小数部分就是所求的算术编码
        stringstream str;
        str.precision(16);
        str << doubleToBinary(start);   // double --> stringstream
    
        return str;
    }
    
    /**
     * 自定义结构体比较函数
     * 按照符号概率p由大到小进行排序
     */
    bool cmp(symbol_struct a, symbol_struct b)
    {
        return a.p > b.p;
    }
    
    int main()
    {
        int symbol_num = 0; // 符号的总数
        cout << "请输入一共有多少个信源符号: ";
        cin >> symbol_num;
        symbol_struct* s = new symbol_struct[symbol_num];
    
        cout << "请输入信源符号(字符型)和对应的概率: " << endl;
        for (int i = 0; i < symbol_num; i++)
        {
            cin >> s[i].name >> s[i].p;
        }
    
        string input_str;
        cout << "请输入由这些符号构成的序列: " << endl;
        getchar();
        getline(cin, input_str);
    
        // 将信源符号按照其出现的概率p由大到小进行排序 
        sort(s, s + symbol_num, cmp);
    
        // 计算累加概率
        for (int i = 0; i < symbol_num; i++)
        {
            if (i == 0)
            {
                s[i].sum_p = 0;
            }
            else
            {
                s[i].sum_p = s[i - 1].p + s[i - 1].sum_p;
            }
        }
    
        stringstream result = arithmetic_coding(s, input_str, symbol_num);
    
        // 输出部分
        cout << "\n\n信源符号 概率  累加概率" << endl;
        for (int i = 0; i < symbol_num; i++)
        {
            cout << "  " << s[i].name << "\t " << s[i].p << "\t " << s[i].sum_p << endl;
        }
        cout << "\n该序列的算术编码的结果为: \n";
        cout << &result.str()[2] << "\n\n" << endl;
    
        delete[] s;
        return 0;
    }
    
    /*
    测试数据:
    4
    a 0.5
    b 0.25
    c 0.125
    d 0.125
    abda
    */
    

    在这里插入图片描述

    展开全文
  • 分布式信源编码算法的理论与实现,关春生,,分布式信源编码的理论基础与工程实践经过了三十年的发展,构成了这个分支的体系结构。本文回顾了分布式信源编码的理论发展,讨论
  • 信源编码的三种方式与实现

    万次阅读 多人点赞 2019-01-15 02:01:21
    信源编码的三种方式与实现一、本文概述二、编码原理1. 哈夫曼编码2. 算术编码3. LZ编码三、算法设计思路1. 哈夫曼编码a. 设置功能结构体和函数b. 压缩文件初始化统计表频度读入文件并统计频度对统计表频度排序建立...

    一、本文概述

    这是第一次在CSDN上写blog,想写很久了,一直因为忙耽搁了,放假了,打算整理一下这学期的一些代码和实验写blog。
    本文主要根据我信息论课程的信源编码大作业报告所写,相关代码放在我的GitHub上,初次在CSDN发blog,小小紧张哈哈哈。

    本文主要实现了哈夫曼编码,且性能较为优秀。另外还拓展实现了LZ编码和算数编码,并在将哈夫曼和LZ-78两种编码方式的cpp文件通过统一的main.cpp文件整合在一起,可以通过运行project来选择希望的编码方式对目标文件进行编码。

    另外,本文的实验中,也出现了一些编译器的问题,例如Visual Studio下和Mac下存在着一定的优劣对比。

    本文中给出了一些实现的部分代码,完整代码见GitHub:
    https://github.com/YZ-WANG/Three-methods-for-source-encoding

    二、编码原理

    本文的实验实现了三种编码方式:哈夫曼编码、LZ编码和算数编码。下面分析其各自基本原理。

    1. 哈夫曼编码

    哈夫曼编码是是一种可变长的分组编码,完全依据各字符出现的概率来构造码字。二进制的哈夫曼编码是基于二叉树的编码思想,所有可能的输入符号在哈夫曼树上对应为一个节点,结点的位置就是该符号的哈夫曼编码。为了构造出唯一可译码,这些节点都是哈夫曼树上的终极结点(即叶子结点),不再延伸,不会出现前缀码。具体编码方法如下:

    1. 将信源消息符号按其出现的概率大小依次排列为 p1≥p2≥…≥Pn;
    2. 取两个概率最小的字母分别配以 0 和 1 两个码元,并将这两个概率相加作为一个新字母的概率,与未分配二进制符号的字母一起重新排队;
    3. 对重排后的两个概率最小符号重复步骤2的过程;
    4. 不断继续上述过程,直到最后两个符号配以 0 和 1 为止;
    5. 从最后一级开始,向前返回得到各个信源符号所对应的码元序列,即为相应码字。

    特别地,有时为了得到最短平均码长,尽量减少赋长码的信源符号,需要在编码前对信源符号作添加,使得信源的符号数量满足 M(N-1)+1,其中M为正整数,N为进制,这样在多次合并后就能充分利用短码,以便降低平均码长。

    此外,哈夫曼编码方法所得到的码并非是唯一的,造成非唯一的原因如下:

    • 每次对信源缩减时,赋予信源最后两个概率最小的符号,用0和1是可以任意的,所以可以得到不同的哈夫曼编码,但不会影响码字的长度。
    • 对信源进行缩减时,两个概率最小的符号合并后的概率与其他信源符号的概率相同时,这两者在缩减信源中进行概率排序,其位置放置次序可以是任意的,故会得到不同的哈夫曼码。此时将影响码字的长度,一般将合并的概率放在上面,这样可以得到较小的码方差。

    哈夫曼编码的特点:

    1. 哈夫曼码的编码方法保证了概率大的符号对应于短码,概率小的符号对应于长码,充分利用了短码;
    2. 而是缩减信源的最后二个码字总是最后一位不同,从而保证了哈夫曼码是即时码。

    哈夫曼码的编码效率是非常高的,它可以单个信源符号编码或用L较小的信源序列编码,对编码器的设计来说也将简单得多。但是应当注意,要达到很高的效率仍然需要按长序列来计算,这样才能使平均码字长度降低。
    哈夫曼编码的解码则在识别出一个个叶子结点后按照叶子结点对应的原信源符号译码。

    哈夫曼编码虽然效率出众,但仍然存在一些分组码所具有但缺点。例如概率特性必须精确测定,以此来编织码表,若略有变化,还需要更换码表。故实际编码过程中需要对原始数据扫描两遍,第一遍用来统计原始数据中各字符出现的概率,创建码表存放起来,第二遍则依据码表在扫描的同时进行编码,才能传输信息。如果将这种编码放在网络通信中,两遍扫描会引起较大的时延;如果用于数据压缩,则会降低速度。因此,出现了自适应哈夫曼编码方法,其码表不是实现构造,而是随着编码的进行,不断动态构造、调整。

    2. 算术编码

    由于在使用分组码对信源单符号进行编码时,没有将符号间的相关性纳入考虑之中:若将m个符号合起来进行编码则会增加设备复杂度,且组间符号的相关性还是无法纳入考虑。这就使得信源编码的匹配原则不能充分满足,编码效率有所损失。

    为了克服这种局限性,一种基于非分组码的编码方法——算数编码应运而生。编码的基本思路是:将需要编码的全部数据看成某一 L L L 长序列,所有可能出现的L长序列的概率映射到 [ 0 , 1 ] [0,1] [0,1] 的区间上,把 [ 0 , 1 ] [0,1] [0,1] 区间分成许多小段,每段长度等于某一序列的概率。再在段内取一个二进制小数用作码字,其长度可与该序列的概率匹配,达到高效率编码的目的。

    算数编码实际的编译码过程比较复杂,但在性能上具有许多优点,特别是所需要的参数很少,不像哈夫曼编码那样需要一个很大的码表。从理论上说,只要已知信源符号集及其符号概率,算数编码的平均码长可以接近符号熵。

    具体编码方法如下:

    1. 将文件以字节为单位读入,并将其分割成bit串形式
    2. 计算文件中bit0和bit1的总数量和各自的概率
    3. 对一定长度L的符号串进行编码,并将数据写入压缩后文件中
    4. 从压缩文件中读入数据,并还原成长度为L的符号串输入至解压文件中

    3. LZ编码

    LZ编码是由以色列研究者齐夫和伦佩尔完全脱离哈夫曼码和算术编码的设计思路,设计出的一系列比哈夫曼编码更有效、比算术编码更快捷的通用压缩算法。将这些算法统称为LZ系列算法。LZ系列算法利用一种巧妙的方式将字典技术应用于通用数据压缩领域,而且,可以从理论上证明LZ系列算法同样可以逼近信息熵的极限。

    实验采用的 LZ-78编码 的编码过程如下:

    • 设信源符号集 A = a 1 , a 2 , … , a K A={a1,a2,…,aK} A=a1,a2,,aK 共K个符号,设输入信源符号序列为 U = ( u 1 , u 2 , … … , u L ) U=(u1,u2,……,uL) U=(u1,u2,,uL),编码是将此序列分成不同的段。
    • 分解是迭代进行的,在第i步,编码器从 s i s_i si - 1 短语后的第一个符号开始向后搜索在此之前从未出现过的最短短语 s i s_i si,将短语 s i s_i si 添入字典第i段。由于 s i s_i si 是此时字典中最短的新短语,所以 s i s_i si 在去掉最后一个符号 x x x 后所得的前缀必定是字典中之前已经出现过的。
    • 若设此前缀是在第 j ( &lt; i ) j(&lt;i) j(<i) 步时出现的,则对 s i s_i si 的编码就可以利用 j j j s i s_i si 最后一位符号 x x x 来表示,即为码字 ( j , x ) (j,x) (j,x)。对于段号 j j j,最多需要 ⌈ l o g i ⌉ \lceil logi \rceil logi bit表示,而符号 x x x 只需 ⌈ l o g K ⌉ \lceil logK \rceil logK bit。若编码猴的字典中短语共有M(U)个,则U序列编码后输出的码流总长度为 ( ⌈ l o g i ⌉ + ⌈ l o g K ⌉ ) (\lceil logi \rceil + \lceil logK \rceil) (logi+logK)

    LZ-78编码的核心实际上就是一个包含了短语、段号、码字、二进制码的字典,如下所示。

    短语段号码字二进制码
    a1(0,a)(0,0)
    b2(0,b)(0,1)
    ba3(2,a)(10,0)
    baa4(3,a)(11,0)

    LZ编码的编码方法非常简捷,译码也很简单,可以一边译码一边建立字典。译码时若收到的码字为 ( j , x ) (j,x) (j,x),则在字典中找到第 j j j 个短语,然后加上符号 x x x 即可译出对应的新短语,并添入字典。因此发送时无需传送字典本身。LZ算法的逻辑简单,硬件实现廉价,运算速度快,在很多计算机数据存储中得到应用。其优点在于能够有效利用信源输出序列的频率、重复性和高使用率的冗余度,是一种自适应算法,只需对信源序列进行一次扫描,无须知道信源的先验统计特性,运算时间正比于序列长度。但也有缺点,一是不能有效地利用位置的冗余度;二是该算法通常在序列起始段压缩效果差一些,随着长度增加效果变好。

    三、算法设计思路

    1. 哈夫曼编码

    a. 设置功能结构体和函数

    为构造哈夫曼树,首先要知道压缩的目标文件中各个字符的频度。因此先对整个文件进行扫描,统计各个字符的频度。在本算法中,考虑到编码方式,将 每个字节对应于一个符号,对于 8 bit 的二进制码,共计 2 8 = 256 2^8=256 28=256 种。故创建一个 结构体 Node,表示符号与对应的频度,用于对其进行统计。

    struct Node
    {
    	unsigned char uch; //一字节的符号
    	unsigned long weight;  //对应的频度
    };
    

    针对哈夫曼树本身,需要对每一个节点进行刻画。创建 结构体 HufNode,其中包含变量:频度 weight、父亲节点 parent、左子节点left_child、右子节点right_child,对应的符号uch,存放其编码的字符数组code。

    struct HufNode
    {
    	unsigned char uch;                      //记录符号
    	unsigned long weight;                   //权重,即频度
    	char * code;                             //存放编码的数组
    	int parent, left_child, right_child;    //定义父节点,左子节点,右子节点
    };
    
    typedef struct HufNode HufNode, * HufTree; //方便后续建树
    

    有了struct HufNode之后,用于构造哈夫曼树的符号就用*HufTree来存储。为256种可能的符号各自构造实例组成指针数组,即Node *tmp_nodes =(Node *)malloc(256*sizeof(Node));。该语句为 存放256种符号的实例的指针数组 在内存开辟了相应的空间。

    实际上,考虑到读入的目标文件实际上在计算机中就是 一长串的二进制码流,我们每次操作的 一字节的符号实际上就是8bit长的二进制码,那么这8bit二进制码其实就对应于十进制的0-255。如此一来,就可以把256种字节用0-255表示,即tmp_nodes[i].uch = (unsigned char)i;,每个节点存储的unsigned char uch实际上就 对应其下标的8位二进制码表示

    实际上没必要在用指针指向对应的节点,只需要存储其对应节点的uch的8位二进制码相应的十进制值,就可以 通过指针数组的索引到达对应节点。在编码构造哈夫曼树时,需要每次在tmp_nodes数组找到目前剩余节点中频度最小的两个节点,将其纳入树中。因此要编写一个函数void Find2Min来完成该功能。该函数实现起来比较简单,主要就是两次for循环遍历未加入哈夫曼树的节点。

    void Find2Min(HufNode * huf_tree, unsigned int n, int * s1, int * s2)
    {
    	unsigned int i;
    	unsigned long min = ULONG_MAX;
    	for(i = 0; i < n; i++)
    		if(huf_tree[i].parent == 0 && huf_tree[i].weight < min)
    		{
    			min = huf_tree[i].weight;
    			* s1 = i;
    		}
    		huf_tree[* s1].parent=1;
    
    	min = ULONG_MAX;//赋值无穷大正数
    	for(i = 0; i < n; i++)
    		if(huf_tree[i].parent == 0 && huf_tree[i].weight < min)
    		{
    			min = huf_tree[i].weight;
    			* s2 = i;
    		}
    }
    

    接着需要写一个构造哈夫曼树的函数。其实该函数思路很简单,循环待操作符号节点个数的次数,并且每次都是在待操作节点中找到频度(也就是权值)最小的两个节点,将其加入树中。于是利用之前的Find2Min(huf_tree, i, &s1, &s2);函数可以很方便地实现。

    //建立哈夫曼树
    //char_sum即出现符号的种类数目;node_num即哈夫曼树的最大节点数目
    void BuildTree(HufNode *huf_tree, unsigned int char_sum, unsigned int node_num)
    {
    	unsigned int i;
    	int s1, s2;
    	for(i = char_sum; i < node_num; i++)
    	{
    		Find2Min(huf_tree, i, &s1, &s2);
    		huf_tree[s1].parent = huf_tree[s2].parent = i;
    		huf_tree[i].left_child = s1;
    		huf_tree[i].right_child = s2;
    		huf_tree[i].weight = huf_tree[s1].weight + huf_tree[s2].weight;
    	}
    }
    

    不难预想到,我们在获得排序完毕的哈夫曼树之后,需要对其进行编码,我们同样出于封装的考虑,写一个函数void HufCode来完成此功能。我们只要调用它,并传入排序成哈夫曼树的完成的*tmp_nodes以及待编码的符号总数即可。最终,会把每个节点的编码结果放入节点的.code变量存放。这里我们对出现的符号种类的节点遍历,分别以这些节点为起点,自下而上检测左右关系来编码,具体实现如下。

    //对完成排序的哈夫曼树进行编码
    void HufCode(HufNode *huf_tree, unsigned char_sum) //char_sum为出现符号种类数
    {
    	//定义略去
    	for(i = 0; i < char_sum; i++)
    	{
    		index = 256-1;
    		for(cur = i, next = huf_tree[i].parent; next != 0;
    			cur = next, next = huf_tree[next].parent)
    			if(huf_tree[next].left_child == cur)
    				code_tmp[--index] = '0';
    			else
    				code_tmp[--index] = '1';
    		huf_tree[i].code = (char * )malloc((256-index) * sizeof(char));
    		strcpy(huf_tree[i].code, &code_tmp[index]);
    	}
    	free(code_tmp);
    }
    

    b. 压缩文件

    初始化统计表频度

    开辟Node *tmp_nodes的256个Node单位的内存空间,用于存储字符频度的统计表。开辟空间后随即进行初始化。

    Node *tmp_nodes =(Node * )malloc(256*sizeof(Node)); //为字符频度统计表分配内存空间
    for(i = 0; i < 256; i++)
    {
      tmp_nodes[i].weight = 0;
      tmp_nodes[i].uch = (unsigned char)i;
    }
    

    读入文件并统计频度

    这里使用C语言中的FILE中的fread函数,从*infile中一字节一字节地读入符号存入(char * )&temp_char中,边读边更新统计表。读完后接下来就对temp_char的这段内存空间里的符号操作即可

    FILE *infile, *outfile;
    unsigned char temp_char; //存储读入的字符
    unsigned long file_len = 0;	//文件字节数
    infile = fopen(ifname, "rb");
    if (infile == NULL)
      return -1;
    fread((char *)&temp_char, 1, 1, infile);
    while(!feof(infile))
    {
      tmp_nodes[temp_char].weight++; //统计表中相应符号频度更新
      file_len++;			//统计文件字节数
      fread((char * )&temp_char, 1, 1, infile);
    }
    fclose(infile);
    

    对统计表频度排序

    这里采用冒泡排序对统计表中的 Node 实例们进行从大到小排序。然后找到第一个频度为0的Node,其索引下标即为出现的符号种类数目。

    for(i = 0; i < 256-1; i++)
        for(j = i+1; j < 256; ++j)
            if(tmp_nodes[i].weight < tmp_nodes[j].weight)
            {
                node_temp = tmp_nodes[i];
                tmp_nodes[i] = tmp_nodes[j];
                tmp_nodes[j] = node_temp;
            }
    for(i = 0; i < 256; i++)
        if(tmp_nodes[i].weight == 0)
            break;
    char_sum = i;
    

    建立哈夫曼树进行编码

    首先给HufNode *类型的huf_tree指针数组开辟空间,共2 * char_sum - 1个节点,并根据统计表对出现的符号的节点进行初始化。

    然后调用

    //初始化树节点
    node_num = 2 * char_sum - 1;
    huf_tree = (HufNode * )malloc(node_num * sizeof(HufNode));
    for(i = 0; i < char_sum; i++)
    {
      huf_tree[i].uch = tmp_nodes[i].uch;
      huf_tree[i].weight = tmp_nodes[i].weight;
      huf_tree[i].parent = 0;			//初始化节点
    }
    free(tmp_nodes);
    //将以上节点全部设置为待加入节点
    for(; i < node_num; i++)
      huf_tree[i].parent = 0;
    
    BuildTree(huf_tree, char_sum, node_num);		//建立哈夫曼树
    HufCode(huf_tree, char_sum);				//对树进行编码
    

    写文件

    首先要写入原始数据的符号种类数目,fwrite((char *)&char_sum, 4, 1, outfile);,因为char_sum是存储为int类型,故占4个字节。然后将哈夫曼编码表写入文件,即.uch.weight变量对。接着写入文件的长度file_len,大小为4字节。

    接下来我们再一次扫描目标文件,这一次每读入一个符号就查表编码。这有一个难点,考虑到哈夫曼编码是变长码,理论上需要按照bit为单位操作;而实际上计算机中变量存储或者文件读写的最小可操作单位都是字节。因此这里我们借助字符类型数组char code_buf[256] = "\0";,每次编码都将码子先并入该字符数组strcat(code_buf, huf_tree[i].code);

    具体实现中,我们使用while循环直到文件读完。在while循环中,每一次我们都读入一字节符号,将其编码存入 code_buf 数组;每当code_buf中字符长度大于8时,获取数组中的前八位,将其对应的ASCII码所对应的字符存入输出文件中,再将整个字符串前移八位,strcpy(code_buf, code_buf+8);。一直循环该操作,直至code_buf字符长度小于8或为0,然后再次读入符号。若长度最终为0,则写入完毕。若不为0,则将其不足的位数补0,写入到输出文件最后。其中核心部分,也就是每8位输出的转换过程如下。

    temp_char = '\0';
    for(i = 0; i < 8; i++)
    {
      temp_char <<= 1; //左移一位
      if(code_buf[i] == '1')
          temp_char |= 1; //与1按位异或
    }
    fwrite((char *)&temp_char, 1, 1, outfile);
    

    c. 解压文件

    压缩所得文件起始即记录了原文件中字符的种类数,获得后可知之后的多少字节中存储了哈夫曼树的编码信息,按照压缩的格式读取信息后,可以还原出编码后的哈夫曼树,即编码表可知。再向后读取,可得文件中字符的总数,即文件的总长度。

    此时,压缩文件中剩余的信息即为编码信息,将其逐位读入后,按照编码表翻译为原来的字符,写入输出文件中,即可得到原文件。需要注意的是,在解码过程中,每次成功解码后将一计数器加一,用于统计解码数是否到达原文件的字符长度,当长度到达后,舍弃压缩文件中剩余位数,完成写入,其目的为防止原先压缩过程中可能存在的补零操作所造成的影响。

    2. 算数编码

    设置功能类class Arithmetic,成员如下:

    string FileAddress; //操作对象文件地址
    int TotalNumber = 0;  //记录总的bit数
    int NumList[2] = {0};   //存储0和1出现的次数
    long double ProbaList[2] = {0.0};   //存储0和1出现的概率
    long double P[2] = {0.0};     //存储0和1概率区间的下限
    Arithmetic();   //构造函数
    void open(string input);
    void Press();   //压缩文件
    void Decode(string sourcefile, string dstfile); //解压文件
    
    

    以字节为单位读入,并将其分割成bit串形式

    read.read((char*)InChar, sizeof(unsigned char));    //读第一个字节
    	while (!read.eof())   //未读到末尾继续循环
    	{
    		TotalNumber += 8;   //每读入一个字符,总bit数加8
    		BitList[0] = (* InChar & 0x80) == 0x80 ? 1 : 0;
    		BitList[1] = (* InChar & 0x40) == 0x40 ? 1 : 0;
    		BitList[2] = (* InChar & 0x20) == 0x20 ? 1 : 0;
    		BitList[3] = (* InChar & 0x10) == 0x10 ? 1 : 0;
    		BitList[4] = (* InChar & 0x08) == 0x08 ? 1 : 0;
    		BitList[5] = (* InChar & 0x04) == 0x04 ? 1 : 0;
    		BitList[6] = (* InChar & 0x02) == 0x02 ? 1 : 0;
    		BitList[7] = (* InChar & 0x01) == 0x01 ? 1 : 0;    //将字节分割成bit形式
    

    计算文件中bit0和bit1的总数量和各自的概率

    ProbaList[0] = long double(NumList[0]) / TotalNumber;    //计算0和1出现的概率
    ProbaList[1] = long double(NumList[1]) / TotalNumber;
    
    P[0] = 0;    //计算0和1概率区间的下限
    P[1] = ProbaList[0];   
    

    对一定长度L的符号串进行编码,并将数据写入压缩后文件中。然后从压缩文件中读入数据,并还原成长度为L的符号串输入至解压文件中

    for (int i(0); i < N; i++)
    {
    	if (count == 0)		break;  //如果已经读完文件,则退出循环
    	for (int j(0); j < 8; j++)
    	{
    		if (temp >= P[1])
    		{	count -= 1;
    			OutList[j] = 1;
    			temp = (temp - P[1]) / ProbaList[1];				
    		}
    	else
    	{		count -= 1;
    			OutList[j] = 0;
    			temp = (temp - P[0]) / ProbaList[0];
    	}
    }
    

    算法的流程图如下。

    算数编码流程图

    3. LZ-78编码

    a. 设计功能类

    LZ-78编码的核心就是编码和解码中构造一个字典,通过字典的段号与最后一位字符来构造码字。因此这里将编码(或解码)这一事件封装成一个class类。类中有一个struct Dictionary变量,该变量存储一段符号串单元的字典元,其中依次包含了:

    • unsigned short preIndex:无符号短整型,长2字节,存储符号串的前缀的段号;
    • unsigned char lastChar:无符号字符型,长1字节,存储符号串末尾字符;
    • unsigned int Index:无符号整型,存储符号串的字典元在字典序列中的段号;
    • vector<unsigned char> stringInDic:无符号字符型组成的vector容器变量(相当于字符串),用于存储完整的该符号串。

    另外,class LZ78中还写了两个重要的函数:

    • 函数 IfStringInDic: 返回bool类型值,表示当前符号串是否已经在字典中出现过。该函数要求传入vector<Dictionary*>类型的变量,即编码中的字典和对应的vector(相当于字符串)。同时,传入的无符号整型Index是引用传递,这是为了让函数的执行结果能传递到外面的preIndex上,即找到并存储前缀的段号。该函数用于编码阶段;
    • 函数 FindPreString: 返回无符号字符类型的vector变量(相当于字符串)。要求传入字典和前缀数值。该函数用于解码阶段。

    整体的编码和解码使用的就是 函数 lz_compress函数 lz_decompress。这两个函数通过调用之前的两个重要的函数,能够简化其代码,最终实现LZ78的解码和编码。

    class LZ78
    {
    public:
        struct Dictionary //设置一个动态字典的单元
        {
            unsigned short preIndex; //2字节,前缀段号
            unsigned char lastChar; //最后一位字符
            unsigned int Index; //序列段号
            vector<unsigned char> stringInDic; //完整符号串
        };
        void lz_compress(string originfile); //压缩文件
        void lz_decompress(string sourcefile, string dstfile); //解压文件
    private:
        bool IfStringInDic(vector<Dictionary*> DataDic, vector<unsigned char> CurrentString, unsigned int &Index);
        //判断字符串是否在字典中
        vector<unsigned char> FindPreString(vector<Dictionary*> DataDic, unsigned int preindex);
        //找到并返回前缀字符串
    };
    

    b. 主程序调用测试

    借助前面定义的功能类,只要实例化LZ78 document;,就可以调用document.lz_compressdocument.lz_decompress来对传入的文件进行压缩和解压。在测试时,也引入了clock( )来测试运行的时间,并通过cout<<来输出运行中的提示。基础代码如下所示。

    int main(int argc, const char * argv[]) {
        LZ78 document;
        document.lz_compress("/Users/xrosheart/Desktop/news.txt");   //压缩文件
        document.lz_decompress("/Users/xrosheart/Desktop/news.txt.lz", "/Users/xrosheart/Desktop/test.txt");
        getchar();
        return 0;
    }
    

    c. 功能类函数实现

    1. 函数 lz_compress

    首先是 处理文件的读写。这里不同于之前哈夫曼编码,这里 采用了C++风格的fstream来进行文件读写 的操作。这也算是小组合作的好处之一,能够相互学习不同的编写方式。

    需要注意的是,在open操作时,要设置为ios::in|ios::binary,这是为了以二进制方式打开文件。要知道,由于历史原因,Windows 操作系统是用 两个字符\r\n来表示换行符的;而Unix操作系统却是用 单个字符\n来表示换行符 的。虽然无论是否指定二进制方式打开文件,读写的最小单位都是字节,但是在创建文件流时,如果指定了以ios::binary方式打开,那么换行符就是单字符的;否则,就采用Windows操作系统的双字符。

    ifstream read;
    read.open(originfile, ios::in|ios::binary);
    if (!read )
    {
    		cout << "文件读取错误" << endl << endl;
    		return;
    }
    
    ofstream write;
    write.open(originfile + ".lz", ios::out|ios::binary);
    if (!write)
    {
    		cout << "输出文件不能建立(.lz)" << endl;
    }
    

    打开文件之后读入目标文件时,我们使用ifstream的read函数进行操作,每次读入一字符,也就是一字节的长度,即8位二进制码。同样地,输出操作时,我们使用ofstream的write函数进行对文件的写入。每次写入3字节,也就刚好把 Dictionary 类型的前两个变量,即 preIndex 和 lastChar 写入。那么在后面的解码操作时,读写也是一样的方式,只是该方式的逆操作。

    //读入字符
    unsigned char *now = new unsigned char;
    read.read((char*)now, sizeof(unsigned char));
    //输出压缩结果
    Dictionary *currentInfo = new Dictionary;
    write.write((char*)currentInfo,3);
    

    接下来就是 边读入边建立字典编码的过程 了。这里首先要分两类,即第一次读入和接下来的读入,这是为了对于文件是否为空的操作。我们这里直接对接下来的读入进行分析。因为是边读入边建立字典,因此我们使用一个while循环包含了这些操作,涉及的变量如下所示。

    //大循环外
    vector<Dictionary*> DataDic;    //使用vector建立字典,单元为后面的currentInfo
    //大循环内
    unsigned char *now = new unsigned char; //用于读取的字符
    unsigned char *reallast = new unsigned char; //一组字符串除去已出现的前缀的末尾字符
    vector<unsigned char> CurrentString; //当前字符串
    unsigned int index = 0;  //字符串存在在字典中的位置, 初始设为0
    Dictionary *currentInfo = new Dictionary;   //存储到字典单元中,使用动态指针,便于读写
    

    我们使用函数 IfStringInDic 来作为do ... while的条件,每次找到一组新出现的字符串,然后前缀段号也由该函数通过引用传递到index变量中。而末尾字符也就存到*reallast指向的空间。最后把这些信息存入到字典单元*currentInfo中,然后将字典单元压入字典(vector)中,即DataDic.push_back(currentInfo);。每次都输出*currentInfo的前三字节到压缩输出文件中,也就是需要到码字了。

    2. 函数 lz_decompress

    该部分实际上与前面类似,不过会简单许多。同样都是建立字典,如果说压缩是将原文件转变为struct Dictionary然后输出 preIndex 和 lastChar 作为码字写入压缩文件;那么解压就是将压缩文件的码字的 preIndex 和 lastChar 转变为struct Dictionary,然后输出字典的 stringInDic。实际上就是互为逆过程。与之前不同的是,这里的采用的是vector<Dictionary> DataDic;DataDic.push_back(*now);。这是因为指针类型的 vector 会导致码字解码的丢失,因此采用传统的 vector 形式。其中利弊会在优化中指出。

    3. 函数 IfStringInDic 和 函数 FindPreString

    这两个函数其实都比较简单。实际上就是对字典的遍历操作,但这两个函数中有一点区别,函数 IfStringInDic 中建立的 DataDic 是 Dictionary* 类型的vector,而函数 FindPreString 中建立的 DataDic 是 Dictionary 类型的vector。这两者的区别就在于遍历查找的速度差别。

    4. 优化

    实际上优化的点就在于数据结构的选择,即vector的单元中选择的单元类型是 Dictionary* 还是 Dictionary。在测试中发现,vector<Dictionary*>vector<Dictionary>的查找要快了不少,但前者的存储空间调用更加负责,在解码的时候会产生码字流失现象。因此只在压缩中采取了前者的数据结构,而在解压中采用了后者的传统结构。

    四、实验拓展与编码操作

    实验对实现的哈夫曼编码和LZ-78编码进行了整合,即可以在一个程序下进行两种编码方式的切换选择,其简易操作界面展示如下。

    1.打开项目,打开main.cpp文件并运行程序,可以看到如图的简易操作界面,上面提示我们选择编码方式,待选项有:选项1,哈夫曼编码;选项2,LZ-78编码。

    图1 运行操作界面
    图2 哈夫曼编码压缩txt
    图3 哈夫曼编码解压txt

    2.选择编码方式,我们先选择哈夫曼编码进行测试,即输入1,然后会车。接下来操作界面会提示请输入您的选项(Q/C/D):,其中Q表示退出程序,C表示编码压缩,D表示解码解压。这里我们先选择压缩,即输入C然后回车,如图2所示。

    3.输入源文件和目标文件路径。在步骤2键入C后,会提示[源文件]:。这里既可以输入绝对路径(如E://user/…),也可以是相对路径(如图2)。输入完后,又会提示[目标文件]:,操作同上。

    4.步骤3完成后就会开始压缩。这里是把目标文件news.txt压缩成news.txt.huf,同时程序会对压缩过程进行计时。如图3所示,这次 哈夫曼编码压缩txt用时13/ms

    5.接着对刚刚产生对压缩文件进行解压。我们选择1,也就是哈夫曼编码,再选择D,然后输入源文件news.txt.huf和解压文件result.txt,进行解压,结果如图4所示。可以看到这次 哈夫曼编码解压txt用时10ms。另外也可以从图5和图6的对比中看到,哈夫曼编码压缩和解压后的文件和原文件一模一样。

    图4 news.txt 截图
    图5 result.txt 截图
    图6 result1.txt 截图

    6.使用哈夫曼编码对news.docx进行压缩,压缩为news.docx.huf。操作过程与结果如图8所示,可见这次 哈夫曼编码压缩docx用时659ms。接着再对news.docx.huf进行解压,得到result.docx,其操作过程和结果如图9所示,可见这次 哈夫曼编码压缩docx用时239ms

    图7 哈夫曼编码压缩docx
    图8 哈夫曼编码解压docx

    7.接下来对LZ-78编码进行测试。使用LZ-78编码把news.txt压缩为news.txt.lz,然后再把news.txt.lz解码为result1.txt,通过图9可见,生成文件与原文件一模一样。压缩过程如图10所示,解压过程如图11所示,可见这次LZ-78编码txt用时24s,解压txt用时49s。其x

    图9 LZ-78编码压缩txt
    图10 LZ-78编码解压txt

    以上就是整合的两种编码方式简易操作界面的操作过程,通过使用C++的clock( )进行计时来记录编码解码的用时,通过对前后文件大小的变化衡量编码效率。该过程也可以进行哈夫曼和LZ-78的编码效果对比。

    五、编码结果与性能分析

    1. 哈夫曼编码

    操作环境: Windows10,Visual Studio 2017。

    测试用例: 使用了老师所给的17KB的news.txt文件、531KB的news.docx,以及自己随机找的96KB的little.docx和17.6M的large.docx,包括了 txt、docx和mp4三种文件类型,和4个不同数量级的文件大小,小到17KB,大到30.2M,测试范围涵盖全面。

    测试数据: 主要测试压缩前后文件大小,计算压缩率;另外记录编码和解码用时。具体数据如下所示。

    原始文件news.txt (17KB)little.docx (96KB)news.docx (531KB)large.docx (17.6M)test.mp4 (30.2M)
    压缩文件news.txt.huf (10KB)little.docx.huf (96KB)news.docx.huf (531KB)large.docx (17.6M)test.mp4.lz (30.2M)
    压缩率58.8%1111
    编码用时10ms133ms659ms24164ms44s
    解码用时463ms239ms7742ms15s

    可见编写的哈夫曼编码适用范围广,对于txt、docx、mp4视频等文件均适用,而且编码解码速度较快。不足之处在于,虽然对于txt文件有着优秀的压缩率,但对于docx、mp4这类较大较负责的文件,几乎无压缩效果。这点也是需要后期有机会改进的。

    2. LZ-78编码

    该算法最初在macOS Xcode 10.1上编写调试,初步效果对于txt和较小的docx文件较好。出于在算法设计中提到的,译码时采用指针类型vector会导致码字丢失,故在解码过程中采用了传统的vector数据结构,速度较慢。这也在测试数据中明显地体现出来了:编码用时比解码用时少,编码速度较快而解码速度稍慢

    原始文件news.txt (17KB)little.docx (98KB)
    压缩文件news.txt.lz (13KB)little.docx.lz (122KB)
    压缩率76.5%1.24
    编码用时44ms30ms
    解码用时275ms202s

    然而,或许是因为macOS类Linux系统与Windows系统的差别,二者对于指针存储结构的处理能力差别较大。因此在win10的 Visual Studio 2017上效果明显劣于macOS上的表现。

    原始文件news.txt (17KB)little.docx (96KB)
    压缩文件news.txt.huf (13KB)little.docx.lz (96KB)
    压缩率76.5%1.24
    编码用时24s2547s
    解码用时47s/

    可见 此处实验使用的LZ-78实现算法更适合在macOS系统上使用。从这其中发现的 系统差别对于编码性能的影响 也算是实验的意外收获了。

    3. 算数编码

    对96KB的news.txt文件进行算数编码,压缩结果如图10所示,压缩总 bit 数为 137872 bit,其中0的概率为 54.3%,1的概率为 47.3%。压缩用时271ms,解压用时1ms。

    图11 编码字符串1字节news.txt结果

    由于未能在代码中解决浮点数在运算和存储中精度的不确定性,因此编码效率无法到达100%,会产生一定的无码,因而无法压缩docx文档。

    另外,在压缩txt文件时,随着待编码字符串长度的增加,对浮点数精确度要求更高,编码准确率降低,以下显示待编码字符串长度为1字节、2字节、3字节时的压缩情况。

    图12 编码字符串1字节时情况
    图13 编码字符串2字节时情况
    图14 编码字符串3字节时情况

    六、问题总结与体会

    以上信源编码的实现需要深刻地理解 哈夫曼编码、LZ编码与算数编码 的原理,并且明白了不同编码的实现方式。一开始时,由于对于这些编码方式的理解并不深刻,对于该如何用程序实现代码也没有思路,所以进展比较缓慢。于是尝试首先理解这些编码的基本编码原理,再尝试利用C++代码实现这些编码的字典,一步步走,最后得以写出完整的编码。

    在实现哈夫曼编码的过程中,最初不知道怎样将文件进行读入或者读出,所以最初实现的编码方式是通过指令台输入要编码的信源序列,并且采用一个数组来保存它,对它进行读取扫描来实现哈夫曼树或者建立字典,但是由于数组长度有限,而且希望以文件格式输入输出,所以最开始实现的程序需要在很大程度上进行改进;此外,在实现哈夫曼树的过程中时,当一步步将概率合并以将哈夫曼树走到上层之后,如何一步步返回到下层又成了问题。

    在实现LZ-78编码的过程中,遇到的两个主要问题就是如何实现bit单位的变长码字以及如何存储字典数据。在查阅资料以及不同数据结构的尝试下,找到了较优的数据结构,即采用指针单位的vector数据类型。另外对于变长码字,由于bit单位的操作较为负责,退而求其次,采用了一个上限长度,不过缺点在于造成了一定的冗余。在macOS的Xcode移植到win10的VS上时,发现了 系统与编译器对编码算法性能的巨大影响。通过查阅资料了解了VS和Xcode的性能比对后,将 原因归结于系统的差别——类Linux系统和windows系统在存储方式的差别对指针类型存储结构的操作性能差异

    在实现算数编码的过程中,最初是对每一个字符进行编码。由于 A S C I I ASCII ASCII码对应的长度为一个字节而许多中文字符对应的长度为两个字节,因此单纯对一个字符进行编码会造成不同字符长度不一致的问题。最后决定对文件中一个字节一个字节读入,然后对 8位比特的256种不同的可能性 进行编码。由于算数编码需要对不同的字符的概率进行映射,而一个文本中8位不同的比特可能组合会高达数十种,造成有些概率非常接近,最终精度不够,编码正确率不够高。最后采取的方式为将文件分割成比特形式,统计比特0和比特1出现的概率并在此基础上编码,提升了准确率。

    最后,将哈夫曼编码和LZ-78整合在一起的过程也遇到了一些阻力:一方面是对VS不够了解,另一方面对于整合用的main.cpp的设计。不过有了之前编码实现的提示,也都比较顺利地解决了困难,最终做出了一个 简易的操作界面,实现了 哈夫曼编码和LZ-78的选择编码

    展开全文
  • 信源编码与信道编码

    千次阅读 2018-04-20 19:14:18
    信源编码:对输入信息进行编码,优化信息和压缩信息,并打包成符合标准的数据包。信源编码的主要作用是:1. 将模拟信号转化为数字信号;2. 对数据进行压缩。在保证通信质量的前提下,尽可能的通过对信源的压缩,提高...
    信源编码:

    对输入信息进行编码,优化信息和压缩信息,并打包成符合标准的数据包。

    信源编码的主要作用是:1. 将模拟信号转化为数字信号;2. 对数据进行压缩。在保证通信质量的前提下,尽可能的通过对信源的压缩,提高通信时的有效性。就是让通信变得更加的有效率。以更少的符号来表示原始信息,所以减少了信源的剩余度。
    信源编码的种类主要包括:Huffman编码、算术编码、L-Z编码,这三种均为无损编码,另外还有一些有损的编码方式。
    信道编码:

    为了减少差错,对传输的信息码元按照一定的规则加入保护成分(监督元),组成所谓的“抗干扰编码”。接收端按照一定的规则进行解码,从解码过程中发现错误或纠正错误,从而提高通信系统的抗干扰能力,实现可靠通信。

    信道编码的主要作用是:通过对做完信源编码后的信息加入冗余信息,使得接收方在收到信号后,可通过信道编码中的冗余信息,做前向纠错保证信息传输的可靠性、提高传输质量
    举个例子,要运一批碗到外地,首先在装箱的时候,将碗摞在一起,这就类似是信源编码,压缩以便更加有效率。然后再箱子中的空隙填上报纸,泡沫,做保护,就像信道编码,保证可靠。
    信道编码的种类主要包括:线性分组码、卷积码、级联码、Turbo码和LDPC码






    展开全文
  • 编码方式—信源编码

    2021-04-27 20:46:55
    编码方式—信源编码 信源编码的介绍 信源编码是一种以提高通信有效性为目的而对信源符号进行的变换,或者说为了减少或消除信源冗余度而进行的信源符号变换,具体说,就是针对信源输出符号序列的统计特性来寻找某种方法,...

    编码方式—信源编码
    信源编码的介绍
    信源编码是一种以提高通信有效性为目的而对信源符号进行的变换,或者说为了减少或消除信源冗余度而进行的信源符号变换,具体说,就是针对信源输出符号序列的统计特性来寻找某种方法,把信源输出符号序列变换为最短的码字序列,使后者的各码元所载荷的平均信息量最大,同时又能保证无失真地恢复原来的符号序列.编码结果是对输入信息进行编码,优化信息和压缩信息并且打成符合标准的数据包.信源编码的作用之一是,即通常所说的数据压缩;作用之二是将信源的模拟信号转化成数字信号,以实现模拟信号的数字化传输.
    最原始的信源编码就是莫尔斯电码,另外还有ASCII码和电报码都是信源编码.但现代通信应用中常见的信源编码方式有:Huffman编码、算术编码、L-Z编码,这三种都是无损编码,另外还有一些有损的编码方式.信源编码的目标就是使信源减少冗余,更加有效、经济地传输,最常见的应用形式就是压缩. 另外,在数字电视领域,信源编码包括通用的MPEG—2编码和H.264(MPEG—Part10 AVC)编码等.
    一种以提高通信有效性为目的而对信源符号进行的变换;为了减少或消除信源剩余度而进行的信源符号变换.为了减少信源输出符号序列中的剩余度、提高符号的平均信息量,对信源输出的符号序列所施行的变换.具体说,就是针对信源输出符号序列的统计特性来寻找某种方法,把信源输出符号序列变换为最短的码字序列,使后者的各码元所载荷的平均信息量最大,同时又能保证无失真地恢复原来的符号序列.
    基于层次树的集分割(SPIHT)信源编码方法是基于EZW而改进的算法,它是有效利用了图像小波分解后的多分辨率特性,根据重要性生成比特流的一个渐进式编码.这种编码方法,编码器能够在任意位置终止编码,因此能够精确实现一定目标速率或目标失真度。同样,对于给定的比特流,解码器可以在任意位置停止解码,而仍然能够恢复由截断的比特流编码的图像.而实现这一优越性能并不需要事先的训练和预存表或码本,也不需要任何关于图像源的先验知识.
    既然信源编码的基本目的是提高码字序列中码元的平均信息量,那么,一切旨在减少剩余度而对信源输出符号序列所施行的变换或处理,都可以在这种意义下归入信源编码的范畴,例如过滤、预测、域变换和数据压缩等.当然,这些都是广义的信源编码.
    一般来说,减少信源输出符号序列中的剩余度、提高符号平均信息量的基本途径有两个:①使序列中的各个符号尽可能地互相独立;②使序列中各个符号的出现概率尽可能地相等.前者称为解除相关性,后者称为概率均匀化.
    第三代移动通信中的信源编码包括语音压缩编码、各类图像压缩编码及多媒体数据压缩编码.
    信源编码定理:
    不同类型的信源,是否存在有每种信源的最佳的信源编码,这通常是用信源编码定理来表示.最简单、最有实用指导意义的信源编码定理是离散、无记忆型信源的二进制变长编码的编码定理.它证明,一定存在一种无失真编码,当把N个符号进行编码时,平均每个符号所需二进码的码长满足.
    其中H(U)是信源的符号熵(比特),这就是说,最佳的信源编码应是与信源信息熵H(U)统计匹配的编码,代码长度可接近符号熵.这一结论不仅表明最佳编码存在,而且还给出具体构造码的方法,即按概率特性编成不等长度码.对不同类型信源,如离散或连续、无或有记忆、平稳或非平稳、无或限定失真等,可以构成不同的组合信源,它们都存在各自的信源编码定理.但它们中绝大部分仅是属于理论上的存在性定理,这给具体寻找和实现不同类型信源的信源编码,带来了相当的难度.
    信源编码的分类:
    信源编码根据信源的性质进行分类,则有信源统计特性已知或未知、无失真或限定失真、无记忆或有记忆信源的编码;按编码方法进行分类可分为分组码或非分组码、等长码或变长码等.然而最常见的是讨论统计特性已知条件下,离散、平稳、无失真信源的编码,消除这类信源剩余度的主要方法有统计匹配编码和解除相关性编码.比如仙农码、费诺码、赫夫曼码,它们属于不等长度分组码,算术编码属于非分组码;预测编码和变换编码是以解除相关性为主的编码.对限定失真的信源编码则是以信息率失真R(D)函数为基础,最典型的是矢量量化编码.对统计特性未知的信源编码称为通用编码.
    信源编码的应用:
    以简单的数据压缩为例即可说明信源编码的应用.若有一离散、无失真、无记忆信源,它含有五种符号U0~U4及其对应概率Pi,对它进行两种编码:等长码和最佳赫夫曼码.

    其中,等长码的平均码长:=3,即三位码.若采用赫夫曼编码,平均码长,即不足两位码.这就是说,数据压缩了以上.
    1.在现代无线通信中的应用:信源编码是以提高通信有效性为目的的编码.通常通过压缩信源的冗余度来实现.采用的一般方法是压缩每个信源符号的平均比特数或信源的码率.
    2.在超宽带中的应用:与信道编码联合,使重要信息得到更好的保护,使解码质量提高.例如不等差错保护,相对于同差错保护而言,不等差错保护根据码流的不同部分对图像重建质量的重要性不同,而采用不同的信道保护机制,是信源信道联合编码的一个重要应用,其信源编码主要采用嵌入式编码.
    信源编码的专业表述:
    既然信源编码的基本目的是提高码字序列中码元的平均信息量,那么,一切旨在减少剩余度而对信源输出符号序列所施行的变换或处理,都可以在这种意义下归入信源编码的范畴,例如过滤、预测、域变换和数据压缩等.当然,这些都是广义的信源编码.
    一般来说,减少信源输出符号序列中的剩余度、提高符号平均信息量的基本途径有两个:1.使序列中的各个符号尽可能地互相独立;2.使序列中各个符号的出现概率尽可能地相等.前者称为解除相关性,后者称为概率均匀化.

    信源编码的一般问题可以表述如下:若某信源的输出为长度等于M的符号序列集合式中符号A为信源符号表,它包含着K个不同的符号,A={ɑk|k=1,…,K},这个信源至多可以输出KM个不同的符号序列.记‖U‖=KM.所谓对这个信源的输出进行编码,就是用一个新的符号表B的符号序列集合V来表示信源输出的符号序列集合U.若V的各个序列的长度等于 N,即 式中新的符号表B共含L个符号,B={bl|l=1,…,L}.它总共可以编出LN个不同的码字.类似地,记‖V‖=LN.为了使信源的每个输出符号序列都能分配到一个独特的码字与之对应,至少应满足关系 ‖V‖=LN≥‖U‖=KM或者 N/M≥logK/logL .
    假若编码符号表B的符号数L与信源符号表A的符号数K相等,则编码后的码字序列的长度N必须大于或等于信源输出符号序列的长度M;反之,若有N=M,则必须有L≥K.只有满足这些条件,才能保证无差错地还原出原来的信源输出符号序列(称为码字的唯一可译性).可是,在这些条件下,码字序列的每个码元所载荷的平均信息量不但不能高于,反而会低于信源输出序列的每个符号所载荷的平均信息量.这与编码的基本目标是直接相矛盾的.下面的几个编码定理,提供了解决这个矛盾的方法.它们既能改善信息载荷效率,又能保证码字唯一可译.
    离散无记忆信源的定长编码定理
    对于任意给定的ε>0,只要满足条件 N/M≥(H(U)+ε)/logL

    那么,当M足够大时,上述编码几乎没有失真;反之,若这个条件不满足,就不可能实现无失真的编码.式中H(U)是信源输出序列的符号熵.通常,信源的符号熵H(U)<logK,因此,上述条件还可以表示为【H(U)+ε】/logL≤N/M≤logK/logL .
    特别,若有K=L,那么,只要H(U)<logK,就可能有N<M,从而提高信息载荷的效率.由上面这个条件可以看出,H(U)离logK越远,通过编码所能获得的效率改善就越显著.实质上,定长编码方法提高信息载荷能力的关键是利用了渐进等分性,通过选择足够大的M,把本来各个符号概率不等[因而H(U)<logK]的信源输出符号序列变换为概率均匀的典型序列,而码字的唯一可译性则由码字的定长性来解决.
    离散无记忆信源的变长编码定理
    变长编码是指V的各个码字的长度不相等.只要V中各个码字的长度 Ni(i=1,…,‖V‖)满足克拉夫特不等式这‖V‖个码字就能唯一地正确划分和译码.离散无记忆信源的变长编码定理指出:若离散无记忆信源的输出符号序列为,式中 A={ɑk|k=1,…,K},符号熵为H(U),对U进行唯一可译的变长编码,编码字母表B的符号数为L,即B={bl|l=1,…,L},那么必定存在一种编码方法,使编出的码字Vi=(vi1,…,viNi),(i=1,…,‖V‖),具有平均长度嚻:MH(U)/logL≤嚻<MH(U)/logL+1 .
    若L=K,则当H(U)<logK=logL时,必有嚻<M;H(U)离logK越远,则嚻越小于M.
    具体实现唯一可译变长编码的方法很多,但比较经典的方法还是仙农编码法、费诺编码法和霍夫曼编码法.其他方法都是这些经典方法的变形和发展.所有这些经典编码方法,都是通过以短码来表示常出现的符号这个原则来实现概率的均匀化,从而得到高的信息载荷效率;同时,通过遵守克拉夫特不等式关系来实现码字的唯一可译.
    霍夫曼编码方法的具体过程是:首先把信源的各个输出符号序列按概率递降的顺序排列起来,求其中概率最小的两个序列的概率之和,并把这个概率之和看作是一个符号序列的概率,再与其他序列依概率递降顺序排列(参与求概率之和的这两个序列不再出现在新的排列之中),然后,对参与概率求和的两个符号序列分别赋予二进制数字0和1.继续这样的操作,直到剩下一个以1为概率的符号序列.最后,按照与编码过程相反的顺序读出各个符号序列所对应的二进制数字组,就可分别得到各该符号序列的码字.

    例如,某个离散无记忆信源的输出符号序列及其对应的概率分布为对这些输出符号序列进行霍夫曼编码的具体步骤和结果如表.由表中可
    以看出,在码字序列中码元0和1的概率分别为10/21和11/21,二者近乎相等,实现了概率的均匀化.同时,由于码字序列长度满足克拉夫特不等式 2×2-2+3×2-3+2×2-4=1 .
    因而码字是唯一可译的,不会在长的码字序列中出现划错码字的情况.

    以上几个编码定理,在有记忆信源或连续信源的情形也有相应的类似结果.在实际工程应用中,往往并不追求无差错的信源编码和译码,而是事先规定一个译码差错率的容许值,只要实际的译码差错率不超过这个容许值即认为满意(见信息率-失真理论和多用户信源编码).
    信源编码的分析
    信源编码和信道编码的区别:
    信源编码的作用之一是设法减少码元数目和降低码元速率,即通常所说的数据压缩.码元速率将直接影响传输所占的带宽,而传输带宽又直接反映了通信的有效性.作用之二是,当信息源给出的是模拟语音信号时,信源编码器将其转换成数字信号,以实现模拟信号的数字化传输.模拟信号数字化传输的两种方式:脉冲编码调制(PCM)和增量调制(ΔM),信源译码是信源编码的逆过程.1.脉冲编码调制(PCM)简称脉码调制:一种用一组二进制数字代码来代替连续信号的抽样值,从而实现通信的方式.由于这种通信方式抗干扰能力强,它在光纤通信、数字微波通信、卫星通信中均获得了极为广泛的应用.增量调制(ΔM):将差值编码传输,同样可传输模拟信号所含的信息.此差值又称“增量”,其值可正可负.这种用差值编码进行通信的方式,就称为“增量调制”,缩写为DM或ΔM,主要用于军方通信中.信源编码为了减少信源输出符号序列中的剩余度、提高符号的平均信息量,对信源输出的符号序列所施行的变换.具体说,就是针对信源输出符号序列的统计特性来寻找某种方法,把信源输出符号序列变换为最短的码字序列,使后者的各码元所载荷的平均信息量最大,同时又能保证无失真地恢复原来的符号序列.信道编码的目的:信道编码是为了保证信息传输的可靠性、提高传输质量而设计的一种编码.它是在信息码中增加一定数量的多余码元,使码字具有一定的抗干扰能力.信道编码的实质:信道编码的实质就是在信息码中增加一定数量的多余码元(称为监督码元),使它们满足一定的约束关系,这样由信息码元和监督码元共同组成一个由信道传输的码字.信源编码很好理解,比如你要发送一个图形,必须把这个图像转成0101的编码,这就是信源编码.
    信道编码数字信号在信道传输时,由于噪声、衰落以及人为干扰等,将会引起差错.为了减少差错,信道编码器对传输的信息码元按一定的规则加入保护成分(监督元),组成所谓“抗干扰编码”.接收端的信道译码器按一定规则进行解码,从解码过程中发现错误或纠正错误,从而提高通信系统抗干扰能力,实现可靠通信.信道编码是针对无线信道的干扰太多,把你要传送的数据加上些信息,来纠正信道的干扰.信道编码数字信号在信道传输时,由于噪声、衰落以及人为干扰等,将会引起差错.为了减少差错,信道编码器对传输的信息码元按一定的规则加入保护成分(监督元),组成所谓“抗干扰编码”.接收端的信道译码器按一定规则进行解码,从解码过程中发现错误或纠正错误,从而提高通信系统抗干扰能力,实现可靠通信.
    信源编码信号:例如语音信号(频率范围300-3400Hz)、图象信号(频率范围0-6MHz)……基带信号(基带:信号的频率从零频附近开始).在发送端把连续消息变换成原始电信号,这种变换由信源来完成.
    信道编码信号:例如二进制信号、2PSK信号……已调信号(也叫带通信号、频带信号).这种信号有两个基本特征:一是携带信息;二是适应在信道中传输,把基带信号变换成适合在信道中传输的信号完成这样的变换是调制器.
    信源编码是对输入信息进行编码,优化信息和压缩信息并且打成符合标准的数据包.信道编码是在数据中加入验证码,并且把加入验证码的数据进行调制.两者的作用完全不一样的.信源编码是指信号来源的编码,主要是指从那个接口进来的.信道编码是说的信号通道的编码,一般是指机内的电路.总的来说:信源编码是对视频、音频,数据进行的编码,即对信息进行编码以便处理,而信道编码是指在信息传输的过程中对信息进行的处理.

    展开全文
  • 信源编码和信道编码

    千次阅读 2018-12-06 15:14:59
    信源编码和信道编码的发展历程 信源编码:  最原始的信院编码就是莫尔斯电码,另外还有ASCII码和电报码都是信源编码。但现代通信应用中常见的信源编码方式有:Huffman编码、算术编码、L-Z编码,这三种都是无损...
  • TETRA信源编码系统的研究及其在DSP上的优化实现、电子技术,开发板制作交流
  • 香农编码、费诺编码、哈夫曼编码的c/c++实现
  • 霍夫曼信源编码实验报告 1 实验 1:霍夫曼信源编码综合设计 【实验目的】 通过本专题设计,掌握霍夫曼编码的原理和实现方法,并熟悉利用 C 语言进行 程序设计,对典型的文本数据和图像数据进行霍夫曼编解码。...
  • 信源编码信源编码是一种以提高通信有效性为目的而对信源符号进行的变换,或者说为了减少或消除信源利余度而进行的信源符号变换。具体说,就是针对信源输出符号序列的统计特性来寻找某种方法,把信源输出符号序列变换...
  • 实验目的1. 实现压缩编码算法——Huffman编码 2. 实现压缩编码算法——Shannon Fano编码 3. 实现压缩编码算法——LZ编码 4. 实现压缩编码算法——算数编码 ...[信源编码源代码](https://github.com/PiggyGa
  • LZW算法是1984年Terry A.Welch在字典压缩算法LZ78基础上改进的一种通用压缩算法。其较快的他说速度和对各种... 在VS2015上对输入的test.bmp实现相应的压缩功能。        
  • 信源编码初步介绍

    万次阅读 多人点赞 2018-06-19 17:54:10
    接下来讲解信源编码相关知识。信源编码是什么?为什么要进行信源编码?对于数字通信系统而言,因为信源是模拟信息,所以信源编码主要完成把模拟信号转换成数字信号;若信源为离散信息,那么信源编码的主要任务就是将...
  • 信源编码 C语言

    2011-11-27 15:09:16
    信源符号按概率大小排序 个概率所对应的二进制数 计算码字 、码长 累加概率 信息熵、编码效率
  • 实验1:霍夫曼信源编码综合设计【实验目的】通过本专题设计,掌握霍夫曼编码的原理和实现方法,并熟悉利用C语言进行程序设计,对典型的文本数据和图像数据进行霍夫曼编解码。【预备知识】1、熵的概念,霍夫曼编码...
  • 基于多级编码的分布式信源编码,陈睿,,分布式信源编码是无线通信领域研究的新热点,本文阐述了分布式编码的基础理论,介绍了应用于分布式编码的LDPC编码方法和多级编码��
  • java实现三种信源编码

    2010-12-18 12:03:39
    信源编码的目的是要减少冗余,提高编码效率。 一、香农码 编码步骤: 1)将个信源符号按概率递减的方式进行排列; 2)按香农不等式计算出每个信源符号的码长; 3)为了编成惟一可译码,计算第i个信源符号的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,339
精华内容 2,135
关键字:

信源编码实现