信息论与编码七八九

1、第七章第七章 循环码循环码n循环码是一类最重要的线性码，已对其循环码是一类最重要的线性码，已对其进行了较深的研究。它具有严谨的代数进行了较深的研究。它具有严谨的代数结构，其性能易分析。目前已发现的大结构，其性能易分析。目前已发现的大部分线性码与循环码有密切关系。它们部分线性码与循环码有密切关系。它们之中的大部分码都可归结为循环码。之中的大部分码都可归结为循环码。n循环特性，编译电路，特别是编码电路循环特性，编译电路，特别是编码电路简单易于实现。简单易于实现。7.1 循环码与理想循环码与理想n一、基本概念一、基本概念 7.4汉明码的汉明码的H矩阵矩阵 交换各列交换各列10101011100110

2、1111000H 各行之间显然有循环特性各行之间显然有循环特性。110100011010001101H若若 ，则它的左（右）移循环移位所得到的，则它的左（右）移循环移位所得到的n重也是一个码字，具有这种性质的重也是一个码字，具有这种性质的n,k分组分组码称为循环码。由于码称为循环码。由于n,k线性分组码是线性分组码是n维线维线性空间性空间 中的一个中的一个k维子空间，因此维子空间，因此n,k 循循环码是环码是n维线性空间中的一个维线性空间中的一个k维循环子空间。维循环子空间。n定义：定义： n重子空间重子空间 ，对任何一个，对任何一个恒有恒有则称则称 循环子空间或循环码循环子空间或循环码HCC

3、 1nVnknVV,knnnVaaaV,021),.,(knnnnVaaaaV,10321),.,(knV,诱潋 蚱阈晕位 n赜珍 n诱洌咴珍心祸k肭n k伤n,诱心祸k 咴珍k咴珠肭n赱n,k珠肫 冯咝庵允腫n,夭腔鲭骗菲基媒膎螯捏 二、码的多项式描述.)(,)()(mod)(,)()()()(),.,( :0122110122110121的某一剩余类中并必在模项式相对应次的一个多上次数低于重都与中每一个即的不同剩余类中次多项式的多项式一定在模所有次数小于多项式重xFnPGFnVxFaxaxaxaxfxFxFnnaxaxaxaxfPGFaaaaannnnnnPnnnninn+=剩余类线性结合

4、代数空间维线性的剩余类构成一个则可以证明模即一个数乘若在该环上再定义项式剩余类环的剩余类构成一个多模运算下在模)()(,)()(,)(,)(012211nxFcaxcaxcaxcaxcaxFxFxFxFnnnnP+=倍元加法是一个理想的充要条件循环码子空间是一个循环其一个子空间结合代数中为模的剩余类线性以多项式定理.:)(,11 .1 .5)1(mod)()(,10120211201012211knknnnnnnnnnnnnnnVVxxaxaxaxaxaxaxaxxaaxaxaxaxa+=+=.,1)(2 . 1 . 5).(),)(,.码的生成元它是循环首一多项式理想的次数最低的非零一个剩余

5、类代数中是模定义循环码成一个理想由它的一切倍式生生成多项式多项式数最低的非零首一可在理想中找到一个次至少由此数所构成理想是由某一元素的倍nxxgxg。数等于数即循环码的信息元个一个主理想，理想的维，所以这是的生成元为且理想中只有一个次数代数中的一个理想。多项式剩余类线性结合它是模条件是：线性码是循环码的充要由此可知：倍式一定是码多项式。次的的倍式且每一个都是每一码多项式次单一多项式的循环码中，存在有唯一上的（定理kxgknxknxgnxgxcgxgxgxxgknkngGFnknknkn)(1,)(1)()()(,)2 . 1 . 70111+=).(| )()(2),(11,)(),1( |

6、)()(),()(11)(,)3 . 1 . 7xcxgxcxgknxkknxgxxgknxgxhxgxxxgkngGFnnnn是一个码组，则，若生成一个主理想。由此作生成元，次单一多项式的能除尽维循环码，就是找一个，找一个结论：循环码。生成一个一定则该次，且是若反之，的因式：一定是循环码的生成多项式上（定理），（），），（重为（相应中任选一个。与二次单一多项式，可在的找一能除尽循环码求）上（例1101000011010000110100001101)()()()(1)(1114,7)1)(1)(1(12.32323372337nxgxxgxxxgxgxxxgxxxxknxxxxxxxGF10

7、11000010110000101100001011G三、循环码的生成矩阵校验矩阵111111111211211222111101111)()()()()()(1kkknknkknknkkknknknknknknknknknknknkngxxgxxgxxgxxgxgxxgxxgxxgxxgxgxxxgxxgxxgxxggxgxgxgxgxhxgnx。的系数均为，由此式可知等式右边的个个0,)()()()(1.00.0000021010111101011110210) 1(1xxxhxhxhgxgxgxgxhxgxggggggggggggGnnkkknknknknnkknknkknknkn +=

8、nknknkkknkknknikniihhhhhhhhhHknhghghghghg*)()1(10)1(0000000)(110000000000,00循环码的即.,)(,),(),()()(.)(,)() 1()(00211110阵的每一行可得低次的系数次序多项式的所有以的互反多项式的系数决定完全由为码的校验多项式或HxhxhxxhxhxhxhxhxhxhxhHxgxxhGHHGknknkkkknTT+=四、系统码的构成knknknknkkkkknKxxmxxmxcxrrxrxrxrmxmxmxmxmxgxrxxmxcPIG)()()()()()()(mod0)()()(0111012211

9、校验多项式信息多项式相当于.)(,)(. 3;)(. 2);(. 1:)(为模的除法问题问题就是以循环码、系统码的编码得校验位各次系数取加法逆元再得除得余式然后用首先构信息组乘以生成的系统码要构造用xgxrxgxmxxxgknkn)()()()(100)(0010)(001,.,1)()()()(,.2 , 1)(mod2121knTkTTknTKkiiniiinikkniIxrxrxrIPHKIxrxrxrGkixrxxcxqxgkixgxxxr码多项式例题:7,4码10111111001110000100001000011)(1)(1)()(mod)(1)(2342435226123PJG

10、xxxrxxxxrxxxrxgxxxxrxxxgK100111001001110011101knTIPH7.2 由生成多项式的根定义分组码是奇数，码长因此在二进制循环码中奇数是无重根的条件是）上要保证（在条件是（无重根的充要上多项式（在定理码字多项式的根。的根必是的倍式，每一码多项式都是nnxGFqnxqGFxgxgnn,121),1)1 . 2 . 7)()(7.4 缩短循环码与准循环码。不一定存在有循环关系缩短循环码的码字之间列。可在原基础上去掉前列；行、可在原基础上去掉前编码电路相同。，生成多项式相同不比原循环码复杂。故纠错能力不差，实现校验码仍为缩短码。准线性子空间得到一作为码字，构成

11、一个的码字位信息位为循环码中前缩短循环码是取一、缩短循环码iHiiGxgknkiikinikikn)(,-)1 (,)(0,二、准循环与双循环就是准循环码。可以证明：缩短循环码循环码每个码字码元位置号。则称这类码为准循环码的一个码字，次后，得到的仍是该码左移或右移循环移位一码字线性分组码，若它的任一个定义1, 2 , 1)(mod,1 . 4 . 5000000nnimnniinmkmn15,220表双环循环码的准循环码。等价于环码。生成的码，称为双环循阵组成的（单位分阵）和定义：由两个循环矩阵kknPIGPIKK三、双循环码和准循环码的多项式表示就是准循环码。可以证明：缩短循环码循环码每个码

12、字码元位置号。则称这类码为准循环码的一个码字，次后，得到的仍是该码移位一码字左移或右移循环线性分组码，若它的任一个定义1, 2 , 1)(mod,1 . 4 . 5000000nnimnniinmkmn.1)(),(.的一个循环码代数中产生的模的用一个长为后跟随式可以看成一个信息多项kKxxPkxmcmPmPImmGc7.6 编码电路n参见参考书 循环移位电路nCRC生成多项式: R.SBCH分组码纠突发错误交织码 广泛使用的四种CRC多项式:P(x)局域网欧洲美国传输802132818116 61122457810111216222326325121621516231112IEEExxxxx

13、xxxxxxxxxCRCbitxxxCCITTCRCbitxxxCRCbitxxxxCRC检测特性:3216:. 5;. 4);1()(,. 3;)(,. 2;. 1、帧校验序列误大多数较大的猝发性错长度的猝发性错误任何其长度小于包含因式只要任何奇数个差错具有至少三项的因式只要所有双比特错误所有单个比特错误FCSFCSxxPxP第八章 循环码的译码)()()()(:.)()()()(,)(1 . 8&011101110111xmxcxExEexexexErxrxrxExcxRqcxcxcxcnnnnnn样得到正确的估计错误图译码器的任务是信道产生的错误图样译码器输入端得到的是进制信道后

14、经过发码循环码译码的一般原理mCCCxExRxExsxSxR.,0)()()()()()(:否则译码错误则正确若根据的伴随式计算译码步骤一、伴随式计算和错误检测)()()()().()()()()(mod()()()()(mod1)()()()(1),(: ,)(),(),(21012100112211xqxgxEgxqxgxRgxSxgxExExcxsxgxxxHxhxgxxgknEHHECHRSecrrrrrececececECRTTTnTnnTTTiiinnnnnn或得生成多项式为对循环码).()(mod0)()(, :)(mod0)()()()()()()(?0)()(0)(0)()(

15、)(00100 xExgxExSknknxgxsxgxExExxEknxgxExgxRxsxExgxsi的所有错误图样以及检测使突发错误的等于循环码至少能检测长度说明不恒等于则或若余式除法电路将则若除法得到的余式就是一个二、伴随式计算) 11)()()()()()(mod()()()()(1,1 , 0),()(mod()()()()(mod()(.),()(1)()(,)()(1 . 1 . 8:11nixExxxExExExgxSxaxSxRxanjxgxSxxSxRxxgxxSxSxSxSxxxRxRxRxSiajjjn图样，也是一个可纠正的错误移位的循环样，则是一个可纠正的错误图也就是

16、说若。所对应的伴随式乘。而任意多项式的伴随式推论：即时右移一位的结果输入在伴随式计算电路中无是模下的在循环移位则的伴随式是若定理tjjtjjqjnNjnqNtq1211) 1(11) 1(010001大为简化。使得错误图样识别电路个。有个错，则错误图样代表进制时，若码要纠正在作为此类错误的代表。的错误图样非位开头为行分类，并将第可根据这种循环关系进。也是可纠正的错误图样后，若为非系统码算电路得到续，可再加个伴随式计。为了使译码连第二组的级缓冲器后，才能接收移出个节拍，仅当第一组的共需从例中可知，译一组码识别电路，纠正一位错例：除法电路的问题之一。和实际应用中引人注目码理论研究译码方法，这正是纠

17、错寻找更为简单、巧妙的环码的其他特性，都较大，则必须利用循较小情况。若仅适合于错误图样代表的方法，利用组合逻辑线路识别杂性。路或组合逻辑电路的复找出错误图样的识别电于由伴随式备的复杂性，主要决定一般说来纠正码译码设)()()(2)(,xcxRnxRnxgtntn由组合逻辑决定。通用译码器。其复杂性（也称为梅吉特循环码的一般译码器。由以上讨论可得出系统。信息组商就是最终所需的估值除法电路，所得的再通过后，把说明译码器输出得由)()()( )( ).()( )()().()(1MeggitxmxgxcxcxgxcxmxgxmxcR(x)门 K级缓冲器伴随式计算电路1组合逻辑电路伴随式计算电路2)(

18、xC 扩展汉明码， 缩短循环码的译码都可以在原码译码电路的基础上加以修改而得到。8.2 捕错译码).(,)()().()()(mod()()()(, 0)(, 1)()(,)()()(mod()()()()(00112211xCxSxRxSxgxExsxExExEkntknxEexexExexexexExgxExExExRxsPPIknknPknknnnnnIPI了得到就进行了纠错减去只要把说明错误图样就是则位上个错误集中在校验元的即所有若一、原理较弱的码。和码长较短、纠错能力某些低码率纠单个随机错误码以及适用于纠突发错误码，knttnktknkntxxknxRxSknkn/:,.,.,),(

19、,)()(.,010或之间满足条件图样译码方法可纠正的错误才是这种位以内时个错全部集中在连续只有当所有捕错译码故称为然后再纠错位低次位码元段误捕获列把错的循环移位运算与过由于这种译码方法是通式的性质进行循环码的特点以及伴随就可用位码段以内任意的连续只要错误集中地出现在情况。种易于工程实现的特殊信息集译码的一必要条件。因此，它是译码的充分条件，而非信息集位码元无错，而这仅是中连续捕获译码要求接收码字由以上讨论知：例：译码电路此时的伴随式重量位以内的充要条件是：的最低次个错误集中在中已把循环码，捕获译码过程上的个错误的纠正定理ktxSWknxRtknqGFtii)()(,)(1 . 2 . 8个指

20、定的位置。以确定错误是否在某几须附加一些电路，为了实现这种运算必此时的错误图样。当然上，则也能确定某几个预先指定的位置同时使个别的错误进入个码元段内，能把大部分错误捕捉到译码过程中，若译码器二、捕获译码的修正kn 8.3软判决译码的基本原理 为了充分利用接收信号波形中的信息，使译码器能以更大的正确概率判决所发的码字，就把解调器输出的抽样电压进行分层和量化。因而由解调器输出到译码器的值不止两个，而有 个 -软判决译码。编码信道称为二进制输入， Q进制输出的离散信道。mQ2.,1010.,10,./,.,.,168.32,3-2-2-正好与一般译码相反能提供最佳的性能时但软译码在纠错后反而更坏则若

21、译码率为对信道质量有一定要求一般应用纠错码时卫星、无线的信道变化较大更适合用于中等纠错能力适合于中等码长普遍应用判决译码将越来越得到软益提高随着数字通信质量的日因此大似然译码要低的多比最但其译码器的复杂度却差不多与最大似然译码的性能所得到性能约一般若的增益能得到额外的硬译码决信息进行软译码时比译码器利用附加的软判通常NSviterbiorQdB。码器性能的影响并不大（均匀）量化时，对译代替线性的，因此用非线性量化由于似然函数是非线性）无限量化的性能。性能就可达到（或接近电平量化。其译码电平，最多量化电平数目：一般用概念一、软判决译码的基本、码元错误概率最低、码字错误概率最低码准则软译码中：两个

22、最佳译16821四、编码效益与软判决增益./,.,/:.,.,./000提出要求必须对在实际应用时共有的统所用纠错码的差错控制系这种门限效应是所有利性能更差说明用纠错码后编码增益为负很小时当由图可以看出而且与信噪比有关有关编码增益不仅与纠错码增益定义为此纠错码的编码少分贝数所能获得的信噪比的减相对没有应用时统后应用一特定的纠错码系在某一误码率下之间的关系图与误码率最有用的图表是信噪比在通信系统性能分析中NENEpNEbbeb.,).(2,8.3,log10.).21(lg10) 1(lg10.,则软判决增益超过此值信道但若为非码长、中等纠错能力中等软判决增益性能获得下电平量化和中等信噪比在软判

23、决增益比硬判决译码要好无限量化的软判决译码当高信噪比时增益未量化信道的渐进编码渐进编码增益有关最小距离及与码率渐进编码增益码增益高信噪比时所获得的编AWGNdBdBRdGdRtRGdRhshh=+=+=8.6 码字错误概率最小的软判决译码第九章 卷积码基础n卷积码有三种比较好的译码方法。n1、Massey门限n2、序列译码准最佳概率译码n3、1967年由Viterbi提出的Viterbi算法，是一种最大似然译码。9.1 基本概念.,3.,12.1.,02121杂性表示了卷积编码器的复互相约束的码元个数为编码约束长度、码段个数编码过程中相互约束的编码约束度、需存贮的单元时间输入信息组在编码器中编

24、码存贮、学上称为卷积运算这种运算在数也称连环码中的校验运算码段个而且也参与了后中的码元有关个码段与前不仅及其相应的码段信息组个时刻输入至编码器的第AmiiimiiiiiNNnNmmcccmcccmCmi码率通常要小，而和比分组码的和表示或卷积码通常用译码约束长度译码约束度一个一码信息元，通常子码才能收到段单位时间内收到的各根据以前的一段时间如子码。而且还要此时刻输入到译码器的在译码时，不仅要根据RnknknkNkNnmknNnNmmmmddddd0000000,001/,),(),(9.2 卷积码的矩阵和多项式描述.,)(, 0 , 0 ,000,001,010,111.?)(.,02100则

25、的延迟个码元位时间表示编码过程中一个单用延迟算子基本生成阵第一行位的结果右移它的每一行都是前一行无限多半无限阵生成矩阵一定相同卷积码的抗干扰性能不系统卷积码与非系统在同样的码参数下与分组码不同和生成矩阵一、卷积码的校验矩阵的矩阵和多项式表示仅介绍与代数译码有关nDggggnGMC方法表示码段各码元的生成也就确定则生成元确定只要子次高次数是卷积码的子生成元其最个多项式表示用如下个数字中的每一段的第段中前若把决定段的值完全由前.,1)(1)(1)(3,)3 , 2 , 1(,1,310000002)3, 1()2, 1()1 , 1(2102102102102102GmDDgDDgDgjjgggmggggmgggggggggggDDggG卷积码序列多项式码序列的函数也写成信息序列或变换函数卷积码生成多项式矩阵为的函数形式可写成码段0)001()011()100()101()111()()()1 ()()(.)11100(.),(1 ,1 , 1 )(),(),()(432221022210002)3, 1()2, 1()1 , 1(DDDDDCDCCDCCDDDmDmmDMDMmknDDDgDgDgDGDG0)001()011()100()101()111()(),(),()()()()()(.)(,)(, 2 , 1)(), 2 , 1