第二章 无失真信源编码4

《第二章 无失真信源编码4》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2.4算术编码Huffman编码更适合于大消息集信源，对于小消息集信源使用算术编码和游程编码压缩效果更好。主要内容：积累概率的递推公式算术编码原理算术编码的码长递推公式的应用不做乘法的算术编码2.4.1积累概率的递推公式信源符号积累概率设信源信源符号积累概率：2.4.1积累概率的递推公式信源序列积累概率传递公式设独立信源序列信源序列S添加一个新的信源符号ur后所得新序列Sur的积累概率。信源序列S的概率。信源符号ur的积累概率。信源序列S添加一个新的信源符号ur后所得新序列Sur的概率。信源符号ur的概率。信源序列的积累概率F(S)与信源符号的积累概率一样，可用[0,1)区间内

2、的个点来表示，因此积累概率F(S)将区间[0,1)分成许多不同的小区间，他们互不重叠，序列S的概率p(S)就是两点间小区间的长度。小区间内的一个点可用来表示序列的概率。2.4.2算术编码原理基本思路：把信源序列的积累概率映射到[0,1)区间上，使每个序列对应该区间内的一点，这些点把区间[0,1)分成许多不同的小区间，这些小区间的长度等于对应序列的概率，在小区间内取一个浮点小数，使其长度与该序列的概率相匹配。算术编码的主要任务是计算信源序列对应的小区间。2.4.2算术编码原理小区间划分的递推计算公式小区间左端点递推公式：小区间右端点递推公式：新序列Sur对应区间的左端点值。信源序

3、列S对应区间的左端点值。信源序列S对应区间的宽度值。信源符号ur对应区间的左端点值。新序列Sur对应区间的右端点值。信源序列S对应区间的左端点值。信源序列S对应区间的宽度值。信源符号ur对应区间的右端点值。2.4.2算术编码原理计算小区间端点值的步骤（1）给出信源符号对应的区间；（2）初始时，设S=Ø（Ø代表空集），low(Ø)=0，high(Ø)=1，range(Ø)=1（3）输入ur，根据公式计算序列Sur的左右端点值，依次下去，直到全部信源序列对应的区间被确定为止。2.4.2算术编码原理[例2-10]设信源求信源序列S=abda对应的小区间信源符号对应区间端点值符号概率区

4、间a0.5[0,0.5)b0.25[0.5,0.75)c0.125[0.75,0.875)d0.125[0.875,1)信源序列对应区间端点值信源序列lowhigha00.5ab0.250.375abd0.3593750.375abda0.3593750.36718752.4.2算术编码原理信源序列对应区间的划分0.75abcd00.50.8751aaabacad0.2500.3750.5abaabbabcabd0.250.3593750.375abcd0.3593750.36718750.375不同的信源序列分别对应不同的互不重叠的小区间，取小区间内的一个点作为对应序列的编码

5、。--------即时码S=abda的编码2.4.2算术编码原理译码步骤：（1）判断码字落在哪个符号区间，翻译出1个符号；（2）将码字减去刚翻译出的符号的左端点值；（3）用刚翻译出的符合对应的区间的长度去除步骤2的结果，判断此值落在哪个符号区间，翻译出一个新符号；（4）反复步骤（2）（3）直至全部信源序列被翻译完为止。2.4.2算术编码原理0.75abcd00.50.8751aaabacad0.2500.3750.5abaabbabcabd0.250.3593750.375abcd0.3593750.36718750.3752.4.3算术编码的码长码字长度应与序列的概率匹配取信

6、源序列码字的前L位，若后面有尾数，就进位到第L位。根据信源编码定理可知信源序列S的平均码长满足：平均每个信源符号的码长：对于DMS有2.4.4递推公式的应用用序列积累概率的递推公式进行序列的算术编码的计算步骤：（1）根据信源符号积累概率公式计算信源符号的积累概率；（2）初始时，设S=Ø，F(Ø)=0，p(Ø)=1；（3）根据序列的积累概率递推公式，计算序列的积累概率F(ur)和序列的概率p(ur)；（4）计算码长；（5）将F(s)写成二进制数形式，取其前L位作为序列S的码字，若后面有尾数就进位到第L位。2.4.4递推公式的应用例[2-12]设二元独立信源求信源序列S=1010的

7、算术编码。解：信源符号的积累概率F(0)=0；F(1)=0.25信源序列1010算术编码序列F(S)p(S)L序列码字Ø01010.010.1111100.010.00112011010.0100110.001001301110100.0100110.00001001501010S=Ø，F(Ø)=0，p(Ø)=12.4.4递推公式的应用算术编码具有渐近最佳性：当序列无限增长时，平均码长渐近地等于序列的熵值。实际存在问题：递推运算中都有乘法——运算量大解决办法：1）编码对象是二元序列，符号概率