信息理论与编码教案.ppt

码符集合X={x1 , x2 , … , xr }。对信源 SN 进行编码，必 有一种方法，使其构成惟一可译码， 且使得信源的每个符 号所需的平均码长满足如下不等式 证明 将 SN 视为一个新的信源， 对上述不等式各边除以N，有 或 因为 所以 当N→∞时 将以上不等式各边乘以log r，有 结论：采用扩展信源编码，当 N 足够大时可使平均码长 接近下限。 3.编码信息率 根据 信源熵 和 对信源 SN 进行变长编码后，平均到单个符号的平均码长携带的信息量称为编码信息率，记为R 无噪信道的输入和输出是一一对应的，其信道矩阵的 特征是为单位矩阵。 对于有 r个输出(输入)符号的无噪信道的信道容量为 对于无噪信道，通过信源编码，使 R?log r，减少 信源剩余度，使信息传输率尽可能接近信道容量。 因此，无失真信源编码定理通常称为无噪信道编码定理。 定义 对信源 SN 进行变长编码后，平均一个信源符号能 携带的最大信息量称为编码率，记作Rs， (单位: bit/符号) 对于二元码符， r＝2，有 log2 r＝1，则 Shannon 第一定理也可以描述为，若 则存在惟一可译码，若H(S) Rs 则不存在惟一可译码。 定义 编码效率定义为 定义 对于变长码，定义码的剩余度为 注意：对于r＝2时 编码效率? 是小于或等于1的无量纲的数 4. 编码效率与编码剩余度 在数量上 例 无离散记忆信源 s1s1 s1s2 s2s1 s2s2 Wi 00 01 10 11 信源熵 H(S)=0.811 bit/符号 定长码 s1→0，s2→1 L =1 编码效率 η=H(S)/L= 0.811 N=2 S2 s1s1 s1s2 s2s1 s2s2 p(S2) 9/16 3/16 3/16 1/16 H(S2)=1.622 bit/2个符号 H(S) =0.811 bit/符号 定长码 L2 = 2码符/2个信源符号 编码效率 η= H(S2)/L2 =H(S)/L = 0.811 bit/符号 s1s1 s1s2 s2s1 s2s2 p(S2) 9/16 3/16 3/16 1/16 Wi 0 10 110 111 li 1 2 3 3 变长码 码符/ 2个信源符号 =0.844码符/ 信源符号 编码效率 H(S)=0.811 bit/符号 若 N=3 则η=0.985 ，若N=4 则η=0.991 1. Shannon 编码方法 若si 按如下不等式取所对应码字的码长为l i 当 r 等于 2 时 , log r =1 5.4.5 变长码的编码方法 采用扩展信源提高编码效率带来的问题 1.码表迅速扩大 2.需求内存大 3.译码延时 (1) 将信源符号消息按其出现概率的大小依次排序； p(s1)≥ p(s2) … ≥ p(sq) (2) 按如下不等式取所对应码字的码长为li ； (3) 计算第个 i 消息的累加概率, 以便获得唯一可译码 . (4) 将累加概率变换为二进制数； (5) 取二进制数的小数点后 li 位作为符号消息的二进制码。 Shannon 编码过程 Shannon 编码过程 si p(si) I(si) li Pi Pi二进制 码字 s1 0.20 2.32 3 0 0.0000 000 s2 0.19 2.40 3 0.20 0.0011 001 s3 0.18 2.47 3 0.39 0.0110 011 s4 0.17 2.56 3 0.57 0.1001 100 s5 0.15 2.74 3 0.74 0.1011 101 s6 0.10 3.32 4 0.89 0.11100 1110 s7 0.01 6.64 7 0.99 01111110 例 si s1