信息处理编码信源编码

第五章信源编码

目的：提高通信系统有效性，实现信源与通信系统间的统计匹配。

§５－１无失真信源编码

一〕首先，我们研究离散、无失真、无记忆信源编码的一般模型：假设不考虑信源统计特性：应满足：相互矛盾！由 ----①

〔一〕离散、无失真、无记忆信源编码的一般模型〔续〕结论：①当n=m时，K≥L不有效。②当K=L时，m≥n，亦不满足有效性。解决方法：引入信源统计特性。考虑信源统计特性：即无需对全部组合的n的L次方种信息一一编码，而仅需对其中少数大概率事件集合中元素进行编码即可。这时，我们可以修改①式为：K/L≥H(U)/logm----②即考虑信源不等概率，而码字为等概率，这就是等长码的仙农无失真信源编码定理：对离散，无记忆、平稳、遍历信源其符号序列：U=(U1,U2…..UL)，可用K个符号C=(C1,C2….Ck)进行等长编码，对任意ε>0,δ>0，只要满足：(K/L)logm≥H(U)+ε----③那么当L足够大时，可使译码过失小于δ，反之，当(K/L)logm≤H(U)-2ε----④时，译码一定出错。这就是等长码信源编码定理。〔一〕离散、无失真、无记忆信源编码的一般模型〔续〕〔一〕离散、无失真、无记忆信源编码的一般模型〔续〕定理证明,主要引用了序列信源中的随机序列的渐近等同分割A.E.P特性.所谓A.E.P是指任何一个离散随机序列信源当序列长度Ｌ→∝时,信源序列会产生两极分化.大概率事件集合与小概率事件集合,即nL=∪对于有性质:①

②

(信源熵)(大概率事件熵)③

(等概率)对于有性质:〔一〕离散、无失真、无记忆信源编码的一般模型〔续〕由此可见，信源编码只需对信源中少数落入典型大概率事件的集合的符号进行编码即可。而对大多数属于非典型小概率事件集合中的信源符号无需编码，且。由A.P.E推出的辅助不等式：

选典型序列中个u编码，即

为此,有以下变长码熵匹配编码定理形式:其次，再讨论变长码，这时公式②可进一步修改为:

〔一〕离散、无失真、无记忆信源编码的一般模型〔续〕-------⑤

对于二进制,可进一步简化为：

-------⑥故称它为熵匹配编码。它就是变长码信源编码定理。可见，上述无失真信源编码定理，不仅是存在性定理，而且是构造性定理。

例：设有一简单离散信源：L=1,n=4对其进行近似于无失真的等长编码，假设要求其编码效率为95%，过失率低于10-6，试求符号联合编码长度L=？解：,σ2=0.6875bit2由编码效率：

即：可见,需要100万个信源符号联合编码,才能到达上述要求,这显然是不现实的.下面,假设进行变长编码又如何呢?再由:变长码010110111

可见，假设采用变长编码，逐位〔L=1〕即可到达100%效率，当然这里仅是一个特例，不过它已足以说明变长码的优越性。如何译码？有两类方法：①加标志信息②寻找内在规律下面，我们给出几种类型的信源编码：其中编码Ⅰ为等长码，码长K=2，但与pi不匹配，编码Ⅱ至Ⅴ为变长码，但是编码Ⅱ的U1和U2均编为“0〞，编码不单义〔奇异〕不能用；信源概率pi编码Ⅰ编码Ⅱ编码Ⅲ编码Ⅳ编码ⅤU11/2000000U21/401011001U31/810100110011U41/81110111110111编码

Ⅲ，发（编码）单义，但是收（译码）不单义，比如收到“00”可能译为亦不能用。编码Ⅳ与Ⅴ，收、发均满足单义，故可用，但是两者是有差别的。虽然都是唯一可译码，但是编码Ⅳ是一类实时唯一可译码，又称为异前置码或非延长码。

所谓异前置是指某一码组的后面向前面看：比方u4=111，被采用后，其前面的任意组合比方11，或1均不能再采用；所谓非延长码，那么是某一码组的前面向后面看：比方u1=0，被采用后，那么从0以后的任何延长出去组合，比方00、01、001等均不能再用。它是最正确变长码。编码Ⅴ也是满足唯一可译性，但不满足异前置或非延长特性，译码时，需要延时判决，所以它不是实时可译码。比方收到“0〞不立即判决，而是延迟一位，根据收到的第二位在判决第一位假设为“00〞那么判第一位为0，即u1；假设为“01〞仍不能判，再观察第三位，假设为“010〞，那么判“01〞为u2，假设为“011〞再观察第四位，假设为“0110〞判为“011〞为u3，假设为“0111〞判为u4。下面，进一步研究实时唯一可译码的码字可别离条件，它可引用很直观的“码树〞概念来说明：将变长码与码树建立“一一对应〞关系：树根码字起点树枝数码的进制数节点码字或码字的一局部终止节点码字节数码长非满树变长码满树等长码下面，我们寻找一种与上述“树图〞等效的解析式表达式----Kraft不等式。分析起来特别对含有很多符号种类的复杂信源更方便。定理：长度为Ki〔i=1,2,…,n〕的m进制异前置码存在的充要条件为：----⑦。证明，下面仅给出必要性证明，充分性见书，若设码树共有K节，则总码枝数为mk个。若某个长度为Ki的码枝被选用，则自该支第Ki节点以后所有码枝不能再选用，即有码枝不能再选用。由于Ki中i是任意的（i=1,2,…,n），所以全树中不能再选用的总码枝数应为：

，显然其值一定要小于全树总码枝数mk，即有

编码规那么：1)

将信源消息U按概率大小排序〔由大至小〕。2)从最小两个概率开始编码，并赋予一定规那么，如下支路小概率为“1〞，上支路大概率为“0〞。假设两支路概率相等，仍为下支为“1〞上支为“0〞。3)将已编码两支路概率合并，重新排队，编码。4)重复步骤3〕直至合并概率归一时为止。5)从概率归一端沿树图路线逆行至对应消息编码，如U3为“110〞。例2〔续〕例三〔续〕可见，编成的码C和C’不一样，这说明哈夫曼编码并不唯一，这是由于哈夫曼编码是与信源统计特性相匹配的编码，而不是某个信源固定特性相匹配，不唯一性是明显的，但是只要在编码和译码过程中遵守同一规则，译码是唯一的。虽然C和C’不一样，但是两者都是哈夫曼编码，并且码长相等。

Kc’=0.4×1+0.2×2+0.2×3+2×0.1×4=2.2Kc=0.4×2+0.2×2×2+0.1×3×2=2.2但是，若从二阶矩来看，即方差来看，C’的方差大，C的方差小，所以C优于C’例三〔续〕下面讨论哈夫曼编码应用中的一些问题：1)首先讨论误差扩散：哈夫曼编码是一种无失真信源最正确编码，但是在实际信道中是有失真的。噪声的引入必然要破坏长码结构，而且是变长码，错误不但影响受干扰位，还要进一步扩散。目前对扩散还没有很有效的方法，工程上克服方法有两种：一是限制哈夫曼码仅能应用于优质信道〔<=10-6〕以限制扩散的可能性；二是采用定期清洗，防止扩散区域增大。但是它是靠牺牲有效性换取的。2)其次是速率匹配问题：由于绝大多数信源是不等概率的，由它编成的码长度与速率是可变的。然而实际信道那么要求其输入端速率是固定的。所以信源与信道之间还存在一个速率匹配问题。在工程上解决这一问题的方法是在两者之间加一个类似与水库的缓存器，它变速入，恒速出，以解决两者速率的匹配。3)第三是与信源统计特性匹配的问题。其中：〔1〕、小消息〔符号〕集信源不易匹配可采用信源消息集不断扩展的方法来解决，但是太复杂。〔2〕、信源统计特性未知时，怎么办？可采用所谓通用编码的方法来解决。上一节我们利用树图的理论寻找出一类唯一可译的变长码的编译码方法。即：〔同构〕树的生成结构规律唯一可译码变长〔树图理论〕〔一一对应〕编、译码方法这一节中我们利用数学中最简单的算术规律来构造一类无失真的信源编码。 〔同构〕算术规律 非分组的信源编码〔一一对应〕算术编码

下面，首先从一个PCM编码例子入手：

000→0×20+0×21+0×22→0→0→0×2–1+0×2-2+0×2-3001→1×20+0×21+0×22→1→1/8→0×2–1+0×2–2+1×2–3010→0×20+1×21+0×22→2→2/8→0×2–1+1×2–2+0×2–3011→1×20+1×21+0×22→3→3/8→0×2–1+1×2–2+1×2–3100→0×20+0×21+1×22→4→4/8→1×2–1+0×2–2+0×2–3101→1×20+0×21+1×22→5→5/8→1×2–1+0×2–2+1×2–3110→0×20+1×21+1×22→6→6/8→1×2–1+1×2–2+0×2–3111→1×20+1×21+1×22→7→7/8→1×2–1+1×2–2+1×2-3PCM码编码公式对应量化层归一化编码公式上面例子是一个简单的三位PCM的例子其编码可表示为：〔简单算术表达式〕⑧

三位码共有八层:

……

可见，这时信源编码过程就可以看作是上述对应二进制小数作移位相加的过程。故称它为算术编码。

仔细分析，上述例子仅是一个特例，因为它没有考虑信源的统计特性，〔它认为信源是遵从等概率分布的〕所以编出的码字是等长码，而对应的算术运算那么是简单的整数项相加。〔即Ki为整数〕。为了解决对一般的具有统计特性的信源的算术编码问题，需要将上述算术编码方式进一步拓广，并要解决信源统计特性与编出的码字相匹配。其中最关键的是要将算术编码与信源的符号概率及累积概率建立一一对应关系。算术编码就是基于这一思路。不过，在引入统计特性后的算术编码中，每次移位的位数可以是非整数〔精度有限的有理数〕，正是由于这种非整数的引入使算数编码变成了非分组码。更确切地说，在每步编码运算中除了实际移动的某一整数位以外，还以内部状态形式保存了应该移动的“分数〞位，并将其累积到下一步编码运算中。这样，只要非整数的精度足够高，那么就可以与信源消息匹配到任意良好的程度。下面，从一个单消息〔符号〕信源入手，简述算术编码原理及编码方程的建立：设信源序列为:S=S1S2…Si…其中Si∈{1,2,…,j,…,N},即有N种类型,下面,首先将信源符号按对应概率大小排队:S1S2…Sj…SN即:对应累计概率=由于信源是由单个符号组成并相互独立,假设设信源序列为：S=S1S3S2S3=S’S3P(S)=p(S1)+p(S1)p(S3)+p(S1)p(S3)p(S2)+p(S1)p(S3)p(S2)p(S3)=p(S1S2S3)+p(S1)p(S3)p(S2)p(S3)=p(S’)+p(S’)p(S3)---------⑨其中p(S’)=p(S1)p(S3)p(S2)=[p(S1)p(S3)]·p(S2)推广之:p(S)=[p(S1)p(S3)p(S2)]·p(S3)=p(S’)·p(S3)----------⑩这样，将一定精度数值作为序列的算术编码，完全可类似于上述归一化分层的整数算术编码。在数学上看，它实质上是一个分割单位区间的过程。完成它必须两个递推过程：一个代表码字C(·),另一个代表状态空间A(·).假设采用累积概率Ps表示码字C(s),符号概率P(s)表示状态区间A(s),由公式⑨⑩可求得：其中sx表示s的后续〔增长〕序列。公式⑾的递推公式是算术编码的根底。----------------⑾

例：假设有一单消息〔符号〕信源，含四种符号：a、b、c、d，构成一序列S=abda且：。试说明算术编码及其具体编、译码过程。解：假设起始状态为空序列Ф，且令A(Ф)=1,C(Ф)=0下面，首先给出以下符号，符号概率pi，累积概率Pj如下：由上述概率表与公式⑾，可计算出以下一系列数值：符号符号概率pi符号累积概率Pjabcd0.100(1/2)0.010(1/4)0.001(1/8)0.001(1/8)0.0000.1000.1100.111C(Φa)=C(Φ)+A(Φ)Pa=0+1×0=0A(Φa)=A(Φ)pa=1×0.1=0.1C(ab)=C(a)+A(a)Pb=0+0.1×0.1=0.01A(ab)=A(a)pb=0.1×0.01=0.001C(abd)=C(ab)+A(ab)Pd=0.01+0.001×0.111=0.010111A(abd)=A(ab)pd=0.001×0.001=0.000001C(abda)=C(abd)+A(abd)Pa=0.010111+0.00001×0=0.010111A(abda)=A(abd)pa=0.000001×0.1=0.0000001上面，我们给出了整个编码过程，实际上它可以看作是对以下单位区间的划分过程：算术编码的译码过程如下：根据编码后的数值大小比较来进行，即判断码字C〔s〕落在哪一个区间就可以得出一个相应的符号序列。具体步骤如下：1.

C〔abda〕=0.010111<0.1

可译出第一符号为a；2.

去掉被乘概率加权因子：C〔abda〕×2=0.010111×10=0.10111在[0.1，0.11]

间，第二个符号译为b；3.

去掉累积概率后再去掉被乘加权因子：0.10111-0.1=0.001110.00111×4=0.00111×100=0.111在[0.111，1]之间，第三个符号译为d；4．同上0.111-0.111=0.000.00×8=0.00×1000=0.00在[0，0.1]之间，第四个符号译为a。综上所述，译码后的总输出为：S*=abda=S〔发送的原序列〕在实际应用时，信源不是简单的单消息〔符号〕信源，而是符号序列信源，这时上述递推公式⑾应修改为：并设所有序列从空序列开始，即A（）=1，C（）=L（）=0若x表示子序列S后面的待编码符号。若P（x/S）<1/2称为小概率符号，且记x为l，否则记x=h

公式中L表示码长,[]表示截短后的有限精度.矢量量化是一维标量量化的拓广,是对多个样值进行的联合量化.标量量化是对逐个样点值进行的量化,而矢量量化那么是对每K个样点值为一组进行的多维联合量化处理.它在数学上可看作K维空间中的映射:矢量量化编码

其中u为K维空间(欧氏)中的一个连续矢量,ul为K维空间(欧氏)中的一个离散量化矢量.对于每个l，在K维空间中有一个区域Cl，它作为K维空间划分的一个子空间.且当u∈Cl就判别它为ul,人们称这种分割矢量空间的方法为Voroni(胞腔)子空间法。可见，矢量量化可以理解为K维欧氏空间Rk中的一种映射变换。它将Rk中的连续矢量u变换成离散的量化矢量ul，且称量化矢量ul为码本和重建码本，而l=1,2,……,L，L那么表示码本的尺寸〔大小〕。Log2L为码本信息量，即码本的二进制码元数，对于矢量量化：可以实现，这点在一维标量量化时是不可能到达的，主要原因是由于矢量量化充分利用了信源样点间统计关联特性。显然有:

⒀为了便于理解，可将上述矢量量化过程按以下图形分解为编、译码两个子过程如下：ulullu编码器（u）理想信道译码器（l）l重建码本码本图中的码本是按照一定的失真度量准那么，通过事先进行大量的训练而建立，并含有所有可能量化矢量值ul，l=1,2……L，这时，信道既不直接传送Ｋ维连续样值ｕ，也不传送离化量化矢量ｕl，传送的是在码本中挑选失真最小的那个量化矢量的编号值l，接收端，由l通过译码器在重建码本中再挑选失真最小量化矢量ｕl作为恢复矢量值。即：QK：ｕl＝β(l)＝β[(ｕ)] ⒁在某种失真准那么下，可以认为：β·α＝１那么：ｕl＝β[α(u)]＝ｕ显然当K＝１时，即为简单的标量量化。⒂

1)

矢量度量准那么的选取2)

多维空间的划分3)

最正确量化器的设计4)

算法研究矢量量化中的几个主要问题是：下面，我们给出一类典型矢量量化实现方案：

码本序号l训练数据群聚迭代建立码本码本矢量量化编码输入连续矢量u

ul可见，矢量量化器发送端主要包括两局部：码本设计与矢量量化编码。码本设计需要大量的反复的输入训练数据进行群聚迭代设计，反复计算质心，因此要消耗大量的时间，然而码本设计并不要求实时，它可以事先预制。矢量量化编码那么严格要求实时实现。因此在量化器中的运算量以及决定它的算法，就变得极为关键，这就是说，矢量量化器能否实际应用关键在于算法。近些年来算法研究进展很大，各种类型最正确全搜索快速算法以及准最正确的各类快速算法不断提出，同时，由于大规模集成电路技术的飞速开展，促使矢量量化技术已逐步走向实用化。它是一类有记忆信源的限失真编码。有记忆信源最主要的是解除信源的相关性，而预测编码主要是从时域来解除相关性，压缩信息率。预测编码

〈一〉预测编码的根本原理信源输出预测器量化编码输出它不直接对信源输出ui进行量化编码，而是对其差值:进行量化编码。其中为预测值。

由信息论：

差值熵：

由信源熵匹配编码有：(16)

其中表示预测前信源编码平均码长其中表示预测后信源编码平均码长从概率观点看，预测可理解为：

由于信息熵是概率分布的泛函数，预测前，信源分布越不均匀，熵越大；预测后，预测越准确，分布越集中，熵值就越小。即。通过预测后，信源数据压缩的倍数就越大。实现预测编码要进一步研究如下三个问题：１〕

预测函数的选取；２〕

预测误差准那么的选取；３〕

预测器输入数据源的选取。第２〕个问题决定预测器质量的标准，第１〕、３〕两个问题那么主要决定预测质量的好坏。下面，我们首先讨论预测函数的选取：

在工程上一般是采用容易实现的线性预测，这时：可见，当预测函数f确定为线性函数以后，预测精度主要决定于K值大小：K越大，预测越准确，但设备也越复杂；

K越小，预测越不准确，设备也就越简化。

其次，讨论预测误差准那么的选取:目前大致有以下四种类型：MMSE〔最小均方误差〕准那么；PSEM〔功率包络匹配〕准那么；PCIV〔预测系数不变性〕准那么；ME〔最大误差〕准那么。其中最常用的是MMSE准那么，PCIV主要特点是与输入信号统计特性无关，它可对多种混合信号进行有效预测。而ME准那么那么主要用于遥测数据压缩。最后,讨论预测器输入数据流的选取,它可以划分为三类:<二>预测编码的根本类型1〕△PCM型ui-1ui-2…ui-Kα1α2αk…量化编码器DPCM中预测系数的计算线性预测值为，为过去p个样值的线性组合，为预测系数假设选择均方误差准那么假设信源输出广义平稳r(m)为样值un的相关函数，上式对ai求偏导r(m)可通过估算将r(m)代入，可得ai求预测系数的线性方程称作正态方程，Yule－Walker方程。Levinson和Durbin提出一种算法能有效的解上述方程。Levinson-Durbin算法Levinson-Durbin算法是一种用来确定线性方程组解的阶递归算法。其中是一个阶Toeplitz矩阵。是预测器系数向量，可表示为是一个p维向量，其元素为对于一阶()预测器，我们得解一阶预测器的剩余均方误差(MSE)为一般的，可以用m-1阶预测器的系数来表示m阶预测器系数的解。于是，把表示为两个向量之和，即式中，向量和标量待定。于是，还可以表示为式中，刚好是反序的向量现在由上式可以得到两个方程。第一个方程为如下矩阵方程从而上式可以简化为这个方程的解为刚好是反序。从而，上式的解就是反序的乘以，即(1)由前式得到的第二个方程为如下标量方程利用前式(1)，可从上式消去。结果的方程给出，即式中是剩余MSE，由下式确定用前式(1)代替最小MSE也可以递归计算，于是得到如下递归关系及在上式中利用递归关系，得到上式中方括号内的项就是前式中的分子，因此它可简化为

量化…线性预测器线性预测器uiyi

xi

ei

这是一类最简单的线性预测器。其预测器输入直接来自信源输出，预测函数为线性加权和，其预测精度主要决定于预测项数K。其主要缺点是量化噪声较大。

1〕△PCM型〔续〕2〕DPCM型：uieixi量化器线性预测器线性预测器yiDPCM与△PCM比较，不同点有：①线性预测器的输入数据源来自输出反响端②对于量化器而言，△PCM是开环型而DPCM是闭环型。可利用反响环进一步压低量化误差。从而进一步提高DPCM的预测性能。<二>预测编码的根本类型〔续〕--延时延时滤波DPCM的特例ΔM:

2〕DPCM型〔续〕若将量化等级定为2,即差值为正时,用”1”代表;差值为负时,用”0”代表;而每个差值只需1比特,这时DPCM即为ΔM，又称它为增量调制.为了减少量化误差,一般要增加取样频率,不能再来用常用的最高频率的2倍，即

>2fm.在收端，译码是编码的反变换，即规定一个增量Δ值，当收到一个“1”则在前一个值中加一个Δ，收到一个“0”，则减去一个Δ值。2〕DPCM型〔续〕3〕噪声反响编码(NFC)<二>预测编码的根本类型〔续〕NFC是吸取△PCM与DPCM的优点，即在△PCM结构简单的根底上,改进其量化噪声大的缺点，将量化器设计在另外增加的一个反响环内,以到达进一步压减量化误差的目标。这一点上类似于DPCM.可见NFC是△PCM与DPCM的混合改进型.<二>预测编码的根本类型〔续〕4)预测误差门限型(非线形)

设信源输出序列为:若仅采用前一位作为后一样值的预测值,则预测误差若,不传送;

若,传送.4)预测误差门限型(非线形)〔续〕其中是允许误差的门限值,即可接受的最大误差,在上述图形中虽然有，前四个应传送，不传送。若选择的预测值不仅仅是前一位，而是前n位的线性加权和，则可构成高阶预测误差门限型，其原理同上，实现方框图如下：

显然这一类型中线性预测器与前三类是一致的，但是由于引入了非线性门限比较器，所以它实质上是一类非线性预测器。<二>预测编码的根本类型〔续〕下面我们给出四种类型中最常用的一种DPCM的性能分析：线性预测可表示为：

其Z变换为：可见线性预测器的响应为：

式中αj为第i项加权系数，N为预测阶次。由DPCM接收部分框图。可求得：故：

<二>预测编码的根本类型〔续〕可见，线性预测器为一全极点滤波器。故又称为全极点模型。下面再分析一下DPCM的几个主要关系式：

预测误差：经量化后：其中qi为量化噪声引入的误差。经无过失传输后接受端恢复后的重建信号为：可见，进一步性能分析可参见教材。

变换编码是从广域频域〔或空域〕解除信源相关性的一种有效的手段。主要数学工具是正交和准正交变换。变换编码下面，首先从一维信源输出开始分析：设信源输出：，变换后输出：则有：由正交性有：如果，通过正交变换只传送M<ｎ个样值，而将ｎ－Ｍ个较小样值丢弃。于是有：这时接收端恢复的信号为：

变换编码〔续〕这里，所以问题可以归结为如何选择正交矩阵Ａ，使经正交变换后Ｍ值较小，且被丢弃的ｎ－Ｍ个值是足够小的。为了更清晰，我们进一步引入二维分析：

其中为的协方差矩阵。为的数学期望。为ｘ的协方差。则：

变换编码〔续〕可见经正交矩阵Ａ变换后，使信源的协方差矩阵变换成纯对角线矩阵，且对角线上元素能按顺序由大到小排列。下面，我们首先寻求正交变换|A|矩阵形式，即在最小均方误差下准则MMSE下寻求最佳的正交变换。即:

变换编码〔续〕首先求最正确bi值：求得：此取bi为xi的数学期望值，其次再求最佳ai值：

求得：或

变换编码〔续〕最后求得：

,其中

此为一理想对角线矩阵，它完全消除了信源的相关性，称它为Karhunan-loeve(K-L)变换，这时,最小均方误差值为:最小项.变换编码〔续〕上述最正确的K-L变换实际上很少应用而仅将它作为理论上最优值得一个参数标准,其原因有1.最正确A矩阵显然与信源统计特性φ密切相关,不同的φ值应有不同的最正确A矩阵,这显然是不现实的.2.K-L变换目前尚没找到相应的快速算法.正因为实现最正确不现实,因此人们将眼光转向准最正确变换,何谓准最正确变换并没有确切的定义,而只是指能找到一类在数学上经线行代数中相似变换后的Jordan标准型.即:变换编码〔续〕在上,下对角线区域内仅会有少数不为0得元素1.目前已找到一批满足上述特性的准最正确变换(不唯一).大致可以划分为两类：变换编码〔续〕可见，由线性代数理论，由相似变换，总能找到一非奇异矩阵A，使，并称与相似，同时由于变换后的Jordan型无确切定义，因此可以找到一批满足上述标准最佳变换。

下面将分别介绍这些准最正确变换，设U为信源消息矩阵，X为经变换后的信号矩阵，在一般情况下有：原那么上，A与B可以是不同类型矩阵，实际上差不多都是同一类型、同一阶次矩阵，即A=B。由于上述变换是随机矩阵变换，所以通常给出其二阶矩阵形式的协方差矩阵的等效形式：变换编码〔续〕1〕离散付氏变换DFT:这里：其中下面讨论不同形式A:变换编码〔续〕变换编码〔续〕变换编码〔续〕例：以n=4DFT为例；假设显然，它是一个非常好的准最正确变换，互相关均为零，自相关由大而小递降型。但是，也可以看出，ADF与Φu密切相关，假设换一个Φu类型，就不会有这么好的结果。2〕离散沃尔什—哈德玛变换WHT由于沃尔什—哈德玛矩阵由许多类似之处,比方他们都是以1和-1为元素，其变换运算只有加减而没有乘除，且两类矩阵之间的关系是简单的初等变换关系。所以我们将两者归为一类来研究。并首先从Hardmard矩阵开始：这里：

5〕离散余弦变换DCT：由于前面在付氏变换中引入了复数，带来了运算上的不方便，DCT正是针对这一缺点而进行的改进。根据离散付氏变换的公式，只需将信源数据长度再扩张一倍，并保证对称性即可求得DCT。DCT根据对称性不同还可划分为两类，〔奇〕ODCT与〔偶〕EDCT，前者将数据扩展为2N-1并以M=0为中心点，两侧各N-1个；后者将数据扩展为2N，并以M=0与M=1之间为中心点。且：

以上各类离散准最正确变换编码各具特色。如果仅从解除相关性的性能上看：KLT>DCT〔平稳马氏链〕>DFT>WHT>HrTST但是如果从复杂性,计算复杂度上来看,上述顺序正好相反:HrT>WHT>DFT>DCT>KLTST通用编码Huffman编码能产生最优信源编码，但需要知道所有信源符号的发生概率。在有记忆离散信源情况下，那么Huffman编码必须知道所有长度n≧2的所有信源符号组合的联合概率。对于实际信源，联合概率的计算复杂度非常高，结果Huffman编码在许多实际的有记忆信源中往往无法实现。Lampel-Ziv(LZ)通用信源编码与Huffman编码不同，LZ编码算法与信源统计特性无关，属于通用信源编码范畴，是一种将变长码段映射为等长码字的算法，编码方法可以描述为：在LZ算法中，离散信源的输出序列分解成长度可变的分组，称为码段(phrases)。每当信源输出字符组在最后位置加上一个字符后与前面的已有码段都不相同时，把它作为一种新的码段引入。将这些码段列入一个位置字典，用来记载已有码段的位置。在对一个新的码段编码时，只要指出字典中现有码段的位置，把新字符附在后面即可。LZ算法举例：考虑二进制序列

按上述编码方式序列可以分解为如下码段：1,0,10,11,01,00,100,111,010,1000,011,001,110,101,10001,1011序列中的每一个码段是前面某一个码段加上一个新的信源输出字符构成的。为了编码，需要构造位置字典。字典位置

字典内容

码字

100011000012001000000030011100001040100110001150101010010160110000010070111100001108100011101001LZ算法的字典LZ算法的字典(续)910010100101010101010000111011101101101011121100001011011311011100100014111010100111151111100011010116101111101LZ算法的信源译码器是编码的逆过程，根据码字的特点，首先可以构造出编码字典，然后对接收序列作相应的解码。需要指出，上述例如中，将44位信源比特编码成16个码字，每个码字5比特，总共是80位码字。因此这种算法没有提供任何数据压缩。本例编码效率低下的原因是由于所考虑的序列非常短。随着序列长度的增加，LZ算法的效率越来越高，可以实现信源输出序列的压缩。如何选择字典列表的总长度是LZ算法实际应用的重要问题。一般而言，无论表有多大，总有可能溢出。为了解决溢出问题，信源编译码器必须协调一致，将无用的码段从各自的字典中删除，在它们留下的位置上换上新的码段。Ziv和Lampel证明，将LZ编码应用于遍历平稳离散信源时，其压缩比可以以概率1收敛于该信源的仙农信息熵。LZ编码压缩比可以到达信源熵率这一结论一方面说明LZ编码的有效性，但也说明通用编码不能做的比Huffman编码更好。LZ算法已经广泛应用于计算机文件的压缩。Unix操作系统中的“compress〞、“uncompress〞以及Windows操作系统中的Winzip、Winrar等文件压缩软件中采用的算法就是LZ算法的不同变种。实用化与纯理论上的要求之间存在着一定差异：首先：实际比理论要复杂，理论分析时往往认为信源平稳遍历的，是遵从某一个分布特征，……等等，实际上是办不到的，最多是近似上大致满足;其次：理论上追求是性能越优良越好，追求最正确，实际上是要更侧重可实现性，追求性能与可实现性之间的折衷，追求准最正确。第三：理论上往往分析各种单一最正确化方法与性能，实际上往往是实用主义，采用多种组合准最正确化。这一点，以后在图像信源编码中表达更明显。实用型信源编码

下面，我们分别讨论三类代表性信源：1〕文件信源〔无失真信源编码〕；2〕语音信源〔限失真信源编码〕3〕图像信源〔限失真信源编码〕实用型信源编码〔续〕1>文件传真信源编码：关于文件传真的一些有关知识：（1）CCITT建议的文件传真的两种分辨率：A行分辨率：1728相素/行（即8样点/mm），

列分辨率：3.85行/mm；B行分辨率：8样点/mm，

列分辨率：7.7行/mm；

〔2〕我国标准：A行分辨率：8样点/mm，列分辨率：4行/mm；B行分辨率：8样点/mm，列分辨率：8行/mm；以上是对A4文件制定的〔210*297mm〕。如果采用各个像素按0.1直接编码，一页A4文件，分辨率为5样点/mm〔行，列〕那么需传送：,用2400b/s(或4800b/s)那么需11(5.5)分钟，假设文件压缩中仅能利用文件信源的一维概率特征，据测试有：pw=93.3%,pB=6.7%,1>文件信源编码〔续〕那么H〔U〕=-pwlogpw–pBlogpB=-0.933log0.933–0.677log0.677=0.3546bit一维熵编码理论压缩比KO为：可见压缩比不高。假设二维信元符号〔消息〕改成“0〞，“1〞游程，即连“0〞，连“1〞的游程为单元，那么可得1>文件信源编码〔续〕由二进制〔m=2〕信源编码定理，有对平均每个像素有：其中

1>文件信源编码〔续〕假设定义：那么可求得：再定义：那么可求得：1>文件信源编码〔续〕这时，黑、白游程混合编码条件下，平均每个像素的信源编码定理。（即像素熵编码定理）最终可求得：理论上极限压缩比为：对A4文件，中文七种样张统计特性如下：

1>文件信源编码〔续〕例：将无失真信源编码理论用于编码。目前第三类机采用的就是修正的哈夫曼码或者是算术码。修正主要有三点：1〕被编码的消息〔符号〕不是简单的“0〞和“1〞；而是“0〞串〔0游程〕“1〞串〔1游程〕的不同长度。2〕信源制定码表的依据。不是实时的实际信源，而是采用8种〔7种〕典型样张可测得的统计特性来近似代表实际信源的统计特性。3〕将对整个一维1728像素的统计特性码表，在制定码表的分解、简化为两类码表的合成，即将黑白游程长度分解为：其中K为根本游程长度〔0~63位〕的整数倍，由它可构成一个构造码表，而R其长度为0至63，称为结尾码，它是根本游程码的码表。1>文件信源编码〔续〕下面举一个例子说明：某一A4文件中一段特性如下：编码前总码长：

LW1=131LB1=4LW2=6LB2=65L=lW1+lB1+lW2+lB2=131+4+6+65=206位将它进行修正哈夫曼编码〔MH〕，分别查黑〔B〕、白〔W〕游程4的结尾码表，构造码表有：lW1=131=2*64+3=128+3,查白游程构造码表：128=>10010查白游程结尾码表：3=>1000故经哈夫曼编码后为：100101000共9位1>文件信源编码〔续〕同理：lB1=4，查黑游程结尾码表：4=>011〔3位〕lW2=6，查白游程结尾码表：6=>1110〔4位〕lB2=65=64+1：64=>00000011111=>010Huffman码：0000001111010〔13位〕Huffman编码后总长为：9+3+4+13=29。实际压缩比：所以上述截断式实际编码修正方法对信源统计特性影响不大。工程上可实用。

1>文件信源编码〔续〕实际统计分析说明：对于A4文件，对中文七类样张的统计平均压缩比这一结论在前面已计算过。1>文件信源编码〔续〕2>语音编码

〔1〕混合编码：以参量编码为主，以波形编码为辅。在满足根本质量前提下，尽可能提高压缩率。下面，我们首先从理论上来分析各类语音编码的潜力。首先分析波形编码：引用R(D)函数理论，假设语音近似遵从正态分布〔实际上为近似Gamma分布〕是一个满足短时广义平稳的一阶正态马氏链。其相关矩阵为R(τ)=σ2ρ│τ│,其中σ2为方差,ρ为相关系数,在均方误差保真度准那么下,由信息论可求得:R(D)=1/2log2σ2(1-ρ2)/D其中:σ2/D为信噪比,且波形编码取样点间的相关系数ρ≈0.96,那么可算得:信噪比(dB)35322825232017R(D)(bit)43.52.52.3421.51压缩倍数k22.283.23.4245.382>语音编码〔续〕〔1〕混合编码〔续〕上述表格绘出的R(D)值是最保守的估计值,原因是:其一:正态分布R(D)值大于其他一切分布R(D)值,故语音实际分布的R(D)值大于上述R(D)估计值.其二:接收语音最终是人耳,计算中未算入人耳的主观性能引入的R(D)值变化,故实际上R(D)还要求按照一般能进入公用移动网,大致要求其信噪比为24-25dB,从表中可查出压缩倍数k≈3.5,再考虑上述两个因素,一般可认为k≈4左右.其次,在分析参量编码,由语音分析,可认为语音最基本组成单元为音素.例如英语为例：其音素大约有个，同时按照通常讲话速率，每秒大约发出10个音素。这时英语语音信源给出的信息率为：

仅从可懂度看，它与目前PCM标准速率64kb/s相比，可求得压缩比方下：〔1〕混合编码〔续〕可见其潜力很大，目前实验室声码器〔参量编码〕已可做到600bit/s左右，尚相差7-8倍。实际上，除了保密通信以及一些特殊的军事通信以外很少采用这类低质量的参量编码〔声码器〕。目前，在移动通信等领域，已将信源编码的焦点转移至混合编码的方向。自八十年代以来，CCITT与现在的ITU—T等国际组织制定了一系列混合编码的标准如下：

标准编码传输速率质量(mos)备注G711PCM64Kbit/s4.2

G722

64,56或48bit/s

G726ADPCM40,32,24,16Kbit/s4.1

G727

同上4.1

G728LD-CELP16Kbit/s4.1

G729CS-ACELP8Kbit/s4.1

宽带语音编码〔1〕混合编码〔续〕标准编码传输速率质量(mos)备注G723-1

6.3-5.3Kbit/s4-3.6

GSM-SRRPELD13Kbit/s3.6

GSM-ER

13Kbit/s4

IS-96(Ⅱ)

13Kbit/s4.1

IS-641

8Kbit/s4

IS-54

8Kbit/s3.6

IS-96(Ⅰ)

8Kbit/s3.4

GSM-HR

6.5Kbit/s3.6

FS-1016

4.8Kbit/s3.2

FS-1015

2.4Kbit/s2.4

用于多媒体低比特率〔1〕混合编码〔续〕决定混合编码的主要技术指标：混合编码的综合性能=f(比特率、质量、时延、复杂度)下面分别讨论这四个指标：〔1〕比特率〔b/s〕：数量指标，取决于信源的压缩率。比特率越低，一般质量也会相应降低，为了补救质量往往又可以采用提高复杂度〔硬、软件〕，但是他又会带来处理时延的增大。因此要考虑综合优化。降低比特率另一措施是将固定速率改变为可变速率IS—95中就采用了基于不同背景噪声电平的1、1/2、1/4、1/8四类不同语音速率。这样可以大大降传送语音的平均速率。〔1〕混合编码〔续〕〔2〕

质量：目前语音质量的评估方法是采用CCITT建议的5级评分的“平均评价得分MOS“方法，4-5分列为高质量可达参加公用网要求；3-4分为根本达标，一般可入移动网要求；3分以下为不合格。评分测试条件：无背景噪声，无传输过失、无模拟转接与二次编码。显然这些条件过于理想化。〔3〕时延：语音为实时通信系统对时延很敏感，时延主要包括：算法时延、处理时延和传输时延。三类时延之和称为单向系统时延，如果无回波，它最大允许值为400ms，最好在200ms以下，又回波，仅允许25ms。〔1〕混合编码〔续〕〔4〕复杂度：语音编码通常是采用DSP来实现的。这些芯片往往可采用每秒计算百万条信令的速度〔mips〕，随机存储器〔RAM〕，和只读存储器〔ROM〕来描述。目前一般将小于15mips的语音编码为低复杂度编码，而将大于30mips的语音编码为高复杂度编码。在一个芯片上装有越多的RAM和ROM，芯片价格就越高，体积就越大，所以复杂度越高，性能越好，但同时受到本钱，功耗，时延等因素制约。〔1〕混合编码〔续〕以下表格给出这些年来，ITU建议的四个标准：G729，G729A以及两类G723—1的四大指标量级：

G729G729-AG723-1G723-1比特率(kb/s)886.35.3话音质量(MOS得分)4.14.14.13.6帧长(ms)10101030子帧长(ms)557.57.5算法延时(ms)151537.537.5复杂度MIPS(定点DSP)2010.514.616RAM(16bit字长)2.7k2k2.2k2.2k〔1〕混合编码〔续〕ADPCM是在DPCM的根底上开展起来的。而DPCM前面已讨论过。由于预测误差的幅度变化范围远小于原始信号〔预测前〕幅度变化范围，因此在相同量化噪声条件下DPCM量化比特数要远少于PCM。从而到达语音压缩编码的目的。ADPCM与DPCM相比，主要区别在于ADPCM中的量化嚣和预测嚣采用了自适应控制，同时在译码嚣中多了一个同步编码调整，其作用是为了在同步级连时不产生误差积累。八十年代以来32kb/sADPCM已日趋成熟。它具有与PCM相近的质量。下面，给出G721ADPCM编、译码框图：2>语音编码〔续〕〔2〕波形编码ADPCM根本原理〔2〕波形编码ADPCM根本原理〔续〕<32kb/sADPCM编码系统S>

<32kb/sADPCM译码系统S>

〔2〕波形编码ADPCM根本原理〔续〕由图可见，在编码器中，输入将八位非线性PCMc‘(n)变换成12位的线性码X〔n〕，再由16电平自适应量化器将差值信号d〔n〕转化成四位二进制码c〔n〕，同时为了适应不同的输入信号采用了自适应参数来控制量化阶距大小，它是由定标因子自适应和自适应速度控制两局部组成。译码系统中的大局部与编码器电路相同。主要是多了一个同步编码调整电路，其作用是为了在同步级联工作时，不产生误差积累。〔2〕波形编码ADPCM根本原理〔续〕参量编码出发点是跟踪波形产生过程，传送好产生波形的参量，而不是波形本身。在收端通过发声模型综合成人工合成语言。固有时称它为生码器。语音产生模型如下：

2>语音编码〔续〕〔3〕参量编码的线性预测人工合成语音的15个主要参量：12个时变滤波器鼓励参数：{α}i=1,2…..12;音调周期p〔基音周期〕；清浊音判决u/v；增益控制参量G；下面给出现线性预测LPC原理框图如下：〔3〕参量编码的线性预测〔续〕线性预测目前仍是混合编码中声码器实现的主流，近些年来，以下三方面值得注意：1〕提高合成语音质量措施：采用余数鼓励声码器RELP；多脉冲鼓励声码器MELP；声道参数模型的改善；2