信息论第九章精.ppt

《信息论第九章精.ppt》由会员分享，可在线阅读，更多相关《信息论第九章精.ppt（63页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、信息论第九章第1页，本讲稿共63页n前向纠错前向纠错(FEC)：发送端的信道编码器将信息码组发送端的信道编码器将信息码组编成具有一定纠错能力的码。接收端信道译码器对编成具有一定纠错能力的码。接收端信道译码器对接收码字进行译码，若传输中产生的差错数目在码接收码字进行译码，若传输中产生的差错数目在码的纠错能力之内时，译码器对差错进行定位并加以的纠错能力之内时，译码器对差错进行定位并加以纠正。纠正。n自动请求重发自动请求重发(ARQ)：用于检测的纠错码在译码器用于检测的纠错码在译码器输出端只给出当前码字传输是否可能出错的指示，输出端只给出当前码字传输是否可能出错的指示，当有错时按某种协议通过一个反向

2、信道请求发送端当有错时按某种协议通过一个反向信道请求发送端重传已发送的码字全部或部分。重传已发送的码字全部或部分。9.1 差错控制的基本方式差错控制的基本方式第2页，本讲稿共63页n混合纠错混合纠错(HEC)：是是FEC与与ARQ方式的结合。方式的结合。发端发送同时具有自动纠错和检测能力的码组，发端发送同时具有自动纠错和检测能力的码组，收端收到码组后，检查差错情况，如果差错在收端收到码组后，检查差错情况，如果差错在码的纠错能力以内，则自动进行纠正。如果信码的纠错能力以内，则自动进行纠正。如果信道干扰很严重，错误很多，超过了码的纠错能道干扰很严重，错误很多，超过了码的纠错能力，但能检测出来，则经

3、反馈信道请求发端重力，但能检测出来，则经反馈信道请求发端重发这组数据。发这组数据。9.1 差错控制的基本方式差错控制的基本方式第3页，本讲稿共63页n分组码分组码：编码的规则仅局限于本码组之内，本码组：编码的规则仅局限于本码组之内，本码组的监督元仅和本码组的信息元相关。的监督元仅和本码组的信息元相关。信息码组由信息码组由 k 个二进制码元组成，共有个二进制码元组成，共有 2k 个不同个不同的信息码组；的信息码组；附加附加nk个码元，每个监督元取值个码元，每个监督元取值与该信息码组的与该信息码组的k个码元有关；个码元有关；编码器输出长度编码器输出长度 n；这这2k 个码字的集合称为个码字的集合称

4、为(n,k)分组码；分组码；n卷积码卷积码：本码组的监督元不仅和本码组的信息元相：本码组的监督元不仅和本码组的信息元相关，而且还与本码组相邻的前关，而且还与本码组相邻的前 n1 个码组的信息个码组的信息元相关元相关。9.2 纠错码分类纠错码分类第4页，本讲稿共63页n是否可用线性方程组来表示是否可用线性方程组来表示n线性码线性码：编码规则可以用线性方程表示；：编码规则可以用线性方程表示；n非线性码非线性码：编码规则不能用线性方程表示；：编码规则不能用线性方程表示；n按码字的结构分按码字的结构分n系统码系统码：前前 k 个码元与信息码组一致；个码元与信息码组一致；n非系统码非系统码：没有系统码的

5、特性。：没有系统码的特性。n按纠正差错的类型可分为按纠正差错的类型可分为纠正随机错误的码纠正随机错误的码和和纠正突发错纠正突发错误的码误的码；n按码字中每个码元的取值可分为按码字中每个码元的取值可分为二进制码二进制码和和多进制码多进制码。9.2 纠错码分类纠错码分类第5页，本讲稿共63页n汉明距离汉明距离/距离：在距离：在(n,k)线性码中，两个码线性码中，两个码字字 U、V 之间对应码元位上符号取值不同的之间对应码元位上符号取值不同的个数，称为码字个数，称为码字 U、V 之间的汉明距离。之间的汉明距离。n线性分组码的一个码字对应于线性分组码的一个码字对应于 n 维线性空间维线性空间中的一点，

6、码字间的距离即为空间中两中的一点，码字间的距离即为空间中两对应点对应点的距离。的距离。码距与纠检错能力码距与纠检错能力第6页，本讲稿共63页n汉明重量汉明重量/码字重量码字重量/W：码字中非：码字中非0码元符号码元符号的个数，称为该码字的汉明重量。的个数，称为该码字的汉明重量。n在二元线性码中，码字重量就是码字中含在二元线性码中，码字重量就是码字中含“1”的个数。的个数。n最小距离与最小重量的关系最小距离与最小重量的关系：线性分组码的最：线性分组码的最小距离等于它的非零码字的最小重量。小距离等于它的非零码字的最小重量。第7页，本讲稿共63页n一般地说，线性码的最小距离越大，意味着任意一般地说，

7、线性码的最小距离越大，意味着任意码字间的差别越大，则码的检、纠错能力越强。码字间的差别越大，则码的检、纠错能力越强。最小距离与检、纠错能力最小距离与检、纠错能力最小距离与纠错能力最小距离与纠错能力：(n,k)线性码能纠线性码能纠 t 个个错误的充要条件是码的最小距离为错误的充要条件是码的最小距离为第8页，本讲稿共63页 几何意义：第9页，本讲稿共63页n最小距离与检错能力最小距离与检错能力：(n,k)线性码能够发现线性码能够发现 l 个错误的充要条件是码的最小距离为个错误的充要条件是码的最小距离为ndmin=l+1 或或 l=dmin1第10页，本讲稿共63页线性空间的概念线性空间的概念n定理

8、：（定理：（n,k）线性分组码是）线性分组码是n维维n重线性重线性空间的一个空间的一个k维线性子空间。维线性子空间。n线性空间相关概念：线性空间相关概念：n（1）n维线性空间：由维线性空间：由n个线性无关的个线性无关的矢量组成基底，它们的全部线性组合所矢量组成基底，它们的全部线性组合所构成的空间。若矢量长度也为构成的空间。若矢量长度也为n，则称，则称n维维n重线性空间重线性空间S。第11页，本讲稿共63页（2）线性子空间：从）线性子空间：从n个基底中选出一组个基底中选出一组k（kn）个基底，它们的全部线性组合也构成）个基底，它们的全部线性组合也构成一个集合，这个集合是一个集合，这个集合是S的一

9、个的一个k维子集，称为维子集，称为k维维n重子空间，记作重子空间，记作 。（3）n维空间的维空间的n个基底不是唯一的。个基底不是唯一的。第12页，本讲稿共63页（4）矢量正交：两矢量内积为零。）矢量正交：两矢量内积为零。矢量空间正交：一空间中的任一矢量都和另一矢量空间正交：一空间中的任一矢量都和另一空间的任一矢量正交。空间的任一矢量正交。（5）对偶空间：以互相正交的基底组张成的）对偶空间：以互相正交的基底组张成的两个线性空间一定正交，这两个空间称为对偶两个线性空间一定正交，这两个空间称为对偶空间，其中一个空间是另一个空间的零空间。空间，其中一个空间是另一个空间的零空间。第13页，本讲稿共63页

10、（6）码空间与校验空间：把）码空间与校验空间：把n维维n重线性空间重线性空间中互相正交的中互相正交的n个基底分成两组：一组个基底分成两组：一组k个基个基底，另一组（底，另一组（n-k）个基底，则它们分别张成）个基底，则它们分别张成k维维n重和（重和（n-k）维）维n重两个正交的对偶空间，重两个正交的对偶空间，将将k维维n重空间用作码空间重空间用作码空间C，将（，将（n-k）维）维n重重空间用作校验空间空间用作校验空间H。第14页，本讲稿共63页 将将H空间的（空间的（n-k）个基底排列起来可构）个基底排列起来可构成一个（成一个（n-k）n矩阵，称为线性码矩阵，称为线性码C的一致的一致校验（或监

11、督）矩阵，简称为校验（或监督）校验（或监督）矩阵，简称为校验（或监督）矩阵矩阵H。H是（是（n，n-k）对偶码的生成矩阵，）对偶码的生成矩阵，它的每一行是一个基底，也是一个码字。它的每一行是一个基底，也是一个码字。第15页，本讲稿共63页第2节 线性分组码第16页，本讲稿共63页n在由在由(n,k)线性码构成的码空间线性码构成的码空间C中，一定存在中，一定存在 k 个线性独立的码字：个线性独立的码字：g1,g2,gk,。码。码 集集 中其中其它任何码字它任何码字C都可以表为这都可以表为这 k 个码字的一种线性个码字的一种线性组合，即组合，即线性分组码的生成矩阵线性分组码的生成矩阵第17页，本讲

12、稿共63页第18页，本讲稿共63页nG中每一行中每一行 gi=(gi1,gi2,gin)都是一个码字；都是一个码字；n对每一个信息组对每一个信息组m，由矩阵，由矩阵G都可以求得都可以求得(n,k)线线性码对应的码字。性码对应的码字。n(n,k)线性码的每一个码字都是生成矩阵线性码的每一个码字都是生成矩阵 G 的行的行矢量的线性组合，所以它的矢量的线性组合，所以它的 2k 个码字构成了由个码字构成了由 G 的行张成的的行张成的 n 维空间的一个维空间的一个 k 维子空间维子空间。第19页，本讲稿共63页n通过行初等变换，通过行初等变换，将将 G 化为前化为前 k 列是单位子阵列是单位子阵的的标准

13、形式标准形式 线性系统分组码线性系统分组码第20页，本讲稿共63页n举例 已知(7,4)线性系统码的监督矩阵为第2节 线性分组码第21页，本讲稿共63页n定理定理 (n,k)线性分组码最小距离等于线性分组码最小距离等于dmin的的充要条件是：校验矩阵充要条件是：校验矩阵H的列矢量中至少要的列矢量中至少要有有dmin个才能线性相关个才能线性相关,而任意（而任意（dmin-1)列线列线性无关。性无关。n定定理理 (n,k)线线性性分分组组码码的的最最小小距距离离必必定定小小于于等于等于(n-k+1)dmin (n-k+1)第22页，本讲稿共63页例：例：H (7，4)线性码线性码 各列都不相同，任

14、意各列都不相同，任意2列之和不等于列之和不等于0，2列线性无关；某列线性无关；某3列线性相关。所以该码的最列线性相关。所以该码的最小距离为小距离为3，小于，小于n-k+14。第23页，本讲稿共63页n（n,k）线线性性码码最最小小距距离离dmin的的上上边边界界是是n-k+1。如如果果我我们们设设计计的的（n,k）线线性性码码的的dmin达达到到了了n-k+1，就就是是达达到到了了设设计计性性能能的的极极点点。因因此此，dmin n-k+1的的码码称称 为为 极极 大大 最最 小小 距距 离离 码码 (MDC MaximizedminimumDistanceCode)。生成矩阵和校验矩阵生成矩

15、阵和校验矩阵第24页，本讲稿共63页伴随式与译码伴随式与译码 m C=(c1,cn)R=(r1,rn)(n,k)信道信道定义定义差错图案差错图案E E(e1,en)RC (r1c1,rncn)二进制码中模二进制码中模2加与模加与模2减是等同的，因此有减是等同的，因此有E=R C 及及R=C E 第25页，本讲稿共63页伴随式S的定义因为因为CHT=0 所以所以RHT(CE)HTCHTEHT=EHT如果收码无误：必有如果收码无误：必有RC即即E0，则则EHT=0 RHT=0。如果收码有误：即如果收码有误：即E 0，则则RHT=EHT 0。在在HT固定的前提下，固定的前提下，RHT仅仅与差错图仅仅

16、与差错图案案E有关，而与发送码有关，而与发送码C无关。定义无关。定义伴随式伴随式S:S=(s1,s2,sn-k)=RHT=EHT 第26页，本讲稿共63页n从物理意义上看，伴随式从物理意义上看，伴随式S并不反映发送的码字是什么，并不反映发送的码字是什么，而只是反映信道对码字造成怎样的干扰。而只是反映信道对码字造成怎样的干扰。n差错图案差错图案E是是n重矢量，共有重矢量，共有2n个可能的组合，而伴随式个可能的组合，而伴随式S是是(n-k)重矢量，只有重矢量，只有2n-k个可能的组合，因此不同的个可能的组合，因此不同的差错图案可能有相同的伴随式。差错图案可能有相同的伴随式。n接收端收到接收端收到R

17、后，因为已知后，因为已知HT，可求出，可求出 SRHT；如果；如果能知道对应的能知道对应的E，则通过，则通过C=RE而求得而求得C。RHT=S?C=RE R S E C 只要只要E正确，译出的码也就是正确的。正确，译出的码也就是正确的。伴随式S的意义第27页，本讲稿共63页差错图案差错图案E的求解的求解(1)可以通过解线性方程求解可以通过解线性方程求解E：S=(s1,s2,sn-k)=EHT =(e1,e2,en)得到线性方程组：得到线性方程组：sn-k=e1h(n-k)(1)+enh(n-k)ns1 =e1h11+en h1n第28页，本讲稿共63页n上述方程组中有上述方程组中有n个未知数个

18、未知数e1,e2,en，却只有，却只有n-k个方程，可知方程组有多解。个方程，可知方程组有多解。n在有理数或实数域中，少一个方程就可能导致无在有理数或实数域中，少一个方程就可能导致无限多个解，而在二元域中，少一个方程导致两个限多个解，而在二元域中，少一个方程导致两个解，少两个方程四个解，以此类推，少解，少两个方程四个解，以此类推，少n-(n-k)=k个方程导致每个未知数有个方程导致每个未知数有2k个解。个解。n因此，由上述方程组解出的因此，由上述方程组解出的E可以有可以有2k个解。到底个解。到底取哪一个作为附加在收码取哪一个作为附加在收码R上的差错图案上的差错图案E的估值呢的估值呢？n概率译码

19、：概率译码：把所有把所有2k个解的重量个解的重量(差错图案差错图案E中中1的个的个数数)作比较，选择其中最轻者作为作比较，选择其中最轻者作为E的估值。该方法概的估值。该方法概念上很简单但计算效率不高。念上很简单但计算效率不高。第29页，本讲稿共63页依据：依据：若若BSC信道的差错概率是信道的差错概率是p，则长度，则长度n的码中错误概率的码中错误概率：0个错个错 1个错个错 2个错个错 n个错个错 (1-p)n p(1-p)n-1 p2(1-p)n-2 pn 由于由于p 出错越少的情况，发生概率越大，出错越少的情况，发生概率越大，E的重量越轻，所的重量越轻，所以该译码方法实际上体现了最小距离译

20、码准则，即最以该译码方法实际上体现了最小距离译码准则，即最大似然译码。大似然译码。第30页，本讲稿共63页标准阵列译码表标准阵列译码表 上述的概率译码，如每接收一个码上述的概率译码，如每接收一个码R就就要解一次线性方程，那就太麻烦了。好在要解一次线性方程，那就太麻烦了。好在伴随式伴随式S的数目是有限的的数目是有限的2n-k个，如果个，如果n-k不不太大，我们可以预先把不同太大，我们可以预先把不同S下的方程组解下的方程组解出来，把各种情况下的最大概率译码输出出来，把各种情况下的最大概率译码输出列成一个码表。这样，在实时译码时就不列成一个码表。这样，在实时译码时就不必再去解方程，而只要象查字典那样

21、查一必再去解方程，而只要象查字典那样查一下码表就可以了。这样构造的表格叫做下码表就可以了。这样构造的表格叫做标标准阵列译码表。准阵列译码表。第31页，本讲稿共63页n表中所列码字是接收到的码字表中所列码字是接收到的码字R。n将没有任何差错时的收码将没有任何差错时的收码R放在第一行，收码等于发码放在第一行，收码等于发码R=C(C Ci,i=0,1,2k-1),差错图案为全零差错图案为全零E0=(0,00)，伴随式为全零，伴随式为全零S0=(0,00)。由于有。由于有2k个码字，码表有个码字，码表有2k列。列。n在第在第2到第到第n+1的的n行中差错图案的所有重量为行中差错图案的所有重量为1(共共

22、n个个)。n如果如果(1+n)2n-k，再在下面行写出全部带有，再在下面行写出全部带有2个差错的图案个差错的图案 (共共 个个)。n如果总行数如果总行数(1+n+)仍然小于仍然小于2n-k，再列出带有，再列出带有3个差错的图案，以个差错的图案，以此类推，直到放满此类推，直到放满2n-k行，每行一个行，每行一个Ej,对应一个不同的伴随式对应一个不同的伴随式Sj。这样，。这样，表的行数表的行数2n-k正好等于伴随式的数目。正好等于伴随式的数目。标准阵列译码表的构成标准阵列译码表的构成 第32页，本讲稿共63页S0 E0S1 E1 Sj Ej E0+C0=0+0=0E0+C1=C1E0+Ci=CiE

23、1+C0=E1E1+CiEj+C0=EjEj+C1Ej+Ci标准阵列译码表标准阵列译码表 E1+C1第33页，本讲稿共63页陪集和子集n译译码码表表中中有有2n-k行行，每每行行是是一一个个陪陪集集，每每陪陪集集的的第第一一个个元元素素(位位于于第第一一列列)叫叫陪陪集集首首。同同一一陪陪集集（同同一一行行）中中的的所所有有元元素素对对应应共共同同的的一一个个伴伴随随式式。第第一一行行陪陪集集的的陪陪集集首首是是全全零零伴伴随随式式S0所所对对应应的的全全零零差差错错图图案案E0(无无差差错错)，而而第第j行行陪陪集集的的陪陪集集首首是是伴伴随随式式Sj所所对对应应的的重重量量最最小小的的差差

24、错错图图案案Ej(C0=0,Rj=Ej)。n定定理理：在在标标准准阵阵列列中中，一一个个陪陪集集的的所所有有 2k 个个 n 重重有有相相同同的的伴伴随随式式，不不同同的的陪陪集集伴伴随随式式互互不不相同。相同。第34页，本讲稿共63页译译码码表表中中有有2k列列，每每列列是是一一个个子子集集，每每子子集集的的第第一一个个元元素素(位位于于第第一一行行)叫叫子子集集头头。同同一一子子集集（同同一一列列）中中的的所所有有元元素素对对应应同同一一个个码码字字，第第一一列列子子集集的的子子集集头头是是全全零零码码字字C0，而而第第i列列子子集集的的子子集集头头是是码码字字Ci(E0=0,Ri=Ci)

25、。第35页，本讲稿共63页例例 一个一个(5,2)系统线性码的生成矩阵是系统线性码的生成矩阵是G=设收码设收码R=(10101)，构造标准阵列译码表，译出发码的估值，构造标准阵列译码表，译出发码的估值解解：(1)构构造造标标准准阵阵列列译译码码表表。分分别别以以信信息息组组m=(00)、(01)、(10)、(11)及已知的及已知的G求得求得4个许用码字为个许用码字为C1=(00000)、C2=(10111)、C3=(01101)、C4=(11010)。求出校验矩阵：求出校验矩阵：H=PT I3 =列出方程组：列出方程组：S=(s1,s2,s3)=(e1,e2,e5)第36页，本讲稿共63页n伴

26、随式有伴随式有2n-k238种组合，差错图案中代表无差错的有一种，代种组合，差错图案中代表无差错的有一种，代表一个差错的图案有表一个差错的图案有 种，已有种，已有6种。种。n代表两个差错的图案有代表两个差错的图案有 种。只需挑选其中的两个，挑选种。只需挑选其中的两个，挑选方法可有若干种，不是唯一的。先将方法可有若干种，不是唯一的。先将Ej=(00000)、(10000)、(01000)、(00100)、(00010)、(00001)代入上面的线性方程组，解代入上面的线性方程组，解得对应的得对应的Sj分别是分别是(000)、(111)、(101)、(100)、(010)、(001)。剩。剩下的伴

27、随式中，下的伴随式中，(011)所对应的差错图案是所对应的差错图案是2k个即个即(00011)、(10100)、(01110)、(11001),其中其中(00011)和和(10100)并列重量最轻，任选其并列重量最轻，任选其中一个如中一个如(00011)。同样可得伴随式。同样可得伴随式(110)所对应的最轻差错图案所对应的最轻差错图案之一是之一是(00110)。译码表的构成译码表的构成第37页，本讲稿共63页S0=000E0+C0=00000C1=10111C2=01101C3=11010S1=111E1=10000001111110101010S2=101E2=010001111100101

28、10010S3=100E3=00100100110100111110S4=010E4=00010101010111111000S5=001E5=00001101100110011011S6=011E6=00011101000111011001S7=110E7=00110100010101111100标准阵列译码表标准阵列译码表第38页，本讲稿共63页将接收码将接收码R10101译码译码 可选以下三种方法之一译码：可选以下三种方法之一译码：n直接搜索码表，查得直接搜索码表，查得(10101)所在列的子集头是所在列的子集头是(10111)，因此译码输，因此译码输出取为出取为(10111)。n先求伴

29、随式先求伴随式RHT=(10101)HT=(010)=S4，确定，确定S4所在行，再所在行，再沿着行对码表作一维搜索找到沿着行对码表作一维搜索找到(10101),最后顺着所在列向上找出码字最后顺着所在列向上找出码字(10111)。n先求出伴随式先求出伴随式RHT=(010)=S4并确定并确定S4所对应的陪集首（差错所对应的陪集首（差错图案）图案）E4=(00010)，再将陪集首与收码相加得到码字，再将陪集首与收码相加得到码字C=R+E4=(10101)+(00010)=(10111)。上述三种方法由上而下，查表的时间下降而所需计算量增大，上述三种方法由上而下，查表的时间下降而所需计算量增大，实

30、际使用时可针对不同情况选用。实际使用时可针对不同情况选用。第39页，本讲稿共63页 对上例作进一步分析，还可以看到，该对上例作进一步分析，还可以看到，该(5,2)码的码的dmin=3,纠错纠错能力是能力是t=INT(3-1)/2=1。因此，译码阵列中只有前。因此，译码阵列中只有前6行具有行具有唯一性、可靠性，真正体现了最大似然译码准则，而第唯一性、可靠性，真正体现了最大似然译码准则，而第7、8行的行的差错图案差错图案(00011)和和(00110)中包含两个中包含两个“1”，已超出了，已超出了t=1的纠的纠错能力，译码已不可靠。比如，当收码错能力，译码已不可靠。比如，当收码R(10100)时，

31、根据码时，根据码表译出的码字是表译出的码字是(10111)，与收码，与收码R的汉明距离是的汉明距离是2，然而收码，然而收码R与与全零码字全零码字(00000)的汉明距离也是的汉明距离也是2，为什么不能译成，为什么不能译成(00000)呢？事呢？事实上，码表的第实上，码表的第7、8行本身就不是唯一的。注意在码表计算过行本身就不是唯一的。注意在码表计算过程中，伴随式程中，伴随式(011)所对应的所对应的4个差错图案中有两个并列重量最轻，个差错图案中有两个并列重量最轻，如果当时选的不是如果当时选的不是(00011)而是而是(10100)，那么码表第，那么码表第7行就不是现行就不是现在这样了。在这样了

32、。对本例对本例 题的题的分析分析第40页，本讲稿共63页n任何一个二元任何一个二元(n,k)线性分组码都有线性分组码都有2n-k个伴个伴随式，假如该码的纠错能力是随式，假如该码的纠错能力是t，则对于任，则对于任何一个重量小于等于何一个重量小于等于t的差错图案，都应有的差错图案，都应有一个伴随式与之对应，也就是说，伴随式一个伴随式与之对应，也就是说，伴随式的数目满足条件的数目满足条件 n上式称作上式称作汉明限汉明限，任何一个纠，任何一个纠t码都应满足码都应满足上述条件。上述条件。完备码(Perfect code)第41页，本讲稿共63页完备码 某二元某二元(n,k)线性分组码能使等式线性分组码能

33、使等式 成成立立，即即该该码码的的伴伴随随式式数数目目不不多多不不少少恰恰好好和和不不大大于于t个个差差错错的的图图案案数数目目相相等等，相相当当于于在在标标准准译译码码阵阵列列中中能能将将所所有有重重量量不不大大于于t的的差差错错图图案案选选作作陪陪集集首首，而而没没有有一一个个陪陪集集首首的的重重量量大大于于t，这这时时的的校校验验位位得得到到最最充充分分的的利利用用。这这样样的的二二元元(n,k)线线性性分分组组码码称称为为完备码完备码。第42页，本讲稿共63页汉明码(Hamming Code)n汉明码不是指一个码，而是代表一类码。汉明码不是指一个码，而是代表一类码。n汉汉明明码码的的纠

34、纠错错能能力力t=1，既既有有二二进进制制的的，也也有有非非二二进进制制的的。二二进进制制时时，汉汉明明码码码码长长n和和信信息息位位k服服从从以以下下规规律律：(n,k)=(2m-1,2m-1-m)其中其中m=n-k，是正整数。，是正整数。n当当m3、4、5、6、7、8时时，有有汉汉明明码码(7,4)、(15,11)、(31,26)、(63,57)、(127,120)、(255,247)。n汉明码是完备码，因为它满足上述等式。汉明码是完备码，因为它满足上述等式。第43页，本讲稿共63页汉明码校验矩阵的构成 汉明码的校验矩阵汉明码的校验矩阵H具有特殊的性质，能使构具有特殊的性质，能使构造方法简

35、化。一个造方法简化。一个(n,k)码的校验矩阵有码的校验矩阵有nk行和行和n列，二进制时列，二进制时n-k个码元所能组成的列矢量总数是个码元所能组成的列矢量总数是2n-k-1,恰好和校验矩阵的列数恰好和校验矩阵的列数n=2m-1相等。只要排列所有相等。只要排列所有列，通过列置换将矩阵列，通过列置换将矩阵H转换成系统形式，就可以进转换成系统形式，就可以进一步得到相应的生成矩阵一步得到相应的生成矩阵G。第44页，本讲稿共63页例例 构造一个构造一个m=3的二元的二元(7，4)汉明码。汉明码。解解：先先利利用用汉汉明明码码的的特特性性构构造造一一个个(7，4)汉汉明明码码的的校校验验矩矩阵阵H，再通

36、过列置换将它变为系统形式：，再通过列置换将它变为系统形式：0 0 0 1 1 1 1 列置换列置换 1 1 1 0 1 0 0 H=0 1 1 0 0 1 1 0 1 1 1 0 1 0 =PT I3 1 0 1 0 1 0 1 1 1 0 1 0 0 1再得生成矩阵再得生成矩阵G为为 1 0 0 0 1 0 1 G=I4 P=0 1 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0 1 0 1 1 第45页，本讲稿共63页1、循环码的多项式描述2、循环码的生成多项式3、系统循环码4、多项式运算电路5、循环码的编码电路6、循环码的译码7、循环汉明码8、缩短循环码第4节循环码第46页，

37、本讲稿共63页(1)循环码的性质n循环码是线性分组码的一个重要子类；n由于循环码具有优良的代数结构，使得可用简单的反馈移位寄存器实现编码和伴随式计算，并可使用多种简单而有效的译码方法；n循环码是研究最深入、理论最成熟、应用最广泛的一类线性分组码。第4节循环码第47页，本讲稿共63页(2)循环码的定义n循环码：如果(n,k)线性分组码的任意码矢C=(Cn1,Cn2,C0)的i 次循环移位，所得矢量C(i)=(Cn1i,Cn2i,C0,Cn1,Cni)仍是一个码矢，则称此线性码为(n,k)循环码。第4节循环码第48页，本讲稿共63页(3)码多项式n码多项式：为了运算的方便，将码矢的各分量作为多项式

38、的系数，把码矢表示成多项式，称为码多项式。其一般表示式为C(x)=Cn1xn1+Cn2xn2+C0)n码多项式i 次循环移位的表示方法记码多项式C(x)的一次左移循环为C(1)(x)，i 次左移循环为C(i)(x)第4节循环码第49页，本讲稿共63页n码多项式的模(xn+1)运算n0和1两个元素模2运算下构成域。第4节循环码第50页，本讲稿共63页n码矢 C 循环i 次所得码矢的码多项式nC(x)乘以x，再除以(xn+1)，得第4节循环码第51页，本讲稿共63页上式表明上式表明：码矢循环一次的码多项式码矢循环一次的码多项式 C(1)(x)是原码多项式是原码多项式 C(x)乘以乘以 x 除以除以

39、(xn+1)的余式。写作的余式。写作因此，因此，C(x)的的 i 次循环移位次循环移位 C(i)(x)是是 C(x)乘以乘以 xi 除以除以(xn+1)的余式，的余式，即即n结论结论：循环码的码矢的：循环码的码矢的 i 次循环移位等效于将码多项式乘次循环移位等效于将码多项式乘 xi 后再模后再模(xn+1)。第4节循环码第52页，本讲稿共63页(4)举例：举例：(7,3)循环码循环码可由任一个码矢，比如可由任一个码矢，比如(0011101)经过循环移位，经过循环移位，得到其它得到其它6个非个非0码矢；码矢；也可由相应的码多项式也可由相应的码多项式(x4+x3+x2+1)，乘以，乘以xi(i=1

40、,2,6)，再模，再模(x7+1)运算得到其它运算得到其它6个非个非0码多项式。移位过程和相应的多项式运算如表码多项式。移位过程和相应的多项式运算如表6.3.1所示。所示。第4节循环码第53页，本讲稿共63页第4节循环码第54页，本讲稿共63页(1)循环码的生成矩阵循环码的生成矩阵 在在(n,k)循环码的循环码的 2k 个码字中，取前个码字中，取前(k1)位皆为位皆为0的码字的码字 g(x)（其次数（其次数r=nk），再经），再经(k1)次循环移位，共得到次循环移位，共得到 k 个码字个码字:g(x),xg(x),xk1 g(x)这这 k 个码字显然是相互独立个码字显然是相互独立的，可作为码生

41、成矩阵的的，可作为码生成矩阵的 k 行，于是得到行，于是得到循环码的生成矩循环码的生成矩阵阵 G(x)第4节循环码第55页，本讲稿共63页(2)循环码的生成多项式循环码的生成多项式n码的生成矩阵一旦确定，码就确定了；码的生成矩阵一旦确定，码就确定了；n这就说明：这就说明：(n,k)循环码可由它的一个循环码可由它的一个(nk)次码多项式次码多项式 g(x)来确定；来确定；n所以说所以说 g(x)生成了生成了(n,k)循环码，因此循环码，因此称称 g(x)为码的生成多为码的生成多项式项式。第4节循环码第56页，本讲稿共63页(3)生成多项式生成多项式和和码多项式码多项式的关系的关系n定理定理：在在

42、(n,k)循环码中，生成多项式循环码中，生成多项式 g(x)是是惟一的惟一的(nk)次码多项式，且次数是最低的次码多项式，且次数是最低的。n定理定理：在：在(n,k)循环码中，每个码多项式循环码中，每个码多项式 C(x)都是都是 g(x)的倍式；而每个为的倍式；而每个为 g(x)倍式且次数小倍式且次数小于或等于于或等于(n1)的多项式，必是一个码多项式的多项式，必是一个码多项式。第4节循环码第57页，本讲稿共63页n定理定理6.3.3(定理定理6.3.2的逆定理的逆定理)：在一个在一个(n,k)线性码线性码中，如果全部码多项式都是最低次的中，如果全部码多项式都是最低次的(nk)次次码多项式的倍

43、式，则此线性码为一个码多项式的倍式，则此线性码为一个(n,k)循环循环码码。第4节循环码第58页，本讲稿共63页n码字循环关系图n单纯循环码的码字循环图：(7,3)循环码第4节循环码第59页，本讲稿共63页n推广循环码的码字循环图：(6,3)循环码第4节循环码第60页，本讲稿共63页(4)如何寻找一个合适的生成多项式如何寻找一个合适的生成多项式n由下面式子可知：循环码的多项式等于信息多项式乘以生成多项式。由下面式子可知：循环码的多项式等于信息多项式乘以生成多项式。这说明这说明：对一个循环码只要生成多项式一旦确定，码就确定了，：对一个循环码只要生成多项式一旦确定，码就确定了，编码问题就解决了。编

44、码问题就解决了。所以所以：作一循环码的关键，就在于寻找一个适当的生成多项式作一循环码的关键，就在于寻找一个适当的生成多项式。第61页，本讲稿共63页n定理：(n,k)循环码的生成多项式循环码的生成多项式 g(x)是是(xn+1)的因式，即的因式，即 xn+1=h(x)g(x)。n定理：若若 g(x)是一个是一个(nk)次次 多项式，且为多项式，且为(xn+1)的因式，则的因式，则 g(x)生成一个生成一个(n,k)循环码循环码。结论：当求作一个当求作一个(n,k)循环码时，只要分解多项循环码时，只要分解多项式式(xn+1)，从中取出，从中取出(nk)次因式作生成多项次因式作生成多项式即可式即可。第4节循环码第62页，本讲稿共63页n举例举例：求：求(7,3)循环码的生成多项式。循环码的生成多项式。解解：分解多项式分解多项式 xn+1，取其，取其4次因式作生成多项式次因式作生成多项式x7+1=(x+1)(x3+x2+1)(x3+x+1)可将一次和任一个三次因式的乘积作为生成多项式，可将一次和任一个三次因式的乘积作为生成多项式，因而可取因而可取 g1(x)=(x+1)(x3+x2+1)=x4+x2+x+1 或或 g2(x)=(x+1)(x3+x+1)=x4+x3+x2+1第4节循环码第63页，本讲稿共63页