信息论与编码第6章(2)(纠错)

1、第第6 6章章 信道编码信道编码 2021-10-91第六章第六章信道编码信道编码 第第6 6章章 信道编码信道编码 2021-10-92 XNUUY第第6 6章章 信道编码信道编码 2021-10-936.16.1 有扰离散信道的编码理论有扰离散信道的编码理论6.26.2 纠错编译码的基本原理与分析方法纠错编译码的基本原理与分析方法6.3 6.3 线性分组码线性分组码6.4 6.4 卷积码卷积码6.56.5 其它信道编码其它信道编码内容第第6 6章章 信道编码信道编码 2021-10-946.1 6.1 有扰离散信道的编码定理有扰离散信道的编码定理 6.1 .1 6.1 .1 差错和差错控制

2、系统分类差错和差错控制系统分类 6.1 .2 6.1 .2 矢量空间与码空间矢量空间与码空间 6.1 .3 6.1 .3 随机编码与信道编码定理随机编码与信道编码定理第第6 6章章 信道编码信道编码 2021-10-956.1.1 6.1.1 差错和差错控制系统分类差错和差错控制系统分类是衡量传输质量的重要指标之一是衡量传输质量的重要指标之一,它有几种不同的定它有几种不同的定义。义。 码元差错率码元差错率/符号差错率符号差错率 指在传输的指在传输的码元码元总数中发生差错的码元数所占的比例总数中发生差错的码元数所占的比例(平平均值均值),简称简称误码率误码率(Error symbol rate)

3、。 是指是指差错概率差错概率 比特差错率比特差错率 /比特误码率比特误码率(Error bit rate)： 在传输的在传输的比特比特总数中发生差错的比特数所占比例总数中发生差错的比特数所占比例 是指是指差错概率差错概率 对对二进制二进制传输系统传输系统,符号差错等效于比特差错符号差错等效于比特差错;对多进制系统对多进制系统,一个符号差错对应多少比特差错却难以确定一个符号差错对应多少比特差错却难以确定第第6 6章章 信道编码信道编码 2021-10-96 为定量地描述信号的差错为定量地描述信号的差错,定义定义差错图样差错图样E: E=CR (模模M ) 最常用的二进制码可当作特例来研究最常用的

4、二进制码可当作特例来研究,其差错图样等于收其差错图样等于收码与发码的模码与发码的模2加加,即即 E = C R 或或 C = R E 设发送的码字设发送的码字C 1 1 1 1 1 1 1 1 1 1 接收的码字接收的码字R 1 0 0 1 0 0 1 1 1 1 差错的图样差错的图样E 0 1 1 0 1 1 0 0 0 0 差错图样中的差错图样中的“1”既是符号差错也是比特差错既是符号差错也是比特差错,差错的个差错的个数叫数叫汉明距离汉明距离。 差错图样类型差错图样类型 随机差错随机差错, 突发差错突发差错：差错图样差错图样第第6 6章章 信道编码信道编码 2021-10-97纠错码分类纠

5、错码分类 从功能角度讲从功能角度讲, ,差错码分为差错码分为检错码检错码和和纠错码纠错码 按照对信息序列的处理方法按照对信息序列的处理方法, ,有有分组码分组码和和卷积码卷积码 按照码元与原始信息位的关系按照码元与原始信息位的关系, ,分为线性码和非线性分为线性码和非线性码码 按照适用的差错类型按照适用的差错类型, ,分成分成: :纠随机差错码和纠突发差纠随机差错码和纠突发差错码错码 按照构造码的理论：代数码、几何码、算术码和组合按照构造码的理论：代数码、几何码、算术码和组合码。码。第第6 6章章 信道编码信道编码 2021-10-98信道编码的基本思想信道编码的基本思想 信道编码信道编码 按

6、一定规则给数字序列按一定规则给数字序列m增加一些增加一些多余多余的码元的码元,使使不具有规律性的信息序列不具有规律性的信息序列 m 变换为具有某种规律变换为具有某种规律性的数码序列性的数码序列 C； 码序列中的码序列中的信息序列码元信息序列码元与与多余码元多余码元之间是之间是的；的； 信道译码器利用这种信道译码器利用这种预知的预知的编码规则译码。检验编码规则译码。检验接收到的数字序列接收到的数字序列 R 是否符合既定的是否符合既定的 规则规则,从而从而发现发现 R 中是否有错中是否有错,或者纠正其中的差错；或者纠正其中的差错； 根据根据来检测来检测/发现和纠正发现和纠正传输过程中产生的传输过程

7、中产生的差错就是信道编码的基本思想。差错就是信道编码的基本思想。第第6 6章章 信道编码信道编码 2021-10-99差错控制系统分类差错控制系统分类 前向纠错前向纠错(FEC)(FEC)：发送端的信道编码器将信息码组编成具有一定发送端的信道编码器将信息码组编成具有一定纠错能力纠错能力的码。的码。 自动请求重发自动请求重发(ARQ)： 发端发送发端发送检错码检错码, 如如CRC(循环冗余校验码循环冗余校验码) 混合纠错混合纠错(HEC)： 是是FEC与与ARQ方式的结合。方式的结合。 信息反馈信息反馈(IRQ)：第第6 6章章 信道编码信道编码 2021-10-9106.1.2 矢量空间与码空

8、间矢量空间与码空间分组码的一个码字可以看作一个分组码的一个码字可以看作一个n重矢量，所以可以用重矢量，所以可以用矢量空间矢量空间来分析和理解分组码。来分析和理解分组码。 F表示码元所在的数域，对于二进制码，表示码元所在的数域，对于二进制码，F代表二元域代表二元域0,1。设。设n重有序元素的集合重有序元素的集合V= Vi , 则称集合则称集合V是数域是数域F上的上的n维维矢量空间矢量空间，或称，或称n维维线性空间线性空间，n维维矢量又称矢量又称n重重(n-tuples)。线性空间的基底、线性空间的基底、自然基底、子空间、矢量正交、矢量自然基底、子空间、矢量正交、矢量空间正交、对偶空间空间正交、对

9、偶空间“重数重数”：构成矢量的有序元素的个数；：构成矢量的有序元素的个数；“维数维数”：张成矢量空间：张成矢量空间基底的个数；维数不可能大于重数，而当维数小于重数时说明这基底的个数；维数不可能大于重数，而当维数小于重数时说明这是个子空间。是个子空间。第第6 6章章 信道编码信道编码 2021-10-911码空间和分组编码的任务码空间和分组编码的任务 消息消息k长长 (n , k) 码字码字n长长 qk 种种 分组编码器分组编码器 qn种种 k维维k重矢量重矢量 n维维n重矢量重矢量 通常通常qn qk，分组编码的任务是要在，分组编码的任务是要在n维维n重矢量空间的重矢量空间的qn种种可能组合中

10、选择其中的可能组合中选择其中的qk个构成一个个构成一个码空间码空间，其元素就是许用码，其元素就是许用码的的码集码集。 选择一个选择一个维维n重子空间作为码空间。重子空间作为码空间。 确定由确定由k维维k重信息空间到重信息空间到维维n重码空间的映射方法。重码空间的映射方法。 码空间的不同选择方法，以及信息组与码组的不同码空间的不同选择方法，以及信息组与码组的不同映射算法，就构成了不同的分组码。映射算法，就构成了不同的分组码。第第6 6章章 信道编码信道编码 2021-10-9126.1.3 随机编码与信道编码定理随机编码与信道编码定理 如果不考虑编码的具体方法，而是运用概率统计的方法如果不考虑编

11、码的具体方法，而是运用概率统计的方法在特定信道条件下对编码信号的性能作出统计分析，求出差在特定信道条件下对编码信号的性能作出统计分析，求出差错概率的上，下限边界，其中最优码所能达到的差错概率上错概率的上，下限边界，其中最优码所能达到的差错概率上界称为随机码界。界称为随机码界。随机编码的含义随机编码的含义机编码。间，则称这种编码为随果随机的选取一个子空种选法，如该子空间的选取有好多重空间的一个子空间。维成的空间为个码字组由所有重空间中的一个元素，维所以码字为码字的长度为个不同的消息。而总共有元符号组成的码组，则个，由编成长度为种符号。其中每个消息有分组码，设消息组对于NNqNNNqqNNqmmm

12、mKNkkk,),.,(),(110第第6 6章章 信道编码信道编码 2021-10-913错误概率的上界错误概率的上界对于离散无记忆信道（对于离散无记忆信道（DMC）。错误平均）。错误平均概率的上界为：概率的上界为：exp( )ErPNE R E(R)为为可靠性函数可靠性函数，也叫误差指数，也叫误差指数 码率码率：R =( lbM) / N M是可能的信息组合数，是可能的信息组合数，M=qK N是每码字的码元数，是每码字的码元数， R表示每码元携带的信息量，单位是每符号比特表示每码元携带的信息量，单位是每符号比特（bit / symbol） 是全部码集的平均差错概率是全部码集的平均差错概率e

13、P第第6 6章章 信道编码信道编码 2021-10-914 正定理正定理：只要传信率：只要传信率R小于信道容量小于信道容量C，总存在一，总存在一种信道码（及解码器），可以以所要求的任意小的种信道码（及解码器），可以以所要求的任意小的差错概率实现可靠的通信。差错概率实现可靠的通信。 逆定理逆定理：信道容量：信道容量C是可靠通信系统传信率是可靠通信系统传信率R的上的上边界，如果边界，如果R C，就不可能有任何一种编码能使，就不可能有任何一种编码能使差错概率任意小。差错概率任意小。 上述两定理统称为有扰或噪声信道的信道编码定理上述两定理统称为有扰或噪声信道的信道编码定理信道编码定理信道编码定理第第6

14、 6章章 信道编码信道编码 2021-10-9156.2 纠错编译码的基本原理与分析方法纠错编译码的基本原理与分析方法6.2.1 纠错编码的基本原理纠错编码的基本原理6.2.2 译码方法译码方法-最优译码最优译码 和最大似然译码和最大似然译码第第6 6章章 信道编码信道编码 2021-10-9166.2.1 纠错编码的基本原理纠错编码的基本原理6.2.1 纠错编码的基本思想纠错编码的基本思想一、从编码定理出发讨论纠错码的基本原理：一、从编码定理出发讨论纠错码的基本原理：)(RNEereP从上面的公式可以看出：要减小从上面的公式可以看出：要减小 Pe：（1）增大）增大N;（2）增大）增大Er(

15、R )；1 增大信道容量增大信道容量C（1）扩展带宽。（）扩展带宽。（2）加大功率。（）加大功率。（3）减小噪声功率。）减小噪声功率。2 减小码率减小码率R(=KlbQ /N)3 增大码长增大码长N C,R,K/N不变不变第第6 6章章 信道编码信道编码 2021-10-917二、从冗余度和噪声均化讨论纠错码的基本原理：二、从冗余度和噪声均化讨论纠错码的基本原理：冗余度：冗余度：就是在信息流中插入冗余比特，插入的冗余比特与就是在信息流中插入冗余比特，插入的冗余比特与 信息比特存在着特定的相关性。这样如果在传输过信息比特存在着特定的相关性。这样如果在传输过 程中有个别信息比特受损，也可以从冗余比

16、特中恢程中有个别信息比特受损，也可以从冗余比特中恢 复或发现受损比特。从而保证了信息传输的可靠性。复或发现受损比特。从而保证了信息传输的可靠性。 传输传输冗余比特冗余比特 必然要动用必然要动用冗余的资源冗余的资源: : 时间时间, ,频带频带, ,功率功率, ,设备复杂度设备复杂度噪声均匀化噪声均匀化：就是让差错随机化，以便符合编码定理的条件从：就是让差错随机化，以便符合编码定理的条件从 而得到符合编码定理结果。其基本思想是设法将而得到符合编码定理结果。其基本思想是设法将 危害较大的，较为集中的噪声干扰分摊开来，使危害较大的，较为集中的噪声干扰分摊开来，使 不可恢复的信息损伤最小。不可恢复的信

17、息损伤最小。 （1）增加码长。）增加码长。 （2）卷积。（）卷积。（3）交织。）交织。第第6 6章章 信道编码信道编码 2021-10-918译码算法的已知条件是要求已知：译码算法的已知条件是要求已知：（1）实际接收到的码字序列）实际接收到的码字序列r,r=(r1,r2,.rN)。（2）发送端所采用的编码算法和该算法产生的码集）发送端所采用的编码算法和该算法产生的码集XN,满足满足。NiNiiiXcccc),.,(21（3）信道模型及信道参数。）信道模型及信道参数。消息组消息组m),.,(21kmmm(N,K)编码器编码器NiXC 码字),.,(21iNiiccc信道信道r接收码),.,(21

18、Nrrr最佳最佳/最大最大似然译码似然译码ic码字估值),.,(21iNiiccc消息消息还原还原),.,(21kmmmim消息6.2.2 译码方法译码方法-最优译码和最大似然译码最优译码和最大似然译码第第6 6章章 信道编码信道编码 2021-10-919XNUUYf1fXFY第第6 6章章 信道编码信道编码 2021-10-920两种典型的译码规则：两种典型的译码规则：最佳译码规则最佳译码规则、极大似然译码规则极大似然译码规则 1 1、最佳译码规则：最佳译码规则：平均差错率最小的译码规则平均差错率最小的译码规则 。XY12 ,rAa aa12 ,sBb bbX12 ,rAa aaN1()

19、1()|sejjjjPP bP F bb*(|)()|)(,:,jjjjiijjP abP aF baAbBFaAb *(,( ,)jjijP a bP a b *(|) (|)()jjijjjP bPPbP aba b *(,( ,)(,:,jjijjjjiP a bP aF baAbBFabA 第第6 6章章 信道编码信道编码 2021-10-921 实际应用中，经常只知道信道的统计特性实际应用中，经常只知道信道的统计特性( (转移概率转移概率) )，而，而不知道信源的统计特性不知道信源的统计特性( (输入概率输入概率) )，这时，这时求不出求不出联合概率联合概率和和后验概率后验概率，因此

20、，因此无法确定无法确定最佳译码规则。最佳译码规则。 既然只知道转移概率，就只能按转移概率的某种约束条件既然只知道转移概率，就只能按转移概率的某种约束条件制订译码规则。制订译码规则。 按最大转移概率条件来确定的译码规则，称为按最大转移概率条件来确定的译码规则，称为极大似然译极大似然译码规则码规则。 *(),:(|)(|),jjjjjjiiF baAbBFP baP baaA 第第6 6章章 信道编码信道编码 2021-10-922*(|)(|)(),:,jjjjjjiiP baP bF baAbaAaBF *(|)(|)jjjiP baP ba *(,( ,)jjijP a bP a b *()

21、( )jiP aP a*(|)()(|)jjjiijP aP aP baP ba 注：*(|)()|)(,:,jjjjiijjP abP aF baAbBFaAb 第第6 6章章 信道编码信道编码 2021-10-923 最佳译码最佳译码，也叫最大后验概率译码，也叫最大后验概率译码(MAP) 最大似然译码最大似然译码( MLD) *(|)()|)(,:,jjjjiijjP abP aF baAbBFaAb 消息组消息组mi 码字码字ci 接收码接收码r 估值估值 消息消息 max ( / )iiPcc r max( /)iiPcr c 信道信道icim消息消息还原还原编码器编码器译码译码*(|

22、)(|)(),:,jjjjjjiiP baP bF baAbaAaBF 第第6 6章章 信道编码信道编码 2021-10-924码字的似然函数码字的似然函数12121( /)( ,.,),(,.,), max( /)max(/)NiiiNNjijjpr rrcccpp rciiir crcr c一般情况下，称为码字的似然函数。对于无记忆信道，如果则有：为了方便计算，可以利用对数运算将乘法运算转化为加法运算。即：为了方便计算，可以利用对数运算将乘法运算转化为加法运算。即：)/(logmax)/(logmax1ijNjjicrpcrp第第6 6章章 信道编码信道编码 2021-10-925BSC信

23、道信道第第6 6章章 信道编码信道编码 2021-10-926,(/)1,(ijjjijijjp crp rcp cr在极大似然译码算法中有：时）时）汉明距离译码是一种硬判决译码。由于汉明距离译码是一种硬判决译码。由于BSC信道是对称信道是对称的，只要发送的码字独立、等概，汉明距离译码也就是的，只要发送的码字独立、等概，汉明距离译码也就是最佳译码。最佳译码。1( /)(/)(1)() (1)1NdN ddNjijjppp rcppppir c最大似然译码等效于最小汉明距离译码。最大似然译码等效于最小汉明距离译码。第第6 6章章 信道编码信道编码 2021-10-9276.3 线性分组码线性分组

24、码 6.3.1 线性分组码的生成矩阵和校验矩阵线性分组码的生成矩阵和校验矩阵 6.3.2 伴随式与标准阵列译码伴随式与标准阵列译码 6.3.3 码距码距,纠错能力纠错能力,MDC码等码等 6.3.4 完备码完备码,循环码循环码,BCH和和RS码码 6.3.5 分组码的扩展分组码的扩展,缩短和缩短和CRC第第6 6章章 信道编码信道编码 2021-10-9286.3 线性分组码线性分组码(n,k)分组码是把信息流分割成一串分组码是把信息流分割成一串前后独立前后独立的的k比特信息组，比特信息组，再将每组信息元映射成再将每组信息元映射成n个码元组成的码字。如下图：个码元组成的码字。如下图：m0 m1

25、 m2 mk-1 m0 m1 m2. mk-1 m0 m1 m2 mk-1 . C0C1C3.Cn-1 C0C1C3.Cn-1 C0C1C3.Cn-1K个信息元可以写成矢量个信息元可以写成矢量(mk-1,.m1,m0)或者矩阵的形式或者矩阵的形式mk-1,.m1,m0。同样码字可以表示为同样码字可以表示为(Cn-1,.C1,C0)或者或者Cn-1,.C1,C0. (码矢码矢,码字码字,码组码组)第第6 6章章 信道编码信道编码 2021-10-929线性分组码中，必须考虑的问题：线性分组码中，必须考虑的问题：（1）码集）码集C能否构成能否构成n维维n重矢量空间的一个重矢量空间的一个k维维n重子

26、空间重子空间。（2）如何寻找）如何寻找最佳的码空间最佳的码空间。（3）qk个信息元组以怎样的算法一一映射到码空间。个信息元组以怎样的算法一一映射到码空间。码率码率对于对于二元二元分组码分组码(n,k),其码率定义为：其码率定义为：RC=k/n对于对于q元元分组码分组码(n,k),其码率定义为：其码率定义为：RC=klbq/n 消息消息m (n , k) 码字码字c m=(mk-1,m1,m0) 分组编码器分组编码器 c=(cn-1,c1,c0) qk qn第第6 6章章 信道编码信道编码 2021-10-9306.3.1生成矩阵和校验矩阵生成矩阵和校验矩阵 线性分组码的码空间线性分组码的码空间

27、C 是由是由 k 个线性无关个线性无关的的基底基底 gk-1,，g1 ，g0 张成的张成的k维维n重重子空间子空间，所有码字都可写成，所有码字都可写成k个个基底的线性组合，即基底的线性组合，即 c = mk-1 gk-1+ m1 g1+m0 g0(1),(2),1,0,1(1)(1)(1)1(1)021(1)111010(0 .iii ni niikknkkknngiggg gkknggggggggggGgg如果 表示第 个基底，并写成行矩阵的形式个基底可以排列成 行 列的形式，如下所示：1)0100.gg第第6 6章章 信道编码信道编码 2021-10-931生成矩阵生成矩阵 当信息元确定后

28、，码字仅由当信息元确定后，码字仅由G矩阵决定，因此我们称这矩阵决定，因此我们称这kn 矩阵矩阵G为该为该(n,k)线性分组码的线性分组码的生成矩阵生成矩阵。 如果已知线性分组码的生成矩阵，则任何一个如果已知线性分组码的生成矩阵，则任何一个k位信息位信息组对应的码字都可以由组对应的码字都可以由mG运算得到。运算得到。 码空间中任何一个码字都可以写成基底的线性组合，即：121011221100,., .nnkkkkccc cmmmmCggggmG第第6 6章章 信道编码信道编码 2021-10-932生成矩阵生成矩阵G(kn)的特点的特点 想要保证想要保证 (n,k)线性分组码能够构成线性分组码能

29、够构成k维维n重子空间，重子空间，G 的的k个行矢个行矢量量gk-1, g1, g0必须是必须是线性无关线性无关的，只有这样才符合作为基底的的，只有这样才符合作为基底的条件。条件。 由于由于k个基底即个基底即G的的k个行矢量线性无关，矩阵个行矢量线性无关，矩阵G的秩一定等的秩一定等于于k。 由于由于基底不是唯一基底不是唯一的，所以的，所以G也就不是唯一的。也就不是唯一的。 不同的基底有可能生成同一码集，但因编码涉及码集和映射两不同的基底有可能生成同一码集，但因编码涉及码集和映射两个因素，码集一样而映射方法不同也不能说是同样的码。个因素，码集一样而映射方法不同也不能说是同样的码。 第第6 6章章

30、 信道编码信道编码 2021-10-933例如例如11111111001110(7,4)010011100111010,1,10111111110011100,1,101,1,0,1,0,0,101001110011101GmCmG已知线性分组码的生成矩阵为如果输入的四位信息组为，时，其对应的码字为：，第第6 6章章 信道编码信道编码 2021-10-934系统形式的生成矩阵系统形式的生成矩阵 (n,k)码的任何生成矩阵都可以通过码的任何生成矩阵都可以通过行运算行运算（不改变码集，（不改变码集，只改变映射规则）简化成只改变映射规则）简化成“系统形式系统形式” 。G = Ik P =Ik是是kk

31、单位矩阵，单位矩阵，P是是k(n-k)矩阵。矩阵。 (1)(1)(1)1(1)01(1)11100(1)01001000100001kn kkkn kn kppppppppp 第第6 6章章 信道编码信道编码 2021-10-935复习： 定义 下面三种变换称为矩阵的初等行变初等行变换换： 1 互换两行； 2 以数k 乘以某一行； 3 把某一行的 k 倍加到另一行上。 若将定义中的“行”换成“列”，则称之为初等列变换初等列变换，初等行变换和初等列变换统称为初等变换初等变换。第第6 6章章 信道编码信道编码 2021-10-936系统码系统码 前前k位由单位矩阵位由单位矩阵Ik决定，等于把信息组

32、决定，等于把信息组m原封不原封不动搬到码字的前动搬到码字的前k位；位； mG = mIk P = mIk mP = m mP 其余的其余的n-k位叫冗余位或位叫冗余位或一致校验位一致校验位，是前，是前k个信个信息位的线性组合。息位的线性组合。 这样生成的（这样生成的（n,k）码叫做）码叫做系统码系统码。 若生成矩阵若生成矩阵G不具备系统形式，则生成的码叫做不具备系统形式，则生成的码叫做非系统码非系统码。 系统化系统化不改变码集不改变码集，只是改变了，只是改变了映射规则映射规则。 第第6 6章章 信道编码信道编码 2021-10-937由上面的生成矩阵生成的码字的特点：由上面的生成矩阵生成的码字

33、的特点：(7,3)1001110010011100111010,1,110011100,1,1 01001110,1,1,1,0,1,00011101GmCmG已知线性分组码的生成矩阵为 如果输入的三位信息组为时，其对应的码字为：特点：特点：码字的前面码字的前面k位就是信息组中的位就是信息组中的k位，而后面的校验位，而后面的校验位为信息组的线性组合。位为信息组的线性组合。第第6 6章章 信道编码信道编码 2021-10-938空间构成空间构成 n维维n重空间有相互正重空间有相互正交的交的n个基底个基底 选择选择k个基底构成码空个基底构成码空间间C 选择另外的选择另外的(n-k)个基个基底构成空

34、间底构成空间D C和和D是对偶的是对偶的 n维维n重空间重空间V k维维k重重 k维维n重重 n-k维维 信息组信息组 码空间码空间 n重重D 空间空间m C H G第第6 6章章 信道编码信道编码 2021-10-939校验矩阵校验矩阵 将将D空间的空间的n-k个基底排列起来可构成一个个基底排列起来可构成一个(n-k)n矩矩阵，称为阵，称为校验矩阵校验矩阵H，也称，也称监督矩阵监督矩阵。用来校验接收。用来校验接收到的码字是否是正确的；到的码字是否是正确的； 即：若即：若c为码空间为码空间C中的任意码字，则中的任意码字，则若不满足此等式，则若不满足此等式，则c必定不是码空间必定不是码空间C中的

35、码字。中的码字。0TcH第第6 6章章 信道编码信道编码 2021-10-940012654321001260514230220121(7,3)1001110 01001110011101,1001110, 01001110011101,m m mc c c c c c cm m mcmcmcmcmmcmmm cmGmC已知线性分组码的生成矩阵为如果信息位为，则有，01012mcmm，第第6 6章章 信道编码信道编码 2021-10-94136464326546542165651054540000,0cccccccccccccccccccccccccc由前面的等式可以得到：，即，即，即，即如果

36、写成矩阵的形式便为：6543210101100001110100001100010001100010Tccccccc 第第6 6章章 信道编码信道编码 2021-10-9421,11,21,02,12,22,0,1,2,0.nnnnnk nnk nnkhhhhhhhhhH1,11,21,02,12,22,0110,1,2,0.TnnnnTnn k nn k nn khhhhhhccchhhCH01,11,21,012,12,22,01,1,2,00.nnnnnTTn k nn k nn kHhhhchhhchhhc HC0由矩阵可以建立码的线性方程组或者47,.( , )Hn kH上面的 行

37、列的矩阵就称为校验矩阵 记为一般情况下任何一个分组码的矩阵可以表示为：第第6 6章章 信道编码信道编码 2021-10-943校验矩阵校验矩阵 G是是(n,k)码的生成矩阵，码的生成矩阵，H是它的校验矩阵；是它的校验矩阵； H是是(n,n-k)对偶码的生成矩阵，它的每一行是对偶码的生成矩阵，它的每一行是对偶码的一个码字。对偶码的一个码字。 G则是它的校验矩阵。则是它的校验矩阵。 GHT=0 ，H PT In-k ，二进制时，负号可，二进制时，负号可省略。省略。第第6 6章章 信道编码信道编码 2021-10-944校验矩阵与生成矩阵的关系校验矩阵与生成矩阵的关系如果系统码的生成矩阵为如果系统码

38、的生成矩阵为G=IK|P,则其对应的校验矩则其对应的校验矩阵为阵为H=-PT|In-k(7,3)100111001001110011101G已知线性分组码的生成矩阵为1011000111010011000100110001H则可以得到其校验矩阵为：GHT=0 或者或者HGT=0第第6 6章章 信道编码信道编码 2021-10-945 例例6-2某线性分组码，其生成矩阵是某线性分组码，其生成矩阵是 G= 求：求：(1)计算码集，列出信息组与码字的映射关系。计算码集，列出信息组与码字的映射关系。(2)将该码系统化处理后，计算系统码码集并列出映射将该码系统化处理后，计算系统码码集并列出映射关系。关系

39、。(3)计算系统码的校验矩阵计算系统码的校验矩阵H。若收码。若收码r = 100110, 检检验它是否码字？验它是否码字？ (4)根据系统码生成矩阵画出编码器电原理图。根据系统码生成矩阵画出编码器电原理图。 1 1 1 0 1 0 1 1 0 0 0 1 0 1 1 1 0 1 第第6 6章章 信道编码信道编码 2021-10-946例例6-2 码集与映射关系码集与映射关系信息 码字 系统码字000 000000 0000000010111010010110101100010101100111011000111011001110101001111011001111011001100010111

40、10001111010110111010做初等行变换第第6 6章章 信道编码信道编码 2021-10-947例例6-2 二元二元(6,3)线性分组码编码器线性分组码编码器 m0m1m2 输入 输出 c0c1c2第第6 6章章 信道编码信道编码 2021-10-948 下面是某线性二元码的全部码字：下面是某线性二元码的全部码字： 。 求求n, k的值；的值； 构造这码的生成矩阵构造这码的生成矩阵G；(找找3个线性无关的码字构个线性无关的码字构成成G,并化为系统形式并化为系统形式) 构成这码的一致校验矩阵构成这码的一致校验矩阵H。 1000000C 2000111C 3011001C 401111

41、0C 5101011C 6101100C 7110010C 8110101C 第第6 6章章 信道编码信道编码 2021-10-9496.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 第第6 6章章 信道编码信道编码 2021-10-950伴随式伴随式S的定义的定义因为因为CHT = 0 所以所以

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

43、信道对码字造成怎样的干扰。 差错图案差错图案E是是n重矢量重矢量，共有，共有2n个可能的组合，而伴随个可能的组合，而伴随式式S是是(n-k)重矢量重矢量，只有，只有2n-k个可能的组合，因此不同个可能的组合，因此不同的差错图案可能有相同的伴随式。的差错图案可能有相同的伴随式。 接收端收到接收端收到R后，因为已知后，因为已知HT，可求出，可求出 SRHT；如；如果能知道对应的果能知道对应的E，则通过，则通过C = RE而求得而求得C。 RHT = S ? C = RE R S E C 只要只要E正确，译出的码也就是正确的。正确，译出的码也就是正确的。 伴随式伴随式S的意义的意义第第6 6章章 信

44、道编码信道编码 2021-10-952BHT0ECB否计算E输出BE编码mGm是输出 BC译码过程框图译码过程框图 (R=B)第第6 6章章 信道编码信道编码 2021-10-953例例 一个一个(5,2)系统线性码的生成矩阵是系统线性码的生成矩阵是G = 设收码设收码R = (10101)，构造，构造标准阵列译码表标准阵列译码表，译出发码，译出发码的估值的估值解：解：(1)构造标准阵列译码表。分别以信息组构造标准阵列译码表。分别以信息组m= (00)、(01) 、(10)、(11)及已知的及已知的G求得求得4个许用码字为个许用码字为C1 =(00000)、C2 = (10111) 、C3 =

45、 (01101)、C4 = (11010)。求出校验矩阵：求出校验矩阵： H = PT I3 = 1011011101ic 242322212014131211100403020100111001001011001hhhhhhhhhhhhhhh第第6 6章章 信道编码信道编码 2021-10-95424243232221 2102043214 143 132 121 110 104104043032021 01000430se he he he he heeese he he he he heese he he he he heee列出方程组：列出方程组：由由RHT确定确定S后，对应的后，对应

46、的E可以有可以有2k(22=4)个解，究竟取哪一个解，究竟取哪一个作为差错图样个作为差错图样E的解的解? 最简单明了的处理方法是概率译码，即最简单明了的处理方法是概率译码，即对所有对所有2k个解的重量个解的重量(差错图样差错图样E中中1的个数的个数)进行比较，选择重量进行比较，选择重量最小的作为最小的作为E的估值。由于的估值。由于E=R+C，E重量最小，就是重量最小，就是R和和C的汉的汉明距离最小。明距离最小。 第第6 6章章 信道编码信道编码 2021-10-955依据：依据：若若BSC信道的差错概率是信道的差错概率是p，则长度，则长度n的码中错误概率的码中错误概率 0个错个错 1个错个错

47、2个错个错 n个错个错 概率概率 (1-p)n p(1-p)n-1 p2(1-p)n-2 pn 由于由于p p(1-p)n-1 p2(1-p)n-2 pn 出错越少的情况，发生概率越大，出错越少的情况，发生概率越大，E的重量越轻，所以该的重量越轻，所以该译码方法实际上体现了最小距离译码准则，即最大似然译码。译码方法实际上体现了最小距离译码准则，即最大似然译码。显然，在进行概率译码时，每接收一个码字就要解一次显然，在进行概率译码时，每接收一个码字就要解一次线性方程，非常复杂麻烦。但如果线性方程，非常复杂麻烦。但如果nk不太大，我们可以预不太大，我们可以预先把不同校正子先把不同校正子S情况下的所有

48、方程组都预先解出来，将各种情况下的所有方程组都预先解出来，将各种情况下的最大概率译码输出列成一个标准阵列译码表。这样，情况下的最大概率译码输出列成一个标准阵列译码表。这样，在实际译码时就不必解方程，只要查译码表就可以了。在实际译码时就不必解方程，只要查译码表就可以了。 第第6 6章章 信道编码信道编码 2021-10-956伴随式有伴随式有2n-k238种种组合，差错图案中代表组合，差错图案中代表无差错的有一无差错的有一种种，代表，代表一个差错一个差错的图案有的图案有 种，已种，已有有6种种。代表代表两个差错两个差错的图案有的图案有 种。只需挑选其中的两个，挑种。只需挑选其中的两个，挑选方法可

49、选方法可有若干种，不是唯一有若干种，不是唯一的。先将的。先将Ej=(00000)、(10000)、(01000)、(00100)、(00010)、(00001)代入上面的线性方程组，代入上面的线性方程组，解得对应的解得对应的Sj分别是分别是(000)、(111)、(101)、(100)、(010)、(001)。剩下的伴随式中，。剩下的伴随式中，(011)所对应的差错图案是所对应的差错图案是2k个即个即(00011)、(10100)、(01110)、(11001),其中其中(00011)和和(10100)并并列重量最轻，列重量最轻，任选其中一个如任选其中一个如(00011)。同样可得伴随式。同样

50、可得伴随式(110)所对应的最轻差错图案之一是所对应的最轻差错图案之一是(00110)。 551 5102 例例 6-3 译码表的构成译码表的构成第第6 6章章 信道编码信道编码 2021-10-957S0=000E0+C0=00000C1=10111C2=01101C3=11010S1=111E1=10000001111110101010S2=101E2=01000111110010110010S3=100E3=00100100110100111110S4=010E4=00010101010111111000S5=001E5=00001101100110011011S6=011E6=0001

51、1101000111011001S7=110E7=00110100010101111100例例 6-3 标准阵列译码表标准阵列译码表第第6 6章章 信道编码信道编码 2021-10-958例例 6-3 将接收码将接收码R10101译码译码可选以下三种方法之一译码：可选以下三种方法之一译码： 直接搜索码表直接搜索码表，查得，查得(10101)所在列的子集头是所在列的子集头是(10111)，因此译码输出取为，因此译码输出取为(10111)。 先求先求伴随式伴随式RHT = (10101) HT = (010) = S4，确定，确定S4所所在行，再沿着行对码表作一维搜索找到在行，再沿着行对码表作一维

52、搜索找到(10101), 最后最后顺着所在列向上找出码字顺着所在列向上找出码字(10111)。 先求出伴随式先求出伴随式RHT = (010) = S4并确定并确定S4所对应的所对应的陪集陪集首首（差错图案差错图案）E4=(00010)，再将，再将陪集首与收码陪集首与收码相加相加得到码字得到码字C= R+ E4= (10101)+ (00010)= (10111)。 第第6 6章章 信道编码信道编码 2021-10-959差错图案差错图案E的求解的求解(1) 可以通过解线性方程求解可以通过解线性方程求解E：S = (sn-k-1,s1, s0) = EHT = (en-1, e1,e0)得到线

53、性方程组：得到线性方程组：sn-k-1=en-1h(n-k-1)(n-1)+e1h(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 h00(1)(1)(1)1(1)01(1)11100(1)0100Tn knn kn knnhhhhhhhhh 第第6 6章章 信道编码信道编码 2021-10-960 上述方程组中有上述方程组中有n个未知数个未知数en1, e1,e0 ，却只有，却只有n-k个个方程，可知方程组有多解。方程，可知方程组有多解。 在有理数或实数域中，

54、少一个方程就可能导致无限多在有理数或实数域中，少一个方程就可能导致无限多个解，而在二元域中，少一个方程导致两个解，少两个解，而在二元域中，少一个方程导致两个解，少两个方程四个解，以此类推，少个方程四个解，以此类推，少n-( n-k) = k个方程导致个方程导致这组未知数有这组未知数有2k组解。组解。 概率译码：概率译码：把所有把所有2k个解的重量个解的重量(差错图案差错图案E中中1的个的个数数)作比较，选择其中最轻者作为作比较，选择其中最轻者作为E的估值。该方法概的估值。该方法概念上很简单但计算效率不高。念上很简单但计算效率不高。差错图案差错图案E的求解的求解(2) 第第6 6章章 信道编码信

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

56、差错没有任何差错时的收码时的收码R放在第一行，放在第一行，收码等于发码收码等于发码R=C(C Ci,i =0,1,2k-1), 差错图案为全零差错图案为全零E0=(0,00)，伴随，伴随式为全零式为全零S0=(0,00)。由于有。由于有2k个码字，码表有个码字，码表有2k列列。第第6 6章章 信道编码信道编码 2021-10-962 在在第第2到第到第n+1的的n行中差错图案的所有行中差错图案的所有重量为重量为1 (共共n个个)。 如果如果(1+ n)t)01dte 第第6 6章章 信道编码信道编码 2021-10-972 （n,k）线性码最小距离）线性码最小距离dmin的上边界是的上边界是n

57、-k +1。如果。如果我们设计的（我们设计的（n,k）线性码的）线性码的dmin达到了达到了n-k +1，就是，就是达到了设计性能的极点。因此，达到了设计性能的极点。因此，dmin n-k +1的码称的码称为为极大最小距离码极大最小距离码 (MDC Maximized minimum Distance Code)。 (1) 二进制码中，除了将一位信息重复二进制码中，除了将一位信息重复n 次的次的 （n,1）码外，不存在其它二进制码外，不存在其它二进制MDC码；码； (2) 非二进制码中，非二进制码中，MDC码是存在的，如码是存在的，如RS码码 （reed-solomon)。MDC码码（Maxi

58、mized minimum Distance Code）第第6 6章章 信道编码信道编码 2021-10-973 纠错能力纠错能力t只是说明距离只是说明距离t的差错一定能纠，的差错一定能纠，并非说并非说距距离大于离大于t的差错一定不能纠。（除非完备码）的差错一定不能纠。（除非完备码） 总体的、平均的纠错能力不但与总体的、平均的纠错能力不但与最小距离最小距离有关，而且有关，而且与与其余码距其余码距或者说与码字的或者说与码字的重量分布特性重量分布特性有关。把码有关。把码距（码重）的分布特性称为距（码重）的分布特性称为距离（重量）谱距离（重量）谱，其中最，其中最小重量就是小重量就是dmin。当所有码距相差不大时（重量谱为。当所有码距相差不大时（重量谱为窄谱），性能较好。重量谱多项式表示：窄谱），性