信息论课程讲义-第五章 纠错编码原理

第五章纠错编码原理有噪声信道编码的主要目的是提高传输可靠性，增加抗干扰能力，因此也称为纠错编码或抗干扰编码。信源编码之后的码字序列抗干扰能力很脆弱，在信道噪声的影响下容易产生差错，为了提高通信系统的有效性和可靠性，要在信源编码器和信道之间加上一个信道编码器。SOURCESOURCECODINGCHANNELCODINGTxCHANNELRxCHANNELDE-CODSOURCEDE-CODSINK10/6/20231•信源编码-SourceCoding–Compressesthedatatoremoveredundancy•信道编码-ChannelCoding–Addsredundancytoprotectagainstchannelerrors10/6/20232一个通信系统总是要以一定的速率、可靠地、保证质量的将信息从一端传送到另一端。Example:Rate=1MbpsErrorrate=10-5；Error-controlcodingTwokeysystemsparametersaretransmittedsignalpower

andchannelbandwidth.Ingeneral,•Signalpower↑errorrate↓•Bandwidth↑errorrate↓Bothsignalpowerandbandwidthcannotbeincreasedinfinitely.10/6/202335.1译码准则5.1.1译码准则的含义⑴一个例子影响通信系统可靠性的一个重要问题是译码方式，可以通过一个例子看一下；有一个BSC信道，如图所示。10/6/20234对于这样一个信道，如果采用自然的译码准则，即收0判0，收1判1；这时可以明显看到，当信源先验概率的等概时p(0)=p(1)=1/2；这时收到Y判X的后验概率等于信道转移概率，系统正确的译码概率为1/4，错误译码概率为3/4。但如果采用另一种译码准则，收0判1，收1判0；则系统正确的译码概率为3/4，错误译码概率为1/4，通信的可靠性提高了。10/6/20235⑵译码准则设一个有噪声离散信道，输入符号集X，输出符号集Y，信道转移概率为P(Y/X);X:{x1,x2,…..,xn}。Y:{y1,y2,……ym}P(Y/X):{p(yj/xi);i=1,2,…n;j=1,2,…m这时定义一个收到yj后判定为xi的单值函数，即：F(yj)=xi(i=1,2,…n;j=1,2,…m)；这个函数称为译码函数。它构成一个译码函数组，这些函数的值组成了译码准则。10/6/20236对于有n个输入，m个输出的信道来说，可以有nm个不同的译码准则。例如上面例子中有4种译码准则分别为：A:{F(0)=0;F(1)=0}B:{F(0)=0;F(1)=1}C:{F(0)=1;F(1)=0}D:{F(0)=1;F(1)=1}10/6/202375.1.2译码错误概率当译码准则确定之后，接收端收到一个yj后，则按译码准则译成F(yj)=xi，这时如果发送的为xi则为正确译码，如果发送的不是xi则为错误译码。所以接收到yj后正确译码的概率就是接收端收到yj后，推测发送端发出xi的后验概率：Prj=P{F(yj)=xi/yj}而错误译码的概率为收到yj后，推测发出除了xi之外其它符号的概率：Pej=P{e/yj}=1-P{F(yj)=xi/yj}其中e表示除了xi之外的所有其它信源符号的集合。10/6/20238然后对所有的yj取平均，则平均正确译码概率为：同样可以得到平均错误译码概率为：这就是平均错误译码概率的基本表达式，在通信系统设计和分析时，总是希望得到最可能小的平均错误译码概率。因此所有通信系统都将平均译码错误概率作为系统可靠性的一个重要指标。10/6/202395.1.3最大后验概率准则由平均错误译码概率的表达式可以看出，错误译码概率与信道输出端随机变量Y的概率分布p(yj)有关，也与译码准则有关。当信道转移概率p(yj/xi)确定，而且信源统计特性p(xi)确定之后，信道输出端的p(yj)也就确定了。因为：p(xi,yj)=p(xi)p(yj/xi);而p(yj)可以由p(xi,yj)的(i=1,2,…,n)求和得到。因此，在这种情况下，平均错误译码概率只与译码准则有关了。通过选择译码准则可以使平均译码概率达到最小值。10/6/202310当式中的每一项的P{F(yj)=xi/yj}达到最大值时，平均错误译码概率就可以为最小值。设信源X的信源空间为：信道的转移矩阵为：10/6/202311收到每一个yj(j=1,2,…m)后，推测发送为xi(i=1,2,…n)的后验概率共有n个，为：p(x1/yj),p(x2/yj),……p(xn/yj)。这其中必有一个为最大的，设其为：p(x*/yj)，即有：p(x*/yj)≥p(xi/yj)(对一切的i)这表明：收到符号yj后就译为输入符号x*，即译码函数选为：F(yj)=x*(j==1,2,…m)这种译码准则称为最大后验概率准则。10/6/202312利用这种准则就可以使平均译码错误概率公式中的求和的每一项达到最小值{1-[F(yj)=x*/yj]}。这时的平均错误译码概率的最小值为：从表达式中可以看到，这个最小值与信源先验概率和信道转移概率有关，特别是信道转移概率，如果除了p(yj/x*)外，其它的项都很小，错误译码概率就小。10/6/2023135.1.4最大似然准则最大后验概率译码准则需要已知后验概率，但信道的统计特性描述一般是信道转移概率，因此希望利用信道转移概率的译码准则。由概率中的贝叶斯定理可有：这样，如果能够保证对所有的ip(x*)p(yj/x*)≥p(xi)p(yj/xi)(i=1,2,……n)就等于：p(x*/yj)≥p(xi/yj)（最大后验）则选择译码准则：F(yj)=x*(j=1,2,……n)10/6/202314这样，可以看到当信道输入符号集X的先验概率为等概时[p(xi)=1/n]，最大后验概率可以用最大信道转移概率来取代。这时，如果p(yj/x*)是yj相应的n个信道转移概率

p(yj/x1),p(yj/x2),……,p(yj/xn)中的最大者，则我们就将yj译成x*，这种译码方法称为“最大似然译码准则”。最大似然译码准则利用了信道转移概率，而不用后验概率，将更方便。10/6/202315这时的最小平均错误译码概率为：[将信道转移矩阵P中每一列中的最大元素去掉，然后将其它元素相加后除以n]。为了减小错误译码概率，主要方法是改变信道转移概率。10/6/202316说明:最大后验概率准则也叫做最小错误译码概率准则，是一种最佳准则。当信道的输入符号先验概率为等概时，最大似然准则就等于最大后验概率准则。当信道的输入符号先验概率不等概时，最大似然准则就不是最佳准则了。但是由于使用方便通常还是应用的。10/6/202317举例：X:{x1,x2,x3}Y:{y1,y2,y3}信道转移矩阵为:10/6/202318如果使用最大似然准则;译码函数为:F(y1)=x1F(y2)=x3F(y3)=x2为信道矩阵各列中的最大项.计算可知;当先验等概时平均错误译码概率为:10/6/202319如果先验不等概时平均错误译码概率为:{1/4,1/4,1/2}10/6/202320Fano不等式可以看到：错误译码概率与译码准则有关，但是主要是由于信道噪声引起的。也就是由信道的疑义度H(X/Y)的存在引起的。因此Pe与H(X/Y)一定存在某种关系。称为Fano不等式。10/6/202321H(Pe)是Pe的熵。这个不等式指出疑义度分为两个部分。第一部份是产生错误还是不产生错误的不确定性；第二部分是产生错误后是哪个输入造成的不确定性。虽然Pe与译码准则有关，但无论什么准则该不等式都成立。当信源和信道确定后，信道疑义度给定了译码错误概率的下限。10/6/202322H(X/Y)Pe1(n-1)/nlognlog(n-1)H(Pe)+Pelog(n-1)10/6/2023235.2信道编码基本概念5.2.1信道编码定理[定理]：有噪声信道编码定理（Shannon第二编码定理）如一个离散有噪声信道有n个输入符号，m个输出符号，信道容量为C。当信道的熵速率R≤C时，只要码长足够长，总可以找到一种编码方法及译码准则，使信道输出端的平均错误译码概率达到任意小，[pe=ε]。当R>C时，则不可能找到一种编码方法及译码准则，使信道输出端的平均错误译码概率达到任意小。10/6/2023245.2.2信道编码的基本概念（分组码）⑴码字空间如果原始信源空间有M个码字，对其进行q元等长码的信道编码，码长为N，信道码字空间的所有码字为qN个，编码器将在这qN个可用码字中选择M个码字分别代表原始信源中的M个码字，信道编码码字空间的这M个码字称为“许用码字”，而另外的qN-M个码字称为“禁用码字”。为了实现纠错编码，一定有qN>M。这M个许用码字也称为一个码组，或称为码字集合。10/6/202325⑵汉明距离：(Hammingdistance)在一个码组（码字集合）中，任意两个等长码字之间，如果有d个相对应的码元不同，则称d为这两个码字的汉明距离。例如：α和β为码组X中的两个不同码字，X为一个长度为N的二元码组，其中：α=[a1,a2,……aN]ai∈{0,1}β=[b1,b2,……bN]bi∈{0,1}则α与β的汉明距离为：d=0表明为全同码，d=N表明为全异码，如果用模2加法的概念，有10/6/202326⑶最小码距：在一个码字集合中，任何两个码字之间的汉明距离组成一个元素集合，D(α,β)，这个集合中的最小值称为这个码字集合的最小汉明距离，简称最小码距，记为：dmin。dmin=min{d(α,β)α,β∈Xα≠β}⑷码字重量（汉明重量）(Hammingweight)在二元编码的码字集合中，码字中“1”码元的个数称为这个码字的重量。记为：W(α)。利用码字重量的概念，汉明距离可以表示为：d(α,β)=W(α⊕β)10/6/202327举例码A码B码C码D许用码字000111000011101110000001100010000001…111码字个数2448最小距离3211传输效率1/32/32/31Pe3×10-42×10-22.3×10-23×10-210/6/202328⑸分组码最小码距与纠检错能力的关系：一个分组码的最小码距为dmin，则其纠检错能力为：若发现e个错误，则要求dmin≥e+1;若纠正t个错误，则要求dmin≥2t+1;若纠正t个错误，同时发现e个错误，则要求dmin≥t+e+1;t<e;例如：dmin=1;无纠检错能力；dmin=2;检一位错dmin=3;纠一位错（或检两位错）dmin=4;纠一位，同时检两位；dmin=5;纠二位错（或检4位错）dmin=6;纠二位，同时检3位；(t=2,e=3)10/6/202329一个许用码字一个许用码字错两位构成的汉明空间00011100101110/6/2023305.2.3纠错编码方法纠错编码：根据一定的纠检错要求，对原始码字进行某种变换，使其具有具有纠检错能力，这种变换称为纠错编码，抗干扰编码。实现方法：信息位+监督位=纠检错编码。纠错编码理论：(1)信道编码定理；中心任务就是效率高，能力强，实现简单的编码译码方法(2)近代(抽象)代数理论：研究向量空间、多项式、群、环、域的性质。10/6/202331差错控制系统：