关于相关信源的码率界限及其编码的评述

关于相关信源的码率界限及其编码的评述摘要随着多媒体移动通信技术的快速发展，人们对信息可靠且有效的传输需求日益增长，但是由于受到无线带宽资源和多径衰落等因素的影响，很难实现高速可靠的数据传输。要解决这一矛盾我们必须采用全新的通信理论及技术。本文从信息论的角度对相关信源编码的相关理论进行了介绍，包括单符号信源编码的理论基础，相关信源的编码理论和码率界限和其编码。关键字：信源编码，相关信源编码，分布式信源编码，Slepian-Wolf编码理论，AbstractWiththedevelopmentofmultimediamobilecommunicationtechnologies,thedemandforreliableandefficienttransmissionofinformationisgrowing.However,duetotheimpactoflimitedwirelessbandwidthresources,multipathfadingandotherfactors,itisdifficulttoachievehigh-speedandreliabledatatransmission.Tosolvethisproblemwemustadoptsomenewcommunicationtheoriesandtechnologies.Thisarticlemakesanintroductiontotherelatedtheoriesofcorrelatedsourcecodingfromtheperspectiveofinformation-theoreticsecurity,includingthebasictheoryofsinglesymbolsourcecodingandcorrelatedsourcecoding.KEYWORD：SourceCoding，CorrelatedSourceCoding，DistributedSourceCoding，CodingTheoryofSlepian-Wolf1.引言信源编码是一种以提高通信有效性为目的而对信源符号进行的变换，或者说为了减少或消除信源冗余度而进行的信源符号变换。具体说，就是针对信源输出符号序列的统计特性来寻找某种方法，把信源输出符号序列变换为最短的码字序列，使后者的各码元所载荷的平均信息量最大，同时又能保证无失真地恢复原来的符号序列。信源编码的作用之一是设法减少码元数目和降低码元速率，即通常所说的数据压缩；作用之二是将信源的模拟信号转化成数字信号，以实现模拟信号的数字化传输。最原始的信源编码就是莫尔斯电码，另外还有ASCII码和电报码都是信源编码。但现代通信应用中常见的信源编码方式有：Huffman编码、算术编码、L-Z编码，这三种都是无损编码，另外还有一些有损的编码方式。信源编码的目标就是使信源减少冗余，更加有效、经济地传输，最常见的应用形式就是压缩。而相关信源编码与传统信源编码不同。它一般采用信道码编码技术得以实现，因而可以看作是一种联合信源-信道编码技术。虽然分布式编码理论早在二十多年前就已经提出，但Slepian-Wolf理论[1]和Wyner-Ziv理论[2]只给出了信源编码的理论根据，并没有给出一种具体的实现方法，因此这方面的进展并不显著。直到近几年，研究者才找到实现分布式信源编码的可行方法，发现了信源编码和信道编码的密切关系。如果信道码能够渐近地接近信道容量，那么把它应用于分布式信源编码就能渐近地接Slepian-Wolf理论极限，Pradhan和Ramchan－dran提出了分布式编码的实现方案[3]，一些具体的实现方案陆续的提出[4-6]，从理论上证明了使用Turbo码可以接Selpian-Wolf编码效率[6]，并且证明了使用LDPC码可以达到比Turbo码更好的效果[7]。本文从信源编码的基本理论出发，介绍了相关信源的分布式编码的信息论基础。重点介绍了Slepian-Wolf理论即相关信源的码率界限，对几种不同的编码方式进行了简单介绍和评述。2.相关信源编码的理论2.1单符号信源编码信源编码理论是信息论的重要内容，信源是多种多样的，但信源符号之间具有一定的相关性，因此可以利用信源的冗余度来进行压缩，通过编码让符号间解除相关性，尽可能独立。或是压缩每个信源的平均比特数，从而提高编码效率。它使信源编码的具体设计和架构更加明确。而香农第一定理明确的提出了信源编码的理论依据。即在无失真的信源编。码当中，离散信源的熵为H(X)，对n次扩展信源进行信源编码，对任意给定的ɛ0，只要有码率：RH(X)+ɛ那么当n足够大时，平均译码错误概率就无限接近于0。这就是单符号离散信源的编码原理。由定理可得，若想符号可以从码字中无损的恢复出来，信源熵H(X)是信源实现无失真编码的速率最小值。香农编码、Fano编码Huffman编码DMS的几个基本的信源编码方法。2.2相关信源编码的理论相关信源编码是分布式信源编码的基本研究问题，目前已经解决了相关信源的可达信息率问题，虽然很多学者做出了努力，但是关于具体码字的设计和优化还没有明确的答案。20世纪70年代，分布式信源编码[8](DistributedSourceCoding,DSC)初步形成，它也可以称为是相关信源的信源编码。DSC的理论基础是Slepian-Wolf理论和Wyner-Ziv理论组成而来。Slepian和Wolf指出如果两个信源有一定关联性，若想实现信源的无损压缩则可以根据它们的信息熵计算出一个理论极限，我们称之为Slepian-Wolf界。其中两个相关信源在分离状态下压缩编码，仍可以达到互相协作时的压缩效率。不久之后，Wyner和Ziv对无损压缩理论做出了进一步研究，并提出了有损压缩编码理论，得到类似的结果。它与传统的信源编码不同，传统的信源编码是编码端充分利用多个信源的冗余信息最大限度的进行压缩，而Slepian-Wolf理论和Wyner-Ziv理论的出现，使人们意识到信源的冗余信息在译码端也可以充分利用，从而达到相同效果。在传统的信源编码中，由无失真信源编码定理而得，只有当编码速率比信息熵大时才能保证信息的正确传送。传统信源编码结构中，两个相关信源X，Y间能够相互通信，通过对信源X和Y进行联合编码，同样要实现无差错恢复出信源，就必须保证编码和速率大于X，Y的联合熵H(X，Y)。图1给出了传统的信源编码结构，其中编码端X，Y可以互相结合各自的信息，同时将信源X压缩到速率为H(X/Y)，信源Y以H(Y)的速率进行压缩，译码器收到X和Y的相关信息序列后进行联合译码。图1传统信源编码结构当两个相关信源不能互相通信时，如下图2所示。已知针对两个独立信源分别用独立信道传送时，若实现无损压缩编码，每个信道的信息率必须大于各信源的无条件熵，即总信息率必须大于H(X)+H(Y)。首先此处要满足这个基本条件。但是X，Y有一定相关性，Slepian和Wolf利用此相关性进行了一定研究，指出若数字信号X、Y满足条件概率分布p(x，y)，如果X，Y在编码端不能互相通信，分别采取独立编码也可以达到X，Y互相通信联合编码的编码效率。只要在解码端联合译码，则分开编码和联合编码都能正确解码，效率相同，这即为Slepian-Wolf定理。图2分布式信源编码结构图2中两个分离的编码器分别对X，Y进行编码，码率设置为Rx和Ry，而在译码处进行联合解码，Slepian-Wolf理论提出对于互相关的两个离散随机信号X、Y，服从联合概率分布p（x，y），那么在编码端得不到Y的情况下对X进行编码可以取得编码效率和在编码端得到Y的情况下对X进行编码的效率一样。也就是说，在编码端可以不需要直接跟Y通信，X最少也能以H（X/Y）比特编码，只要在解码端可以得到Y，那么X仍能正确解码。根据Slepian-Wolf理论，图3所示的两种编码方案可以取得相同的编码效率。图3两种编码器结构Slepian-Wolf理论可以简单地描述如下：假定X和Y是两个互相关的离散无记忆信源，对X和Y进行独立编码，H（X）、H（Y）分别是X，Y的熵，编码器X输出的码率是Rx，编码器Y输出的码率是Ry，在解码端进行联合解码，如果在解码端可以无失真的恢复X，Y需要满足下面三个式子：Rx≥H（X/Y）Ry≥H（Y/X）Rx+Ry≥H（X/Y）Slepian-Wolf理论的可达码率界限如图4所示：图4Slepian-Wolf理论可达的码率界限只要如Rx和Ry的取值范围在图中的Slepian-Wolf压缩可达速率的区域，则在解码端可以任意小的误码率来联合解码。在Slepian-Wolf的无损编码理论发表后不久，Wyner-Ziv就对这个理论进行了扩充，建立了在解码端使用辅助信息的有损编码理论[2]，如图5所示：图5Wyner-Ziv有损分布式编码结构3.相关信源的分布式编码方案在相关信源编码理论的支撑下，其分布式编码方案也越来越多，但是一直没有提出实际可行的方案。之后，研究学者发现信源编码和信道编码之间有紧密联系，可以采用有优异性能的信道码来实现，这样则可以逼Slepian-Wolf的理论限值。编码方案具体可以分为基于校验位(Parity)和基于伴随式的分布式信源编码(DistributedSourceCodingUsingSyndrome,DISCUS)两种方式。3.1Discus编码方案2000年，Pradhan和Ramchandran[9]首先提出了DISCUS方案，将卷积码的维特比译码方法进行修正，解码器根据伴随式s搜索陪集中与y最接近的序列。之后提出的方案均是在DISCUS的基础之上的变形。2005年Z.Tu,J.Li和Blum[10]就将陪集首的变化转移到译码端外，进行反向伴随式变换，然后与y结合，这样解码端只需在伴随式为0的陪集中进行即可，并且不用修改卷积码的维特比译码算法，另外，也可以采用Turbo码实现。2007年，针对伴随式方案，又提出了一种基于卷积码和Turbo码的速率自适应方案，对伴随式比特进行打孔，并设计了最佳解码方法来补偿打孔带来的性能损失。与此同时，译码的复杂性与增加的打孔比特数量呈线性关系。Discus编码方案[3]考虑了两个相关的信源X和Y的独立编码和联合解码，在X和Y之间想象一条虚拟的信道P（Y/X），把信源X看作信道的输入，把参考信息Y看作信道的输出，即把信源Y看成是信源X经过噪声污染后的结果，这样就可以利用信道码的纠错性能来恢复信源码字。该方案的关键问题是信源码字空间的分割，把信源X的输出划分成不同的组，称之为陪集，这种划分使得在每一个陪集中的两个码字之间的最小距离尽可能的达到最大，以便在解码端通过观察参考信息Y在陪集中找到和参考信息距离最近的码字作为解码结果，编码器则通过只传输陪集的索引来达到数据压缩的目的，陪集的这种特性正好与信道码的特性十分的相似。对于（n，k）信道分组码，n为码字长度，k为信息比特长度，这组信道码正好是在所有码长为n的码字序列中选取的距离尽可能大的2k个序列，H为该信道码的校验矩阵，对于每一组信道码的陪集都可以用它的校正子来表征，定义校正子S=XH′，S也称为信道码的伴随式，X是该信道码中的码字，每一组信道码对应一个伴随式，该伴随式也就是这个陪集的索引。在编码过程中，把待编码码字看作是码字长度为n的码字序列中的一个元素，然后找出这个码字所在的信道码，再传输该组信道码的索引（校正子或伴随式）到解码端，这样传输的码字长度就由n变成了n-k，节省了k个比特。在解码端，接收到的是编码码字所属陪集的伴随式，解码的工作就是利用参考信息Y在伴随式S所指示的信道码中找到与X距离最近的码字，即利用信道码解码来恢复被编码的码字。4.总结本文由单符号信源编码的基础理论出发，详细的论述了相关信源的编码理论。详细的描述了相关信源的编码即分布式信源编码中的Slepian-Wolf理论，得出了相关信源编码的码率界限，并介绍了Wyner-Ziv理论。然后详细介绍了DISCUS编码方案和LPDC编码方案的理论基础并进行评述。通过该课