通信原理电子版讲义--信道编码（3）

19.2线性分组码信道编码：研究各种编码的方法和译码的方法。•编码器k个信息比特输入BSCn个信道比特输出译码器n个信道比特输出k个信息比特输出nkf1,01,0:knf1,01,0:编码器是一对一的映射，译码器是多对一的映射图中的编码器称做码，编码率是。kn,nk2线性分组码的主要性质•线性分组码:信息位和校验位之间的监督关系是线性的监督位能表示成信息的线性和形式•1。封闭性。任意两个码组的和还是许用的码组。•2。码的最小距离等于非零码的最小码重。•线性分组码:码的校验矩阵（监督矩阵）码的生成矩阵生成矩阵G与监督矩阵H的关系系统码与非系统码(码的等价性）对偶空间校验子S（伴随式、纠错）3问题：为了能纠一位错，k位信息至少需要多少位的监督信息？如何设计？•回顾：•偶校验码的监督关系：•S=1，传输出错；•S=0，无误传输•上式称为监督关系，S称为校验子。•对于分组码(n,k)，如希望用r=n-k个监督位构造出r个监督方程式来指示一位错码的n种可能位置，纠正错误，则要求或。nr1212rkr021...aaaSnn4举例:说明具体如何构造线性分组码•设:分组码(7,4)中，若要能纠正一位错码，要求监督码元数。现取如果取k=4，则可以确定n=7。•用3个校验子来确定传输的7个位置是否出错•假设传输时的码字为•如果与错码的位置对应如下:)(0123456ccccccc321SSS5传输时的码字与错码的位置关系如下321SSS321SSS0c1c5c2c6c3c错码位置错码位置001101010110100111011000无错4c6•根据上表•发送端编码时,信息位•监督位,根据信息位的取值按监督关系来确定•即:监督位应该使上三式的取值为0•得到：65421ccccS65312ccccS64303ccccS6543,,,cccc012,,ccc643065316542cccccccccccc7•给出信息位•根据上式可以算出监督位从而得到（7，4）的所有码组：3456cccc012ccc012ccc00000001000111000101110011000010101101001000111101011001010011011000010101101110101001100111110100011100011111113456cccc3456cccc012ccc8写成矩阵的形式•即0001001101010101100101110123456ccccccc0THC][1001101010101100101110123456cccccccCHknkknIPH)(9•H就称为（7，4）码的校验矩阵（或监督矩阵）。•只要监督矩阵确定，则编码时信息位与监督位的关系就确定了。•线性分组码的设计实际上是如何设计监督矩阵的问题。•写成另一种矩阵形式•变换得到3456012110110110111cccccccGUccccccccccc1101000101010001100101110001][34560123456)(knkkQIG643065316542cccccccccccc10•G称为码的生成矩阵。•如知道生成矩阵同样可以确定编码的码组。•上例中：•其中knkknIPH)(110110110111P)(knkkQIGTPQ11010101111111生成矩阵G与监督矩阵H的关系•线性分组码全部码字：•且•对于任何线性分组码而言，上述关系总是存在的：GUC0THC000TTTTHGGHUGH0THG12例：如果输入码组为0011，已知分组码的监督方程如下，求编码器输出码字。•解：•监督方程的矩阵形式：000034613562456aaaaaaaaaaaa0001001101010101100101110123456Taaaaaaa13•监督矩阵•注：H矩阵称为典型形式，各行一定是线性无关的。•一个非典型形式的经过运算可以化成典型形式，通过监督矩阵可以知道监督码和信息码的监督关系。rrkrrrIPH,10011010101011001011114•生成矩阵通过生成矩阵可以得到生成码组。•如果输入码组为00111101010111111000010000100001,QIGkTPQ0111100110101011111100001000010000111001100GA1100011001115•注：由这种方式得到的生成矩阵称为典型生成矩阵•由它产生的分组码必定为系统码•就是信息码字保持不变，监督位附加其后，每行一定是线性无关的，每行都是一个生成码组。16系统码与非系统码•假设信息位为:•编码后的码组为:•称这种码为系统码•系统码-----编码后前k个就是信息位，后n-k是监督位。•如果不存在上述关系，则称为非系统码。•上例的（7，4）码是系统码•只有系统码才有关系•系统码和非系统码都有性质•]...[21knnnccc]......[0121cccccknknnnTPQ0TGH17码的等价性•设两编码器，输出的码集合是C1、C2。•如(1)C1、C2集合相同，(2)C1、C2只是变换了比特顺序。称这两个编码器是等价的•等价性不涉及信息映射。•系统码可同一个非系统码等价（如果是线性的则一定能），•线性码有可能同一个非线性码等价。零空间、对偶码•若C是n维线性空间的一个k维子空间，则必存在一个的n-k维子空间H，它与C互为零空间。即CH，或CH=。•用校验矩阵H中行矢量张成的子空间是一个(n,n-k)线性分组码，它与码C互为对偶码19对偶码•在中任意找出k个线性不相关的向量就构成了一种（n，k）码。•任意找出（n－k）个线性不相关的向量就够成了一种（n，n－k）分组码。•对（n，k）码，给定G则会有一个H和它对应，H的各行是中的（n－k）个线性不相关的向量，所以可以用来构造一个（n，n－k）码，这个码叫做原来那个码的对偶码。•如果H和G（或者其行初等变换的结果）相等，则对偶码和原来的码是一样的，称自对偶。nGF2nGF220校验子S与错误图样•假设我们发送的码组为C，•接收到的码组为Y，则Y＝C＋e•错误图样•发送，收到y，•y中可能有些位置上和c不一样（有误码）。可以表示成Y＝C＋e。向量e叫错误图案，它指示哪些位置有错（e中值为1的位置），哪些位置没有错（e中值为0的位置）。•错误图案e是中的一个向量，有个可能的图案。CcnGF2n221校验子S（伴随式）•伴随式只和错误图案e有关，和发送内容c无关，故可用于译码器判断出错的位置。•伴随式s是r＝n－k维向量，总共有2k个不同的值。•如将接收到的Y按照设计的监督关系进行运算，•可以得到上例结果。•如设计使S的不同组合与错误e一一对应，则我们可以利用错误图样得到e，从而进行纠错译码。TTTeHHecyHs22陪集•陪集•给定e就能算出一个，但e和s不是一一对应的。若某个e算出的伴随式是s，则对任意，也算出相同的s。也就是说，有个不同的e对应着相同的s。•把所有的e按其伴随式的值排成一个标准阵列（94页表9.2.1）。排法是：所有相同s的e排成一行（这一行的所有e构成的集合叫给定s所对应的陪集），每行中码重最小的（即错误最少的图案）排在第一个（这个e叫这个陪集的陪集首）TeHsCc23译码器工作过程•(1)计算s•(2)根据s查出陪集首•（3）纠正错误24编码器与译码器•编码器25汉明码汉明码监督位为位，因此它可以组成个可能情况，其中一个为无错。因此可以监督码位共要纠正一个错误，必须满足最小码距•如果r位监督位所组成的校正子码组与误码图样一一对应，这种码组称为完备码（取等号时）rr212r12,12rknrr即3mind26扩展汉明码•如果在汉明码基础上，再加上一位对所有码字进行校验的监督位–监督码字由r位增加到r+1位–信息位不变•码长码结构•纠1位错，检测2位错•如（8，4），（16，11）rn2)12,2(rrr27扩展汉明码矩阵如(7,4)－(8,4)0001111HHE28缩短汉明码•(n,k)－(n-s,k-s)•如(15,11)－(12,8)监督矩阵Hs是将原H的前3列去掉•缩短汉明码的最小码距至少和原来码的码距相同，因为监督位没有变。