第6章信道编码-Qtech

1、第6章 信道编码 信道编码信道编码是以信息在信道上的正确传输为是以信息在信道上的正确传输为目标的编码，可分为两个层次上的问题：目标的编码，可分为两个层次上的问题：n如何正确接收载有信息的信号如何正确接收载有信息的信号线路编码线路编码n如何避免少量差错信号对信息内容的影如何避免少量差错信号对信息内容的影响响纠错编码纠错编码1本章内容n有扰离散信道的编码定理有扰离散信道的编码定理 n纠错编译码的基本原理与分析方法纠错编译码的基本原理与分析方法n线性分组码线性分组码 n卷积码卷积码26.1 有扰离散信道的编码定理 n差错和差错控制系统分类差错和差错控制系统分类n矢量空间与码空间矢量空间与码空间 n随

2、机编码随机编码 n信道编码定理信道编码定理 3差错类型n差错符号差错符号：由符号发生差错引起，也叫：由符号发生差错引起，也叫信信号差错号差错，信号差错概率用，信号差错概率用误码元率误码元率表示；表示；n差错比特差错比特：由信息比特发生差错引起，也：由信息比特发生差错引起，也叫叫信息差错信息差错，信息差错概率用，信息差错概率用误比特率误比特率表表示；示；n对于对于二进制二进制传输系统，符号差错等效于比传输系统，符号差错等效于比特差错；特差错；n对于对于多进制多进制系统，一个符号差错到底对应系统，一个符号差错到底对应多少比特差错却难以确定。因为一个符号多少比特差错却难以确定。因为一个符号由多个比特

3、组成。由多个比特组成。4差错图样（error pattern） n为了定量地描述信号的差错，定义收、为了定量地描述信号的差错，定义收、发码之发码之“差差”为为 ：差错图样差错图样E发码发码C 收码收码R （模（模M） n例：例：8进制进制(M=8)码元，码元，若发码若发码 C=（0,2,5,4,7,5,2）收码变为收码变为 R=（0,1,5,4,7,5,4）差错图样差错图样E=CR=（0,1,0,0,0,0,6）（模）（模8）5差错图样（error pattern）n二进制码：二进制码：E=C R 或或 C = R E ，差错图样，差错图样中的中的“”既是符号差错也是比特差错，差错的既是符号差

4、错也是比特差错，差错的个数叫汉明距离。个数叫汉明距离。 6差错图样类型 n随机差错随机差错：若差错图样上各码位的取值：若差错图样上各码位的取值既与前后位置无关又与时间无关，即差既与前后位置无关又与时间无关，即差错始终以相等的概率独立发生于各码字、错始终以相等的概率独立发生于各码字、各码元、各比特；各码元、各比特；n突发差错：突发差错：前后相关、成堆出现。突发前后相关、成堆出现。突发差错总是以差错码元开头、以差错码元差错总是以差错码元开头、以差错码元结尾，头尾之间并不是每个码元都错，结尾，头尾之间并不是每个码元都错，而是码元差错概率超过了某个额定值。而是码元差错概率超过了某个额定值。7纠错码分类

5、 n从功能角度从功能角度：检错码：检错码 、纠错码、纠错码 n对信息序列的处理方法对信息序列的处理方法：分组码、卷积：分组码、卷积码码n码元与原始信息位的关系码元与原始信息位的关系：线性码、非：线性码、非线性码线性码 n差错类型差错类型：纠随机差错码、纠突发差错：纠随机差错码、纠突发差错码、介于中间的纠随机码、介于中间的纠随机/突发差错码。突发差错码。n构码理论构码理论：代数码、几何码、算术码、：代数码、几何码、算术码、组合码等组合码等 8差错控制系统分类 n前向纠错（前向纠错（FEC）：发端信息经纠错编：发端信息经纠错编码后传送，收端通过纠错译码自动纠正码后传送，收端通过纠错译码自动纠正传递

6、过程中的差错传递过程中的差错 n反馈重发（反馈重发（ARQ）：）：收端通过检测接收收端通过检测接收码是否符合编码规律来判断，如判定码码是否符合编码规律来判断，如判定码组有错，则通过反向信道通知发端重发组有错，则通过反向信道通知发端重发该码该码 n混合纠错（混合纠错（HEC）：）：前向纠错和反馈重前向纠错和反馈重发的结合，发端发送的码兼有检错和纠发的结合，发端发送的码兼有检错和纠错两种能力错两种能力 96.1.2矢量空间与码空间 n基本的纠错码为（基本的纠错码为（n,k）分组码（块码）分组码（块码）n每块为每块为k个符号个符号n由由n个码元组成码字个码元组成码字n码字可视为码字可视为n重矢量（重

7、矢量（n个矢量元素）个矢量元素）1001(1)(,),iiiiji nijVV VVVVF6.1.2矢量空间与码空间 nF表示码元所在的数域表示码元所在的数域(对于二进制码，对于二进制码，F代表二元域代表二元域0,1)n设设n重有序元素的集合重有序元素的集合V= Vi , n若满足条件：若满足条件：nV中矢量元素在矢量加运算下构成加群；中矢量元素在矢量加运算下构成加群；nV中矢量元素与数域中矢量元素与数域F元素的标乘封闭在元素的标乘封闭在V中；中；n分配律、结合律成立，分配律、结合律成立， 则称集合则称集合V是数域是数域F上的上的n维维矢量空间矢量空间，或称，或称n维维线性空间线性空间，n维矢

8、量又称维矢量又称n重重(n-tuples)。1101(1)(,),iiiiji nijVV VVVVF矢量空间中矢量的关系 对于域对于域F上的若干矢量上的若干矢量n线性组合线性组合：n线性相关线性相关：其中任一矢量可表示为其它矢量的线性组合其中任一矢量可表示为其它矢量的线性组合n线性无关线性无关或或线性独立线性独立：一组矢量中的任意一个：一组矢量中的任意一个都不可能用其它矢量的线性组合来代替都不可能用其它矢量的线性组合来代替.。1212,ikVVVV及1 122,()kiiiVaVa VaVaF1 1220,()iiiaVa VaVaF且不全为零矢量空间与基底n一组线性无关的矢量一组线性无关的

9、矢量 ，其线性，其线性组合的组合的集合集合就构成了一个就构成了一个矢量空间矢量空间V，这，这组矢量就是这个矢量空间的组矢量就是这个矢量空间的基底基底。nn维矢量空间应包含维矢量空间应包含n个基底个基底 n基底不是唯一的基底不是唯一的，例：线性无关的两个，例：线性无关的两个矢量（矢量（1,0）和（）和（0,1）以及（）以及（-1,0）和）和（0,-1）可张成同一个两维空间）可张成同一个两维空间 。1312,nV VV二元域GF(2)上三重矢量空间 n以（以（100）为基底可张成）为基底可张成一维三重一维三重子空间子空间V1，含，含21 =2 个元素，即个元素，即n以以(010)(001)为基底可

10、张成为基底可张成二维三重二维三重子空间子空间V2，含含 22 =4个元素，即个元素，即n以以(100)(010)(001)为基底可张成为基底可张成三维三重三维三重空空间间V,含含 23 =8个元素，个元素，V1和和V2都是都是V的子空间。的子空间。141(000),(100)V2(000),(001),(010),(011)V概念n重数重数n构成矢量的有序元素的个数构成矢量的有序元素的个数n维数维数n构成矢量空间的基底的个数构成矢量空间的基底的个数15矢量空间n每个矢量空间或子空间中必然包含零矢量每个矢量空间或子空间中必然包含零矢量n两个两个矢量正交矢量正交：V1 V2 0 n两个两个矢量空间

11、正交矢量空间正交：某矢量空间中的任意：某矢量空间中的任意元素与另一矢量空间中的任意元素正交元素与另一矢量空间中的任意元素正交 n正交的两个子空间正交的两个子空间V1、V2互为互为对偶空间对偶空间 (Dual Space)，其中一个空间是另一个空，其中一个空间是另一个空间的间的零空间零空间（null space，也称零化空，也称零化空间）。间）。 16码空间 17 消息消息k长长 (n , k) 码字码字n长长 qk 种种 分组编码器分组编码器 qn种种 k维维k重矢量重矢量 n维维n重矢量重矢量 通常通常qn qk，分组编码的任务是，分组编码的任务是要在要在n维维n重矢量空间的重矢量空间的qn

12、种可能组合种可能组合中选择其中的中选择其中的qk个构成一个个构成一个码空间码空间，其元素就是许用码的其元素就是许用码的码集码集。 分组编码的任务 n选择一个选择一个维维n重子空间作为码空间。重子空间作为码空间。n确定由确定由k维维k重信息空间到重信息空间到维维n重码空间重码空间的映射方法。的映射方法。 码空间的不同码空间的不同选择方法，以及信息组选择方法，以及信息组与码组的不同映射算法，就构成了不同与码组的不同映射算法，就构成了不同的分组码。的分组码。186.1.3随机编码n编码的分析设计途径：编码的分析设计途径：n1.数学解析途径，即将代数、几何、数论等理数学解析途径，即将代数、几何、数论等

13、理论运用到编解码，如分组码，卷积码。论运用到编解码，如分组码，卷积码。n2.运用概率统计方法在特定信道条件下对编码运用概率统计方法在特定信道条件下对编码信号的性能作出统计分析，求出差错概率的上信号的性能作出统计分析，求出差错概率的上下限边界，其中最优码所能达到的差错概率上下限边界，其中最优码所能达到的差错概率上界称作界称作随机码界随机码界。n用这种方法不能得知最优码是如何具体编出来的，用这种方法不能得知最优码是如何具体编出来的，却能得知最优码可以好到什么程度，并进而推导出却能得知最优码可以好到什么程度，并进而推导出有扰离散信道的编码定理，对指导编码技术具有特有扰离散信道的编码定理，对指导编码技

14、术具有特别重要的理论价值。别重要的理论价值。 196.1.3随机编码n对于一个对于一个(N,K)分组编码器分组编码器n对对K个个q进制组成的消息组进制组成的消息组m=(m0,m1,mk-1)编码；编码；n生成生成N个个q进制符号组成的码字进制符号组成的码字c=(c0,c1,cN-1)；n在在(N,K)分组编码器中随机选定的码集有分组编码器中随机选定的码集有qNM种种 n一个消息组的编码有一个消息组的编码有qN种选择（种选择（N个码元，个码元，q进制）进制）nqK个消息组共有个消息组共有 种选择种选择n令令M= qK，可得上式可得上式20KqNq )(6.1.3随机编码n在在(N,K)分组编码器

15、中随机选定的码集有分组编码器中随机选定的码集有qNM个个 n第第m个码集个码集(记作记作cm )被随机选中的概率是被随机选中的概率是n设与这种选择相对应的条件差错概率是设与这种选择相对应的条件差错概率是Pe(cm)n全部码集的平均差错概率是全部码集的平均差错概率是()( )NMmPqc2111( ) ( )( )NMNMqqNMeemmemmmPPPqPccc6.1.3随机编码n必定存在某些码集必定存在某些码集n某些码集某些码集n若若 ，就必然存在一批码集就必然存在一批码集 即差错概率趋于零的好码一定存在；即差错概率趋于零的好码一定存在； 11( ) ( )( )NMNMqqNMeemmemm

16、mPPPqPccc22( )emePPc( )emePPc0eP ( )0emPc6.1.3随机编码n码集点数码集点数M=qK占占N维矢量空间总点数维矢量空间总点数qN的比例是的比例是F =qK / qN = q-(N-K) n当当K和和N的差值拉大即冗余的空间点数增加时，的差值拉大即冗余的空间点数增加时，平均而言码字的分布将变得稀疏，码字之间的平平均而言码字的分布将变得稀疏，码字之间的平均距离将变大，平均差错概率将变小。均距离将变大，平均差错概率将变小。 n当当F0 即即(N-K)时，能否让平均差错概时，能否让平均差错概率率 ？ nGallager在在1965年推导了年推导了 的上边界，并证

17、明这的上边界，并证明这个上边界是按指数规律收敛的。个上边界是按指数规律收敛的。 0eP 23eP6.1.4信道编码定理nE(R)为为可靠性函数可靠性函数，也叫误差指数；，也叫误差指数； n码率码率：R =( lbM) / N nM是可能的信息组合数，是可能的信息组合数，M=qKnN是每码字的码元数，是每码字的码元数，nR表示每码元携带的信息量，单位是比特每符表示每码元携带的信息量，单位是比特每符号（号（bit / symbol） 24()NE RePe6.1.4信道编码定理nR在在0,R0区间时：区间时：E(R)R曲线是斜率为曲线是斜率为-1（-45 ）的直线，）的直线，E(R)反反比于比于R

18、；n而当而当R=C（信道容量信道容量）时：时：E(R)=0，即可靠性，即可靠性为零。为零。 25 E(R) C R 0 R0 -45 E(R)和和R的关系曲线的关系曲线6.1.4信道编码定理n正定理正定理：只要传信率：只要传信率R小于信道容量小于信道容量C，总存在一种信道码（及解码器），可以总存在一种信道码（及解码器），可以以所要求的任意小的差错概率实现可靠以所要求的任意小的差错概率实现可靠的通信。的通信。n逆定理逆定理：信道容量：信道容量C是可靠通信系统传信是可靠通信系统传信率率R的上边界，如果的上边界，如果R C，就不可能有，就不可能有任何一种编码能使差错概率任意小。任何一种编码能使差错概

19、率任意小。 266.2 纠错编译码的基本原理与分析n内容：内容：n纠错编码的基本思路纠错编码的基本思路 n译码方法最优译码与最大似然译码译码方法最优译码与最大似然译码 276.2.1纠错编码的基本思路nR不变不变，信道容量大者，信道容量大者其可靠性函数其可靠性函数E(R)也大；也大；nC不变不变，码率减小时其，码率减小时其可靠性函数可靠性函数E(R)增大增大 。()NE RePe28E(R) R0 R1 R2 C1 C2 增大增大E(R)的途径的途径n信道编码定理信道编码定理6.2.1纠错编码的基本思路n增大信道容量增大信道容量C n扩展带宽：开发新的宽带媒体扩展带宽：开发新的宽带媒体n加大功

20、率：提高发送功率、提高天线增益加大功率：提高发送功率、提高天线增益n降低噪声：采用低噪声器件降低噪声：采用低噪声器件n减小码率减小码率R （R =( lbM) / N ）nQ、N不变而减小不变而减小K nQ、K不变而增大不变而增大NnN、K不变而减小不变而减小Qn增大码长增大码长N 296.2.1纠错编码的基本思路n另一种思路是从概念上分析纠错编码的基本原理，可以把纠错能力的获取归结为两条：一条是利用冗余度，另一条是噪声均化（随机化、概率化）103101027. 4)1 (101mmemePPmP30冗余度就是在信息流中插入冗余比特。例：3bit表示4种意义。为了传输这些冗余位，必然动用冗余的

21、资源。这些资源可以是：时间、频带、功率、设备复杂度噪声均化就是让差错随机化，就是设法将危害较大的、较为集中的噪声干扰分摊开来。1、增加码长N例：设某BSC信道误码率Pe=0.01，假如编码后的纠错能力是10%。先设码长N=10，码字中多于1位误码时就会产生译码差错，差错概率为：6.2.1纠错编码的基本思路405401092. 4)1 (401mmemePPmP31如果保持码率不变，将码长增加到N=40，那么当码字中多于4位误码时，会产生译码差错，差错的概率为n卷积：卷积码在一定约束长度内的若干码字之间加进了相卷积：卷积码在一定约束长度内的若干码字之间加进了相关性，译码时不是根据单个码字，而是一

22、串码字，这样就关性，译码时不是根据单个码字，而是一串码字，这样就可以将噪声分摊到码字序列而不是一个码字上。可以将噪声分摊到码字序列而不是一个码字上。n交错：交错是对付突发差错的有效措施。交错：交错是对付突发差错的有效措施。6.2.2最优译码与最大似然译码n译码器的任务译码器的任务是从受损的信息序列中是从受损的信息序列中尽可能正确地恢复出原信息。尽可能正确地恢复出原信息。n译码算法的已知条件是：译码算法的已知条件是：n实际实际接收到的码字序列接收到的码字序列r, r=(r1,r2,rN)n发端所采用的编码算法和该算法产生的发端所采用的编码算法和该算法产生的码集码集XN，满足，满足 n信道模型及信

23、道参数。信道模型及信道参数。 3212(,)NiiiiNc cccX6.2.2最优译码与最大似然译码n最佳译码最佳译码，也叫最大后验概率译码，也叫最大后验概率译码(MAP: Maximum a posteriori)n已知已知r的条件下找出可能性最大的发码作为译码估值的条件下找出可能性最大的发码作为译码估值n通过经验与归纳推测发码的方法通过经验与归纳推测发码的方法n实现困难实现困难33 消息组消息组mi 码字码字ci 接收码接收码r 估值估值 消息消息 icim编码器编码器 信道信道 译码译码 消息还原消息还原max (/ )iiPcc rmax (/ )iiPcc r6.2.2最优译码与最大

24、似然译码Maximum Likelihood Decodingn已知已知r的条件下使先验概率最大的译码算法的条件下使先验概率最大的译码算法34max (/ )iiPcc rmax( /)iiPcr c6.2.2最优译码与最大似然译码n如果如果n构成码集的构成码集的2K个码字以相同概率发送，满足个码字以相同概率发送，满足P(ci ) = 1/2K ， i=1,2,2K nP(r)对于任何对于任何r都有相同的值，满足都有相同的值，满足P(r) = 1/2K n则则P(ci /r)最大等效于最大等效于P(r / ci)的最大，在此前的最大，在此前提下最佳译码等效于最大似然译码。提下最佳译码等效于最大

25、似然译码。 35()(/)(/),1,2,2( )KiiiPPPiPcrccrr6.2.2最优译码与最大似然译码n对于无记忆信道，对于无记忆信道， n例：例：BSC信道的最大似然译码可以简化为信道的最大似然译码可以简化为最小汉明距离译码最小汉明距离译码。n汉明距离译码是一种硬判决译码。由于汉明距离译码是一种硬判决译码。由于BSC信道是对称的，只要发送的码字独立、信道是对称的，只要发送的码字独立、等概率等概率 ，汉明距离译码也就是最佳译码。，汉明距离译码也就是最佳译码。 361( /)(/)NijijjMaxPMaxP rcr c376.3 线性分组码n码集码集C能否构成能否构成n维维n重矢量空

26、间的一个重矢量空间的一个k维维n重子空间？重子空间？n如何寻找最佳的码空间？如何寻找最佳的码空间？nqk个信息元组以什么算法一一对应映射到码空间。个信息元组以什么算法一一对应映射到码空间。n码率编码效率：码率编码效率：Rc =k/n （二进制）；（二进制）； Rc =k*lbq/n (q进制进制)38 消息消息m (n , k) 码字码字c m=(mk-1,m1,m0) 分组编码器分组编码器 c=(cn-1,c1,c0) qk qn6.3.1生成矩阵和校验矩阵 c m G 1n 1k kn 码字码字 消息消息 生成矩阵生成矩阵 Ggk-1g1g0T，有，有k个个(1n)行矢行矢量，如何选择呢？

27、量，如何选择呢？39线性分组码的形成 c = mk-1 gk-1+ m1 g1+m0 g0 n码空间的所有元素（即码字）都可以写成码空间的所有元素（即码字）都可以写成k个基底个基底的线性组合；的线性组合；n由于由于k个基底即个基底即G的的k个行矢量线性无关，矩阵个行矢量线性无关，矩阵G的的秩一定等于秩一定等于k。n当信息元确定后，码字仅由当信息元确定后，码字仅由G矩阵决定，因此称矩阵决定，因此称这这kn 矩阵矩阵G为该为该(n,k)线性分组码的生成矩阵。线性分组码的生成矩阵。 40生成矩阵G(kn)的特点n想要保证想要保证 (n,k)线性分组码能够构成线性分组码能够构成k维维n重重子空间，子空

28、间，G 的的k个行矢量个行矢量gk-1, g1, g0必须是必须是线性无关的，只有这样才符合作为基底的线性无关的，只有这样才符合作为基底的条件。条件。n由于基底不是唯一的，所以由于基底不是唯一的，所以G也就不是唯也就不是唯一的。一的。 n不同的基底有可能生成同一码集，但因编不同的基底有可能生成同一码集，但因编码涉及码集和映射两个因素，码集一样而码涉及码集和映射两个因素，码集一样而映射方法不同也不能说是同样的码。映射方法不同也不能说是同样的码。 41系统形式的生成矩阵 (n,k)码的任何生成矩阵都可以通过行运算码的任何生成矩阵都可以通过行运算（以及列置换）简化成（以及列置换）简化成“系统形式系统

29、形式” 。G = Ik P =Ik是是kk单位矩阵，单位矩阵，P是是k(n-k)矩阵。矩阵。 42(1)(1)(1)1(1)01(1)11100(1)01001000100001kn kkkn kn kppppppppp 生成的码字Cn前前k位由单位矩阵位由单位矩阵Ik决定，等于把信息组决定，等于把信息组m原封原封不动搬到码字的前不动搬到码字的前k位；位；n其余的其余的n-k位叫冗余位或位叫冗余位或一致校验位一致校验位，是前，是前k个个信息位的线性组合。信息位的线性组合。n这样生成的（这样生成的（n,k）码叫做）码叫做系统码系统码。n若生成矩阵若生成矩阵G不具备系统形式，则生成的码叫不具备系统

30、形式，则生成的码叫做做非系统码非系统码。n系统化不改变码集，只是改变了映射规则。系统化不改变码集，只是改变了映射规则。 43空间构成nn维维n重空间有相互重空间有相互正交的正交的n个基底个基底n选择选择k个基底构成码个基底构成码空间空间Cn选择另外的选择另外的(n-k)个个基底构成空间基底构成空间DnC和和H是对偶的是对偶的 CDT0, GHT=044 n维维n重空间重空间V k维维k重重 k维维n重重 n-k维维 信息组信息组 码空间码空间 n重对偶重对偶 空间空间m C 空间空间D GH对偶空间n与与(n,k)分组线性码的码空间分组线性码的码空间C相对应，必然存相对应，必然存在一个对偶空间

31、在一个对偶空间D：n码空间基底数为码空间基底数为k,找出另外找出另外n-k个基底，可找到对偶个基底，可找到对偶空间；空间；n用用n-k个基底生成的个基底生成的(n,n-k)分组线性码，称为分组线性码，称为(n,k)分分组线性码的对偶码。组线性码的对偶码。45校验矩阵n将将H空间的空间的n-k个基底排列起来可构成一个个基底排列起来可构成一个(n-k)n矩阵，称为矩阵，称为校验矩阵校验矩阵H。用来校验接收到的。用来校验接收到的码字是否是正确的；码字是否是正确的；ncHT=0 (任意码字正交与任意码字正交与H的任意行矢量的任意行矢量)nG是是(n,k)码的生成矩阵，码的生成矩阵，H是它的校验矩阵；是

32、它的校验矩阵；nH是是(n,n-k)对偶码的生成矩阵，它的每一行是一个对偶码的生成矩阵，它的每一行是一个基底。基底。 G则是它的校验矩阵。（对偶是相互的）则是它的校验矩阵。（对偶是相互的）nGHT=0 ，H PT In-k ，二进制时，负号可省，二进制时，负号可省略。略。46n例例6-2(6,3)线性分组码，其生成矩阵线性分组码，其生成矩阵是是 G= 求：求：(1)计算码集，列出信息组与码字的映射关系。计算码集，列出信息组与码字的映射关系。(2)将该码系统化处理后，计算系统码码集并列将该码系统化处理后，计算系统码码集并列出映射关系。出映射关系。(3)计算系统码的校验矩阵计算系统码的校验矩阵H。

33、若收码。若收码r = 100110, 检验它是否码字？检验它是否码字？ (4)根据系统码生成矩阵画出编码器电原理图。根据系统码生成矩阵画出编码器电原理图。 471 1 1 0 1 0 1 1 0 0 0 1 0 1 1 1 0 1 例6-2 码集与映射关系（1） c = mk-1 gk-1+ m1 g1+m0 g0 48信息 码字 系统码字000 000000 0000000010111010010110101100010101100111011000111011001110101001111011001111011001100010111100011110101101110101 1 1 0

34、 1 0 1 1 0 0 0 1 0 1 1 1 0 1 例6-2 计算系统码码集（2）将G改写成改写成= Ik P 形式：形式：491 1 1 0 1 0 1 1 0 0 0 1 0 1 1 1 0 1 原原 行相加作为第行相加作为第1 1行；行；原原 行相加作为第行相加作为第2 2行；行；原原 行相加作为第行相加作为第3 3行；行；得到矩阵：得到矩阵：1 0 0 1 1 1 0 1 0 1 1 0 0 0 1 0 1 1 例6-2 计算系统码码集（2） c = mk-1 gk-1+ m1 g1+m0 g0 ，结果如下：，结果如下：50信息 码字 系统码字000 000000 0000000

35、01 011101 001011010 110001 010110011 101100 011101100 111010 100111101 100111 101100110 001011 110001111 010110 1110101 0 0 1 1 1 0 1 0 1 1 0 0 0 1 0 1 1 码集未变，但映射关系变了！码集未变，但映射关系变了！例6-2 计算校验矩阵H（3）511 0 0 | 1 1 1 0 1 0 | 1 1 0 0 0 1 | 0 1 1 G = = G = = I3|P,H = H = PT|In-k =1 1 0 | 1 0 0 1 1 1 | 0 1 0

36、 1 0 1 | 0 0 1 不同的不同的3个基底分别个基底分别构成了码空间和对偶构成了码空间和对偶码空间；码空间；若收码若收码r=100110，rHrHT T = 100110 = 0010, = 100110 = 0010,不是码字。不是码字。 T001|101010|111100|110例6-2 编码器电原理图（4）：52C=(c5,c4,c3,c2,c1,c0=(m2,m1,m0,c2,c1,c0)=m2100111+m1010110+m0001011,求解得到：C5=m2C4=m1C3=m0c2=m2+m1C1=m2+m1+m0C0=m2+m01 0 0 | 1 1 1 0 1 0

37、| 1 1 0 0 0 1 | 0 1 1 例6-2 编码器电原理图（4）：53 m0m1m2 输入 输出 c0c1c26.3.2 伴随式与标准阵列译码 m C=(cn-1,c1,c0) R=(rn-1,r1,r0) (n,k) 信道信道定义定义差错图案差错图案E E(en1,e1,e0) RC (rn-1cn-1,r1c1,r0c0) 二进制码中模二进制码中模2加与模加与模2减是等同的，因此有减是等同的，因此有E = R C 及及R = C E 54伴随式S的定义因为因为CHT = 0 （码字与校验矩阵的正交性）（码字与校验矩阵的正交性）所以所以RHT(CE)HTCHTEHT= EHT如果收

38、码无误：必有如果收码无误：必有RC即即E0， 则则EHT= 0 RHT = 0。如果收码有误：即如果收码有误：即E 0， 则则RHT = EHT 0。 在在HT固定的前提下，固定的前提下，RHT仅仅与差仅仅与差错图案错图案E有关，而与发送码有关，而与发送码C无关。定义无关。定义伴随式伴随式S S = (sn-k-1,s1,s0) = RHT = EHT 55 伴随式S的意义n从物理意义上看，伴随式从物理意义上看，伴随式S并不反映发送的码字是并不反映发送的码字是什么，而只是反映信道对码字造成怎样的干扰。什么，而只是反映信道对码字造成怎样的干扰。n差错图案差错图案E是是n重矢量，共有重矢量，共有2

39、n个可能的组合，而个可能的组合，而伴随式伴随式S是是(n-k)重矢量，只有重矢量，只有2n-k个可能的组合，个可能的组合，因此不同的差错图案可能有相同的伴随式。因此不同的差错图案可能有相同的伴随式。n接收端收到接收端收到R后，因为已知后，因为已知HT，可求出，可求出 SRHT；如果能知道对应的如果能知道对应的E，则通过，则通过C = RE而求得而求得C。 56 差错图案E的求解(1) 可以通过解线性方程求解可以通过解线性方程求解E：S = (sn-k-1,s1,s0) = EHT = (en-1, e1,e0)得到线性方程组：得到线性方程组：sn-k-1=en-1h(n-k-1)(n-1)+e

40、1h(n-k-1)1+ e0 h(n-k-1)0 s1 = en-1h1(n-1) + + e1 h11 + e0 h10s0 = en-1h0(n-1) + + e1 h01 + e0 h0057(1)(1)(1)1(1)01(1)11100(1)0100Tn knn kn knnhhhhhhhhh 差错图案E的求解(2) n上述方程组中有上述方程组中有n个未知数个未知数en1, e1,e0 ，却只，却只有有n-k个方程，可知方程组有多解。个方程，可知方程组有多解。n在有理数或实数域中，少一个方程就可能导致在有理数或实数域中，少一个方程就可能导致无限多个解，而在二元域中，少一个方程导致无限多

41、个解，而在二元域中，少一个方程导致两个解，少两个方程四个解，以此类推，少两个解，少两个方程四个解，以此类推，少n-( n-k) = k个方程导致每个未知数有个方程导致每个未知数有2k个解。个解。n因此，由上述方程组解出的因此，由上述方程组解出的E可以有可以有2k个解。个解。到底取哪一个作为附加在收码到底取哪一个作为附加在收码R上的差错图案上的差错图案E的估值呢？的估值呢？n概率译码：概率译码：把所有把所有2k个解的重量个解的重量(差错图案差错图案E中中1的个数的个数)作比较，选择其中最轻者作为作比较，选择其中最轻者作为E的估的估值。该方法概念上很简单但计算效率不高。值。该方法概念上很简单但计算

42、效率不高。5859依据：依据：若若BSC信道的差错概率是信道的差错概率是p，则长度，则长度n的码中错误概率的码中错误概率 ： 0个错个错 1个错个错 2个错个错 n个错个错 (1-p)n p(1-p)n-1 p2(1-p)n-2 pn 由于由于p 出错越少的情况，发生概率越大，出错越少的情况，发生概率越大，E的重量越轻。的重量越轻。所以该译码方法实际上体现了最小距离译码准则，所以该译码方法实际上体现了最小距离译码准则，即最大似然译码。即最大似然译码。标准阵列译码表 上述的概率译码，如每接收一个码上述的概率译码，如每接收一个码R就要解一次线性方程，太麻烦！就要解一次线性方程，太麻烦！ 伴随式伴随

43、式S的数目是有限的的数目是有限的2n-k个，如个，如果果n-k不太大，可以预先把不同不太大，可以预先把不同S下的方下的方程组解出来，把各种情况下的最大概率程组解出来，把各种情况下的最大概率译码输出列成一个码表。译码输出列成一个码表。 在实时译码时就不必再去解方程，而在实时译码时就不必再去解方程，而只要象查字典那样查一下码表就可以了。只要象查字典那样查一下码表就可以了。这样构造的表格叫做这样构造的表格叫做标准阵列译码表标准阵列译码表。 60标准阵列译码表的构成 n表中所列码字是接收到的码字表中所列码字是接收到的码字R；n将没有任何差错时的收码将没有任何差错时的收码R放在放在第一行第一行，收码等于

44、发码，收码等于发码R=C(C Ci,i =0,1,2k-1), 差错图案为全零差错图案为全零E0=(0,00)，伴随，伴随式为全零式为全零S0=(0,00)。由于有。由于有2k个码字，码表有个码字，码表有2k列。列。n在第在第2到第到第n+1的的n行中差错图案的所有重量为行中差错图案的所有重量为1 (共共n个个)。612n2n如果总行数如果总行数(1+n + )仍然小于仍然小于2n-k，再列出带有，再列出带有3个差错的个差错的图案，以此类推，直到放满图案，以此类推，直到放满2n-k行，每行一个行，每行一个Ej, 对应一个不对应一个不同的伴随式同的伴随式Sj。这样，表的行数。这样，表的行数2n-

45、k正好等于伴随式的数目。正好等于伴随式的数目。如果如果(1+ n)2n-k，再在下面行写出全部带有，再在下面行写出全部带有2个差错的图个差错的图案案(共共 个个)。62S0 E0S1 E1 Sj Ej E0+C0= 0+0= 0E0+C1= C1E0+Ci= CiE1+C0= E1 E1+Ci Ej+C0= EjEj+C1Ej+Ci 标准阵列译码表标准阵列译码表在码表的第在码表的第j行、第行、第i列填入列填入Ci+Ej： E1+C1 11022n kn k ECE1122n kn k SE112n k EC12n ki EC1221n kk EC21kjEC121kEC02121kkECC陪集

46、和子集n译码表中有译码表中有2n-k行，每行是一个行，每行是一个陪集陪集，每陪集的第一，每陪集的第一个元素个元素(位于第一列位于第一列)叫叫陪集首陪集首。同一陪集（同一行）。同一陪集（同一行）中的所有元素对应共同的一个伴随式。第一行陪集的中的所有元素对应共同的一个伴随式。第一行陪集的陪集首是全零伴随式陪集首是全零伴随式S0所对应的全零差错图案所对应的全零差错图案E0(无差无差错错)，而第，而第j行陪集的陪集首是伴随式行陪集的陪集首是伴随式Sj所对应的重量所对应的重量最小的差错图案最小的差错图案Ej (C0=0, Rj=Ej)。n译码表中有译码表中有2k列，每列是一个列，每列是一个子集子集，每子

47、集的第一个，每子集的第一个元素元素(位于第一行位于第一行)叫叫子集头子集头。同一子集（同一列）中。同一子集（同一列）中的所有元素对应同一个码字，第一列子集的子集头是的所有元素对应同一个码字，第一列子集的子集头是全零码字全零码字C0，而第，而第i列子集的子集头是码字列子集的子集头是码字Ci (E0=0, Ri=Ci) 。6364例例 6-3 一个一个(5,2)系统线性码的生成矩阵是系统线性码的生成矩阵是G = 设收码设收码R = (10101)，构造标准阵列译码表，译出发码的估值，构造标准阵列译码表，译出发码的估值解：解：(1)构造标准阵列译码表。分别以信息组构造标准阵列译码表。分别以信息组m=

48、 (00)、(01) 、(10)、(11)及已知的及已知的G求得求得4个许用码字为（个许用码字为（c = mk-1 gk-1+ m1 g1+m0 g0 =mG)C1 =(00000)、C2 = (10111) 、C3 = (01101)、C4 = (11010)。求出校验矩阵：求出校验矩阵： H = PT I3 = 列出方程组：列出方程组：1011011101ic 242322212014131211100403020100111001001011001hhhhhhhhhhhhhhh24243232221 2102043214 143 132 121 110 104104043 032021

49、01000430se he he he he heeese he he he he heese he he he he heeeS = EHT65伴随式有伴随式有2n-k238种组合，差错图案中代表无差错的有一种，代表种组合，差错图案中代表无差错的有一种，代表一个差错的图案有一个差错的图案有 种，已有种，已有6种。种。代表两个差错的图案有代表两个差错的图案有 种。只需挑选其中的两个就可凑足种。只需挑选其中的两个就可凑足8种种组合。组合。挑选方法可有若干种，不是唯一的。先将挑选方法可有若干种，不是唯一的。先将Ej=(00000)、(10000)、(01000)、(00100)、(00010)、(

50、00001)代入上面的线性方程组，解得对代入上面的线性方程组，解得对应的应的Sj分别是分别是(000)、(111)、(101)、(100)、(010)、(001)。剩下的伴随式中，剩下的伴随式中，(011)所对应的差错图案是所对应的差错图案是2k个即个即(00011)、(10100)、(01110)、(11001),其中其中(00011)和和(10100)并列重量最轻，任选其中一个并列重量最轻，任选其中一个如如(00011)。同样可得伴随式。同样可得伴随式(110)所对应的最轻差错图案之一是所对应的最轻差错图案之一是(00110)。 551 5102 例例 6-3 译码表的构成译码表的构成66

51、S0=000E0+C0=00000C1=10111C2=01101C3=11010S1=111E1=10000001111110101010S2=101E2=01000111110010110010S3=100E3=00100100110100111110S4=010E4=00010101010111111000S5=001E5=00001101100110011011S6=011E6=00011101000111011001S7=110E7=00110100010101111100例例 6-3 标准阵列译码表标准阵列译码表（第（第j行、第行、第i列填入列填入Ci+Ej）例 6-3 将接收码R

52、10101译码 可选以下三种方法之一译码：可选以下三种方法之一译码：n直接搜索码表，查得直接搜索码表，查得(10101)所在列的子集头是所在列的子集头是(10111)，因此译码输出取为因此译码输出取为(10111)。n先求伴随式先求伴随式RHT = (10101) HT = (010) = S4，确定，确定S4所在所在行，再沿着行对码表作一维搜索找到行，再沿着行对码表作一维搜索找到(10101), 最后顺着所在最后顺着所在列向上找出码字列向上找出码字(10111)。n先求出伴随式先求出伴随式RHT = (010) = S4并确定并确定S4所对应的陪集首所对应的陪集首（差错图案）（差错图案）E4

53、=(00010)，再将陪集首与收码相加得到码字，再将陪集首与收码相加得到码字C= R+ E4= (10101)+ (00010)= (10111)。 上述三种方法由上而下，查表的时间下降而所需计算量增上述三种方法由上而下，查表的时间下降而所需计算量增大，实际使用时可针对不同情况选用。大，实际使用时可针对不同情况选用。6768 对上例作进一步分析，还可以看到，该对上例作进一步分析，还可以看到，该(5,2)码的码的dmin=3, 纠错能力是纠错能力是t = INT(3-1)/2 = 1。因此，译码阵列中。因此，译码阵列中只有前只有前6行具有唯一性、可靠性，真正体现了最大似然译行具有唯一性、可靠性，

54、真正体现了最大似然译码准则，而第码准则，而第7、8行的差错图案行的差错图案(00011)和和(00110)中包含两中包含两个个“1”，已超出了，已超出了t= 1的纠错能力，译码已不可靠。比如，的纠错能力，译码已不可靠。比如，当收码当收码R(10100)时，根据码表译出的码字是时，根据码表译出的码字是(10111)，与，与收码收码R的汉明距离是的汉明距离是2，然而收码，然而收码R与全零码字与全零码字(00000)的汉的汉明距离也是明距离也是2，为什么不能译成，为什么不能译成(00000)呢？事实上，码表呢？事实上，码表的第的第7、8行本身就不是唯一的。注意在码表计算过程中，行本身就不是唯一的。注

55、意在码表计算过程中，伴随式伴随式(011)所对应的所对应的4个差错图案中有两个并列重量最轻，个差错图案中有两个并列重量最轻，如果当时选的不是如果当时选的不是(00011)而是而是(10100)，那么码表第，那么码表第7行就行就不是现在这样了。不是现在这样了。 对例对例 6-3的的分析分析6.3.3码距、纠错能力、MDC码及重量谱 nN重码矢重码矢c = (cn-1,c n-2,c1,c0)可与可与N维矢量维矢量空间空间XN中的一个点对应，全体码字所对中的一个点对应，全体码字所对应的点构成矢量空间里的一个子集应的点构成矢量空间里的一个子集 ；n发码一定在这个子集里，传输无误时的发码一定在这个子集

56、里，传输无误时的收码也一定位于该子集；收码也一定位于该子集； n当出现差错时，接收的当出现差错时，接收的N重矢量重矢量:n对应到子集外空间某一点对应到子集外空间某一点 ；n对应到该子集，却对应到该子集的另一点上；对应到该子集，却对应到该子集的另一点上； 696.3.3码距、纠错能力、MDC码及重量谱 n码集各码字间的距离码集各码字间的距离是不同的，码距最小是不同的，码距最小者决定码的特性，称者决定码的特性，称之为之为最小距离最小距离dmin；ndmin表明各码字差异表明各码字差异程度，差异越大，抗程度，差异越大，抗干扰能力越强；干扰能力越强；n这里这里dmin=3，纠错能，纠错能力是力是1，检

57、错能力是，检错能力是270td=7dmin=3d=5C1C2C3C4C56.3.3码距、纠错能力、MDC码及重量谱 n定理定理6.1 任何最小距离任何最小距离dmin的线性分组码，的线性分组码，其检错能力为（其检错能力为（dmin-1）, 纠错能力纠错能力t为为71min12dtINT 定理定理6.2 线性分组码的最小距离等于码线性分组码的最小距离等于码集中非零码字的最小重量集中非零码字的最小重量 dmin = min w (C i ) C i C 及及C i 0 6.3.3码距、纠错能力、MDC码及重量谱 n定理定理6.3 (n,k) 线性分组码最小距离等于线性分组码最小距离等于dmin的充

58、要条件是：校验矩阵的充要条件是：校验矩阵H中有中有（dmin-1)列线性无关。列线性无关。n定理定理6.4 (n,k) 线性分组码的最小距离必线性分组码的最小距离必定小于等于定小于等于 (n-k+1)dmin (n-k+1) 726.3.3码距、纠错能力、MDC码及重量谱 例：例： H (7，4)线性码线性码 各列都不相同，任意各列都不相同，任意2列之和不等于列之和不等于0，2列线性无关；任意列线性无关；任意2列之和一定等于矩列之和一定等于矩阵中某一列，任意阵中某一列，任意3列线性相关。所以该列线性相关。所以该码的最小距离为码的最小距离为3，小于，小于n-k +14。7311101000111

59、01011010016.3.3码距、纠错能力、MDC码及重量谱 n（n,k）线性码最小距离）线性码最小距离dmin的上边界是的上边界是n-k +1。如果我们设计的（如果我们设计的（n,k）线性码的）线性码的dmin达到了达到了n-k +1，就是达到了设计性能的极点。因此，就是达到了设计性能的极点。因此，dmin n-k +1的码称为的码称为极大最小距离码极大最小距离码 (MDC Maximized minimum Distance Code)。n总体的、平均的纠错能力不但与最小距离有总体的、平均的纠错能力不但与最小距离有关，而且与其余码距或者说与码字的重量分关，而且与其余码距或者说与码字的重量

60、分布特性有关。布特性有关。 746.3.4完备码(Perfect code) n任何一个二元任何一个二元(n,k)线性分组码都有线性分组码都有2n-k个伴随式，个伴随式，假如该码的纠错能力是假如该码的纠错能力是t，则对于任何一个重量小，则对于任何一个重量小于等于于等于t的差错图案，都应有一个伴随式与之对应，的差错图案，都应有一个伴随式与之对应，也就是说，伴随式的数目满足条件也就是说，伴随式的数目满足条件 7502012tnkinnnnnti上式称作汉明限，任何一个纠上式称作汉明限，任何一个纠t码都应满足上述条件。码都应满足上述条件。6.3.4完备码 某二元某二元(n,k)线性分组码能使等式线性