第5讲 信道编码：基本概念、线性分组码

信道编码例如：假设要传送A、B两个消息编码一：消息A----“0”；消息B----“1”若产生错码（“0”错成“1”或“1”错成“0”）收端无法发现，该编码无检错纠错能力此时的编码没有冗余编码二：消息A----“00”；消息B----“11”若一位产生错码，变成“01”或“10”，因“01”“10”为禁用码组，收端可发现有错，但无法确定错码位置，不能纠正，增加一位冗余后具有检出一位错码的能力编码三：消息A----“000”；消息B----“111”传输中产生一位或是两位错码，都将变成禁用码组，具有检出两位错码的能力在产生一位错码情况下，收端可根据“大数”法则进行正确判决，能够纠正这一位错码，该编码具有纠正一位错码的能力在产生两位错码情况下，只具有检错能力这表明增加两位冗余码元后码具有检出两位错码及纠正一位错码的能力上述编码方法被称为重复码，记为(n,1)，编码方法：把每个信息比特u重复n遍形成一个码组c=(u,u,…,u)译码方法：若译码器收到的一个n个比特码组y=(yn-1,yn-2,…,y0

)，判决码组y中比特“1”和“0”的个数：1）若比特“1”的个数多则判决发送的“1”码；2）若比特“0”的个数多则判决发送的“0”码仍然出错的概率（其中p为信道误码率）：n表示码组长度，1表示信息码元的个数信源编码信道编码发送滤波器接收滤波器信道译码信源解码调制器解调器信源信道信宿信道编码的相关概念：码重、码距等简单的信道编码汉明码循环码卷积码原因：在数字信号的传输过程中，实际信道不理想，存在噪声和干扰，导致接收端的误判，产生差错控制差错的方法：1）合理的设计基带信号；2）选择调制、解调方式；3）均衡技术；4）增大发送功率在此基础之上再采用信道编码技术控制差错信道编码的目的添加冗余位信道编码：1）保持信息的位数不变的情况下，采用增加码长的方法降低误码率2）基本思想：通过对信息码元序列作某种变换：使原来彼此相互独立，没有关联的信息码元序列，经过这种变换后，产生某种规律性或相关性；在接收端可根据这种规律性来检查，或者纠正传输序列中的差错3）实现：发送端按照某种规则在信息序列上附加监督码元，接收端则按照同一规则检查两者间关系信源编码：是指将信源中多余的信息除去，即降低冗余度，以提高传输的效率，即有效性编码1）去除冗余2）提高传输速率信道编码：为了对抗信道中的噪音和衰减，通过增加冗余，来提高抗干扰能力以及纠错能力，即可靠性编码1）添加冗余2）降低差错率：牺牲通信的有效性（信息传输速率）来提高可靠性因此信道编码又可称为差错控制编码按照差错的类型可将信道分为：1）独立随机差错信道差错随机出现，且相互独立，主要有高斯白噪声引起2）突发差错信道信道传输的不理想，存在比较大的脉冲干扰导致差错成串出现信道中差错的种类差错控制方式—检错重发能够发现错误的码判决信号发收检错重发（ARQ）接收端按一定规则对收到的码组进行有无错误的判别。若发现有错，则通知发送端重发，直到正确收到为止具体实现时，通常有3种形式2发送端：接收端：133124ACKACKNAK发现错误(a)停止等待重发TiTw1）如果未发现错误，则发回ACK信号给发送端，发送端收到ACK信号再发下一个码组2）若检测到错误，则发回NAK信号，发送端收到NAK信号后重发前一码组，并再次等候ACK信号或NAK信号发送端：接收端：1234562341034562345678956789发现错误NAK从码组2开始重发(b)返回重发1）不停地送出一个个连续码组，不再等候收端返回的ACK信号，收到到NAK则开始重发2）N的大小取决于信号传递及处理所带来的延时发送端：接收端：12345627812345627899发现错误NAK重发码组2(c)选择重发与返回重发不同的是，发端并不重发错误码组后的所有码组，而只重发有错的那个码组能够纠正错误的码发收前向纠错（FEC）发送端将信息序列编码成能够纠正错误的码，接收端根据编码规则进行检查，如果有错自动纠正，特点如下：不需要反馈信道，特别适合只能提供单向信道场合自动纠错，不要求检错重发，延时小，实时性好纠错码必须与信道的错误特性密切配合若纠错较多，则编、译码设备复杂，传输效率低差错控制方式—前向纠错能够发现和纠正错误的码发收混合纠错检错（HEC）判决信号FEC与ARQ的结合发端发出同时具有检错和纠错能力的码，收端收到后，检查错误情况：如果错误在纠错能力之内，则自动纠正；若超出纠错能力，但在检错能力之内，则经反向信道要求重发差错控制方式—混合纠错检错信道编码的几个基本概念1）码重：码字中非零位的数目定义为该码组的重量，即所含“1”的个数简称码重，记为Wc。如“10011”码组的码重为32）码距：两个码组中对应码位上具有不同二进制码元的位数被定义为两码组的距离，称为汉明（Hamming）距离，简称码距，记为d(ci,cj

)。如两码组“10011”与“11010”间码距为23）编码效率：指一个码组中信息位所占比重，用η

表示

η

=k/n其中k为信息码元的数目，n为码长。η

值越大表明信息位所占的比重越大，码组传输信息的有效性越高若某信源产生两个符号A与B，假设分别用两个长度为4的码组（已被信道编码）进行表示：A=0110；B=1100，码距d=2，此时只有这两个码组是许用码组，其他4位二进制比特位的组合均为禁用码组（不能代表任何消息）假设这种信道编码方式具有检错能力，下面分析码距与检错能力的关系1）消息A经过传输后发生一位错误后的情况可能为：A(0110)→{1110，0010，0100，0111}2）消息A经过传输后发生二位错误后的情况可能为：A(0110)→{1010，0000，0101，1100，1111，0011}A码组的误码集合中存在许用码组B，可知该编码方法不能检查二位以上的错误因此编码的检错能力与码距有关最小码距与检、纠错能力关系在一个码组集合中，任意两个码组间距离的最小值，即码组集合中任意两元素间的最小距离，记为dmin假设A和B是某个许用码组集合中的两个许用码组，它们之间的距离n是该集合的最小码距，则：码组A发生n位错误后构成的误码集合中必然包含许用码组B，此时便失去了检错能力有上述分析可知：假设一个码能检测e个独立错误，则要求其最小码距

dmin≥e

+1反之，若码的最小距离为dmin，则最多能检测dmin-1个错码若某信源产生两个符号A与B，假设分别用两个长度为4的码组（已被信道编码）进行表示：A=0110；B=1000，码距d=3假设这种信道编码方式具有纠错能力，下面分析码距与纠错能力的关系1）若信道中只可能发生一位或两位错误，则消息A与消息B经过传输后发生一位错误后的情况分别可能为：A(0110)→{1110，0010，0100，0111}B(1000)→{0000，1100，1010，1001}若该种编码方法可以纠正t=1个错误，此时上面两个误码集合是没有交集的。因此可以完全的纠错，即可以分别将误码集合中的码字纠正为A或B2）若信道中最多可以发生两位以内错误，消息A与消息B经过传输后发生一位或两位错误后的情况分别可能为：A(0110)→{1110，0010，0100，0111，1010，0000，0101，1100，1111，0011}B(1000)→{0000，1100，1010，1001，0100，1110，1011，1010，1001，1101}每个误码集合中前4个码组为误码一位的码组，后6个位误码两位的码组若该种编码方法可以纠正t=2个错误，即d<2t+1；观察发现两个误码集合存在交集，交集中的码组用相应的颜色标出；两个集合中黑色字体的码组都可以被正确的纠正，但对于其他颜色的码组，比如1110，它在两个集合中都存在，此时接收端不知道该纠正为A还是B。因此当d<2t+1时不能完全正确的进行纠错由上述分析可知：一个码能纠正t个错码，则要求其最小码距

dmin

≥2t+1反之，若码的最小距离为dmin

，则最多能纠正(dmin-1)/2个错码一个码能纠正t个错码，同时能检测e个错码，则要求其最小码距

dmin≥e+t+1(e>t)纠正t个错码，同时能检测e个错码，称为纠检结合，错码数较少时执行纠错方式，错码数较多时执行检错方式有限域的简单知识所谓有限域是指包含有限个元素的集合，按照所规定的运算规则运算后的结果仍为集合中的元素编码理论中有限域为{0,1}二元集合，记为GF(2)GF(2)的加法与乘法：1）加法：相同为0，相异为1；2）乘法：除了1·1=1，其他均为0二元扩展域，记为GF(2n)：由GF(2)中的元素构成的长为n的序列的集合，若1）加法2）乘法二、线性分组码线性分组码的数学定义：信道编码可表示为由编码前的信息码元空间Uk到编码后的码字空间Cn的一个映射f，即：f：Uk

→Cn

其中(n>k)若f进一步满足线性关系：则称f为线性编码映射，若f为一一对应映射，则称f为唯一可译线性编码，由f编写的码c=(cn-1cn-2…c0)称为线性分组码，u=(un-1un-2…u0)为编码前的信息分组，其中k为信息位数，n为码长，其编码效率为η=k/n数学定义的解释：1）“线性”是指码组中码元之间的约束关系为线性；2）“分组”是在编码时将每k个信息位分为一组进行独立处理；3）将其变换成长度为n（n>k）的二进制码组，一般称为（n,k）线性分组码线性分组码的特征：1）加法封闭性：码组集合中任意两个码组相加仍为集合中的一个许用码组；2）全零序列是线性分组码中的一个码字；3）码组集合中码组之间的最小码距等于某非零码字的最小码重偶监督偶校验码发送端编码：将一位监督码元附加在信息码元后，使得码组中“1”码元个数为偶数（偶监督）接收端译码校验：1）计数接收码组中“1”码元个数是否为偶数，即计算S=an-1+an-2+……+a02）S=0认为没错，S=1认为有错3）上式称为监督方程（监督关系式），其中S称为校正子（校验子、伴随式）4）S只能判断有错无错，而不能纠错汉明码的构造

假设有1个信息码组由4位二进制位组成，在其后添加3位二进制位作为监督码元，最后所组成的码组表示为：c=(u6u5u4u3c2c1c0)并且令：1）c2监督u6u5u4，即2）c1监督u6u5u3，即3）c0监督u6u4u3，即接收端译码校验，得到监督方程：对于上式，若无错误发生，三个校验子均为0；假设传输过程中有且仅有一位发生错误：1）若c0发生错误，观察监督方程，则三个校验子S2S1S0的组合为001；2）若c1发生错误，S2S1S0=010；3）若c2发生错误，S2S1S0=100；4）若u3发生错误，S2S1S0=011；5）若u4发生错误，S2S1S0=101；6）若u5发生错误，S2S1S0=110；7）若u6发生错误，S2S1S0=111；因此依据监督关系式就可计算出所有4位二进制信息位u6u5u4u3的监督位c2c1c0，这一过程即为(7,4)线性码的构造过程，其码组空间为：表中所示为(7,4)线性码的码组空间监督矩阵的推导将监督关系式进行变换观察发现上式即为一个线性方程组，因此可用矩阵方程来表示：对于上面的矩阵方程，令：则矩阵方程可化简为：H·CT=OT

或C·HT=O那么H称为线性码监督矩阵，r×n

阶的矩阵，由r（监督位个数）个线性独立方程组的系数组成，每一行代表了监督位与信息位间的监督关系。观察矩阵H：把具有(P·Ir)形式的H矩阵称为典型形式的监督矩阵，其中P矩阵为r×k

阶矩阵,Ir矩阵为r×r

阶单位方阵H矩阵的各行应线性无关。矩阵若能写成典型形式，则其各行一定线性无关生成矩阵的推导对监督关系式进行移项变换（移动红色部分）：观察上面的矩阵方程：其中系数矩阵与监督矩阵H中的P矩阵一样，对此矩阵方程两边做转置变换：其中Q=PT，为k×r

阶矩阵；U矩阵表示信息位由上面的矩阵方程可知，只要用信息位与矩阵Q相乘就可得到监督位，然后拼接在信息位之后就是一个（n,k）线性分组码集合中的一个码字虽然通过Q矩阵可以产生线性分组码，但需要分为两步，如果对Q矩阵做变换：

在Q矩阵的左边加上一个k×k阶单位阵，即：则一个（n,k）线性分组码可以通过下面的矩阵方程产生矩阵G则被称为线性分组