由定义式可以知道，

信源编码的核心问题：

信源的熵H(S)



信息速率Rb



其中，RS是符号速率，单位是(符号/s)或者是(Baud)
信源编码的主要问题：

信源的符号数L、概率场{Si}已知，如何选择划分的符号数J，使得Jlog2L≤n1log2D，即位数n1 满足



然后n1log2D尽可能小，来提高编码效率ηC=H(S)/n1log2D？
解决方法：
（1）均匀编码（等长编码）：
将原本“信源的符号数为L，每J个符号一组来编码”产生的序列集数目LJ减少至典型序列TS(J,ε)的数目a。

利用典型序列大概率的特性，我们就有可能在允许传输一定失真的场合，只对典型序列进行编码和传输，而对非典型序列则不进行编码和传输（或者每遇到信源发出的一个非典型序列，信源发送某个固定的序列，这个固定的序列只占编码后的一个码字）。这样，相对于将整个空间的每个序列都进行编码，所需的码字长度就可以大大缩短，由此就可以有效地提高传输的效率。

这种做法的缺点是，非典型序列译码时会有错误。因此，还需要进一步约束符号数J，使得存在整数J0，码长J＞J0时，译码的错误概率PE＜ε。满足该条件时，编码速率R被称为是可达的。若R＞H(S)，则R是可达的。

在实际计算中，已知信源概率场，若只对典型序列编码，要求误码率PE，编码效率ηC，求出信源的平均信息量H(S)，ε，符号自信息量的方差，据此就可以求出满足要求的J。

例1：





（2）非均匀编码（不等长编码）
均匀编码的确能显著减少序列集数目，而且因每个码字的长度相同，容易实现恒定的编码输出速率。但带来的问题是，要想实现高效率的编码，均匀编码所需码字的长度J往往很大，这会在实际应用中造成编码缓存空间很大和时延增大等问题。实际系统中，大量应用的是不等长的编码方法。
不等长编码的一边规则是，对出现概率大的符号或符号组用位数较少的码字表示；而对出现概率小的符号或符号组用位数较大的码字表示。
由于不等长编码不同符号的位数不同，有可能会出现：某个符号的码字就是另一个符号的码字的前几位，从而影响接受时间。因此，引入概念异字头码。
异字头码：任一码字都不是另一码字的字头或前缀。接收的时候，收到就知道是谁，不用花时间等它会不会是其他码字的字头。
异字头码的编码方法：编码树

将信源符号分成尽可能等概的D个子集，与码树的第一级的D个节点对应；对每个子集按相同的方法又分为D个二级子集，与码树的第二级节点相对应；以此类推，直至子集不能再分为止。
若D是组成码字的元素的个数，则任一唯一可译码的平均码长满足

n≥H(S)/logD

存在有D元的可译码，其平均长度

n＜1+H(S)/logD

等长编码与不等长编码小结
共同点：

前提：信源Si共L种符号，每种符号出现概率分别为Pi。对于等长编码，信源序列每J个进行编码，D进制编码；对于不等长编码，采用编码树（或其他，原理相同），D进制编码，得到的新的码字的码长分别为ni

编码效率





不同点：

等长编码：

编码速率（信息速率）







不等长编码：

编码速率（信息速率）




平均码长

接上一节信源编码（一）简单介绍第五章的主要内容，下面介绍编码的具体定义
 
 
5.1 编码的定义
信源输出符号序列长度L＝1，信源符号集A(a1，a2，…，an)，信源概率空间为

若将信源X通过二元信道传输，就必须把信源符号ai变换成由0，1符号组成的码符号序列，这个过程就是信源编码。
码可分为两类：
固定长度的码，码中所有码字的长度     都相同，如表5-1中的码1就是定长码
可变长度码，码中的码字长短不一，如表中码2就是变长码。
不同的码符号序列，如表所示：


奇异码和非奇异码 
若信源符号和码字是一一对应的，则该码为非奇异码。反之为奇异码。
如下表中的码1是奇异码，码2是非奇异码。 
唯一可译码 和非唯一可译码
唯一可译码：任意有限长的码元序列，只能被唯一地分割成一个个的码字，便称为唯一可译码。


唯一可译码中又分为非即时码和即时码
定长码中每个码字长度相等，所以只要定长码是非奇异码，则必为唯一可译码。
对于变长码，需要判断
唯一可译码存在的充分和必要条件：各码字的长度Ki 应符合克劳夫特不等式：


非即时码：如果接收端收到一个完整的码字后，不能立即译码，还需等下一个码字开始接收后才能判断是否可以译码。
即时码：只要收到符号就表示该码字已完整，可以立即译码。
即时码的条件:
设W1=Wi1Wi2…WiL为一个码字，对于任意的1≤j≤l，称码符号序列的前j个元素Wi1Wi2… Wij为码字的前缀。
按照上述定义，有以下命题：
一个唯一可译码成为即时码的充要条件是其中任何一个码字都不是其它码字的前缀。
 也称为异前缀码
非延长码
任意一个码字都不是其它码字的前缀部分，异前缀码。
码的分类表


 
克劳夫特不等式
设二进制码树中X    (a1， a2 ， a3 ， a4  )，K1＝1，K2＝2，K3＝2，K4＝3，应用上述判断定理：


因此不存在满足这种Ki的唯一可译码。


唯一可译码判别准则
命题：
一种码是唯一可译码的 充要条件是S1,S2,…  中没有一个含有S0中的码字。
— 首先判断是否为非奇异码
— 计算是否满足Kraft不等式
— 将码画成一棵码树，看是否满足即时码的树图构造，若满足则是唯一可译码
— 用后缀集合F来判断
 
 
无失真信源编码描述-1
信源输出
                X＝(X1X2…Xl…XL)，
              Xl{a1，a2，…，ai，…，an}
编码为
             Y＝(Y1Y2…Yk… YkL)，
        Yk{b1，b2，…，bj，…，bm}。
要求能够无失真或无差错地译码，同时传送Y时所需要的信息率最小                     
无失真的信源编码定理
— 定长编码定理
由L个符号组成的、每个符号的熵为HL(X)的无记忆平稳信源符号序列X1X2…Xl…XL，可用KL个符号Y1，Y2，…，Yk，…，（每个符号有m种可能值）进行定长编码。对任意>0，>0，只要 
                                                            
则当L足够大时，必可使译码差错小于；
反之，当时，译码差错一定是有限值，而L足够大时，译码几乎必定出错。
说明：
n 左边是输出码字每符号所能载荷的最大信息量
n 等长编码定理
n 码字所能携带的信息量大于信源序列携带的信息量，则总可以实现几乎无失真的编码，条件是编码的长度L足够大。 
n 反之，当时，不可能构成无失真的编码，也就是不可能做一种编码器，能使收端译码时差错概率趋于零。
n  时，则为临界状态，可能无失真，也可能有失真。




在连续信源的情况下，由于信源的信息量趋于无限，显然不能用离散符号序列Y来完成无失真编码，而只能进行限失真编码。
编码效率：
为衡量编码效果，定义编码效率


信源的平均符号熵为H(X)，采用平均符号码长为来编码，所得的效率。
编码效率总是小于1，且最佳编码效率为 
最佳编码效率：
编码定理从理论上阐明了编码效率接近1的理想编码器的存在性，它使输出符号的信息率与信源熵之比接近于1，即


— 变长编码定理 
在变长编码中，码长K是变化的
提问：对同一信源，其即时码或唯一可译码可以有许多种。究竟哪一种好呢？从高速传输信息的观点来考虑，当然 希望选择由短的码符号组成的码字，就是用码长来作为选择准则
根据信源各个符号的统计特性，如概率大的符号用短码，概率小的用较长的码，使得编码后平均码长降低，从而提高编码效率。（统计匹配）
单个符号变长编码定理
若离散无记忆信源的符号熵为H(X)，每个信源符号用m进制码元进行变长编码，一定存在一种无失真编码方法，其码字平均长度满足下列不等式


离散平稳无记忆序列变长编码定理
对于平均符号熵为HL(X)的离散平稳无记忆信源，必存在一种无失真编码方法，使平均信息率满足不等式


其中为任意小正数。
用变长编码来达到相当高的编码效率，一般所要求的符号长度L可以比定长编码小得多。
无失真信源编码
上面的两个定理实际上是一样的，可以由第一个推导出第二个。设用m进制码元做变长编码，序列长度为L个信源符号，则该序列所对应的码字的平均长度       满足下面的不等式


而平均输出信息率为


故有，当L足够大时，可使，因此，
无失真信源编码
香农第一编码定理给出了码字的平均长度的下界和上界。但并不是说大于这上界不能构成唯一可译码，而是因为我们总是希望尽可能短。
定理说明当平均码长小于上界时，唯一可译码也存在。也就是说，定理给出的是最佳码的最短平均码长，并指出这个最短的平均码长与信源熵是有关的。
编码效率和剩余度
编码效率为


剩余度（冗余度）

在学习信息论与编码的时候，博主在学马尔科夫信源的时候因为上课走神导致在这个知识点上有点迷糊，不过好在及时课下复习了一下大概上算是理清了。所以在这里简单做一下总结。
一、马尔科夫信源的定义
在讨论定义之前，我们要先明白这两个概念：符号集、状态。
信源的符号集与状态
所谓符号集很好理解，就是你这个信源可能会发出符号有哪些。比如说{0,1}，这里其实{}里面的东西可以任何可以代表符号的东西。

而状态可以这样理解，它是这些符号集的一些组合，比如说{00，01,10,11}。这里我们或许会想那这个状态只能是两个符号构成吗？当然不是，这个要取决于你自己是要处理多少阶的。（emmm，这个解释是有点涉及后面的马科夫信源了，在这里不必深究，看到后面自然就能明白“阶”的含义了）。

那么总结一下，信源输出随机信号序列（符号用x来表示）：x1，x2…xn

信源的状态序列是（状态用s来表示）S1，S2…Sn
马科夫信源的定义
好了，有了以上两个概念大家在理解马科夫信源上面就会比较容易了。
马尔科夫信源指的是一个信源要满足一下两个条件

1.这个信源发出的符号只与当前状态有关，与前面的状态和输出的符号无关。（在这里就可以看出他与我们正常的以符号序列来表达消息的理解方式不一样，这里要注意）

2.当前信源的状态可以有当前发出的符号和前一状态所唯一确定（可能有点抽象，但是应该不难理解，不太清楚地话继续往下看之后回头或许就能理解了）
Ok，我们知道了定义那么我就要去思考这个马尔科夫信源的与我们之前所学习的有记忆信源到底有什么不同之处呢？

这个不同之处就在于我们之前所学的一般有记忆信源是通过在一串符号序列中，通过描述符号之间的联合概率来来描述这种符号与符号之间的关联的。但是我们马尔科夫信源就不一样了，它很nb。它是通过符号之间的转移概率来描述这种关系的，也就是条件概率。（这里可能有点点抽象）换句话来说，就是马尔科夫信源是通过状态转移概率来发出每一个符号的。而转移概率的大小取决于它与前面符号的关联性。

转移概率的表现形式是P（xi | Sj）。也就是说已知某个状态，它接下来发出某个符号的概率。
好的在这里，我们一起来思考下，如果知道了此状态发出了每一个符号的概率，也就是上面表达式，那么是不是就意味着我们就能知道下个符号的信息了。
好的这个理解的话，我们再看，这虽说是符号的转换，但是，这个是否能看成，你是从这个状态到下个状态的转换呢，也就是整体向右移一下（通俗理解），可以看成c语言中的队列，先进先出。（这里可能听起来有点迷糊不要着急继续往下看）那么这里要引出一个概念，状态转移矩阵。状态转移矩阵就是由这些每种状态下的转移概率所组成的，每一行加起来都会是1。这个你去看看书上的图不会很难理解。这里的状态转移矩阵就是一种变换，它可以让你从一个状态转换成另外一个状态。每成一次矩阵，或者说每进行一次变换，就是一步转移。
好的，打住！回忆一下我们要干啥。我们要的是不是主要去研究这个信源。那么研究信源很重要的一点就是研究它的熵，考试中主要考的也就是如何计算这个熵。这里的熵指的是平均符号熵。
马尔科夫的极限熵
ok，在这里我们要知道，所谓极限熵到底什么，以及它到底是能用来干啥。极限熵的研究通常是针对有记忆信源。离散无记忆的信源的平均符号熵可以说是很好计算，就是计算一个消息的熵然后除以这个消息的符号个数（注意这里要弄明白消息和信源的关系，信源是发出符号的，而消息指的是一个符号序列）在实际应用中我们可以用平均符号熵来计算信源的熵，但是是有一定的误差的（对于离散有记忆信源来说）但是，当你的符号序列趋于无穷大的时候，那么是不是将平均符号熵看成信源的熵（这里有一些推倒过程，去犯下教材吧，有证明）相信大家都能接受。

还有一点要提一下，就是什么是m阶马尔科夫信源熵，m阶马尔科夫信源熵就是它的状态只与前面m个符号相关。那么它的状态空间就是n的m次方，n是信源所能发出符号的个数，这个不难理解。
好的这样我们来看下马尔科夫的极限熵。这个跟我们之前学过的由条件熵来求联合熵的方法一样（不明白的那我也没办法了，不多赘述，自己看下书吧，这个不难）那么我们是不是可以想象一下就是你用所有的状态的概率与在该状态下所能发出下个符号的熵进行相乘进行求和，就能得到这个信源的熵。那么关键就是这个状态的概率，其实，从直观上去想，每个状态的概率应该从统计平均上来说是固定的，这个可以通过MATLAB仿真跑一下就可以很清楚的看出来。证明我不是在胡扯。

那么现在是不是只要求出两类东西我们就能求出信源的熵了。一个是每个状态的概率，还有就是每个状态下所发出的符号熵就行了（这里不太清楚的好好自己想一下，或者回头去重新看下，能理解的）。好的那么我们就想，当这些状态的概率都趋于稳定的时候，你对它进行一步转移是不是得到的还是一个稳定的概率，因为n趋于无穷的时候，不就是稳定了的吗，这个应该也不是太难理解。所以用所有的状态乘以一步转移矩阵，所得到的还是这些状态，他们的值是不会发生变化的。这里可能会有的人想之前不是说乘以一个状态转移矩阵不是应该是从一个状态变换到另一个状态吗，那么好的。这里要明白的是一个状态转移到另外一个状态是从单个的状态乘以单个的转移概率来进行变换的。而在这里是状态空间与矩阵相乘。（准确来说是状态空间中的每一个状态的概率）所以状态空间中每一个状态的概率是不会发生变化的。那么就是W*P=W, W就是你的状态空间中每个状态的概率。这样就能求出来每一个状态的概率了。

ok，那么每一个状态下的所发出的符号熵的求法是怎么样的的呢这个其实就是把每种状态下的状态转移概率进行求信息量，然后全部加起来。这个如果不明白自己看看书上的例题，很容易就能想通的。

好的之后就可以相乘，求和，得出马尔科夫信源的熵了。

呼~~，终于写完了。码字不易，如果觉得对你有所帮助给一点点赞，博主会很开心的。
博客同步更新  YouKonSUN的个人博客

哈夫曼编码的源代码资源链接：哈夫曼编码

1. 哈夫曼编码过程

将信源符号的概率从大到小依次排列
取最小的两个符号按规律进行码元赋值，比如最小的两个当中较大的对应码元’1’，较小的那个对应码元’0’
重复步骤1，直到所有的概率值都进行码元的赋值
从后往前跟踪符号概率出现的位置所对应的码元，该码元序列就是对应概率的哈夫曼码
2. 二叉树概念



1. 二叉树:



定义


  
二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点之后，每个顶点定义了唯一的父结点，和最多2个子结点。然而，没有足够的信息来区分左结点和右结点。如果不考虑连通性，允许图中有多个连通分量，这样的结构叫做森林




程序结构

二叉树在程序里面是靠链表来实现的，而链表的基本单位就是结构体了，在程序中一个二叉树节点的基本结构就如下面的代码所展现的



struct BinTree
{
    int value;              //该节点的值
    struct BinTree *L_Tree; //该节点的左子节点(如果有的话就赋值，没有的话就为空)
    struct BinTree *R_Tree; //该节点的右子节点(如果有的话就赋值，没有的话就为空)
};



图像结构

一个基本的二叉树在宏观结构上如下图所示 




2. 二叉树的遍历


  
二叉树分为前序遍历、后序遍历、中序遍历


前序遍历：根节点->左子树->右子树
中序遍历：左子树->根节点->右子树
后序遍历：左子树->右子树->根节点
上图的二叉树结构如果分别用三种遍历方法进行遍历的话访问节点分别是

前序遍历：ABDGHEICF
中序遍历：GDHBIEACF
后序遍历：GHDIEBFCA
3. 二叉树的建立

先序建立：建立根节点->建立左子树->建立右子树
后序建立：建立左子树->建立右子树->建立根节点
先序建立的图像表达：(从左到右，从上到下)



后序建立的图像表达：(从左到右，从上到下)





3. 快速排序的概念



1. 快速排序的基本思想：


  
通过一趟排序将要排序的数据分为独立的两部分，其中一部分的数据都要比另一部分的数据大，然后对这两部分数据再次进行快排，分别分为独立的两部分，一直到整个数据序列变为有序的序列


举例：例如要排序的数据为(2,4,7,3,1,8,2,5)

第一次快速排序(基准值为 2，left 为 0，right 为 7),0 和 7 的来源就是要排序的数组下标范围，上面的数组下标范围就是 0 到 7，一共 8 个数。接下来就是 left 不断右移，也就是每次加一，找到大于 2 的数就把它放到此时 right 所对应的下标处。然后 right 不断左移，找到小于 2 的数就把它放到此时 left 所对应的下标，然后再转到 left，不断循环，直到 left 等于 right。我们现在先移动 right

2   2,4,7,3,1,8,2,5     left=0 right=6
2   1,4,7,3,1,8,2,5     left=0 right=4
2   1,4,7,3,4,8,2,5     left=1 right=4
2   1,4,7,3,4,8,2,5     left=1 right=1
2   1,2,7,3,4,8,2,5     left=1 right=1

然后分别对下标为 0-0 和 2-7(以7为基准) 的范围内的数据进行新一轮的快速排序，直到全部完成(0-0不需要再进行排序了)




2. 快速排序的程序实现(递归)



void quick_seq(struct huffman_bintree *t, int left, int right)
{
    struct huffman_bintree key = t[left];
    int low = left;     //不改变 left 的值，因为要用 left 是否等于 right 来作为排序的结束标志
    int high = right;   //我们用 low 与 high 来替代 left 与 right 的作用

    /* 如果 left >= right，程序就结束，不再进行快排 */
    if(left < right)
    {
        /* 如果左下标小于右下标，并且右下标所在的值大于等于基准值的话，就把右下标的值向左移动，一直到
         * 左下标等于右下标或者遇到右下标所在的值小于基准值的时候，替换右下标对应的值为左下标对应的值
         */
        while((low < high) && (t[high].weight >= key.weight))
        {
            high --;
        }
        t[low] = t[high];

        /* 如果左下标小于右下标，并且左下标所在的值小于等于基准值的话，就把左下标的值向右移动，一直到
         * 左下标等于右下标或者遇到左下标所在的值大于基准值的时候，替换左下标对应的值为右下标对应的值
         */
        while((low < high) && (t[low].weight <= key.weight))
        {
            low ++;
        }
        t[high] = t[low];

        t[low] = key;   //最后把基准值放回到左右下标对应的地方，此时左右下标相等，无所谓左边还是右边，放哪都可以

        quick_seq(t, left, high - 1);   //从基准值分开，对基准值左边的元素进行快排
        quick_seq(t, low + 1, right);   //从基准值分开，对基准值右边的元素进行快排
    }
}



4. 哈夫曼树相关概念



1. 哈夫曼树的建立


  
哈夫曼树是一种最优二叉树，哈夫曼树的节点建立是与每个节点的权重有关的


例如给定一组权重为(0.2,0.1,0.02,0.08,0.3,0.3)，其哈夫曼树的构建步骤如下所示



由上图可知，叶子节点的个数就是需要编码的字符的个数，而总的节点个数就是叶子节点个数 leaf*2 - 1 个，也就是说有 leaf-1 个节点是开始并没有的，而是在编码过程中产生的



2. 哈夫曼树建立的程序实现



/* 程序功能 ：建立一个哈夫曼树
 * forest ： 森林(森林指的是所有节点的总和),此处森林的节点个数就是 leaf*2 - 1 个
 * weight ： 权重数组的开始
 * character ： 字符数组的开始
 * leaf_node_num ： 叶子节点个数
 */
void huffman_tree_init(struct huffman_bintree *forest, float *weight, char *character, int leaf_node_num)
{
    int leaf_num = 0;
    int i = 0;
    int not_leaf_num = 0;

    not_leaf_num = leaf_node_num - 1;   //非叶子节点的数目是叶子节点数目减去1

    /* 初始化叶子节点，把叶子节点相应的权值、字符、叶子节点标志、左右子树全部初始化 */
    for (leaf_num = 0; leaf_num < leaf_node_num; leaf_num ++)
    {   
        forest[leaf_num].weight = weight[leaf_num];         //根据传入的权值初始化叶子节点的权值
        forest[leaf_num].character = character[leaf_num];   //根据传入的字符初始化叶子节点的字符
        forest[leaf_num].leaf_node = 1;                     //1 代表这个节点是叶子节点，这个在遍历哈夫曼树的时候会用得到
        forest[leaf_num].l_tree = forest[leaf_num].r_tree = NULL;   //叶子节点没有左右子树，所以赋值为空
    }

    /* 初始化非叶子节点 */
    for (i = 0; i < not_leaf_num; i ++)
    {
        quick_seq(forest, 2*i, i+leaf_node_num-1);  //对第 2*i 个到第 i+leaf_node_num-1 减一个 forest 元素进行快速排序，最终结果由小到大排列
        forest[i+leaf_node_num].weight = forest[i*2].weight + forest[i*2+1].weight; //新节点的权值等于经过快排之后最小的两个权值的和
        forest[i+leaf_node_num].character = 0;  //非叶子节点并没有字符
        forest[i+leaf_node_num].leaf_node = 0;  //非叶子节点，所以为0

        /* 其实下面这个判断并不是强制的，只是为了我们平常的手工编码习惯设置的，当然可以一直选择下面任意一个分支 */
        if(forest[i*2].weight - forest[i*2+1].weight == 0)
        {
            forest[i+leaf_node_num].l_tree = &forest[i*2];
            forest[i+leaf_node_num].r_tree = &forest[i*2+1];
        }
        else
        {
            forest[i+leaf_node_num].l_tree = &forest[i*2+1];
            forest[i+leaf_node_num].r_tree = &forest[i*2];
        }       
    }
}



3. 哈夫曼树的遍历

按照前序遍历的方式进行遍历，这里不再进行赘述



对哈夫曼树进行编码

也就是按照前序遍历的步骤，每遇到一个叶子节点就把当前已经遍历过的所有节点的编码值打印出来，然后退回一个码位，继续遍历，编码结果如下图所示





4. 编码的程序实现

/* 遍历哈夫曼树 */
void huffman_tree_trav(struct huffman_bintree T, char *h_code)
{
    int i = 0;

    /* 如果这个节点是非叶子节点 */
    if(T.leaf_node == 0)
    {
        h_code[huff_count] = '0';   //先走左边分支，当然也可以先走右边的分支
        huff_count ++;  //编码数量加一
        huffman_tree_trav(*T.l_tree, h_code);   //递归进行编码
        h_code[huff_count] = '1';   //当上面的函数返回的时候，会进行到这一步，这里走右分支
        huff_count ++;  //编码数量加一
        huffman_tree_trav(*T.r_tree, h_code);   //递归进行编码
    }
    else if(T.leaf_node == 1)   //如果是叶子节点，就打印目前 h_code 数组里面存放的所有字符
    {
        h_code[huff_count] = '\0';  //字符串结束标志
        printf("| letter : %c\thuffman_code : %s", T.character, h_code);    //打印编码

        /* 只是用作数据输出对齐，不用管这一部分 */
        for (i = 0; i < 37 - strlen(h_code); i ++)
        {
            printf(" ");
        }
        printf("|\n");
        huffman_code_length += T.weight*strlen(h_code); //计算平均码长
    }
    huff_count --;  //当此函数返回的时候已经到达叶子节点，我们需要返回该叶子节点的根节点，然后进行另一个分支的遍历，所以编码数要减去一
}