chap信源编码.ppt

游程编码------------------- MH编码 MH编码: 文件传真是指一般文件、图纸、手写稿、表格、报纸等文件的传真，这种信源是黑白二值的，也即信源为二元信源（q=2）。 MH编码是一维编码方案，它是一行一行的对文件传真数据进行编码。编码将游程编码和霍夫曼码相结合，是一种改进的霍夫曼码。 游程编码------------------- MH编码 MH码以国际电话电报咨询委员会（CCITT）确定的8幅标准文件样张为样本信源，对这8幅样张作统计，计算出“黑”、“白”各种游程长度的出现概率，然后根据这些概率分布，分别得出“黑”、“白”游程长度的霍夫曼码表。 MH码分别对“黑”、“白”像素的不同游程长度进行霍夫曼编码，形成黑、白两张霍夫曼码表。MH码的编、译码都通过查表（P134-135，表5.4.1，表5.4.2）进行。 MH码编码规范 游程编码中MH编码其基本的编码规范为 (1) 游程长度在0～63时，直接查表用相应的结尾码作为码字； 如：20白40黑 (2) 游程长度在64～1728范围内时，用组合码加上结尾码作为相应的码字； 如：856黑 MH编码编码规范 （续） (3) 每行的第一个游程规定为白游程(长度可以为零)，每行用一个结束码(EOL) 终止；  (4) 在传输时，每页数据之前加一个结束码，每页尾部连续使用6个结束码。 MH编码编码规范 （续） 5)译码时，每一行的码都应恢复出1728个像素，否则有错。 6)为了在传输时可实现同步操作，规定T为每个编码行的最小传输时间，一般规定T最小为20，最大为5。若编码行传输时间小于T，则在结束码之前填上足够的“0”码元(称填充码)。 如果采用编码仅仅是用于存储，则可省去步骤中的4)至6)步。 MH码---------------------------例题 设某页传真文件中某一扫描行的像素点为： 17白 5黑 55白 10黑 l641白 解:通过查表可得该扫描行的码为： 该行经编码后只需用54位二元码元，而原来一行共有1728个像素，如用“0”表示白，用“l”表示黑，则共需1728位二元码元。可见，这一行数据的压缩比为1728:54＝32，因此压缩效率很高。 多元游程序列 多元序列也存在相应的游程序列 多元序列变换成游程序列再进行压缩编码没有多大意义 游程编码只适用于二元序列，对于多元信源，一般不能直接利用游程编码 5.4.2 算术编码 算术编码 非分组码的编码方法之一——算术码 原理： 从全序列出发，考虑符号之间的依赖关系来进行编码 从整个符号序列出发，将各信源序列的概率映射到[0，1）区间上，使每个符号序列对应于区间内的一点，也就是一个二进制的小数。这些点把[0，1）区间分成许多小段，每段的长度等于某一信源序列的概率。再在段内取一个二进制小数，其长度可与该序列的概率匹配，达到高效率编码的目的。 算术编码------------------概率区间 由于Fi和 Fi-1都是小于“1”的正数，可用[0，1）区间内的两个点来表示，而pi-1就是这两个点之间的长度，如图所示。 算术编码--------------------递推公式 我们可取该小区间内的一点来代表这个信源符号序列，那么选取此点方法可以有多种，实际中常取小区间的下界值。对信源符号序列的编码方法也可有多种，下面介绍常用的一种算术编码方法。 算术编码--------------------二元码 算术编码---------------二元码递推公式 算术编码--------------------编码方法 将信源符号序列S的累积概率值写成二进位的小数F(S)=0.c1c2……cL,ci∈{0,1} ，取小数点后L位，若后面有尾数，就进位到第L位，并使L满足: 式中 表示大于或等于x的最小整数。 这样得到信源符号序列所对应的一个算术码： 取S二进制表示小数点后L位，得到信源符号序列的算术码字为1101010 本例对输入信源符号序列进行算术编码后平均码长为： 编码效率为： 算术码的译码: 对二元算术码而言，其译码过程是一系列比较过程： 每一步比较C-F(S)与A(S)p(0) ， 这里S为前面已译出的序列串，A(S)是序列串S 对应的宽度，F(S)是序列 S的累积概率值，即为 S对应区间的下界限， A(S)p(0)是此区间内下一个输入为符号“0”所占的子区间宽度。 译码规则为： 若 C-F(S) ＜ A(S)p(0) ，则译输出