信息论与编码理论-信道编码-线性分组码2

2023/2/51Tochoosetimeistosavetime2023/2/526.2.1一般概念6.2.2一致监督方程和一致监督矩阵6.2.3线性分组码的生成矩阵6.2.4线性分组码的编码6.2.5线性分组码的最小距离、检错和纠错能力6.2.6线性分组码的译码6.2.7线性分组码的性能6.2.8汉明码6.2.9由已知码构造新码的方法6.2.10线性分组码的码限6.2线性分组码2023/2/53(2)纠错译码①最佳译码准则（最大似然译码）通信是一个统计过程，纠、检错能力最终要反映到差错概率上。对于FEC方式，采用纠错码后的码字差错概率为pwe，p(C)：发送码字C的先验概率p(C/R)：后验概率若码字数为2k，对充分随机的消息源有p(C)=1/2k，所以最小化的pwe等价为最小化p(C’≠C│R)，又等价为最大化p(C’=C│R)；6.2.6线性分组码的译码2023/2/54对于BSC信道：最大化的p(C’=C│R)等价于最大化的p(R│C)，最大化的p(R│C)又等价于最小化d(R,C)，所以使差错概率最小的译码是使接收向量R与输出码字C’距离最小的译码。6.2.6线性分组码的译码2023/2/55②标准阵列码矢参数发送码矢：取自于2k个码字集合{C}；接收矢量：可以是2n个n重中任一个矢量。译码方法把2n个n重划分为2k个互不相交的子集，使得在每个子集中仅含一个码矢；根据码矢和子集间一一对应关系，若接收矢量Rl落在子集Dl中，就把Rl译为子集Dl含有的码字Cl；当接收矢量R与实际发送码矢在同一子集中时，译码就是正确的。标准阵列：是对给定的(n,k)线性码，将2n个n重划分为2k个子集的一种方法。6.2.6线性分组码的译码2023/2/56标准阵列构造方法先将2k个码矢排成一行，作为标准阵列的第一行，并将全0码矢C1=(00…0)放在最左面的位置上；然后在剩下的(2n－2k)

个n重中选取一个重量最轻的n重E2放在全0码矢C1下面，再将E2分别和码矢相加，放在对应码矢下面构成阵列第二行；在第二次剩下的n重中，选取重量最轻的n重E3，放在E2下面，并将E3分别加到第一行各码矢上，得到第三行；…，继续这样做下去，直到全部n重用完为止。得到表6.2.2所示的给定(n,k)线性码的标准阵列。6.2.6线性分组码的译码2023/2/576.2.6线性分组码的译码2023/2/58标准阵列的特性定理6.2.5：在标准阵列的同一行中没有相同的矢量，而且2n个n重中任一个n重在阵列中出现一次且仅出现一次。[证明]：因为阵列中任一行都是由所选出某一n重分别与2k个码矢相加构成的，而2k个码矢互不相同，它们与所选矢量的和也不可能相同，所以在同一行中没有相同的矢量；在构造标准阵列时，是用完全部n重为止，因而每个n重必出现一次；每个n重只能出现一次。假定某一n重X出现在第l行第i列，那么X＝El+Ci，又假设X出现在第m行第j列，那么X＝Em+Cj，l<m，6.2.6线性分组码的译码2023/2/59因此El+Ci=Em+Cj，移项得Em=El+Ci+Cj

而Ci+Cj也是一个码矢，设为Cs，于是Em=El+Cs，这意味着Em是第l行中的一个矢量，但Em是第m行(m>l)的第一个元素，而按阵列构造规则，后面行的第一个元素是前面行中未曾出现过的元素，这就和阵列构造规则相矛盾。6.2.6线性分组码的译码2023/2/510定理6.2.6(线性码纠错极限定理)：二元(n,k)线性码能纠2n－k个错误图样。这2n－k个可纠的错误图样，包括0矢量在内，即把无错的情况也看成一个可纠的错误图样。[证明]：(n,k)线性码的标准阵列有2k列（和码矢矢量相等），2n/2k=2n－k行，且任何两列和两行都没有相同的元素。陪集：标准阵列的每一行叫做码的一个陪集。陪集首：每个陪集的第一个元素叫做陪集首。每一列包含2n－k个元素，最上面的是一个码矢，其它元素是陪集首和该码矢之和，例如第j列为6.2.6线性分组码的译码2023/2/511若发送码矢为Cj，信道干扰的错误图样是陪集首，则接收矢量R必在Dj中；若错误图样不是陪集首，则接收矢量R不在Dj中，则译成其它码字，造成错误译码；当且仅当错误图样为陪集首时，译码才是正确的。可纠正的错误图样：这2n－k个陪集首称为可纠正的错误图样。6.2.6线性分组码的译码2023/2/512线性码纠错能力与监督元数目的关系：一个可纠t个错误的线性码必须满足

上式中等式成立时的线性码称为完备码。即[证明]：纠一个错误的(n,k)线性码，必须能纠正个错误图样，因此6.2.6线性分组码的译码2023/2/513对纠两个错误的(n,k)线性码，必须能纠个错误图样，所以依此类推，一个纠t个错误的(n,k)线性码必须满足对于完备码，由码的纠错能力所确定的伴随式数恰好等于可纠的错误图样数，所以完备码的(n－k)个监督码元得到了充分的利用。6.2.6线性分组码的译码2023/2/514定义：(n,k)线性码的所有2n－k个伴随式，在译码过程中若都用来纠正所有小于等于个随机错误，以及部分大于t的错误图样，则这种译码方法称为完备译码。限定距离译码：任一个(n,k)线性码，能纠正个随机错误，如果在译码时仅纠正t’<t个错误，而当错误个数大于t’时，译码器不进行纠错而仅指出发生了错误，称这种方法为限定距离译码。6.2.6线性分组码的译码2023/2/515从多维矢量空间的角度看完备码：假定围绕每一个码字Ci放置一个半径为t的球，每个球内包含了与该码字汉明距离小于等于t的所有接收码字R的集合；这样，在半径为t=[(dmin－1)/2]的球内的接收码字数是因为有2k个可能发送的码字，也就有2k个不相重叠的半径为t的球。包含在2k个球中的码字总数不会超过2n个可能的接收码字。于是一个纠t个差错的码必然满足不等式如果上式中等号成立，表示所有的接收码字都落在2k个球内，而球外没有一个码，这就是完备码。6.2.6线性分组码的译码

Here2023/2/516完备码特性：围绕2k个码字，汉明距离为t=[(dmin－1)/2]的所有球都是不相交的，每一个接收码字都落在这些球中之一，因此接收码与发送码的距离至多为t，这时所有重量≤t的错误图样都能用最佳（最小距离）译码器得到纠正，而所有重量≥t+1的错误图样都不能纠正。6.2.6线性分组码的译码2023/2/517举例：对纠一个错误的(7,4)汉明码，可见，(7,4)汉明码是一个完备码。所有汉明码都是完备码（满足2n－k=2m=n+1）。标准阵列译码=最小距离译码法=最佳译码法陪集首是可纠正的错误图样，为了使译码错误概率最小，应选取出现概率最大的错误图样作陪集首；重量较轻的错误图样出现概率较大，所以在构造标准阵列时是选取重量最轻的n重作陪集首；这样，当错误图样为陪集首时（可纠的错误图样），接收矢量与原发送码矢间的距离（等于陪集首）最小；6.2.6线性分组码的译码2023/2/518因此，选择重量最轻的元素作陪集首，按标准阵列译码就是按最小距离译码；所以标准阵列译码法也是最佳译码法。定理6.2.7：在标准阵列中，一个陪集的所有2k个n重有相同的伴随式，不同的陪集伴随式互不相同。[证明]：设H为给定(n,k)线性码的监督矩阵，在陪集首为El的陪集中的任意矢量R为R=El+Ci,i=1,2,…,2k其伴随式为S=RHT=(El+Ci)HT=ElHT+CiHT=ElHT上式表明：陪集中任意矢量的伴随式等于陪集首的伴随式。即同一陪集中所有伴随式相同。不同陪集中，由于陪集首不同所以伴随式不同。6.2.6线性分组码的译码2023/2/519③结论任意n重的伴随式决定于它在标准阵列中所在陪集的陪集首。标准阵列的陪集首和伴随式是一一对应的，因而码的可纠错误图样和伴随式是一一对应的，应用此对应关系可以构成比标准阵列简单得多的译码表，从而得到(n,k)线性码的一般译码步骤。(n,k)线性码的一般译码步骤计算接收矢量R的伴随式ST=HRT；根据伴随式和错误图样一一对应的关系，利用伴随式译码表，由伴随式译出R的错误图样E；将接收字减错误图样，得发送码矢的估值C’=R－E。6.2.6线性分组码的译码2023/2/520上述译码法称为伴随式译码法或查表译码法。线性分组码一般译码器译码器如图6.2.9。这种查表译码法具有最小的译码延迟和最小的译码错误概率，原则上可用于任何(n,k)线性码。6.2.6线性分组码的译码2023/2/521在通信中检纠错码的实际性能是在统计上体现出来的。以下分析均以BSC信道为模型。(1)不可检错误概率(2)译码错误概率(3)译码失败概率(4)比特误码率6.2.7线性分组码的性能2023/2/522(1)不可检错误概率pud由(n,k)线性码的重量分布求pud令Ai为码的重量分布，表示重量为i的码字个数，i=0,1,2,…,n；由于仅当错误图样与码矢集合中的非0码矢相同时，才不能检出错误，所以（p是BSC的误码率，且码字等概发送）举例：(7,3)码的重量分布是A0=1,A1=A2=A3=0,A4=7，其不可检错误概率为pud＝7×p4(1－p)3，若p=0.01，则pud≈6.8×10－8。利用(n,k)码重量分布与其对偶码的重量分布关系求pud设A0,A1,A2,…,An是(n,k)码的重量分布；B0,B1,B2,…,Bn是它的对偶码的重量分布；6.2.7线性分组码的性能2023/2/523对偶码的重量枚举式：下面的多项式称为(n,k)码和它的对偶码的重量枚举式。MacWilliams恒等式：若已知线性码的对偶码的重量分布，就可确定该码本身的重量分布。由式(6.2.23)得6.2.7线性分组码的性能2023/2/524令将这个恒等式代入式(6.2.26)得将恒等式和(6.2.25)代入上式得.6.2.7线性分组码的性能2023/2/525当k<(n－k)时，用式(6.2.28)计算pud比较简单；当k>(n－k)时，用式(6.2.29)计算pud则更容易。举例：已知(7,4)码的监督矩阵H(7,4)，它等于其对偶码的生成矩阵G(7,3)，即由此生成矩阵的行的线性组合，可得到(7,3)码的8个码字由此得到(7,3)对偶码的重量枚举式为B(x)=1+7x4利用式(6.2.29)得出(7,4)码的未检出错误概率为pud=2－3[1+7×(1－2p)4]－(1－p)7设p=0.01，则pud=6×10－6。6.2.7线性分组码的性能2023/2/526(2)译码错误概率pwe正确译码概率pwc：纠正小于等于t个差错的概率译码错误概率pwe译码错误发生在差错数目大于t，接收向量R与另一码字C’的距离小于等于t的情况；Di是重量i并译为错误码字的可能的接收向量R的数目，即译码错误概率pwe为6.2.7线性分组码的性能2023/2/527(3)译码失败概率pwf由于仍存在不满足式(6.2.30)的接收码矢R，对于限定距离译码器来说就处于译码失败状态，即pwf=1－pwc－pwe图6.2.30中RA—正确译码概率RB—译码错误概率RC—译码失败概率6.2.7线性分组码的性能2023/2/528(4)比特误码率pbc：信道的比特差错概率，对于BSC信道，pbc等于信道转移概率p。pbd：译码错误导致的码字之间的比特差错率。pbm：消息源与消息接收终端之间的比特差错概率。一般认为消息和码字之间的映射不改变码字差错导致在整个码长内比特差错的均匀分布特性，在统计意义上有pbm≈pbd6.2.7线性分组码的性能2023/2/529pbe译码错误的误码率：设码字是等概率发送，则是发送全0码字并错接收为重量为j的码字的概率；Pbe与pwe的关系码字错必然有至少2t+1位码字比特错；每个码字平均有位消息比特错，所以pbe与pwe有如下渐进关系6.2.7线性分组码的性能2023/2/530pbf译码失败造成的误码率pbd译码后总的误码率：pbd=pbe+pbf6.2.7线性分组码的性能2023/2/531汉明码是汉明于1950年提出的纠一个错误的线性码，也是第一个纠错码。由于它编码简单，因而是在通信系统和数据存储系统中得到广泛应用的一类线性码。汉明码的结构参数：纠一个错误的线性码，其最小距离dmin=3；监督矩阵任意两列线性无关/H的任两列互不相同；没有全0的列。监督元个数n－k=r；H阵中每列有r个元素，至多可构成2r－1种互不相同的非0列。对于任意正整数m≥3，汉明码的结构参数为码长：n=2m－1信息位数：k=2m－m－1监督位数：n－k=m码的最小距离：dmin=3(t=1)6.2.8汉明码2023/2/532汉明码监督矩阵构成的两种方式构成H阵的标准形式，H=[QIm]，其中Im为m阶单位子阵，子阵Q是构造Im后剩下的列任意排列。用这种形式的H阵编出的汉明码是系统码。按m重（重量为m）表示的二进制顺序排列。按这种形式H阵编出的码是非系统码。当发生可纠的单个错误时，伴随式为H阵中对应的列，所以伴随式的二进制数值就是错误位置号，有时这种码译码比较方便。由于汉明码可纠的错误图样数为6.2.8汉明码2023/2/533(1)扩展/Extending和打孔/Puncturing(2)增广/Augmenting和删信/Expunging/Expurgating(3)延长/Lengthening和缩短/Shortening(4)乘积/Product(5)级联/Concatenating(6)交织/Interleaving6.2.9由已知码构造新码的方法2023/2/534(1)扩展/Extending和打孔/Puncturing扩展：保持码字数k不变，增加冗余位数以增加码长。打孔：保持k不变，减小冗余位。可以认为是扩展的逆过程。(2)增广/Augmenting和删信/Expunging/Expurgating增广：保持n不变，增加码字数目k。删信：保持n不变减小k。(3)延长/Lengthening和缩短/Shortening延长：同时增加k和n。缩短：同时减小k和n。6.2.9由已知码构造新码的方法2023/2/535举例：(7,4,3)汉明码的各种修正关系如图6.2.31所示。6.2.9由已知码构造新码的方法2023/2/536(4)乘积/Product消息作为阵列，分别进行行列编码。(5)级联/Concatenating对消息编码后的码字再进行一次编码。级联编码的第一次所用码称外码；第二次所用码称内码。级联编码常用于既有随机差错又有突发差错的信道编码。(6)交织/Interleaving交织编码分为分组交织和卷积交织两种。如果交织编码所用的(n,k)码可以纠正t个随机差错，那么交织深度为D的交织编码可以纠正Dt长的突发错误。6.2.9由已知码构造新码的方法2023/2/537举例：视盘存储的纠错编码采用对(31,21)纠双错的BCH码进行256深度的交织，可以有效纠正因为介质损坏、磁（光）头污染或者定时抖动等引起的连续差错。6.2.9由