信源编码理论

信息论基础与应用，总结了信源编码的基本概念、无失真离散信源失真、限失真信源编码定理、信源编码方法等详细知识点。

信源编码理论

• 信源编码的基本概念
  • 信源编码
    • 定义：将信源的一个符号集映射成为一个新的码元符号集
    • 目的：降低不确定度、减少冗余（也就是改变了码长）
    • 一个序列码长的计算：L(C)=-求和(p(x)logp(x))
  • 码的分类
    • 按长度分
      • 固定长码（每个码元的长度是一定的）
      • 可变长度码
    • 码
      • 非分组码
      • 分组码（映射关系固定）
        • 奇异码（信源符号与码元不一一对应）
        • 非奇异码（一一对应）
          • 非唯一可译码
          • 唯一可译码（给出一组码，只有一种分法）
            • 非即时码
            • 即时码（不用看后面的比特就能分好当下的码）
  • 扩展码：是指在编码过程中，通过某些技术手段增加编码的长度或复杂度，通常是为了实现某种特定的功能或目标（感觉有点类似并联信道）
  • 码树（唯一可译码）
    • 根据码树的节点关系推导出了判别唯一可译码的是否存在的不等式【克劳夫特不等式】
  • 最佳码：平均码长降低到信源熵（信源熵代表的就是信源的平均信息量）（由于符号的概率分布通常是不均匀的，这样可以降低冗余）
• 无失真离散信源失真
  • 定长编码定理不等式
    • 定长码
      • 定义信源编码后的码的长度是一定的（信源有q种符号，进行N次扩展；编码有r种码元(进制)，平均码长为l），满足【r的l次方>=q的n次方】（码字总数>=消息数）
      • 平均码长L：指的是一个信源符号对应的码元长度【码元/符号】（若是有信源N次扩展，记得除N）
    • 编码信息率/码率：R=H(X)/L【信源信息量/平均码长】【bit/码元】【指编码后每个码元所携带的实际信息量】【也可以是最佳码长/实际码长】
    • 编码效率
      • n=R/logr【码率/该码元最大信息量】【编码后每个码元所带的信息量/编码后等概率分布的最大信息量】
      • H(X)/(Llogr)【信源信息量/每个码字携带最大信息量】【编码前每个符号的信息量/编码后每个符号所带最大信息量】
  • 无失真变长码编码定理
    • 变长码
      • 【克劳夫特不等式】判断即时码和唯一可译码
      • 计算平均码长：每个码字长度乘对应概率求和【码元/符号】（若是有信源N次扩展，记得除N）
    • 香农第一定理（变长无失真信源信源编码定理）不等式
    • 编码信息率/码率和编码效率同上
• 限失真信源编码定理
  • 失真测度
    • 失真函数d(xi,yj)：在信息传输的整个过程中，输入和输出不相等，就会有相关的失真函数
    • 序列失真函数（长度为N）：每个失真函数求和然后除N
    • 失真矩阵d(x,y)：类似转移矩阵，只是每个位置放的是失真函数
    • 平均失真D=每个失真函数乘对应的联合概率然后求和=每个平均失真求和/N（序列失真）=【求和（p(xi)p(yj|xi)d(xi,yj)）】
  • 信息率失真函数
    • 保真度准则：D实际<D规定
    • R(D)定义：在保真度原则下，在所允许的B中寻找一个合适的信道P(y|x)使互信息量最小（一个关于D的函数）【改变p(y|x)就会改变D】【注意信息量的概率计算公式=求和（p(x)p(y|x)logp(y|x)）】
    • 性质
      • 定义域[Dmin,Dmax]
        • Dmin：无噪的情况下（有损），那么就是一对多，那么在此情况下求最小的平均失真度，也就是转移矩阵中的每一行都是非1或0，且1对应的都是d(xi,yi)最小的（可以写出此时的转移概率矩阵，非0即1）
        • Dmax：此时的信息传输速率/互信息量最小，那么X与Y相互独立，那么【D=求和（p(yj)p(xi)d(xi,yj)）】，当求和（p(xi)d(xi,yj)）一定时，那么在此情况下求最小的平均失真度，Y的概率分布一定是非1即0 （可以写出此时的转移概率矩阵，非0即1）
      • R(D)是关于D的下凸的，单调递减的函数【离散：当D=0时，R(D)=H(X)；D=Dmax，R(D)=0】【连续：当D=0时，R(D)=无穷大；D=Dmax，R(D)=0】
  • 香农第三定理：离散无记忆平稳信源的信息率失真函数为R(D)，当传码率R>=R(D)时，一定存在编码方式使得译码失真度小于(D+一个任意小的数)
• 信源编码方法
  • 无失真信源编码方法
    • 香农码
      • 将每个符号的概率从小到大排列起来，并求出该数之前概率的累加起来（第一个是0）
      • 算出对应的自信息，进而确定每个符号的码长是大于自信息的最小整数
      • 码字是每个数对应的累积概率变成小数形式的二进制，从这个二进制数的小数部分选取一定码长作为符号对应码元
    • 菲诺（费诺）编码法
      • 按照概率将符号分为俩组，使俩组的总概率的差最小，分别给俩组赋0和1
      • 将每组再按照上面的方法分组赋值，不断重复，直至分完
      • 这样每个符号都会有被标记的符号串，从前到后，作为其码元
    • 赫夫曼编码（二进制）
      • 将每个符号的概率从小到大排列起来
      • 取最小的俩个概率，先分配标记0和1，再对这俩个概率求和，和剩余概率重新一起排列
      • 继续重复上面的步骤，直到和为1
      • 确定每个符号的码元：先确定符号对应的概率，再跟踪对应概率，找到收集被标记的数，然后从后到前排列，就是码元
      • 赫夫曼编码（M进制）：和上面一样，就是分配求和时选的是M个，不能完全分的话，第一次不选M个，比如【3进制，8个符号，那么第一次要选2个概率】
• 信源信息量<=平均码长